Introduction
Multi-armed bandit (MAB) algorithms, such as Upper Confidence Bound (UCB) and Thompson Sampling, are foundational to sequential decision-making. However, their success typically relies on strict parametric assumptions about reward distributions—such as bounded supports or specific exponential family forms. When these assumptions fail, as they often do in messy, real-world scenarios, standard algorithms can become overly cautious or dangerously aggressive, leading to high regret.
To bridge the gap between theoretical assumptions and practical reality, this paper introduces Dirichlet Sampling (DS). DS is a novel family of randomized algorithms that replaces rigid parametric assumptions with data-driven re-sampling. It is designed to be optimal when the environment is well-understood and robust when the practitioner is unsure about the underlying distribution.
The Dirichlet Sampling Framework
Instead of assuming a specific mathematical formula for the reward distribution, Dirichlet Sampling uses the history of observed rewards to simulate potential future outcomes. The core mechanics rely on three key innovations:
- A Duel-Based Framework: DS shifts away from calculating independent indices for every arm. Instead, it identifies a Leader (the most frequently sampled arm) and pits it against Challengers.
- Non-Parametric Re-sampling: For challenger arms, the algorithm draws weights from a Dirichlet distribution to create a "noisy" version of the empirical mean. This acts as a non-parametric version of Thompson Sampling.
- Data-Dependent Exploration Bonus: To prevent the algorithm from getting stuck on a deceptively lucky sub-optimal arm, DS incorporates an exploration bonus. Unlike traditional fixed bonuses, this penalty adapts based on the observed data and the leader's performance.
By only re-sampling for challengers and comparing them to the leader's empirical mean, the algorithm is computationally more efficient than standard Thompson Sampling, which requires drawing random samples for every arm at every step.
Variants of Dirichlet Sampling
The authors introduce three specific flavors of DS tailored to different levels of uncertainty:
- BDS (Bounded DS): Designed for rewards with a known range but potentially unknown upper bounds. BDS is proven to be asymptotically optimal for bounded distributions, matching theoretical lower bounds of regret.
- QDS (Quantile DS): Utilizes truncation and quantiles to handle semi-bounded distributions.
- RDS (Robust DS): A "set-and-forget" variant that adapts its exploration leverage based on sample size, built to handle any light-tailed distribution.
Key Insights and Theoretical Guarantees
A major contribution of this paper is demonstrating that the theoretical cost of robustness is surprisingly small. Standard algorithms fail on unbounded distributions because probability mass can "leak" to infinity, making a sub-optimal arm look infinitely better than it is. DS uses its data-dependent bonuses to track and mitigate this leakage.
While optimal algorithms achieve $O(\log T)$ regret, the robust RDS variant achieves $O(\log T \log \log T)$. In practice, this slight theoretical penalty is negligible, making the trade-off highly favorable for real-world applications.
Real-World Application: Agriculture Data
To test the robustness of DS, the authors evaluated the algorithms using the DSSAT (Decision Support System for Agrotechnology Transfer) simulator, modeling over 30 years of maize crop yields based on different planting dates.
Agricultural data is notoriously complex: it is multimodal, right-skewed, and often features a spike at zero due to crop failure. It does not fit neatly into the "sub-Gaussian" boxes that most bandit theories require. In these experiments, when standard algorithms (like IMED or NPTS) were given conservative, incorrectly large upper bounds, their performance degraded significantly.
In contrast, RDS and QDS remained stable and outperformed the baselines. RDS emerged as the overall winner, proving that trading a fraction of theoretical optimality for broad robustness is a winning strategy in complex environments.
Limitations and Future Directions
While Dirichlet Sampling offers a robust alternative to traditional MAB algorithms, the current framework has a few limitations:
- Heavy Tails: The current work focuses on "light-tailed" distributions. It does not yet address heavy-tailed distributions (e.g., those found in finance or network traffic), though the authors suggest techniques like "median-of-means" could extend DS to these cases.
- Semi-Bounded Restrictions: Some proofs for the Quantile version (QDS) currently require the distribution to be bounded from below (e.g., rewards cannot be negative).
- Hyperparameter Tuning: While RDS is fully adaptive, QDS still requires the practitioner to choose a quantile parameter ($\alpha$), which may demand some domain knowledge.
Future iterations of this work aim to relax these restrictions, further expanding the versatility of the Dirichlet Sampling framework.
Summary updated