Combinatorial multi armed bandits: Applications and analyses
Kombınatorık çok kollu haydutlar: Uygulamalar ve analızler
- Tez No: 527460
- Danışmanlar: PROF. DR. SAVAŞ DAYANIK, YRD. DOÇ. DR. CEM TEKİN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Endüstri ve Endüstri Mühendisliği, Computer Engineering and Computer Science and Control, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 115
Özet
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.
Özet (Çeviri)
We focus on two related problems: Combinatorial multi-armed bandit problem (CMAB) with probabilistically triggered arms (PTAs) and Online Contextual Influence Maximization Problem with Costly Observations (OCIMP-CO) where we utilize a CMAB approach. Under the assumption that the arm triggering probabilities (ATPs) are positive for all arms, we prove that a class of upper confidence bound (UCB) policies, named Combinatorial UCB with exploration rate κ (CUCB-κ), and Combinatorial Thompson Sampling (CTS), which estimates the expected states of the arms via Thompson sampling, achieve bounded gapdependent and O( √ T) gap-independent regret improving on previous works which study CMAB with PTAs under more general ATPs. Then, we numerically evaluate the performance of CUCB-κ and CTS in a real-world movie recommendation problem. For the Online Contextual Influence Maximization Problem with Costly Observations, we study a case where the learner can observe the spread of influence by paying an observation cost, by which it aims to maximize the total number of influenced nodes over all epochs minus the observation costs. Since the offline influence maximization problem is NP-hard, we develop a CMAB approach that use an approximation algorithm as a subroutine to obtain the set of seed nodes in each epoch. When the influence probabilities are Hölder continuous functions of the context, we prove that these algorithms achieve sublinear regret (for any sequence of contexts) with respect to an approximation oracle that knows the influence probabilities for all contexts. Moreover, we prove a lower bound that matches the upper bound with respect to time and cost order, suggesting that the upper bound is the best possible. Our numerical results on several networks illustrate that the proposed algorithms perform on par with the state-of-the-art methods even when the observations are cost-free.
Benzer Tezler
- Multi-armed bandit algorithms for communication networks and healthcare
İletişim ağları ve sağlık uygulamaları için çok kollu haydut algoritmaları
İLKER DEMİREL
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEM TEKİN
- Contextual combinatorial volatile multi-armed bandits in compact context spaces
Tıkız bağlam uzaylarında bağlamsal birleşimsel değişken çok-kollu haydut
ANDI NIKA
Yüksek Lisans
İngilizce
2021
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEM TEKİN
- Online learning for energy efficient navigation using contextual information
Başlık çevirisi yok
YONCA YUNATCI
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolChalmers University of Technology - Development of anti-cancer antibody fragments with improved characteristics through antibody engineering approaches
Antikor mühendisliği yaklaşımları ile iyileştirilmiş özelliklere sahip anti-kanser antikor fragmanlarının geliştirilmesi
MERVE ARSLAN
Doktora
İngilizce
2023
BiyokimyaDokuz Eylül ÜniversitesiGenom Bilimleri ve Moleküler Biyoteknoloji Ana Bilim Dalı
DOÇ. DR. SİNAN GÜVEN
DR. SİBEL KALYONCU UZUNLAR
- Multi agent planning under uncertainty using deep Q-networks
Derin Q-ağları kullanımı ile belirsizlik altında çoklu ajan planlaması
FARABİ AHMED TARHAN
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. NAZIM KEMAL ÜRE