Abstract
The stochastic multi-arm bandit problem has been extensively studied under standard assumptions on the arm's distribution (e.g bounded with known support, exponential family, etc). These assumptions are suitable for many real-world problems but sometimes they require knowledge (on tails for instance) that may not be precisely accessible to the practitioner, raising the question of the robustness of bandit algorithms to model misspecification. In this paper we study a generic Dirichlet Sampling (DS) algorithm, based on pairwise comparisons of empirical indices computed with re-sampling of the arms' observations and a data-dependent exploration bonus. We show that different variants of this strategy achieve provably optimal regret guarantees when the distributions are bounded and logarithmic regret for semi-bounded distributions with a mild quantile condition. We also show that a simple tuning achieve robustness with respect to a large class of unbounded distributions, at the cost of slightly worse than logarithmic asymptotic regret. We finally provide numerical experiments showing the merits of DS in a decision-making problem on synthetic agriculture data.
Introduction
In the classic Multi-Armed Bandit (MAB) problem, a learner attempts to maximize cumulative rewards by choosing between $K$ different actions (arms). To achieve theoretical optimality, standard algorithms such as Upper Confidence Bound (UCB) or Thompson Sampling typically require precise knowledge regarding the "tails" of the reward distributions—for instance, assuming they are sub-Gaussian or belong to a specific exponential family.
In practical applications, these tail parameters are rarely known with certainty. If a model is misspecified (e.g., assuming rewards are bounded between 0 and 1 when they occasionally exceed this range), traditional "optimal" algorithms can suffer significant performance loss. This paper addresses the gap between theoretical optimality and practical robustness by introducing Dirichlet Sampling (DS), a non-parametric framework that adapts to unknown reward distributions without rigid parametric assumptions.
The Dirichlet Sampling Framework
The DS framework builds upon Non-Parametric Thompson Sampling (NPTS) but introduces two critical innovations designed to balance exploration and exploitation more effectively:
- A Duel-Based Structure: Rather than computing independent indices for every arm, the algorithm identifies a "leader" (the arm sampled most frequently) and pits "challengers" against it in pairwise duels. This structure improves computational efficiency by avoiding unnecessary random weight draws for the leader arm.
- Data-Dependent Exploration Bonuses: To prevent the algorithm from prematurely abandoning a high-performing arm due to early poor samples, a bonus is added to the re-sampled mean. Unlike previous methods using fixed constants, this bonus is dynamically calculated based on the arm's specific history and a "leverage" parameter $\rho$.
Algorithmic Variants
The paper details three specific versions of the DS strategy:
- BDS (Bounded DS): Optimized for rewards with a known range or detectable upper bounds.
- QDS (Quantile DS): Employs a truncation mechanism and Conditional Value-at-Risk (CVaR) to handle semi-bounded distributions.
- RDS (Robust DS): The most flexible variant, which uses an increasing leverage sequence to guarantee sub-linear regret for any light-tailed distribution without requiring manual hyperparameter tuning for specific tail shapes.
Theoretical Insights and the Cost of Robustness
A fundamental challenge in bandit theory for unbounded distributions is "mass leakage," where probability mass can effectively "leak" toward infinity. The authors demonstrate that it is mathematically impossible to achieve standard logarithmic regret without some control over the tails (such as a quantile condition).
To overcome this, the RDS algorithm intentionally trades a small amount of asymptotic efficiency for significant robustness. While optimal algorithms aim for $O(\log T)$ regret, RDS achieves $O(\log T \log \log T)$. This slight increase in regret is a strategic trade-off, providing an algorithm that remains reliable across nearly any light-tailed scenario without practitioner intervention.
Experimental Results
The authors evaluated the DS framework using both synthetic benchmarks and a real-world agriculture simulator:
- Synthetic Data: Testing on Gaussian, Exponential, and Gaussian Mixture distributions confirmed the theoretical properties and the algorithms' sensitivity to tail behavior.
- Agriculture Simulator (DSSAT): The Decision Support System for Agrotechnology Transfer was used to model maize crop yields based on 30 years of historical data. These reward distributions are particularly challenging: they are multimodal, right-skewed, and feature a "peak at zero" representing crop failure.
Key Findings
- Asymptotic Optimality: BDS and QDS were proven to achieve the Burnetas & Katehakis lower bound, the gold standard for theoretical regret under their respective assumptions.
- Superiority in Agriculture: In the DSSAT crop-farming experiments, RDS emerged as the overall winner. It outperformed state-of-the-art baselines like NPTS and IMED, especially when those baselines were provided with conservative (overestimated) upper bounds.
- Robustness to Misspecification: RDS proved significantly less sensitive to hyperparameter choices than other robust competitors (such as R-UCB-LT), making it a more dependable tool for real-world decision-making.
Conclusion and Future Work
Dirichlet Sampling offers a robust, non-parametric path forward for stochastic bandits. By moving away from rigid tail assumptions, the DS framework provides practitioners with tools that are both theoretically sound and practically resilient.
Future research directions include extending the framework to "heavy-tailed" distributions (e.g., Pareto or Frechet) common in financial modeling, and further refining the analysis of boundary-crossing probabilities to develop even more efficient exploration bonuses.
Summary updated