Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures
| Autor: | Huseyin Ozkan, Kaan Gokcesu, Mohammadreza Mohaghegh Neyshabouri, Hakan Gökcesu, Suleyman S. Kozat |
|---|---|
| Přispěvatelé: | Neyshabouri, Mohammadreza Mohaghegh, Gökçesu, Kaan, Gökçesu, Hakan, Özkan, Hüseyin, Kozat, Süleyman Serdar |
| Rok vydání: | 2019 |
| Předmět: |
linear prediction
Computational complexity theory Computer Networks and Communications Computer science online learning Context (language use) 02 engineering and technology multiclass classification Upper and lower bounds Multiclass classification Big data big data Artificial Intelligence 0202 electrical engineering electronic engineering information engineering contextual bandits Online algorithm multiarmed bandit tree estimation model Binary tree adversarial universal Lipschitz continuity Adversarial Computer Science Applications Computational complexity mixture Asymptotically optimal algorithm Online learning Contextual bandits 020201 artificial intelligence & image processing Algorithm Universal Software |
| Zdroj: | IEEE Transactions on Neural Networks and Learning Systems |
| ISSN: | 2162-2388 2162-237X |
| DOI: | 10.1109/tnnls.2018.2854796 |
| Popis: | We propose an online algorithm for sequential learning in the contextual multiarmed 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 algorithm 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 an efficient implementation for our algorithm using various hierarchical partitioning structures, such as lexicographical or arbitrary position splitting and binary trees (BTs) (and several other partitioning examples). For instance, in the case of BT 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 (with respect to 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 multiclass classification with real and synthetic data. In these experiments, we show that our algorithm is highly superior to the state-of-the-art techniques while maintaining the introduced mathematical guarantees and a computationally decent scalability. IEEE |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|