PaperlayerView exact revision on arXiv

Source-linked AI summary

Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals

Emilie Kaufmann, Wouter Koolen

arXiv:1811.11419v2stat.MLcs.LG

TL;DR

The paper addresses the need for time-uniform deviation control under adaptive sampling, including deviations involving multiple arms in exponential-family bandits. It constructs hierarchical-prior mixture martingales and combines them across arms, obtaining bounds that support sequential tests and confidence intervals. The approach extends to generic distributions and applications including GLR stopping rules and confidence regions, while some results rely on bounded outcomes or uniqueness assumptions.

  • Problem

    Existing deviation inequalities often treat one arm at a time or only finite horizons, limiting direct control of multi-arm deviations in sequential bandit problems.

  • Method

    The paper constructs arm-wise mixture martingales from hierarchical priors and multiplies them to control KL-based self-normalized sums over adaptive subsets of arms.

  • Results

    The resulting inequalities are time-uniform and support generalized-likelihood-ratio stopping rules, tight confidence regions, and applications across exponential families.

  • Takeaways & Limitations

    The mixture-martingale approach provides a common basis for sequential identification procedures and confidence intervals for functions of bandit means.

  • Takeaways & Limitations

    Some analyses assume uniqueness of the relevant optimiser, while the alternative mixture construction discussed applies to bounded outcomes and can produce negative mixture values.

Abstract

from arXiv · show

This paper presents new deviation inequalities that are valid uniformly in time under adaptive sampling in a multi-armed bandit model. The deviations are measured using the Kullback-Leibler divergence in a given one-dimensional exponential family, and may take into account several arms at a time. They are obtained by constructing for each arm a mixture martingale based on a hierarchical prior, and by multiplying those martingales. Our deviation inequalities allow us to analyze stopping rules based on generalized likelihood ratios for a large class of sequential identification problems, and to construct tight confidence intervals for some functions of the means of the arms.

1. Introduction

The paper develops time-uniform KL-based deviation inequalities for adaptively sampled exponential-family bandits, combining evidence across multiple arms. These inequalities support generalized-likelihood-ratio stopping rules and tighter confidence intervals for functions of arm means.

  • Motivation and setup: The framework targets tight confidence regions valid uniformly in time under arbitrary adaptive sampling in multi-armed bandits.It measures deviations through KL divergence and supports sequential allocation and hypothesis-testing problems.
  • Novelty of the concentration results: The inequalities combine evidence from several arms through a summation form rather than separate per-arm bounds.They can also apply to arbitrary random subsets of arms using a weighted union bound.
  • Novelty of the concentration results: Mixture martingales built for exponential families yield explicit calibration functions and thresholds valid over the entire time range t ∈ N.This improves on prior multi-arm results restricted to a finite horizon and avoids intractable generic thresholds.
  • Applications to sequential tests: The resulting bounds support generalized-likelihood-ratio stopping rules for generic sequential identification problems.Under suitable assumptions, these rules combined with appropriate sampling achieve asymptotic sample-complexity optimality.
  • Applications to confidence intervals: Directly summing two arms' self-normalized deviations produces a tighter confidence interval for µ1 − µ2 than projecting a union-bound box.For linear functions of the mean vector, the confidence-width improvement can yield a factor 2 reduction in sample complexity.

2. Martingales and Deviation Inequalities for Exponential Family Bandit Models

The paper develops a martingale framework for time-uniform deviations in exponential-family bandits. It defines g-VCC processes, combines arm-wise test martingales over subsets, and derives deviations through Ville’s inequality and calibrated convex transforms.

  • Exponential-family bandit models: The model consists of K independently distributed arms from a one-dimensional canonical exponential family, sampled sequentially by an adaptive rule.Each arm is represented by its mean, observation count, and empirical mean.
  • Exponential-family bandit models: The target deviations involve sums of Na(t)d(µ̂a(t), µa), with an ln ln(Na(t)) cost for uniformity over time.The divergence is the KL divergence between exponential-family distributions parameterized by their means.
  • Martingale framework: A g-VCC process has arm-wise test martingales whose products remain martingales for every subset of arms.This structure enables concentration bounds for sums across selected arms under adaptive sampling.
  • Calibration: The asymptotic χ2 behavior of self-normalized terms suggests a calibration based on 1/2 ln(1−λ), with an additional cost for time uniformity.This provides a benchmark for the calibration functions used in the applications.
  • Deviation inequalities: Ville’s inequality and the Cramér-Chernoff method convert the martingale domination condition into time-uniform deviation inequalities.The resulting thresholds can be expressed through a calibration function Cg or the convex conjugate g∗.
  • Mixture martingales: Mixture martingales are formed by integrating arm-specific martingales over priors, then multiplying the resulting processes across arms.The construction uses Tonelli’s theorem and preserves the test-martingale property under adaptive sampling.

3. New Deviation Inequalities for Exponential Families

The paper develops time-uniform KL deviation inequalities for one-dimensional exponential families, including Gaussian and Gamma refinements, with thresholds calibrated for simultaneous deviations over arm subsets. The results compare favorably with prior finite-horizon bounds and use hierarchical-prior mixture martingales, while revealing the unavoidable ln(ln(t)) cost of time uniformity.

  • Uniform subset control: The three theorems control simultaneous two-sided deviations over arm subsets, with c = 2 and d = 4 for Gaussian or Gamma models and c = 3 and d = 1 for general families.The relevant calibration function is CG, CΓ, or Cexp according to the distributional setting.
  • Calibration comparison: Gaussian and Gamma calibration functions are close to the ideal Cgχ2, whereas Cexp differs by an additive term of order 10.The idealized calibration behaves as x + ln(x), while the Gaussian and Gamma functions are reported to be very close to it.
  • Advantages of the general result: The general theorem applies beyond Gaussian and Gamma models, supports tighter one-sided thresholds, and yields an improved result uniformly over subsets through the positive-part construction.The discussion specifically notes applicability to Bernoulli and Poisson distributions and a smaller one-sided calibration ˜Cexp.
  • Comparison and time-uniformity: Compared with Magureanu et al. (2014), the new thresholds can be much smaller and remain valid over the entire time range t ∈ N rather than only a finite horizon.The paper also reports a ln(ln(t)) threshold for general exponential families, while noting that this term is unavoidable in the Gaussian case and that the result is not claimed to be generally tightest there.
  • Proof strategy: The proofs construct mixture martingales from hierarchical priors, multiply arm-wise martingales, and use their domination of exponential transforms to obtain summed evidence across arms.The hierarchical mixture uses a logarithmic factor to make the prior proper; handling the resulting negative mixture values contributes a ln(ln Na(t)) term.

4. Asymptotically Optimal Adaptive Sequential Testing

The section formulates sequential identification as adaptive testing over a partition of mean vectors and develops a GLR stopping rule with confidence guarantees. Combined with Tracking, the procedure can be asymptotically optimal under regularity conditions on the optimal sampling weights.

  • Problem: Sequential identification partitions the possible mean vectors into hypotheses and seeks a δ-correct adaptive strategy that identifies the true hypothesis.The strategy must succeed for every possible mean vector with probability at least 1 − δ.
  • General GLR rule: The GLR stopping rule stops when the statistically plausible parameter set is contained in one partition element.This can also be viewed as running parallel GLR tests against the alternatives for each hypothesis.
  • Correctness: Theorem 7 supplies thresholds making the GLR rule δ-correct for every sampling rule while ensuring confidence regions contain the true parameter uniformly over time.Proposition 15 states both the uniform confidence-region guarantee and the error-probability bound.
  • Asymptotic optimality: With well-defined and continuous optimal weights, Tracking combined with the GLR rule is δ-correct and asymptotically matches the sample-complexity lower bound.The result applies for every δ ∈ (0, 1].
  • Adaptive allocation: Optimal weights specify the sampling fractions for each arm, motivating the Tracking rule used to allocate observations adaptively.The weights are defined when the relevant optimizer is unique, and tracking may use uniform exploration before empirical means enter the admissible mean space.
  • Scope and assumptions: Uniqueness of the optimal weights can fail in practical problems, although later work handles set-valued, upper hemi-continuous, convex-valued weight maps.The paper also notes that efficient computation of the weights is required for implementation.

5. Smaller Thresholds for Better Sequential Tests

The paper exploits the subset structure of multi-arm deviations to reduce thresholds for specialized sequential tests. For best-arm identification and rank-structured problems, these reductions preserve δ-correctness and can support earlier stopping or asymptotically optimal procedures.

  • Subset-based deviations: Deviation inequalities hold for any arm subset, and weighted union bounds extend them uniformly over subsets in a prescribed support.This allows thresholds to reflect the subsets actually used by a test rather than all arms indiscriminately.
  • Best-arm identification: For best-arm identification, the GLR statistic involves only pairs of arms, enabling a smaller δ-correct threshold than the universal threshold.The reduction follows by applying a weighted union bound over the K − 1 pairs involving the leading arm.
  • Best-arm identification: For large t, the improved best-arm threshold is smaller than the original threshold ln 2t(K−1)/δ, potentially allowing earlier stopping while preserving optimal sample-complexity guarantees.The paper connects this form to the stylized ln((ln(t) + 1)/δ) threshold used in some experiments.
  • Confidence-region caveat: The improved best-arm stopping threshold does not imply a uniformly δ-valid confidence region for the associated confidence interval.The paper explicitly distinguishes δ-correct stopping from simultaneous confidence-region validity.
  • Rank-based thresholds: Rank R means each alternative set can be decomposed into pieces involving only R arms, allowing thresholds to depend on rank rather than the total number of arms.Best-arm identification has rank 2, while Largest Profit Identification has rank 4.
  • Game-tree identification: In depth-two game trees, the identification problem has rank L + 1, much smaller than the K · L leaves, and the GLR rule can be asymptotically optimal with Tracking under continuity of the weights.The optimal weights are numerically computable using disciplined convex optimization tools.

6. Projected Confidence Intervals

The paper constructs time-uniform confidence regions and projects them onto functions of arm means, with tightness determined by both the function and the region’s weight vector. For linear functions and minima, combining evidence across arms can materially improve confidence intervals, though the best weighting depends on the target.

  • Confidence regions: δ-uniformly valid confidence regions hold simultaneously for all t under every sampling rule.These regions can be projected onto functions of the unknown parameter.
  • Linear functions: For linear functions v⊺µ, Box and Ellipse intervals arise from singleton-supported and full-set-supported weight vectors.The Box interval uses separate arm evidence, whereas the Ellipse interval combines evidence from all arms.
  • Linear functions: The Ellipse bound can be much tighter than the Box bound in small-δ regimes because it depends on the two-norm rather than the one-norm of v.The comparison concerns the placement of the sum relative to the square root.
  • Minimum means: For lower confidence bounds on minima, combining evidence across many arms provides little benefit, making uniform singleton weights optimal.A minimum can be low whenever one entry is low, so the relevant configuration changes only one coordinate.
  • Minimum means: For upper confidence bounds on minima, considering many subsets can help because smaller subsets trade fewer evidence terms against smaller thresholds.Cardinality-based weights can be evaluated by sorting arm contributions, with each objective evaluation obtainable in O(K ln K) time.
  • Practical choice of weight vector: In Bernoulli experiments, uniform cardinality-based weights are robust for small δ, and aggregating evidence across arms can further reduce upper confidence bounds.The experiment varies the number M of arms sharing the minimum mean and compares singleton, full-set, and uniform-over-size weights.

7. Conclusion

Sequential learning uses adaptive samples to decide what to do, when to stop, and what to recommend or estimate. The paper uses mixture martingales to construct confidence regions and applies the resulting inequalities to confidence intervals, GLR stopping rules, and Track-and-Stop analysis.

  • Conclusion: Sequential bandit learning asks what can be inferred from samples when the learner adaptively chooses arms.These inferences support decisions about actions, stopping, recommendations, and estimation.
  • Conclusion: Mixture martingales yield confidence regions based on self-normalized sums for exponential-family multi-armed bandits.The paper argues that these regions are among the tightest known and match established statistical lower bounds in spirit.
  • Conclusion: The deviation inequalities support projected confidence intervals, GLR stopping rules, and a tight analysis of asymptotically optimal Track-and-Stop sampling.These applications demonstrate the generality of the mixture-martingale approach across sequential procedures.

Appendix A. Proof of Proposition 8

The appendix proves Proposition 8 by using a feasible auxiliary choice and an inequality whose gap can be verified to increase by differentiation. The proof then applies a logarithmic bound.

  • Proof strategy: A feasible choice z = 1 + 1 (x−1)+√2(x −1) is used, with equality at x = 1.The gap between the two sides is increasing, as can be checked by differentiation.
  • Proof strategy: The final proof step applies a logarithmic inequality.

Appendix B. Additional Proofs for Exponential Families

The appendix derives time-uniform exponential-family deviation inequalities by relating KL deviations to martingale deviations on sampling-count slices, then removing the slice restriction with a discrete-prior mixture martingale.

  • Deviation control: The resulting bounds control self-normalized deviations involving Na(t)d(µ̂a(t), µa) and logarithmic time penalties.The proof converts mixture-martingale events into explicit deviation events and uses inequalities for the logarithmic terms.
  • Slice reduction: Lemma 27 relates KL deviations of empirical means to deviations of exponential-family martingale terms on geometric sampling-count slices.The slice condition is Na(t) ∈ [(1 + ξ)^(i−1), (1 + ξ)^i].
  • Mixture martingale: A carefully chosen discrete prior and mixture martingale extend the control from individual slices to every time t.The construction is introduced for the most complicated case and uses priors indexed by the slice parameter.
  • Deviation control: The same proof pattern applies to the other cases, with corresponding priors yielding an improved constant C(ξ) = ln ζ(2) / (ln(1+ξ))^2.

B.2 Tight Tuning: Proof of Lemma 12

This section proves Lemma 12, establishing the tightest tuning achievable with the method through two auxiliary lemmas and convex optimization arguments.

  • Lemma 12 gives the tightest possible tuning achievable with the method.
  • The proof first establishes two auxiliary lemmas before deriving Lemma 12.
  • Convexity reduces the optimization to solving for a zero derivative.
  • The rewrite in terms of h is valid because 1/(1 −q) ≥1, yielding the stated value.
  • The auxiliary function ˜hz(x) is defined by minimizing y (x −ln ln y) over y ∈[1,z].

B.3 A Tighter One-Arm Bound

This section derives a one-arm deviation threshold from Lemma 13 and extends the martingale construction to exponential families satisfying a prior-regularity assumption.

  • Lemma 13 directly yields valid thresholds involving only a single arm.
  • The one-arm threshold uses x, whereas the multiple-arm threshold uses h−1(1 + x), creating an overhead for controlling multiple arms.
  • The martingale construction extends to other one-dimensional exponential families when a continuous prior satisfying the stated assumption can be constructed.
  • Theorem 33 converts the prior assumption into a deviation inequality, while suitable priors are explicitly available for Gaussian and Gamma distributions.
  • Constructing the required priors is closely related to a bilateral inverse Laplace transform, which is difficult beyond Gaussian or Gamma distributions.
  • For Gaussian distributions, optimizing the grid parameter at ln(1 + ξ) = 4λ gives gG(λ) = 2λ −2λ ln (4λ) + ln ζ(2λ) −1 2 ln (1 −λ).

C.2 Application to Gamma Distributions

This section applies the general prior construction to Gamma distributions, verifies the required assumption, and derives the resulting deviation function.

  • Gamma distributions with known shape α form a one-parameter exponential family, including the Exponential distribution when α = 1.
  • The family of functions defined in (29) satisfies Assumption 32.
  • The proof verifies the assumption through a change of variables and separate checks of its conditions.
  • The analysis uses monotonicity properties of the Gamma-function approximation error and of the relevant expression around η = 0.
  • Theorem 33 provides the basis for the Gamma test martingale after evaluating the function g0(λ, ξ, c).
  • The resulting Gamma deviation function is gΓ(λ) = 2λ −2λ ln (4λ) + ln ζ(2λ) −ln (1 −λ).

Appendix D. Optimal Sample Complexity: Proof of Theorem 17

This appendix proves optimal sample complexity under the Tracking rule by combining its sampling properties, continuity arguments, threshold bounds, and matching lower bounds.

  • The proof begins with a deterministic property of the Tracking sampling rule that reformulates an earlier sampling lemma.
  • Under the Tracking rule, every arm receives at least order (t−K/2)+−1 samples, with a further eventual lower bound summarized by Lemma 37.
  • On ET (ϵ), once t ≥T 1/4, the selected index is 1, so Alt(ˆµ(t)) = Alt(µ) and the empirical likelihood ratio has the stated representation.
  • Joint continuity and Berge’s maximum theorem establish continuity of the relevant optimization function.
  • The error contribution is bounded by BT exp(−CT 1/8), while the threshold bound supplies the complementary control.
  • Letting ξ and ϵ vanish yields the target upper bound, and Proposition 16’s lower bound turns that inequality into equality.
Loading 1811.11419v2…