Timezone: »
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.
Author Information
Arun Kuchibhotla (Carnegie Mellon University)
Qinqing Zheng (Facebook AI Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Near-Optimal Confidence Sequences for Bounded Random Variables »
Wed. Jul 21st 04:00 -- 06:00 PM Room
More from the Same Authors
-
2023 Poster: Semi-Supervised Offline Reinforcement Learning with Action-Free Trajectories »
Qinqing Zheng · Mikael Henaff · Brandon Amos · Aditya Grover -
2023 Poster: Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validation »
Jin-Hong Du · Pratik Patil · Arun Kuchibhotla -
2023 Oral: Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validation »
Jin-Hong Du · Pratik Patil · Arun Kuchibhotla -
2022 Poster: Online Decision Transformer »
Qinqing Zheng · Amy Zhang · Aditya Grover -
2022 Oral: Online Decision Transformer »
Qinqing Zheng · Amy Zhang · Aditya Grover -
2020 Poster: Sharp Composition Bounds for Gaussian Differential Privacy via Edgeworth Expansion »
Qinqing Zheng · Jinshuo Dong · Qi Long · Weijie Su