An asymptotically optimal solution for contextual bandit problem in adversarial setting

Abstract

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.

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.