# Estimating means of bounded random variables by betting

arXiv: https://arxiv.org/abs/2010.09686 · HTML: https://mlsanity.com/paper/2010.09686/

## Key facts

- Cited by 169 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2020.

## Built on by (most cited first, 30 of 169)

- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Prediction-Powered Inference](https://mlsanity.com/paper/2301.09633/) (2023)
- [Active Statistical Inference](https://mlsanity.com/paper/2403.03208/) (2024)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Tracking the risk of a deployed model and detecting harmful distribution shifts](https://mlsanity.com/paper/2110.06177/) (2021)
- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [E-detectors: a nonparametric framework for sequential change detection](https://mlsanity.com/paper/2203.03532/) (2022)
- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Fast yet Safe: Early-Exiting with Risk Control](https://mlsanity.com/paper/2405.20915/) (2024)
- [Time-uniform central limit theory and asymptotic confidence sequences](https://mlsanity.com/paper/2103.06476/) (2021)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [E-Values Expand the Scope of Conformal Prediction](https://mlsanity.com/paper/2503.13050/) (2025)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [Auditing Fairness by Betting](https://mlsanity.com/paper/2305.17570/) (2023)
- [Semiparametric Efficient Inference in Adaptive Experiments](https://mlsanity.com/paper/2311.18274/) (2023)
- [Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach](https://mlsanity.com/paper/2408.07511/) (2024)
- [Experts Don't Cheat: Learning What You Don't Know By Predicting Pairs](https://mlsanity.com/paper/2402.08733/) (2024)
- [Martingale Methods for Sequential Estimation of Convex Functionals and Divergences](https://mlsanity.com/paper/2103.09267/) (2021)
- [Runtime Monitoring of Dynamic Fairness Properties](https://mlsanity.com/paper/2305.04699/) (2023)
- [Sequential Kernelized Independence Testing](https://mlsanity.com/paper/2212.07383/) (2022)
- [Prediction-Powered E-Values](https://mlsanity.com/paper/2502.04294/) (2025)
- [WATCH: Adaptive Monitoring for AI Deployments via Weighted-Conformal Martingales](https://mlsanity.com/paper/2505.04608/) (2025)
- [Adaptive Learn-then-Test: Statistically Valid and Efficient Hyperparameter Selection](https://mlsanity.com/paper/2409.15844/) (2024)
- [Model-X Sequential Testing for Conditional Independence via Testing by Betting](https://mlsanity.com/paper/2210.00354/) (2022)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Active, anytime-valid risk controlling prediction sets](https://mlsanity.com/paper/2406.10490/) (2024)
- [Reliable and Scalable Robot Policy Evaluation with Imperfect Simulators](https://mlsanity.com/paper/2510.04354/) (2025)
- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [Semi-Supervised Risk Control via Prediction-Powered Inference](https://mlsanity.com/paper/2412.11174/) (2024)

## Abstract (arXiv)

This paper derives confidence intervals (CI) and time-uniform confidence sequences (CS) for the classical problem of estimating an unknown mean from bounded observations. We present a general approach for deriving concentration bounds, that can be seen as a generalization and improvement of the celebrated Chernoff method. At its heart, it is based on a class of composite nonnegative martingales, with strong connections to testing by betting and the method of mixtures. We show how to extend these ideas to sampling without replacement, another heavily studied problem. In all cases, our bounds are adaptive to the unknown variance, and empirically vastly outperform existing approaches based on Hoeffding or empirical Bernstein inequalities and their recent supermartingale generalizations. In short, we establish a new state-of-the-art for four fundamental problems: CSs and CIs for bounded means, when sampling with and without replacement.