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ı: Belirtilmemiş.
Ö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
- Adaptive inverse optimal controller design for non-affine nonlinear systems using machine learning techniques
makine öğrenmesi teknikleri kullanarak doğrusal ve afin olmayan sistemler için adaptif ters optimal kontrolör tasarımı
MUHAMMET EMRE SANCI
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. GÜLAY ÖKE GÜNEL
- Dynamics of structured populations and an optimal harvesting model
Yapılandırılmış popülasyonların dinamiği ve bir optimal ürün alma modeli
CELİL EKİCİ
Yüksek Lisans
İngilizce
1995
MatematikOrta Doğu Teknik ÜniversitesiPROF.DR. OKTAY ÇELEBİ
Y.DOÇ.DR. BİLLUR KAYMAKÇALAN
- 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
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. MÜJDE GÜZELKAYA
- Independent task assignment for heterogeneous systems
Heterojen sistemler için bağımsız iş atama
ERTUĞRUL KARTAL TABAK
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Doğru akım makinasının adaptif ve optimal kontrolunun pratik gerçeklenmesi
Practical implementation of optimal model reference adaptive control of direct current machine
VEDAT DEVECİ
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. M. KEMAL SARIOĞLU