Near-Optimal Confidence Sequences for Bounded Random Variables
This work addresses the fundamental challenge of online inference for sequential decision-making, offering incremental improvements over prior confidence sequence methods.
The paper tackles the problem of providing confidence intervals valid uniformly over growing sample sizes in online inference, such as A/B testing and bandit selection, by developing a near-optimal confidence sequence for bounded random variables using Bentkus' concentration results, which improves on existing methods like Hoeffding, Bernstein, and Bennett inequalities and is validated in synthetic coverage problems and adaptive stopping applications.
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.