  Optimally solving a multi-armed bandit problem suffers the curse of
dimensionality. Indeed, resorting to dynamic programming leads to an
exponential growth of computing time, as the number of arms and the horizon
increase. We introduce a decompositioncoordination heuristic, DeCo, that turns
the initial problem into parallelly coordinated one-armed bandit problems. As a
consequence, we obtain a computing time which is essentially linear in the
number of arms. In addition, the decomposition provides a theoretical lower
bound on the regret. For the two-armed bandit case, dynamic programming
provides the exact solution, which is almost matched by the DeCo heuristic.
Moreover, in numerical simulations with up to 100 rounds and 20 arms, DeCo
outperforms classic algorithms (Thompson sampling and Kullback-Leibler
upper-confidence bound) and almost matches the theoretical lower bound on the
regret for 20 arms.
