3 A lower bound by duality
These are the results of Section 3 of the paper and of Sections S1.3, S2.1, and S2.2, in the setting of the previous chapter.
The pairs \((t,x^t)\) are pairs of a time \(t\) in \(\{ 0,1,\ldots \} \cup \{ \infty \} \) and a path \(x\), under the \(\sigma \)-algebra that observes only \(x^t\). A randomized stopping time is a measurable map \((x,u)\mapsto \tau (x,u)\), with \(u\in [0,1]\), such that \(\tau (\cdot ,u)\) is a stopping time of \((\mathcal{F}_t)\) for every \(u\). For a distribution \(P\) of \(X\), \(P^\tau \) is the distribution of \((\tau ,X^\tau )\), where \(\tau =\tau (X,U)\) with \(X\sim P\) and \(U\) uniform on \([0,1]\) and independent of \(X\).
For \(\xi \in \Delta _T\), \(Q^\xi \) is the distribution of \((\tau ,X^\tau )\) for \(X\sim Q\) and an independent time \(\tau \) with distribution \(\xi \). The set \(\mathcal{B}\) contains the mixtures \(\bar P=\int P_\lambda ^{\tau _\lambda }\pi (\mathrm{d}\lambda )\), where \(\pi \) is a probability measure on a measurable space, \(\lambda \mapsto P_\lambda \in \mathcal{P}\) is a probability kernel, and \((\lambda ,x,u)\mapsto \tau _\lambda (x,u)\) is measurable, with \(\tau _\lambda \) a randomized stopping time for every \(\lambda \).
For every e-process \((E_t)\), every \(P\in \mathcal{P}\), and every randomized stopping time \(\tau \), \(\mathrm{E}_P\{ E_{\tau (X,U)}\} \le 1\) (Section 3).
Fubini’s theorem, since \(\mathrm{E}_P\{ E_{\tau (X,u)}\} \le 1\) for every \(u\).
For \(0\le t\le T\) and \(B\in \mathcal{F}_t\), \(Q^\xi [\{ t\} \times B]=\xi _tQ_t(B)\), and \(Q^\xi \) is the image of \((\sum _t\xi _t\delta _t)\otimes Q\) under the map that stops the path at the time (Section 3).
By the definition of the image measure.
The set \(\mathcal{B}\) contains the Bayesian mixtures of stopped elements of the null of Koolen and Grünwald (2022, Section 3), the mixtures over a probability measure on pairs of a null distribution and a stopping time of \((\mathcal{F}_t)\) (Section 3).
A stopping time is a randomized stopping time that does not depend on \(u\).
For probability measures \(\mu \) and \(\nu \) and a measurable \(H\) with values in \([0,\infty ]\) and \(\int H\mathrm{d}\nu \le 1\), \(\mathrm{E}_\mu (\log H)\le \mathrm{KL}(\mu \| \nu )\).
If \(\mathrm{KL}(\mu \| \nu ){\lt}\infty \), then \(\mu \) has a density \(f\) with respect to \(\nu \) with \(\log f\) \(\mu \)-integrable, by the definition of the Kullback–Leibler divergence in Mathlib, and Jensen’s inequality gives \(\mathrm{E}_\mu \{ \log (H/f)\} \le \log \int H\mathrm{d}\nu \le 0\).
For an e-process \((E_t)\) and \(\bar P\in \mathcal{B}\), the function \(H(t,x^t)=E_t(x^t)\) on the pairs satisfies \(\int H\mathrm{d}\bar P=\int \mathrm{E}_{P_\lambda }\{ E_{\tau _\lambda (X,U)}\} \pi (\mathrm{d}\lambda )\le 1\).
Fubini’s theorem and Lemma 30.
For every \(\mathcal{X}\), every \(\xi \in \Delta _T\), every e-process \((E_t)\), and every \(\bar P\in \mathcal{B}\), \(\sum _{t=0}^T\xi _t\mathrm{E}_Q(\log E_t)\le \mathrm{KL}(Q^\xi \| \bar P)\) (Section 3).
By Lemma 31, \(\int \log H\mathrm{d}Q^\xi =\sum _t\xi _t\mathrm{E}_Q(\log E_t)\) in \([-\infty ,\infty ]\), and the Gibbs inequality applies to \(H\) by eq. (S4).
Let \(T\ge 0\). For every e-process \((E_t)\), every \(\xi \in \Delta _T\), and every \(\bar P\in \mathcal{B}\),
which is eq. (5), with the convention \(0\times \infty =0\) in the sums. Consequently, for every \(\xi \in \Delta _T\), \(\Gamma _T\ge \inf _{(E_t)}\sum _t\xi _tR_t(E_t)\ge \sum _t\xi _t\mathrm{E}_Q(\log E^{\star }_t)-\inf _{\bar P\in \mathcal{B}}\mathrm{KL}(Q^\xi \| \bar P)\), which is eq. (6).
If every \(\tau _\lambda \) is independent of \(X\), then
and the right-hand side of (5) is at most zero.
As in Section S1.3, the Gibbs inequality is applied once on the pairs \((t,x^t)\), to \(H=E^{\star }_t\mathbf{1}(t\le T)\), for which \(\int H\mathrm{d}\bar P\) is an average of the \(\mathrm{E}_{P_\lambda }(E^{\star }_t)\le 1\).
For every \(\xi \in \Delta _T\), \(\sup _{(E_t)}\sum _{t=0}^T\xi _t\mathrm{E}_Q(\log E_t)=\sum _{t=0}^T\xi _t\mathrm{E}_Q(\log E^{\star }_t)-\inf _{(E_t)}\sum _{t=0}^T\xi _tR_t(E_t)\).
Lemma 15, summed over \(t\).
Under the standing assumption, \(\Gamma _T=\max _{\xi \in \Delta _T}\inf _{(E_t)}\sum _{t=0}^T\xi _tR_t(E_t)\), for every \(\mathcal{X}\).
Sion’s minimax theorem is applied to \((\xi ,v)\mapsto \sum _t\xi _tv_t\) on \(\Delta _T\) and on the convex set of the vectors \(v\) that dominate the regrets of some e-process stopped at \(T\). This set is convex because the regret is convex in the e-variable and combinations of stopped e-processes are e-processes, and the mixtures \((1-\varepsilon )E_t+\varepsilon \) relate the two infima, as in (S13). The maximum is attained by upper semicontinuity on the compact \(\Delta _T\). This is the proof of Proposition S1(ii) in Section S2.1, which the paper adopted after the formalization.
Let \(T\ge 0\). (i) Suppose that \(\Gamma _T=0\), and that \(\mathcal{X}\) is finite or \(P_T\ll Q_T\) for every \(P\in \mathcal{P}\). Then \(E^{\star }_0,\ldots ,E^{\star }_T\) have versions such that \((E^{\star }_{t\wedge T})_{t\ge 0}\) is an e-process. (ii) On every sample space \(\mathcal{X}\), \(\Gamma _T=\max _{\xi \in \Delta _T}\inf _{(E_t)}\sum _{t=0}^T\xi _tR_t(E_t)\). (iii) If \(\mathcal{X}\) is finite, then, for every \(\xi \in \Delta _T\),
which is eq. (S11).
As in Section S2.1. (i) Take e-processes \((E^n_t)\) with regrets at most \(2^{-n}\). The pointwise inequality \(u-1-\log u\ge (u^{1/2}-1)^2\) bounds \(\mathrm{E}_Q\{ (U^n_t)^{1/2}-1\} ^2\) by the regret, with \(U^n_t=E^n_t/E^{\star }_t\), and summability gives the almost sure convergence of \(E^n_t\) to \(E^{\star }_t\). Fatou’s lemma then gives the e-process property, after the set of convergence is transferred from \(Q\)-null to \(P\)-null sets through the marginals. For finite \(\mathcal{X}\), the same argument applies to the \(E^n\) set to zero at the nodes of \(Q\)-probability zero. (ii) Lemma 39. (iii) Lemma 1 gives one inequality of (S11), and the theorem of Koolen and Grünwald with eq. (S14) the other.
For a finite \(\mathcal{X}\), \(\Gamma _T\) is the infimum of \(\max _{t\le T}R_t(E_t)\) over the bounded e-processes \((E_t)\) stopped at \(T\) (Section S2.1).
For a node \(x^t\) of positive probability under some null distribution \(P\), \(E_t(x^t)\le 1/P(X^t=x^t)\), as the e-variable \(1+\infty \mathbf{1}(X^t=x^t)\) shows, in place of \(1+m\mathbf{1}(X^t=x^t)\) with \(m\to \infty \). The bound is the sum over the finitely many nodes up to \(T\).
The alternatives \(Q^\xi \) with \(\xi \) a unit mass have disjoint supports: for \(t\ne t'\), the unit masses at \(t\) and \(t'\) give mutually singular distributions on the pairs (Section S2.1).
They are concentrated on the disjoint sets of the pairs with times \(t\) and \(t'\).