Introduction
Consider sequential testing of a composite null class P \mathcal{P} P of probability laws on a measurable space X \mathcal{X} X . In the classical formulation, one specifies a composite alternative Q \mathcal{Q} Q and seeks a test with strong worst-case performance over Q \mathcal{Q} Q . If there is a least-favorable pair ( P ⋆ , Q ⋆ ) ∈ P × Q (P^\star,Q^\star)\in\mathcal{P}\times\mathcal{Q} ( P ⋆ , Q ⋆ ) ∈ P × Q , then the corresponding likelihood ratio provides a minimax test: it is designed against the hardest alternative Q ⋆ Q^\star Q ⋆ and protects against the hardest null P ⋆ P^\star P ⋆ . Robust likelihood-ratio tests of this form go back to Huber’s censored probability-ratio construction for neighborhood models ([8 ] ), while Huber and Strassen later developed a broad minimax theory in terms of least-favorable pairs and capacities ([9 ] ). More recently, Saha and Ramdas [16 ] formulated this principle in terms of e-values for arbitrary composite nulls and alternatives and showed how one can perform one-sided sequential tests for Huber-contamination and total-variation neighborhoods, including sequentially adaptive contamination. The minimax criterion is compelling when performance at the hardest alternative is the primary objective. It can, however, leave substantial power on the table when the realized data-generating distribution is easier than the least-favorable one. A test optimized for Q ⋆ Q^\star Q ⋆ has no reason to exploit the additional separation of a particular Q ∈ Q Q \in\mathcal{Q} Q ∈ Q from the null class. In sequential problems, this loss appears directly as slower exponential growth of the evidence process and hence a larger detection delay. Moreover, in many testing problems there is no naturally separated alternative class for which a nontrivial least-favorable pair exists. A canonical example is testing a composite null against its complement.
This motivates a different objective. Instead of fixing a composite class and optimizing the worst case over it, take the alternative to be simply the complement
Q = P c , \mathcal{Q} = \mathcal{P}^{c}, Q = P c ,
and ask for a single valid sequential test that adapts to whichever S ∈ P c S \in\mathcal{P}^{c} S ∈ P c actually generates the data, given a level α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . We construct an e-process and a “power-one” sequential test that can control the type-1 error at a prespecified level α \alpha α and, for a fixed alternative S ∉ P S \notin\mathcal{P} S ∈ / P , the e-process asymptotically achieves the oracle growth rate,
Γ ( S ) : = inf R ∈ P D K L ( S ∥ R ) , (1) \Gamma(S) := \inf_{R \in\mathcal{P}} D_{\mathrm{KL}}(S \mathbin\Vert R), \tag*{(1)} Γ ( S ) := R ∈ P inf D KL ( S ∥ R ) , (1)
which is known to be optimal for testing P \mathcal{P} P ([11 , 12 ] ). Here D K L D_{\mathrm{KL}} D KL denotes the KL divergence. See § 1.1 for a detailed discussion on the e-process and its growth rate.
We develop this idea for a canonical robust-testing model. For some d ∈ N d \in\mathbb{N} d ∈ N , let X = { 1 , … , d } \mathcal{X} = \{1,\ldots,d\} X = { 1 , … , d } be the observation space and consider a discrete distribution with d d d components with probability mass function
P = ( P 1 , … , P d ) , P = (P_1,\ldots,P_d), P = ( P 1 , … , P d ) ,
with P i > 0 P_i > 0 P i > 0 , for all i = 1 , … , d i = 1,\ldots,d i = 1 , … , d . Take the null hypothesis to be the total-variation neighborhood ([8 ] ) around P P P :
P 0 : = B T V ( P , ϵ 0 ) = { R ∈ Δ d : D T V ( R , P ) ≤ ϵ 0 } , (2) \mathcal{P}_0 := \mathcal{B}_{\mathrm{TV}}(P,\epsilon_0) = \{R \in\Delta_d : D_{\mathrm{TV}}(R,P) \le\epsilon_0\}, \tag*{(2)} P 0 := B TV ( P , ϵ 0 ) = { R ∈ Δ d : D TV ( R , P ) ≤ ϵ 0 } , (2)
where Δ d \Delta_d Δ d is the probability simplex, D T V ( R , P ) D_{\mathrm{TV}}(R,P) D TV ( R , P ) is the total variation distance between R R R and P P P :
D T V ( R , P ) = 1 2 ∑ i = 1 d ∣ R i − P i ∣ . D_{\mathrm{TV}}(R,P) = \frac{1}{2}\sum_{i=1}^{d} |R_i-P_i|. D TV ( R , P ) = 2 1 i = 1 ∑ d ∣ R i − P i ∣.
With a slight abuse of notation, we will denote the probability distributions by their d d d -dimensional probability mass functions. The radius ϵ 0 \epsilon_0 ϵ 0 has a direct interpretation: under any distribution in the null, the probability of every event differs from its nominal probability by at most ϵ 0 \epsilon_0 ϵ 0 . It therefore specifies the discrepancies against which the test must protect, even when evidence is monitored continuously.
But in contrast to Huber [8 ] ; Saha and Ramdas [16 ] , our alternative is not another prespecified ball; it is the entire complement Δ d ∖ P 0 \Delta_d \setminus\mathcal{P}_0 Δ d ∖ P 0 . Our goal here is to approach the instance-optimal information rate defined in (1) , instead of the minimax information rate, inf P ∈ P , S ∈ Q D K L ( S ∥ P ) \inf_{P \in\mathcal{P},S \in\mathcal{Q}} D_{\mathrm{KL}}(S\mathbin\Vert P) inf P ∈ P , S ∈ Q D KL ( S ∥ P ) as in Saha and Ramdas [16 ] .
We also construct e-processes for both Wald and Farrell optimality for testing P 0 \mathcal{P}_0 P 0 against its entire complement P 0 c = Δ d ∖ P 0 \mathcal{P}_0^c = \Delta_d \setminus\mathcal{P}_0 P 0 c = Δ d ∖ P 0 . Specifically, we seek a single e-process whose threshold-crossing times define level-α \alpha α tests with power one under every alternative, and whose expected stopping times are optimal in two complementary regimes. In the Wald regime, the alternative S ∉ P 0 S \notin\mathcal{P}_0 S ∈ / P 0 is fixed and α ↓ 0 \alpha\downarrow0 α ↓ 0 ; for every fixed full-support S S S , we aim to attain
E S [ τ α ] ∼ log ( 1 / α ) Γ ( S ) . \mathbb{E}_S[\tau_\alpha] \sim\frac{\log(1/\alpha)}{\Gamma(S)}. E S [ τ α ] ∼ Γ ( S ) log ( 1/ α ) .
In the Farrell regime, α ∈ ( 0 , 1 / 2 ) \alpha\in(0,1/2) α ∈ ( 0 , 1/2 ) is fixed and the alternative approaches the null boundary, so that Γ ( S ) ↓ 0 \Gamma(S) \downarrow0 Γ ( S ) ↓ 0 ; with P \mathcal{P} P , ϵ 0 \epsilon_0 ϵ 0 , d d d fixed, we aim for
E S [ τ α ] = O ( log log ( 1 / Γ ( S ) ) Γ ( S ) ) . \mathbb{E}_S[\tau_\alpha] = O\left(\frac{\log\log(1/\Gamma(S))}{\Gamma(S)}\right). E S [ τ α ] = O ( Γ ( S ) log log ( 1/Γ ( S )) ) .
The first guarantee attains the exact information-theoretic leading constant, while the second matches the Farrell lower bound in order in its sequence-wise sense. We obtain both guarantees by averaging an adaptive clipped-Kelly e-process with a complementary e-process designed for alternatives near the null boundary.
The remainder of this introduction reviews the required background, discusses related work, and states these contributions precisely.
Background on e-values, test supermartingales, one-sided tests, growth rate and consistency
An e-variable is a nonnegative random variable whose expectation is bounded above by one under every distribution in the null class. Specifically, B B B is an e-variable for P \mathcal{P} P if
E P [ B ] ≤ 1 for all P ∈ P . \mathbb{E}_{P}[B] \le1 \qquad\text{for all } P \in\mathcal{P}. E P [ B ] ≤ 1 for all P ∈ P .
The observed realization of an e-variable is called an e-value.
Let M = { M n } n ≥ 0 M = \{M_n\}_{n\ge0} M = { M n } n ≥ 0 be an integrable process adapted to a filtration F = { F n } n ≥ 0 \mathcal{F} = \{\mathcal{F}_n\}_{n\ge0} F = { F n } n ≥ 0 . We call M M M a martingale for P P P if, for every n ≥ 1 n \ge1 n ≥ 1 ,
E P [ M n ∣ F n − 1 ] = M n − 1 , ∀ P ∈ P . (3) \mathbb{E}_{P}[M_n \mid\mathcal{F}_{n-1}] = M_{n-1}, \qquad\forall P \in\mathcal{P}. \tag*{(3)} E P [ M n ∣ F n − 1 ] = M n − 1 , ∀ P ∈ P . (3)
Similarly, M M M is a supermartingale for P P P , if, for every n ≥ 1 n \ge1 n ≥ 1 ,
E P [ M n ∣ F n − 1 ] ≤ M n − 1 , ∀ P ∈ P . (4) \mathbb{E}_{P}[M_n \mid\mathcal{F}_{n-1}] \le M_{n-1}, \qquad\forall P \in\mathcal{P}. \tag*{(4)} E P [ M n ∣ F n − 1 ] ≤ M n − 1 , ∀ P ∈ P . (4)
A test (super)martingale is a process that satisfies the corresponding condition under every distribution in P \mathcal{P} P , is nonnegative, and starts at M 0 = 1 M_0 = 1 M 0 = 1 . A stopping time τ \tau τ is a nonnegative integer-valued, possibly infinite random variable satisfying { τ ≤ n } ∈ F n \{\tau\le n\} \in\mathcal{F}_n { τ ≤ n } ∈ F n for every n ∈ N n \in\mathbb{N} n ∈ N . We write T \mathcal{T} T for the collection of all such stopping times, including those that may never stop.
Ville’s inequality (Ville, [18 ] ) guarantees that a test (super)martingale satisfies
sup P ∈ P P ( ∃ n ∈ N : M n ≥ 1 / α ) ≤ α . (5) \sup_{P \in\mathcal{P}} P(\exists n \in\mathbb{N}: M_n \ge1/\alpha) \le\alpha. \tag*{(5)} P ∈ P sup P ( ∃ n ∈ N : M n ≥ 1/ α ) ≤ α . (5)
A short proof appears in Howard et al. [6 ] . Equivalently, P ( M τ ≥ 1 / α ) ≤ α P(M_\tau\ge1/\alpha) \le\alpha P ( M τ ≥ 1/ α ) ≤ α for every τ ∈ T \tau\in\mathcal{T} τ ∈ T and every P ∈ P P \in\mathcal{P} P ∈ P ; see Howard et al. [7 ] . Consequently, stopping and rejecting at
τ α = inf { n ≥ 1 : M n ≥ 1 / α } (6) \tau_\alpha= \inf\{n \ge1 : M_n \ge1/\alpha\} \tag*{(6)} τ α = inf { n ≥ 1 : M n ≥ 1/ α } (6)
defines a level-α \alpha α sequential test. Under the null, the probability of ever stopping with a false rejection is at most α \alpha α ; equivalently, τ α = ∞ \tau_\alpha= \infty τ α = ∞ with probability at least 1 − α 1-\alpha 1 − α .
This formulation differs from Wald’s classical sequential testing framework [19 ] , in which the procedure may terminate by either accepting or rejecting the null, with the stopping rule calibrated to specified Type-I and Type-II error probabilities. Our setting instead follows Robbins’ theory of “power-one” or one-sided tests [4 , 15 ] : only a target Type-I error level is specified, and sampling stops exclusively to reject the null. Such a test is called consistent under an alternative Q Q Q if it has power one under Q Q Q .
A test (super)martingale is called consistent, or power one, for an alternative Q Q Q if
M n ⟶ ∞ Q -almost surely . M_n \longrightarrow\infty\quad Q\text{-almost surely}. M n ⟶ ∞ Q -almost surely .
Under each alternative, the process then accumulates unbounded evidence against the null and eventually crosses every finite rejection threshold. In i.i.d. settings, evidence can accumulate exponentially, as emphasized by Kelly [10 ] . This motivates measuring performance through the worst-case logarithmic growth rate
lim inf n → ∞ log M n n \liminf_{n\to\infty}\frac{\log M_n}{n} n → ∞ lim inf n log M n
[17 , 5 , 21 ] . A positive growth rate implies consistency. A test (super)martingale attaining the largest possible growth rate is called log-optimal. This optimality criterion has been studied and advocated by Breiman [2 ] , Cover [3 ] , Shafer [17 ] , and Grünwald et al. [5 ] , among others.
Agrawal et al. [1 ] provides upper and lower bounds for power-one sequential tests in two different asymptotic settings: one is the “Wald setting”, where the type-1 error level α \alpha α approaches zero for a fixed alternative S S S . The second lower bound applies to the “Farrell setting”, where α \alpha α is fixed and Γ ( S ) \Gamma(S) Γ ( S ) approaches 0 along a sequence of alternatives.
Related work
Robust/minimax hypothesis testing. Robust likelihood-ratio testing begins with Huber’s censored probability-ratio test [8 ] , which clips individual likelihood-ratio factors to prevent a small number of contaminated observations from dominating the evidence. Huber and Strassen [9 ] developed a general minimax theory of hypothesis testing under capacities and least-favorable distributions. These works establish the classical principle that, when an appropriate least-favorable pair exists, testing can be reduced to a likelihood-ratio test between that pair.
E-values and e-processes. The second thread of literature that is relevant involves recent fundamental advances in composite hypothesis testing. For example, Grünwald et al. [5 ] introduce growth-rate optimal (GRO) e-variables for testing problems with composite null and alternative. The universal inference method [20 ] used an e -value to propose a level-α \alpha α test for any composite null without requiring any regularity conditions, but requiring reference measures. Reverse information projections and numeraire e-variables characterize pointwise log-optimal evidence under composite nulls [11 , 12 ] . See Ramdas et al. [14 ] for a detailed review.
Our contribution is to turn this static pointwise characterization into an adaptive sequential procedure with explicit stopping-time and computational guarantees in the finite-alphabet robust model. The closest modern precursor is Saha and Ramdas [16 ] . They prove that least-favorable pairs yield log-optimal e-values for arbitrary composite nulls and alternatives, construct Huber-robust and TV-robust versions of such tests, and obtain sequential validity even when the contamination mechanism varies adaptively with the past, extending Huber and Strassen [9 ] . In particular, their theory already gives the least-favorable clipped likelihood ratio for two separated TV neighborhoods. Our question is orthogonal: rather than optimizing the worst case over a prespecified alternative class, we take the alternative to be P c \mathcal{P}^{c} P c and ask whether one valid procedure can asymptotically attain the oracle rate (1) at every realized alternative.
Ram and Ramdas [13 ] show the existence of relatively growth-rate optimal e-processes and thus power-one tests under rather general conditions, including the TV ball. However, their work is abstract and their constructions are far from practical, and they do not have stopping time guarantees or regret bounds. Our work extends theirs by adding the specific contributions (i), (ii), (iii), and (iv) mentioned in the next subsection.
Contributions
(i) Finite-sample adaptive regret. For testing the null P \mathcal{P} P in (2) against an unknown full-support alternative S ∈ P c S \in\mathcal{P}^{c} S ∈ P c , we construct an e-process { M n C K } n \{M_{n}^{\mathrm{CK}}\}_{n} { M n CK } n and show the finite-sample bound on the regret
0 ≤ n Γ ( S ) − E S log M n C K ≤ log ( n + d − 1 d − 1 ) . (7) 0 \le n\Gamma(S) - \mathbb{E}_{S}\log M_{n}^{\mathrm{CK}} \le\log\left(\frac{n+d-1}{d-1}\right). \tag*{(7)} 0 ≤ n Γ ( S ) − E S log M n CK ≤ log ( d − 1 n + d − 1 ) . (7)
Consequently, the expected regret is O ( d log n ) O(d\log n) O ( d log n ) and the normalized expected and almost-sure log wealth converge to Γ ( S ) \Gamma(S) Γ ( S ) .
(ii) Wald-optimal expected stopping time. For the level-α \alpha α test using the that e-process, τ α C K : = inf { n : M n C K ≥ α − 1 } \tau_{\alpha}^{\mathrm{CK}} := \inf\{n : M_{n}^{\mathrm{CK}} \ge\alpha^{-1}\} τ α CK := inf { n : M n CK ≥ α − 1 } , we prove that
E S τ α C K = log ( 1 / α ) Γ ( S ) ( 1 + o ( 1 ) ) , α ↓ 0. \mathbb{E}_{S}\tau_{\alpha}^{\mathrm{CK}} = \frac{\log(1/\alpha)}{\Gamma(S)}(1+o(1)), \qquad\alpha\downarrow0. E S τ α CK = Γ ( S ) log ( 1/ α ) ( 1 + o ( 1 )) , α ↓ 0.
It is well known that no level-α \alpha α sequential test can improve the first-order constant 1 / Γ ( S ) 1/\Gamma(S) 1/Γ ( S ) at the same instance [1 ] .
(iii) Farrell-optimal expected stopping time. We construct another e-process { M n F } n \{M_{n}^{\mathrm{F}}\}_{n} { M n F } n for adaptation near the null boundary for which the level α \alpha α stopping time, τ α F \tau_{\alpha}^{\mathrm{F}} τ α F , is Farrell-optimal:
E S τ α F = O P , ϵ 0 , d ( d + log ( 1 / α ) + log log ( e e / Γ ( S ) ) Γ ( S ) ) , 0 < Γ ( S ) ≤ 1 , \mathbb{E}_{S}\tau_{\alpha}^{\mathrm{F}} = O_{P,\epsilon_{0},d}\left(\frac{d+\log(1/\alpha)+\log\log(e^{e}/\Gamma(S))}{\Gamma(S)}\right), \qquad0 < \Gamma(S) \le1, E S τ α F = O P , ϵ 0 , d ( Γ ( S ) d + log ( 1/ α ) + log log ( e e /Γ ( S )) ) , 0 < Γ ( S ) ≤ 1 ,
that is, for fixed α ∈ ( 0 , 1 / 2 ) \alpha\in(0,1/2) α ∈ ( 0 , 1/2 ) , we have E S τ α F = O ( Γ ( S ) − 1 log log ( 1 / Γ ( S ) ) ) \mathbb{E}_{S}\tau_{\alpha}^{\mathrm{F}} = O(\Gamma(S)^{-1}\log\log(1/\Gamma(S))) E S τ α F = O ( Γ ( S ) − 1 log log ( 1/Γ ( S ))) , as Γ ( S ) ↓ 0 \Gamma(S) \downarrow0 Γ ( S ) ↓ 0 . At fixed α ∈ ( 0 , 1 / 2 ) \alpha\in(0,1/2) α ∈ ( 0 , 1/2 ) , it matches the optimal Farrell order in the sequence-wise sense of the lower bound. Averaging this process with clipped Kelly retains the exact Wald constant and increases the expected-regret bound by at most log 2 \log2 log 2 .
(iv) Exact logarithmic-time implementation. A naive fresh oracle computation sorts all d d d ratios and costs O ( d log d ) O(d\log d) O ( d log d ) per round. We show that, after a rescaling, only the coordinate corresponding to the newly observed symbol changes. Maintaining these quantities in an augmented balanced binary search tree yields the same fresh every-round clipped-Kelly oracle in O ( log d ) O(\log d) O ( log d ) worst-case update time, after O ( d log d ) O(d\log d) O ( d log d ) initialization, using O ( d ) O(d) O ( d ) memory.
Our adaptive process instead learns the oracle corresponding to the realized alternative, enjoys logarithmic finite-sample regret, achieves the information-theoretically optimal first-order stopping time at that instance, and can be implemented efficiently.
Organization. Section 2 constructs an adaptive e-process showing that its expected stopping time achieves Wald optimality as the type-I error converges to zero. Section 3 studies adaptation near the null boundary and Farrell-type optimality, and combines the two regimes. Section 4 gives efficient dynamic implementation of both e-processes. Section 5 shows a simulation experiment, and Section 6 discusses the scope of the results. Proofs of the theoretical results appear in Section A. An alternative oracle-mixture construction is provided in Section B.
Adaptive clipped-Kelly e-process
From this point onward we specialize to the finite-alphabet TV-robust model in (2) . We assume throughout that d ≥ 2 d \ge2 d ≥ 2 , P i > 0 P_i > 0 P i > 0 for every i i i , and
0 < ϵ 0 < 1 − min i P i , 0 < \epsilon_0 < 1 - \min_i P_i, 0 < ϵ 0 < 1 − i min P i ,
so that the TV ball is nontrivial and its complement is nonempty. The case ϵ 0 = 0 \epsilon_0 = 0 ϵ 0 = 0 reduces to the ordinary likelihood-ratio/Kelly construction and is simpler than the robust case considered here.
The pointwise Kelly oracle
We write
Δ d ∘ : = { U ∈ Δ d : U i > 0 for all i } \Delta_d^\circ:= \{U \in\Delta_d : U_i > 0 \text{ for all } i\} Δ d ∘ := { U ∈ Δ d : U i > 0 for all i }
for the interior of the simplex. All oracle parameters used by the adaptive procedures lie in Δ d ∘ \Delta_d^\circ Δ d ∘ because the predictors use strictly positive pseudocounts.
Define the one-step e-variable class
E 0 : = { E ≥ 0 : sup R ∈ P 0 E R E ≤ 1 } . (8) \mathcal{E}_0 := \left\{E \ge0 : \sup_{R \in\mathcal{P}_0} \mathbb{E}_R E \le1\right\}. \tag*{(8)} E 0 := { E ≥ 0 : R ∈ P 0 sup E R E ≤ 1 } . (8)
Note that for U ∈ Δ d U \in\Delta_d U ∈ Δ d , Γ ( U ) \Gamma(U) Γ ( U ) defined in (1) can be written as
Γ ( U ) = sup E ∈ E 0 ∑ i = 1 d U i log E i . (9) \Gamma(U) = \sup_{E \in\mathcal{E}_0} \sum_{i=1}^{d} U_i \log E_i. \tag*{(9)} Γ ( U ) = E ∈ E 0 sup i = 1 ∑ d U i log E i . (9)
To construct a sequential test that adapts to an unknown alternative, we first solve the idealized problem in which the alternative distribution U U U is known. An oracle with this knowledge would choose a betting factor that is valid for every distribution in the null class P 0 \mathcal{P}_0 P 0 and maximizes the expected logarithmic return under U U U :
E U ∈ arg max E ∈ E 0 ∑ i = 1 d U i log E i . E_U \in\arg\max_{E \in\mathcal{E}_0} \sum_{i=1}^{d} U_i \log E_i. E U ∈ arg E ∈ E 0 max i = 1 ∑ d U i log E i .
Under i.i.d. sampling from U U U , repeatedly using this factor yields expected log wealth n Γ ( U ) n\Gamma(U) n Γ ( U ) after n n n observations. Thus the pointwise oracle identifies both the information rate available at a particular alternative and the betting factor that an adaptive procedure should aim to learn.
The main result of this section gives an explicit characterization of this oracle for a TV-ball null. We show that the optimal factor is obtained by clipping the nominal likelihood ratio U i / P i U_i/P_i U i / P i between two thresholds determined by the robustness radius. Equivalently, it is the likelihood ratio U i / R U ( i ) U_i/R_U(i) U i / R U ( i ) , where R U R_U R U is the reverse-KL projection of U U U onto P 0 \mathcal{P}_0 P 0 . This characterization provides the link between the static optimization problem and the adaptive construction below: we can apply the oracle map to an estimate of U U U based on past observations, while retaining null validity for every such estimate.
We work with strictly positive oracle inputs U ∈ Δ d ∘ U \in\Delta_d^\circ U ∈ Δ d ∘ , as is automatically the case for the smoothed empirical predictors used later. If U ∈ P 0 U \in\mathcal{P}_0 U ∈ P 0 , no null-valid factor can have positive expected log return under U U U , and the constant factor one is optimal. Accordingly, for U ∈ Δ d ∘ ∩ P 0 U \in\Delta_d^\circ\cap\mathcal{P}_0 U ∈ Δ d ∘ ∩ P 0 , set E U ≡ 1 E_U \equiv1 E U ≡ 1 , R U = U R_U = U R U = U , and Γ ( U ) = 0 \Gamma(U) = 0 Γ ( U ) = 0 . For the remainder of this section, fix U ∈ Δ d ∘ ∖ P 0 U \in\Delta_d^\circ\setminus\mathcal{P}_0 U ∈ Δ d ∘ ∖ P 0 . Strict positivity also ensures that the lower clipping threshold introduced below is strictly positive.
Define a ( U ) ∈ ( 0 , 1 ) a(U) \in(0,1) a ( U ) ∈ ( 0 , 1 ) and b ( U ) ∈ ( 1 , ∞ ) b(U) \in(1,\infty) b ( U ) ∈ ( 1 , ∞ ) through
∑ i = 1 d ( a ( U ) P i − U i ) + = a ( U ) ϵ 0 , (10) \sum_{i=1}^{d} \bigl(a(U)P_i-U_i\bigr)_+ = a(U)\epsilon_0, \tag*{(10)} i = 1 ∑ d ( a ( U ) P i − U i ) + = a ( U ) ϵ 0 , (10)
∑ i = 1 d ( U i − b ( U ) P i ) + = b ( U ) ϵ 0 . (11) \sum_{i=1}^{d} \bigl(U_i-b(U)P_i\bigr)_+ = b(U)\epsilon_0. \tag*{(11)} i = 1 ∑ d ( U i − b ( U ) P i ) + = b ( U ) ϵ 0 . (11)
Set
E U ( i ) = clip ( U i P i , a ( U ) , b ( U ) ) , clip ( z , a , b ) = min { b , max { a , z } } , (12) E_U(i)=\operatorname{clip}\left(\frac{U_i}{P_i},a(U),b(U)\right),\qquad\operatorname{clip}(z,a,b)=\min\{b,\max\{a,z\}\}, \tag*{(12)} E U ( i ) = clip ( P i U i , a ( U ) , b ( U ) ) , clip ( z , a , b ) = min { b , max { a , z }} , (12)
and
R U ( i ) = U i E U ( i ) . (13) R_U(i)=\frac{U_i}{E_U(i)}. \tag*{(13)} R U ( i ) = E U ( i ) U i . (13)
Lemma 2.1 (Existence and uniqueness of the oracle thresholds). If U ∈ Δ d ∘ ∖ P 0 U \in\Delta_d^\circ\setminus\mathcal{P}_0 U ∈ Δ d ∘ ∖ P 0 , then (10)–(11) have unique solutions a ( U ) ∈ ( 0 , 1 ) a(U) \in(0,1) a ( U ) ∈ ( 0 , 1 ) and b ( U ) ∈ ( 1 , ∞ ) b(U) \in(1,\infty) b ( U ) ∈ ( 1 , ∞ ) .
Theorem 2.2 (Reverse projection and pointwise Kelly oracle). Let U ∈ Δ d ∘ U \in\Delta_d^\circ U ∈ Δ d ∘ . Then:
(a) R U ∈ P 0 R_U \in\mathcal{P}_0 R U ∈ P 0 and E U ∈ E 0 E_U \in\mathcal{E}_0 E U ∈ E 0 ;
(b) R U R_U R U is the unique reverse information projection (RIPr) and R U = arg min R ∈ P 0 D K L ( U ∥ R ) R_U = \arg\min_{R\in\mathcal{P}_0}D_{\mathrm{KL}}(U\mathbin\Vert R) R U = arg min R ∈ P 0 D KL ( U ∥ R ) ;
(c) Γ ( U ) = D K L ( U ∥ R U ) = inf R ∈ P 0 D K L ( U ∥ R ) \Gamma(U)=D_{\mathrm{KL}}(U\mathbin\Vert R_U)=\inf_{R\in\mathcal{P}_0}D_{\mathrm{KL}}(U\mathbin\Vert R) Γ ( U ) = D KL ( U ∥ R U ) = inf R ∈ P 0 D KL ( U ∥ R ) , and E U = U / R U E_U=U/R_U E U = U / R U is the unique maximizer in (9) .
These facts specialize the reverse-projection characterization of log-optimal e-variables Lardy et al. [11 ] ; Larsson et al. [12 ] . In particular, it turns out that in this case we can avoid the explicit use of their more general bipolar machinery, because we are able to find an e-variable which is the likelihood ratio of U U U to some element of P 0 \mathcal{P}_0 P 0 , immediately making it the log-optimal e-variable by results in the latter paper.
Corollary 2.3. For positive weights c 1 , … , c d c_1,\ldots,c_d c 1 , … , c d and U i = c i / ∑ j c j U_i=c_i/\sum_j c_j U i = c i / ∑ j c j ,
E U = arg max E ∈ E 0 ∑ i = 1 d c i log E i . E_U=\underset{E\in\mathcal{E}_0}{\arg\max}\sum_{i=1}^{d}c_i\log E_i. E U = E ∈ E 0 arg max i = 1 ∑ d c i log E i .
The pointwise oracle identifies the best expected logarithmic growth attainable when the alternative distribution is known. But the oracle is unavailable because the alternative is unknown. We now construct a single sequential procedure that learns this oracle from the observations. At each round, we estimate the alternative using past data and apply the oracle map to that estimate. Since E U E_U E U is valid for the entire null class for every oracle input U U U , this predictable substitution preserves anytime validity. The remaining task is to quantify the loss in log wealth caused by having to estimate the alternative.
For the expected-regret and stopping-time analysis, we assume that the observations are i.i.d. from a fixed alternative S S S . For S ∈ Δ d S \in\Delta_d S ∈ Δ d and U ∈ Δ d ∘ U \in\Delta_d^{\circ} U ∈ Δ d ∘ , write
h ( S , U ) : = ∑ i = 1 d S i log E U ( i ) . h(S,U) := \sum_{i=1}^{d} S_i \log E_U(i). h ( S , U ) := i = 1 ∑ d S i log E U ( i ) .
This is the expected logarithmic return under S S S of the betting factor designed for U U U . In particular, h ( S , S ) = Γ ( S ) h(S,S) = \Gamma(S) h ( S , S ) = Γ ( S ) when S S S has full support, so the difference
Γ ( S ) − h ( S , U ) \Gamma(S) - h(S,U) Γ ( S ) − h ( S , U )
measures the one-step cost of using U U U in place of the true alternative. The following lemma bounds this cost by D K L ( S ∥ U ) D_{\mathrm{KL}}(S\|U) D KL ( S ∥ U ) . It provides the key link between learning the alternative and accumulating evidence: a predictor with small cumulative log-loss regret also yields a robust e-process with small expected regret relative to the oracle. Below we obtain a stronger pathwise finite-sample bound for a smoothed empirical predictor.
Lemma 2.4 (Oracle mismatch is bounded by KL). Let S ∉ P 0 S \notin\mathcal{P}_0 S ∈ / P 0 have full support and let U ∈ Δ d U \in\Delta_d U ∈ Δ d have strictly positive coordinates. Then
0 ≤ Γ ( S ) − h ( S , U ) ≤ D K L ( S ∥ U ) . (14) 0 \le\Gamma(S) - h(S,U) \le D_{\mathrm{KL}}(S\|U). \tag*{(14)} 0 ≤ Γ ( S ) − h ( S , U ) ≤ D KL ( S ∥ U ) . (14)
Predictable clipped-Kelly process
Fix pseudocounts α i > 0 \alpha_i > 0 α i > 0 and let
α + = ∑ i α i , N i ( t ) = ∑ r = 1 t 1 { X r = i } . \alpha_+ = \sum_i \alpha_i,\qquad N_i(t) = \sum_{r=1}^{t} \mathbf{1}\{X_r=i\}. α + = i ∑ α i , N i ( t ) = r = 1 ∑ t 1 { X r = i } .
The every-round predictor and factor are
U ^ t − 1 , i = N i ( t − 1 ) + α i t − 1 + α + , E t = E U ^ t − 1 , (15) \widehat{U}_{t-1,i} = \frac{N_i(t-1)+\alpha_i}{t-1+\alpha_+},\qquad E_t = E_{\widehat{U}_{t-1}}, \tag*{(15)} U t − 1 , i = t − 1 + α + N i ( t − 1 ) + α i , E t = E U t − 1 , (15)
and
M n C K = ∏ t = 1 n E t ( X t ) . M_n^{\mathrm{CK}} = \prod_{t=1}^{n} E_t(X_t). M n CK = t = 1 ∏ n E t ( X t ) .
By Corollary 2.3 , this is exactly a follow-the-regularized-leader or Kelly update over E 0 \mathcal{E}_0 E 0 . The fresh predictor appears to require an O ( d log d ) O(d\log d) O ( d log d ) oracle recomputation after every observation. Section 4 shows that the identical every-round factor can instead be maintained exactly in O ( log d ) O(\log d) O ( log d ) time.
Theorem 2.5. The process ( M n C K ) n (M_n^{\mathrm{CK}})_n ( M n CK ) n is a nonnegative test supermartingale under P \mathcal{P} P .
This validity statement holds for every choice of positive pseudocounts and requires no accuracy guarantee for the predictor. Conditional on the past, the selected factor belongs to E 0 \mathcal{E}_0 E 0 , which is sufficient for the supermartingale property. The quality of the predictor instead determines how quickly evidence accumulates under an alternative. We next quantify this learning cost.
For a particularly clean finite-sample bound, we now take the Laplace pseudocounts
α 1 = ⋯ = α d = 1. (16) \alpha_1 = \cdots= \alpha_d = 1. \tag*{(16)} α 1 = ⋯ = α d = 1. (16)
Other fixed positive pseudocounts lead to the same logarithmic order with constants depending on the pseudocount vector.
Theorem 2.6 (Pathwise regret of adaptive clipped Kelly). Assume (16) . For every observation sequence x 1 , x 2 , … ∈ X x_1,x_2,\ldots\in\mathcal{X} x 1 , x 2 , … ∈ X and every n ≥ 1 n \ge1 n ≥ 1 , let S ˉ n , i = N i ( n ) / n \bar{S}_{n,i}=N_i(n)/n S ˉ n , i = N i ( n ) / n and define the best fixed null-valid wealth in hindsight by
W n ⋆ : = max E ∈ E 0 ∏ t = 1 n E ( x t ) . W_n^\star:= \max_{E\in\mathcal{E}_0}\prod_{t=1}^{n}E(x_t). W n ⋆ := E ∈ E 0 max t = 1 ∏ n E ( x t ) . Then
0 ≤ log W n ⋆ − log M n C K = n Γ ( S ˉ n ) − log M n C K ≤ log ( n + d − 1 d − 1 ) . 0 \le\log W_n^\star-\log M_n^{\mathrm{CK}}=n\Gamma(\bar{S}_n)-\log M_n^{\mathrm{CK}}\le\log\left(\frac{n+d-1}{d-1}\right). 0 ≤ log W n ⋆ − log M n CK = n Γ ( S ˉ n ) − log M n CK ≤ log ( d − 1 n + d − 1 ) .
The benchmark W n ⋆ W_n^\star W n ⋆ is allowed to inspect all n n n observations before choosing a single null-valid factor to use throughout the sequence. The theorem shows that the predictable procedure nearly matches this hindsight choice: for fixed d d d , the difference in log wealth grows only logarithmically with the horizon. The comparison holds for every observation sequence.
The regret penalty depends only on n n n and d d d ; the robustness radius enters through the feasible factors and the benchmark Γ ( S ˉ n ) \Gamma(\bar{S}_n) Γ ( S ˉ n ) . Under i.i.d. sampling from S S S , the fixed oracle E S E_S E S is one of the competitors defining W n ⋆ W_n^\star W n ⋆ . Taking expectations therefore gives the upper bound in the following corollary.
Corollary 2.7 (Expected regret and pointwise instance optimality). Assume (16) and that the observations are i.i.d. from a fixed full-support S ∈ Δ d ∖ P 0 S\in\Delta_d\setminus\mathcal{P}_0 S ∈ Δ d ∖ P 0 . For every n ≥ 1 n\ge1 n ≥ 1 ,
0 ≤ n Γ ( S ) − E S log M n C K ≤ log ( n + d − 1 d − 1 ) . (17) 0\le n\Gamma(S)-\mathbb{E}_S\log M_n^{\mathrm{CK}}\le\log\left(\frac{n+d-1}{d-1}\right). \tag*{(17)} 0 ≤ n Γ ( S ) − E S log M n CK ≤ log ( d − 1 n + d − 1 ) . (17) Consequently, for d ≥ 2 d\ge2 d ≥ 2 ,
n Γ ( S ) − E S log M n C K ≤ ( d − 1 ) log ( e ( n + d − 1 ) d − 1 ) . (18) n\Gamma(S)-\mathbb{E}_S\log M_n^{\mathrm{CK}}\le(d-1)\log\left(\frac{e(n+d-1)}{d-1}\right). \tag*{(18)} n Γ ( S ) − E S log M n CK ≤ ( d − 1 ) log ( d − 1 e ( n + d − 1 ) ) . (18) In particular,
0 ≤ Γ ( S ) − 1 n E S log M n C K ≤ 1 n log ( n + d − 1 d − 1 ) ⟶ 0. (19) 0\le\Gamma(S)-\frac{1}{n}\mathbb{E}_S\log M_n^{\mathrm{CK}}\le\frac{1}{n}\log\left(\frac{n+d-1}{d-1}\right)\longrightarrow0. \tag*{(19)} 0 ≤ Γ ( S ) − n 1 E S log M n CK ≤ n 1 log ( d − 1 n + d − 1 ) ⟶ 0. (19)
Corollary 2.8 (Almost-sure pointwise instance optimality). Under the assumptions of Corollary 2.7,
1 n log M n C K ⟶ Γ ( S ) almost surely under S . (20) \frac{1}{n}\log M_n^{\mathrm{CK}}\longrightarrow\Gamma(S)\qquad\text{almost surely under }S. \tag*{(20)} n 1 log M n CK ⟶ Γ ( S ) almost surely under S . (20)
Together, these corollaries show that the cost of learning the alternative vanishes per observation, both in expectation and almost surely. Since Γ ( S ) > 0 \Gamma(S)>0 Γ ( S ) > 0 for every fixed alternative under consideration, the wealth diverges almost surely and the test eventually rejects at every fixed significance level. Thus the same procedure has power one at every full-support alternative outside the null ball. We next ask how many observations this eventual rejection requires.
Instance-optimal expected stopping time
For an anytime-valid wealth process M M M , define
τ α ( M ) : = inf { n ≥ 1 : M n ≥ α − 1 } . (21) \tau_\alpha(M):=\inf\{n\ge1:M_n\ge\alpha^{-1}\}. \tag*{(21)} τ α ( M ) := inf { n ≥ 1 : M n ≥ α − 1 } . (21)
This gives a level-α \alpha α test by Ville’s inequality. The growth benchmark Γ ( S ) \Gamma(S) Γ ( S ) has a direct operational interpretation: its reciprocal is the optimal first-order expected sample size per unit of log evidence.
Theorem 2.9 (Universal information lower bound). Fix a full-support S ∉ P 0 S \notin\mathcal{P}_0 S ∈ / P 0 , let R S R_S R S be its reverse projection from Theorem 2.2 , and let τ \tau τ be any stopping rule satisfying
sup R ∈ P 0 P R ( τ < ∞ ) ≤ α , P S ( τ < ∞ ) = 1. \sup_{R \in\mathcal{P}_0} \mathbb{P}_R(\tau< \infty) \le\alpha,\qquad\mathbb{P}_S(\tau< \infty) = 1. R ∈ P 0 sup P R ( τ < ∞ ) ≤ α , P S ( τ < ∞ ) = 1. Then
E S τ ≥ log ( 1 / α ) Γ ( S ) . (22) \mathbb{E}_S\tau\ge\frac{\log(1/\alpha)}{\Gamma(S)}. \tag*{(22)} E S τ ≥ Γ ( S ) log ( 1/ α ) . (22)
The above information lower bound is a specialization of Theorem 3.1 of Agrawal et al. [1 ] . We provide a self-contained proof for our special case in the appendix.
Theorem 2.10 (Expected stopping time of adaptive clipped Kelly). Assume the pseudocounts (16) . Fix a full-support S ∉ P 0 S \notin\mathcal{P}_0 S ∈ / P 0 and let
τ α C K : = τ α ( M C K ) . \tau_{\alpha}^{\mathrm{CK}} := \tau_{\alpha}(M^{\mathrm{CK}}). τ α CK := τ α ( M CK ) . Then, as α ↓ 0 \alpha\downarrow0 α ↓ 0 ,
E S τ α C K ∼ log ( 1 / α ) Γ ( S ) . (23) \mathbb{E}_S\tau_{\alpha}^{\mathrm{CK}} \sim\frac{\log(1/\alpha)}{\Gamma(S)}. \tag*{(23)} E S τ α CK ∼ Γ ( S ) log ( 1/ α ) . (23)
Remark 2.11. The convergence n − 1 E S log M n C K → Γ ( S ) n^{-1}\mathbb{E}_S\log M_n^{\mathrm{CK}} \to\Gamma(S) n − 1 E S log M n CK → Γ ( S ) does not by itself imply (23) . The proof of the theorem in the appendix uses the stronger exponential concentration available on a finite alphabet to control the tail of the hitting time and hence establish uniform integrability at the relevant scale.
Farrell optimal e-process: adaptation near the null boundary
The stopping-time result in the previous section fixes an alternative S S S and lets the error level α \alpha α decrease to zero. A different difficulty arises when α \alpha α is fixed and the alternative approaches the null. In this regime, Γ ( S ) \Gamma(S) Γ ( S ) decreases to zero, and the procedure must learn both where the null is violated and the scale of that violation. Optimality in the first limit does not imply optimality in the second. We now construct a complementary process that adapts to this unknown scale. Averaging it with clipped Kelly gives one test with the exact Wald constant and the optimal Farrell order in their respective limits.
Retain the standing assumptions on P P P , d d d , ϵ 0 \epsilon_0 ϵ 0 , which are fixed throughout the small-gap analysis. Put
Δ ( S ) = D T V ( S , P ) − ϵ 0 , Γ ( S ) = inf R ∈ P 0 D K L ( S ∥ R ) , ℓ ( x ) = log log ( e e / x ) ( 0 < x ≤ 1 ) . \Delta(S) = D_{\mathrm{TV}}(S,P) - \epsilon_0,\qquad\Gamma(S) = \inf_{R \in\mathcal{P}_0} D_{\mathrm{KL}}(S\|R),\qquad\ell(x) = \log\log(e^e/x)\quad(0 < x \le1). Δ ( S ) = D TV ( S , P ) − ϵ 0 , Γ ( S ) = R ∈ P 0 inf D KL ( S ∥ R ) , ℓ ( x ) = log log ( e e / x ) ( 0 < x ≤ 1 ) .
Performance is evaluated under i.i.d. observations from S ∉ P 0 S \notin\mathcal{P}_0 S ∈ / P 0 . The small-gap bounds allow zero coordinates in S S S .
The geometry of a small violation
For an event A ⊆ X A \subseteq\mathcal{X} A ⊆ X , every null distribution satisfies
R ( A ) ≤ P ( A ) + ϵ 0 . R(A) \le P(A) + \epsilon_0. R ( A ) ≤ P ( A ) + ϵ 0 .
Moreover, D T V ( S , P ) = max A { S ( A ) − P ( A ) } D_{\mathrm{TV}}(S,P) = \max_A\{S(A)-P(A)\} D TV ( S , P ) = max A { S ( A ) − P ( A )} . Thus an alternative has an event whose null constraint is violated by exactly Δ ( S ) \Delta(S) Δ ( S ) . The following lemma relates this event-level violation to the information number used in our earlier results.
Lemma 3.1 (Uniform information comparison). Define
η 0 = min A ⊆ X : P ( A ) > ϵ 0 { P ( A ) − ϵ 0 } , c 0 = min { ϵ 0 , η 0 } > 0. \eta_0=\min_{A\subseteq\mathcal{X}:P(A)>\epsilon_0}\{P(A)-\epsilon_0\},\qquad c_0=\min\{\epsilon_0,\eta_0\}>0. η 0 = A ⊆ X : P ( A ) > ϵ 0 min { P ( A ) − ϵ 0 } , c 0 = min { ϵ 0 , η 0 } > 0. For every S ∈ Δ d ∖ P 0 S\in\Delta_d\setminus\mathcal{P}_0 S ∈ Δ d ∖ P 0 ,
2 Δ ( S ) 2 ≤ Γ ( S ) ≤ c 0 − 2 Δ ( S ) 2 . (24) 2\Delta(S)^2\leq\Gamma(S)\leq c_0^{-2}\Delta(S)^2. \tag*{(24)} 2Δ ( S ) 2 ≤ Γ ( S ) ≤ c 0 − 2 Δ ( S ) 2 . (24) These constants depend on the fixed null geometry and need not be computed by the algorithm. In particular, the lemma does not assume a positive lower bound on the coordinates of S S S . It does not assert uniform constants as d d d or ϵ 0 \epsilon_0 ϵ 0 vary.
Learn an event, bet for one block, and retain the capital
Let m j = 2 j m_j=2^j m j = 2 j for j ≥ 0 j\geq0 j ≥ 0 , and let S ˉ m \bar{S}_m S ˉ m be the empirical distribution after m m m observations. At time m j m_j m j , select
A ^ j = { i : S ˉ m j , i > P i } , q j = P ( A ^ j ) + ϵ 0 , \widehat{A}_j=\{i:\bar{S}_{m_j,i}>P_i\},\qquad q_j=P(\widehat{A}_j)+\epsilon_0, A j = { i : S ˉ m j , i > P i } , q j = P ( A j ) + ϵ 0 ,
Δ ^ j = ( D T V ( S ˉ m j , P ) − ϵ 0 ) + , λ j = 4 Δ ^ j . (25) \widehat{\Delta}_j=(D_{\mathrm{TV}}(\bar{S}_{m_j},P)-\epsilon_0)_+,\qquad\lambda_j=4\widehat{\Delta}_j. \tag*{(25)} Δ j = ( D TV ( S ˉ m j , P ) − ϵ 0 ) + , λ j = 4 Δ j . (25)
The selected event maximizes the empirical violation of a null constraint. Its betting intensity is proportional to the estimated excess. If the estimated excess is zero, the account does not bet.
Account j j j starts at one, bets only during observations m j + 1 , … , 2 m j m_j+1,\ldots,2m_j m j + 1 , … , 2 m j , and then freezes. Precisely, let ν j ( n ) = ( ( n ∧ 2 m j ) − m j ) + \nu_j(n)=((n\wedge2m_j)-m_j)_+ ν j ( n ) = (( n ∧ 2 m j ) − m j ) + and set
W n ( j ) = { 1 , n ≤ m j , exp { λ j ∑ t = m j + 1 n ∧ 2 m j ( 1 { X t ∈ A ^ j } − q j ) − ν j ( n ) λ j 2 8 } , n > m j . (26) W_n^{(j)}=
\begin{cases}
1, & n\leq m_j,\\
\exp\left\{\lambda_j\sum_{t=m_j+1}^{n\wedge2m_j}\left(\mathbf{1}\{X_t\in\widehat{A}_j\}-q_j\right)-\dfrac{\nu_j(n)\lambda_j^2}{8}\right\}, & n>m_j.
\end{cases} \tag*{(26)} W n ( j ) = ⎩ ⎨ ⎧ 1 , exp { λ j ∑ t = m j + 1 n ∧ 2 m j ( 1 { X t ∈ A j } − q j ) − 8 ν j ( n ) λ j 2 } , n ≤ m j , n > m j . (26)
Allocate initial capital w j = 1 / [ ( j + 1 ) ( j + 2 ) ] w_j=1/[(j+1)(j+2)] w j = 1/ [( j + 1 ) ( j + 2 )] and define
M n F = ∑ j = 0 ∞ w j W n ( j ) . (27) M_n^{\mathrm{F}}=\sum_{j=0}^{\infty}w_jW_n^{(j)}. \tag*{(27)} M n F = j = 0 ∑ ∞ w j W n ( j ) . (27)
The weights sum to one, so M 0 F = 1 M_0^{\mathrm{F}}=1 M 0 F = 1 . The process is independent of α \alpha α .
At each time only one account is active. Learning the event from the preceding pilot keeps its choice predictable. Under an alternative, a sufficiently accurate pilot identifies an event with true violation of order Δ ( S ) \Delta(S) Δ ( S ) , and the next block then earns log wealth of order m j Δ ( S ) 2 m_j\Delta(S)^2 m j Δ ( S ) 2 . Trying geometrically increasing pilot sizes costs only log ( 1 / w j ) = O ( log ( j + 1 ) ) \log(1/w_j)=O(\log(j+1)) log ( 1/ w j ) = O ( log ( j + 1 )) log capital. This becomes the iterated logarithm in the stopping-time bound.
Theorem 3.2 (Small-gap sample complexity). The process M F M^{\mathrm{F}} M F is a test supermartingale under P 0 . \mathcal{P}_0. P 0 . There is an absolute constant C C C such that, for every S ∉ P 0 S\notin\mathcal{P}_0 S ∈ / P 0 and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
E S τ α ( M F ) ≤ C Δ ( S ) 2 [ d + log ( 1 / α ) + ℓ ( Δ ( S ) 2 ) ] . (28) \mathbb{E}_S\tau_\alpha(M^{\mathrm{F}})\leq\frac{C}{\Delta(S)^2}\left[d+\log(1/\alpha)+\ell(\Delta(S)^2)\right]. \tag*{(28)} E S τ α ( M F ) ≤ Δ ( S ) 2 C [ d + log ( 1/ α ) + ℓ ( Δ ( S ) 2 ) ] . (28) Consequently, for 0 < Γ ( S ) ≤ 1 0<\Gamma(S)\leq1 0 < Γ ( S ) ≤ 1 ,
E S τ α ( M F ) ≤ C P , ϵ 0 , d Γ ( S ) [ d + log ( 1 / α ) + ℓ ( Γ ( S ) ) ] , (29) \mathbb{E}_S\tau_\alpha(M^{\mathrm{F}})\leq\frac{C_{P,\epsilon_0,d}}{\Gamma(S)}\left[d+\log(1/\alpha)+\ell(\Gamma(S))\right], \tag*{(29)} E S τ α ( M F ) ≤ Γ ( S ) C P , ϵ 0 , d [ d + log ( 1/ α ) + ℓ ( Γ ( S )) ] , (29) where C P , ϵ 0 , d < ∞ C_{P,\epsilon_0,d}<\infty C P , ϵ 0 , d < ∞ depends only on the fixed null geometry. Also, M n F → ∞ M_n^{\mathrm{F}}\to\infty M n F → ∞ almost surely under every such S S S .
For fixed α \alpha α , the theorem gives O ( Γ ( S ) − 1 log log ( 1 / Γ ( S ) ) ) O(\Gamma(S)^{-1}\log\log(1/\Gamma(S))) O ( Γ ( S ) − 1 log log ( 1/Γ ( S ))) expected sample size uniformly as Γ ( S ) ↓ 0 \Gamma(S)\downarrow0 Γ ( S ) ↓ 0 . The proof controls the entire hitting-time tail, rather than only the expected log wealth. No small-gap optimality claim for the original clipped-Kelly process is needed.
One process for both asymptotic regimes
Define
M n m i x = 1 2 M n C K + 1 2 M n F . (30) M_n^{\mathrm{mix}}=\frac{1}{2}M_n^{\mathrm{CK}}+\frac{1}{2}M_n^{\mathrm{F}}. \tag*{(30)} M n mix = 2 1 M n CK + 2 1 M n F . (30)
Here M C K M^{\mathrm{CK}} M CK is the Laplace-smoothed clipped-Kelly process defined in (15) . The mixture is a simple device for retaining each component’s guarantee; the same general combination principle appears in [1 Proposition 5.1] .
Corollary 3.3 (Exact Wald constant and optimal Farrell order). The process M m i x M^{\mathrm{mix}} M mix is an α \alpha α -independent test supermartingale under P 0 \mathbb P_0 P 0 and is power one under every i.i.d. S ∉ P 0 S\notin\mathcal P_0 S ∈ / P 0 . For each fixed full-support S ∉ P 0 S\notin\mathcal P_0 S ∈ / P 0 ,
E S τ α ( M m i x ) ∼ log ( 1 / α ) Γ ( S ) as α ↓ 0. (31) \mathbb E_S\tau_\alpha(M^{\mathrm{mix}})\sim\frac{\log(1/\alpha)}{\Gamma(S)}\quad\text{as }\alpha\downarrow0. \tag*{(31)} E S τ α ( M mix ) ∼ Γ ( S ) log ( 1/ α ) as α ↓ 0. (31) For every S ∉ P 0 S\notin\mathcal P_0 S ∈ / P 0 with 0 < Γ ( S ) ≤ 1 0<\Gamma(S)\le1 0 < Γ ( S ) ≤ 1 , it also satisfies
E S τ α ( M m i x ) ≤ C P , ϵ 0 , d ′ Γ ( S ) [ d + log ( 1 / α ) + ℓ ( Γ ( S ) ) ] . (32) \mathbb E_S\tau_\alpha(M^{\mathrm{mix}})\le\frac{C'_{P,\epsilon_0,d}}{\Gamma(S)}\left[d+\log(1/\alpha)+\ell(\Gamma(S))\right]. \tag*{(32)} E S τ α ( M mix ) ≤ Γ ( S ) C P , ϵ 0 , d ′ [ d + log ( 1/ α ) + ℓ ( Γ ( S )) ] . (32) Finally, for fixed full-support S ∉ P 0 S\notin\mathcal P_0 S ∈ / P 0 ,
0 ≤ n Γ ( S ) − E S log M n m i x ≤ log ( n + d − 1 d − 1 ) + log 2. (33) 0\le n\Gamma(S)-\mathbb E_S\log M_n^{\mathrm{mix}}\le\log\left(\frac{n+d-1}{d-1}\right)+\log2. \tag*{(33)} 0 ≤ n Γ ( S ) − E S log M n mix ≤ log ( d − 1 n + d − 1 ) + log 2. (33)
The word “optimal” in the Farrell claim refers to order and to the impossibility of a uniformly smaller rate. It does not assert a sharp leading constant or a matching lower bound at every isolated alternative. Specifically, for every fixed α ∈ ( 0 , 1 / 2 ) \alpha\in(0,1/2) α ∈ ( 0 , 1/2 ) and every level-α \alpha α test τ \tau τ having power one against the whole complement,
lim sup S ∉ P 0 : Γ ( S ) ↓ 0 Γ ( S ) E S τ ℓ ( Γ ( S ) ) > 0. (34) \limsup_{S\notin\mathcal P_0:\Gamma(S)\downarrow0}\frac{\Gamma(S)\mathbb E_S\tau}{\ell(\Gamma(S))}>0. \tag*{(34)} S ∈ / P 0 : Γ ( S ) ↓ 0 lim sup ℓ ( Γ ( S )) Γ ( S ) E S τ > 0. (34)
To apply the general Farrell lower bound [1 Theorem 3.2 and Corollary 3.3] , Appendix § 7 .§ 4 constructs an explicit one-parameter family approaching a common boundary null whose KL projection is that same null throughout. This verifies that the lower-bound obstruction occurs in the present TV-ball problem. Exact implementation details for the learned-event and combined processes appear in § 4.2 .
The statistical roles of the two components are different. Clipped Kelly retains the full information number at each fixed alternative. The event-based component supplies uniform scale adaptation near the boundary.
Exact O ( log d ) O(\log d) O ( log d ) dynamic implementation
This section gives exact implementations of clipped Kelly, the Farrell-optimal processes, and their mixture.
Clipped-Kelly implementation
We first describe a static implementation that costs O ( d log d ) O(d\log d) O ( d log d ) per oracle evaluation, and then show how to maintain the same every-round factor in O ( log d ) O(\log d) O ( log d ) worst-case time per observation. Throughout this section, complexity counts unit-cost exact arithmetic operations and comparisons, and memory is measured in numeric storage words.
Write ρ i = U i / P i \rho_i=U_i/P_i ρ i = U i / P i and sort ρ ( 1 ) ≤ ⋯ ≤ ρ ( d ) \rho_{(1)}\leq\cdots\leq\rho_{(d)} ρ ( 1 ) ≤ ⋯ ≤ ρ ( d ) . Carry P i , U i P_i,U_i P i , U i along with the permutation and define the prefix and suffix sums
P j p r e = ∑ r = 1 j P ( r ) , U j p r e = ∑ r = 1 j U ( r ) , P j s u f = ∑ r = j d P ( r ) , U j s u f = ∑ r = j d U ( r ) . P_j^{\mathrm{pre}}=\sum_{r=1}^{j}P_{(r)},\qquad U_j^{\mathrm{pre}}=\sum_{r=1}^{j}U_{(r)},\qquad P_j^{\mathrm{suf}}=\sum_{r=j}^{d}P_{(r)},\qquad U_j^{\mathrm{suf}}=\sum_{r=j}^{d}U_{(r)}. P j pre = r = 1 ∑ j P ( r ) , U j pre = r = 1 ∑ j U ( r ) , P j suf = r = j ∑ d P ( r ) , U j suf = r = j ∑ d U ( r ) .
Proposition 4.1 (Sorting-and-scanning oracle). For U ∈ Δ d ∘ ∖ P 0 U\in\Delta_d^\circ\setminus\mathcal{P}_0 U ∈ Δ d ∘ ∖ P 0 , use the endpoint conventions ρ ( 0 ) = 0 \rho_{(0)}=0 ρ ( 0 ) = 0 and ρ ( d + 1 ) = + ∞ \rho_{(d+1)}=+\infty ρ ( d + 1 ) = + ∞ . The lower threshold is
a ( U ) = U j p r e P j p r e − ϵ 0 a(U)=\frac{U_j^{\mathrm{pre}}}{P_j^{\mathrm{pre}}-\epsilon_0} a ( U ) = P j pre − ϵ 0 U j pre for an index j ∈ { 1 , … , d } j\in\{1,\ldots,d\} j ∈ { 1 , … , d } satisfying
P j p r e > ϵ 0 , ρ ( j ) ≤ a ( U ) ≤ ρ ( j + 1 ) . P_j^{\mathrm{pre}}>\epsilon_0,\qquad\rho_{(j)}\leq a(U)\leq\rho_{(j+1)}. P j pre > ϵ 0 , ρ ( j ) ≤ a ( U ) ≤ ρ ( j + 1 ) . The upper threshold is
b ( U ) = U j s u f P j s u f + ϵ 0 b(U)=\frac{U_j^{\mathrm{suf}}}{P_j^{\mathrm{suf}}+\epsilon_0} b ( U ) = P j suf + ϵ 0 U j suf for an index j ∈ { 1 , … , d } j\in\{1,\ldots,d\} j ∈ { 1 , … , d } satisfying
ρ ( j − 1 ) ≤ b ( U ) ≤ ρ ( j ) . \rho_{(j-1)}\leq b(U)\leq\rho_{(j)}. ρ ( j − 1 ) ≤ b ( U ) ≤ ρ ( j ) . Coordinates tied at a threshold may be placed on either side. Thus, a static oracle evaluation costs O ( d log d ) O(d\log d) O ( d log d ) time and O ( d ) O(d) O ( d ) memory.
Naively recomputing the oracle in (15) sorts d d d ratios after every observation. We now give an exact dynamic implementation of the same fresh factor. It maintains an implicit representation of the factor: its value at a specified category can be evaluated in constant time, whereas explicitly listing all d d d values takes O ( d ) O(d) O ( d ) time. The complexity bounds are arithmetic bounds; the bit cost additionally depends on the numerical input representations and the growing counts. This section uses the standing assumption ϵ 0 > 0 \epsilon_0>0 ϵ 0 > 0 ; when ϵ 0 = 0 \epsilon_0=0 ϵ 0 = 0 , no clipping thresholds are needed and the ordinary likelihood-ratio update is simpler.
After t t t observations define
c i ( t ) = N i ( t ) + α i , C t = t + α + , z i ( t ) = c i ( t ) P i . c_i(t)=N_i(t)+\alpha_i,\qquad C_t=t+\alpha_+,\qquad z_i(t)=\frac{c_i(t)}{P_i}. c i ( t ) = N i ( t ) + α i , C t = t + α + , z i ( t ) = P i c i ( t ) .
Then
U ^ t , i P i = z i ( t ) C t , ∑ i P i z i ( t ) = C t . \frac{\widehat{U}_{t,i}}{P_i}=\frac{z_i(t)}{C_t},\qquad\sum_i P_i z_i(t)=C_t. P i U t , i = C t z i ( t ) , i ∑ P i z i ( t ) = C t .
Whenever U ^ t ∉ P 0 \widehat{U}_t\notin\mathcal{P}_0 U t ∈ / P 0 , let a t , b t a_t,b_t a t , b t be its oracle thresholds and set
A t = C t a t , B t = C t b t . A_t=C_ta_t,\qquad B_t=C_tb_t. A t = C t a t , B t = C t b t .
For every t ≥ 0 t \ge0 t ≥ 0 and x ≥ 0 x \ge0 x ≥ 0 , define
F t ( x ) : = ∑ i P i ( x − z i ( t ) ) + − ϵ 0 x . (35) F_t(x) := \sum_i P_i(x-z_i(t))_+ - \epsilon_0 x. \tag*{(35)} F t ( x ) := i ∑ P i ( x − z i ( t ) ) + − ϵ 0 x . (35)
G t ( x ) : = ∑ i P i ( z i ( t ) − x ) + − ϵ 0 x . (36) G_t(x) := \sum_i P_i(z_i(t)-x)_+ - \epsilon_0 x. \tag*{(36)} G t ( x ) := i ∑ P i ( z i ( t ) − x ) + − ϵ 0 x . (36)
Lemma 4.2 (Rescaled threshold equations). Assume U ^ t ∉ P 0 \widehat{U}_t \notin\mathcal{P}_0 U t ∈ / P 0 . Then A t A_t A t and B t B_t B t are the unique positive solutions of
F t ( A ) = 0 , G t ( B ) = 0 , F_t(A)=0, \qquad G_t(B)=0, F t ( A ) = 0 , G t ( B ) = 0 , respectively. Moreover,
E U ^ t ( i ) = clip ( z i ( t ) , A t , B t ) C t . (37) E_{\widehat{U}_t}(i)=\frac{\operatorname{clip}(z_i(t),A_t,B_t)}{C_t}. \tag*{(37)} E U t ( i ) = C t clip ( z i ( t ) , A t , B t ) . (37)
For any predictor, the count recursion implies that, if X t + 1 = k X_{t+1}=k X t + 1 = k , then
z k ( t + 1 ) = z k ( t ) + 1 P k , z i ( t + 1 ) = z i ( t ) ( i ≠ k ) . (38) z_k(t+1)=z_k(t)+\frac{1}{P_k}, \qquad z_i(t+1)=z_i(t) \quad(i\ne k). \tag*{(38)} z k ( t + 1 ) = z k ( t ) + P k 1 , z i ( t + 1 ) = z i ( t ) ( i = k ) . (38)
For a nonnegative query value v v v , define
P t < ( v ) = ∑ z i ( t ) < v P i , S t < ( v ) = ∑ z i ( t ) < v P i z i ( t ) = ∑ z i ( t ) < v c i ( t ) . P_t^{<}(v)=\sum_{z_i(t)<v}P_i, \qquad S_t^{<}(v)=\sum_{z_i(t)<v}P_i z_i(t)=\sum_{z_i(t)<v}c_i(t). P t < ( v ) = z i ( t ) < v ∑ P i , S t < ( v ) = z i ( t ) < v ∑ P i z i ( t ) = z i ( t ) < v ∑ c i ( t ) .
Then
F t ( v ) = v { P t < ( v ) − ϵ 0 } − S t < ( v ) . (39) F_t(v)=v\{P_t^{<}(v)-\epsilon_0\}-S_t^{<}(v). \tag*{(39)} F t ( v ) = v { P t < ( v ) − ϵ 0 } − S t < ( v ) . (39)
Similarly, let
P t > ( v ) = ∑ z i ( t ) > v P i , S t > ( v ) = ∑ z i ( t ) > v P i z i ( t ) , P_t^{>}(v)=\sum_{z_i(t)>v}P_i, \qquad S_t^{>}(v)=\sum_{z_i(t)>v}P_i z_i(t), P t > ( v ) = z i ( t ) > v ∑ P i , S t > ( v ) = z i ( t ) > v ∑ P i z i ( t ) ,
so
G t ( v ) = S t > ( v ) − v { P t > ( v ) + ϵ 0 } . (40) G_t(v)=S_t^{>}(v)-v\{P_t^{>}(v)+\epsilon_0\}. \tag*{(40)} G t ( v ) = S t > ( v ) − v { P t > ( v ) + ϵ 0 } . (40)
Write P t ≥ ( v ) P_t^{\ge}(v) P t ≥ ( v ) and S t ≥ ( v ) S_t^{\ge}(v) S t ≥ ( v ) for the corresponding sums over { i : z i ( t ) ≥ v } \{i:z_i(t)\ge v\} { i : z i ( t ) ≥ v } .
For an outside-null predictor, F t F_t F t is convex, is negative for sufficiently small positive arguments, and has a unique positive root; after that crossing it remains positive. Thus F t ( v ) ≥ 0 F_t(v)\ge0 F t ( v ) ≥ 0 is a monotone predicate over the ordered stored keys. The function G t G_t G t is strictly decreasing: its right and left slopes are − P t ≥ ( x ) − ϵ 0 -P_t^{\ge}(x)-\epsilon_0 − P t ≥ ( x ) − ϵ 0 and − P t ≥ ( x ) − ϵ 0 -P_t^{\ge}(x)-\epsilon_0 − P t ≥ ( x ) − ϵ 0 , respectively. Hence G t ( v ) ≤ 0 G_t(v)\le0 G t ( v ) ≤ 0 is also a monotone predicate.
To locate the crossings relative to the stored keys, write
z min ( t ) = min i z i ( t ) , z max ( t ) = max i z i ( t ) . z_{\min}(t)=\min_i z_i(t), \qquad z_{\max}(t)=\max_i z_i(t). z m i n ( t ) = i min z i ( t ) , z m a x ( t ) = i max z i ( t ) .
Whenever U ^ t ∉ P 0 \widehat{U}_t\notin\mathcal{P}_0 U t ∈ / P 0 ,
F t ( C t ) = G t ( C t ) = C t { DTV ( U ^ t , P ) − ϵ 0 } > 0. F_t(C_t)=G_t(C_t)=C_t\{\operatorname{DTV}(\widehat{U}_t,\mathcal{P})-\epsilon_0\}>0. F t ( C t ) = G t ( C t ) = C t { DTV ( U t , P ) − ϵ 0 } > 0.
Also,
F t ( z min ( t ) ) = − ϵ 0 z min ( t ) < 0 , G t ( z max ( t ) ) = − ϵ 0 z max ( t ) < 0. F_t(z_{\min}(t))=-\epsilon_0z_{\min}(t)<0, \qquad G_t(z_{\max}(t))=-\epsilon_0z_{\max}(t)<0. F t ( z m i n ( t )) = − ϵ 0 z m i n ( t ) < 0 , G t ( z m a x ( t )) = − ϵ 0 z m a x ( t ) < 0.
The root properties therefore imply
z min ( t ) < A t < C t < B t < z max ( t ) . z_{\min}(t)<A_t<C_t<B_t<z_{\max}(t). z m i n ( t ) < A t < C t < B t < z m a x ( t ) .
In particular, the smallest satisfying stored key in each query below exists and has a predecessor.
Maintain the distinct z i ( t ) z_i(t) z i ( t ) as keys of a balanced binary search tree with worst-case height O ( log d ) O(\log d) O ( log d ) , such as an AVL or red–black tree, grouping ties in the same node. A node at key v v v stores its group mass, count sum, and cardinality,
p v = ∑ z i ( t ) = v P i , s v = ∑ z i ( t ) = v c i ( t ) , m v = # { i : z i ( t ) = v } . p_v = \sum_{z_i(t)=v} P_i,\qquad s_v = \sum_{z_i(t)=v} c_i(t),\qquad m_v = \#\{i : z_i(t)=v\}. p v = z i ( t ) = v ∑ P i , s v = z i ( t ) = v ∑ c i ( t ) , m v = # { i : z i ( t ) = v } .
Separate category arrays store P i P_i P i , c i ( t ) c_i(t) c i ( t ) , and z i ( t ) z_i(t) z i ( t ) , so a node does not need a list of category indices. Once the node at z k ( t ) z_k(t) z k ( t ) is located, removing category k k k subtracts P k P_k P k and the old c k ( t ) c_k(t) c k ( t ) from its group totals and decrements its cardinality, all in constant time. The node is deleted if its cardinality becomes zero. Insertion into an existing group adds the updated contributions and increments its cardinality; otherwise a new node is inserted.
Each node also stores the aggregate masses of its entire subtree T \mathcal{T} T ,
P ( T ) = ∑ i ∈ T P i , S ( T ) = ∑ i ∈ T P i z i ( t ) = ∑ i ∈ T c i ( t ) , P(\mathcal{T}) = \sum_{i\in\mathcal{T}} P_i,\qquad S(\mathcal{T}) = \sum_{i\in\mathcal{T}} P_i z_i(t) = \sum_{i\in\mathcal{T}} c_i(t), P ( T ) = i ∈ T ∑ P i , S ( T ) = i ∈ T ∑ P i z i ( t ) = i ∈ T ∑ c i ( t ) ,
where i ∈ T i \in\mathcal{T} i ∈ T means that category i i i belongs to a node in T \mathcal{T} T . Each aggregate is the sum of the current group total and the two child-subtree totals. These aggregates are repaired in constant time per visited node during rotations, insertion, and deletion.
Lemma 4.3 (Exact lower query). Assume U ^ t ∉ P 0 \widehat{U}_t \notin\mathcal{P}_0 U t ∈ / P 0 . Let v v v be the smallest stored key satisfying F t ( v ) ≥ 0 F_t(v) \ge0 F t ( v ) ≥ 0 . If F t ( v ) = 0 F_t(v) = 0 F t ( v ) = 0 , then A t = v A_t = v A t = v . Otherwise,
A t = S t ≤ ( v ) P t < ( v ) − ϵ 0 . A_t = \frac{S_t^{\le}(v)}{P_t^{<}(v)-\epsilon_0}. A t = P t < ( v ) − ϵ 0 S t ≤ ( v ) . The key v v v and A t A_t A t are found by one augmented-tree descent in O ( log d ) O(\log d) O ( log d ) time.
Lemma 4.4 (Exact upper query). Assume U ^ t ∉ P 0 \widehat{U}_t \notin\mathcal{P}_0 U t ∈ / P 0 . Let v v v be the smallest stored key satisfying G t ( v ) ≤ 0 G_t(v) \le0 G t ( v ) ≤ 0 . If G t ( v ) = 0 G_t(v) = 0 G t ( v ) = 0 , then B t = v B_t = v B t = v . Otherwise,
B t = S t ≥ ( v ) P t ≥ ( v ) + ϵ 0 , B_t = \frac{S_t^{\ge}(v)}{P_t^{\ge}(v)+\epsilon_0}, B t = P t ≥ ( v ) + ϵ 0 S t ≥ ( v ) , where the suffix includes the node at $v. The key v v v and B t B_t B t are found by one augmented-tree descent in O ( log d ) O(\log d) O ( log d ) time.
Null-ball membership is also logarithmic. Since both U ^ t \widehat{U}_t U t and P P P sum to one, D T V ( U ^ t , P ) = ∑ i ( P i − U ^ t , i ) + D_{\mathrm{TV}}(\widehat{U}_t,P) = \sum_i(P_i-\widehat{U}_{t,i})_+ D TV ( U t , P ) = ∑ i ( P i − U t , i ) + . Substituting U ^ t , i = P i z i ( t ) / C t \widehat{U}_{t,i}=P_i z_i(t)/C_t U t , i = P i z i ( t ) / C t gives
D T V ( U ^ t , P ) = C t P t < ( C t ) − S t < ( C t ) C t . (41) D_{\mathrm{TV}}(\widehat{U}_t,P)=\frac{C_tP_t^{<}(C_t)-S_t^{<}(C_t)}{C_t}. \tag*{(41)} D TV ( U t , P ) = C t C t P t < ( C t ) − S t < ( C t ) . (41)
Thus a single prefix query decides membership by comparing C t P t < ( C t ) − S t < ( C t ) C_tP_t^{<}(C_t)-S_t^{<}(C_t) C t P t < ( C t ) − S t < ( C t ) with ϵ 0 C t \epsilon_0 C_t ϵ 0 C t .
Initialization. Set c i ( 0 ) = α i c_i(0)=\alpha_i c i ( 0 ) = α i , C 0 = α + C_0=\alpha_+ C 0 = α + , and z i ( 0 ) = α i / P i z_i(0)=\alpha_i/P_i z i ( 0 ) = α i / P i . Form and sort the initial keys, group ties, and build the augmented balanced tree. Then evaluate (41) for U ^ 0 \widehat{U}_0 U 0 . If U ^ 0 ∉ P 0 \widehat{U}_0 \notin\mathcal{P}_0 U 0 ∈ / P 0 , perform the lower and upper queries to initialize A 0 A_0 A 0 , B 0 B_0 B 0 ; otherwise record that the first factor is identically one. These initial queries cost O ( log d ) O(\log d) O ( log d ) in addition to the O ( d log d ) O(d\log d) O ( d log d ) construction cost.
Online update. At the start of round t + 1 t+1 t + 1 , the tree and category arrays represent U ^ t \widehat{U}_t U t . If U ^ t ∈ P 0 \widehat{U}_t \in P_0 U t ∈ P 0 , its factor is identically one; otherwise the stored thresholds give E U ^ t E_{\widehat{U}_t} E U t through (37) . After observing X t + 1 = k X_{t+1}=k X t + 1 = k , first evaluate E U ^ t ( k ) E_{\widehat{U}_t}(k) E U t ( k ) using the current state and multiply the wealth by this factor. Then remove category k k k 's old contribution from its tie group, and update
c k ( t + 1 ) = c k ( t ) + 1 , z k ( t + 1 ) = z k ( t ) + 1 P k , C t + 1 = C t + 1. c_k(t+1)=c_k(t)+1,\qquad z_k(t+1)=z_k(t)+\frac{1}{P_k},\qquad C_{t+1}=C_t+1. c k ( t + 1 ) = c k ( t ) + 1 , z k ( t + 1 ) = z k ( t ) + P k 1 , C t + 1 = C t + 1.
All other category entries remain unchanged. Insert the updated contribution at the new key and evaluate (41) for U ^ t + 1 \widehat{U}_{t+1} U t + 1 . If this predictor is outside the null ball, perform the two threshold queries for A t + 1 , B t + 1 A_{t+1},B_{t+1} A t + 1 , B t + 1 ; otherwise record that the next factor is identically one. Thus every betting rule is chosen from past data, exactly as in (15) .
Theorem 4.5 (Exact dynamic every-round clipped Kelly). In the unit-cost exact-arithmetic model, after O ( d log d ) O(d\log d) O ( d log d ) initialization, an implicit representation of the every-round factor E U ^ t E_{\widehat{U}_t} E U t can be maintained using O ( d ) O(d) O ( d ) numeric storage words and O ( log d ) O(\log d) O ( log d ) worst-case time per observation. Given this representation, evaluating the factor at a specified category takes O ( 1 ) O(1) O ( 1 ) time. Through horizon n n n the total cost is
O ( d log d + n log d ) . O(d\log d+n\log d). O ( d log d + n log d ) . Let M n d y n M_n^{\mathrm{dyn}} M n dyn denote the wealth produced by this implementation, with M 0 d y n = 1 M_0^{\mathrm{dyn}}=1 M 0 dyn = 1 . For every observation sequence and every n ≥ 0 n\ge0 n ≥ 0 ,
M n d y n = M n C K . M_n^{\mathrm{dyn}}=M_n^{\mathrm{CK}}. M n dyn = M n CK .
Table 1. Computational complexity of the dynamic algorithm, measured in unit-cost arithmetic operations.
Exact implementation of the Farrell-optimal and the combined process
The learned-event process involves infinitely many accounts, and each account bets on an event selected from a pilot sample. Nevertheless, its exact implementation requires only one active account, accumulated frozen capital, and an augmented tree of category counts. We first describe the capital bookkeeping, then show how to select and evaluate the learned events without scanning all categories.
K j + w j W n ( j ) + 1 j + 2 , K j = ∑ r < j w r W 2 m r ( r ) . K_j+w_jW_n^{(j)}+\frac{1}{j+2},\qquad K_j=\sum_{r<j}w_rW_{2m_r}^{(r)}. K j + w j W n ( j ) + j + 2 1 , K j = r < j ∑ w r W 2 m r ( r ) .
Thus the account state requires only constant storage. At the end of block j j j , update
K j + 1 = K j + w j W 2 m j ( j ) K_{j+1}=K_j+w_jW_{2m_j}^{(j)} K j + 1 = K j + w j W 2 m j ( j )
and initialize the next account at one.
A direct implementation maintains the category counts and scans them at each dyadic boundary to select the next event. This uses O ( d ) O(d) O ( d ) memory and O ( n + d log ( n + 1 ) ) O(n + d \log(n + 1)) O ( n + d log ( n + 1 )) total work through time n n n , in addition to O ( d ) O(d) O ( d ) initialization. Its boundary updates cost O ( d ) O(d) O ( d ) . The following construction reduces these updates to O ( log d ) O(\log d) O ( log d ) .
Selecting the event by a suffix query. Maintain the raw-count ratios
v i ( n ) = N i ( n ) P i v_i(n) = \frac{N_i(n)}{P_i} v i ( n ) = P i N i ( n )
in an augmented balanced search tree. As in § 4.1 , group equal keys and store group cardinalities together with group and subtree sums of P i P_i P i and N i ( n ) N_i(n) N i ( n ) . Only the observed category changes its key, by 1 / P i 1/P_i 1/ P i , so one removal and insertion update the tree in O ( log d ) O(\log d) O ( log d ) worst-case time. Initially all keys are zero, allowing O ( d ) O(d) O ( d ) initialization.
At a dyadic time m = m j m = m_j m = m j , the selected event is
A ^ j = i ( m ) > m . \widehat{A}_j = i(m) > m. A j = i ( m ) > m .
A single strict suffix query therefore returns
p j = ∑ v i ( m ) > m P i , s j = ∑ v i ( m ) > m N i ( m ) . p_j = \sum_{v_i(m)>m} P_i,\qquad s_j = \sum_{v_i(m)>m} N_i(m). p j = v i ( m ) > m ∑ P i , s j = v i ( m ) > m ∑ N i ( m ) .
These two sums determine the next bet:
q j = p j + ϵ 0 , Δ ^ j = ( s j m − p j − ϵ 0 ) + , λ j = 4 Δ ^ j . q_j = p_j + \epsilon_0,\qquad\widehat{\Delta}_j = \left(\frac{s_j}{m} - p_j - \epsilon_0\right)_{+},\qquad\lambda_j = 4\widehat{\Delta}_j. q j = p j + ϵ 0 , Δ j = ( m s j − p j − ϵ 0 ) + , λ j = 4 Δ j .
The query does not enumerate the members of A ^ j \widehat{A}_j A j .
Evaluating membership lazily. During the next block, the event A ^ j \widehat{A}_j A j must remain fixed even as the counts change. We recover its membership one observed category at a time. Maintain arrays stamp [ i ] \operatorname{stamp}[i] stamp [ i ] and bit [ i ] \operatorname{bit}[i] bit [ i ] , initially setting every stamp to ( − 1 ) (-1) ( − 1 ) .
1 N i ( t − 1 ) > m j P i , stamp [ i ] = j . \mathbf{1}_{N_i(t-1)>m_jP_i},\qquad\operatorname{stamp}[i] = j. 1 N i ( t − 1 ) > m j P i , stamp [ i ] = j .
At this first appearance of ( i ) (i) ( i ) in the block, its count has not changed since the pilot ended. Hence N i ( t − 1 ) = N i ( m j ) N_i(t-1) = N_i(m_j) N i ( t − 1 ) = N i ( m j ) , and the stored bit equals 1 i ∈ A ^ j \mathbf{1}_{i\in\widehat{A}_j} 1 i ∈ A j . Subsequent appearances reuse this bit. Incrementing the block identifier invalidates the old cache without clearing either array.
The current account is then multiplied by
exp { λ j [ bit [ i ] − q j ] − λ j 2 8 } , \exp\left\{\lambda_j\bigl[\operatorname{bit}[i]-q_j\bigr]-\frac{\lambda_j^2}{8}\right\}, exp { λ j [ bit [ i ] − q j ] − 8 λ j 2 } ,
after which the count and its tree entry are updated. Membership evaluation and account bookkeeping cost O ( 1 ) O(1) O ( 1 ) ; the tree update costs O ( log d ) O(\log d) O ( log d ) .
Boundary updates and the combined process. The first observation completes the initial pilot and selects account zero. At each subsequent dyadic endpoint, first complete the old account’s final bet and update the counts. Then freeze its capital and select the next account from the updated tree. This order ensures that each account uses exactly its prescribed pilot and betting block.
To maintain M m i x M^{\mathrm{mix}} M mix , also retain the tree of smoothed keys used by clipped Kelly. Evaluate both components using the pre-observation counts, increment the shared counts once, and update both trees. At a dyadic endpoint, select the next learned event after these updates. The two component wealths determine M n m i x = ( M n C K + M n r ) / 2 M_n^{\mathrm{mix}} = (M_n^{\mathrm{CK}} + M_n^{\mathrm{r}})/2 M n mix = ( M n CK + M n r ) /2 in constant time.
Proposition 4.6 (Logarithmic-time implementation). The process M F M^{\mathrm{F}} M F can be maintained with O ( d ) O(d) O ( d ) initialization and memory and O ( log d ) O(\log d) O ( log d ) worst-case time per observation. The combined process in (30) can therefore be maintained with O ( d log d ) O(d\log d) O ( d log d ) initialization, O ( d ) O(d) O ( d ) memory, and O ( log d ) O(\log d) O ( log d ) worst-case time per observation.
The proof in Appendix § 7 .§ 3 verifies the maintained state and the update order.
Experiment
We compare the proposed plug-in clipped-Kelly process with the least-favorable-distribution (LFD) e-process in a four-category multinomial model. We take
P = ( 0.25 , 0.25 , 0.25 , 0.25 ) , ϵ 0 = ϵ 1 = 0.05 , P=(0.25,0.25,0.25,0.25), \qquad\epsilon_0=\epsilon_1=0.05, P = ( 0.25 , 0.25 , 0.25 , 0.25 ) , ϵ 0 = ϵ 1 = 0.05 ,
with null class B T V ( P , 0.05 ) B_{\mathrm{TV}}(P,0.05) B TV ( P , 0.05 ) and, for defining the LFD benchmark, alternative class B T V ( Q , 0.05 ) B_{\mathrm{TV}}(Q,0.05) B TV ( Q , 0.05 ) , where Q = ( 0.37 , 0.13 , 0.25 , 0.25 ) Q=(0.37,0.13,0.25,0.25) Q = ( 0.37 , 0.13 , 0.25 , 0.25 ) . The corresponding least-favorable pair is R ⋆ = ( 0.30 , 0.20 , 0.25 , 0.25 ) R^{\star}=(0.30,0.20,0.25,0.25) R ⋆ = ( 0.30 , 0.20 , 0.25 , 0.25 ) and Q ⋆ = ( 0.32 , 0.18 , 0.25 , 0.25 ) Q^{\star}=(0.32,0.18,0.25,0.25) Q ⋆ = ( 0.32 , 0.18 , 0.25 , 0.25 ) , giving E L F D = Q ⋆ / R ⋆ = ( 1.0667 , 0.9 , 1 , 1 ) E_{\mathrm{LFD}}=Q^{\star}/R^{\star}=(1.0667,0.9,1,1) E LFD = Q ⋆ / R ⋆ = ( 1.0667 , 0.9 , 1 , 1 ) . We generate i.i.d. observations from
S = ( 0.37 , 0.08 , 0.30 , 0.25 ) , S=(0.37,0.08,0.30,0.25), S = ( 0.37 , 0.08 , 0.30 , 0.25 ) ,
which lies on the boundary of the alternative TV ball since D T V ( S , Q ) = 0.05 D_{\mathrm{TV}}(S,Q)=0.05 D TV ( S , Q ) = 0.05 . At each round, our method forms the Laplace-smoothed empirical distribution S ~ t − 1 , i = ( N i ( t − 1 ) + 1 ) / ( t + 3 ) \widetilde{S}_{t-1,i}=(N_i(t-1)+1)/(t+3) S t − 1 , i = ( N i ( t − 1 ) + 1 ) / ( t + 3 ) and uses the corresponding pointwise clipped-Kelly oracle E S ~ t − 1 E_{\widetilde{S}_{t-1}} E S t − 1 . We compare this with the fixed LFD process and with an infeasible oracle that knows S S S . The alternative center Q Q Q is supplied only to the LFD benchmark. The adaptive procedure uses the null center P P P , the robustness radius, and past observations; it does not receive Q Q Q or the data-generating distribution S S S . The oracle curve represents the performance available if S S S were known.
Figure 1 shows the mean cumulative log wealth over 10,000 independent simulations up to time 500; the dashed line is the level-0.05 threshold log 20 and the dotted line is the average pathwise regret, log W t ⋆ − log M t C K \log W_t^\star- \log M_t^{\mathrm{CK}} log W t ⋆ − log M t CK , of our plug-in clipped Kelly e-process. The LFD growth rate is 0.01545, whereas the oracle rate is Γ ( S ) = 0.05899 \Gamma(S) = 0.05899 Γ ( S ) = 0.05899 , about 3.82 times larger.
Figure 1. Mean cumulative log wealth in the four-category TV-neighborhood experiment with ϵ 0 = ϵ 1 = 0.05 \epsilon_0=\epsilon_1=0.05 ϵ 0 = ϵ 1 = 0.05 . The curves show the proposed predictable plug-in clipped-Kelly process, the fixed least-favorable-distribution (LFD) process, and the infeasible oracle that knows the true alternative S S S . Results are averaged over 10,000 independent Monte Carlo replications. Although the plug-in process incurs an initial learning cost, its long-run growth rate is substantially larger than that of the LFD process.
The plug-in method initially incurs a learning cost but approaches the oracle slope and substantially outgrows the fixed LFD process, with mean stopping times 98.1, 195.3, and 52.7 for the plug-in, LFD, and oracle procedures, respectively.
Discussion
We studied power-one sequential testing with the goal of adapting to the unknown alternative while maintaining anytime validity over a total variation ball. Our predictable clipped-Kelly e-process learns the corresponding pointwise oracle online, with a pathwise regret bound. We also establish the optimality of the stopping time for that e-process asymptotically as the type-I error level α \alpha α converges to zero. We construct a complementary e-process that provides adaptation to alternatives approaching the null boundary. Averaging the two processes yields a single e-process with power one against the entire complement of the null. Its expected stopping time is simultaneously optimal in both regimes.
Exact dynamic implementation accompanies the statistical guarantees. After O ( d log d ) O(d \log d) O ( d log d ) initialization, the combined process requires O ( log d ) O(\log d) O ( log d ) worst-case time per observation. The existing LFD process has the same initialization cost and takes constant time per observation. Thus, adaptation to the unknown alternative is achieved with only logarithmic per-observation overhead, while allowing faster evidence accumulation against the null.
The TV model serves as a concrete robust model, for which we establish statistical and computational guarantees. The statistical arguments can be extended to other convex robust null classes on finite alphabets, including Huber’s ϵ \epsilon ϵ -contamination neighborhoods and general f f f -divergence neighborhoods. The explicit formulas and computational guarantees, however, depend on the structure of the chosen null class.
Acknowledgments. AI tools assisted with the design of computationally efficient algorithms, obtaining the regret bound, the implementation of simulation experiments, and the writing. The authors take full responsibility for all content of the paper.
Omitted Proofs
Omitted Proofs from Section 2
Proof of Lemma 2.1 . For the lower threshold, define
F − ( z ) = ∑ i ( z P i − U i ) + − z ϵ 0 . F_{-}(z) = \sum_i (zP_i-U_i)_{+}-z\epsilon_0. F − ( z ) = i ∑ ( z P i − U i ) + − z ϵ 0 .
It is continuous and convex. Since U i / P i > 0 U_i/P_i>0 U i / P i > 0 for every i i i , if 0 < z < min i U i / P i 0<z<\min_i U_i/P_i 0 < z < min i U i / P i then the positive-part sum vanishes and F − ( z ) = − z ϵ 0 < 0 F_{-}(z)=-z\epsilon_0<0 F − ( z ) = − z ϵ 0 < 0 . On the other hand,
F − ( 1 ) = ∑ i ( P i − U i ) + − ϵ 0 = D T V ( U , P ) − ϵ 0 > 0. F_{-}(1)=\sum_i(P_i-U_i)_{+}-\epsilon_0=D_{\mathrm{TV}}(U,P)-\epsilon_0>0. F − ( 1 ) = i ∑ ( P i − U i ) + − ϵ 0 = D TV ( U , P ) − ϵ 0 > 0.
Thus a root exists in ( 0 , 1 ) (0,1) ( 0 , 1 ) . At any root z z z , writing L z = { i : U i / P i < z } L_z=\{i:U_i/P_i<z\} L z = { i : U i / P i < z } ,
z { P ( L z ) − ϵ 0 } = U ( L z ) > 0 , z\{P(L_z)-\epsilon_0\}=U(L_z)>0, z { P ( L z ) − ϵ 0 } = U ( L z ) > 0 ,
so the left slope is positive. Convexity rules out a second positive crossing. For the upper threshold,
F + ( z ) = ∑ i ( U i − z P i ) + − z ϵ 0 F_{+}(z)=\sum_i(U_i-zP_i)_{+}-z\epsilon_0 F + ( z ) = i ∑ ( U i − z P i ) + − z ϵ 0
is continuous, F + ( 1 ) = D T V ( U , P ) − ϵ 0 > 0 F_{+}(1)=D_{\mathrm{TV}}(U,P)-\epsilon_0>0 F + ( 1 ) = D TV ( U , P ) − ϵ 0 > 0 , and F + ( z ) = − z ϵ 0 < 0 F_{+}(z)=-z\epsilon_0<0 F + ( z ) = − z ϵ 0 < 0 once z > max i U i / P i z>\max_i U_i/P_i z > max i U i / P i . Moreover, its right and left derivatives are, respectively,
− ∑ i : U i / P i > z P i − ϵ 0 , − ∑ i : U i / P i ≥ z P i − ϵ 0 , -\sum_{i:U_i/P_i>z}P_i-\epsilon_0,\qquad-\sum_{i:U_i/P_i\ge z}P_i-\epsilon_0, − i : U i / P i > z ∑ P i − ϵ 0 , − i : U i / P i ≥ z ∑ P i − ϵ 0 ,
which are strictly negative. Hence F + F_{+} F + is strictly decreasing and has a unique root in ( 1 , ∞ ) (1,\infty) ( 1 , ∞ ) .
Proof of Theorem 2.2 . If U ∈ P 0 U\in\mathcal{P}_0 U ∈ P 0 , Jensen’s inequality gives ∑ i U i log E i ≤ log ∑ i U i E i ≤ 0 \sum_i U_i\log E_i\le\log\sum_i U_iE_i\le0 ∑ i U i log E i ≤ log ∑ i U i E i ≤ 0 for every E ∈ E 0 E\in\mathcal{E}_0 E ∈ E 0 , so E U ≡ 1 E_U\equiv1 E U ≡ 1 is optimal and R U = U R_U=U R U = U . Assume henceforth that U ∉ P 0 U\notin\mathcal{P}_0 U ∈ / P 0 .
L = { i : U i / P i < a ( U ) } , H = { i : U i / P i > b ( U ) } . L=\{i:U_i/P_i<a(U)\},\qquad H=\{i:U_i/P_i>b(U)\}. L = { i : U i / P i < a ( U )} , H = { i : U i / P i > b ( U )} .
On L L L , R U ( i ) = U i / a ( U ) < P i R_U(i)=U_i/a(U)<P_i R U ( i ) = U i / a ( U ) < P i ; on the middle set R U ( i ) = P i R_U(i)=P_i R U ( i ) = P i ; and on H H H , R U ( i ) = U i / b ( U ) > P i R_U(i)=U_i/b(U)>P_i R U ( i ) = U i / b ( U ) > P i . By the threshold equations,
∑ i ∈ L ( P i − R U ( i ) ) = 1 a ( U ) ∑ i ∈ L ( a ( U ) P i − U i ) = ϵ 0 , \sum_{i\in L}(P_i-R_U(i))=\frac{1}{a(U)}\sum_{i\in L}(a(U)P_i-U_i)=\epsilon_0, i ∈ L ∑ ( P i − R U ( i )) = a ( U ) 1 i ∈ L ∑ ( a ( U ) P i − U i ) = ϵ 0 ,
and similarly
∑ i ∈ H ( R U ( i ) − P i ) = ϵ 0 . \sum_{i\in H}(R_U(i)-P_i)=\epsilon_0. i ∈ H ∑ ( R U ( i ) − P i ) = ϵ 0 .
Thus R U R_U R U is a probability vector and D T V ( R U , P ) = ϵ 0 D_{\mathrm{TV}}(R_U,P)=\epsilon_0 D TV ( R U , P ) = ϵ 0 . Next,
1 − P ⋅ E U = ∑ i ∈ L ( U i − a ( U ) P i ) + ∑ i ∈ H ( U i − b ( U ) P i ) = − a ( U ) ϵ 0 + b ( U ) ϵ 0 , \begin{aligned}
1-P\cdot E_U
&=\sum_{i\in L}(U_i-a(U)P_i)+\sum_{i\in H}(U_i-b(U)P_i)\\
&=-a(U)\epsilon_0+b(U)\epsilon_0,
\end{aligned} 1 − P ⋅ E U = i ∈ L ∑ ( U i − a ( U ) P i ) + i ∈ H ∑ ( U i − b ( U ) P i ) = − a ( U ) ϵ 0 + b ( U ) ϵ 0 ,
so
P ⋅ E U + ϵ 0 { b ( U ) − a ( U ) } = 1. P \cdot E_U+\epsilon_0\{b(U)-a(U)\}=1. P ⋅ E U + ϵ 0 { b ( U ) − a ( U )} = 1.
Therefore, for every R ∈ P 0 R \in\mathcal{P}_0 R ∈ P 0 ,
E R E U ≤ 1 , \mathbb{E}_R E_U \le1, E R E U ≤ 1 ,
so E U ∈ E 0 E_U \in\mathcal{E}_0 E U ∈ E 0 .
It follows from part (a) and Theorem 4.1 of Larsson et al. [12 ] that R U R_U R U is a reverse projection. Also, one can check that for arbitrary R ∈ P 0 R \in\mathcal{P}_0 R ∈ P 0 ,
D K L ( U ∥ R ) − D K L ( U ∥ R U ) = − ∑ i U i log R i R U ( i ) ≥ − log ∑ i U i R i R U ( i ) = − log ∑ i R i E U ( i ) ≥ 0. \begin{aligned}
D_{\mathrm{KL}}(U\|R)-D_{\mathrm{KL}}(U\|R_U)=-\sum_i U_i\log\frac{R_i}{R_U(i)} \\
&\ge-\log\sum_i U_i\frac{R_i}{R_U(i)} \\
&=-\log\sum_i R_iE_U(i)\ge0.
\end{aligned} D KL ( U ∥ R ) − D KL ( U ∥ R U ) = − i ∑ U i log R U ( i ) R i ≥ − log i ∑ U i R U ( i ) R i = − log i ∑ R i E U ( i ) ≥ 0.
Hence R U R_U R U is a reverse projection. Because U i > 0 U_i>0 U i > 0 for all i i i , every R R R with finite D K L ( U ∥ R ) D_{\mathrm{KL}}(U\|R) D KL ( U ∥ R ) has positive coordinates, and R ↦ D K L ( U ∥ R ) R\mapsto D_{\mathrm{KL}}(U\|R) R ↦ D KL ( U ∥ R ) is strictly convex there; the reverse projection is therefore unique. Finally, for any E ∈ E 0 E\in\mathcal{E}_0 E ∈ E 0 ,
∑ i U i log E i = D K L ( U ∥ R U ) + ∑ i U i log E i E U ( i ) ≤ D K L ( U ∥ R U ) + log ∑ i R U ( i ) E i ≤ D K L ( U ∥ R U ) . \begin{aligned}
\sum_i U_i\log E_i=D_{\mathrm{KL}}(U\|R_U)+\sum_i U_i\log\frac{E_i}{E_U(i)} \\
&\le D_{\mathrm{KL}}(U\|R_U)+\log\sum_i R_U(i)E_i \\
&\le D_{\mathrm{KL}}(U\|R_U).
\end{aligned} i ∑ U i log E i = D KL ( U ∥ R U ) + i ∑ U i log E U ( i ) E i ≤ D KL ( U ∥ R U ) + log i ∑ R U ( i ) E i ≤ D KL ( U ∥ R U ) .
Equality holds for E = E U E=E_U E = E U , and strictness in Jensen together with full support of U U U gives uniqueness.
For m , δ > 0 m,\delta>0 m , δ > 0 , define
K m , δ : = { U ∈ Δ d : min i U i ≥ m , D T V ( U , P ) ≥ ϵ 0 + δ } . \mathcal{K}_{m,\delta}:=\left\{U\in\Delta_d:\min_i U_i\ge m,\ D_{\mathrm{TV}}(U,P)\ge\epsilon_0+\delta\right\}. K m , δ := { U ∈ Δ d : i min U i ≥ m , D TV ( U , P ) ≥ ϵ 0 + δ } .
Lemma A.1 (Continuity and uniform boundedness). On every nonempty K m , δ \mathcal{K}_{m,\delta} K m , δ , the maps U ↦ a ( U ) U\mapsto a(U) U ↦ a ( U ) , U ↦ b ( U ) U\mapsto b(U) U ↦ b ( U ) , U ↦ E U U\mapsto E_U U ↦ E U , and U ↦ Γ ( U ) U\mapsto\Gamma(U) U ↦ Γ ( U ) are continuous. Moreover,
m max i P i ≤ E U ( i ) ≤ 1 min i P i \frac{m}{\max_i P_i}\le E_U(i)\le\frac{1}{\min_i P_i} max i P i m ≤ E U ( i ) ≤ min i P i 1 uniformly over U ∈ K m , δ U\in\mathcal{K}_{m,\delta} U ∈ K m , δ and i ≤ d i\le d i ≤ d .
Proof. For the lower root define
F ( U , z ) = ∑ i ( z P i − U i ) + − z ϵ 0 . F(U,z)=\sum_i(zP_i-U_i)_+-z\epsilon_0. F ( U , z ) = i ∑ ( z P i − U i ) + − z ϵ 0 .
This function is jointly continuous. For U ∈ K m , δ U\in\mathcal{K}_{m,\delta} U ∈ K m , δ , the unique root satisfies
m max i P i ≤ a ( U ) < 1 , \frac{m}{\max_i P_i}\le a(U)<1, max i P i m ≤ a ( U ) < 1 ,
and F ( U , 1 ) = D T V ( U , P ) − ϵ 0 ≥ δ F(U,1)=D_{\mathrm{TV}}(U,P)-\epsilon_0\ge\delta F ( U , 1 ) = D TV ( U , P ) − ϵ 0 ≥ δ , so no sequence of lower roots can converge to one. If U n → U U_n\to U U n → U , compactness gives a convergent subsequence a ( U n k ) → a ∞ a(U_{n_k})\to a_\infty a ( U n k ) → a ∞ ; joint continuity yields F ( U , a ∞ ) = 0 F(U,a_\infty)=0 F ( U , a ∞ ) = 0 , and uniqueness forces a ∞ = a ( U ) a_{\infty}=a(U) a ∞ = a ( U ) . Hence the full sequence converges. The same argument applies to b ( U ) b(U) b ( U ) , whose roots lie in the common compact interval [ 1 , 1 / min i P i ] [1,1/\min_i P_i] [ 1 , 1/ min i P i ] and are separated from one by the same margin condition.
Clipping is continuous, so U ↦ E U U \mapsto E_U U ↦ E U is continuous. Since clipping keeps every coordinate between the minimum and maximum of U i / P i U_i/P_i U i / P i ,
m max i P i ≤ E U ( i ) ≤ 1 min i P i . \frac{m}{\max_i P_i} \le E_U(i) \le\frac{1}{\min_i P_i}. max i P i m ≤ E U ( i ) ≤ min i P i 1 .
The lower bound is positive uniformly on K m , δ \mathcal{K}_{m,\delta} K m , δ , and therefore Γ ( U ) = ∑ i U i log E U ( i ) \Gamma(U)=\sum_i U_i\log E_U(i) Γ ( U ) = ∑ i U i log E U ( i ) is continuous as well.
Proof of Lemma 2.4. The lower bound follows because E U ∈ E 0 E_U \in\mathcal{E}_0 E U ∈ E 0 and E S E_S E S is pointwise optimal at S S S . For the upper bound, recall that E U = U / R U E_U=U/R_U E U = U / R U for some R U ∈ P 0 R_U\in\mathcal{P}_0 R U ∈ P 0 . Hence
D K L ( S ∥ R U ) = D K L ( S ∥ U ) + h ( S , U ) . D_{\mathrm{KL}}(S\Vert R_U)=D_{\mathrm{KL}}(S\Vert U)+h(S,U). D KL ( S ∥ R U ) = D KL ( S ∥ U ) + h ( S , U ) .
Since R S R_S R S minimizes R ↦ D K L ( S ∥ R ) R\mapsto D_{\mathrm{KL}}(S\Vert R) R ↦ D KL ( S ∥ R ) over P 0 \mathcal{P}_0 P 0 ,
Γ ( S ) = D K L ( S ∥ R S ) ≤ D K L ( S ∥ R U ) , \Gamma(S)=D_{\mathrm{KL}}(S\Vert R_S)\le D_{\mathrm{KL}}(S\Vert R_U), Γ ( S ) = D KL ( S ∥ R S ) ≤ D KL ( S ∥ R U ) ,
which rearranges to the upper bound in (14) .
Proof of Theorem 2.5. Fix R ∈ P 0 R\in\mathcal{P}_0 R ∈ P 0 and suppose that X 1 , X 2 , … X_1,X_2,\ldots X 1 , X 2 , … are i.i.d. with distribution R R R . For every t ≥ 1 t\ge1 t ≥ 1 , the predictor U ^ t − 1 \widehat{U}_{t-1} U t − 1 is F t − 1 \mathcal{F}_{t-1} F t − 1 -measurable and has strictly positive coordinates. By Theorem 2.2 , E U ^ t − 1 ∈ E 0 E_{\widehat{U}_{t-1}}\in\mathcal{E}_0 E U t − 1 ∈ E 0 , and hence
∑ i = 1 d R i E U ^ t − 1 ( i ) ≤ 1. \sum_{i=1}^{d}R_iE_{\widehat{U}_{t-1}}(i)\le1. i = 1 ∑ d R i E U t − 1 ( i ) ≤ 1.
Since X t X_t X t is independent of F t − 1 \mathcal{F}_{t-1} F t − 1 with distribution R R R , we obtain
E R [ M t C K ∣ F t − 1 ] = M t − 1 C K E R [ E U ^ t − 1 ( X t ) ∣ F t − 1 ] = M t − 1 C K ∑ i = 1 d R i E U ^ t − 1 ( i ) ≤ M t − 1 C K . \begin{aligned}
\mathbb{E}_R\left[M_t^{\mathrm{CK}}\mid\mathcal{F}_{t-1}\right]
=M_{t-1}^{\mathrm{CK}}\mathbb{E}_R\left[E_{\widehat{U}_{t-1}}(X_t)\mid\mathcal{F}_{t-1}\right] \\
&=M_{t-1}^{\mathrm{CK}}\sum_{i=1}^{d}R_iE_{\widehat{U}_{t-1}}(i)
\le M_{t-1}^{\mathrm{CK}}.
\end{aligned} E R [ M t CK ∣ F t − 1 ] = M t − 1 CK E R [ E U t − 1 ( X t ) ∣ F t − 1 ] = M t − 1 CK i = 1 ∑ d R i E U t − 1 ( i ) ≤ M t − 1 CK .
The process is adapted and nonnegative, with M 0 C K = 1 M_0^{\mathrm{CK}}=1 M 0 CK = 1 . Taking expectations and iterating gives E R M t C K ≤ 1 \mathbb{E}_R M_t^{\mathrm{CK}}\le1 E R M t CK ≤ 1 for every t t t , which also establishes integrability. Thus ( M t C K ) t ≥ 0 (M_t^{\mathrm{CK}})_{t\ge0} ( M t CK ) t ≥ 0 is a nonnegative test supermartingale under every i.i.d. law R ∞ R^{\infty} R ∞ with R ∈ P 0 R\in\mathcal{P}_0 R ∈ P 0 .
Now we state and prove the following auxiliary lemma, which we will invoke later.
Lemma A.2 (Logarithmic envelope). There is a constant C < ∞ C<\infty C < ∞ , depending only on P P P and α \alpha α , such that every smoothed empirical predictor based on T T T observations satisfies
max i ∣ log E U ( i ) ∣ ≤ C + log ( T + 1 ) . \max_i\left|\log E_U(i)\right|\le C+\log(T+1). i max ∣ log E U ( i ) ∣ ≤ C + log ( T + 1 ) .
Proof of Lemma A.2. Every coordinate satisfies U i ≥ α min / ( T + α + ) U_i\ge\alpha_{\min}/(T+\alpha_+) U i ≥ α m i n / ( T + α + ) and U i ≤ 1 U_i\le1 U i ≤ 1 . If U ∈ P 0 U\in\mathcal{P}_0 U ∈ P 0 , then E U ≡ 1 E_U\equiv1 E U ≡ 1 . Otherwise, clipping keeps E U ( i ) E_U(i) E U ( i ) between the minimum and maximum of U i / P i U_i/P_i U i / P i .
Proof of Theorem 2.6. Fix n ≥ 1 n \ge1 n ≥ 1 and a sequence x n x^n x n , and write N i = N i ( n ) N_i=N_i(n) N i = N i ( n ) . We use log 0 = − ∞ \log0=-\infty log 0 = − ∞ , omit zero-weight terms in logarithmic sums, and use 0 0 = 1 0^0=1 0 0 = 1 in likelihood products.
For A = E 0 \mathcal{A}=\mathcal{E}_0 A = E 0 or A = P 0 \mathcal{A}=\mathcal{P}_0 A = P 0 , define
J A ( c ) : = max z ∈ A ∑ i c i log z i , c ∈ [ 0 , ∞ ) d . J_{\mathcal{A}}(c):=\max_{z\in\mathcal{A}}\sum_i c_i\log z_i,\qquad c\in[0,\infty)^d. J A ( c ) := z ∈ A max i ∑ c i log z i , c ∈ [ 0 , ∞ ) d .
These maxima exist and are finite: both classes are compact, the objective is upper semicontinuous, and each class contains a vector with strictly positive coordinates. Indeed, E 0 \mathcal{E}_0 E 0 is closed, and since P ∈ P 0 P\in\mathcal{P}_0 P ∈ P 0 , every E ∈ E 0 E\in\mathcal{E}_0 E ∈ E 0 satisfies
0 ≤ E i ≤ 1 P i , i = 1 , … , d . 0\le E_i\le\frac{1}{P_i},\qquad i=1,\ldots,d. 0 ≤ E i ≤ P i 1 , i = 1 , … , d .
Thus E 0 \mathcal{E}_0 E 0 is compact; compactness of P 0 \mathcal{P}_0 P 0 follows from its definition as a closed subset of the simplex.
Let c t = 1 + N ( t ) c_t=1+N(t) c t = 1 + N ( t ) and choose a maximizer z t z_t z t at c t c_t c t . Since every coordinate of c t c_t c t is positive, every coordinate of z t z_t z t is positive. Evaluating the objective at the previous maximizer gives
J A ( c t ) ≥ ∑ i c t , i log z t − 1 , i = J A ( c t − 1 ) + log z t − 1 ( x t ) . J_{\mathcal{A}}(c_t)\ge\sum_i c_{t,i}\log z_{t-1,i}=J_{\mathcal{A}}(c_{t-1})+\log z_{t-1}(x_t). J A ( c t ) ≥ i ∑ c t , i log z t − 1 , i = J A ( c t − 1 ) + log z t − 1 ( x t ) .
Moreover,
J A ( c + c ′ ) ≤ J A ( c ) + J A ( c ′ ) , c , c ′ ∈ [ 0 , ∞ ) d . J_{\mathcal{A}}(c+c')\le J_{\mathcal{A}}(c)+J_{\mathcal{A}}(c'),\qquad c,c'\in[0,\infty)^d. J A ( c + c ′ ) ≤ J A ( c ) + J A ( c ′ ) , c , c ′ ∈ [ 0 , ∞ ) d .
Consequently, summing over t t t yields
∑ t = 1 n log z t − 1 ( x t ) ≤ J A ( 1 + N ) − J A ( 1 ) ≤ J A ( N ) . \sum_{t=1}^{n}\log z_{t-1}(x_t)\le J_{\mathcal{A}}(1+N)-J_{\mathcal{A}}(1)\le J_{\mathcal{A}}(N). t = 1 ∑ n log z t − 1 ( x t ) ≤ J A ( 1 + N ) − J A ( 1 ) ≤ J A ( N ) .
By Corollary 2.3 , we may take z t = E U ^ t z_t=E_{\widehat{U}_t} z t = E U t when A = E 0 \mathcal{A}=\mathcal{E}_0 A = E 0 . Therefore,
log M n C K ≤ J E 0 ( N ) = log W n ⋆ . \log M_n^{\mathrm{CK}}\le J_{\mathcal{E}_0}(N)=\log W_n^\star. log M n CK ≤ J E 0 ( N ) = log W n ⋆ .
This proves the nonnegativity of the regret.
Next, set R t = R U ^ t R_t=R_{\widehat{U}_t} R t = R U t and define
D n ( x n ) : = ∏ t = 1 n R t − 1 ( x t ) , L 0 ( x n ) : = max R ∈ P 0 ∏ i R i N i . D_n(x^n):=\prod_{t=1}^{n}R_{t-1}(x_t),\qquad L_0(x^n):=\max_{R\in\mathcal{P}_0}\prod_i R_i^{N_i}. D n ( x n ) := t = 1 ∏ n R t − 1 ( x t ) , L 0 ( x n ) := R ∈ P 0 max i ∏ R i N i .
Since U ^ t = c t / ( t + d ) \widehat{U}_t=c_t/(t+d) U t = c t / ( t + d ) has full support, Theorem 2.2 implies that R t R_t R t maximizes ∑ i c t , i log R i \sum_i c_{t,i}\log R_i ∑ i c t , i log R i over P 0 \mathcal{P}_0 P 0 . Applying the preceding telescoping inequality to P 0 \mathcal{P}_0 P 0 therefore gives
log D n ( x n ) ≤ J P 0 ( N ) = log L 0 ( x n ) . \log D_n(x^n)\le J_{\mathcal{P}_0}(N)=\log L_0(x^n). log D n ( x n ) ≤ J P 0 ( N ) = log L 0 ( x n ) .
Also define the unrestricted maximum likelihood
L Δ ( x n ) : = max q ∈ Δ d ∏ i q i N i = ∏ i ( N i n ) N i . L_\Delta(x^n):=\max_{q\in\Delta_d}\prod_i q_i^{N_i}=\prod_i\left(\frac{N_i}{n}\right)^{N_i}. L Δ ( x n ) := q ∈ Δ d max i ∏ q i N i = i ∏ ( n N i ) N i .
We now establish
log W n ⋆ = log L Δ ( x n ) − log L 0 ( x n ) = n Γ ( S ‾ n ) , \log W_n^\star=\log L_\Delta(x^n)-\log L_0(x^n)=n\Gamma(\overline{S}_n), log W n ⋆ = log L Δ ( x n ) − log L 0 ( x n ) = n Γ ( S n ) ,
including when S ˉ n \bar{S}_n S ˉ n lies on the boundary of the simplex. Let
I : = { i : N i > 0 } , I := \{i : N_i > 0\}, I := { i : N i > 0 } ,
and let R ⋆ R^\star R ⋆ attain L 0 ( x n ) L_0(x^n) L 0 ( x n ) . Since P ∈ P 0 P \in\mathcal{P}_0 P ∈ P 0 has full support, L 0 ( x n ) > 0 L_0(x^n) > 0 L 0 ( x n ) > 0 ; hence R i ⋆ > 0 R_i^\star> 0 R i ⋆ > 0 for every i ∈ I i \in I i ∈ I . For every E ∈ E 0 E \in\mathcal{E}_0 E ∈ E 0 , Jensen’s inequality and null validity imply
∑ i ∈ I S ˉ n , i log R i ⋆ E i S ˉ n , i ≤ log ( ∑ i ∈ I R i ⋆ E i ) ≤ 0 , \sum_{i\in I} \bar{S}_{n,i}\log\frac{R_i^\star E_i}{\bar{S}_{n,i}} \le\log\left(\sum_{i\in I} R_i^\star E_i\right) \le0, i ∈ I ∑ S ˉ n , i log S ˉ n , i R i ⋆ E i ≤ log ( i ∈ I ∑ R i ⋆ E i ) ≤ 0 ,
where the inequality is immediate if E i = 0 E_i = 0 E i = 0 for some i ∈ I i \in I i ∈ I . Rearranging and maximizing over E ∈ E 0 E \in\mathcal{E}_0 E ∈ E 0 gives
log W n ⋆ ≤ log L Δ ( x n ) − log L 0 ( x n ) . \log W_n^\star\le\log L_\Delta(x^n) - \log L_0(x^n). log W n ⋆ ≤ log L Δ ( x n ) − log L 0 ( x n ) .
To prove the reverse inequality, define
E i ⋆ : = { S ˉ n , i / R i ⋆ , i ∈ I , 0 , i ∉ I . E_i^\star:=
\begin{cases}
\bar{S}_{n,i}/R_i^\star, & i \in I,\\
0, & i \notin I.
\end{cases} E i ⋆ := { S ˉ n , i / R i ⋆ , 0 , i ∈ I , i ∈ / I .
We claim that E ⋆ ∈ E 0 E^\star\in\mathcal{E}_0 E ⋆ ∈ E 0 . Indeed, for every R ∈ P 0 R \in\mathcal{P}_0 R ∈ P 0 , convexity of P 0 \mathcal{P}_0 P 0 ensures that
R λ : = ( 1 − λ ) R ⋆ + λ R ∈ P 0 , 0 ≤ λ ≤ 1. R_\lambda:= (1-\lambda)R^\star+ \lambda R \in\mathcal{P}_0,\qquad0 \le\lambda\le1. R λ := ( 1 − λ ) R ⋆ + λ R ∈ P 0 , 0 ≤ λ ≤ 1.
Because R ⋆ R^\star R ⋆ maximizes ∑ i ∈ I S ˉ n , i log R i \sum_{i\in I}\bar{S}_{n,i}\log R_i ∑ i ∈ I S ˉ n , i log R i over P 0 \mathcal{P}_0 P 0 , the right derivative at λ = 0 \lambda= 0 λ = 0 satisfies
0 ≥ d d λ ∑ i ∈ I S ˉ n , i log R λ , i ∣ λ = 0 + = ∑ i ∈ I S ˉ n , i R i − R i ⋆ R i ⋆ . 0 \ge\left.\frac{d}{d\lambda}\sum_{i\in I}\bar{S}_{n,i}\log R_{\lambda,i}\right|_{\lambda=0+}
= \sum_{i\in I}\bar{S}_{n,i}\frac{R_i-R_i^\star}{R_i^\star}. 0 ≥ d λ d i ∈ I ∑ S ˉ n , i log R λ , i λ = 0 + = i ∈ I ∑ S ˉ n , i R i ⋆ R i − R i ⋆ .
Since ∑ i ∈ I S ˉ n , i = 1 \sum_{i\in I}\bar{S}_{n,i}=1 ∑ i ∈ I S ˉ n , i = 1 , this yields
∑ i R i E i ⋆ = ∑ i ∈ I R i S ˉ n , i R i ⋆ ≤ 1. \sum_i R_iE_i^\star= \sum_{i\in I}\frac{R_i\bar{S}_{n,i}}{R_i^\star}\le1. i ∑ R i E i ⋆ = i ∈ I ∑ R i ⋆ R i S ˉ n , i ≤ 1.
Thus E ⋆ ∈ E 0 E^\star\in\mathcal{E}_0 E ⋆ ∈ E 0 , and
∑ i ∈ I N i log E i ⋆ = log L Δ ( x n ) − log L 0 ( x n ) . \sum_{i\in I}N_i\log E_i^\star= \log L_\Delta(x^n)-\log L_0(x^n). i ∈ I ∑ N i log E i ⋆ = log L Δ ( x n ) − log L 0 ( x n ) .
Together with the preceding upper bound, this proves
log W n ⋆ = log L Δ ( x n ) − log L 0 ( x n ) . \log W_n^\star= \log L_\Delta(x^n)-\log L_0(x^n). log W n ⋆ = log L Δ ( x n ) − log L 0 ( x n ) .
Furthermore, maximizing the null likelihood is equivalent to minimizing D K L ( S ˉ n ∥ R ) D_{\mathrm{KL}}(\bar{S}_n\mathbin\Vert R) D KL ( S ˉ n ∥ R ) over R ∈ P 0 R \in\mathcal{P}_0 R ∈ P 0 . Therefore,
log W n ⋆ = n D K L ( S ˉ n ∥ R ⋆ ) = n Γ ( S ˉ n ) . \log W_n^\star= nD_{\mathrm{KL}}(\bar{S}_n\mathbin\Vert R^\star)=n\Gamma(\bar{S}_n). log W n ⋆ = n D KL ( S ˉ n ∥ R ⋆ ) = n Γ ( S ˉ n ) .
Finally, define
Q L ( x n ) : = ∏ t = 1 n U ^ t − 1 , x t . Q_L(x^n):=\prod_{t=1}^{n}\widehat{U}_{t-1,x_t}. Q L ( x n ) := t = 1 ∏ n U t − 1 , x t .
The identity E U ^ t − 1 = U ^ t − 1 / R t − 1 E\widehat{U}_{t-1}=\widehat{U}_{t-1}/R_{t-1} E U t − 1 = U t − 1 / R t − 1 gives
M n C K = Q L ( x n ) D n ( x n ) . M_n^{\mathrm{CK}}=\frac{Q_L(x^n)}{D_n(x^n)}. M n CK = D n ( x n ) Q L ( x n ) .
Using log D n ( x n ) ≤ log L 0 ( x n ) \log D_n(x^n) \le\log L_0(x^n) log D n ( x n ) ≤ log L 0 ( x n ) , we obtain
log W n ⋆ − log M n C K = log L Δ ( x n ) − log L 0 ( x n ) − log Q L ( x n ) + log D n ( x n ) ≤ log L Δ ( x n ) Q L ( x n ) . \log W_n^\star- \log M_n^{\mathrm{CK}} = \log L_\Delta(x^n) - \log L_0(x^n) - \log Q_{\mathrm{L}}(x^n) + \log D_n(x^n)
\le\log\frac{L_\Delta(x^n)}{Q_{\mathrm{L}}(x^n)}. log W n ⋆ − log M n CK = log L Δ ( x n ) − log L 0 ( x n ) − log Q L ( x n ) + log D n ( x n ) ≤ log Q L ( x n ) L Δ ( x n ) .
Consequently,
0 ≤ log W n ⋆ − log M n C K ≤ log L Δ ( x n ) Q L ( x n ) . (42) 0 \le\log W_n^\star- \log M_n^{\mathrm{CK}} \le\log\frac{L_\Delta(x^n)}{Q_{\mathrm{L}}(x^n)}. \tag*{(42)} 0 ≤ log W n ⋆ − log M n CK ≤ log Q L ( x n ) L Δ ( x n ) . (42)
For the Laplace predictor,
Q L ( x n ) = ( d − 1 ) ! ∏ i = 1 d N i ! ( n + d − 1 ) ! . (43) Q_{\mathrm{L}}(x^n) = \frac{(d-1)!\prod_{i=1}^{d}N_i!}{(n+d-1)!}. \tag*{(43)} Q L ( x n ) = ( n + d − 1 )! ( d − 1 )! ∏ i = 1 d N i ! . (43)
Moreover,
n ! ∏ i N i ! ∏ i ( N i n ) N i ≤ 1 , \frac{n!}{\prod_i N_i!}\prod_i\left(\frac{N_i}{n}\right)^{N_i}\le1, ∏ i N i ! n ! i ∏ ( n N i ) N i ≤ 1 ,
because the left-hand side is the probability, under the multinomial law with parameter S ˉ n \bar S_n S ˉ n , of observing the count vector N N N . Therefore,
L Δ ( x n ) Q L ( x n ) ≤ ( n + d − 1 ) ! n ! ( d − 1 ) ! = ( n + d − 1 d − 1 ) . (44) \frac{L_\Delta(x^n)}{Q_{\mathrm{L}}(x^n)}\le\frac{(n+d-1)!}{n!(d-1)!}=\binom{n+d-1}{d-1}. \tag*{(44)} Q L ( x n ) L Δ ( x n ) ≤ n ! ( d − 1 )! ( n + d − 1 )! = ( d − 1 n + d − 1 ) . (44)
Combining (42) , (44) , and log W n ⋆ = n Γ ( S ˉ n ) \log W_n^\star=n\Gamma(\bar S_n) log W n ⋆ = n Γ ( S ˉ n ) proves the result.
Proof of Corollary 2.7. Since E S ∈ E 0 E_S\in\mathcal{E}_0 E S ∈ E 0 , Theorem 2.6 implies, pathwise,
∑ t = 1 n log E S ( X t ) − log M n C K ≤ log W n ⋆ − log M n C K ≤ log ( n + d − 1 d − 1 ) . \sum_{t=1}^{n}\log E_S(X_t)-\log M_n^{\mathrm{CK}}\le\log W_n^\star-\log M_n^{\mathrm{CK}}\le\log\binom{n+d-1}{d-1}. t = 1 ∑ n log E S ( X t ) − log M n CK ≤ log W n ⋆ − log M n CK ≤ log ( d − 1 n + d − 1 ) .
Taking expectations under S S S gives the upper bound in (17) , since E S log E S ( X t ) = Γ ( S ) \mathbb{E}_S\log E_S(X_t)=\Gamma(S) E S log E S ( X t ) = Γ ( S ) . The lower bound follows from conditional pointwise optimality: E S [ log E U ^ t − 1 ( X t ) ∣ F t − 1 ] = h ( S , U ^ t − 1 ) ≤ Γ ( S ) \mathbb{E}_S[\log E_{\widehat U_{t-1}}(X_t)\mid\mathcal{F}_{t-1}]=h(S,\widehat U_{t-1})\le\Gamma(S) E S [ log E U t − 1 ( X t ) ∣ F t − 1 ] = h ( S , U t − 1 ) ≤ Γ ( S ) . The simpler bound (18) follows from ( N k ) ≤ ( e N / k ) k \binom{N}{k}\le(eN/k)^k ( k N ) ≤ ( e N / k ) k . Dividing (17) by n n n proves (19) .
Proof of Corollary 2.8. Put
Δ t : = Γ ( S ) − h ( S , U ^ t − 1 ) ≥ 0. \Delta_t:=\Gamma(S)-h(S,\widehat U_{t-1})\ge0. Δ t := Γ ( S ) − h ( S , U t − 1 ) ≥ 0.
Since E S ∑ t = 1 n Δ t = n Γ ( S ) − E S log M n C K \mathbb{E}_S\sum_{t=1}^{n}\Delta_t=n\Gamma(S)-\mathbb{E}_S\log M_n^{\mathrm{CK}} E S ∑ t = 1 n Δ t = n Γ ( S ) − E S log M n CK , Corollary 2.7 gives
E S ∑ t = 1 n Δ t ≤ log ( n + d − 1 d − 1 ) . \mathbb{E}_S\sum_{t=1}^{n}\Delta_t\le\log\binom{n+d-1}{d-1}. E S t = 1 ∑ n Δ t ≤ log ( d − 1 n + d − 1 ) .
For n k = 2 k n_k=2^k n k = 2 k , Markov’s inequality yields, for every ε > 0 \varepsilon>0 ε > 0 ,
P S ( ∑ t = 1 n k Δ t > ε n k ) ≤ log ( 2 k + d − 1 d − 1 ) ε 2 k . \mathbb{P}_S\left(\sum_{t=1}^{n_k}\Delta_t>\varepsilon n_k\right)\le\frac{\log\binom{2^k+d-1}{d-1}}{\varepsilon2^k}. P S ( t = 1 ∑ n k Δ t > ε n k ) ≤ ε 2 k log ( d − 1 2 k + d − 1 ) .
The right-hand side is summable in k k k . Borel–Cantelli therefore gives n k − 1 ∑ t ≤ n k Δ t → 0 n_k^{-1}\sum_{t\le n_k}\Delta_t\to0 n k − 1 ∑ t ≤ n k Δ t → 0 almost surely; monotonicity of the partial sums extends this to all n n n .
Now define
D t : = log E U ^ t − 1 ( X t ) − h ( S , U ^ t − 1 ) . D_t:=\log E_{\widehat U_{t-1}}(X_t)-h(S,\widehat U_{t-1}). D t := log E U t − 1 ( X t ) − h ( S , U t − 1 ) .
Then ( D t ) (D_t) ( D t ) is a martingale-difference sequence. By Lemma A.2 , ∣ D t ∣ ≤ C ′ ( 1 + log ( t + 1 ) ) |D_t| \le C'(1+\log(t+1)) ∣ D t ∣ ≤ C ′ ( 1 + log ( t + 1 )) , so
∑ t = 1 ∞ E S [ D t 2 ∣ F t − 1 ] t 2 < ∞ \sum_{t=1}^{\infty}\frac{\mathbb{E}_S[D_t^2\mid\mathcal{F}_{t-1}]}{t^2}<\infty t = 1 ∑ ∞ t 2 E S [ D t 2 ∣ F t − 1 ] < ∞
almost surely.
The martingale strong law and Kronecker’s lemma imply n − 1 ∑ t ≤ n D t → 0 n^{-1}\sum_{t\le n}D_t\to0 n − 1 ∑ t ≤ n D t → 0 almost surely. Since
1 n log M n C K = Γ ( S ) − 1 n ∑ t = 1 n Δ t + 1 n ∑ t = 1 n D t , \frac{1}{n}\log M_n^{\mathrm{CK}}=\Gamma(S)-\frac{1}{n}\sum_{t=1}^{n}\Delta_t+\frac{1}{n}\sum_{t=1}^{n}D_t, n 1 log M n CK = Γ ( S ) − n 1 t = 1 ∑ n Δ t + n 1 t = 1 ∑ n D t ,
(20) follows.
Proof of Theorem 2.9 . If E S τ = ∞ \mathbb{E}_S\tau=\infty E S τ = ∞ there is nothing to prove. Put τ m = τ ∧ m \tau_m=\tau\wedge m τ m = τ ∧ m and write
Y t = log S ( X t ) R S ( X t ) , E S Y t = Γ ( S ) . Y_t=\log\frac{S(X_t)}{R_S(X_t)},\qquad\mathbb{E}_S Y_t=\Gamma(S). Y t = log R S ( X t ) S ( X t ) , E S Y t = Γ ( S ) .
The likelihood ratio of the stopped observation under S S S relative to R S R_S R S is ∏ t = 1 τ m S ( X t ) / R S ( X t ) \prod_{t=1}^{\tau_m}S(X_t)/R_S(X_t) ∏ t = 1 τ m S ( X t ) / R S ( X t ) , and hence
D K L ( P S τ m ∥ P R S τ m ) = E S ∑ t = 1 τ m Y t . D_{\mathrm{KL}}\left(\mathbb{P}_S^{\tau_m}\middle\Vert\mathbb{P}_{R_S}^{\tau_m}\right)=\mathbb{E}_S\sum_{t=1}^{\tau_m}Y_t. D KL ( P S τ m P R S τ m ) = E S t = 1 ∑ τ m Y t .
Because τ m ≤ m \tau_m\le m τ m ≤ m and { τ m ≥ t } ∈ F t − 1 \{\tau_m\ge t\}\in\mathcal{F}_{t-1} { τ m ≥ t } ∈ F t − 1 , independence under the i.i.d. law S S S gives
E S ∑ t = 1 τ m Y t = ∑ t = 1 m E S [ 1 { τ m ≥ t } Y t ] = Γ ( S ) ∑ t = 1 m P S ( τ m ≥ t ) = Γ ( S ) E S τ m . \begin{aligned}
\mathbb{E}_S\sum_{t=1}^{\tau_m}Y_t
&=\sum_{t=1}^{m}\mathbb{E}_S[1\{\tau_m\ge t\}Y_t]\\
&=\Gamma(S)\sum_{t=1}^{m}\mathbb{P}_S(\tau_m\ge t)\\
&=\Gamma(S)\mathbb{E}_S\tau_m.
\end{aligned} E S t = 1 ∑ τ m Y t = t = 1 ∑ m E S [ 1 { τ m ≥ t } Y t ] = Γ ( S ) t = 1 ∑ m P S ( τ m ≥ t ) = Γ ( S ) E S τ m .
By data processing through the indicator 1 { τ ≤ m } 1\{\tau\le m\} 1 { τ ≤ m } ,
Γ ( S ) E S τ m ≥ D K L ( p m , q m ) , \Gamma(S)\mathbb{E}_S\tau_m\ge D_{\mathrm{KL}}(p_m,q_m), Γ ( S ) E S τ m ≥ D KL ( p m , q m ) ,
where p m = P S ( τ ≤ m ) → 1 p_m=\mathbb{P}_S(\tau\le m)\to1 p m = P S ( τ ≤ m ) → 1 and q m = P R S ( τ ≤ m ) ≤ α q_m=\mathbb{P}_{R_S}(\tau\le m)\le\alpha q m = P R S ( τ ≤ m ) ≤ α . Hence lim inf m D K L ( p m , q m ) ≥ log ( 1 / α ) \liminf_m D_{\mathrm{KL}}(p_m,q_m)\ge\log(1/\alpha) lim inf m D KL ( p m , q m ) ≥ log ( 1/ α ) . Monotone convergence gives (22).
Proof of Theorem 2.10 . Write Γ = Γ ( S ) > 0 \Gamma=\Gamma(S)>0 Γ = Γ ( S ) > 0 and fix 0 < η < Γ / 8 0<\eta<\Gamma/8 0 < η < Γ/8 . By Lemma A.1 , there are δ , L > 0 \delta,L>0 δ , L > 0 such that
∥ U − S ∥ 1 ≤ δ ⟹ h ( S , U ) ≥ Γ − η , max i ∣ log E U ( i ) ∣ ≤ L . (45) \|U-S\|_1\le\delta\quad\Longrightarrow\quad h(S,U)\ge\Gamma-\eta,\qquad\max_i|\log E_U(i)|\le L. \tag*{(45)} ∥ U − S ∥ 1 ≤ δ ⟹ h ( S , U ) ≥ Γ − η , i max ∣ log E U ( i ) ∣ ≤ L . (45)
Let S ˉ t = N ( t ) / t \bar S_t=N(t)/t S ˉ t = N ( t ) / t for t ≥ 1 t\ge1 t ≥ 1 . For the Laplace predictor,
∥ U ^ t − S ˉ t ∥ 1 ≤ 2 d t + d . \|\widehat U_t-\bar S_t\|_1\le\frac{2d}{t+d}. ∥ U t − S ˉ t ∥ 1 ≤ t + d 2 d .
For all sufficiently large t t t this is at most δ / 2 \delta/2 δ /2 . If ∥ S ˉ t − S ∥ 1 > δ / 2 \|\bar S_t-S\|_1>\delta/2 ∥ S ˉ t − S ∥ 1 > δ /2 , then some coordinate differs from its mean by more than δ / ( 2 d ) \delta/(2d) δ / ( 2 d ) . Hoeffding’s inequality and a union bound therefore give
P S ( ∥ U ^ t − S ∥ 1 > δ ) ≤ 2 d exp ( − t δ 2 2 d 2 ) . (46) \mathbb{P}_S(\|\widehat U_t-S\|_1>\delta)\le2d\exp\left(-\frac{t\delta^2}{2d^2}\right). \tag*{(46)} P S ( ∥ U t − S ∥ 1 > δ ) ≤ 2 d exp ( − 2 d 2 t δ 2 ) . (46)
for all sufficiently large t t t .
For a deterministic horizon n n n , let T n = ⌈ K log n ⌉ T_n=\lceil K\log n\rceil T n = ⌈ K log n ⌉ . Summing (46) over t ≥ T n t\ge T_n t ≥ T n and choosing K K K sufficiently large gives constants C < ∞ C<\infty C < ∞ and q > 2 q>2 q > 2 such that
P S ( ∃ t ≥ T n : ∥ U ^ t − S ∥ 1 > δ ) ≤ C n − q . \mathbb{P}_S\left(\exists t\ge T_n:\lVert\widehat{U}_t-S\rVert_1>\delta\right)\le Cn^{-q}. P S ( ∃ t ≥ T n : ∥ U t − S ∥ 1 > δ ) ≤ C n − q .
Define
Z t = log E U ^ t − 1 ( X t ) , m t = E S [ Z t ∣ F t − 1 ] , Z_t=\log\mathbb{E}_{\widehat{U}_{t-1}}(X_t),\qquad m_t=\mathbb{E}_S[Z_t\mid\mathcal{F}_{t-1}], Z t = log E U t − 1 ( X t ) , m t = E S [ Z t ∣ F t − 1 ] ,
and let σ \sigma σ be the first t > T n t>T_n t > T n for which the predictor U ^ t − 1 \widehat{U}_{t-1} U t − 1 leaves the δ \delta δ -neighborhood of S S S . The stopped increments
( Z t − m t ) 1 { t < σ } , t > T n , (Z_t-m_t)1\{t<\sigma\},\qquad t>T_n, ( Z t − m t ) 1 { t < σ } , t > T n ,
form a martingale-difference sequence bounded in absolute value by 2 L 2L 2 L . Azuma–Hoeffding therefore yields
P S ( σ > n , ∑ t = T n + 1 n Z t < ( n − T n ) ( Γ − 2 η ) ) ≤ e − c η ( n − T n ) . (47) \mathbb{P}_S\left(\sigma>n,\ \sum_{t=T_n+1}^{n}Z_t<(n-T_n)(\Gamma-2\eta)\right)\le e^{-c_\eta(n-T_n)}. \tag*{(47)} P S ( σ > n , t = T n + 1 ∑ n Z t < ( n − T n ) ( Γ − 2 η ) ) ≤ e − c η ( n − T n ) . (47)
The first T n T_n T n increments satisfy, deterministically by Lemma A.2 ,
∑ t = 1 T n Z t ≥ − O ( T n log T n ) = − o ( n ) . \sum_{t=1}^{T_n}Z_t\ge-O(T_n\log T_n)=-o(n). t = 1 ∑ T n Z t ≥ − O ( T n log T n ) = − o ( n ) .
Combining this with (46) and (47) , for all sufficiently large n n n ,
P S ( log M n C K < n ( Γ − 3 η ) ) ≤ C n − q + e − c η n . (48) \mathbb{P}_S\left(\log M_n^{\mathrm{CK}}<n(\Gamma-3\eta)\right)\le Cn^{-q}+e^{-c_\eta n}. \tag*{(48)} P S ( log M n CK < n ( Γ − 3 η ) ) ≤ C n − q + e − c η n . (48)
Put B = log ( 1 / α ) B=\log(1/\alpha) B = log ( 1/ α ) and
n B = ⌈ B Γ − 4 η ⌉ . n_B=\left\lceil\frac{B}{\Gamma-4\eta}\right\rceil. n B = ⌈ Γ − 4 η B ⌉ .
For all sufficiently large B B B and every n ≥ n B n\ge n_B n ≥ n B , n ( Γ − 3 η ) > B n(\Gamma-3\eta)>B n ( Γ − 3 η ) > B . Therefore
P S ( τ α C K > n ) ≤ C n − q + e − c η n . \mathbb{P}_S\left(\tau_\alpha^{\mathrm{CK}}>n\right)\le Cn^{-q}+e^{-c_\eta n}. P S ( τ α CK > n ) ≤ C n − q + e − c η n .
Using E τ = ∑ n ≥ 0 P ( τ > n ) \mathbb{E}\tau=\sum_{n\ge0}\mathbb{P}(\tau>n) E τ = ∑ n ≥ 0 P ( τ > n ) gives
E S τ α C K ≤ n B + ∑ n ≥ n B { C n − q + e − c η n } = n B + o ( B ) , \mathbb{E}_S\tau_\alpha^{\mathrm{CK}}\le n_B+\sum_{n\ge n_B}\{Cn^{-q}+e^{-c_\eta n}\}
=n_B+o(B), E S τ α CK ≤ n B + n ≥ n B ∑ { C n − q + e − c η n } = n B + o ( B ) ,
because q > 2 q>2 q > 2 and n B ≍ B n_B\asymp B n B ≍ B . Hence
lim sup α ↓ 0 E S τ α C K log ( 1 / α ) ≤ 1 Γ − 4 η . \limsup_{\alpha\downarrow0}\frac{\mathbb{E}_S\tau_\alpha^{\mathrm{CK}}}{\log(1/\alpha)}
\le\frac{1}{\Gamma-4\eta}. α ↓ 0 lim sup log ( 1/ α ) E S τ α CK ≤ Γ − 4 η 1 .
Let η ↓ 0 \eta\downarrow0 η ↓ 0 . The matching lower bound follows from Theorem 2.9 , since anytime validity implies P R S ( τ α C K < ∞ ) ≤ α \mathbb{P}_{R_S}(\tau_\alpha^{\mathrm{CK}}<\infty)\le\alpha P R S ( τ α CK < ∞ ) ≤ α and Corollary 2.8 implies τ α C K < ∞ \tau_\alpha^{\mathrm{CK}}<\infty τ α CK < ∞ S S S -almost surely.
Omitted proofs from Section 3
Proof of Lemma 3.1 . For any R ∈ P 0 R \in\mathcal{P}_0 R ∈ P 0 , the triangle inequality gives D T V ( S , R ) ≥ Δ ( S ) D_{\mathrm{TV}}(S,R) \ge\Delta(S) D TV ( S , R ) ≥ Δ ( S ) . Pinsker’s inequality therefore gives D K L ( S ∥ R ) ≥ 2 Δ ( S ) 2 D_{\mathrm{KL}}(S\|R) \ge2\Delta(S)^2 D KL ( S ∥ R ) ≥ 2Δ ( S ) 2 , proving the lower bound.
For the upper bound first suppose S S S has full support. Let a < 1 < b a < 1 < b a < 1 < b be the clipped-Kelly thresholds from Theorem 2.2 , and write
L = { i : S i / P i < a } , H = { i : S i / P i > b } , E S ( i ) = clip ( S i / P i , a , b ) , R S ( i ) = S i / E S ( i ) . L = \{i:S_i/P_i < a\}, \qquad H = \{i:S_i/P_i > b\}, \qquad E_S(i) = \operatorname{clip}(S_i/P_i,a,b), \qquad R_S(i) = S_i/E_S(i). L = { i : S i / P i < a } , H = { i : S i / P i > b } , E S ( i ) = clip ( S i / P i , a , b ) , R S ( i ) = S i / E S ( i ) .
The threshold equations imply
a = S ( L ) P ( L ) − ϵ 0 , b = S ( H ) P ( H ) + ϵ 0 , P ( L ) > ϵ 0 . a = \frac{S(L)}{P(L)-\epsilon_0}, \qquad b = \frac{S(H)}{P(H)+\epsilon_0}, \qquad P(L) > \epsilon_0. a = P ( L ) − ϵ 0 S ( L ) , b = P ( H ) + ϵ 0 S ( H ) , P ( L ) > ϵ 0 .
Every event discrepancy has absolute value at most ϵ 0 + Δ ( S ) \epsilon_0+\Delta(S) ϵ 0 + Δ ( S ) . Consequently,
1 − a ≤ Δ ( S ) P ( L ) − ϵ 0 ≤ Δ ( S ) η 0 , b − 1 ≤ Δ ( S ) P ( H ) + ϵ 0 ≤ Δ ( S ) ϵ 0 . 1-a \le\frac{\Delta(S)}{P(L)-\epsilon_0} \le\frac{\Delta(S)}{\eta_0}, \qquad b-1 \le\frac{\Delta(S)}{P(H)+\epsilon_0} \le\frac{\Delta(S)}{\epsilon_0}. 1 − a ≤ P ( L ) − ϵ 0 Δ ( S ) ≤ η 0 Δ ( S ) , b − 1 ≤ P ( H ) + ϵ 0 Δ ( S ) ≤ ϵ 0 Δ ( S ) .
Hence ∣ E S ( i ) − 1 ∣ ≤ Δ ( S ) / c 0 |E_S(i)-1| \le\Delta(S)/c_0 ∣ E S ( i ) − 1∣ ≤ Δ ( S ) / c 0 for every i i i . Since S i = R S ( i ) E S ( i ) S_i=R_S(i)E_S(i) S i = R S ( i ) E S ( i ) and both vectors sum to one,
Γ ( S ) = D K L ( S ∥ R S ) ≤ ∑ i ( S i − R S ( i ) ) 2 R S ( i ) = ∑ i R S ( i ) ( E S ( i ) − 1 ) 2 ≤ c 0 − 2 Δ ( S ) 2 . \Gamma(S)=D_{\mathrm{KL}}(S\|R_S) \le\sum_i \frac{(S_i-R_S(i))^2}{R_S(i)} = \sum_i R_S(i)(E_S(i)-1)^2 \le c_0^{-2}\Delta(S)^2. Γ ( S ) = D KL ( S ∥ R S ) ≤ i ∑ R S ( i ) ( S i − R S ( i ) ) 2 = i ∑ R S ( i ) ( E S ( i ) − 1 ) 2 ≤ c 0 − 2 Δ ( S ) 2 .
To extend the result to boundary alternatives, we verify continuity of Γ \Gamma Γ on the entire simplex. Compactness of P 0 \mathcal{P}_0 P 0 and joint lower semicontinuity of KL give lower semicontinuity. For upper semicontinuity at S S S , choose a minimizer R ∗ ∈ P 0 R^* \in\mathcal{P}_0 R ∗ ∈ P 0 and let R ρ = ( 1 − ρ ) R ∗ + ρ P R_\rho=(1-\rho)R^*+\rho P R ρ = ( 1 − ρ ) R ∗ + ρP for 0 < ρ < 1 0<\rho<1 0 < ρ < 1 . This is a strictly positive null vector. If S k → S S_k \to S S k → S , then
lim sup k Γ ( S k ) ≤ D K L ( S ∥ R ρ ) ≤ Γ ( S ) − log ( 1 − ρ ) . \limsup_k \Gamma(S_k) \le D_{\mathrm{KL}}(S\|R_\rho) \le\Gamma(S)-\log(1-\rho). k lim sup Γ ( S k ) ≤ D KL ( S ∥ R ρ ) ≤ Γ ( S ) − log ( 1 − ρ ) .
Letting ρ ↓ 0 \rho\downarrow0 ρ ↓ 0 proves continuity. Approximation by full-support alternatives completes the proof.
Proof of Theorem 3.2 . Validity. For any fixed event A A A , put q A = P ( A ) + ϵ 0 q_A=P(A)+\epsilon_0 q A = P ( A ) + ϵ 0 . If R ∈ P 0 R\in\mathcal{P}_0 R ∈ P 0 and λ ≥ 0 \lambda\ge0 λ ≥ 0 , Hoeffding’s lemma gives
E R exp { λ ( 1 { X ∈ A } − q A ) − λ 2 / 8 } ≤ 1 , \mathbb{E}_R\exp\{\lambda(\mathbf{1}\{X\in A\}-q_A)-\lambda^2/8\}\le1, E R exp { λ ( 1 { X ∈ A } − q A ) − λ 2 /8 } ≤ 1 ,
since R ( A ) ≤ q A R(A)\le q_A R ( A ) ≤ q A . The same inequality holds conditionally for predictable A A A and λ \lambda λ . Each W ( j ) W^{(j)} W ( j ) is constant before its block, uses predictable null-valid factors during the block, and is constant afterwards. Thus it is a test supermartingale. Conditional Tonelli applies to their nonnegative mixture. The mixture starts at one and is integrable because its expectation is at most one.
An accurate pilot gives a useful bet. Write Δ = Δ ( S ) > 0 \Delta=\Delta(S)>0 Δ = Δ ( S ) > 0 and let
G j = { D T V ( S ‾ m j , S ) ≤ Δ / 8 } . G_j=\{D_{\mathrm{TV}}(\overline{S}_{m_j},S)\le\Delta/8\}. G j = { D TV ( S m j , S ) ≤ Δ/8 } .
Using D T V ( S ‾ m , S ) = max A { S ‾ m ( A ) − S ( A ) } D_{\mathrm{TV}}(\overline{S}_m,S)=\max_A\{\overline{S}_m(A)-S(A)\} D TV ( S m , S ) = max A { S m ( A ) − S ( A )} , a union bound over 2 d 2^d 2 d events and one-sided Hoeffding give
P S ( G j c ) ≤ 2 d exp ( − m j Δ 2 / 32 ) . (49) \mathbb{P}_S(G_j^c)\le2^d\exp(-m_j\Delta^2/32). \tag*{(49)} P S ( G j c ) ≤ 2 d exp ( − m j Δ 2 /32 ) . (49)
This is only an analysis step: the algorithm does not enumerate events. On G j G_j G j ,
7 8 Δ ≤ Δ ^ j ≤ 9 8 Δ , S ( A ^ j ) − q j ≥ Δ ^ j − 1 8 Δ . \frac{7}{8}\Delta\le\widehat{\Delta}_j \le\frac{9}{8}\Delta,\qquad S(\widehat{A}_j)-q_j \ge\widehat{\Delta}_j-\frac{1}{8}\Delta. 8 7 Δ ≤ Δ j ≤ 8 9 Δ , S ( A j ) − q j ≥ Δ j − 8 1 Δ.
In particular, conditional on the pilot, the mean log increment in the next block satisfies
μ j = 4 Δ ^ j ( S ( A ^ j ) − q j ) − 2 Δ ^ j 2 \mu_j=4\widehat{\Delta}_j\bigl(S(\widehat{A}_j)-q_j\bigr)-2\widehat{\Delta}_j^2 μ j = 4 Δ j ( S ( A j ) − q j ) − 2 Δ j 2
≥ 2 Δ ^ j ( Δ ^ j − Δ / 4 ) ≥ 35 32 Δ 2 ≥ Δ 2 , λ j ≤ 9 2 Δ . \ge2\widehat{\Delta}_j(\widehat{\Delta}_j-\Delta/4)\ge\frac{35}{32}\Delta^2\ge\Delta^2,\qquad\lambda_j\le\frac{9}{2}\Delta. ≥ 2 Δ j ( Δ j − Δ/4 ) ≥ 32 35 Δ 2 ≥ Δ 2 , λ j ≤ 2 9 Δ.
The log increment has range length λ j \lambda_j λ j . Independence of the next block and the pilot, followed by Hoeffding’s inequality, gives on G j G_j G j
P S ( log W 2 m j ( j ) < 1 2 m j Δ 2 ∣ F m j ) ≤ exp ( − m j Δ 4 2 λ j 2 ) ≤ exp ( − m j Δ 2 / 41 ) . \mathbb{P}_S\left(\log W_{2m_j}^{(j)}<\frac{1}{2}m_j\Delta^2\mathrel{\big|}\mathcal{F}_{m_j}\right)\le\exp\left(-\frac{m_j\Delta^4}{2\lambda_j^2}\right)\le\exp(-m_j\Delta^2/41). P S ( log W 2 m j ( j ) < 2 1 m j Δ 2 F m j ) ≤ exp ( − 2 λ j 2 m j Δ 4 ) ≤ exp ( − m j Δ 2 /41 ) .
Combining with (49) ,
P S ( log W 2 m j ( j ) < 1 2 m j Δ 2 ) ≤ ( 2 d + 1 ) exp ( − m j Δ 2 / 41 ) . (50) \mathbb{P}_S\left(\log W_{2m_j}^{(j)}<\frac{1}{2}m_j\Delta^2\right)\le(2^d+1)\exp(-m_j\Delta^2/41). \tag*{(50)} P S ( log W 2 m j ( j ) < 2 1 m j Δ 2 ) ≤ ( 2 d + 1 ) exp ( − m j Δ 2 /41 ) . (50)
Control the entire stopping-time tail. Let κ j = log ( ( j + 1 ) ( j + 2 ) / α ) \kappa_j=\log((j+1)(j+2)/\alpha) κ j = log (( j + 1 ) ( j + 2 ) / α ) and let j ∗ j_* j ∗ be the first nonnegative integer with
2 j ∗ Δ 2 ≥ max { 2 κ j ∗ , 41 [ log ( 2 d + 1 ) + 2 ] } . (51) 2^{j_*}\Delta^2\ge\max\{2\kappa_{j_*},\,41[\log(2^d+1)+2]\}. \tag*{(51)} 2 j ∗ Δ 2 ≥ max { 2 κ j ∗ , 41 [ log ( 2 d + 1 ) + 2 ]} . (51)
Such an integer exists. If m j Δ 2 / 2 ≥ κ j m_j\Delta^2/2\ge\kappa_j m j Δ 2 /2 ≥ κ j , then M 2 m j F ≥ w j W 2 m j ( j ) M_{2m_j}^{\mathrm{F}}\ge w_jW_{2m_j}^{(j)} M 2 m j F ≥ w j W 2 m j ( j ) and (50) imply
P S ( τ α ( M F ) > 2 m j ) ≤ ( 2 d + 1 ) exp ( − m j Δ 2 / 41 ) . \mathbb{P}_S(\tau_\alpha(M^{\mathrm{F}})>2m_j)\le(2^d+1)\exp(-m_j\Delta^2/41). P S ( τ α ( M F ) > 2 m j ) ≤ ( 2 d + 1 ) exp ( − m j Δ 2 /41 ) .
Both conditions in (51) persist at subsequent dyadic times: the left side doubles, whereas κ j + 1 − κ j = log ( ( j + 3 ) / ( j + 1 ) ) ≤ log 3 \kappa_{j+1}-\kappa_j=\log((j+3)/(j+1))\le\log3 κ j + 1 − κ j = log (( j + 3 ) / ( j + 1 )) ≤ log 3 .
Put m = 2 j ∗ m=2^{j_*} m = 2 j ∗ , B d = 2 d + 1 B_d=2^d+1 B d = 2 d + 1 , and t = m Δ 2 / 41 ≥ log B d + 2 t=m\Delta^2/41\ge\log B_d+2 t = m Δ 2 /41 ≥ log B d + 2 . Summing the hitting-time tail over dyadic intervals yields
E S τ α ( M F ) ≤ 2 m + 2 m ∑ r ≥ 0 2 r P S ( τ α ( M F ) > 2 m 2 r ) \mathbb{E}_S\tau_\alpha(M^{\mathrm{F}})\le2m+2m\sum_{r\ge0}2^r\mathbb{P}_S(\tau_\alpha(M^{\mathrm{F}})>2m2^r) E S τ α ( M F ) ≤ 2 m + 2 m r ≥ 0 ∑ 2 r P S ( τ α ( M F ) > 2 m 2 r )
≤ 2 m + 2 m B d ∑ r ≥ 0 2 r e − t 2 r ≤ 2 m + 4 m B d e − t < 3 m . \le2m+2mB_d\sum_{r\ge0}2^r e^{-t2^r}\le2m+4mB_de^{-t}<3m. ≤ 2 m + 2 m B d r ≥ 0 ∑ 2 r e − t 2 r ≤ 2 m + 4 m B d e − t < 3 m .
For the penultimate inequality, use 2 r ≥ r + 1 2^r\ge r+1 2 r ≥ r + 1 and t ≥ 2 t\ge2 t ≥ 2 to bound the series by e − t / ( 1 − 2 e − t ) ≤ 2 e − t e^{-t}/(1-2e^{-t})\le2e^{-t} e − t / ( 1 − 2 e − t ) ≤ 2 e − t .
Solve for the epoch and convert to information. Set u = log ( 1 / Δ 2 ) ≥ 0 u=\log(1/\Delta^2)\ge0 u = log ( 1/ Δ 2 ) ≥ 0 and
H = d + log ( 1 / α ) + log ( e + u ) ≥ 3. H=d+\log(1/\alpha)+\log(e+u)\ge3. H = d + log ( 1/ α ) + log ( e + u ) ≥ 3.
Choose 2 j 2^j 2 j to be the first dyadic integer at least 256 H / Δ 2 256H/\Delta^2 256 H / Δ 2 . Then 2 j < 512 H / Δ 2 2^j<512H/\Delta^2 2 j < 512 H / Δ 2 and
j + 2 ≤ 11 + u + log H log 2 ≤ 8 H ( e + u ) , log ( j + 2 ) ≤ 3 H . j+2\le11+\frac{u+\log H}{\log2}\le8H(e+u),\qquad\log(j+2)\le3H. j + 2 ≤ 11 + log 2 u + log H ≤ 8 H ( e + u ) , log ( j + 2 ) ≤ 3 H .
It follows that 2 κ j ≤ 14 H 2\kappa_j\le14H 2 κ j ≤ 14 H , while 41 [ log ( 2 d + 1 ) + 2 ] ≤ 100 d ≤ 100 H 41[\log(2^d+1)+2]\le100d\le100H 41 [ log ( 2 d + 1 ) + 2 ] ≤ 100 d ≤ 100 H . Thus this j j j satisfies (51) , and
E S τ α ( M F ) ≤ 3 ⋅ 2 j ∗ < 1536 H / Δ 2 . \mathbb{E}_S\tau_\alpha(M^{\mathrm{F}})\le3\cdot2^{j_*}<1536H/\Delta^2. E S τ α ( M F ) ≤ 3 ⋅ 2 j ∗ < 1536 H / Δ 2 .
This is (28) . By Lemma 3.1 ,
Δ − 2 ≤ c 0 − 2 Γ ( S ) − 1 , log ( 1 / Δ 2 ) ≤ log ( 1 / Γ ( S ) ) + log ( c 0 − 2 ) . \Delta^{-2} \le c_0^{-2}\Gamma(S)^{-1}, \qquad\log(1/\Delta^2) \le\log(1/\Gamma(S))+\log(c_0^{-2}). Δ − 2 ≤ c 0 − 2 Γ ( S ) − 1 , log ( 1/ Δ 2 ) ≤ log ( 1/Γ ( S )) + log ( c 0 − 2 ) .
For Γ ( S ) ≤ 1 \Gamma(S) \le1 Γ ( S ) ≤ 1 , the last fixed additive constant changes ℓ ( Γ ( S ) ) \ell(\Gamma(S)) ℓ ( Γ ( S )) by at most a constant depending on c 0 c_0 c 0 . Absorbing it proves (29) .
Finally, (50) is summable in j j j . By Borel–Cantelli, all sufficiently large frozen accounts have W 2 m j ( j ) ≥ exp ( m j Δ 2 / 2 ) W_{2m_j}^{(j)} \ge\exp(m_j\Delta^2/2) W 2 m j ( j ) ≥ exp ( m j Δ 2 /2 ) almost surely. Their weighted frozen contributions tend to infinity and are retained forever. The other contributions are nonnegative, so M n F → ∞ M_n^{\mathrm{F}} \to\infty M n F → ∞ almost surely.
Proof of Corollary 3.3 . Mixtures preserve the test-supermartingale property. Also,
τ α ( M m i x ) ≤ τ α / 2 ( M C K ) ∧ τ α / 2 ( M F ) \tau_\alpha(M^{\mathrm{mix}}) \le\tau_{\alpha/2}(M^{\mathrm{CK}}) \wedge\tau_{\alpha/2}(M^{\mathrm{F}}) τ α ( M mix ) ≤ τ α /2 ( M CK ) ∧ τ α /2 ( M F )
pathwise.
Theorem 3.2 proves power one and (32) . For a fixed full-support S S S , Theorem 2.10 and log ( 2 / α ) ∼ log ( 1 / α ) \log(2/\alpha) \sim\log(1/\alpha) log ( 2/ α ) ∼ log ( 1/ α ) give the Wald upper bound. The information lower bound applies to this valid, power-one test and gives E S τ α ( M m i x ) ≥ log ( 1 / α ) / Γ ( S ) \mathbb{E}_S\tau_\alpha(M^{\mathrm{mix}}) \ge\log(1/\alpha)/\Gamma(S) E S τ α ( M mix ) ≥ log ( 1/ α ) /Γ ( S ) , proving (31) .
For regret, M n m i x ≥ M n C K / 2 M_n^{\mathrm{mix}} \ge M_n^{\mathrm{CK}}/2 M n mix ≥ M n CK /2 gives the upper bound in (33) . To prove the lower bound, let L n = ∏ t = 1 n S ( X t ) / R S ( X t ) L_n = \prod_{t=1}^{n} S(X_t)/R_S(X_t) L n = ∏ t = 1 n S ( X t ) / R S ( X t ) . Validity under R S R_S R S and Jensen’s inequality give
E S log M n m i x = n Γ ( S ) + E S log ( M n m i x / L n ) ≤ n Γ ( S ) + log E R S M n m i x ≤ n Γ ( S ) . \mathbb{E}_S \log M_n^{\mathrm{mix}} = n\Gamma(S) + \mathbb{E}_S \log(M_n^{\mathrm{mix}}/L_n) \le n\Gamma(S) + \log\mathbb{E}_{R_S}M_n^{\mathrm{mix}} \le n\Gamma(S). E S log M n mix = n Γ ( S ) + E S log ( M n mix / L n ) ≤ n Γ ( S ) + log E R S M n mix ≤ n Γ ( S ) .
The nonnegativity statement here is for expected regret. The original nonnegative pathwise regret need not transfer to an arbitrary mixture.
Omitted Proofs from Section 4
Proof of Proposition 4.1 . At the lower root the active set is a prefix, so
a P j p r e − U j p r e = a ϵ 0 . aP_j^{\mathrm{pre}} - U_j^{\mathrm{pre}} = a\epsilon_0. a P j pre − U j pre = a ϵ 0 .
The displayed formula follows, and the interval condition is exactly self-consistency of that prefix. The upper active set is a suffix, giving
U j s u f − b P j s u f = b ϵ 0 . U_j^{\mathrm{suf}} - bP_j^{\mathrm{suf}} = b\epsilon_0. U j suf − b P j suf = b ϵ 0 .
Coordinates at a threshold contribute zero to its defining equation, so including or excluding them does not change the result. After sorting, the cumulative sums and a scan identify both thresholds in O ( d ) O(d) O ( d ) time. Sorting therefore dominates the computational cost.
Proof of Lemma 4.2 . Substitute U ^ t , i = P i z i ( t ) / C t \widehat{U}_{t,i} = P_i z_i(t)/C_t U t , i = P i z i ( t ) / C t into (10) –(11) and multiply by C t C_t C t . This gives F t ( A t ) = G t ( B t ) = 0 F_t(A_t) = G_t(B_t) = 0 F t ( A t ) = G t ( B t ) = 0 , and uniqueness follows from the corresponding oracle threshold equations. Equation (37) follows by positive homogeneity of clipping.
Proof of Lemma 4.3 . The crossing inequalities ensure that v v v exists and has a predecessor. The positive root is v v v if equality holds; otherwise it lies strictly between the predecessor of v v v and v v v . On that interval the active lower set is exactly { i : z i ( t ) < v } \{i : z_i(t) < v\} { i : z i ( t ) < v } , so
F t ( x ) = x { P t ≤ ( v ) − ϵ 0 } − S t ≤ ( v ) . F_t(x) = x\{P_t^{\le}(v)-\epsilon_0\}-S_t^{\le}(v). F t ( x ) = x { P t ≤ ( v ) − ϵ 0 } − S t ≤ ( v ) .
Because the function crosses from negative to positive on this interval, P t < ( v ) − ϵ 0 > 0 P_t^{<}(v)-\epsilon_0>0 P t < ( v ) − ϵ 0 > 0 , and solving F t ( x ) = 0 F_t(x)=0 F t ( x ) = 0 gives the formula.
For the search, carry running prefix totals ( p 0 , s 0 ) (p_0,s_0) ( p 0 , s 0 ) for all keys preceding the current subtree, initially ( 0 , 0 ) (0,0) ( 0 , 0 ) . At a node with key w w w and left subtree L \mathcal{L} L , compute
p = p 0 + P ( L ) , s = s 0 + S ( L ) . p=p_0+P(\mathcal{L}),\qquad s=s_0+S(\mathcal{L}). p = p 0 + P ( L ) , s = s 0 + S ( L ) .
These are P t < ( w ) P_t^{<}(w) P t < ( w ) and S t < ( w ) S_t^{<}(w) S t < ( w ) , so F t ( w ) = w ( p − ϵ 0 ) − s F_t(w)=w(p-\epsilon_0)-s F t ( w ) = w ( p − ϵ 0 ) − s is evaluated in constant time. If it is nonnegative, retain the node and its prefix totals as a candidate and descend left. Otherwise, replace ( p 0 , s 0 ) (p_0,s_0) ( p 0 , s 0 ) by ( p + p w , s + s w ) (p+p_w,s+s_w) ( p + p w , s + s w ) and descend right. Empty subtrees have zero aggregates. The last retained candidate is the smallest satisfying key, and its saved totals give the threshold in constant additional time. The descent visits O ( log d ) O(\log d) O ( log d ) nodes.
Proof of Lemma 4.4 . The crossing inequalities again ensure that v v v exists and has a predecessor. If G t ( v ) < 0 G_t(v)<0 G t ( v ) < 0 , the root lies strictly between the predecessor of v v v and v v v . Throughout that interval the active upper set is exactly { i : z i ( t ) ≥ v } \{i:z_i(t)\ge v\} { i : z i ( t ) ≥ v } , including the entire group at v v v . Hence
G t ( x ) = S t ≥ ( v ) − x { P t ≥ ( v ) + ϵ 0 } . G_t(x)=S_t^{\ge}(v)-x\{P_t^{\ge}(v)+\epsilon_0\}. G t ( x ) = S t ≥ ( v ) − x { P t ≥ ( v ) + ϵ 0 } .
and solving G t ( x ) = 0 G_t(x)=0 G t ( x ) = 0 gives the formula.
Use the same running-prefix descent as in the lower query. At a node with key w w w and prefix totals p = P t < ( w ) p=P_t^{<}(w) p = P t < ( w ) , s = S t < ( w ) s=S_t^{<}(w) s = S t < ( w ) , evaluate
G t ( w ) = C t − s − w ( 1 − p + ϵ 0 ) . G_t(w)=C_t-s-w(1-p+\epsilon_0). G t ( w ) = C t − s − w ( 1 − p + ϵ 0 ) .
This identity follows because the suffix including the node at w w w has mass 1 − p 1-p 1 − p and count sum C t − s C_t-s C t − s , and the group at w w w contributes zero to G t ( w ) G_t(w) G t ( w ) . Retain the node and descend left when G t ( w ) ≤ 0 G_t(w)\le0 G t ( w ) ≤ 0 ; otherwise update the prefix totals and descend right. At the selected key, the saved totals give
P t ≥ ( v ) = 1 − P t < ( v ) , S t ≥ ( v ) = C t − S t < ( v ) . P_t^{\ge}(v)=1-P_t^{<}(v),\qquad S_t^{\ge}(v)=C_t-S_t^{<}(v). P t ≥ ( v ) = 1 − P t < ( v ) , S t ≥ ( v ) = C t − S t < ( v ) .
Thus each visited node requires constant work, and the entire query takes O ( log d ) O(\log d) O ( log d ) time.
Proof of Theorem 4.5 . We first specify the state maintained by the algorithm, verify that initialization and each observation update preserve it, and then deduce the claimed complexity and pathwise equality.
Maintained state and initialization. Immediately before observing X t + 1 X_{t+1} X t + 1 , the algorithm maintains the following invariant:
The category arrays and the stored total contain the exact values
c i ( t ) = N i ( t ) + α i , z i ( t ) = c i ( t ) P i , C t = ∑ i = 1 d c i ( t ) = t + α + . c_i(t)=N_i(t)+\alpha_i,\qquad z_i(t)=\frac{c_i(t)}{P_i},\qquad C_t=\sum_{i=1}^{d}c_i(t)=t+\alpha_+. c i ( t ) = N i ( t ) + α i , z i ( t ) = P i c i ( t ) , C t = i = 1 ∑ d c i ( t ) = t + α + .
The balanced tree has one node for each distinct key z i ( t ) z_i(t) z i ( t ) , with ties grouped together. All group totals, group cardinalities, and subtree aggregates are correct.
The stored indicator correctly records whether U ^ t ∈ P 0 \widehat{U}_t\in\mathcal{P}_0 U t ∈ P 0 . Whenever U ^ t ∉ P 0 \widehat{U}_t\notin\mathcal{P}_0 U t ∈ / P 0 , the stored values A t , B t A_t,B_t A t , B t are exactly its scaled oracle thresholds.
At t = 0 t=0 t = 0 , set c i ( 0 ) = α i c_i(0)=\alpha_i c i ( 0 ) = α i , z i ( 0 ) = α i / P i z_i(0)=\alpha_i/P_i z i ( 0 ) = α i / P i , and C 0 = α + C_0=\alpha_+ C 0 = α + . Sorting the initial keys, grouping ties, and building the augmented balanced tree establishes the first two parts of the invariant. Equation (41) determines null-ball membership exactly. If the initial predictor is outside the null ball, Lemmas 4.3 and 4.4 return its exact scaled oracle thresholds. Thus the invariant holds at t = 0 t=0 t = 0 .
Forming the initial keys takes O ( d ) O(d) O ( d ) time, sorting takes O ( d log d ) O(d\log d) O ( d log d ) time, and grouping ties and building the tree with its subtree aggregates take O ( d ) O(d) O ( d ) time. The membership query and, when required, the two threshold queries take O ( log d ) O(\log d) O ( log d ) time altogether. Hence initialization costs O ( d log d ) O(d\log d) O ( d log d ) .
One observation update. Suppose the invariant holds at time t t t , and let X t + 1 = k X_{t+1}=k X t + 1 = k . Using the current stored state, the algorithm first evaluates
e t + 1 = { 1 , U ^ t ∈ P 0 , clip ( z k ( t ) , A t , B t ) C t , U ^ t ∉ P 0 . e_{t+1}=
\begin{cases}
1, & \widehat{U}_t\in\mathcal{P}_0,\\
\dfrac{\operatorname{clip}(z_k(t),A_t,B_t)}{C_t}, & \widehat{U}_t\notin\mathcal{P}_0.
\end{cases} e t + 1 = ⎩ ⎨ ⎧ 1 , C t clip ( z k ( t ) , A t , B t ) , U t ∈ P 0 , U t ∈ / P 0 .
By the invariant and (37) , e t + 1 = E U ^ t ( k ) e_{t+1}=E_{\widehat{U}_t}(k) e t + 1 = E U t ( k ) . Reading z k ( t ) z_k(t) z k ( t ) from the category array and applying the stored thresholds require only a fixed number of arithmetic operations and comparisons. Thus factor evaluation costs O ( 1 ) O(1) O ( 1 ) . The algorithm updates the wealth by
M t + 1 d y n = M t d y n e t + 1 M_{t+1}^{\mathrm{dyn}}=M_t^{\mathrm{dyn}}e_{t+1} M t + 1 dyn = M t dyn e t + 1
before incorporating the new observation into the predictor.
It then removes category k k k ’s old contribution from the node at z k ( t ) z_k(t) z k ( t ) , updates
c k ( t + 1 ) = c k ( t ) + 1 , z k ( t + 1 ) = z k ( t ) + 1 P k , C t + 1 = C t + 1 , c_k(t+1)=c_k(t)+1,\qquad z_k(t+1)=z_k(t)+\frac{1}{P_k},\qquad C_{t+1}=C_t+1, c k ( t + 1 ) = c k ( t ) + 1 , z k ( t + 1 ) = z k ( t ) + P k 1 , C t + 1 = C t + 1 ,
and inserts the updated contribution at z k ( t + 1 ) z_k(t+1) z k ( t + 1 ) . No other category count or key changes. After repairing the affected group totals and subtree aggregates, the arrays and tree therefore represent exactly the predictor U ^ t + 1 \widehat{U}_{t+1} U t + 1 .
Each removal or insertion takes O ( log d ) O(\log d) O ( log d ) worst-case time. Indeed, locating the relevant group and performing any necessary node insertion, deletion, or rebalancing involve only O ( log d ) O(\log d) O ( log d ) nodes. Once a group is located, its totals and cardinality are changed in constant time. At each affected node, the subtree aggregates are recomputed from its group totals and the two child-subtree aggregates, also in constant time. Thus maintaining the augmentation does not increase the asymptotic cost of the balanced-tree operations.
Finally, the algorithm applies (41) to determine membership for U ^ t + 1 \widehat{U}_{t+1} U t + 1 . If this predictor is outside the null ball, it uses Lemmas 4.3 and 4.4 to obtain its exact scaled oracle thresholds; otherwise it records that the next factor is identically one. This establishes the invariant at time t + 1 t+1 t + 1 . These queries require at most three further tree descents, each costing O ( log d ) O(\log d) O ( log d ) .
Consequently, a complete observation update consists of constant work, one removal, one insertion, and a constant number of logarithmic-time queries. Its total worst-case cost is therefore O ( log d ) O(\log d) O ( log d ) .
The induction above shows that, on every round t + 1 t+1 t + 1 , the dynamic implementation applies exactly E U ^ t ( X t + 1 ) E_{\widehat{U}_t}(X_{t+1}) E U t ( X t + 1 ) , with U ^ t \widehat{U}_t U t computed from the first t t t observations. Therefore, for every observation sequence,
M n d y n = ∏ t = 0 n − 1 E U ^ t ( X t + 1 ) = M n C K . M_n^{\mathrm{dyn}}=\prod_{t=0}^{n-1}E_{\widehat{U}_t}(X_{t+1})=M_n^{\mathrm{CK}}. M n dyn = t = 0 ∏ n − 1 E U t ( X t + 1 ) = M n CK .
where the empty product equals one. This proves the claimed identity for every n ≥ 0 n \ge0 n ≥ 0 .
Storage and total cost. Each tree node represents a nonempty group of categories, so there are at most d d d nodes. Each node stores a constant number of fields, and the category arrays contain O ( d ) O(d) O ( d ) entries. The global state requires constant storage, and any traversal stack requires at most O ( log d ) O(\log d) O ( log d ) additional words. Hence the total storage is O ( d ) O(d) O ( d ) words.
Combining the O ( d log d ) O(d \log d) O ( d log d ) initialization cost with the O ( log d ) O(\log d) O ( log d ) worst-case cost of each of the n n n observation updates gives
O ( d log d + n log d ) , O(d \log d + n \log d), O ( d log d + n log d ) ,
as claimed.
Proof of Proposition 4.6. Maintain the global counts and the raw-count keys
v i ( n ) = N i ( n ) P i . v_i(n) = \frac{N_i(n)}{P_i}. v i ( n ) = P i N i ( n ) .
Only the observed category changes its key, by 1 / P i 1/P_i 1/ P i . As in the dynamic implementation in § 4 , use an augmented balanced search tree, grouping equal keys. Store the group and subtree sums of P i P_i P i and N i ( n ) N_i(n) N i ( n ) , together with group cardinalities. The all-zero initial keys form one group, so initialization costs O ( d ) O(d) O ( d ) . One removal and insertion maintain the tree in O ( log d ) O(\log d) O ( log d ) worst-case time per observation.
At time m = m j m=m_j m = m j , one strict suffix query gives
p j = ∑ v i ( m ) > m P i = P ( A ^ j ) , s j = ∑ v i ( m ) > m N i ( m ) = m S ‾ m ( A ^ j ) . p_j = \sum_{v_i(m)>m} P_i = P(\widehat{A}_j), \qquad s_j = \sum_{v_i(m)>m} N_i(m) = m\overline{S}_m(\widehat{A}_j). p j = v i ( m ) > m ∑ P i = P ( A j ) , s j = v i ( m ) > m ∑ N i ( m ) = m S m ( A j ) .
Consequently q j = p j + ϵ 0 q_j=p_j+\epsilon_0 q j = p j + ϵ 0 and
Δ ^ j = ( s j / m − p j − ϵ 0 ) + . \widehat{\Delta}_j = (s_j/m-p_j-\epsilon_0)_+. Δ j = ( s j / m − p j − ϵ 0 ) + .
No category list is needed for this query.
For membership during a betting block, maintain arrays stamp [ i ] \operatorname{stamp}[i] stamp [ i ] and bit [ i ] \operatorname{bit}[i] bit [ i ] , initializing every stamp to − 1 -1 − 1 . The first observation fills the first pilot, after which account zero is selected. The current block identifier is j j j . On observing category i i i at time t ∈ { m j + 1 , … , 2 m j } t \in\{m_j+1,\ldots,2m_j\} t ∈ { m j + 1 , … , 2 m j } , before incrementing its count , do the following:
If stamp [ i ] ≠ j \operatorname{stamp}[i] \ne j stamp [ i ] = j , set bit [ i ] = 1 { N i ( t − 1 ) > m j P i } \operatorname{bit}[i] = 1\{N_i(t-1)>m_jP_i\} bit [ i ] = 1 { N i ( t − 1 ) > m j P i } and stamp [ i ] = j \operatorname{stamp}[i]=j stamp [ i ] = j .
Use bit [ i ] \operatorname{bit}[i] bit [ i ] to update the current account.
Increment N i N_i N i and repair its tree entry.
At the first appearance of i i i in the block, it has not been observed since the pilot ended. Therefore N i ( t − 1 ) = N i ( m j ) N_i(t-1)=N_i(m_j) N i ( t − 1 ) = N i ( m j ) , so the stored bit equals 1 { i ∈ A ^ j } 1\{i\in\widehat{A}_j\} 1 { i ∈ A j } . Later appearances reuse that exact bit. At a new block, incrementing the identifier invalidates all old bits without clearing the arrays.
At a dyadic endpoint, first finish and freeze the old account, then select the next bet from the updated counts. One suffix query initializes the new account. Thus an observation requires constant account work, one logarithmic-time tree update, and at most one logarithmic-time query. Arrays and tree use O ( d ) O(d) O ( d ) memory. Equation (??) evaluates the mixture in constant time from the account state.
For the combined process, retain a separate tree for the smoothed keys used by clipped Kelly. Evaluate both betting factors from their pre-observation states, increment the shared counts once, and update both trees. At a dyadic endpoint, select the next learned event only after this update. The two trees have O ( d ) O(d) O ( d ) total storage and each requires only a constant number of logarithmic-time operations per observation. Including the clipped-Kelly initialization in Theorem 4.5 gives total work O ( d log d + n log d ) O(d \log d + n \log d) O ( d log d + n log d ) through time n n n . These counts include unit-cost exponential evaluations for the account factors. They make no bit-complexity or floating-point certification claim.
Verification of the Farrell lower bound
Choose a category i i i with ϵ 0 < 1 − P i \epsilon_0 < 1 - P_i ϵ 0 < 1 − P i , and put q = P i + ϵ 0 ∈ ( 0 , 1 ) q = P_i + \epsilon_0 \in(0,1) q = P i + ϵ 0 ∈ ( 0 , 1 ) . Define the full-support boundary null
R i 0 = q , R ℓ 0 = P ℓ 1 − q 1 − P i ( ℓ ≠ i ) . R_i^0 = q,\qquad R_\ell^0 = P_\ell\frac{1-q}{1-P_i}\quad(\ell\ne i). R i 0 = q , R ℓ 0 = P ℓ 1 − P i 1 − q ( ℓ = i ) .
For 0 < δ < 1 − q 0 < \delta< 1-q 0 < δ < 1 − q , set
S i δ = q + δ , S ℓ δ = R ℓ 0 1 − q − δ 1 − q ( ℓ ≠ i ) . S_i^\delta= q+\delta,\qquad S_\ell^\delta= R_\ell^0 \frac{1-q-\delta}{1-q}\quad(\ell\ne i). S i δ = q + δ , S ℓ δ = R ℓ 0 1 − q 1 − q − δ ( ℓ = i ) .
Then D T V ( R 0 , P ) = ϵ 0 D_{\mathrm{TV}}(R^0,P)=\epsilon_0 D TV ( R 0 , P ) = ϵ 0 and D T V ( S δ , P ) = ϵ 0 + δ D_{\mathrm{TV}}(S^\delta,P)=\epsilon_0+\delta D TV ( S δ , P ) = ϵ 0 + δ . Every null has R i ≤ q R_i\le q R i ≤ q , so data processing gives
Γ ( S δ ) ≥ inf r ≤ q kl ( q + δ , r ) = kl ( q + δ , q ) . \Gamma(S^\delta)\ge\inf_{r\le q}\operatorname{kl}(q+\delta,r)=\operatorname{kl}(q+\delta,q). Γ ( S δ ) ≥ r ≤ q inf kl ( q + δ , r ) = kl ( q + δ , q ) .
The conditional distributions on X ∖ { i } \mathcal{X}\setminus\{i\} X ∖ { i } agree under S δ S^\delta S δ and R 0 R^0 R 0 . Therefore
Γ ( S δ ) = D K L ( S δ ∥ R 0 ) = kl ( q + δ , q ) ∼ δ 2 2 q ( 1 − q ) . (52) \Gamma(S^\delta)=D_{\mathrm{KL}}(S^\delta\mathbin\Vert R^0)=\operatorname{kl}(q+\delta,q)\sim\frac{\delta^2}{2q(1-q)}. \tag*{(52)} Γ ( S δ ) = D KL ( S δ ∥ R 0 ) = kl ( q + δ , q ) ∼ 2 q ( 1 − q ) δ 2 . (52)
Choose a sufficiently small fixed a > 0 a>0 a > 0 , and then δ k ↓ 0 \delta_k\downarrow0 δ k ↓ 0 with Γ ( S δ k ) = a e − ( 2 k + 1 ) \Gamma(S^{\delta_k})=ae^{-(2k+1)} Γ ( S δ k ) = a e − ( 2 k + 1 ) . This is a direct sequence with anchor R 0 R^0 R 0 and comparison constant one, in the terminology of [1 Section 3.2] . That section explicitly permits fixed rescalings of the geometric buckets. Its lower bound implies a positive limsup of Γ ( S δ k ) E S δ k τ / ℓ ( Γ ( S δ k ) ) \Gamma(S^{\delta_k})\mathbb{E}_{S^{\delta_k}}\tau/\ell(\Gamma(S^{\delta_k})) Γ ( S δ k ) E S δ k τ / ℓ ( Γ ( S δ k )) for every level-α \alpha α , power-one test, with α < 1 / 2 \alpha<1/2 α < 1/2 . This proves (34) . The statement is sequence-wise; it supplies no universal lower bound at every isolated S S S .
Mixture over pointwise oracles
For completeness, we collect here the oracle-mixture construction and its regret guarantees. These results are not needed for the main predictable plug-in procedure. This is an alternative method, which is computationally
Let A ⊂ Δ d ∖ P 0 \mathcal{A}\subset\Delta_d\setminus\mathcal{P}_0 A ⊂ Δ d ∖ P 0 be compact, contained in some K m , δ \mathcal{K}_{m,\delta} K m , δ , and let Π \Pi Π be a probability measure with full support on A \mathcal{A} A . Define the oracle mixture
B n Π : = ∫ A ∏ t = 1 n E U ( X t ) Π ( d u ) . (53) B_n^\Pi:=\int_{\mathcal{A}}\prod_{t=1}^{n}E_U(X_t)\,\Pi(\mathrm{d}u). \tag*{(53)} B n Π := ∫ A t = 1 ∏ n E U ( X t ) Π ( d u ) . (53)
Theorem B.1 (Finite-sample regret of the oracle mixture). The process ( B n Π ) (B_n^\Pi) ( B n Π ) is a test supermartingale under the conditionally varying null. Fix a full-support S ∈ A S\in\mathcal{A} S ∈ A . For every measurable V ⊆ A V\subseteq\mathcal{A} V ⊆ A with Π ( V ) > 0 \Pi(V)>0 Π ( V ) > 0 ,
0 ≤ n Γ ( S ) − E S log B n Π ≤ log 1 Π ( V ) + n sup U ∈ V { Γ ( S ) − h ( S , U ) } ≤ log 1 Π ( V ) + n sup U ∈ V D K L ( S ∥ U ) . (54) 0\le n\Gamma(S)-\mathbb{E}_S\log B_n^\Pi
\le\log\frac{1}{\Pi(V)}+n\sup_{U\in V}\{\Gamma(S)-h(S,U)\}
\le\log\frac{1}{\Pi(V)}+n\sup_{U\in V}D_{\mathrm{KL}}(S\mathbin\Vert U). \tag*{(54)} 0 ≤ n Γ ( S ) − E S log B n Π ≤ log Π ( V ) 1 + n U ∈ V sup { Γ ( S ) − h ( S , U )} ≤ log Π ( V ) 1 + n U ∈ V sup D KL ( S ∥ U ) . (54)
Proof. Each fixed-U U U product is a valid test supermartingale, so Tonelli’s theorem proves validity of the mixture. B n Π B_n^{\Pi} B n Π is a valid horizon-n n n e-variable under R S n R_S^n R S n . Set
L n = ∏ t = 1 n S ( X t ) R S ( X t ) . L_n=\prod_{t=1}^{n}\frac{S(X_t)}{R_S(X_t)}. L n = t = 1 ∏ n R S ( X t ) S ( X t ) .
Full support and Jensen’s inequality give
E S log B n Π = n Γ ( S ) + E S log B n Π L n ≤ n Γ ( S ) + log E R S ⊗ n B n Π ≤ n Γ ( S ) . \mathbb{E}_S\log B_n^{\Pi}=n\Gamma(S)+\mathbb{E}_S\log\frac{B_n^{\Pi}}{L_n}
\le n\Gamma(S)+\log\mathbb{E}_{R_S^{\otimes n}}B_n^{\Pi}
\le n\Gamma(S). E S log B n Π = n Γ ( S ) + E S log L n B n Π ≤ n Γ ( S ) + log E R S ⊗ n B n Π ≤ n Γ ( S ) .
Let Π V \Pi_V Π V be Π \Pi Π conditioned on V V V . Pathwise, Jensen’s inequality for the concave logarithm gives
log B n Π ≥ log Π ( V ) + log ∫ V ∏ t = 1 n E U ( X t ) Π V ( d u ) ≥ log Π ( V ) + ∫ V ∑ t = 1 n log E U ( X t ) Π V ( d u ) . \log B_n^{\Pi}\ge\log\Pi(V)+\log\int_V\prod_{t=1}^{n}E_U(X_t)\,\Pi_V(du)
\ge\log\Pi(V)+\int_V\sum_{t=1}^{n}\log E_U(X_t)\,\Pi_V(du). log B n Π ≥ log Π ( V ) + log ∫ V t = 1 ∏ n E U ( X t ) Π V ( d u ) ≥ log Π ( V ) + ∫ V t = 1 ∑ n log E U ( X t ) Π V ( d u ) .
Taking expectation under S S S yields
E S log B n Π ≥ log Π ( V ) + n ∫ V h ( S , U ) Π V ( d u ) . \mathbb{E}_S\log B_n^{\Pi}\ge\log\Pi(V)+n\int_V h(S,U)\,\Pi_V(du). E S log B n Π ≥ log Π ( V ) + n ∫ V h ( S , U ) Π V ( d u ) .
Rearranging proves the second line of (54) ; the last line follows from Lemma 2.4. □
Corollary B.2 (Logarithmic mixture regret under local prior mass). Fix a full-support S ∈ A S\in\mathcal{A} S ∈ A and put m S = min i S i m_S=\min_i S_i m S = min i S i . Suppose there are constants c S > 0 c_S>0 c S > 0 , κ S > 0 \kappa_S>0 κ S > 0 , and ρ S > 0 \rho_S>0 ρ S > 0 such that
Π ( { U ∈ A : ∥ U − S ∥ 1 ≤ ρ } ) ≥ c S ρ κ S , 0 < ρ ≤ ρ S . (55) \Pi(\{U\in\mathcal{A}:\lVert U-S\rVert_1\le\rho\})\ge c_S\rho^{\kappa_S},\qquad0<\rho\le\rho_S. \tag*{(55)} Π ({ U ∈ A : ∥ U − S ∥ 1 ≤ ρ }) ≥ c S ρ κ S , 0 < ρ ≤ ρ S . (55) Then there is a finite constant C S C_S C S such that, for all n ≥ 2 n\ge2 n ≥ 2 ,
0 ≤ n Γ ( S ) − E S log B n Π ≤ κ S 2 log n + C S . (56) 0\le n\Gamma(S)-\mathbb{E}_S\log B_n^{\Pi}\le\frac{\kappa_S}{2}\log n+C_S. \tag*{(56)} 0 ≤ n Γ ( S ) − E S log B n Π ≤ 2 κ S log n + C S . (56) In particular,
1 n E S log B n Π ⟶ Γ ( S ) . \frac{1}{n}\mathbb{E}_S\log B_n^{\Pi}\longrightarrow\Gamma(S). n 1 E S log B n Π ⟶ Γ ( S ) . For a prior with a density bounded below in a neighborhood of an interior point S S S of the ( d − 1 ) (d-1) ( d − 1 ) -dimensional simplex, one may take κ S = d − 1 \kappa_S=d-1 κ S = d − 1 .
Proof. For ρ ≤ m S / 2 \rho\le m_S/2 ρ ≤ m S /2 and ∥ U − S ∥ 1 ≤ ρ \lVert U-S\rVert_1\le\rho ∥ U − S ∥ 1 ≤ ρ , every U i ≥ m S / 2 U_i\ge m_S/2 U i ≥ m S /2 . Using D K L ( S ∥ U ) ≤ ∑ i ( S i − U i ) 2 / U i D_{\mathrm{KL}}(S\mathbin\Vert U)\le\sum_i(S_i-U_i)^2/U_i D KL ( S ∥ U ) ≤ ∑ i ( S i − U i ) 2 / U i gives
D K L ( S ∥ U ) ≤ 2 m S ∥ U − S ∥ 2 2 ≤ 2 m S ρ 2 . D_{\mathrm{KL}}(S\mathbin\Vert U)\le\frac{2}{m_S}\lVert U-S\rVert_2^2\le\frac{2}{m_S}\rho^2. D KL ( S ∥ U ) ≤ m S 2 ∥ U − S ∥ 2 2 ≤ m S 2 ρ 2 .
Apply Theorem B.1 to the ℓ 1 \ell_1 ℓ 1 ball of radius ρ \rho ρ and use (55) . Choosing ρ \rho ρ proportional to n − 1 / 2 n^{-1/2} n − 1/2 , truncated if necessary to lie below min { ρ S , m S / 2 } \min\{\rho_S,m_S/2\} min { ρ S , m S /2 } , yields (56) . □
Corollary B.3 (Almost-sure growth of the oracle mixture). Under the assumptions above, for every fixed full-support S ∈ A S \in\mathcal{A} S ∈ A ,
1 n log B n Π ⟶ Γ ( S ) almost surely under S . \frac{1}{n}\log B_n^{\Pi} \longrightarrow\Gamma(S) \qquad\text{almost surely under } S. n 1 log B n Π ⟶ Γ ( S ) almost surely under S . Proof. Let S ^ n \widehat{S}_n S n be the empirical distribution. Since each E U E_U E U is null-valid,
1 n log B n Π ≤ Γ ( S ^ n ) ⟶ Γ ( S ) \frac{1}{n}\log B_n^{\Pi} \leq\Gamma(\widehat{S}_n) \longrightarrow\Gamma(S) n 1 log B n Π ≤ Γ ( S n ) ⟶ Γ ( S ) almost surely. Conversely, fix η > 0 \eta> 0 η > 0 . Continuity provides a neighborhood V V V of S S S on which h ( S , U ) ≥ Γ ( S ) − η h(S,U) \geq\Gamma(S)-\eta h ( S , U ) ≥ Γ ( S ) − η . Uniform continuity on the compact parameter set implies inf U ∈ V h ( S ^ n , U ) ≥ Γ ( S ) − 2 η \inf_{U\in V}h(\widehat{S}_n,U) \geq\Gamma(S)-2\eta inf U ∈ V h ( S n , U ) ≥ Γ ( S ) − 2 η eventually. Hence B n Π ≥ Π ( V ) e n ( Γ ( S ) − 2 η ) B_n^{\Pi} \geq\Pi(V)e^{n(\Gamma(S)-2\eta)} B n Π ≥ Π ( V ) e n ( Γ ( S ) − 2 η ) eventually. Let η ↓ 0 \eta\downarrow0 η ↓ 0 .
Finite-grid approximation to the mixture
Let U ( 1 ) , … , U ( K ) U^{(1)},\ldots,U^{(K)} U ( 1 ) , … , U ( K ) be candidate alternatives and let π k > 0 \pi_k > 0 π k > 0 , ∑ k π k = 1 \sum_k \pi_k = 1 ∑ k π k = 1 . Then
B n ( K ) = ∑ k = 1 K π k ∏ t = 1 n E U ( k ) ( X t ) B_n^{(K)}=\sum_{k=1}^{K}\pi_k\prod_{t=1}^{n}E_{U^{(k)}}(X_t) B n ( K ) = k = 1 ∑ K π k t = 1 ∏ n E U ( k ) ( X t )
is a test supermartingale and, pathwise,
log B n ( K ) ≥ max k ≤ K { ∑ t = 1 n log E U ( k ) ( X t ) + log π k } . \log B_n^{(K)}\geq\max_{k\leq K}\left\{\sum_{t=1}^{n}\log E_{U^{(k)}}(X_t)+\log\pi_k\right\}. log B n ( K ) ≥ k ≤ K max { t = 1 ∑ n log E U ( k ) ( X t ) + log π k } .
Thus a uniform prior pays at most log K \log K log K relative to the best grid oracle. Precomputing K K K static oracles costs O ( K d log d ) O(Kd\log d) O ( K d log d ) using sorting and each observation costs O ( K ) O(K) O ( K ) thereafter. The statistical price is the approximation gap
Γ ( S ) − max k ≤ K E S log E U ( k ) ( X ) . \Gamma(S)-\max_{k\leq K}\mathbb{E}_S\log E_{U^{(k)}}(X). Γ ( S ) − k ≤ K max E S log E U ( k ) ( X ) .
A direct nonasymptotic stopping-time consequence is also available. If μ k ( S ) : = E S log E U ( k ) ( X ) > 0 \mu_k(S):=\mathbb{E}_S\log E_{U^{(k)}}(X)>0 μ k ( S ) := E S log E U ( k ) ( X ) > 0 and L k : = max i log E U ( k ) ( i ) L_k:=\max_i\log E_{U^{(k)}}(i) L k := max i log E U ( k ) ( i ) , then the k k k th expert log-wealth is a random walk with bounded increments and positive drift μ k ( S ) \mu_k(S) μ k ( S ) , so its threshold-hitting time has finite expectation. Wald’s identity and the bounded overshoot then give
E S τ α ( B ( K ) ) ≤ log ( 1 / α ) + log ( 1 / π k ) + L k μ k ( S ) . \mathbb{E}_S\tau_\alpha(B^{(K)})\leq\frac{\log(1/\alpha)+\log(1/\pi_k)+L_k}{\mu_k(S)}. E S τ α ( B ( K ) ) ≤ μ k ( S ) log ( 1/ α ) + log ( 1/ π k ) + L k .
Minimizing over k k k gives the best finite-grid bound.