Near-Optimal Confidence Sequences for Bounded Random Variables

Arun Kuchibhotla · Qinqing Zheng

Keywords: [ Algorithms ] [ Online Learning Algorithms ]

[ Abstract ]
[ Paper ]
[ Visit Poster at Spot A4 in Virtual World ] [ Visit Poster at Spot A4 in Virtual World ]
Wed 21 Jul 9 a.m. PDT — 11 a.m. PDT
Spotlight presentation: Online Learning 1
Wed 21 Jul 6 a.m. PDT — 7 a.m. PDT


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{\'e}r-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.

Chat is not available.