Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms
Not on the map. Why?
Abstract (arXiv)
In this work, we derive sharp non-asymptotic deviation bounds for weighted sums of Dirichlet random variables. These bounds are based on a novel integral representation of the density of a weighted Dirichlet sum. This representation allows us to obtain a Gaussian-like approximation for the sum distribution using geometry and complex analysis methods. Our results generalize similar bounds for the Beta distribution obtained in the seminal paper Alfers and Dinges [1984]. Additionally, our results can be considered a sharp non-asymptotic version of the inverse of Sanov's theorem studied by Ganesh and O'Connell [1999] in the Bayesian setting. Based on these results, we derive new deviation bounds for the Dirichlet process posterior means with application to Bayesian bootstrap. Finally, we apply our estimates to the analysis of the Multinomial Thompson Sampling (TS) algorithm in multi-armed bandits and significantly sharpen the existing regret bounds by making them independent of the size of the arms distribution support.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 8 of its 56 references that are in the map. First posted on arXiv 6 Apr 2023.
Builds on
8 of 56 references.
References · 8
- 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
- 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
- 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 79
- 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
- 2013Thompson Sampling for 1-Dimensional Exponential Family Banditscited by 42
- 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
- 2018KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpointscited by 20
- 2023A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithmscited by 4
Built on by
Citing papers per year: 2025: 2.
2 papers.