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

  1. Tez No: 498467
  2. Yazar: MOHAMMADREZA MOHAGHEGH NEYSHABOURI
  3. Danışmanlar: DOÇ. DR. SÜLEYMAN SERDAR KOZAT
  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: 2018
  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ı: 56

Özet

Bağlamsal çok silahlı haydut algoritması çerçevesinde sıralı öğrenme için çevrimiçi algoritmalar öneriyoruz. Yaklaşımımız, bağlam uzayını bölmek ve daha sonra, bölünen kısımları ve haydut kolları arasındaki olası tüm eşleştirmeleri değerlendirerek, bunları veri odaklı bir şekilde en uygun şekilde birleştirmektir. Bizim yaklaşımımızda, en iyi haritalamanın, en iyi kol seçim politikasını, rahat Lipschitz koşullarında istenen herhangi bir dereceye kadar tahmin edebileceğini gösteriyoruz. Bu nedenle algoritmalarımızı en uygun uyarlanır kombinasyona göre tasarlıyoruz ve en iyi haritalama performansının yanı sıra en iyi kol seçim politikasını asimptotik olarak gerçekleştiriyoruz. Bu en iyilemenin, aynı zamanda, çekişmeli ortamlarda bile sağlanması garanti altına alınmaktadır çünkü bağlamlar veya haydut kollarının hatası ile ilgili herhangi bir istatistiksel varsayıma dayanmıyoruz. Ayrıca, algoritmalarımız için, sözlüksel veya rasgele bir şekilde bölme ve ikili ağaçlar (ve diğer birkaç bölümleme örnekleri) gibi çeşitli hiyerarşik bölümleme yapılarında verimli uygulamalar tasarlıyoruz. Örneğin, ikili ağaç bölümlemesi durumunda, hesaplama karmaşıklığı, en iyi bölümdeki bölgelerin sayısında logaritmik olarak doğrusaldır. Sonuç olarak, son teknoloji ile kıyaslandığında, her tur başına ortalama kayıpta matematiksel olarak kanıtlanmış olan üst sınırları (en iyi kol seçim politikası) tanıtarak önemli performans iyileştirmeleri sağlamaktayız. Deneysel çalışmalarımız, haydut düzeninden gerçek ve sentetik verilere sahip çok sınıflı sınıflamaya kadar çeşitli senaryoları kapsamaktadır. Bu deneylerde, sunulan matematiksel garantileri ve hesaplanabilir ölçeklenebilirliği korurken, algoritmalarımızın en son teknolojilerden oldukça üstün olduğunu göstermekteyiz.

Özet (Çeviri)

We propose online algorithms for sequential learning in the contextual multi-armed bandit setting. Our approach is to partition the context space and then optimally combine all of the possible mappings between the partition regions and the set of bandit arms in a data driven manner. We show that in our approach, the best mapping is able to approximate the best arm selection policy to any desired degree under mild Lipschitz conditions. Therefore, we design our algorithms based on the optimal adaptive combination and asymptotically achieve the performance of the best mapping as well as the best arm selection policy. This optimality is also guaranteed to hold even in adversarial environments since we do not rely on any statistical assumptions regarding the contexts or the loss of the bandit arms. Moreover, we design efficient implementations for our algorithms in various hierarchical partitioning structures such as lexicographical or arbitrary position splitting and binary trees (and several other partitioning examples). For instance, in the case of binary tree partitioning, the computational complexity is only log-linear in the number of regions in the finest partition. In conclusion, we provide significant performance improvements by introducing upper bounds (w.r.t. the best arm selection policy) that are mathematically proven to vanish in the average loss per round sense at a faster rate compared to the state-of-the-art. Our experimental work extensively covers various scenarios ranging from bandit settings to multi-class classification with real and synthetic data. In these experiments, we show that our algorithms are highly superior over the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability.

Benzer Tezler

  1. Hızlıca keşfeden rastgele ağaç yöntemi ile insansı robot kolu yörünge planlaması

    Trajectory planning of a humanoid robot arm by using rapidly-exploring randomized tree method

    BURAK BOYACIOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. ŞENİZ ERTUĞRUL

  2. Parametre belirsizliği altında çoklu algılayıcılara ait bağımlı ölçümlerle hiıpotez sınaması

    Hypothesis testing with dependent observations of multiple sensors in the presence parameter uncertainty

    SELİN IŞIK

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Elektrik ve Elektronik MühendisliğiHacettepe Üniversitesi

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

    DOÇ. DR. BERKAN DÜLEK

  3. Doğrusal olmayan sistemler için model öngörülü kontrol yöntemine ters optimal kontrol yapısının katılması

    Injection of inverse optimal control structure to model predictive control method for non-linear systems

    LÜTFİ ULUSOY

    Doktora

    Türkçe

    Türkçe

    2021

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

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    PROF. DR. MÜJDE GÜZELKAYA

  4. Visible light positioning systems: Fundamental limits, algorithms and resource allocation approaches

    Görünür ışık konumlandırma sistemleri: Temel sınırlar, algoritmalar ve kaynak tahsisi yaklaşımları

    MUSA FURKAN KESKİN

    Doktora

    İngilizce

    İngilizce

    2018

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

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

    PROF. DR. SİNAN GEZİCİ

  5. Essays on service systems with matching

    Başlık çevirisi yok

    ERHUN ÖZKAN

    Doktora

    İngilizce

    İngilizce

    2018

    Kamu YönetimiUniversity of Southern California

    DR. AMY R. WARD