Geri Dön

Combinatorial multi armed bandits: Applications and analyses

Kombınatorık çok kollu haydutlar: Uygulamalar ve analızler

  1. Tez No: 527460
  2. Yazar: ANIL ÖMER SARITAÇ
  3. Danışmanlar: PROF. DR. SAVAŞ DAYANIK, YRD. DOÇ. DR. CEM TEKİN
  4. Tez Türü: Yüksek Lisans
  5. 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
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
  13. 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

  1. 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

    İngilizce

    2022

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CEM TEKİN

  2. 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

    İngilizce

    2021

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CEM TEKİN

  3. 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

    İngilizce

    2023

    BiyokimyaDokuz Eylül Üniversitesi

    Genom Bilimleri ve Moleküler Biyoteknoloji Ana Bilim Dalı

    DOÇ. DR. SİNAN GÜVEN

    DR. SİBEL KALYONCU UZUNLAR

  4. 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

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Uçak ve Uzay Mühendisliği Ana Bilim Dalı

    DOÇ. DR. NAZIM KEMAL ÜRE