STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals
Václav Voráček, Francesco Orabona · 2025
Read STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals by Václav Voráček, Francesco Orabona (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22422.txt.
Introduction
Confidence intervals for a bounded mean can be tightened by recalculating the target of a bet, Václav Voráček and Francesco Orabona show in a 2025 paper. Their method is called STaR-Bets. Building such intervals is a classical statistics problem with uses across science and machine learning, and tight intervals matter most when sampling is expensive.
Betting algorithms are the current state of the art and give optimal confidence sequences. In the fixed horizon setting, though, they are either suboptimal or heuristic, with strong empirical results but no finite-time guarantee. No betting method was known to guarantee the optimal width. The new algorithm bridges that gap and, in tests, beats the competitor the authors compare against.
Catalog record
| CREATOR | Václav Voráček, Francesco Orabona |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22422
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals Thanks: work done while with University of Tübingen. Václav Voráček, Francesco Orabona Abstract The construction of confidence intervals for the mean of a bounded random variable is a classical problem in statistics with numerous applications in machine learning and virtually all scientific fields. In particular, obtaining the tightest possible confidence intervals is vital every time the sampling of the random variables is expensive. The current state-of-the-art method to construct confidence intervals is by using betting algorithms. This is a very successful approach for deriving optimal confidence sequences, even matching the rate of law of iterated logarithms. However, in the fixed horizon setting, these approaches are either sub-optimal or based on heuristic solutions with strong empirical performance but without a finite-time guarantee. Hence, no betting-based algorithm guaranteeing the optimal 𝒪 ( σ 2 log 1 δ n ) \mathcal{O}(\sqrt{\frac{\sigma^{2}\log\frac{1}{\delta}}{n}}) width of the confidence intervals are known. This work bridges this gap. We propose a betting-based algorithm to compute confidence intervals that empirically outperforms the competitors. Our betting strategy uses the optimal strategy in every step (in a certain sense), whereas the standard betting methods choose a constant strategy in advance. Leveraging this fact results in strict improvements even for classical concentration inequalities, such as the ones of Hoeffding or Bernstein. Moreover, we also prove that the width of our confidence intervals is optimal up to an 1 + o ( 1 ) 1+o(1) factor diminishing with n n . The code is available on github . 1 Introduction Quantifying uncertainty is a cornerstone of statistical inference, and Confidence Intervals (CIs) remain one of the most widely used tools for this purpose. Typically constructed within the frequentist paradigm, a (1-\delta) -CI provides a range of plausible values for an unknown parameter, derived from observed data, with the guarantee that the procedure yields intervals covering the true parameter value in 1-\delta proportion of hypothetical repetitions. In particular, in this paper we are interested in providing CI for the mean of a bounded random variable. So, more formally, after observing n i.i.d. samples X_{1},\dots,X_{n} of a random variable in [0,1] with mean \mu , we want to find l_{n} and u_{n} such that \mathbb{P}\{\mu\leq u_{n}\}\geq 1-\delta/2\ \text{ and }\ \mathbb{P}\{\mu\geq l_{n}\}\geq 1-\delta/2~. (1) We aim for narrow confidence intervals, i.e., small u_{n}-l_{n} . Classical methods provide well-established procedures with optimal asymptotic properties, but their performance deteriorates when n is small. This paper explores an alternative approach to constructing confidence intervals, based on the framework of game-theoretic probability and sequential betting. In this framework, the algorithm makes sequential bets on the values of X_{i}-m . If m is close to the true mean \mu , then the random variables X_{i}-m is approximately zero mean. Now, it is intuitive that no strategy can hope to gain money betting on a fair random variable and we expect little money betting on a random variable with mean very close to zero. Conversely, if the algorithm makes enough money, we can infer that m is far from the true mean \mu . The above reasoning can be carried out in rigorous way, using the concept of test martingales [ 19 ] . In particular, one can show that we can construct the confidence interval as the set of all values of m such that the wealth does not reach \frac{2}{\delta} . In this view, a better betting algorithm results in a tighter confidence interval. These approaches give state-of-the-art theoretical and empirical results in the time-uniform case. However, they fall short in the finite-sample regime, both in theory and in practice. Contributions. In this paper, we propose a new strategy for betting in the finite-sample regime. We explicitly take into account how many rounds we still have and that by how much we still need to multiply our current wealth to reach the threshold. This give rise to a new family of betting algorithms for the finite-sample setting, the \bigstar -algorithms (STaR=Sequential Target-Recalculating). We show that this strategy can be used, for example, to immediately improve the confidence intervals calculated through Hoeffding and Bernstein, without losing anything . Moreover, we present a new algorithm, STaR-Bets, that achieve valid state-of-the-art confidence intervals on a variety of distributions. Additionally, we show that its variant, Bets, attains the optimal rates for confidence interval width—marking the first such result for betting-based confidence interval methods. 2 Related Work The literature on how to construct confidence intervals for the mean of a random variable is vast. Classic results like Hoeffding’s [ 10 ] and Bernstein’s [ 3 ] inequalities require the knowledge of the variance of the random variable (which can always upper bounded for bounded random variables). Later, Maurer and Pontil [12] and Audibert et al. [2] proved that it is possible to prove empirical Bernstein’s inequalities, that is, with optimal dependency on the variance but without its prior knowledge. However, these results tend to be loose on small samples because they sacrifice the tightness of the interval with a simple and interpretable formula. On the other hand, it is possible to design procedures to numerically find the intervals, without having a closed formula. A classic example is the Clopper-Pearson confidence interval [ 5 ] for Bernoulli random variables, that is obtained by inverting the Cumulative Distribution Function (CDF) of the binomial distribution. This approach is general, in the sense that it can be applied to any random variable when the CDF is known. However, no optimal solution is known if we do not have prior knowledge of the CDF of the random variable. An alternative approach is the betting one, proposed by Cover [7] for the finite-sample case and by Shafer and Vovk [20] and Shafer et al. [19] for the time-uniform case, as a general way to perform statistical testing of hypotheses. The first paper to consider an implementable strategy for testing through betting is Hendriks [9] . Later, Jun and Orabona [11] proposed to design the betting algorithms by specifically minimizing the regret w.r.t. a constant betting scheme. Waudby-Smith and Ramdas [23] suggested the use of betting heuristics, motivated by asymptotic analyses and online convex optimization approaches to betting algorithms [ 14 , 8 ] . Recently, Orabona and Jun [13] have shown that regret-based betting algorithms based on universal portfolio algorithms [ 6 ] can recover the optimal law of iterated logarithm too, and achieve state-of-the-art performance for time-uniform confidence intervals. However, these approaches fail to give optimal widths in the finite-sample regime that we consider in this paper. We explicitly note that even the optimal portfolio strategy for the finite-time setting [ 15 ] does not achieve the optimal widths because it suffers from an additional \log T factor. This is due to the fact that minimizing the regret with respect to a fixed strategy does not seem to be right objective to derive confidence intervals in the finite-sample case. The problem of achieving the tightest possible confidence interval for random variables for small samples has received a lot of interest in the statistical community. It is enough to point out that even the Clopper-Pearson approach has been considered to be too wasteful, because of the discrete nature