Near-Optimal Confidence Sequences for Bounded Random Variables

Abstract

Many inference problems, such as sequential decision problems like A/B testing, adaptive sampling schemes like bandit selection, are often on- line in nature. The fundamental problem for on- line 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 Cramer-Chernoff technique such as the Hoeffding, Bernstein, and Bennett inequalities. The resulting confidence sequence is confirmed to be favorable in synthetic coverage problems, adaptive stopping algorithms, and multi-armed bandit problems.