mlsanityData to 14 Oct 2026

Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals

arXiv 1811.11419 ↗First posted 28 Nov 2018stat.ML cs.LGcited by 76

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 76 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 Nov 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 13; 2023: 14; 2024: 11; 2025: 17; 2026: 14.

76 papers.

Sort:

  1. 2022Top Two Algorithms Revisitedcited by 34
  2. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  3. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 29
  4. 2022Fully Adaptive Composition in Differential Privacycited by 22
  5. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 21
  6. 2021Near-optimal inference in adaptive linear regressioncited by 21
  7. 2021Martingale Methods for Sequential Estimation of Convex Functionals and Divergencescited by 18
  8. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  9. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  10. 2022Optimal Clustering with Bandit Feedbackcited by 15
  11. 2023Adaptive Algorithms for Relaxed Pareto Set Identificationcited by 15
  12. 2022Bregman Deviations of Generic Exponential Familiescited by 13
38 more
  1. 2024Cost Aware Best Arm Identificationcited by 13
  2. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
  3. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  4. 2022Non-Asymptotic Analysis of a UCB-based Top Two Algorithmcited by 11
  5. 2026Best Arm Identification with LLM Judges and Limited Humancited by 10
  6. 2024Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streamscited by 9
  7. 2024Optimal Multi-Fidelity Best-Arm Identificationcited by 9
  8. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  9. 2023Best Arm Identification with Fairness Constraints on Subpopulationscited by 8
  10. 2023Optimal Best-Arm Identification in Bandits with Access to Offline Datacited by 8
  11. 2023Optimal Batched Best Arm Identificationcited by 8
  12. 2025Anytime-valid, Bayes-assisted, Prediction-Powered Inferencecited by 7
  13. 2022On the complexity of All varepsilon-Best Arms Identificationcited by 6
  14. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  15. 2023Time-Uniform Confidence Spheres for Means of Random Vectorscited by 6
  16. 2024Best-Arm Identification in Unimodal Banditscited by 6
  17. 2021PAC Mode Estimation using PPR Martingale Confidence Sequencescited by 5
  18. 2022On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structurecited by 5
  19. 2024Anytime-Valid Inference for Double/Debiased Machine Learning of Causal Parameterscited by 5
  20. 2024Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Banditscited by 5
  21. 2024Preference-based Pure Explorationcited by 5
  22. 2022Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gapcited by 4
  23. 2023Thompson Exploration with Best Challenger Rule in Best Arm Identificationcited by 4
  24. 2025Pure Exploration with Feedback Graphscited by 4
  25. 2025FraPPE: Fast and Efficient Preference-based Pure Explorationcited by 4
  26. 2025Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequencescited by 4
  27. 2022Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraintscited by 3
  28. 2022SPRT-based Efficient Best Arm Identification in Stochastic Banditscited by 3
  29. 2022Best Arm Identification with Contextual Information under a Small Gapcited by 3
  30. 2023AdaStop: adaptive statistical testing for sound comparisons of Deep RL agentscited by 3
  31. 2023Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budgetcited by 3
  32. 2024Fair Best Arm Identification with Fixed Confidencecited by 3
  33. 2025The Batch Complexity of Bandit Pure Explorationcited by 3
  34. 2025Best-of-∞ -- Asymptotic Performance of Test-Time LLM Ensemblingcited by 3
  35. 2023Best Arm Identification in Stochastic Bandits: Beyond β-optimalitycited by 2
  36. 2025Best Group Identification in Multi-Objective Banditscited by 2
  37. 2025Constrained Pareto Set Identification with Bandit Feedbackcited by 2
  38. 2025E-Scores for (In)Correctness Assessment of Generative Model Outputscited by 2

50 most cited of 76 All 76 (JSON)