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. (Request a copy)

Abstract

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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Telecommunications
Faculty of Engineering and Natural Sciences
Depositing User: Hüseyin Özkan
Date Deposited: 29 Jul 2019 11:21
Last Modified: 26 Apr 2022 10:06
URI: https://research.sabanciuniv.edu/id/eprint/37445

Available Versions of this Item

Actions (login required)

View Item
View Item