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
- Tez No: 533766
- Danışmanlar: DR. ÖĞR. ÜYESİ 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: 2019
- 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ı: 93
Özet
Bağlamsal haydut algoritmalarının, bilişsel radyo ağlarından tavsiye sistemlerine ve tıbbi tanıya kadar, belirsiz ortamlarda sıralı karar verme problemlerini çözmede etkili olduğu gösterilmiştir. Bu uygulamaların birçoğu birden fazla ve muhtemelen birbiriyle çelişen amaçlar içerir. Bu tezde, bağlamsal haydut problemlerinin bir uzantısı olan benzerlik bilgisine sahip çok amaçlı bağlamsal haydut problemleri ele alınmıştır. Öğrenicinin seçtiği her kol için rastgele bir skaler ödül aldığı tek amaçlı bağlamsal haydut problemlerinin aksine, çok amaçlı bağlamsal haydut problemlerinde, öğrenici seçtiği her kol için rastgele bir ödül vektörü elde eder. Bu ödül vektörünün her bir elemanı bir amaca karşılık gelir ve ödül vektörünün dağılımı, o turun başlangıcında gözlemlenen bağlama bağlıdır. İlk olarak, bu tezde, bu yapıya uyan, amaçlardan birinin diğer amaca baskın olduğu, iki amaçlı, benzerlik bilgisine sahip yeni bir çok amaçlı bağlamsal haydut problemi tanımlanmıştır. Burada, öğrenicinin amacı, baskın olan amaçtaki toplam ödülünü en üst düzeye çıkardığından emin olmak kaydıyla baskın olmayan amaçtaki toplam ödülünü en üst düzeye çıkarmaktır. Bu problem için bir çok amaçlı bağlamsal haydut algoritması (the multi-objective contextual multi-armed bandit algorithm veya kısaca MOC-MAB) önerilmiştir ve iki farklı performans ölçütü tanımlanmıştır: 2-boyutlu (2D) pişmanlık ve Pareto pişmanlık. Ardından, MOC-MAB'ın hem 2D pişmanlığının hem de Pareto pişmanlığının, tur sayısının altdoğrusal bir fonksiyonu olduğu gösterilmiştir. Ayrıca MOC-MAB'ın sentetik ve gerçek dünya veri kümelerindeki performansı değerlendirilmiştir. Bir sonraki problemde, rastgele sayıda amaca ve benzerlik bilgisine sahip, aynı zamanda yüksek boyutlu ve muhtemelen sayılamayan bir kol kümesi bulunduran çok amaçlı bağlamsal haydut problemi ele alınmıştır. Pareto Contextual Zooming (PCZ) adında bir çevrimiçi öğrenme algoritması önerilmiş ve PCZ'nin Pareto pişmanlığının, tur sayısının altdoğrusal bir fonksiyonu olduğu ve bu fonksiyounun optimuma yakın olduğu gösterilmiştir.
Özet (Çeviri)
Contextual bandit algorithms have been shown to be effective in solving sequential decision making problems under uncertain environments, ranging from cognitive radio networks to recommender systems to medical diagnosis. Many of these real world applications involve multiple and possibly conflicting objectives. In this thesis, we consider an extension of contextual bandits called multi objective contextual bandits with similarity information. Unlike single-objective contextual bandits, in which the learner obtains a random scalar reward for each arm it selects, in the multi-objective contextual bandits, the learner obtains a random reward vector, where each component of the reward vector corresponds to one of the objectives and the distribution of the reward depends on the context that is provided to the learner at the beginning of each round. For this setting, first, we propose a new multi-objective contextual multi-armed bandit problem with similarity information that has two objectives, where one of the objectives dominates the other objective. Here, the goal of the learner is to maximize its total reward in the non-dominant objective while ensuring that it maximizes its total reward in the dominant objective. Then, we propose the multi-objective contextual multi-armed bandit algorithm (MOC-MAB), and define two performance measures: the 2-dimensional (2D) regret and the Pareto regret. We show that both the 2D regret and the Pareto regret of MOC-MAB are sublinear in the number of rounds. We also evaluate the performance of MOC-MAB in synthetic and real-world datasets. In the next problem, we consider a multi-objective contextual bandit problem with an arbitrary number of objectives and a high-dimensional, possibly uncountable arm set, which is endowed with the similarity information. We propose an online learning algorithm called Pareto Contextual Zooming (PCZ), and prove that it achieves sublinear in the number of rounds Pareto regret, which is near-optimal.
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
- 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
- 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 anomaly detection with kernel density estimators
Çekirdek yoğunluk tahmincileri ile çevrimiçi anomali tespiti
MİNE KERPİÇÇİ
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SÜLEYMAN SERDAR KOZAT
YRD. DOÇ. DR. HÜSEYİN ÖZKAN
- Online minimax optimal density estimation and anomaly detection in nonstationary environments
Durağan olmayan ortamlarda çevrimiçi minimaks optimal yoğunluk tahmini ve anomali tespiti
KAAN GÖKCESU
Yüksek Lisans
İngilizce
2017
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. SÜLEYMAN SERDAR KOZAT