Abstract
In the multiarmed bandit problem, a gambler chooses an arm of a slot machine to pull considering a tradeoff between exploration and exploitation. We study the stochastic bandit problem where each arm's reward is bounded in the interval $[0,1]$. We introduce DMED-M, a novel algorithm that achieves near-optimal regret by exploiting only the first $d$ empirical moments of the reward distributions. By leveraging the theory of Tchebycheff systems, we provide explicit, highly efficient update rules for $d \le 4$, bridging the gap between computationally heavy optimal policies and fast but sub-optimal ones like UCB.
Introduction
The classic multi-armed bandit (MAB) problem requires an agent to maximize cumulative rewards by balancing exploration (learning payouts) and exploitation (pulling the best-known arm). For rewards bounded in $[0,1]$, policies like Deterministic Minimum Empirical Divergence (DMED) are asymptotically optimal, reaching the theoretical lower bound for regret. However, DMED is computationally intensive, requiring the storage of the full empirical distribution and solving a convex optimization problem at each step, leading to $O(\log n)$ complexity per round. In contrast, algorithms like Upper Confidence Bound (UCB) are fast ($O(1)$ complexity) but fail to achieve optimal regret. This paper introduces DMED-M to provide a computationally lightweight yet asymptotically optimal solution.
Methods
DMED-M restricts decision-making to the first $d$ empirical moments (e.g., mean, variance, skewness, kurtosis) rather than the full reward history. The core challenge is minimizing the Kullback-Leibler (KL) divergence subject to $d$ moment constraints. Utilizing the theory of Tchebycheff systems and moment spaces, we prove that the optimal solution to this constrained problem is always a specific, sparse discrete distribution called the "upper principal representation."
Because this representation has a finite support (a small number of points), we are able to derive explicit polynomial equations to solve the optimization. For $d \le 4$, we provide exact, closed-form mathematical solutions. This decoupling allows the algorithm to compute the discrete distribution just once per round and then easily optimize for the target expected value, maintaining $O(1)$ complexity. We also introduce DMED-MM (a mixed policy) that slightly modifies the selection criterion to improve worst-case performance when the gap between the $d$-moment approximation and the true distribution is large.
Results and Discussion
The performance of DMED-M was evaluated using simulated environments with rewards drawn from various Beta distributions (e.g., Be(0.6, 0.9), Be(1.2, 1.8)). A key theoretical result is the convergence of DMED-M to the optimal DMED as the number of moments $d$ increases.
As shown in Figure 1, the "gap ratio"—representing the distance from the theoretical lower bound—drops sharply as $d$ increases. In practice, tracking just the first 3 or 4 moments ($d=3, 4$) captures almost all the benefits of the full empirical distribution while keeping the math solvable via explicit, fast polynomial equations.
Empirical results over 100,000 plays demonstrate that DMED-M significantly outperforms standard UCB2 and UCB-tuned policies.
Figure 2 illustrates that as $d$ increases from 1 to 4, the regret curves of DMED-M shift downward, eventually hugging the optimal DMED baseline. This confirms that tracking just a few moments is sufficient for near-optimal performance while maintaining the computational efficiency of UCB-style algorithms. For certain distributions where probability mass is concentrated away from boundaries, the DMED-MM variant further improves convergence, matching the full DMED's performance almost perfectly.
Conclusion
DMED-M successfully bridges the gap between efficiency and optimality in stochastic bandits. By tracking only the first few empirical moments, the algorithm achieves $O(1)$ per-round complexity while matching the regret performance of more complex, asymptotically optimal policies. Future work includes investigating whether DMED-M's regret bound is the absolute best possible for any policy restricted to $d$ moments under specific regularity conditions.
Summary updated