Title: Regional Multi-Armed Bandits,
Abstract: We consider a variant of the classic multi-armed bandit problem where the
expected reward of each arm is a function of an unknown parameter. The arms are
divided into different groups, each of which has a common parameter. Therefore,
when the player selects an arm at each time slot, information of other arms in
the same group is also revealed. This regional bandit model naturally bridges
the non-informative bandit setting where the player can only learn the chosen
arm, and the global bandit model where sampling one arms reveals information of
all arms. We propose an efficient algorithm, UCB-g, that solves the regional
bandit problem by combining the Upper Confidence Bound (UCB) and greedy
principles. Both parameter-dependent and parameter-free regret upper bounds are
derived. We also establish a matching lower bound, which proves the
order-optimality of UCB-g. Moreover, we propose SW-UCB-g, which is an extension
of UCB-g for a non-stationary environment where the parameters slowly vary over
time.