Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals

Abstract

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.

References in corpus (4)

• Minimal Exploration in Structured Stochastic Bandits
• Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
• Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling
• Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration

Cited by in corpus (17)

• Time-uniform, nonparametric, nonasymptotic confidence sequences
• On the bias, risk and consistency of sample means in multi-armed bandits
• Inference for Batched Bandits
• Gradient Ascent for Active Exploration in Bandit Problems
• Confidence sequences for sampling without replacement
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Uncertainty quantification using martingales for misspecified Gaussian processes
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Non-Asymptotic Pure Exploration by Solving Games
• A nonasymptotic law of iterated logarithm for general M-estimators
• PAC Mode Estimation using PPR Martingale Confidence Sequences
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses
• Testing exchangeability: fork-convexity, supermartingales, and e-processes
• Nonparametric iterated-logarithm extensions of the sequential generalized likelihood ratio test