Research map / Bandits and online learning / Multi-armed bandits
Near-Optimal Confidence Sequences for Bounded Random Variables
Arun K Kuchibhotla, Qinqing Zheng
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace classical concentration-based confidence sequences with Bentkus confidence sequences | Adaptive mean estimation · Bounded-mean data generated as averages of m uniform samples | stopping-time ratio to second best: 0.79, 0.66, 0.72, 0.86, 0.84 | Improved |
| Replace A-Hoeffding confidence sequences with A-Bentkus confidence sequences | Best-arm identification algorithm · Bernoulli-reward best-arm identification | sample count: 52% to 61% | Improved |
| Use Bentkus rather than classical confidence sequences | Confidence sequences for the mean · Bernoulli(0.1), typically n ≥ 20 | confidence interval width | Improved |
| Use Bentkus rather than A-Hoeffding | Confidence sequences for the mean · Bernoulli(0.5), moderate to large sample sizes | confidence interval width | Improved |
| Use Bentkus rather than A-Hoeffding | Confidence sequences for the mean · Bernoulli(0.5), moderate to large sample sizes | confidence interval width | No clear effect |
| Truncate confidence intervals to [0, 1] (ablation) | A-Hoeffding in best-arm identification · Best-arm identification, K = 2 | iterations: 107 -> 132 | Hurt |
| Use cumulative minimum/maximum bounds to define the sampling radius (ablation) | A-Bentkus in best-arm identification · Best-arm identification | sample complexity | Hurt |
| Use Bernstein-type confidence sequences instead of A-Hoeffding | Best-arm identification algorithm · Best-arm identification | sample complexity | Hurt |
| Use the A-Bentkus method | Confidence sequences for the mean · Bernoulli(0.1), 1000 replications | miscoverage rate: 0.001 | No clear effect |
| Use a faster-growing stitching function h(k) (ablation) | A-Bentkus confidence sequence · Bounded random variables | confidence interval width | Hurt |
Closest papers by meaning
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.88)
- On the Asymptotic Optimality of Confidence Interval Based Algorithms for Fixed Confidence MABs (AAAI 2025 · similarity 0.88)
- Improved Online Confidence Bounds for Multinomial Logistic Bandits (ICML 2025 · similarity 0.86)
- A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits (NeurIPS 2024 · similarity 0.86)
- Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.86)
- Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
