Combinatorial multi armed bandits: Applications and analyses

Birbiriyle yakından ilişkili iki probleme odaklanıyoruz: Kolları olasılıksal olarak tetiklenen Kombinatorik Çok Kollu Haydut Problemi (KÇKHP) ve bir KÇKHP yaklaşımı getirdiğimiz Kontekst içeren Gerçek zamanlı Etki Maksimizasyonu Problemi (KGEMP). Kolları tetikleme olasılıklarının (KTO) pozitif olduğunu varsaydığımız KÇKHP probleminde, bu konularda sıklıkla çalışılan bir grup algoritmanın performans garantilerini bularak literatürdeki, KTOlar daha zayıf varsayımlar altındayken bulunan performans garantilerini geliştiriyoruz. Sonrasında ise bir gerçek hayat film önerisi sisteminde bu algoritmaları numerik olarak değerlendiriyoruz. KGEMP problemi için ise, öğrenicinin etki yayılımını bir bedel ödeyerek öğrendiği ve bu yolla, bütün dönemlerdeki toplam etkilenen düğüm sayısından gözlem bedel değeri çıkarılarak elde edilen amaç fonksiyonunu maksimize etmeye çalışan bir problem durumunu çalışıyoruz. Gerçek zamanlı olmayan Etki Maksimizasyonu problemi NP-Zor olduğundan, bir yaklaşım algoritmasını alt-rutin olarak kullanan bir KÇKHP problemi öneriyoruz. Etkileme olasılıklarının kontekstin Hölder-sürekli bir fonksiyonu olduğu durumda, pişmanlığın zamanın lineer bir fonksiyonunun altında kalacağını ispatlıyoruz. Dahası, pişmanlık için bir alt sınır bularak bulduğumuz üst sınırın elde edilebilecek en iyi üst sınır olduğunu kanıtlıyoruz. Numerik sonuçlarımız ile ise önerdiğimiz algoritmaların, gözlemlerin bedelsiz olduğu durumlarda bile literatürdeki en iyi algoritmalar ile başabaş bir performans gösterdiğini görüyoruz.