STAR-Bets: Sequential TArget-Recalculating Bets for Tighter Confidence Intervals

We thank the Reviewer for their feedback. We agree that our writing could be improved, but this is an easy change that we can do in the camera ready version. Moreover, given that the only listed weaknesses are the improvable writing and the misunderstanding of the unfair comparison, we would be grateful if the Reviewer could reconsider their score as foreshadowed in the review.

We answer the specific questions in the following.

Weaknesses

Scenarios might be unclear and only seem somewhat related to the aims of the paper
We present several examples of betting games and strategies from which we made some observations that motivate our proposed betting strategy. We could have just stated our algorithm, but we feel it is better to present intuitions on why one can improve over a constant betting strategy. Notably, Reviewer QY1z mentioned that they specifically liked this part.

Unfair comparison with Hedged CS
This is not correct: The comparison is completely fair because we compare with the fixed time version of Hedged (Remark 3 of [19]), called Hedged CI. The confusion of the Reviewer is probably due the fact that [19] presents two Hedged algorithms: Hedged-CI (fixed time) and Hedged-CS (time-uniform).

Questions

Why not intervals at all times t<n?
As you note, we can (trivially) do this and compute the "current" interval after every observed sample at no additional cost with the same final interval. However, we explicitly decided not to do it because our sole focus is on CIs and not CSs, and we did not want to confuse the readers. When one needs a CS, we would not recommend our algorithm.

Why only bounded means? (we assume this is a typo and should have been means of bounded random variables)
The class of bounded random variables is a rich and practical regime (it is rather easy to check if my random variable is bounded, rather than checking if it has (say) c-subgaussian tails). It is probably possible to extend this idea to other classes of confidence intervals (the linked references are for confidence sequences, so it cannot be directly applied here).

Does STaR generalize to hedged?
As we write above, there are hedged algorithms: CI and CS. Hedged CI differs only mildly (in the variance estimator, for the sake of proof) from our "base" algorithm (cf, lines 281-284) and the STaR technique can be directly applied to it; one would get similar empirical results to ours. On the other hand, the STaR technique is not applicable to CSs (there is no end time when we want to have either 1/delta or 0 money).

Limitations

The results of this work may be applicable to many testing-by-betting and anytime valid methods as a way to covert anytime-valid -processes to fixed-time, non asymptotic confidence intervals. However, the authors focus specifically on bounded-mean confidence intervals. I would be happy to improve my score if the authors provide intuition on this framing.
As the Reviewers note, our approach might have a larger number of applications. In this paper, we decided to focus on the problem of confidence intervals for bounded random variables because this is a widely known setting that is both foundational and important from a practical point of view. As a matter of fact, we started working on this topic because applied people explicitly asked us for a better method for the calculation of valid confidence intervals of bounded random variables for deep learning applications, as, for example, in

Angelopoulos AN, Bates S, Fannjiang C, Jordan MI, Zrnic T, Prediction-powered inference, Science, 2023

In future work, we will explore the application of the STaR method to other settings in the testing-by-betting literature.

Anytime guarantees missing
As we wrote above, it is trivial to get the anytime-version. We decided to not include it for the sake of clarity.

Comparison with [4]
Thank you for pointing out the work of Koning & van Meer (2025). They indeed have a similar n-t term, but the connection to our work is only apparent. More in detail, their method does not improve the test at time n, instead they want to (potentially) provide some intermediate rejections at times t<n. This is not at all our objective. Instead, we aim at improving the rejection rate at t=n. Hence, their paper and our work are orthogonal. We will add a discussion on this point to avoid confusions between the two methods.

We thank the Reviewer for clarifying their view. Here, we just want to explain one subtle point.

This method bets all wealth by the time $n$, so the error budget is only spread across all $t \leq n$

This is not completely exact: our algorithm bets more aggressively approaching $n$, but this does not imply that by the time we reach $n$ the wealth is 0. In fact, even betting everything, to lose all the money we should observe a value of the random variable of 0 or 1 (depending on the bet). Hence, unless the random variable has probability mass exactly on 0 and 1, in practice the algorithm will likely have available wealth in all means to be tested. So, if needed, one can keep using the algorithm after $n$, just setting the betting strategy to anything else after $n$. In this view, Hedged-CI and our algorithm are not fundamentally different in how they use with the budget $\delta$ over the infinite number of rounds. The only real difference is that our algorithm will try its best to use its budget in the first $n$ rounds, that directly results in tighter intervals.

We thank the Reviewer for their feedback. In the following we answer their specific concerns.

Weaknesses

Bootstrapping algorithms are overlooked
We (and apparently previous work on this topic too) are not aware of bootstrapping algorithms for confidence intervals with guaranteed coverages. That said, we would be happy to be corrected by the Reviewer on this point.

The problem setup is never rigorously defined … In particular, are the samples $X_1, ..., X_n$ assumed i.i.d.?
Actually, it is defined: Please see the sentence starting at the 6th line of the paper (line 25) starting “So, more formally, after observing $n$ i.i.d. samples $X_1, \dots , X_n$ ..”

Sequential algorithms do not possess any advantage over non-sequential "batch" algorithms. However (lines 171-173) suggest the opposite
While there is no advantage in general, lines 171-173 comment on the fact that the derivation of standard (“batch”) concentration inequalities, as Hoeffding, Bennett, and Bernstein, can be interpreted as sequential betting schemes where one selects a constant bet beforehand. In these cases, we provably show that this can be improved by recalculating the best bet before every observation and this is the STaR technique.

Further comments

• A typo; thanks.
• Thm 2 is not stated clearly Actually, Theorem 2 is stated clearly: It is a scheme, so you can choose the individual components to arrive at different confidence intervals. All the confidence intervals we derived in the paper (Hoeffding, Bernstein, all our new algorithms) are correct by Theorem 2.
• relation W on X is not mentioned The relation can be arbitrary (even none), it is only important that W is a test process under the null hypothesis.
• inline equation at odds with the fact that W is a supermartingale It is actually correct because here we comment on a specific test process (the display just before) which happens to be a martingale, thus the equality.

Questions

What are the model assumptions and exact problem formulation?
See first paragraph of the paper. Observe i.i.d. sample $X_1, ... X_n$ and produce confidence interval for the mean parameter. Then we want to produce as tight (short) confidence interval as possible.

Why don’t you start with the easier batch setting and rather do it sequentially?
We believe the Reviewer might have the wrong intuition on this problem. In fact, in Section 4.1 we explicitly prove that the sequential approach is never worse and it can be better than the batch approach (see Corollary 5). Let’s try to give some intuition on why this is the case, for example considering the Bernstein bound (Appendix B). In the Bernstein case, we know that the optimal asymptotic bet (that is, the “batch” bet) depends on the variance of the random variable. However, this kind of bet does not take into account what actually happened on a specific sequence, that is, it is independent of the outcomes. Instead, by sequentially recalculating the optimal bet, we take into account the past outcomes, through their effect on the wealth. At this point the Reviewer might wonder why only using the past to calculate a bet and not the future too? This would not work, because we still need to generate a supermartingale. Finally, we urge the Reviewer to focus on the fact 1) the previous SotA results were also from a sequential method (Hedged-CI) and 2) our approach gives SotA results on this problem.

We thank the Reviewer for their feedback. In the following we address their comments and questions.

Weaknesses

This is a classical and well-studied topic, it is not clear what substantive new theoretical insights this work contributes beyond existing methods.
We proposed a method producing significantly shorter confidence intervals than state of the art (see Appendix C, we performed and condensed (literally) millions of experiments) with significant evidence that further improvements are unlikely to be significant. On the theory side, we provided the first analysis of a betting based confidence interval reaching the optimal width (up to a constant factor).

Questions

For the related work section, it would help significantly if the author can provide a table that summarizes the theoretical guarantees (e.g., rates or forms of optimality) for each method discussed. It would greatly help clarify the landscape. At present, the discussion is purely verbal, and the claims regarding optimality remain somewhat vague.
In general, in the setting of bounded random variables the optimal rates are known and attained. However, the “optimal” methods are known to perform poorly on small sample sizes. This has motivated the line of research of confidence intervals and confidence sequences based on betting algorithms, because they give rise to much shorter intervals. Before our paper, the SotA method was by Waudby-Smith and Ramdas (2024) (247 citations). We establish a new SotA by beating their method both empirically (see experiments) and theoretically (see Theorem 8, whereas the methods in Waudby-Smith and Ramdas (2024) have only an asymptotic convergence without a rate).

Related to the point above, in the experiment section, when comparing different methods, could the authors write out each method more explicitly (maybe in the appendix)?
Good point, we can definitely expand the discussion of the competing methods in the Appendix.

Why does Figure 2 present two plots with different numbers of methods shown?
Figure 2 presents results for two different random variables (see titles): Beta(5,1) and Bernoulli(0.3). Note that the Clopper-Pearson interval is applicable only to Bernoulli (binomial) random variables, thus is not present in the plot with the Beta distribution experiments.

Typo in definition 1, should be martingale
No, we are happy to include supermartingales (yielding Hoeffding and Bernstein inequalities) as indicated by footnote 2.

Typo in proof of Theorem 2
Yes, thank you, we will fix.

Unclear notation from the proof of Proposition 4: The author define $l^{H} = argmin_{\lambda \in \mathcal{C}} \sum_{i=1}^{n} X_{i}$. However, it is unclear how does the optimization objective related to $\lambda$?
We are sorry for the (understandable) confusion, we will fix this. The set of feasible lambdas $C$ depends on $\sum_i X_i$ and it should have been a condition rather than a constraint set. $\ell^H$ is the argmin over $\lambda$ of the following optimization problem ($m,n,\delta$ are constants):

Interpretation of Theorem 8: Could the author elaborate a bit more on how this result shows the optimal width? How does it rely on the knowledge of the variance $\sigma^2$?
The result shows that whenever you want a confidence interval of the optimal width up to a (1+c) factor for c >0, there is always a number of samples (depending on the variance and other things) such that the algorithm produces a confidence interval of the optimal width up to the given factor. To determine the minimal number of samples needed, we must know the variance, but the algorithm is running without this knowledge. This is necessary, since the minimal width of confidence interval is $\log(1/\delta)/n$ and we need $\sigma^2 > \log(1/\delta)/n$ for the asymptotical regime to kick in. (Also, it is easy to show that $n=O(c^{-8})$ when treating everything as else as constants).

Limitations

An in-depth comparison on the theoretical properties between the proposed method and existing methods is lacking.
As said above, optimality in this setting is easy. Instead, one strives for numerically small intervals and theoretical guarantees. The only other algorithms to satisfy these constraints are the algorithms in Waudby-Smith and Ramdas (2024). They propose to use heuristic strategies that only guarantees an asymptotic convergence to the optimal width of the confidence interval, but no explicit rate. Note that the absence of rate might not be fixable because their estimator of the variance might converge arbitrarily slowly on some distributions. Instead, we prove a finite time rate for our approach. On this point, it is also easy to calculate that $c$ in Theorem 8 decays as $n^{-1/8}$ (this treats all the other problem parameters as constants when we only increase $n$) when selecting constants in the proof as In Appendix A (lines 405-408).

We thank the Reviewer for their careful reading of our work and for being available to raise their score if the definition/meaning of $\ell^{H}$ is clarified and the typos corrected. We will fix all the typos the Reviewers found and in the following we answer their specific questions.

Questions

Confusion about $\ell^H$
We are sorry for the (understandable) confusion, we will fix this. The set of feasible lambdas $C$ depends on $\sum_i X_i$ and it should have been a condition rather than a constraint set. $\ell^H$ is the argmin over $\lambda$ of the following optimization problem ($m,n,\delta$ are constants):

How quickly does $c$ decay in theorem 8?
It is easy to calculate that $c$ decays as $n^{-1/8}$ (this treats all the other problem parameters as constants when we only increase $n$) when selecting constants in the proof as In Appendix A (lines 405-408). That said, we did not try to optimize this rate and a potentially better choice of constants might exist. We will elaborate on this in the revised version of the paper.

We thank the Reviewer for their feedback. In the following we address their comments and questions.

Weaknesses

Theorem 3 (typo, should be thm 8) only considers alg 3.
Yes, this is true (and clearly stated in the statement). We have proven that STaR technique helps certain classes of betting strategies, but the improvements of Alg. 4 over Alg. 3 are only empirical. That said, Appendix C provides evidence that already Alg. 3 beats the SotA empirically, and in terms of guarantees by virtue of Theorem 8.

The focus is on bounded random variables - what about more general settings?
Generally speaking, the technique is not limited to bounded random variables but to betting algorithms of a specific form. Given how fundamental is the setting of bounded random variables, both in theory and in practice, we find it very difficult to consider it as a limitation. As a proof of this point of view, the most important work in this area (Waudby-Smith and Ramdas 2024) considers exactly the same setting. As a matter of fact, we started working on this topic because applied people explicitly asked us for a better method for the calculation of valid confidence intervals of bounded random variables for deep learning applications, as, for example, in

Angelopoulos AN, Bates S, Fannjiang C, Jordan MI, Zrnic T, Prediction-powered inference, Science, 2023

In future work, we will explore the application of the STaR method to other settings in the testing-by-betting literature.

Questions

How is $O(\sqrt{\frac{\sigma^2 \log(1/\delta)}{n}})$ the right order?
Intuitively, this is predicted by central limit theorem, where the sample mean $\frac{1}{n} \sum_{i=1}^{n} X_i$ behaves like a normal random variable with standard deviation $s = \sqrt{\sigma^2/n}$, then the standard Gaussian tail bound asserts $\delta = P[ X - E[X] > t] \leq \exp(-t^2/(2s^2))$, then solving for $t$ gives us the desired expression (we have that $\sigma^2 = \text{Var}[X]$).

Combining lower and upper confidence bound at different confidence levels
Yes, this is completely possible. In (1) we presented the standard way to get two-sided confidence intervals from the one sided ones (the focus of the paper are the one sided ones). If the application requires splitting the probabilities differently, everything will work just as good.

Typo after line 119
Yes, thank you, there should have been a minus sign in the second bracket.