Geri Dö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

  1. Tez No: 533766
  2. Yazar: ERALP TURĞAY
  3. Danışmanlar: DR. ÖĞR. ÜYESİ CEM TEKİN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  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. Combinatorial multi armed bandits: Applications and analyses

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

    ANIL ÖMER SARITAÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. SAVAŞ DAYANIK

    YRD. DOÇ. DR. CEM TEKİN

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

  4. Online anomaly detection with kernel density estimators

    Çekirdek yoğunluk tahmincileri ile çevrimiçi anomali tespiti

    MİNE KERPİÇÇİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

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

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

    PROF. DR. SÜLEYMAN SERDAR KOZAT

    YRD. DOÇ. DR. HÜSEYİN ÖZKAN

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

    İngilizce

    2017

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

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

    DOÇ. DR. SÜLEYMAN SERDAR KOZAT