Research map / Learning theory and algorithms / Sample complexity
STAR-Bets: Sequential TArget-Recalculating Bets for Tighter Confidence Intervals
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes STaR-Bets, a betting-based fixed-horizon confidence interval method for bounded means that adapts each bet to remaining rounds and remaining wealth needed, with a proof of near-optimal interval width.
Problem
Constructing tight finite-sample (fixed horizon) confidence intervals for the mean of a bounded random variable; existing betting-based methods are either suboptimal or heuristic without finite-time guarantees.
Approach
A STaR (Sequential Target-Recalculating) betting principle that sets each bet using the remaining rounds n-t and the log-wealth still needed log(1/(W delta)); applied to Hoeffding/Bernstein tests it never widens intervals, and combined with a second-moment estimator it yields STaR-Bets with width matching the optimal sqrt(sigma^2 log(1/delta)/n) up to 1+o(1).
Key results
- STaR-Bets produces shorter intervals than Hedged-CI across Beta and Bernoulli settings, with coverage statistically close to 1-delta in most cases.
- On Bernoulli samples, STaR-Bets performs very close to randomized Clopper-Pearson and beats standard Clopper-Pearson at small sample sizes.
- Theorem proves STaR-Bets width matches the optimal sqrt(sigma^2 log(1/delta)/n) up to a 1+O(n^{-1/4}) factor, with validity holding by test-process argument.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use STaR-Bets instead of standard Clopper-Pearson | Bernoulli confidence intervals · Bernoulli, small sample sizes | interval width | Helped |
| Use STaR-Bets instead of randomized Clopper-Pearson | Bernoulli confidence intervals · Bernoulli, small sample sizes | interval width | Mixed |
| Use STaR-Bets instead of Hedged-CI | Bernoulli confidence intervals · Bernoulli | interval width | Helped |
| Use STaR-Bets instead of T-test | Beta confidence intervals · Beta distributions with a > b | interval width | Hurt |
| Use STaR-Bets instead of T-test | Beta confidence intervals · Beta distributions with b > a | interval width | Helped |
| Use STaR-Bets instead of Hedged-CI | Beta confidence intervals · Beta | interval width | Helped |
| Use STaR-Bets instead of T-test | Beta confidence intervals · Beta, increasing sample size | interval width | No clear effect |
| Use STaR-Bets | Confidence interval methods · Most tested settings | coverage | No clear effect |
| Add the STaR component to Bets (ablation) | Bets · Bernoulli and Beta experiments | interval width | Helped |
| Add the STaR component to Bets (ablation) | Bets · Confidence interval experiments | interval width | Helped |
| Add the final-round bet (ablation) | Bets and STaR-Bets · Confidence interval experiments | interval width | Helped |
| Remove the final-round bet (ablation) | STaR-Bets · Confidence interval experiments | interval width | Hurt |
Surprising findings
- The T-test interval, which lacks guaranteed coverage, has coverage noticeably above 1-delta on some Beta settings while being shorter than STaR-Bets when a > b.
Limitations
- Optimality proven only for Bets (the base algorithm); the STaR-augmented combination is supported only by empirical evidence.
- Assumes n much larger than log(1/delta).
- Last-round randomization and clipping choices are heuristic implementation details; the constant c in the second-moment estimator is chosen heuristically.
Experimental setup
Benchmarks: Beta distribution mean estimation Bernoulli mean estimation
Metrics: confidence interval width empirical coverage CDF of lower confidence bounds
Baselines: T-test Clopper-Pearson Randomized Clopper-Pearson Hedged-CI Hoeffding empirical Bernstein PMBSS
Builds on: Hoeffding's inequality Bernstein's inequality Hedged-CI betting Clopper-Pearson Freedman's inequality
Closest papers by meaning
- Gambling-Based Confidence Sequences for Bounded Random Vectors (ICML 2024 · similarity 0.87)
- On the Tightness and Computational Tractability of Higher-Dimensional Confidence Sequences (NeurIPS 2026 · similarity 0.86)
- Sequential Kernel Goodness-of-fit Testing (ICML 2024 · similarity 0.83)
- Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.83)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.83)
- Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams (ICML 2024 · similarity 0.82)
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.