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
- Tez No: 692691
- Danışmanlar: DOÇ. DR. CEM TEKİN
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 91
Özet
Tıkız bağlam uzaylarında bağlamsal birleşimsel çok-kollu değişken haydut problemi (CCV-MAB), eşzamanlı olarak tüm özgün özellikleri göz önünde bulundurularak, geniş bir yelpazede pratik problemleri çözmek için genel bir çerçeve sunarak ele alınmıştır. CCV-MAB iki yaklaşım kullanılarak çözülmüştür. İlk olarak, bağlam uzayı X'i 'benzer bölgelere' sıralı ayrıştıran ve bu bölgelere karşılık gelen benzer istatistikleri kaydeden uyarlanır ayrıklaştırma adlı yöntem kullanılmıştır. Beklenen ödül monotonluğu ve zayıf süreklilik varsayımları altında, beklenen ödül ve beklenen taban kolu sonuçları için, uyarlanır ayrıklaştırma kullanan ve tüm \epsilon>0 için \tilde{O} ( T^{(\bar{D}+1)/(\bar{D}+2) +\epsilon}) pişmanlığa sahip bir çevrimiçi öğrenme algoritması Uyarlanır Bağlamsal Birleşimsel Üst Güven Sınırı (ACC-UCB) önerilmiştir, \bar{D} X ile ilişkili yaklaşık eniyilik boyutunu temsil etmektedir. Bu boyut taban kolu varışlarının iyicilliğini ve beklenen ödül yapısını yakalar. İkinci olarak, beklenen taban kolu sonuçları Gauss süreci (GP) kullanılarak modellenmiştir. Bu sayede GP sonsalının düzgünlüğü kullanılarak uyarlanır ayrıklaştırma ihtiyacı ortadan kaldırılmıştır. Çalışmada \tilde{O}(K\sqrt{T \bar{\gamma}_T}) pişmanlığa sahip Çekirdek Üst Güven Sınırı ile İyimser Birleşimsel Öğrenme ve Eniyileme (O'CLOK-UCB) önerilmiştir. \bar{\gamma}_T ilk T turda görünen taban kolu bağlam kümesiyle ilişkili azami bilgi kazancı ve K tüm turlar arasında herhangi bir olurlu üstün kolun azami sayallığıdır. ACC-UCB'nin literatürdeki güncel algoritmalardan ve O'CLOK-UCB'un ACC-UCB'den üstünlüğü simülasyon ortamında gözlemlenmiştir.
Özet (Çeviri)
We consider the contextual combinatorial volatile multi-armed bandit (CCV-MAB) problem in compact context spaces, simultaneously taking into consideration all of its individual features, thus providing a general framework for solving a wide range of practical problems. We solve CCV-MAB using two approaches. First, we use the so called adaptive discretization technique which sequentially partitions the context space X into 'regions of similarity' and stores similar statistics corresponding to such regions. Under monotonicity of the expected reward and mild continuity assumptions, for both the expected reward and the expected base arm outcomes, we propose Adaptive Contextual Combinatorial Upper Confidence Bound (ACC-UCB), an online learning algorithm that uses adaptive discretization and incurs \tilde{O}(T^{(\bar{D}+1)/(\bar{D}+2)+\epsilon}) regret for any \epsilon>0, where \bar{D} represents the approximate optimality dimension related to X. This dimension captures both the benignness of the base arm arrivals and the structure of the expected reward. Second, we impose a Gaussian process (GP) structure on the expected base arms outcomes and thus, using the smoothness of the GP posterior, eliminate the need for adaptive discretization. We propose Optimistic Combinatorial Learning and Optimization with Kernel Upper Confidence Bounds (O'CLOK-UCB) which incurs \tilde{O}(K\sqrt{T\bar{\gamma}_T}) regret, where \bar{\gamma}_T is the maximum information gain associated with the set of base arm contexts that appeared in the first T rounds and K here is the maximum cardinality of any feasible super arm over all rounds. For both methods, we provide experimental results which conclude in the superiority of ACC-UCB over the previous state-of-the-art and of O'CLOCK-UCB over ACC-UCB.
Benzer Tezler
- 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 - 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
- Automatic detection of compound structures by joint selection of region groups from multiple hierarchical segmentations
Bileşik yapıların çoklu sıradüzensel bölütlemelerden bölge gruplarının ortaklaşa seçilmesiyle otomatik sezimi
HÜSEYİN GÖKHAN AKÇAY
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. SELİM AKSOY
- Proje yönetiminde kantitatif yöntemlerin uygulanması
The application of the quantitative methods in project management
ZİYA ULUKAN
- Ekstrüzyona dayalı yapımda yeniden yapılandırma süreçleri için kavramsal bir çerçeve
A conceptual framework for the reconfiguration processes in extrusion-based making
HÜLYA ORAL KARAKOÇ
Doktora
Türkçe
2021
Mimarlıkİstanbul Teknik ÜniversitesiBilişim Ana Bilim Dalı
PROF. DR. MERYEM BİRGÜL ÇOLAKOĞLU