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
- Tez No: 498467
- Danışmanlar: DOÇ. DR. SÜLEYMAN SERDAR KOZAT
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- 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ı: 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
- 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
2016
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. ŞENİZ ERTUĞRUL
- 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
2019
Elektrik ve Elektronik MühendisliğiHacettepe ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. BERKAN DÜLEK
- 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
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. MÜJDE GÜZELKAYA
- 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
2018
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SİNAN GEZİCİ