Timezone: »

 
Spotlight
Near-Optimal Confidence Sequences for Bounded Random Variables
Arun Kuchibhotla · Qinqing Zheng

Wed Jul 21 06:20 AM -- 06:25 AM (PDT) @
in Online Learning 1 »

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.

Keywords: Algorithms · Online Learning Algorithms

Author Information

Arun Kuchibhotla (Carnegie Mellon University)
Qinqing Zheng (Facebook AI Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors