STAR-Bets: Sequential TArget-Recalculating Bets for Tighter Confidence Intervals
Authors: Vaclav Voracek
Francesco Orabona
Venue: NeurIPS 2025 poster ()
Keywords: confidence intervals
testing by betting
concentration inequality
empirical bernstein bound
Primary area: theory
TL;DR: We propose a construction of confidence intervals for bounded r.vs. via betting using a new betting strategy

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 $\mathcal{O}(\sqrt{\frac{\sigma^2\log\frac1\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)$ factor diminishing with $n$.

STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals
Václav Voráček Second Foundation* vasek. www.wekwgaaoail......o com
Francesco Orabona
King Abdullah University of Science and Technology francesco@orabona.cmm
Abstract
The construction of confidence intervals for the mean of bounded random variable is classical problem in statistics with numerous applications in machine learn- ing 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 construct confidence intervals is by using betting algorithms. This is a very successful approach for deriving optimal confidence sequences, even matching rate of law of iterated logarithms. However, in the fixed horizon setting, these approaches or based on heuristic solutions with strong empirical performance but without a finite-time guarantee. Hence, no betting-base based algorithm guarantecing the optimal
either sub-optimal
log E v..
width of the confidence intervals are known. This work bridges this gap. We propose betting-bast 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 constant strategy in advance. Leveraging this fact results in strict improve- ments even for classical concentration inequalities, such as the ones Hoeffding Bernstein. Moreover, also prove that the width of our confidence intervals is optimal up to an + o(1) factor diminishing with n. The code is available github
O(V
1 Introduction
Quantifying uncertainty is a cornerstone of statistical inference, and Confidence Intervals (CIs) remain of the most widely used tools for this purpose. Typically constructed within the frequentist paradigm, a (1 - 6)- 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 - 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 i.i.d. samples XI,...,X X,, of a random variable in [0, 1] with mean μt, we want to find I, and un such that
P(u un) > 5/2 and P(u (
8/2.
We aim for narrow confidence intervals, i.e., small u., -,-- 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 the framework of game-theoretic probability and sequential betting. In this framework, the algorithm makes sequential bets the values of X; m. If m is close to the true mean μ., then the random
work done while with University of Tübingen.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

variables X; 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 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 yr. The above reasoning can be carried out in rigorous way, using the concept of test martingales [20]. 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 g. In this view, a better betting algorithm results in tighter confidence interval.
These approaches give state-of-the-ar theoretical and empirical results in the time-uniform case. However, they fall short in the inite-sample regime, both in theory and in practice.
Contributions. In this paper, we propose a 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 reach the threshold. This give rise new family of betting algorithms for the finite-sample setting, the *-algorithms (STae=-equential Target-Recalculatie We show that this strategy can be used, for example, 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 wirth-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 's [10] and Bernstein's 3 incqualities 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- 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 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 66 for the finite-sample case and by Shafer and Vovk [99 and Shafer et al. [20] for the time-uniform case, as general way to perform statistical testing of hypotheses. The first paper to consider an implementable strategy for testing through betting is Hendriks (.. Later, Jun and Orabona [1]] proposed to design the betting algorithms by specifically minimizing the regret w.r.t. a constant betting scheme. Waudhy-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 [I3] have shown that regret-based betting algorithms based on universal portfolio algorithms 7 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 sample regime that 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 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 Hlopper-Pearson approach has been considered to be too wasteful, because of the discrete nature of the CDF that does not allow an exact inversion P In this view, sometimes people prefer to use approximate methods, that is, methods that do not guarantee the exact level of confidence 1 - 8, because they are less conservative [see, e.g., the reviews in I [8]. Recently, Phan et al. [16] proposed an approach based on constructing an envelope that contains the CDF of the random variable with
"See Voracek 22, for optimal, randomized procedure.

---

high probability. This approach was very promising in the small sample regime, however in Section 6 we will show that our approach consistently better.
In this paper, we build on the ideas of Cover 66 regarding the construction of optimal betting strategies for Bernoulli random variables and design general betting scheme in that spirit.
A Coin-Bettinn Game
The statistical testing framework rely is based betting. In particular, we will set up simple betting games based on the hypothesis we want to test. The outcome of the testing will be linked to how much money betting algorithm makes. Hence, we will be interested in designing "optimal" betting strategies. In the following, we first describe a simple betting game to draw some intuition about the optimal betting strategies. Then, in Section we formally introduce the testing by betting framework.
We introduce simple sequential coin betting game in which we bet on the outcomes of coin toss. If the result is Heads, we gain the staked amount, otherwise we lose it. The game is as follows: We will bet for n rounds, and win if we multiply our initial wealth by least factor of k. Hence, are not interested in how much money we make, but only if we pass a certain threshold.
Let's now discuss some possible scenarios, to see how the optimal betting strategy changes.
Scenario 1, n 1, 2: optimal to bet everything and if the outcome is Heads, win.
Generally, in the last round we should always bet everything we have. Scenario
5, 1: 0.9: this case, is optimal not bet anything, and we win.
Scenario 3, n = 2, k 4/3: Consider the possible outcomes: Heads/Heads, Hcads/Tails, Tails/Heads, Tails/Tails. In the last case we always lose. we want to win in the Heads/Tails case, we would need to bet 1/3, in which case we reach the desired wealth after observing Heads and we stop betting. In the case we first observe Tails and we end up with 2/3 money. Then, we recover Scenario and bet all the money.
Before we continue with more general scenarios, we make some observations. These considerations will be useful when we will link betting strategies to the proof of standard concentration inequalities. such as Hoeffding's or Bernstein's.
The original values of n, do not matter. Instead, what matter are how these quantities "change over time," that is, how many rounds are left and how many times still need to multiply our wealth.
When we hit the required wealth, we should stop betting.
For a given n, the smaller is, the less we need to bet. Conversely, & is large, we need to bet aggressively.
We should always finish the game by either going bankrupt by hitting the target.
Already in (6 Example 31, it was shown that if a betting strategy is optimal (for hypothesis testing, in the sense of Proposition[]] (7). it either has reach the target, or go bankrupt. The contrary was also proven, that there exists such an algorithm. More generally, all possible outcomes of the coin-betting game were described. Let's now consider more complex scenarios.
Scenario 4, n,, le 2 1+ 2- In this case, our bets would be x 2-", so that we win as soon as we observe a single heads outcome.
Scenario 5, n, A & 2": this case, our bets would be s in general, as we need to roughly double wealth every round and hope for lots of heads.
Scenario 6, n, k: In the general case, bet & /log k/nn n. In this way, if we observe H heads and T tails, the wealth would be roughly
log n
H
log k
T
2 (1
log k.
T (
log k:
H-T
1
1
1
1
k
n1
71
as long as H -
T -
vn log k.
3

---

Let us examine the event H - - lolog:: If the coin is fair, the event H - T log in which case we successfully multiplied our wealth by factor k- happens with probability at most x k. and it is not just coincidence. Thus, if we multiply our wealth by factor of k, we can rule out the possibility that the game is fair at confidence level 1 - This statement is the cornerttone of the testing by betting framework and we will make formal and prove it in the next section.
Testing and Confidence Intervals by Betting
Before describing this technique in detail, introduce the precise mathematical framework. We start with the definition of test processes: Sequences of random variables modeling fair betting games. In these games, our wealth always non-nege non-negative and stays constant (or decreases) in expectation. In the literature, test processes are also called e-processes and they are marperr)-atiiggllss..
Definition 1 (Test process). Let Wo, Wi,.. W,,, be a sequence of non-negative random variables. We call it test process if [B[W)] 1 and I[[ Wo...., Wi] W,, for i > 0.
Next, Markov's 's inequality quantifies how unlikely it is for test process to grow large. Proposition (Markov's inequality). Let Wo. W1 W...., W,, be a test process. For any ō E (0,1) )) holds that TP [ > }/} & 8.
Proof. [[ & E [[ and Wn O. Then, 1 1. & 8W, and take expectation.
Finally, we introduce the betting-basse based confidence intervals.
Theorem confidence interval obtained within the following scheme has coverage at least
Confidence interval by betting
Objective:
Construct a (1 - conffidenee interval for [[ from X Xn E [0,
Procedure:
For each m E [0, 1], form a null hypothesis Ho(m) [[ Let S = {m Ho(m) not rejected by betting at 1 level].
Outcome:
Interval I such that S I, then I is (1 ò)-CI for [[X].
Testing by betting
Objective:
Test the null hypothesis Ho on XI...., X,, at confidence level 1 Construct W Wn such that it is test process under Ho. If Wn > 1. reject Ho at confidence level 1 - 5.
Procedure:
Outcome:
Proof. If the mean j is not contained the resulting confidence interval, the null hypothesis Hu(p) E[X]= μ was rejected by betting. The corresponding sequence WH,..., W is a test
process and because it was rejected, we have W > J. But this happens with probability at most 1 by Markov's inequality.
Test process under null hypothesis: popular process (optimal in a certain sense [4] for testing a null hypothesis Ho(m) m for a given m E [0. is:
W
W W (1 + 4 (X, - (X), for i 1,
(2)
where l E
m-1+ is our betting strategy. The betting strategy is, of course, independent of X but can depend on X and the other known quantities m, n, Under the null hypothesis, we have E[W++1 W
1 1
Wil B[W.]. Additionally, by the bound on e,, we ensure that W > 0, and so in 1 is a test process. We have already used this test process in the bein-betting example, if we identify Heads (resp. Tails) with (resp. 0) and set m 1.4 then f,/2 2 is the fraction of money we bet.
(Wr')
Theorem 2 provides scheme on how to construct confidence intervals by testing all the possible values m of the expectation of the random variable. Such an approach would require test continuum of hypotheses which is impossible in general. There are two standard ways to proceed:
We allow for the game be unfair against us.

---

Algorithm 1 Hoeffding testing
Algorithm 2 * Hoeffding testing
Require: i.idd. X1, ...... X, [0. 1]
Require: iid. XI...., Xn E [0, 1]
Require: 8> 0, m E [0, 11. W
Require: > 0, m E [0. 1,.1 W
for 1 = 1... n do
for 1...n do
n
e V (log {) /n
e# - 18 (log W 1)
/nn (n-t+1)
W W exp ( (Xx - m) _
W - W exp
( (Xt m)
(0
if W > 3 then Reject Ho(m) :m E[X]
W > 3 then
Reject Ho(m) m E[X]
1. Root finding: If the function m W has simple structure (e.g.. quasi-convex), then the set of non-rejected mean candidates form an interval and we can easily find its end points by numerical methods, even in closed form.
2. Discretization: Discretize the interval [0, into G grid points my < m2 <... < mg- Use the same betting strategies for all m in m, & m & M,+1 and all 1 & i < G 1 this case, the function m W" is monotonic in between the grid points, and so evaluating Wm only at grid-points provide sufficient information for the construction of the confidence interval. We adopt this approach.
1. In
4.1 Hoeffding and Sequential Target-Recalculee (*) Bets
In this section, we recover the classical confidence intervals by Hoeffding's inequality within the betting framework using Theorem 2 recovering Bernstein's 's intervals follows the same steps, is deferred to Appendix B Our plan is to show that the Hoeffding betting strategy violates the design principles we have discussed earlier in this section. Hence, we can fix those problems and obtain tighter confidence intervals, essentially for free. More generally, we introduce *-bttting strategies as the ones that have the better design principles.
We will use the following lemma to derive the test processes.
Lemma 3 (Hoeffding's 's lemma). Let X [0, 1] with mean μ E[X], then
c (x- 2 & V
E
Furthermore, the sequence Wo 1, W
W, exp (e (e. p) f)
f for 2 0 is a test process.
We compare the testing-by- by- betting algorithms. The standard Hoeffding test in Algorithm T and our improved, HHoefffiig test in Algorithm [ We observe that the constant betting of Algorithm [ violates our desiderata for a good betting algorithm. Concretely, may happen that at some point Additionally, it does adapt the current
W > 3. but keep betting and end up with W situation of how much do we need to increase W and in how many rounds. In particular, the terms n said, the only important quantities are i) dw: how many times we need multiply our wealth and ii) n t: the number of remaining rounds. This motivates the following definition.
and log defining the bet become irrelevant as f increases. Instead,
We call a betting algorithm for a test process (Wi)__ *algorrihhm if it uses the quantities the log W, and n to compute the bet at time f.
As an example, we can immediately generate the -version of the Hoeffding algorithm in Algorithm and prove that it is never worse than the original algorithm.
Proposition 4. Let m [0, 1]. Whenever Algorithm rejects the null hypothesis Ho(m). m E[X]. then so does Algorithm if they share the realizations X,, 1 & t &
5

---

Final wealth depending on m
Development of the wealth with m 0.86
20
20
Hoeffding *-Hoeffding
Wealth W
Hoeffding
HHHeeldiing
Bernstein * Bernstein
10
Bernstein
10
Bernstein
0.82
0.84
0.86
0.88
0.9
0
200
400
600
800
1000
Candidate mean m
Iteration Ł
Figure 1: Comparison of the Algorithms 12 5 and 6 with = 0.05 on 1000 realizations of the Bernoulli random variable with mean 0.9. (L): We show the final value of W depending the choice of m for the algorithms. The vanilla versions have exponential dependency on m, while the * versions virtually always end up with W E {0. 3 Additionally, we can confirm that the versions reject the null hypothesis for more values of m. (R): Here we show the evolution of W throughout that the Bernstein's 's testing algorithm already
the runs of the algorithmss for m 0.86. We achieved the required wealth, but later lost it, unlike * *-Bernstein's 's testing which stopped betting after reaching it. We can also see that towards the end, * *-Hofffding betting started betting very aggressively in order to have a chance to reach the desired wealth.
Proof. Consider Algorithm| 1 We first show that e is selected in a way that > X; required to reject the null hypothesis smallest possible. That is:
n Σ 1-1
1
arg min AER X E.E(
min
X
s.t. A -X)
log
The constraint is E X, 3 + log / A + nA/8. Minimizing the RHS over X, the solution is
v 1 8log t/nn
Now, consider Algorithm By the same argument, f time l is minimizing Σi= X; under the constraint that the null hypothesis is rejected. Consequently, the required Σn X₃ for Algorithm 2 is initially the same for Algorithm I but it decreases whenever e changes with respect to the previous iteration.
Corollary 5. Consider generating confidence intervals using Theorem 2 and betting algorithm.
The confidence intervals given by the betting Algorithm hare are not-wider than the confidence intervals by Algorithm [ all other things being equal. Moreover, there are cases when Algorithm produces strictly smaller confidence intervals.
Many popular confidence intervals including Hoeffding's ss Bernstein's, and Bennet's can benefit from *-httting. A standard way to derive concentration inequalities is to bound the cumulant generating function. We have seen this in Hoeffding's 's inequality with E [exp(E f (X - -]1)] & exp((%/8). In general, we get IE [exp(E-
Remark 6.
minimize >" X; under the condition that e >>_ (X; m) - log f(é) > log 5. which is precisely the reason
( (X- 44)] f((). Then, l is selected
why *bbtting outperforms standard betting Proposition 4 We demonstrate this in Figure L
We observe that alggorithms usually end with either 0 or 1/ wealth. This is natural consequence of the adaptiveness, as we described in Figure 1 from both sides if * algorithm reaches the target, it stops betting. On the other hand, if the target not reached yet, the bets become more and more aggressive, often resulting in bankruptcy. This is not bad property. If we want to design confidence intervals with exact coverage
6, the following proposition shows that it is actually necessary.
Proposition 7. Consider the process W; = W & (X; ()) with Wo = 1 and algorithm for selecting bets l, If the algorithm always finishes with W,, {0, }3 then the algorithm falsely rejects the hypothesis Ho(u) p μ confidence level 1 - 8 with probability precisely 1 -.
Proof. By construction, R[W,] 1. Let the algorithm halt with Wr 1 with probability p. then B[W,] [ G. yiclding p 8 as required.
D

---

SeaR-Bets Algorithm
In the previous section, we have described the key concept of * --betting that can be implemented within the majority of common (finite time) betting schemes. It remains to choose a good betting scheme. So, here will introduce our algorithm: -ets- Now, will present an informal reasoning to derive a first version of our betting algorithm. Then, we prove formally that it produces intervals with the optimal width.
[0, I] be an i.id. sample of a random variable X for which we aim to find a one-sided interval for the mean parameter. In the following, we also assume that log z. that is, our sample is large enough. This is not restrictive assumption. If it is violated, then optimal confidence interval has width for general distribution on [0. 1] and cannot hope to have short interval anyway.
Let ,,,...,,,, Xn
We use the processes from of the form W;+ = (1 {(x; - m)) to refute the hypothesis m [. So, we construct a betting strategy that aims at achieving at least wealth after n rounds. First, we approximate the logarithm of the final wealth using a second-order Taylor expansion:
l (X, (0)mmm3
Σ log(1 + 4 (X; -m) = Σ 4 (x m)
(4)
For the moment, will assume that this is good approximation, but eventually, will derive it formally.
Define S= - m) and V > 1 (X; mm)?. From the r.h.s. of 4 the constant bet e*
maximizing the approximate wealth is
12 * arg max ES V
S v max ES
62
(18)2 2 V.
2 -
(5)
A reasonable approach is to try to estimate f* over time, in order to achieve a wealth close to the one in (5). This is roughly the approach followed in previous work [see, c.g.. Instead, here we follow the approach suggested in Waudby-Smith and Ramdas [23]: We are only interested in the case where the (approximate) log- weelthh reaches log 1.- In other words, the outcome of the betting game is binary: We either reach the desired log- wealth for the candidate of the mean, m, and we reject the null hypothesis Ho(m) E[X] = m, or we fail to do so. This means that we want
(L+)2
V log 1
2 log V
Estimating V online, Shekhar and Ramdas 21 proved that this strategy will give asymptotically aiming for finite-time guarantee, which
optimal confidence intervals almost surely. However, requires a completely different angle of attack.
First of all, it might not be immediately apparent why we expressed ( as function of V only, while we could also get an S term. The reason that this is an easier quantity to estimate: Estimating V. B[(X- m E ((1) is easier than estimating S z E[X m] E O( in the terms of relative error. Relative error relevant because if we overestimate by factor 2, then we would end up with 0 (approximated)
Also, observe that e* 0(( log // which justifies the Taylor approximation in 4 Indeed, we aim to approximate and [,, ml & 1. so the error of the Taylor approximation
))
log 1 8
1 log 8
log
n. O
O
This error is of an order smaller than log 1 as long as n >> log 3. as we have assumed. Recalling our goal of achieving a log-wealth of log }. this means that the Taylor approximation is sufficiently good.
Let us examine the approximate length of the confidence interval consisting of candidate means m for which we did not reach log-weald wealth log ::
242 V
2 log A
1 = S 2V log & 2 log
1 5
e* S
< log 3
= sv
(6)
2
V
3
7

---

Algorithm 3 Testing with Bets
Algorithm 4 Testing with *-Bets
,,,...,,,,, Require: i..d. ,,...,, Xn n [0, 1] Require: a. > 0, m E [0, I].n
Require: iid. X;..... Xn E [0, 1]
Require: ar, ō > 0, m E [0. 10.1].n V 0, IgW < 0
V 0, IgW
for & I & TI do
for $ & n do
V/(l- - + 10 10 An
v - V/(L -1) + 10log on
(1-1)
(1-1)* ^
8 V 22og (n(x))
8 V 2( ; (gg))/((r
1)u)
lgW 1gW log( 1 2(X; mm)
IgW - lgW + log( + {(X; - m))
V - + (X; m)²
V - V + (X; m)
if IgW z log then Rejected
if Igg log then Rejected
We can further approximate V [[V] nV[x] + EIS E[S nV[x], since nV[x] E O(n). while E[S]2/n E (1), then the bound from (6) matches the width from the Bernstein's inequality, which is the one of Normal approximation and thus cannot be improved.
The only missing ingredient is how to estimate V over time. Recalling that we aim for a low relative nog error, after seeing t outcomes we will use the estimator V/n [x=n(x:-m)² + 82 " where the second term is carefully constructed to guarantee that the estimate has small relative eror with high probability (depending on a) uniformly over m and
& n.
The final algorithm is shown in Algorithm 3 where we run the above betting procedure for possible values of m [0, 1] and reject them as mean candidates if the log-wealth is at least log 1.-
Theorem 8. For every random variable X [0, 1] with mean μ and variance o² 0, every a, E (0, 1), and e > O, there is no depending on a, 8, o² .c, such that for all n t na, Algorithm rejects at confidence level 1 5 every satisfying
21
X
(2 + log
m
with probubility at least 1 a. Furthermore, we have that no O(c when treating the other variables as constants.
The proof is in Appendix
Corollary 9. Algorithm can be used in the frumework of Theorem 2 (using the discretization technique for constructing intervals) to construct confidence intervals of the width up to a 1 + o(1) factor diminishing with
Our proposed algorithm is -Bets in Algorithm the --version of Algorithm 3 implementation details in Appendix D
We discuss the
We remark that while the algorithm is tailored to confidence intervals, it naturally produces confidence sequence as a br-pruduct. More concretely, we do not need to construct the test process Wi.... W. from Theorem at once and then collect the non-rejected mean candidates. We can construct the test processes sequentially when new samples arrive and after each of which we recompute the confidence interval. A mild modification (either replace Markov's inequality by Ville's inequality, or do some brain gymnastics) of the original argument shows that all the confidence intervals contain the mean simuitaneously with probability 1 8 in the frequentist sense. Straightforward modification of Theorem g shows that the width of the confidence interval after
observing samples is (up to a constant factor) /lo nn/t2. This being said, we believe that there are generally better options when one needs confidence sequences discussed in Section 2 such as 13
We conclude this section by emphasizing that while we have proven an optimality result of Algo- rithm in Theorem 3 and other optimality results of -ttechnique in Proposition when they are combined in A we were not able to prove these optimality properties, and we only have empirical evidence the superiority over the competitors. The validity of the hypothesis testing (and thus of the resulting confidence interval) still holds by Theorem 2
8

---

Average distance mean
Beta(5,1), n=8, 16, ... 256, delta=0.05
Bernoulli(0.3) n=8, 16, ... 256, delta=0.05
100
STaft bet Hedged-C1
10
Hoediding
Emp, Bernstein
PMBSS
random CP
10
10-1
10a
10a Number of samples
10a
10a
We directly compare the widths of the confidence intervals. Note the log log scale. For all the methods and every n = 8, . we have estimated the mean 1000 of fresh realization of the corresponding random variable and plotted the average distance to the mean. (L): When estimating the mean of beta distribution, we observe that that with increasing we are getting closer to the performance T-tsst (R): When estimating Bernoulli mean, the performance of Bets is very similar to the specialized optimal methods.
Figure 2:
Experiments
Now we provide some experiments suggesting that *-Bets yields shorter confidence intervals than alternative methods. Here, we provide a "teaser" our experiments, while the extensive experimental evaluation is in Appendix [ We identified several methods as our direct or indirect competitors and will briefly discuss them.
Confidence interval derived from the T-test. This is a widely used confidence interval in practice, but it does not have guaranteed coverage general. We show that our x-Bets algorithm is competitive with the T-test and has guaranteed coverage for X E [0, 1].
Clopper-Pearson (5] is the best deterministic confidence interval for a binomial sample (sum of Bernoulli random variables). Nevertheless, B-Bets often produces shorter intervals.
Randomized Clopper-Pearson competitive.
22 is the optimal binomial confidence interval. B-Bets is still
Hedged-CI CI (3 is confidence interval based on betting and currently the best known algorithm for constructing confidence intervals. It is very similar to our Bets algorithm from 3 with comparable performance. The difference lies in the fact the we estimate B[(X m)² while [33 estimates [[ J. However, our --ets is significantly stronger.
Hoeffding's inequality and the empirical Bernstein bound are the standard ways to construct confidence intervals, and so we include them in the experiments. Empirical Bernstein bound is usually weak because of the additive terms. Hoeffding's 's inequality is generally weak, but when V[X] ~ z. it is competitive with some of the methods, but not with * -Bes..
The method" of Phan al. [16] was state of the art at the time of introduction, aiming at short intervals for very small (10 - 50) sample sizes. We show that *-Bets is is stronger even this regime. Furthermore, this method does not scale well to large samples.
First, we perform several experiments with Beta and Bernoulli distribution to quickly assess the competing methods. We show in Figure how the widths of the confidence intervals evolve we increase and conclude, that from our direct competitors, Hedged- CI of Waudby-Smith and Ramdas 23 is the strongest one, thus we use it in our further experiments. In Figure we provide teaser for the extensive experimental evaluation Appendix C Specially, we introduce CDF figure that shows the distribution of the lower-confidence bounds over 1000 repetitions of the experiments with the same setting, which allows for a systematic comparison of the methods.
It is called practical mean bounds for small samples, abbreviate it PMBSS.

---

Beta(0.1, 2), n=100, delta=0.05
Beta(2, 0.1), n=100, delta=0.05
1.00
1.00
STaR-bot
0.75
Hedged-CI
0.75
quantile
0.50
0.50
0.25
0.25
0.00
0.00
0.85
0.90
0.95
0.00
0.02
0.04
0.06
Lower confidence bound
(ernoulli(0.3). 3030, delta=0.00
(ernoulli(O.3). 1000, 0.05
1.00
1.00
0.75
0.75
quantile
0.50
0.50
STaRtbet Hedged-CI
0.25
CP
0.25
random CP
0.00
0.00
0.1
0.2
0.3
0.24
0.26
0.28
0.30
0.32
Lower confidence bound
Figure 3: CDF figure: When curve corresponding method passes through a point (ær y). means that the y-fraction (of 1000 repetitions) of lower confidence bounds was smaller than a. The vertical magenta line shows the mean position, and the vertical one shows the 1 quantile. We can see that in both cases, * -Bts passes through the intersection, implying that the coverage is > 1 1 8. (Top) Estimation of the mean of Beta distribution (I.): we can see that T-test produces shorter intervals than *-Bets, but that it has significantly smaller coverage than claimed. (R): Here, *-Bets produces shortest intervals. (Bottom) Estimation of the mean of Bernoulli distribution using (I.) and 1000 (R) samples. We observe that in the low sample regime, B-Bets is mildly worse than the unbeatable randomized Clopper-Pearte Pearson, arguably better than standard Clopper-Peanee Pearson, and significantly better than Hedging of [23). In the regime of larger samples, we see that *-Bets stays very close to the optimal intervals, while the competitor is still significantly worse.
Conclusions: We have introduced *ttechnique in the construction of confidence intervals that directly (strictly) improves many betting algorithms and concentration inequalities, such as the ones of Hoeffding and Bernstein. Then, we have proposed a new betting algorithm for which he have proven that can construct confidence intervals of the optimal length up to diminishing factor. While the *Ktechnique is powerful in experiments, we have only proven that never hurts (certain class of algorithms) and that it usually helps. How much it helps remains an open theoretical question.
10

---

References
[1] A. Agresti and B. A. Coull. Approximate better than "exact" for interval estimation of binomial proportions. The American Statistician, 52(2):119 10::1169,,,, 1998.
[2] J.-Y. Audibert, R. Munos, and C. Szepesvári. Variance estimates and exploration function in multi-armed bandit. In CERTIS Research Report 07-31. 2007.
[3] S. Bernstein. On modification of Chebyshev's inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):3849, 49, 1924.
[4] E. Clerico. On the optimality of coin-betting for mean estimation. arXiv preprint arXiv:2412.02640, 2024.
[5] C. J. Clopper and E. Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4))404-413, 1934.
[6] T. M Cover. Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin. Technical Report 12, Department of Statistics, Stanford University, 1974. URL
edu. wwwp:ss41qmmmme
[7] T. M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Transactions on Information Theory, 42(2):348-363, 1996.
[8] A. Cutkosky and F. Orabona. Black-box reductions for parameter-free free online learning in Banach spaces. In Proc. of the Conference on Learning Theory (COLT), 2018.
[9] H. Hendriks. Test martingales for bounded random variables. arXiv preprint arXiv:2109.08923, 2018.
[10] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30 1963.
[11] K.-. Jun and F. Orabona. Parameter-free online convex optimization with sub-exponential noise. In Proc. of the Conference Learning Theory (COLT), 2019.
[12] A. Maurer and M. Pontil. Empirical Bernstein bounds and sample variance penalization. In Proc. of the Conference on Learning Theory, 2009.
[13] F. Orabona and K.-S. Jun. Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Trans. Inf. Theory, 70(1):436 4544366455..00 2024.
[14] F. Orabona and D. Pál. Coin betting and paremeter-free online learning. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 577-585. Curran Associates, Inc., 2016.
[15] E. Ordentlich and T. M. Cover. The cost of achieving the best portfolio in hindsight. Mathematics of Operations Research, 23(4):960-982, 1998.
[16] M. Phan, P. Thomas, and E. Learned-Miller. Towards practical mean bounds for small samples. In International Conference Machine Learning, pages 8567-8576. PMLR, 2021.
[17] A. Ramdas and Wang. Hypothesis testing with e-values. arXiv preprint arXiv:2410.23614. 2024.
[18] M. F. Schilling and J. A. Doi. A coverage probability approach to finding an optimal binomial confidence procedure. The American Statistician, 68(3):133-145, 2014.
[19] G. Shafer and V. Vovk. Probability and finance: it's 's only game! John Wiley & Sons, 2001.
[20] G. Shafer, A. Shen, N. Vereshchagin, and V. Vovk. Test martingales, Bayes factors and p-values. Statistical Science, 26(1):84-101, 2011.
[21] S. Shekhar and A. Ramdas. On the near-optimality of betting confidence sets for bounded means. arXiv preprint arXiv:2310001547, 2023.

---

[22] V. Voracek. Treatment of statistical estimation problems in randomized smoothing for adver- sarial robustness. Advances in Neural Information Processing Systems, 37:133464-133486 2024.
[23] I. Waudby-Smine and A. Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(1):1-27, 2024.
A Proof of Theorem
Before we prove the theorem, we introduce several propositions we use in the sequel. We start with a (time uniform) version of Bennett's inequality.
Proposition 10 (part of Lemma I of (2). Let XI....,X, Xn & b be i..dd real-valued random variables and let V/ b- b- B[X]. For any E (0, 1), simultaneously for all & 1 & n, we have
1 b'
Ex, B[X]) & / 2 log
log
5
More generally, let X1.... Xn be sequence of martingale differences (i.e., E[X; XI,1) = 0 for all i). Let nV = LLV, X (x...,,X--II,, For any ö E (0,1), si- multaneously for all & n, we huve
X1-11.
E 2 log
1 5+300 log
1
The first part of the proposition is implied by the second one and is the standard Freedman's s inequality up to a factor in the last term. This factor was removed in (2), but the result was stated for an i.idd sequence (the first part of the lemma) and not for martingale differences. However, the proof of 2 applies also to the second part.
Remark 11.
Now, we use it to bound the deviation of our second moment estimator from the mean for all m and t simultancously with high probability.
Proposition 12. Let X X,, E [o, 1] be i.i.d. random variables with variance V[x] = 0². For any (0, 1). simaltaneously for all 1 & & and all E [0,1] we have all the following inequalities with probability at least ac
E (X, m)
10n log
18n log
11n log (E - mm
EI(( - m)²] 1 V
30.
21=1 (X, m)²
10n log
18n log
9n log
> E[(X m]
1
t2
PE (X -2
P - m)]
X²
2no² log 1
log 1
E[X2]
12
31
D X;
2no log
1
1 log
E[x]
<
n
(8)
t2
3t
Proof. We use Proposition 10 on random variables X, -X,XXX2 -X2 XX,, and union bound, using the fact
that V[X & V[X] as X T 1]. This yields the latter two identities. Then, as X2 22-2mXX -2m + m² (X - m))? we have accumulated 1 + 2m & 3 of the identical error terms, yielding
Σ E (X,
m) [[ m) &
18no2 log
log
<\
t
from which we express the stated bounds, using B[(X m) 2 0² and log f & n mlog / The lower bound then follows from completing the square.
D
12

---

Further, we use the uniform version of Bennett's inequality to bound the sum of the observations in the first rounds; again, for all m simultaneously.
Proposition 13. Let XI..... Xn [0, 1] be i.id. random variables with mean y B[X] and variance x² = V[X]. and lei 0 & X & C be random variables such that X is independent of X for j e i for some positive constant C. With probability least a we have for all [0. μul and all
1 < t & simultaneussl that
2 (mm)
XxXX; - -m) &C
(1 (1 log
+
log
+ t(p - m)
3
a
MXX, - -m) 2 -C (V 122002 log
log
a
3
Σ (X; - m) & CN. 2102 log + log
2 a
a 3
Proof. We decompose the random variables Ax(x; m) into a martingale difference sequence
M₁ = >x(X - (6) and a drift term D; >z(1e m). We bound deterministically the drift term:
Dj < <C((u--m)
and so holds for all m and t simultaneously. We bound the martingale using the Freedman's- styyle inequality from Proposition I0
2
C 2
P
Σ M
3 ON.
2to² log a
3 <a
log
Adding up the two bounds concludes the proof.
Finally, we introduce a quadratic lower-bound of a logarithm near zero. Lemma 14. Let 1/2 and |z|
2c then
log(1 + 2) 3 cx?
Proof. We inspect the behavior of f(x) log(1 (1 + x) x + cr First, f(0) = Now we look at the derivatives (a) ) = 1/(x + 1) 1 2cr and f'(x) = -1(r 1)a + 2c. Setting f to zero, we get ax1 2c - 2cr) = 0, so the roots are I and x2 = 1/(2c) - these points are local extremes, concretely local minimum and local maximum respectively by the second derivative test,
and so the inequality holds for & > 1/(2c)
Now are ready to restate the main theorem
to prove.
Theorem 15 (Theorem & restated). For every random variable X [0. 1] with mean μ and variance o² > 0, every a, (0, ), and O, there is no depending on a, 5, o² e, such that for all ž no- Algorithm 3 rejects at confidence level 1 - 8 every satisfying
Σ X
(2 +
e)
log
m
01
with probability at least 1 a.
Proof. Statement (9) holds true if the events from Proposition 12 and Proposition 13 (applied on Xj...., Xeyn, to be specified later) are met. Namely, Proposition 12 ensures that our estimator of [[(X- m)) is never too small and is consistent. also ensures that empirical mean of converges to j. Proposition 13 provides bound on the wealth in early stage. We note that both of the propositions hold uniformly for m [0, n]. Thus, we instantiate both of the bounds (with failure probabilities a/2) and further assume that the events are met. Throughout the sketch, will be
13

---

introducing new constants on the fly. For all constants, we have that we can choose large enough no make them arbitrarily close to
We fix m E [0. 14] whose exact expression will be decided at the end of the proof. Let Y X m and 1t m.. Let lapt
V u((=+e0 By Lemma 14, for any constant 1/2 > > 0, we have that log(1 + (Y) > EY (1/2 01 e for all & & V2lap--
2
Analysis of the run of algorithm: We split the steps into an arbitrarily (relatively) short "warm up" phase of c2n steps, where things can go poorly, but the effect of this will be negligible. Then, there will be "convergent phase" of (1 c2)n steps, in which (1 c3 ca) E l, (1 C3 Copt- We briefly comment on the constants. By Lemma
14 it holds that 01 & 30t = ((1/vn) as can set it to On (n-a). 1). By Proposition
long lupe 0.1. 02 is arbitrary,
12 we have C3 &
( 1 log ", //(on) 11 a/ //(on))) and so given the choice of cz, we have C3 O(n1/44.
Warm up phase: In this phase, we have 0 & l & Vloa per the second part of Proposition 12 and the fact that [[(X-m) o² + +
First, deterministically upper bound the quadratic term:
(aa+
Can
Σ
c1 +
e.Y? > 2n (a+ ol ((0
1 2
4 log B
C2
g2
Next, by Proposition
13 applied on
and C= V2lapi. we have
Cam
Σ 4(X: - m) 2-
4log] 3
V /22gn02 log
1 log
4
n1o2 + 52)
3
-
4log 1 log² 2 On( + E2)
> -2
202 log
log a
+
where we see that both the quadratic and linear term go to zero increases and Co decreases.
Convergent phase: By Proposition
12 have (1 cap & l & (1 Cop From the
definition of &, we have that e, Σ
Y
2 2log] 8. Thus,
Σ
n
RY?
a
Gy?
C3
2
2
n
+ C3
2 log
1 5
C3
C3
1
Now, add up the lower bounds from the warm-up phase and from the quadratic term in the convergent case:
Wamn-up phase
Quadratic term convergent plase
4 4 4ogg 1 log² 4 (n + x2)
4log 0² + E2
+ C3
2
-21 202 log log
+ V
a Ci
02
Ci +
log
a
2
2
1 C3
(1 + c4) log 5¹
for some C4 > O. Given the choices of constants above, we can have ca; cs, E O(n 2/4) for the constants to come. Finally, we lower bound the log-wealth:
log(1 + &YY) > lopil1 - c3)
Σ
Yi xx)
(1 + ct) co) 3.
1=cgn+1
which is greater than log 1 if
o2+v2
2 X; m
(2 + c1)
(02 E2) log 1
(10)
(1
22 63) (1 (z)
n
14

---

From Proposition 13
we have assumed the events
2220 log
1
4
X
pC2
log
2
-c/ /eo/vi-
pol
V1
3n
1=1
and
20² log
402 log a
4
(X; 11) 2
log
12
3n
a
Vn
i=c5n+1
We now reveal our choice of m:
D - X; - (cs +cs+ (2)
x2 log x
co + 0n
402
log
m
71
n
vn
We now show the value of m we have selected satisfies bigger than J. Observe that
10 and it will result in a log-wealth
A E X;
E Lizenn+1 X;
(1
02)
11 02)
n
-i=1
X;
Σ
Lizezn+1 X; -1 1
_1=1 X,
+ C2
cafl
n
n1
Hence, we have
12 Xs
02)m m > (cs + v2) (02 + c2) log
Linegn+1
Moreover, observe that these last inequalities apply for all < m.
Thus, for the chosen m,, we have reached log-wealth log 3 and so it is rejected. Finally, we have assumed the event 1 ΣT X, nl| & 1//n from ( So, recalling that = / m, for our choice of m also have e 1/ Hence, to 22 and c22 Cg arbitrarily close O, finishing the proof of the main part. Given our tracking of constants,
make (cs + 22) e/a) arbitrarily close
see that the final leading term is off by factor + O(n 11/4,, concluding the second statement.
B Bernstein betting
We derive the algorithm for Bernstein testing referenced in Figure and show that *-ing it is strict improvement. The steps are analogical to the Hoeffding's 's betting derivation. We note that the provided version of Bernstein's 'ns inequality is mildly weaker than the standard one in the interest of simplicity.
Lemma 16 (Bernstein simplified). Ler X E [0, 1] with mean = E[X] and variance V[X], then
E ((x-
1,, VeER.
(11)
Furthermore, the sequence Wo 1, W = exp (X, - - 028) for R 0 is a test process.
Proposition 17. Let m [0.1]. Whenever Algorithm 5 rejects the null hypothesis Ho(m) m ] then so does Algorithm 6 if they share the realizations X,, 1 1& &
Proof. Consider Algorithm 5 We first show that e is selected in way that Σn X, required to reject the null hypothesis smallest possible. That is:
g arg min
min
X
s.t. A
2 (X, m) no"x² log
ABR X 10. 1=1
15

---

The constraint is Ei=1 X; 2 nm + log //A+ no? Minimizing the RHS over X, the solution is log // (no2).
Now, consider Algorithm By the same argument, e at time I is minimizing Di= X under the constraint that the null hypothesis is rejected. Consequently, the required Σ X; for Algorithm is initially the same as for Algorithm but it decreases whenever & changes with respect to the previous iteration.
Algorithm 5 Bernstein testing
Algorithm 6 * Bernstein testing
Require: i.i.d. XI,...,X6 X [0.
Require: i..dd XI...., Xn E [0.
Require: 8 0, m E [0, 11. n, 0² V[X] W
Require: 0, m E [0. 11. 0² V[x] W -
for t = 1... n.....no do
for 1... do
gd V (log {)) (nno?)
2 - v (log w8 /enn/(nn/ 1)0?)
W - W exp (e" (Xe - mm)= (2)
W - W exp (4 (X. m) (of
if W > then Reject Ho(m) m E[X]
W > 1 then
Reject Ho(m) E[x]
C Experiments
We provide CDF plots as we believe they contain most information about the behavior of the confidence interval. We repeat the description from the main paper.
In short, the more the curve is to the right, the better it is.
Every algorithm provides lower bound on the mean parameter of the corresponding distribution. We repeat the experiment 1000 times and for every algorithm plot the empirical CDF of the produced lower bounds. Lee. a curve passing through point (x, 3) should be understood as y-fraccions of the lower bounds are smaller than We include vertical and a horizontal magenta line representing the mean (vertical) and the vertical line at point (H, 8'), where y is the true mean and 8' is the empirical coverage. We have zoomed in to a box centered at (14, 1 111-)) to see what is the coverage; also, we have added black 0.95 -ne--ddedd confidence intervals. If the eCDF meets the vertical
8 (horizontal) as the desired coverage. The eCDF of the algorithm passes
vertical lines corresponding magenta line above (resp. below) the black line, it has coverage smaller (resp. bigger) than 1 - at confidence level 0.95. All algorithms apart from T-test have guaranteed coverage least 1 5, so if they occur under the black line, it by a chance.
C.1 Experimental results
Here, provide general experimental results. We always show STaR bet from Algorithm 4 with details from [D] Hedged-CI is from (23] with the default settings. T-test and (randomized) Clopper- Pearson intervals are standard.
Bernoulli:
Here, we can see that * is performing very closely to randomized CooperrPPersson and outperforming standard Clopper-Pearson small sample sizes. On the larder sample sizes, the performance of all three algorithms become very similar, significantly outperforming Hedge-CI.
Here, compete with T-test based confidence interval with formal guarantees. We can see that as long as a > b (a, are parameters of the beta distributions), T-test is outperforming *; however, it clearly has larger coverage than 1 1-6 8. violating the principles of confidence intervals. When > a, * usually provides shorter intervals than T-test. Hedged-CI provides much larger ones. With increasing n, the performance of T-test and of * become essentially identical.
Beta:
Coverage: In the majority of cases, the coverage * is statistically indistinguishable from Coverage of Hedged- CI is usually 1.
16

---

Bernoulli, delta 0.05, averaged over 1000 runs
Hedged
random
0.1
0.5
= 0.9
1.0
n 1010
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.0
0.1
0.2
0.3
0.4
0.5
0.2
0.4
0.6
0.8
1.0
1.0
n = 20
0.5
quantile
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.0
0.3
0.4
0.4
0.6
0.9
11
1.0
n= 50
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
n = 100
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.25
0.30
0.35
0.40
0.45
0.50
0.65
0.70
0.75
0.80
0.85
0.90
lower confidence bound

---

Bernoulli, delta 0.05, averaged over 1000 runs
Hedged
0.1
0.5
0.9
1.0
n = 200
0.5
0.0
0.02
0.04
0.06
0.08
0.10
0.35
0,40
0.45
0.50
0.75
0.80
0.85
0.90
1.0
n = 400
0.5
quantile
0.0
0.04
0.06
0.08
0.10
0.35
0.40
0.45
0.50
0.82
0.84
0.86
0.88
0.90
81
1.0
n = 800
0.5
0.0
0.05
0.06
0.07
0.08
0.09
0.10
0.40
0.42
0.44
0.46
0.48
0.50
0.82
0.84
0.86
0.88
0.90
1.0
n = 1000
0.5
0.0
0.06
0.07
0.08
0.09
0.10
0.42
0.44
0.46
0.48
0.50
0.84
0.86
0.88
0.90
lower confidence bound

---

Beta, 10, delta 0.05, averaged over 1000 runs
b = 0.1
b = 0.5
b 2
b = 5
1.0
1.0
1.0
1.0
a = 0.1
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.2
0.4
0.00
0.05
0.10
0.15
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.6
0.8
0.0
0.2
0.4
0.00
0.05
0.15
0.20
0.000
0.025
0.050
0.075
0.100
19
1.0
1.0
a a 2
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.6
0.8
1.0
0.4
0.6
0.8
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.7
0.8
0.9
1.0
0.6
0.7
0.8
0.9
0.4
0.5
0.6
0.7
0.2
0.3
0.4
0.5
lower confidence bound

---

Beta, 50, delta 0.05, averaged over 1000 runs
Hed
b = 0.1
b = 0.5
b 2
b = 5
1.0
1.0
1.0
1.0
a 0.1
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.3
0.4
0.5
0.00
0.05
0.10
0.15
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.6
0.7
0.4
0.5
0.10
0.15
0.20
0.02
0.04
0.08
0.10
20
1.0
1.0
a =
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.80
0.85
0.90
0.95
0.6
0.7
0.8
0.35
0.40
0.45
0.50
0.20
0.25
0.30
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.900
0.925
0.950
0.975
0.80
0.85
0.90
0.60
0.65
0.70
0.40
0.45
0.50
lower confidence bound

---

Beta, 500, delta 0.05, averaged over 1000 runs
Hed
b = 0.1
b = 0.5
b 2
b = 5
1.0
1.0
1.0
1.0
a = 0.1
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.40
0.45
0.50
0.10
0.12
0.14
0.16
0.03
0.04
0.05
0.010
0.015
0.020
1.0
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.76
0.78
0.80
0.82
0.84
0.425
0.450
0.475
0.500
0.16
0.18
0.20
0.07
0.08
0.09
21
1.0
1.0
a =
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.92
0.93
0.94
0.95
0.74
0.76
0.78
0.80
0.44
0.46
0.48
0.50
0.25
0.26
0.27
0.28
0.29
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.965
0.970
0.975
0.980
0.88
0.89
0.90
0.91
0.68
0.70
0.72
0.47
0.48
0.49
0.50
lower confidence bound

---

C.2 Influence of 5
The majority of the experiments are made with 8 0.05; here, we present the subset of the experiments with different values of 8. The results follow the patterss observed with d = 0.05.
22

---

Bernoulli, delta 0.001, averaged over 1000 runs
Hedged
random
0.1
0.5
0.9
1.0
n 10
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.0
0.1
0.2
0.3
0.4
0.5
0.2
0.4
0.6
0.8
1.0
1.0
n = 20
0.5
quantile
0.0
0.00
0.02
0.04
0.06
0.10
0.0
0.3
0.4
0.2
0.4
0.6
0.8
1.0
22
1.0
n ==50
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.1
0.2
0.3
0.4
0.5
0.5
0.6
0.7
0.8
0.9
1.0
n = 100
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
lower confidence bound

---

Bernoulli, delta 0.01, averaged over 1000 runs
Hedged
random
0.1
0.5
0.9
1.0
n 10
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.0
0.1
0.2
0.3
0.4
0.5
0.2
0.4
0.6
0.8
1.0
1.0
n = 20
0.5
quantile
0.0
0.00
0.04
0.06
0.10
0.2
0.3
0.5
0.4
24
1.0
n ==50
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.2
0.3
0.4
0.5
0.5
0.6
0.7
0.8
0.9
1.0
n = 100
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.2
0.3
0.4
0.5
0.65
0.70
0.75
0.80
0.85
0.90
lower confidence bound

---

Beta, 100, delta 0.001, averaged over 1000 runs
Hed
b = 0.1
b = 0.5
b =
2
b = 5
1.0
1.0
1.0
1.0
a = 0.1
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.3
0.4
0.5
0.05
0.10
0.15
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.6
0.3
0.5
0.10
0.15
0.20
0.04
0.06
0.08
0.10
25
1.0
1.0
a =
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.80
0.85
0.90
0.95
0.65
0.70
0.75
0.80
0.35
0.40
0.45
0.50
0.200
0.225
0.250
0.275
0.300
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.90
0.95
0.80
0.85
0.90
0.60
0.65
0.70
0.40
0.45
0.50
lower confidence bound

---

Beta, 100, delta 0.001, averaged over 1000 runs
Hed
b = 0.1
b = 0.5
b =
2
b = 5
1.0
1.0
1.0
1.0
a = 0.1
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.3
0.4
0.5
0.05
0.10
0.15
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.6
0.3
0.5
0.10
0.15
0.20
0.04
0.06
0.08
0.10
26
1.0
1.0
a = 2
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.80
0.85
0.90
0.95
0.65
0.70
0.75
0.80
0.35
0.40
0.45
0.50
0.200
0.225
0.250
0.275
0.300
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.90
0.95
0.80
0.85
0.90
0.60
0.65
0.70
0.40
0.45
0.50
lower confidence bound

---

C.3 Selection of c
As discussed in Appendix D.3 we estimate the expectation E[ m] using the empirical mean with an additive cmn/((t - I) term, where t is the current round, is the number of rounds and c a free parameter. We provide experiments suggesting that the algorithm the choice, especially increases, and we choose e 1 as natural choice to not overfit on our benchmark distributions.
so sensitive about
In the following experiments, we used Algorithm 4 with the details Appendix D sweeping over exponentially spaced grid of values of c.
27

---

Bernoulli, delta 0.05, averaged over 1000 runs
0.1
= 0.5
0.9
1.0
n 1010
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.0
0.1
0.2
0.3
0.4
0.5
0.4
0.6
0.8
1.0
1.0
n = 50
0.5
quantile
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.5
0.6
0.8
0.9
23
1.0
n = 250
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.35
0.40
0.45
0.50
0.80
0.82
0.84
0.86
0.88
0.90
1.0
n = 1000
0.5
0.0
0.05
0.06
0.07
0.08
0.09
0.10
0.42
0.44
0.46
0.48
0.50
0.85
0.86
0.87
0.88
0.89
0.90
lower confidence bound

---

Beta, 10, delta 0.05, averaged over 1000 runs
b 0.1
b = 0.5
b 2
b =
5
1.0
1.0
1.0
1.0
a 0.1
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.2
0.4
0.00
0.05
0.10
0.15
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.00
0.05
0.15
0.20
0.000
0.025
0.050
0.075
0.100
23
1.0
1.0
a a 2
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.6
0.8
1.0
0.4
0.6
0.8
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.7
0.8
0.9
1.0
0.6
0.8
0.4
0.6
0.2
0.3
0.4
0.5
lower confidence bound

---

Beta, 50, delta 0.05, averaged over 1000 runs
b 0.1
b = 0.5
b 2
b =
5
1.0
1.0
1.0
1.0
a 0.1
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.3
0.4
0.5
0.00
0.05
0.10
0.15
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.6
0.7
0.8
0.3
0.5
0.10
0.15
0.20
0.02
0.04
0.06
0.08
0.10
30
1.0
1.0
a a 2
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.80
0.85
0.90
0.95
0.6
0.7
0.8
0.30
0.35
0.40
0.45
0.50
0.15
0.20
0.25
0.30
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.900
0.925
0.950
0.975
0.80
0.85
0.90
0.55
0.60
0.65
0.70
0.35
0.40
0.45
0.50
lower confidence bound

---

C.4
Last round bet
Here we provide experiments quantifying the effect of (an additional) last round betting described in Appendix
D.2
STaR-Bets is Algorithm 4 with detail from D
Bets STaR-Bett -ett without the *-component.
(STaR) bets w/o last bet are the first two algorithms without the last round bet (described in Appendix D.2)
Hedged-CI is the confidence interval of 23
We can see that Hedged-CI CI performs similarly to Bets without last bet, and STaR bets without the last bet is significantly stronger. Adding last bet help both algorithms, but the effect is less significant on STaR, since by design, tries to end up with or 2 money. Sometimes the performance of Hedged-CI and Bets without last bet (and also of the pair STaR with/without last bet) so similar, that the curves are indistinguishable.
31

---

Bernoulli, delta 0.05, averaged over 1000 runs
w/o
0.1
p= 0.5
= 0.9
1.0
n 1010
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.0
0.1
0.2
0.3
0.4
0.5
0.2
0.4
0.6
0.8
1.0
1.0
n = 20
0.5
quantile
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.0
0.3
0.4
0.4
0.6
0.9
33
1.0
n ==
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
n = 100
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.25
0.30
0.35
0.40
0.45
0.50
0.65
0.70
0.75
0.80
0.85
0.90
lower confidence bound

---

Beta, 100, delta 0.05, averaged over 1000 runs
w/o
b = 0.1
b = 0.5
2
b = 5
1.0
1.0
1.0
1.0
a = 0.1
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.3
0.4
0.5
0.05
0.10
0.15
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
1.0
a = 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.65
0.70
0.75
0.80
0.85
0.35
0.40
0.45
0.50
0.100
0.125
0.150
0.175 0.200
0.04
0.06
0.08
33
1.0
1.0
1.0
1.0
a a
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.85
0.90
0.95
0.65
0.70
0.75
0.80
0.40
0.45
0.50
0.200
0.225
0.250
0.275
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.94
0.96
0.98
0.84
0.86
0.88
0.90
0.92
0.60
0.65
0.70
0.400
0.425
0.450
0.475
0.500
lower confidence bound

---

Beta, 1000,
delta 0.05,, averaged over 1000 runs
w/o
b = 0.1
b = 0.5
= 2
b = 5
1.0
1.0
1.0
1.0
a 0.1
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.425
0.450
0.475
0.500
0.12
0.14
0.16
0.030
0.035
0.040
0.045 0.050
0.0125 0.0150
0.0175 0.0200
1.0
1.0
1.0
1.0
a 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.78
0.80
0.82
0.84
0.44
0.46
0.48
0.50
0.16
0.17
0.18
0.19
0.20
0.075
0.080
0.085
0.090
44
1.0
1.0
1.0
1.0
a a 2
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.93
0.94
0.95
0.76
0.77
0.78
0.79
0.80
0.46
0.48
0.50
0.26
0.27
0.28
0.29
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.970
0.975
0.980
0.89
0.90
0.91
0.69
0.70
0.71
0.47
0.48
0.49
0.50
lower confidence bound

---

C.5 Variance of the confidence interval with data shuffling
While the majority of confidence intervals are independent of the data order, is not the case for the betting based one. Here, we present several experiments where for every setting, the corresponding sample of random variables was obtained and then it was only shuffled for all the 1000 experiments. Note that here the coverage is meaningless, as we do not draw fresh samples.
35

---

Bernoulli, delta 0.05, averaged over 1000 runs
Hedged
random
0.1
0.5
= 0.9
1.0
n 1010
0.5
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.2
0.3
0.4
0.5
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
n = 20
0.5
quantile
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.20
0.25
0.30
0.35
0.40
0.45
0.50
0.55
0.60
0.65
0.70
0.75
0.80
0.85
0.90
39
1.0
n 50
0.5
0.0
0.02
0.04
0.06
0.08
0.10
0.30
0.35
0.40
0.45
0.50
0.6
0.7
0.8
0.9
1.0
n = 100
0.5
0.0
0.05
0.06
0.07
0.08
0.09
0.10
0.350
0.375
0.400
0.425
0.450
0.475
0.500
0.70
0.75
0.80
0.85
0.90
lower confidence bound

---

Beta, 50, delta 0.05, averaged over 1000 runs
Hed
b = 0.1
b = 0.5
b 2
b = 5
1.0
1.0
1.0
1.0
a 0.1
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.35
0.40
0.45
0.50
0.075
0.100
0.125
0.150
0.175
0.00
0.02
0.04
0.000
0.005
0.010
0.015
0.020
1.0
1.0
1.0
1.0
a 0.5
0.5
0.5
0.5
0.5
quantile
0.0
0.0
0.0
0.0
0.6
0.7
0.8
0.40
0.45
0.50
0.125
0.150
0.175
0.200
0.04
0.06
0.08
0.10
31
1.0
1.0
a a 2
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.85
0.90
0.95
0.70
0.75
0.80
0.400
0.425
0.450
0.475
0.500
0.22
0.24
0.26
0.28
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.900
0.925
0.950
0.975
0.84
0.86
0.88
0.90
0.92
0.625
0.650
0.675
0.700
0.725
0.42
0.44
0.46
0.48
0.50
lower confidence bound

---

D Implementation details
There are certain aspects where the algorithm we implemented deviates from the vanilla version in Algorithm 3 but the underlying process is still Test process, so the resulting confidence intervals are valid. Here, we describe these details.
D.1 Clipping
Instead of clipping the estimate of [ - =m)3] to its upper bound max (1-m)(11)) m))), we clip m(1 - m) instead. It would be the maximal value of [ mm)²) if m [[ The testing problem is hard when m z [[ (and easy otherwise), so this way, we help the algorithm on the hard values of m and hurt on the easy ones, yielding better empirical performance.
D.2 Last round randomization
Just as the conservativeness of Clopper-Pearson is fixed by randomization, we attempt similar thing in the betting games After finishing the testing procedure, draw uniform random variable U supported in [0, 1]; if W 3 U/5, we set to 3-- Otherwise, we it O. is easy to see that after this manipulation, W is still a test-variable, since it is still non-negative and its expectation did not increase. The effect of this is usually small for *-Bets, since wealth. The exceptions n, small variance, or instances with E[X] 1, in which cases the bets has to be very small, and so is not easy properly adapt the betting strategy and ensure that we bet aggressively enough needed. See Appendix C.4 for experiments.
end up with wealth W. Then,
is encouraged by design to end up with 1/6
instances with small
D.3 Choice of second moment estimator
Algorithms have hyperparameter a corresponding the lower bound of probability of having short intervals in the proofs. It influences how conservative we should be in estimating E[[ mm We have (empirically) observed that the larger intuition is that our win (or loss) E(X m) can be as low -êm, and so with larger we should be more careful about the choice of We instantiate the 10 log E a nn/(t 1)² term as cmn/(t 1)² with = 1. In Appendix C.33 we provide experiments suggesting that the exact choice of is not that erucial, but proper argument about how should depend on not given.
the more conservative we should be. The
'The resulting random variable is known all-or- all-or-nothing random variable,
77
38

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] pprovided proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we do provide an algorithm and prove some proeprties.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: Well, we wanted to provide a confidence interval for bounded random variables and we did so.
39

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are present, the proofs are ready and will be submited with supplement.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: it will be in suplement.
Guidelines:
The answer NA means that the paper does not include experiments.
40

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: yes, is suplement.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttppp.cc/pbllc/guideeee http://oeeuuiiiiinoooooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
41

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: no training in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: yes, we derive confidence intervals and we are disgusted that you explicitly say that I-sigma error is 96% CI.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: no resource intensive stuff
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
42

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: are ethical people.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: come on, derive confidence intervals.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: no, we would like people ot use our confidence intervals.
Guidelines:
The answer NA means that the paper poses such risks.
43

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: no assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: no
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: no crows
44

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: we really do just confidence intervals.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: nothing discuss.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy hctt:::://aarrrssscc///ffeeeeeee for what should or should not be described.
45


Reviews:
[{"review_id": "B878w2bSE7", "reviewer": "Reviewer_sGJY", "summary": "This paper considers the setting of construction of  $(1-\\delta)$CI of a bounded random variable from $n$ i.i.d. Samples for a given $\\delta$. The main contribution of the paper is to develop a novel technique to improve the performance of existing betting based methods for construction of CI as well as improving the CI based on concentration bound such as Hoeffding and Bernstein. The improved betting algorithm, i.e., STaR performs better than the existing methods for CI construction including the state of the art betting based methods.", "questions": "Questions:\n\n1- How does one show that the optimal width is of order of $O(\\sqrt{\\frac{\\sigma^2 \\log(1/\\delta)}{n}})$?\n\n2 In Equation 1, the confidence interval is defined such that the probability of error on both the left and right sides is $\\delta/2$. Doesn’t this exclude cases where the error is not equally split, but the total error is still $\\delta$?\n\nSuggestions:\n\n1- If I understand it correctly, I think there is a typo in the equation given below line 119.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1- Idea of improving the betting based methods in novel and Intuition of why STaR algorithm works well is explained well through an example in Section 3.\n\n2- Numerical experiments are quite interesting. I really liked the comparison with Clopper-Pearson method in Figure 3. \n\n\nWeakness:\n\n1-  Theorem 3 is only provided for Algorithm 3.  Maybe I am missing something but how does that lead to theoretical support for Algorithm 4?\n\n2- The paper is only written for bounded random variables. This somewhat restricts the scope of the paper. I wonder if this technique can be useful in more general settings.", "was_revised": true, "final_justification": "I thank the authors for their clarification. I think, they have answered my questions appropriately and I am raising the score.", "rebuttal": "We thank the Reviewer for their feedback. In the following we address their comments and questions.\n\n##  Weaknesses\n**Theorem 3 (typo, should be thm 8) only considers alg 3.**\\\nYes, 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.\n\n**The focus is on bounded random variables - what about more general settings?**\\\nGenerally 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\n\nAngelopoulos AN, Bates S, Fannjiang C, Jordan MI, Zrnic T, Prediction-powered inference, Science, 2023\n\nIn future work, we will explore the application of the STaR method to other settings in the testing-by-betting literature.\n\n## Questions\n**How is  $O(\\sqrt{\\frac{\\sigma^2 \\log(1/\\delta)}{n}})$ the right order?**\\\nIntuitively, 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]$).\n\n**Combining lower and upper confidence bound at different confidence levels**\\\nYes, 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.\n\n**Typo after line 119**\\\nYes, thank you, there should have been a minus sign in the second bracket."}, {"review_id": "8zmNZDjuAR", "reviewer": "Reviewer_QY1z", "summary": "The paper considers the problem of constructing confidence intervals for the mean of a bounded random variable, given access to a fixed number of samples, and proposes new methods for constructing confidence intervals using betting algorithms. Previous betting-based confidence intervals are either designed for anytime-validity, and as a result are sub-optimal for a fixed sample size, or lack non-asymptotic bounds on their width. The main idea behind the proposed star-betting method, is to design betting algorithms that always finish with either 0 wealth or just enough wealth to reject a candidate value for the mean, as opposed to betting algorithms that simply try to achieve maximal wealth. This property is shown to yield confidence intervals with exact coverage. In addition, the testing by betting method of Waudby-Smith and Ramdas is modified such that it produces confidence intervals whose widths satisfy an optimal non-asymptotic bound.", "questions": "I’m a bit puzzled by what $\\ell^H$ in the proof of Proposition 4 is supposed to be. It’s defined as the argmin of $\\sum_{i=1}^{n}X_i$, w.r.t. $\\lambda$ in some set. Does this mean $\\ell^H$ is any feasible value? $\\ell_{\\star}^{H}$ is defined to be the minimiser of $\\sum_{i=t}^{n}X_i$. Is this also just any feasible value?\n\nIn Theorem 8, is it possible to say how quickly the constant c decays as n increases?\n\nThe following is a list of suggested fixes to typos or weird sentences:\n- Line 27: “optimal asymptotically properties” to “optimal asymptotic properties”\n- Line 36 “testing martingale” to “test martingale”\n- Line 40 “fail short” to “fall short”\n- Line 43 “betting algorithm” to “betting algorithms”\n- Line 51 “Bernestein’s” to “Bernstein’s”\n- Line 85 “a betting algorithm does” to “a betting algorithm makes”\n- Line 131 I think M_0 should be W_0\n- Line 135 Given the definition of a test process, there should be an inequality $\\mathbb{E}[W_n] \\leq \\mathbb{E}[W_0]$ and a non-strict inequality $W_n \\geq 0$.\n- Line 146 “we have the non-negativity” to “$W_i^m$ is non-negative”\n- Line 150 “such approach” to “such an approach”\n- Line 157 “monotonous” to “monotonic”\n- Line 203 “And on the other hand” to “On the other hand”\n- Line 204 “Resulting one bankruptcy” to “resulting in bankruptcy”\n- Line 223 $W_{i=1}$\n- Line 226 “, but briefly, we will motivate it” should this be “, but later, we will motivate it more formally”?\n- Line 267 “the $\\star$ version of just derived Algorithm 3” to “the $\\star$ version of Algorithm 3”\n- Line 276 “with T-test” to “with the T-test”\n- Line 285 “and empirical Bernstein bound” to “and the empirical Bernstein bound”\n- Line 286 “Empirical Bernstein bound” to “The empirical Bernstein bound”\n- Line 289 “Method of Phan et al.” to “The method of Phan et al.”\n- Line 293 “how do the widths” to “how the widths”\n- Line 304 “How much does it helps” to “How much it helps”\n\nIf the definition/meaning of $\\ell^{H}$ was clarified and the typos were corrected, I would be prepared to raise my score.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\nThe paper contains several nice ideas, such as the observation that a fixed-horizon betting algorithm should always finish with wealth of either 0 or $1/\\delta$.\n\nI like some aspects of how the ideas of the paper are presented. For instance, the examples (or scenarios) presented throughout the paper help to understand how an optimal fixed-horizon betting algorithm should behave.\n\nThe paper contains several nice results and proofs. For instance, I find Proposition 7 and its proof to be quite satisfying.\n\n**Weaknesses:**\nThe main weakness is that some parts of the paper were very difficult to read and understand. In addition, there were many typos and strange sentences (see Questions for details).\n\nA minor weakness is that the paper is does not quantify how much star-betting improves the theoretical bound.", "was_revised": true, "final_justification": "My first impressions of the paper were already positive. My main concern was that some parts of the paper were difficult to read and understand, such as the initially mysterious $\\ell^H$ quantity. The authors’ rebuttal has addressed my concerns about clarity, and my impression of the paper remains very positive. Therefore, I strongly feel that this paper should be accepted.", "rebuttal": "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.\nWe will fix all the typos the Reviewers found and in the following we answer their specific questions.\n\n## Questions\n**Confusion about $\\ell^H$**\\\nWe 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):\n$$ \n\\min_{X_1, \\dots X_n \\in [0,1], \\lambda \\in \\mathbb{R}} \\sum_{i=1}^n X_i, \\quad\n\\text{s.t.}\\quad  \\lambda\\sum_{i=1}^n (X_i-m) -n\\lambda^2/8 \\geq \\log\\frac1\\delta\n$$\n\n\n**How quickly does $c$ decay in theorem 8?**\\\nIt 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."}, {"review_id": "V87E95ixBs", "reviewer": "Reviewer_Toih", "summary": "This paper considers the problem of constructing confidence interval for the mean of bounded random variable, given a set of i.i.d. observations from the same distribution. The author uses the betting process to construct the confidence interval, and propose the \"$\\ast$-technique\" to improve on the current betting method. Specifically, the \"$\\ast$-technique\" is to substitute $\\mathrm{log}(1/\\delta)$ and $n$ with $\\mathrm{log}(1/\\delta W)$ and $n-t+1$ during the betting process, leading to a more adaptive process. Experiments were conducted to compare the proposed method with other state-of-the-arts, and shows a promising empirical advantage of the proposed method, STaR-Bets.", "questions": "Writing:\n\n1. The paper is relatively easy to follow, though it would be better if there is a paragraph summarizing the organization of the paper.\n\n2. 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.\n\n3. 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)? Also, why does Figure 2 present two plots with different numbers of methods shown? \n\n\nTheoretical results related:\n\n1. Typo from Definition 1 & Proposition 1: I think the author intended to define the test process as a martingale, so in definition 1, the last $\\le$ should be $=$ instead.\n\n2. Incoherent argument in the proof of Theorem 2: Please double check the proof. For example, the last sentence, $1-\\delta$ should be $\\delta$.\n\n3. 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$?\n\n4. 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$?", "limitations": "An in-depth comparison on the theoretical properties between the proposed method and existing methods is lacking.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n\n1. The idea of the \"$\\ast$-technique\" is interesting and intuitive, since finding a way to make the betting process more adaptive is crucial to improve CI’s informativeness.\n\n2. Empirical performance of the proposed method is promising compared to other state-of-the-art methods.\n\nWeakness:\n\n1. The writing of the paper should be improved to enhance clarity. Specific suggestions and questions are listed in the Questions section below.\n\n2. Given that confidence interval construction for the mean under i.i.d. data is a classical and well-studied topic, it is not clear what substantive new theoretical insights this work contributes beyond existing methods. The paper would benefit from clarifying the practical and theoretical advantages of the proposed approach. Please see more concrete questions and concerns listed in the Questions section below.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their feedback. In the following we address their comments and questions.\n\n## Weaknesses\n**This is a classical and well-studied topic, it is not clear what substantive new theoretical insights this work contributes beyond existing methods.**\\\nWe 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).\n\n## Questions\n\n**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.**\\\nIn 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. \nBefore 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).\n\n\n**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)?**\\\nGood point, we can definitely expand the discussion of the competing methods in the Appendix. \n\n**Why does Figure 2 present two plots with different numbers of methods shown?**\\\nFigure 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.\n\n**Typo in definition 1, should be martingale**\\\nNo, we are happy to include supermartingales (yielding Hoeffding and Bernstein inequalities) as indicated by footnote 2.\n\n**Typo in proof of Theorem 2**\\\nYes, thank you, we will fix.\n\n**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$?**\\\nWe 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):\n$$ \n\\min_{X_1, \\dots X_n \\in [0,1], \\lambda \\in \\mathbb{R}} \\sum_{i=1}^n X_i, \\quad\n\\text{s.t.}\\quad  \\lambda\\sum_{i=1}^n (X_i-m) -n\\lambda^2/8 \\geq \\log\\frac1\\delta\n$$\n\n\n\n**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$?**\\\nThe 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).\n\n## Limitations\n**An in-depth comparison on the theoretical properties between the proposed method and existing methods is lacking.**\\\nAs 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)."}, {"review_id": "tSgvdrpQ10", "reviewer": "Reviewer_B2su", "summary": "This work considers the problem of assigning tight confidence intervals to the mean of a finite-size sample from a given distribution. To that end, a sequential betting-based algorithm is constructed with finite-sample optimality guarantees and performance gains over the existing non-sequential algorithms.", "questions": "1. Since future samples cannot be affected by any action by the observer, there is no inherent advantage in constructing CIs sequentially. The only reason I could think of for working sequentially is data spoofing. Do you have a more ethical reason for doing this?", "limitations": "No. Please my comments and questions above.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The problem of designing tight confidence intervals (CIs) for finite-size samples is important. \n\nThe following issues are of concern:\n* The paper contains multiple English mistakes. In some cases, these errors hinder clear understanding. \n* Bootstrapping algorithms, which are widely used by statisticians when the underlying distribution is unknown, are entirely overlooked.\n* The authors seem to be interested in determining a tight CI at a specific horizon $n$. As no \"active control\" over the samples is possible in this setting (in contrast to, say, reinforcement learning), sequential algorithms do not possess any advantage over non-sequential \"batch\" algorithms. However, the lengthy exposition about betting and lines 171-173 implicitly suggest the opposite. In fact, lines 171-173 seem to suggest that more data can deteriorate performance.\n\nFurther comments:\n* Def. 1: The last restriction means that W is a supermartingale. Please state this. Also, $M_0$ should be $W_0$.\n* Theorem 2: This theorem is not stated clearly. In particular, $S$ is not unique, as various CIs may be constructed to meet a certain confidence level.\n* There: In the \"testing by betting\" part, no relation between $W$ and $X$ is mentioned.\n* Line 145-146: The inline equation seems to be at odds with the fact that $W$ is a supermartingale.\n* Sec. 3: This example ( and \"Scenarios\") should be explained in the context of CI assignment. Also, please make the reference to this example in lines 147-148 clearer.", "was_revised": true, "final_justification": "There is no underlying reason for working sequentially except for data spoofing. The paper is poorly written both in terms of content and in terms of grammar.", "rebuttal": "We thank the Reviewer for their feedback.\nIn the following we answer their specific concerns.\n\n## Weaknesses\n**Bootstrapping algorithms are overlooked**\\\nWe (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.\n\n**The problem setup is never rigorously defined … In particular, are the samples $X_1, ..., X_n$ assumed i.i.d.?**\\\nActually, 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$ ..”\n\n**Sequential algorithms do not possess any advantage over non-sequential \"batch\" algorithms. However  (lines 171-173)  suggest the opposite**\\\nWhile 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.\n\n\n### Further comments\n* A typo; thanks. \n* **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.\n* **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.\n* **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.\n\n\n## Questions\n**What are the model assumptions and exact problem formulation?**\\\nSee 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.\n\n\n**Why don’t you start with the easier batch setting and rather do it sequentially?**\\\nWe believe the Reviewer might have the wrong intuition on this problem. \nIn 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.\nFinally, 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."}, {"review_id": "9YuXZlvvBF", "reviewer": "Reviewer_Epqr", "summary": "This paper proposes a method for constructing fixed-time, non-asymptotic confidence intervals through a testing-by-betting approach similar to the work of [1]. The authors leverage a general framework called Sequential Target-Recalculating to size their bets to ensure that the \"wealth\" of their process aims to reach the desired $1/\\delta$ level by the fixed time of inference $N$. The authors leverage their framework to show that their approach strictly improves classical confidence intervals based on Hoeffding and Bernstein inequalities, and provide empirical results demonstrating the efficacy of their methods. \n\n[1] I. Waudby-Smith and A. Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(1):1–27, 2024.", "questions": "* The Markov inequality stated in Proposition 1 provides error guarantees at a fixed time $N$; the related martingale concentration equality (Ville's inequality [2]) uses the same threshold $1/\\delta$, while providing time uniform guarantees. Is there a reason as to why we only construct confidence intervals at time $n$, rather than at any arbitrary times $t \\leq n$? \n* Is there a particular reason for this approach applying only to bounded means? Sequential testing methods often generalize to other settings, such as when variables have bounds on their MGF [3].\n* The test process provided in Defn. 1 is strikingly similar to the definition of $e$-processes [1] in the any-time valid literature. As I understand this work, the STaR method is a tailored approach for fixed sample testing that essentially \"bets all wealth\" before the final time $n$, ensuring that the conclusion of reject / accept is achieved by time $n$. Does this approach generalize to existing testing-by-betting methods, such as Hedged? \n\n[2] Jean Ville. E ́tude critique de la notion de collectif. Gauthier-Villars Paris, 1939\n[3] https://arxiv.org/abs/1810.08240", "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 $e$-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. \n*  The authors miss the opportunity to state anytime-valid guarantees for their test, which they implicitly use in their main algorithm (Algorithm 4). \n* The authors may be missing existing works that leverage similar principles for generalizing a fixed-time approaches to a similar framework. [4] proposes a generalization of the standard $t$-test to an anytime valid test, and has a similar update (where the denominator of the sequential term at time $t$ is divided by $O(n-t)$).\n\n\n[4] https://arxiv.org/pdf/2501.03982", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n* The approach proposed by the authors provides a flexible framework for improving existing concentration inequalities for use as confidence intervals. The authors demonstrate this by applying their framework to well-known concentration inequalities such as Hoeffding or Bernstein. \n* Empirically, the authors provide extensive baseline comparisons for means of bounded random variables, including specialized confidence intervals for the Bernoulli case. \n\n**Weaknesses**\n* Some sections of this paper may be unclear to the reader: for example, the scenarios in pg. 3 of the paper are not quite clear and only seem somewhat related to the aims of the paper.\n* As opposed to a commonly used baseline (Hedged), the confidence intervals proposed in this work are only valid at a fixed time. It would be more fair for authors to compare fixed-time confidence intervals to similar methods, as opposed to anytime-valid approaches that are necessary wider than fixed-time inference due to protecting type I error at all times, rather than just a single sample size $N$.", "was_revised": true, "final_justification": "Despite the novelty of the approach (tuning a betting scheme to be tight given knowledge of the horizon), this work is ultimately limited by a lack of examples beyond the bounded mean setting, which has been extensively studied in the literature. The ideas of this work are sound and solid (which is why we maintain a score close to acceptance), but this work could benefit from being framed more generally as an approach for tuning anytime valid methods for a fixed horizon.", "rebuttal": "We thank the Reviewer for their feedback.\nWe agree that our writing could be improved, but this is an easy change that we can do in the camera ready version.\nMoreover, 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.\n\nWe answer the specific questions in the following.\n\n\n## Weaknesses\n**Scenarios might be unclear and only seem somewhat related to the aims of the paper**\\\nWe 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.\n\n**Unfair comparison with Hedged CS**\\\nThis 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).\n\n## Questions\n\n**Why not intervals at all times t<n?**\\\nAs 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.\n\n**Why only bounded means? (we assume this is a typo and should have been means of bounded random variables)**\\\nThe 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).\nIt 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).\n\n**Does STaR generalize to hedged?**\\\nAs 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).\n\n\n\n\n\n\n## Limitations\n\n**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.**\\\nAs 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.\nAs 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\n\nAngelopoulos AN, Bates S, Fannjiang C, Jordan MI, Zrnic T, Prediction-powered inference, Science, 2023\n\nIn future work, we will explore the application of the STaR method to other settings in the testing-by-betting literature.\n\n\n\n**Anytime guarantees missing**\\\nAs we wrote above, it is trivial to get the anytime-version. We decided to not include it for the sake of clarity.\n\n**Comparison with [4]**\\\nThank 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."}]

Author rebuttal:

Meta-review: The paper considers the problem of constructing confidence intervals for the mean of a bounded random variable, given access to a fixed number of samples, and proposes new methods for constructing confidence intervals using betting algorithms. Previous betting-based confidence intervals are either designed for anytime-validity, and as a result are sub-optimal for a fixed sample size, or lack non-asymptotic bounds on their width. The main idea behind the proposed star-betting method, is to design betting algorithms that always finish with either 0 wealth or just enough wealth to reject a candidate value for the mean, as opposed to betting algorithms that simply try to achieve maximal wealth.

The reviews were mixed but relying on my own expertise I can confidently recommend acceptance.
Decision: Accept (poster)