Contextual multi-armed bandits with structured payoffs
Yapılandırılmış getirili bağlamsal çok kollu haydutlar
- Tez No: 644344
- Danışmanlar: DR. ÖĞR. ÜYESİ CEM TEKİN
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 131
Özet
Çok kollu haydut (MAB) problemleri belirsizlik altında sıralı karar verme işlemini modellerler. Geleneksel MAB probleminde, öğrenici her turda bir kol seçer ve ardından seçilen kolun bilinmeyen ödül dağılımdan rastgele bir ödül gözlemler. Öğrenicinin amacı en yüksek ödülü veren kolları seçmeyi öğrenerek toplam ödülü ençoklamaktır. MAB'nin bir uzantısı olan bağlamsal MAB probleminde, öğrenici her turun başlangıcında bir bağlamı (yan bilgi) gözlemler, bir kol seçer ve dağılımı hem gelen bağlama hem de seçilen kola bağlı olan rastgele bir ödülü gözlemler. Başka bir MAB çeşidi olan tektepeli MAB'de ise beklenen ödülün kollar üzerinde tek tepeli bir yapı sergilediğini varsayar ve beklenen ödülün artış yönünü öğrenerek ``zirve'' ödüllü kolu tespit etmeye çalışır. Bu tezde, tek tepeli MAB probleminin bir uzantısı olan bağlamsal tek tepeli MAB problemi incelenmektedir ve bu modelin kollardaki ve bağlamlardaki yapılardan istifade ederek kablosuz iletişim alanında yapay zeka tabanlı radyo dizaynında güçlü bir araç olduğu gösterilmektedir. Yapay zeka özellikli telsizlerin, ağ kaynaklarını optimize etmeyi öğrenerek 5. nesil (5G) milimetre dalga (mmWave) ağlarının spektral verimliliğini artırması beklenmektedir. Ancak, kaynakların mmWave bandı üzerinden tahsis edilmesi, hızla değişen kanal koşulları nedeniyle son derece zordur. Bu tezde, bilinmeyen kanal istatistikleri altında ve herhangi bir kanal durum bilgisi (CSI) geri bildirimi olmaksızın mmWave radyo ağları için çeşitli tasarım olanakları altında çeşitli kaynak tahsisi problemleri ele alınmıştır: i) bir enerji hasat vericisi için dinamik oran seçimi, ii) heterojen uygulamalar için dinamik güç tahsisi ve iii) çok kullanıcılı bir ağda dağıtılmış kaynak tahsisi. Tüm bu problemlerde beklenen ödül hem kısmen sıralı kollar (iletişim parametreleri) üzerinde tek tepeli hem de kısmen sıralı bağlamlar (yan-bilgi) üzerinde tek tepeli veya monoton bir yapı sergilemektedir. Kolların üzerindeki yapı, keşfedilecek kolların sayısını azaltmaya yardımcı olurken, bağlamlar üzerindeki yapı, daha iyi seçimler yapmak için yakın bağlamlardan alınan geçmiş bilgileri kullanmaya yardımcı olur. Tez kapsamında iletişim parametrelerinin dinamik uyarlanması problemi yukarıda belirtilen özelliklere sahip yapılandırılmış getirili MAB olarak modellenmiş ve sıklıkçı ve Bayes tabanlı yaklaşımlara dayalı çevrimiçi öğrenme algoritmaları önerilmiştir. Bu algoritmaların pişmanlıklarının zamanda logaritmik olduğu kanıtlanmıştır. Tez kapsamında bunlar haricinde, dinamik olarak değişen kanal kullanılabilirliği ve gönderim hızı kısıtlamaları altında heterojen uygulamalara hizmet veren bilişsel bir radyo ağında dinamik hız ve kanal adaptasyonu problemi da ele alınmıştır. Problem bir Bayes öğrenme problemi olarak modellenmiş ve her bir hız-kanal çiftini iki boyutlu bir eylem olarak ele alan yeni bir öğrenme algoritması önerilmiştir. Bu problemde kullanılabilir eylemler kümesi, birincil kullanıcı etkinliğindeki ve ağ uygulamalarının gönderim hızı gereksinimlerindeki değişimler nedeniyle zaman içinde dinamik olarak değişir. Bunlara ek olarak, seçilebilen kol kümesinin sürekli olduğu durumları içeren senaryolar da çalışılmıştır. Son olarak, geliştirilen algoritmaların yukarıda belirtilen kaynak tahsisi problemlerinde performansı önemli ölçüde iyileştirdiğini simülasyonlar yoluyla da gösterilmiştir.
Özet (Çeviri)
Multi-Armed Bandit (MAB) problems model sequential decision making under uncertainty. In traditional MAB, the learner selects an arm in each round, and then, observes a random reward from the arm's unknown reward distribution. In the end, the goal is to maximize the cumulative reward by learning to select optimal arms as much as possible. In the contextual MAB---an extension to MAB---the learner observes a context (side-information) in the beginning of each round, selects an arm, and then, observes a random reward whose distribution depends on both the arriving context and the chosen arm. Another MAB variant, called unimodal MAB, assumes that the expected reward exhibits a unimodal structure over the arms, and tries to locate the arm with the ``peak" reward by learning the direction of increase of the expected reward. In this thesis, we consider an extension to unimodal MAB called contextual unimodal MAB, and demonstrate that it is a powerful tool for designing Artificial Intelligence (AI)-enabled radios by utilizing the special structure of the dependence of the reward to contexts and arms of the wireless environment. While AI-enabled radios are expected to enhance the spectral efficiency of 5th generation (5G) millimeter wave (mmWave) networks by learning to optimize network resources, allocating resources over the mmWave band is extremely challenging due to rapidly-varying channel conditions. We consider several resource allocation problems in this thesis under various design possibilities for mmWave radio networks under unknown channel statistics and without any channel state information (CSI) feedback: i) dynamic rate selection for an energy harvesting transmitter, ii) dynamic power allocation for heterogeneous applications, and iii) distributed resource allocation in a multi-user network. All of these problems exhibit structured payoffs which are unimodal functions over partially ordered arms (transmission parameters) as well as unimodal or monotone functions over partially ordered contexts (side-information). Structure over arms helps in reducing the number of arms to be explored, while structure over contexts helps in using past information from nearby contexts to make better selections. We formalize dynamic adaptation of transmission parameters as a structured MAB, and propose frequentist and Bayesian online learning algorithms. We show that both approaches yield logarithmic in time regret. We also investigate dynamic rate and channel adaptation in a cognitive radio network serving heterogeneous applications under dynamically varying channel availability and rate constraints. We formalize the problem as a Bayesian learning problem, and propose a novel learning algorithm which considers each rate-channel pair as a two-dimensional action. The set of available actions varies dynamically over time due to variations in primary user activity and rate requirements of the applications served by the users. Additionally, we extend the work to cater to the scenario when the arms belong to a continuous interval as well as the contexts. Finally, we show via simulations that our algorithms significantly improve the performance in the aforementioned radio resource allocation problems.
Benzer Tezler
- 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
- An asymptotically optimal solution for contextual bandit problem in adversarial setting
Çekişmeli ortamlarda bağlamsal haydut problemi için asimptotik olarak en uygun çözüm
MOHAMMADREZA MOHAGHEGH NEYSHABOURI
Yüksek Lisans
İngilizce
2018
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. SÜLEYMAN SERDAR KOZAT
- Personalizing treatments via contextual multi-armed bandits by identifying relevance
İlgi belirleyerek bağlamsal çok kollu haydutlar ile tedavileri kişiselleştirme
CEM BULUCU
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ CEM TEKİN
- Algorithms and regret bounds for multi-objective contextual bandits with similarity information
Benzerlik bilgisine sahip çok amaçlı bağlamsal haydut problemlerinde pişmanlık sınırları ve algoritmalar
ERALP TURĞAY
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ CEM TEKİN
- Combinatorial multi armed bandits: Applications and analyses
Kombınatorık çok kollu haydutlar: Uygulamalar ve analızler
ANIL ÖMER SARITAÇ
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SAVAŞ DAYANIK
YRD. DOÇ. DR. CEM TEKİN