Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms

1 Introduction

• A novel integral representation of the weighted-sum density yields two-sided Gaussian-type deviation bounds with optimal dependence on Dirichlet parameter sum and dimension.For dimension 2, the results recover the Beta case and generalize Alfers and Dinges [1984].Source: §1 · pp. 1–2
• The bounds provide a non-asymptotic version of the inverse of Sanov’s theorem for Bayesian inference on measures with finite support.The paper also applies them to Dirichlet-process posterior means, including Bayesian bootstrap.Source: §1 · p. 2
• In Multinomial Thompson Sampling, the resulting instance-dependent regret bounds have an optimal leading term and a remaining term independent of state-space dimension.The paper describes these bounds as much tighter than previously known results.Source: §1 · p. 2
• Existing crossing-probability results are limited: the equal-parameter formula is uninformative, while a prior lower bound incurs an exponential-in-dimension factor.Strong dependence among Dirichlet components also prevents direct use of bounds for sums of independent variables.Source: §1 · p. 2

2 Main Results

• K_inf measures the least KL divergence from a measure to measures whose expectation is at least µ.The corresponding M-projection is connected to maximum likelihood for empirical measures and appears as a rate function in Bayesian large deviations.Source: §2 · pp. 2–3
• Theorem 1 gives crossing-probability bounds for weighted Dirichlet sums under endpoint and parameter-size conditions.The weight function maps the two endpoints to 0 and b, and the minimum endpoint Dirichlet parameter must be at least c0 · ε^-2.Source: §2 · p. 3
• The lower and upper bounds use parameter vectors shifted at opposite endpoints, α+ and α−, respectively.For any µ in (0, b), the lower-bound statement uses α+ and the upper-bound statement uses α−.Source: §2 · p. 4
• The endpoint-parameter condition controls remainder terms, while a sufficiently large uniform prior can satisfy it in the Bayesian setting.The weight-function endpoint condition can be achieved by shifting u and f by the same constant.Source: §2 · p. 4
• Theorem 1 is a non-asymptotic counterpart to the inverse Sanov large-deviation result for finite-support Bayesian inference.The comparison concerns crossing events of the form wf ≥ µ and holds under mild conditions on the prior distribution.Source: §2 · p. 5

3 Application: Deviations for the Dirichlet process posterior

• The posterior draw is modeled as DP(ν + n empirical measure), based on an i.i.d. sample from P.The section studies deviations of the posterior draw applied to a bounded function g.Source: §3 · p. 5
• With a finite-support base measure, the Dirichlet-process prior yields the Bayesian bootstrap, for which the section gives a conditional deviation inequality.The stated choice is γ = c0·ε^-2 + 1, and the inequality applies conditionally on the observed sample for t ∈ (0, 1 − Pg).Source: §3 · pp. 5–6
• The section derives Hoeffding- and Bernstein-type deviation inequalities for Dirichlet-process posterior draws under the stated two-point base-measure and parameter conditions.The propositions assume a base measure νγ = γδx0 + γδx1, where g(x0)=0 and g(x1)=1, with γ ≥ c0ε^-2 + 1.Source: §3 · p. 6
• The bounds can also estimate the difference between the posterior mean and the true mean directly.Source: §3 · p. 7

4.1 Multinomial reward

• MTS is a Thompson-sampling algorithm with a Dirichlet prior and posterior for arms sharing a finite reward support.At each round it samples posterior means and chooses the arm with the highest sample mean.Source: §4 · p. 8, §4.1 · p. 9

4 Application: Refined analysis of Multinomial Thompson Sampling

• The refined instance-dependent MTS regret bound is independent of arm-support size, unlike the previous bound’s exponential growth with support size.The paper says a randomized-rounding extension is optimal and has space complexity O(K log(T)) and per-round time complexity O(log(T)).Source: §4 · p. 8

4.1 Multinomial reward

• For multinomial rewards, the theorem’s regret bound does not depend on support size m.Source: §4.1 · p. 9
• The earlier analysis’s exponential-in-m deviation bound translated directly into an exponential-in-m regret bound; the paper uses a sharper deviation inequality instead.The comparison also notes that the paper’s inequality avoids the extra artificial-reward prior parameter of order O(log(T)) required by Tiapkin et al. [2022].Source: §4.1 · p. 9

4.2 Bounded reward

• For bounded rewards, RMTS rounds each reward to a neighboring grid value using a Bernoulli draw that preserves its expectation.The transformed reward is then fed to MTS.Source: §4.2 · p. 9
• With grid size m = O(log T), RMTS is problem-dependent optimal for bounded rewards, relying on MTS’s support-independent regret bound.Source: §4.2 · p. 10
• RMTS has space complexity O(K log(T)) and per-round time complexity O(K log(T)), compared with O(T) space and time for NPTS.The passage states that RMTS preserves problem-dependent optimality.Source: §4.2 · p. 10

5 Proof of the main results

• The proof strategy combines the weighted-sum density representation with its non-asymptotic expansion to prove the main results.Source: §5 · p. 10, §5.1 · p. 10

A Proof of Lemma 1

• A lemma supplies lower and upper density bounds by considering Dirichlet parameters with one endpoint incremented.The two parameter shifts are defined separately for the two endpoint coordinates.Source: §5.1 · pp. 10–11

5.2 Proof of Corollary 1

• The complementary probability identity for wf converts an upper-tail event into a lower-tail event for w(b − f), allowing Theorem 1’s bound to be applied.Source: §5.2 · p. 13

A.1 Density of weighted sum of the Dirichlet distribution

• The density proof uses changes of variables and coarea calculations to express the weighted-sum density as an integral.Source: §A.1 · pp. 18–19

A.2 Method of Saddle Point

• The saddle-point method selects the unique imaginary saddle point and a contour where the real part is minimized, then applies the Laplace method.The section bounds expansion remainder terms in its analysis.Source: §A.2 · pp. 19, 20, 23

B Elements of Linear Algebra

• The linear-algebra appendix defines a canonical full-rank map into the null space using reduced row-echelon form, invariant to row operations on the matrix.Source: B Elements of Linear Algebra · p. 25

C MTS algorithm

• The algorithm appendix describes MTS and RMTS; RMTS replaces a reward by a randomized neighboring grid value before updating the posterior.The rounded reward uses a Bernoulli draw based on the reward’s fractional grid position.Source: C MTS algorithm · pp. 26–27

• The section provides a proof of Theorem 2.Source: D Proof of regret bounds · p. 27
• The section provides a proof of Theorem 3.Source: D Proof of regret bounds · p. 27
• Theorem 2 and Theorem 3 are the results proved in this section.Source: D Proof of regret bounds · p. 27

• The proof setup defines events and a decomposition for each suboptimal arm a ≠ a⋆.The value ε is to be specified later, and a⋆ is defined as the unique optimal arm.Source: §D.1 · pp. 27–28
• The stated multinomial TS propositions concern any ε > 0 and any suboptimal arm a.The section identifies Propositions 5, 6, and 7 as results whose proofs use Theorem 1.Source: §D.1 · p. 28
• A log(T) · log log(T) term does not depend on M.Source: §D.1 · p. 28

D.2 Proof of Theorem 3

• For sufficiently large T, taking m ≥ log(T) satisfies all stated conditions and yields the theorem's conclusion.The proof uses a condition on m for RMTS derived from Theorem 2.Source: §D.2 · p. 28

D.3 Proof of Proposition 5-7

• The section gathers proofs of Propositions 5, 6, and 7.Source: §D.3 · p. 29

D.3.1 Proof of Propositions 5

• For Proposition 5, the proof uses a union bound and changes a sum over time to a sum over pull counts; fixing the count n fixes the distribution of αₐ^[n].The distribution depends on the pull count and the arm's distribution pₐ.Source: §D.3.1 · p. 29

• Conditioning on the pull count and using the tower property leads to an overall bound for t = 0, …, T − 1.The proof states that the conditional quantity satisfies the definition of Econc,1 and applies Theorem 1 when the specified condition holds.Source: §D.3.2 · pp. 29–30
• For n ≥ n₀, the proof obtains a uniform upper bound using a lower bound on Kinf(p(a), µ⋆−ε, f)−eε(n).Source: §D.3.2 · p. 30
• The proof chooses n₀ = (1 + ε′) log(T) / Kinf(p, µ⋆−ε, u) for any ε′ > 0.It invokes a normal-tail upper bound in the derivation.Source: §D.3.2 · p. 30
• A log log(T) · log(T) term appears in the bound, and the proof takes log(T) to make a final term vanish for large T.The proof also invokes Lemma 11 by Garivier et al. [2022].Source: §D.3.2 · p. 30

D.3.3 Proof of Proposition 7

• The displayed expression includes a log(T)·log log(T) term.Source: §D.3.3 · p. 30
• The proof conditions on the history through round t−1, uses independence of posterior samples, and switches from global time to counts.It treats the expectation by separating two cases.Source: §D.3.3 · pp. 30–31
• The first term is bounded using the lower tail bound for a Gaussian, followed by a choice of truncation points.The proof also invokes Hoeffding's inequality for another probability bound.Source: §D.3.3 · p. 32
• For the second term, the proof applies Theorem 1 to probabilities under expectation and chooses n0 = O(ε^-5) for a tail bound.The argument also uses Lemma 11 by Garivier et al. [2022].Source: §D.3.3 · pp. 32–33

E Technical Lemmas

• An auxiliary result is presented as similar to Lemma D.14 of Tiapkin et al. [2022].Source: E Technical Lemmas · p. 33
• The section analyzes how Kinf changes under small changes to its first argument, the distribution.Source: E Technical Lemmas · p. 34
• The Kinf analysis uses a variational formula and a dual optimizer, with the second-sum analysis using the support condition q⋆f ≥ μ.The proof also invokes a uniform upper bound attributed to Honda and Takemura [2010].Source: E Technical Lemmas · pp. 34–35
• For categorical samples, the empirical distribution is shifted by prior counts before deriving deviation and concentration results.The setup defines frequencies from i.i.d. samples and a prior-count vector whose entries sum to n0.Source: E Technical Lemmas · pp. 35–36
• Lemma 10 considers f from {0, …, m} to [0, b], with f(0) = 0 and f(m) = b; the excerpt also gives m ≥ 1 and 0 < δ < γ/2, but omits the resulting claim.Source: E Technical Lemmas · p. 36