Abstract
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 decomposition-coordination 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.
Introduction
The Multi-Armed Bandit (MAB) problem is a cornerstone of sequential decision-making under uncertainty. In the finite-horizon Bayesian setting, the goal is to maximize the expected total reward over a fixed number of steps $T$. While this can be formulated as a Markov Decision Process (MDP), solving it exactly via Dynamic Programming (DP) is computationally prohibitive. The state space grows exponentially with the number of arms, a phenomenon known as the "curse of dimensionality." Consequently, practitioners often rely on heuristics like Thompson Sampling or Upper Confidence Bound (UCB) algorithms, which, while effective, are often designed for asymptotic performance rather than specific finite horizons.
This paper introduces the Decomposition-Coordination (DeCo) method, a heuristic based on Lagrangian relaxation that transforms the complex multi-arm problem into a series of parallel, single-arm subproblems. This approach not only reduces computational complexity to a linear scale relative to the number of arms but also provides a rigorous theoretical framework for bounding the optimality gap.
The DeCo Framework: Lagrangian Relaxation
The fundamental difficulty in MAB problems arises from the coupling constraint: only one arm can be pulled at any time step $t$. The DeCo method addresses this by relaxing the "hard" constraint into a "soft" or expected constraint.
1. Decomposition via Multipliers
By introducing time-dependent Lagrangian multipliers $\mu = (\mu_0, \dots, \mu_{T-1})$, the authors decouple the arms. These multipliers act as a "shadow price" for pulling an arm. In this relaxed version, the decision-maker can theoretically pull multiple arms or none, provided the average number of pulls equals one. This relaxation allows the original MDP to be decomposed into $|A|$ independent one-arm subproblems. Each subproblem is a simple DP that can be solved efficiently.
2. Offline Coordination
Before the online interaction begins, the method performs an offline coordination phase. Using a gradient descent algorithm, it finds the optimal sequence of multipliers $\mu$ that minimizes the dual function (the upper bound of the relaxed problem). This phase is computationally efficient, with a complexity of $O(K T^3)$, where $K$ is the number of distinct arm priors and $T$ is the horizon. This is a significant improvement over the $O(T^6)$ complexity associated with calculating Finite-Horizon Gittins indices.
3. Online Index Policy
During the online phase, the pre-computed value functions are used to derive an index policy. At each step $t$, the algorithm calculates an index for each arm based on its current state (e.g., the parameters of its Beta distribution). The arm with the highest index is selected. This index naturally splits into two components:
- Exploitation: The immediate expected reward of the arm.
- Exploration: The "value of information," representing the expected increase in future rewards gained by updating the arm's state.
Theoretical Insights: The Optimality Gap
A significant contribution of this work is the mathematical characterization of the optimality gap—the difference between the reward of the DeCo policy and the theoretical upper bound provided by the relaxation. The authors prove that the gap is driven by "confusion" states: situations where either no arm's index exceeds the current "price" $\mu_t$, or where multiple arms have indices exceeding $\mu_t$.
Interestingly, the paper identifies a "Many Arms Blessing." As the number of arms increases, the empirical performance of DeCo tends to converge toward the theoretical lower bound on regret. This suggests that the Lagrangian relaxation becomes increasingly tight in high-dimensional environments, making DeCo particularly effective for large-scale problems.
Experimental Results
The authors evaluated DeCo against several benchmarks, including Thompson Sampling (TS), KL-UCB, Information-Directed Sampling (IDS), and the Finite-Horizon Gittins (FH-Gittins) index, using simulated Bernoulli MABs.
- Performance: In simulations with up to 20 arms and a horizon of $T=100$, DeCo consistently outperformed TS and KL-UCB. In 2-arm scenarios where exact DP is feasible, DeCo's performance was nearly identical to the optimal solution.
- Efficiency: DeCo slashes the computational burden of FH-Gittins while maintaining comparable performance. The $O(KT^3)$ scaling makes it viable for horizons up to $T=500$.
- Scalability: Because the decomposition results in parallel subproblems, the method scales linearly with the number of arms in the online phase, overcoming the primary bottleneck of traditional DP.
Conclusion and Future Work
The Decomposition-Coordination method provides a powerful bridge between the theoretical optimality of DP and the practical efficiency of index policies. By interpreting exploration through the lens of economic shadow prices, DeCo offers a robust framework for finite-horizon MABs.
While the current implementation requires a known horizon and specific Bayesian priors, its reliance on time-dependent Bellman equations makes it uniquely suited for non-stationary environments where rewards or constraints change over time. Future research may address the impact of prior misspecification and the extension of DeCo to even larger horizons.
Summary updated