Near-Optimal Confidence Sequences for Bounded Random Variables
arXiv:2006.05022
Abstract
Many inference problems, such as sequential decision problems like A/B testing, adaptive sampling schemes like bandit selection, are often online in nature. The fundamental problem for online inference is to provide a sequence of confidence intervals that are valid uniformly over the growing-into-infinity sample sizes. To address this question, we provide a near-optimal confidence sequence for bounded random variables by utilizing Bentkus' concentration results. We show that it improves on the existing approaches that use the Cram{é}r-Chernoff technique such as the Hoeffding, Bernstein, and Bennett inequalities. The resulting confidence sequence is confirmed to be favorable in both synthetic coverage problems and an application to adaptive stopping algorithms.
arXiv commentAccepted to ICML 2021
References in corpus (5)
- lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
- On Hoeffding's inequalities
- Always Valid Inference: Bringing Sequential Analysis to A/B Testing
- Binomial upper bounds on generalized moments and tail probabilities of (super)martingales with differences bounded from above
- On Finding the Largest Mean Among Many