5 Stopping rules that depend on the null mean
These are the results of Section 4.2 of the paper, of Section S1.5, of the upper bound of Section S1.6, and of Section S1.8.
The random walk \((S_t)_{t\ge 0}\) has \(S_0=0\) and independent \(\mathrm{N}(0,1)\) increments; it is realized on the space of its increments, with distribution \(\mathrm{N}(0,1)^{\otimes \infty }\). The reward is \(h_0=1\) and \(h_t=s\exp \{ (1-s^2)S_t^2/(2t)\} \) for \(t\ge 1\).
Let \(s{\gt}0\). (i) For every \(\theta \in \mathbb {R}\) and every \(t\ge 1\), \(E^{\star }_t=sL^\theta _t\exp \{ (1-s^2)t(\bar X_t-\theta )^2/(2s^2)\} \). (ii) For every \(T\ge 0\), \(\eta _T=\sup _\tau \mathrm{E}(h_{\tau \wedge T})\), where \(\tau \) ranges over the stopping times of the filtration generated by \((S_t)\).
(i) Eq. (S2) with \(m=\theta \) and \(v\in \{ s^2,1\} \), as in Section S1.5. (ii) With \(g_t=s\exp \{ (1-s^2)t(\bar X_t-\theta )^2/(2s^2)\} \), \(E^{\star }_t=L^\theta _tg_t\), and the change of measure from \(P_\theta \) to \(Q_\theta \) on \(\mathcal{F}_t\) gives \(\mathrm{E}_\theta (E^{\star }_{\tau \wedge T})=\mathrm{E}_{Q_\theta }(g_{\tau \wedge T})\). Under \(Q_\theta \), \(S_t=\sum _{i\le t}(X_i-\theta )/s\) is the random walk, \(g_t=h_t\), and the map from the data to the increments sends the stopping times of \((\mathcal{F}_t)\) bijectively to those of the filtration generated by \((S_t)\).
Assume the law of the iterated logarithm. If \(s{\lt}1\), then \(\limsup _{t\to \infty }\log h_t/\log \log t=1-s^2\) almost surely (Section 4.2).
\(\log h_t=\log s+(1-s^2)S_t^2/(2t)\), and \(S_t^2/(2t\log \log t)\) has limit superior one almost surely.
For an integer \(u\ge 1\) and \(x\ge 0\), \(\mathrm{pr}(\max _{t\le u}S_t\ge x)\le \exp \{ -x^2/(2u)\} \), and \(\mathrm{pr}(\max _{t\le u}|S_t|\ge x)\le 2\exp \{ -x^2/(2u)\} \).
Doob’s maximal inequality for the submartingale \(\exp (xS_t/u)\). The bound for \(-S_t\) applies the same inequality to \(\exp (-xS_t/u)\) instead of the symmetry of the random walk.
Let \(q{\gt}1\), and let \(B_k=\{ t\le T:q^k\le t{\lt}q^{k+1}\} \). For \(z\ge 0\), \(\mathrm{pr}(\max _{t\in B_k}S_t^2/t\ge z^2)\le 2\exp \{ -z^2/(2q)\} \), and the blocks \(B_k\) with \(k\ge N=1+\lfloor \log T/\log q\rfloor \) are empty.
With \(m\) and \(u\) the smallest and the largest elements of \(B_k\), \(u{\lt}qm\), and eq. (S5) applies at \(u\) with \(x=zm^{1/2}\).
Let \(s\in (0,1)\), \(a=1-s^2\), \(T\ge 1\), and \(q\in (1,1/a)\). Then \(\log \eta _T\le aq\log (2+2\log T/\log q)+\log \{ 1/(1-aq)\} \).
As in Section S1.6. With \(M=\max [1,\max _{1\le t\le T}\exp \{ aS_t^2/(2t)\} ]\), \(h_t\le M\) for \(t\le T\), so that \(\eta _T\le \mathrm{E}(M)\) by Lemma 2(ii). The union bound over the blocks gives \(\mathrm{pr}(M{\gt}x)\le \min \{ 1,2Nx^{-1/(aq)}\} \) for \(x\ge 1\), and \(\mathrm{E}(M)=1+\int _1^\infty \mathrm{pr}(M{\gt}x)\mathrm{d}x\le (2N)^{aq}/(1-aq)\).
Let \(s\ge 1\) and \(\varepsilon {\gt}0\), and let \(\tau _\varepsilon \) be the first \(t\ge 1\) with \(S_t^2/t\le \varepsilon \). Then \(\mathrm{E}(h_{\tau _\varepsilon \wedge T})\ge s\exp \{ -(s^2-1)\varepsilon /2\} \mathrm{pr}(\tau _\varepsilon \le T)\).
On \(\{ \tau _\varepsilon \le T\} \), \(h_{\tau _\varepsilon }\ge s\exp \{ -(s^2-1)\varepsilon /2\} \), and \(h_t\ge 0\) elsewhere.
If \(s\ge 1\), then \(\Gamma _T\le \log \eta _T\le \log s\) for every \(T\ge 0\), and, given the law of the iterated logarithm, \(\log \eta _T\to \log s\) as \(T\to \infty \).
For \(s\ge 1\), \(h_t\le s\), so that \(\eta _T\le s\) by Lemma 2(ii), and Proposition 1(iii) gives \(\Gamma _T\le \log \eta _T\), with the numéraires of Proposition 2, since \(\rho ^2\ge 1-s^2\) for every \(\rho \). For the limit, the law of the iterated logarithm gives infinitely many sign changes of the random walk. At a sign change between \(t\) and \(t+1\), \(|S_t|\le |S_{t+1}-S_t|\), and the law of large numbers gives \((S_{t+1}-S_t)^2/t\to 0\) almost surely, so that \(\tau _\varepsilon {\lt}\infty \) almost surely. Eq. (S10) then gives \(\liminf _T\eta _T\ge s\exp \{ -(s^2-1)\varepsilon /2\} \) for every \(\varepsilon {\gt}0\).
For \(s\ge 1\) and every \(T\), the e-process \((E^{\star }_{t\wedge T}/\eta _T)_{t\ge 0}\) of Proposition 1(iii) has regret at most \(\log s\) against every \(Q_\mu \) at every \(t\le T\), so that the minimax regret in the worst case over \(\mu \) is at most \(\log s\) (Section 4.3).
For \(s\ge 1\), \(\prod _{i=2}^t\ell (Y_i)\) is also the numéraire of every \(Q_\mu \) (Proposition S4); the regrets do not depend on the versions of the numéraires, by their uniqueness, and Proposition 4 bounds \(\log \eta _T\).