Optimal Strategies for Graph-Structured Bandits
We study a structured variant of the multi-armed bandit problem specified by a set of Bernoulli distributions ν=(ν_a,b)_a∈A,b∈B with means (μ_a,b)_a∈A,b∈B∈[0,1]A×B and by a given weight matrix ω=(ω_b,b′)_b,b′∈B, where A is a finite set of arms and B is a finite set of users. The weight matrix ω is such that for any two users b,b′∈B,max_a∈A∣μ_a,b−μ_a,b′∣≤ω_b,b′. This formulation is flexible enough to capture various situations, from highly-structured scenarios (ω∈{0,1}B×B) to fully unstructured setups (ω≡1).We consider two scenarios depending on whether the learner chooses only the actions to sample rewards from or both users and actions. We first derive problem-dependent lower bounds on the regret for this generic graph-structure that involves a structure dependent linear programming problem. Second, we adapt to this setting the Indexed Minimum Empirical Divergence (IMED) algorithm introduced by Honda and Takemura (2015), and introduce the IMED-GS⋆ algorithm. Interestingly, IMED-GS⋆ does not require computing the solution of the linear programming problem more than about log(T) times after T steps, while being provably asymptotically optimal. Also, unlike existing bandit strategies designed for other popular structures, IMED-GS⋆ does not resort to an explicit forced exploration scheme and only makes use of local counts of empirical events. We finally provide numerical illustration of our results that confirm the performance of IMED-GS⋆.
