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 (2018) Asymptotically optimal contextual bandit algorithm using hierarchical structures. IEEE Transactions on Neural Networks and Learning Systems . ISSN 2162-237X (Print) 2162-2388 (Online) Published Online First

There is a more recent version of this item available.
Full text not available from this repository. (Request a copy)


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
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: 06 Aug 2018 11:04
Last Modified: 26 Apr 2022 09:57

Available Versions of this Item

Actions (login required)

View Item
View Item