Asymptotically optimal contextual bandit algorithm using hierarchical structures

Neyshabouri, Mohammadreza Mohaghegh and Gökçesu, Kaan and Gökçesu, Hakan and Özkan, Hüseyin and Kozat, Süleyman Serdar (2019) Asymptotically optimal contextual bandit algorithm using hierarchical structures. IEEE Transactions on Neural Networks and Learning Systems, 30 (3). pp. 923-937. ISSN 2162-237X (Print) 2162-2388 (Online)

This is the latest version of this item.

Full text not available from this repository.

Official URL: http://dx.doi.org/10.1109/TNNLS.2018.2854796


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.

Item Type:Article
Uncontrolled Keywords:Adversarial; big data; contextual bandits; multiclass classification; online learning; universal
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5101-6720 Telecommunication
ID Code:37445
Deposited By:Hüseyin Özkan
Deposited On:29 Jul 2019 11:21
Last Modified:29 Jul 2019 11:21

Available Versions of this Item

Repository Staff Only: item control page