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ı: Belirtilmemiş.
Ö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 Unıversıty Of Technology - Yenilenebilir enerji sistemleri ile entegre iki alanlı güç sisteminde yük frekans kontrolü için optimizasyon yöntemleri kıyaslaması
Comparison of optimization methods for load frequency control in a two-area power system integrated with renewable energy systems
FATİH DEMİRCAN
Yüksek Lisans
Türkçe
2025
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞEN DEMİRÖREN
- Experimental analysis of inkjet printed multi metal oxide photoelectrodes for water splitting applications
Su ayrıştırma uygulamaları için mürekkep püskürtme baskılı çoklu metal oksit fotoelektrotların deneysel analizi
GÜLSÜM EFSUN TEKNECİ
Yüksek Lisans
İngilizce
2020
Enerjiİzmir Yüksek Teknoloji EnstitüsüMalzeme Bilimi ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. ENGİN KARABUDAK
DR. ÖĞR. ÜYESİ UMUT ADEM