Hierarchical Unimodal Bandits

Abstract

We study a multi-armed bandit problem with clustered arms and a unimodal reward structure, which has applications in millimeter wave (mmWave) communication, road navigation, etc. More specifically, a set of N arms are grouped together to form C clusters, and the expected reward of arms belonging to the same cluster forms a Unimodal function (a function is Unimodal if it has only one peak, e.g. parabola). First, in the setting when $C=1$ C = 1 , we propose an algorithm, SGSD (Stochastic Golden Search for Discrete Arm), that has better guarantees than the prior Unimodal bandit algorithm [Yu and Mannor 2011 ]. Second, in the setting when $C \ge 2$ C ≥ 2 , we develop HUUCB (Hierarchical Unimodal Upper Confidence Bound (UCB) algorithm), an algorithm that utilizes the clustering structure of the arms and the Unimodal structure of the rewards. We show that the regret upper bound of our algorithm grows as $O(\sqrt{CT\log (T)})$ O ( C T log ( T ) ) , which can be significantly smaller than UCB’s $O(\sqrt{NT\log (T)})$ O ( N T log ( T ) ) regret guarantee. We perform a multi-channel mmWave communication simulation to evaluate our algorithm. Our simulation results confirm the advantage of our algorithm over the UCB algorithm [Auer et al. 2002 ] and a two-level policy (TLP) proposed in prior works [Pandey et al. 2007 ].