# On the spine of two-particle Fleming-Viot process driven by Brownian motion

Krzysztof Burdzy and Tvrtko Tadić  KB: Department of Mathematics, Box 354350,
University of Washington, Seattle, WA 98195, USA<EMAIL_ADDRESS>TT: Microsoft
Corporation, One Microsoft Way, Redmond, WA 98052<EMAIL_ADDRESS>
###### Abstract.

The spine of two-particles Fleming-Viot process driven by Brownian motion is
not a Bessel-3 process.

###### Key words and phrases:

Fleming-Viot type process, Brownian motion, Bessel process, logarithmic
transformation

###### 2020 Mathematics Subject Classification:

60G17, 60J65, 60J80

##  1\. Introduction

We start with an informal outline of the main idea of this note. A more
detailed review, including history and citations, will be presented later in
the introduction.

A Fleming-Viot process is a branching process. Under very mild assumptions, it
has a unique spine. When the number of individuals in the population is very
large, the distribution of the spine is expected to be very close to the
distribution of the driving process conditioned on survival forever. There is
an example showing that the distribution of the spine may be different from
the distribution of the driving process conditioned on survival forever. The
published example is rather artificial so we present in this note a different
example illustrating the same claim. Our new example is more natural in the
sense that it is based on a model examined in a number of papers on Fleming-
Viot processes.

###  1.1. Literature review

Fleming-Viot-type processes were originally defined in [5]. In this model,
there is a population of fixed size. Every individual moves independently from
all other individuals according to the same Markovian transition mechanism, in
a domain with a boundary. When an individual hits the boundary, an individual
chosen randomly (uniformly) from the survivors splits into two individuals and
the process continues in this manner. The question of whether the process can
be continued for all times was addressed in [5, 4, 3, 11]. All of these papers
studied, among other process, Fleming-Viot processes driven by Brownian
motion.

A very special case of a Fleming-Viot process is when there are only two
individuals driven by Brownian motion on $[0,\infty)$ and $0$ plays that role
of the boundary; this model was studied in [4, 11]. In particular, it was
shown in both papers that this process has infinite lifetime.

Every Fleming-Viot process has a unique spine, i.e., a trajectory inside the
branching tree that never hits the boundary of the domain where the process is
confined; this was proved under strong assumptions in [11, Thm. 4] and later
in the full generality in [2].

It was proved in [2] that if the state space is finite and the number of
individuals in the population goes to infinity then the distributions of spine
processes converge to the distribution of the driving Markov process
conditioned on survival forever. The same paper contains an example of a
Fleming-Viot process driven by a Markov process on a three-element state space
(one of the elements plays the role of the boundary). In that example, the
population consists of two individuals and the distribution of the spine is
not equal to the distribution of the driving Markov process conditioned on
survival forever. A Markov process with a three-element state space seems to
be a rather artificial example in the context of Fleming-Viot models. We will
show that the spine of the Fleming-Viot process with two individuals driven by
Brownian motions on $[0,\infty)$ has a spine with a distribution different
from the distribution of Brownian motion conditioned to stay positive, i.e.,
the distribution of the 3-dimensional Bessel process. The point of this note
is to show that proving that the spine does not have the distribution of the
3-dimensional Bessel process is somewhat tricky. In hindsight, this does not
seems to be difficult because our proof is quite elementary, Nevertheless, our
previous attempts in [6, 7] generated some new results but failed to show the
difference. In a sense that will be made more precise later on in the paper,
the spine is quite “close” to a 3-dimensional Bessel process and therefore it
is quite hard to distinguish the two. The problem has been open for some time
and while the solution is not really difficult we now have a better
understanding as to why the spine is nevertheless similar to a 3-dimensional
Bessel process in certain respects.

##  2\. Model and main result

We will now define a Fleming-Viot process and other elements of the model.
Informally, the process consists of two independent Brownian particles
starting at the same point in $(0,\infty)$. At the time when one of them hits
0, it is killed and the other one branches into two particles. The new
particles start moving as independent Brownian motions and the scheme is
repeated.

###  2.1. Notation and definitions

On the formal side, let $(W_{1}(t):t\geq 0)$ and $(W_{2}(t):t\geq 0)$ be two
independent Brownian motions starting from $W_{1}(0)=W_{2}(0)=1$. Let

$\displaystyle T_{0}$ $\displaystyle=0,$ $\displaystyle Y_{0}$
$\displaystyle=1,$ $\displaystyle\tau_{j}$ $\displaystyle=\inf\\{t\geq
0:W_{j}(t)=0\\},\qquad j=1,2,$ $\displaystyle T_{1}$
$\displaystyle=\min(\tau_{1},\tau_{2}),$ $\displaystyle Y_{1}$
$\displaystyle=\max(W_{1}(T_{1}),W_{2}(T_{1})),$

and for $k\geq 2$,

$\displaystyle T_{k}$
$\displaystyle=\inf\\{t>T_{k-1}:\min(W_{1}(t)-W_{1}(T_{k-1})+Y_{k-1},W_{2}(t)-W_{2}(T_{k-1})+Y_{k-1})=0\\},$
$\displaystyle Y_{k}$
$\displaystyle=\max(W_{1}(T_{k})-W_{1}(T_{k-1})+Y_{k-1},W_{2}(T_{k})-W_{2}(T_{k-1})+Y_{k-1}).$

It follows from [3, Thm. 5.4] or [11, Thm. 1] that, a.s.,

(1) $T_{k}\to\infty.$

Hence, for any $t\geq 0$ we can find $j$ such that $t\in[T_{j-1},T_{j})$. Then
we set

(2) $\displaystyle\mathcal{V}(t)$
$\displaystyle=(V_{1}(t),V_{2}(t))=(W_{1}(t)-W_{1}(T_{j-1})+Y_{j-1},W_{2}(t)-W_{2}(T_{j-1})+Y_{j-1}).$

This completes the definition of $\\{\mathcal{V}(t),t\geq 0\\}$, an example of
a Fleming-Viot process.

Let $J_{t}=J(t)$ denote the spine, i.e., $J_{t}=V_{1}(t)$ if
$t\in[T_{k-1},T_{k})$ and

$\displaystyle
W_{1}(T_{k})-W_{1}(T_{k-1})+Y_{k-1}>W_{2}(T_{k})-W_{2}(T_{k-1})+Y_{k-1}.$

If the last condition fails, we let $J_{t}=V_{2}(t)$ for
$t\in[T_{k-1},T_{k})$.

Note that $J(T_{k})=Y_{k}$ for all $k\geq 1$.

Recall that $d$-dimensional Bessel process $X_{t}$ is defined by

(3) $\displaystyle dX_{t}=dB_{t}+\frac{d-1}{2X_{t}}dt,$

where $B$ is Brownian motion; see [12, Sect. 3.3 C]. It is well known that
Brownian motion on $[0,\infty)$ conditioned to never hit 0 has the transition
probabilities of 3-dimensional Bessel process; this theorem was first proved
in [8].

###  2.2. Main result

######  Theorem 2.1.

The distributions of $\\{J_{t},0\leq t<\infty\\}$ and $\\{X_{t},0\leq
t<\infty\\}$ starting from 1 are singular with respect to each other.

We will explicitly define an event that has a strictly positive probability
according to the first distribution but not according to the second one, and
vice versa.

We will now review two attempts to prove Theorem 2.1 that failed.

The following version of the Law of the Iterated Logarithm was proved in [7].

######  Theorem 2.2.

Almost surely,

(4) $\displaystyle\limsup_{n\to\infty}\frac{Y_{n}}{\sqrt{2T_{n}\log\log
T_{n}}}=1.$

The Law of Iterated Logarithm stated in (4) is the same as that for the
3-dimensional Bessel process (see [14]), which has the same distribution as
the one-dimensional Brownian motion conditioned not to hit 0. Hence, Theorem
2.2 does not eliminate the possibility that the spine $J_{t}$ has the
distribution of Brownian motion conditioned not to hit 0.

In this note, we will prove the following result.

######  Theorem 2.3.

For every $u>0$,

$\displaystyle\frac{1}{u}\log\operatorname{\mathds{P}}\left(\inf_{s\geq 0}\log
X(s)<-u\right)=-1=\lim_{t\to\infty}\frac{1}{t}\log\operatorname{\mathds{P}}\left(\inf_{n\geq
0}\log J(T_{n})<-t\right).$

The general message from Theorems 2.2 and 2.3 is that it is hard to
distinguish between the spine and 3-dimensional Bessel process by studying
“extreme” behavior of the two processes. The proof of Theorem 2.1 will be
based on the analysis of the processes on the “logarithmic scale.”

##  3\. Bessel processes

Recall the stochastic differential equation (3) defining Bessel processes. Let
$f(x)=\log x$. Then $f^{\prime}(x)=1/x$ and $f^{\prime\prime}(x)=-1/x^{2}$.
Let $A_{t}=f(X_{t})$. Then by the Ito formula

$\displaystyle dA_{t}$
$\displaystyle=df(X_{t})=\frac{1}{X}_{t}dB_{t}+\left(\frac{d-1}{2X_{t}}\cdot\frac{1}{X_{t}}-\frac{1}{2}\cdot\frac{1}{X_{t}^{2}}\right)dt=\frac{1}{X_{t}}dB_{t}+\frac{d-2}{2X_{t}^{2}}dt$
$\displaystyle=e^{-A_{t}}dB_{t}+\frac{d-2}{2}e^{-2A_{t}}dt.$

For 3-dimensional Bessel process, i.e., when $d=3$, the formula is

$dA_{t}=e^{-A_{t}}dB_{t}+\frac{1}{2}e^{-2A_{t}}dt.$

We see that the process $A_{t}$ is a time change of the process
$B_{t}+\frac{1}{2}t$, if we use the clock

$\displaystyle\rho(t):=\int_{0}^{t}e^{-2A_{s}}ds=\int_{0}^{t}\frac{1}{X_{s}^{2}}ds.$

In other words, $\\{A_{\rho(t)},t\geq 0\\}=\\{\log X_{\rho(t)},t\geq 0\\}$ has
the same distribution as $\left\\{B_{t}+\frac{1}{2}t,t\geq 0\right\\}$. Hence,
we have

######  Lemma 3.1.

For the 3 -dimensional Bessel process $X_{t}$ we have a.s.,

$\lim_{t\to\infty}\frac{1}{t}{\log
X_{\rho(t)}}=\lim_{t\to\infty}\frac{1}{t}\left(B_{t}+\frac{1}{2}t\right)=\frac{1}{2}.$

######  Lemma 3.2.

Suppose that $X=\\{X(t)\ :\ t\geq 0\\}$ is the 3-dimensional Bessel process
with $X(0)=1$. Let $M=\inf_{t\geq 0}\log X(t)$. Then $-M$ has the exponential
distribution with mean 1.

###### Proof.

Time change does not affect the distribution of the infimum of a process,
hence $M$ has the same distribution as $\min_{t\geq
0}\left(B_{t}+\frac{1}{2}t\right)$. According to [12, Sect. 3.3, Exercise
5.9], $-M$ is exponential with mean 1. ∎

##  4\. Logarithmic transformation of Fleming-Viot process

We will use complex representation $V_{1}(t)+iV_{2}(t)$ of the process
$\mathcal{V}(t)=(V_{1}(t),V_{2}(t))$ defined in (2). We apply the complex
mapping $z\mapsto\log z$ to this process so that it is transformed into a
process in the strip $D:=\\{(x,y):0<y<\pi/2\\}$ (see Fig. 1). Consider the
following time change,

(5) $\phi(t)=\int_{0}^{t}\frac{1}{|\mathcal{V}(s)|^{2}}ds.$

It follows from conformal invariance of two-dimensional Brownian motion (see
[13, Thm. V (2.5)]) that the process
$Z(t)=(Z_{1}(t),Z_{2}(t)):=\log\mathcal{V}({\phi(t)})$ is two-dimensional
Brownian motion jumping from the boundary of $D$ to an appropriate point in
$D$ every time it exits $D$. Let $R_{1},R_{2},\dots$ be the times of jumps of
$Z$, and let $R_{0}=0$.

Figure 1. The logarithmic transformation of the Fleming-Viot process.

######  Lemma 4.1.

We have the following representation

(6) $Z_{1}(t)=\log|\mathcal{V}(\phi(t))|=B_{t}+(N_{t}-1)\log\sqrt{2},$

where $\\{B_{t}:t\geq 0\\}$ is Brownian motion and $\\{N_{t}:t\geq 0\\}$ is a
renewal process independent of $B$ such that $N_{0}=1$, and, a.s.,

$\lim_{t\to\infty}\frac{N_{t}}{t}=\left(\frac{\pi}{4}\right)^{-2}.$

###### Proof.

A jump takes $Z$ from $(Z_{1}(R_{k}),Z_{2}(R_{k}))\in\partial D$, i.e., the
point at which $Z$ exits $D$, to
$\left(\log\left(\sqrt{2}\right)+Z_{1}(R_{k}),\pi/4\right)$.

Brownian motions driving $Z_{1}$ and $Z_{2}$ between jumps are independent of
each other. The times $R_{k}$ are the times when $Z_{2}$ exits $[0,\pi/2]$.
Hence, $\\{R_{k},k\geq 0\\}$ is independent of the Brownian motion $B_{t}$
driving $Z_{1}(t)$.

Let $N_{t}=\inf\\{k:R_{k}>t\\}$. Then

$\displaystyle Z_{1}(t)$
$\displaystyle=\log|\mathcal{V}(\phi(t))|=B_{t}+(\inf\\{k:R_{k}>t\\}-1)\log\sqrt{2}$
$\displaystyle=\log|\mathcal{V}(\phi(t))|=B_{t}+(N_{t}-1)\log\sqrt{2}.$

The intervals $\\{R_{k}-R_{k-1},k\geq 1\\}$ are i.i.d. The distribution of
each interval is the distribution of the exit time of Brownian motion from
$[0,\pi/2]$ starting from its center. It is well known that
$\operatorname{\mathds{E}}[R_{k}-R_{k-1}]=\left({\pi}/{4}\right)^{2}$. Thus,
by renewal theory (see, [9]), we have a.s.,

$\lim_{t\to\infty}\frac{N_{t}}{t}=\frac{1}{\operatorname{\mathds{E}}[R_{2}-R_{1}]}=\left(\frac{\pi}{4}\right)^{-2}.$

∎

It follows from Lemma 4.1 that

(7) $\displaystyle\lim_{t\to\infty}\frac{Z_{1}(t)}{t}$
$\displaystyle=\lim_{t\to\infty}\frac{B_{t}}{t}+\lim_{t\to\infty}\frac{N_{t}-1}{t}\log\sqrt{2}=0+\left(\frac{\pi}{4}\right)^{-2}\log\sqrt{2}$
$\displaystyle=\left(\frac{4}{\pi}\right)^{2}\log\sqrt{2}=:\kappa\approx
0.561844.$

######  Corollary 4.2.

The process $\\{\log J(T_{n}),n\geq 0\\}$ is a random walk, such that $\log
J(T_{0})=\log J_{0}=0$, and satisfying

$\log J(T_{n})=\log J(T_{n-1})+\log\sqrt{2}+K_{n},\qquad n\geq 1,$

where $\\{K_{n},n\geq 1\\}$ is an i.i.d. sequence. The distribution of $K_{n}$
is that of $Z_{1}(R_{1})$.

###### Proof.

Recall that the process $B$ in (6) is Brownian motion and $R_{1}$ is the exit
time from the interval $[0,\pi/2]$ for a Brownian motion starting at $\pi/4$
and independent of $B$. Note that

$\log J(T_{n})-\log J(T_{n-1})=\log\sqrt{2}+Z_{1}(R_{n})-Z_{1}(R_{n-1}).$

The lemma follows from independence of $\\{R_{n},n\geq 1\\}$ and $B$, and the
fact that $R_{n}-R_{n-1}\stackrel{{\scriptstyle d}}{{=}}R_{1}$. ∎

######  Theorem 4.3.

We have

$\lim_{t\to\infty}e^{t}\operatorname{\mathds{P}}\left(\inf_{n\geq 0}\log
J(T_{n})<-t\right)=c\in(0,\infty).$

###### Proof.

Since $\\{\log J(T_{n}),n\geq 0\\}$ is a random walk, the function

$\displaystyle t\to\operatorname{\mathds{P}}\left(\inf_{n\geq 0}\log
J(T_{n})<-t\right)=\operatorname{\mathds{P}}\left(\sup_{n\geq 0}(-\log
J(T_{n}))>t\right)$

satisfies the Wiener-Hopf equation; see [1, point 2, bottom of page 191] for
general overview, and [10, Theorem 3.1]. It follows from these references that

(8) $\displaystyle\lim_{t\to\infty}e^{\gamma
t}\operatorname{\mathds{P}}\left(\inf_{n\geq 0}\log
J(T_{n})<-t\right)=\lim_{t\to\infty}e^{\gamma
t}\operatorname{\mathds{P}}\left(\sup_{n\geq 0}(-\log J(T_{n}))>t\right)=c,$

where $\gamma$ is the positive solution to the equation

$\operatorname{\mathds{E}}\left[e^{\gamma(-\log
J(T_{1}))}\right]=\operatorname{\mathds{E}}[J(T_{1})^{-\gamma}]=1.$

It follows from [11, (6.21)] that

$\operatorname{\mathds{P}}(J(T_{1})\in
dy)=\frac{2}{\pi}\left[\frac{1}{(1-y)^{2}+1}-\frac{1}{(1+y)^{2}+1}\right].$

It is not difficult to check that
$\operatorname{\mathds{E}}[J(T_{1})^{-1}]=1$. Hence $\gamma=1$ and, therefore,
the theorem follows from (8). ∎

###### Proof of Theorem 2.3.

The theorem follows from Lemma 3.2 and Theorem 4.3 ∎

##  5\. Comparing the spine and 3-dimensional Bessel process

Recall definition (5) of $\phi$ and let

$\displaystyle\sigma(t)=\int_{0}^{t}\frac{1}{J(s)^{2}}ds.$

Let $S_{0},S_{1},\ldots$ be such that $\phi(S_{n})=T_{n}$ and let
$H_{0},H_{1},\ldots$ be such that $\sigma(H_{n})=T_{n}$.

######  Lemma 5.1.

For $t_{1},t_{2}>0$, if $\sigma(t_{1})=\phi(t_{2})$ then $t_{1}\leq t_{2}$.

###### Proof.

For all $s>0$ we have $0<J^{2}(s)\leq|\mathcal{V}(s)|^{2}<\infty$. If
$t_{1}>t_{2}$ then

$\sigma(t_{1})=\int_{0}^{t_{1}}\frac{1}{J(s)^{2}}ds\geq\int_{0}^{t_{1}}\frac{1}{|\mathcal{V}(s)|^{2}}ds>\int_{0}^{t_{2}}\frac{1}{|\mathcal{V}(s)|^{2}}ds=\phi(t_{2}).$

∎

The following lemma gives us the comparison between time $(H_{n})$ and
$(S_{n})$.

######  Corollary 5.2.

For all $n\geq 0$ we have $H_{n}\leq S_{n}$.

###### Proof.

The case $n=0$ is trivial, since, $H_{0}=S_{0}=0$. For $n\geq 1$ we have
$\sigma(H_{n})=T_{n}=\phi(S_{n})$, hence by Lemma 5.1 we have $H_{n}\leq
S_{n}$. ∎

######  Lemma 5.3.

Almost surely, $H_{n}\to\infty$ and $S_{n}\to\infty$.

###### Proof.

Since $(T_{n})_{n\geq 0}$ is a non-decreasing sequence, the definition of
$H_{n}$ implies that $(H_{n})_{n\geq 1}$ is a non-decreasing sequence. Hence,
$L_{H}:=\lim_{n\to\infty}H_{n}$ exists in $[0,\infty]$.

If the event $\\{L_{H}<\infty\\}$ holds then
$T_{n}=\sigma(H_{n})\leq\sigma(L_{H})<\infty$ for all $n$, and, therefore,
$\limsup_{n\to\infty}T_{n}<\infty$. The probability of the last event is zero
according to (1) so $\operatorname{\mathds{P}}(L_{H}<\infty)=0$. This shows
that $H_{n}\to\infty$, a.s. Corollary 5.2 implies that $S_{n}\to\infty$, a.s.
∎

######  Lemma 5.4.

If $\kappa$ is defined as in (7) then, a.s.,

$\limsup_{t\to\infty}\frac{\log J(\sigma(t))}{t}\geq\kappa>\frac{1}{2}.$

###### Proof.

Since $S_{n}\to\infty$, we can use (6) and (7) to conclude that,

$\lim_{n\to\infty}\frac{\log|\mathcal{V}(\phi(S_{n}))|}{S_{n}}=\lim_{t\to\infty}\frac{Z_{1}(t)}{t}=\kappa,\quad\text{a.s.}$

Note that
$\sqrt{2}J(\sigma(H_{n}))=\sqrt{2}J(T_{n})=|\mathcal{V}(T_{n})|=|\mathcal{V}(\phi(S_{n}))|$
and recall that $S_{n}\leq H_{n}$. Thus

$\limsup_{n\to\infty}\frac{\log
J(\sigma(H_{n}))}{H_{n}}\geq\lim_{n\to\infty}\frac{\log|\mathcal{V}(\phi(S_{n}))|-\log\sqrt{2}}{S_{n}}=\kappa.$

The lemma follows since $H_{n}\to\infty$. ∎

###### Proof of Theorem 2.1.

For a process $U_{t}>0$, let

$\displaystyle\alpha(t)$ $\displaystyle=\int_{0}^{t}\frac{1}{U_{s}^{2}}ds,$
$\displaystyle F(U)$ $\displaystyle=\left\\{\lim_{t\to\infty}\frac{\log
U(\alpha(t))}{t}=\frac{1}{2}\right\\}.$

According to Lemmas 3.1 and 5.4, $\operatorname{\mathds{P}}(F(X))=1$ while
$\operatorname{\mathds{P}}(F(J))=0$. ∎

##  6\. Acknowledments

We are grateful to Jan Swart for the most useful advice. Our main result is
inspired by ideas that he kindly shared with us.

## References

  * [1] Søren Asmussen.  A probabilistic look at the Wiener-Hopf equation.  SIAM Rev., 40(2):189–201 (electronic), 1998.
  * [2] Mariusz Bieniek and Krzysztof Burdzy.  The distribution of the spine of a Fleming-Viot type process.  Stochastic Process. Appl., 128(11):3751–3777, 2018.
  * [3] Mariusz Bieniek, Krzysztof Burdzy, and Sam Finch.  Non-extinction of a Fleming-Viot particle model.  Probab. Theory Related Fields, 153(1-2):293–332, 2012.
  * [4] Mariusz Bieniek, Krzysztof Burdzy, and Soumik Pal.  Extinction of Fleming-Viot-type particle systems with strong drift.  Electron. J. Probab., 17:no. 11, 15, 2012.
  * [5] Krzysztof Burdzy, Robert Hołyst, and Peter March.  A Fleming-Viot particle representation of the Dirichlet Laplacian.  Comm. Math. Phys., 214(3):679–703, 2000.
  * [6] Krzysztof Burdzy, Bartosz Kołodziejek, and Tvrtko Tadić.  Inverse exponential decay: stochastic fixed point equation and ARMA models.  Bernoulli, 25(4B):3939–3977, 2019.
  * [7] Krzysztof Burdzy, Bartosz Kołodziejek, and Tvrtko Tadić.  Stochastic fixed point equation and local dependence measure, 2020.  Math ArXiv: 2004.01850.
  * [8] J. L. Doob.  Conditional Brownian motion and the boundary limits of harmonic functions.  Bull. Soc. Math. France, 85:431–458, 1957.
  * [9] Rick Durrett.  Probability: theory and examples.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, fourth edition, 2010.
  * [10] P. Embrechts and N. Veraverbeke.  Estimates for the probability of ruin with special emphasis on the possibility of large claims.  Insurance Math. Econom., 1(1):55–72, 1982.
  * [11] Ilie Grigorescu and Min Kang.  Immortal particle for a catalytic branching process.  Probab. Theory Related Fields, 153(1-2):333–361, 2012.
  * [12] Ioannis Karatzas and Steven E. Shreve.  Brownian motion and stochastic calculus, volume 113 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 1991.
  * [13] Daniel Revuz and Marc Yor.  Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, third edition, 1999.
  * [14] Tokuzo Shiga and Shinzo Watanabe.  Bessel diffusions as a one-parameter family of diffusion processes.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 27:37–46, 1973\.


* [NSW17] Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen.  Dynamic minimum spanning forest with subpolynomial worst-case update time.  In FOCS, pages 950–961. IEEE Computer Society, 2017.
  * [Ove88] Mark H. Overmars.  Efficient data structures for range searching on a grid.  J. Algorithms, 9(2):254–275, 1988.
  * [RSW18] Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg.  Computing exact minimum cuts without knowing the graph.  In Proceedings of the 9th ITCS, pages 39:1–39:16, 2018.
  * [ST83] Daniel Dominic Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  J. Comput. Syst. Sci., 26(3):362–391, 1983.
  * [Tho07] Mikkel Thorup.  Fully-dynamic min-cut.  Combinatorica, 27(1):91–127, 2007.
  * [Vit85] Jeffrey Scott Vitter.  Random sampling with a reservoir.  ACM Transactions on Mathematical Software, 11:37–57, 1985.
  * [Wul13] Christian Wulff-Nilsen.  Faster deterministic fully-dynamic graph connectivity.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1757–1769, 2013.
  * [Zel11] Mariano Zelke.  Intractability of min- and max-cut in streaming graphs.  Inf. Process. Lett., 111(3):145–150, 2011.

##  Appendix A Proof of Claim 3.1

A path $T$ of length $n$ has $n-1$ edges. We consider the edges
$\\{e_{1},\cdots,e_{n-1}\\}$ of the path $T$ from left to right. This ordering
naturally defines left and right vertex of an edge in the path. Given this
ordering, we identify each edge $e_{\ell}$ with the point $\ell$ in the
Interval problem. For an edge $e$ (which is not in the path) which connects
the left vertex of edge $e_{i}$ and the right vertex of edge $e_{j}$, we
identify $e$ with an interval $I_{e}=(i,j)$.

If we consider a 2-respecting cut that respects edges $e_{i}$ and $e_{j}$
($i\leq j$), then we claim that the cost of this cut is equal to
$\mathsf{Cost}(i,j)$ in the Interval problem. This is because:

  1. 1.

For any edge $e$ to contribute to this cut, the edge has to connect a vertex
$v$, which is between right-side of edge $e_{i}$ and left-side of edge
$e_{j}$, with a vertex $u$ which is either on the left-side of edge $e_{i}$ or
right-side of edge $e_{j}$. The interval $I_{e}$, will cover either $i$ or
$j$, but nor both, and hence contributes to $\mathsf{Cost}(i,j)$. In Figure 3,
where we are interested in $\mathsf{Cost}(2,5)$, interval $I_{3}$ is such an
interval.

  2. 2.

For any edge $e^{\prime}$, which connects the left-side of edge $e_{i}$ to the
right-side of edge $e_{j}$, $I_{e}$ covers both $i$ and $j$. For any edge
$e^{\prime\prime}$, which is contained between the right-side of edge $e_{i}$
to the left-side of edge $e_{j}$, $I_{e^{\prime}}$ covers none of $i$ and $j$.
In both cases, the corresponding intervals do not contribute to
$\mathsf{Cost}(i,j)$. In Figure 3, interval $I_{1}$ is the first kind of
interval, and $I_{2}$ is the second kind. Neither of $I_{1}$ and $I_{2}$
contributes to $\mathsf{Cost}(2,5)$.

Note that this argument goes both ways, i.e.,
$\mathsf{Cost}(i^{\prime},j^{\prime})$ represents the cost of a 2-respecting
min-cut which respects edge $e_{i^{\prime}}$ and $e_{j^{\prime}}$.


$\displaystyle=\operatorname{\widetilde{\mathcal{O}}}\left(\sqrt{d}H\sqrt{t\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{t}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right]}\right),$

where the last line again uses the configuration $K=t$ and the definition of
$\widetilde{\pi}_{t}$. ∎

######  Lemma C.5.

The Bias-2 \+ Bonus-2 part in Equation C.1 is of order
$\operatorname{\widetilde{\mathcal{O}}}(d{\beta_{1}}^{-1})$.

###### Proof.

This part is already a constant in Equation A.3 ∎

######  Lemma C.6.

The Bonus-1 term in Equation C.1 is bounded by

$\displaystyle\quad\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}\left[\sum_{k=1}^{K}\operatornamewithlimits{\mathbb{E}}_{a\sim\pi_{k}^{i}(\cdot\mid
s)}\left[{\beta_{1}}\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}+\beta_{2}\sum_{j=1}^{d}\bm{\phi}(s,a)[j]\times\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}_{h}\times\mathcal{A}^{i}}(\widehat{\Sigma}_{t,i}^{\dagger}\bm{\phi}(s^{\prime},a^{\prime}))[j]\right]\right]\right]$
$\displaystyle\leq\beta_{1}t\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{t}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right]+\beta_{2}\sqrt{\gamma^{-1}t\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{t}^{i}(\cdot\mid
a)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right]}.$

###### Proof.

For the $\beta_{1}$-part, we have

$\displaystyle\quad\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}\left[\sum_{k=1}\operatornamewithlimits{\mathbb{E}}_{a\sim\pi_{k}^{i}(\cdot\mid
s)}\left[{\beta_{1}}\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right]\right]$
$\displaystyle={\beta_{1}}\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}\left[\sum_{k=1}^{K}\left\langle\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\pi_{k}^{i}(\cdot\mid
s)}\left[\bm{\phi}(s,a)\bm{\phi}(s,a)^{\mathsf{T}}\right],\widehat{\Sigma}_{t,i}^{\dagger}\right]\right\rangle\right]$
$\displaystyle=\beta_{1}t\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{t}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right],$

which directly becomes the first part in the conclusion (where, again, we used
the configuration that $K=t$ and also the definition of
$\widetilde{\pi}_{t}$).

For the $\beta_{2}$-part, from the calculations in Equation B.7, we know

$\sum_{j=1}^{d}(\bm{\phi}(s,a))[j]\times\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}_{h}\times\mathcal{A}^{i}}(\widehat{\Sigma}_{t,i}^{\dagger}\bm{\phi}(s^{\prime},a^{\prime}))[j]\leq\sqrt{\gamma^{-1}}\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}.$

Utilizing Cauchy-Schwartz inequality and the fact that
$\operatornamewithlimits{\mathbb{E}}[\sqrt{X}]\leq\sqrt{\operatornamewithlimits{\mathbb{E}}[X]}$,
we can get

$\displaystyle\quad\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}\left[\sum_{k=1}^{K}\operatornamewithlimits{\mathbb{E}}_{a\sim\pi_{k}^{i}(\cdot\mid
s)}\left[\beta_{2}\sum_{j=1}^{d}\bm{\phi}(s,a)[j]\times\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}_{h}\times\mathcal{A}^{i}}(\widehat{\Sigma}_{t,i}^{\dagger}\bm{\phi}(s^{\prime},a^{\prime}))[j]\right]\right]\right]$
$\displaystyle\leq\beta_{2}\sqrt{\gamma^{-1}}\sqrt{K\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}\left[\sum_{k=1}^{K}\operatornamewithlimits{\mathbb{E}}_{a\sim\pi_{k}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right]\right]}$
$\displaystyle=\beta_{2}t\sqrt{\gamma^{-1}\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{t}^{i}(\cdot\mid
a)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right]}.$

Putting two parts together gives our conclusion. ∎

###  C.2 Summing Up $\operatornamewithlimits{\mathbb{E}}[{\textsc{Gap}}]$’s
Using Potentials

######  Theorem C.7.

Under the conditions of Theorem B.1, i.e., setting
$\eta=\Omega(\max\\{\frac{\sqrt{\gamma}}{H},\frac{\gamma}{\beta_{1}+\beta_{2}}\\})$,
${\beta_{1}}=\widetilde{\Omega}(\frac{dH}{\sqrt{K}})$,
$\beta_{2}=\widetilde{\Omega}(\frac{H}{K})$, and
$\gamma=\operatorname{\widetilde{\mathcal{O}}}(\frac{d}{K})$ for CCE-Approx
executions with parameter $K$ (which is set to $t$ in each epoch $t$ where 4
is violated), we have

$\sum_{t=1}^{T}\sum_{i=1}^{m}\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{t}}\left[\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}[{\textsc{Gap}}_{t}^{i}(s)]\right]=\operatorname{\widetilde{\mathcal{O}}}(md^{2}H\sqrt{T}),\quad\text{with
probability }1-\operatorname{\widetilde{\mathcal{O}}}(\delta).$

###### Proof.

For any $t$, let the last time 4 that was violated be $I_{t}$. Then
$\widetilde{\pi}_{t}=\widetilde{\pi}_{I_{t}}$ and
$\widehat{\Sigma}_{t,i}^{\dagger}=\widehat{\Sigma}_{I_{t},i}^{\dagger}$ by 4.
For any $\tau$, we denote $n_{\tau}$ as the number of indices such that
$I_{t}=\tau$. Throughout the proof, we use
$\eta_{t},\beta_{1,t},\beta_{2,t},\gamma_{t}$ to denote the
$\eta,\beta_{1},\beta_{2},\gamma$ used by CCE-Approx in the $t$-th epoch,
respectively. Recall the conclusion from Theorem C.2 (note that the LHS of
Theorem C.2 is
$\operatornamewithlimits{\mathbb{E}}[t\times{\textsc{Gap}}_{t}^{i}(s)]$),

$\displaystyle\quad\sum_{t=1}^{T}\sum_{i=1}^{m}\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{t}}\left[\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}[{\textsc{Gap}}_{t}^{i}(s)]\right]=\sum_{t=1}^{T}\sum_{i=1}^{m}\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{I_{t}}}\left[\operatornamewithlimits{\mathbb{E}}_{\textsc{Gap}}[{\textsc{Gap}}_{I_{t}}^{i}(s)]\right]$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{m}\operatorname{\widetilde{\mathcal{O}}}\Bigg{(}\frac{\eta_{I_{t}}^{-1}}{I_{t}}+\frac{d\beta_{1,I_{t}}^{-1}}{I_{t}}+\left(\eta_{I_{t}}H^{2}+\beta_{1,I_{t}}\right)\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{I_{t}}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{I_{t}}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{I_{t},i}^{\dagger}}^{2}\right]\right]+$
$\displaystyle\qquad\qquad\qquad\left(H\sqrt{\frac{d}{I_{t}}}+\beta_{2,I_{t}}\sqrt{\gamma_{I_{t}}^{-1}}\right)\sqrt{\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{I_{t}}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{I_{t}}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{I_{t},i}^{\dagger}}^{2}\right]\right]}\Bigg{)}.$

We focus on a single agent $i\in[m]$. For notational simplicity, we denote
$(s,a)\sim_{h}^{i}\pi$ as the state-action pair that agent $i\in[m]$ observes
in layer $h\in[H]$. The first two terms are bounded by
$\operatorname{\widetilde{\mathcal{O}}}(\sum_{t=1}^{T}(\eta_{t}^{-1}/t+d\beta_{1,t}^{-1}/t))$.
For the third term, we replace the coefficients with a sup:

$\displaystyle\quad\sum_{t=1}^{T}\operatorname{\widetilde{\mathcal{O}}}\left(\eta_{I_{t}}H^{2}+\beta_{1,I_{t}}\right)\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{I_{t}}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{I_{t}}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{{I_{t}},i}^{\dagger}}^{2}\right]\right]$
$\displaystyle\leq\sup_{t\in[T]}\left(t\eta_{t}H^{2}+t\beta_{1,t}\right)\operatorname{\widetilde{\mathcal{O}}}\left(\sum_{t=1}^{T}n_{t}\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\widetilde{\pi}_{t}}\left[\frac{1}{t}\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\right),$

where, for simplicity, we define $n_{t}$ as zero for those $t$ where 4 isn’t
violated. Similarly, for the last term, we replace the coefficients with a sup
and then apply Cauchy-Schwartz. We get

$\displaystyle\quad\sum_{t=1}^{T}\operatorname{\widetilde{\mathcal{O}}}\left(H\sqrt{\frac{d}{I_{t}}}+\beta_{2,I_{t}}\sqrt{\gamma_{I_{t}}^{-1}}\right)\sqrt{\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{I_{t}}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{I_{t}}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{I_{t},i}^{\dagger}}^{2}\right]\right]}$
$\displaystyle\leq\sup_{t\in[T]}\left(\sqrt{d}H+\beta_{2,t}\sqrt{\gamma_{t}^{-1}t}\right)\sum_{t=1}^{T}\sqrt{\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{I_{t}}}\left[\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}_{I_{t}}^{i}(\cdot\mid
s)}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{I_{t},i}^{\dagger}}^{2}\right]\right]}$
$\displaystyle\leq\sup_{t\in[T]}\left(\sqrt{d}H+\beta_{2,t}\sqrt{\gamma_{t}^{-1}t}\right)\sqrt{T}\sqrt{\sum_{t=1}^{T}n_{t}\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\widetilde{\pi}_{t}}\left[\frac{1}{t}\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]}.$

Thus the only thing we need to do before concluding the proof is to show that

$\sum_{t=1}^{T}n_{t}\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\widetilde{\pi}_{t}}\left[\frac{1}{t}\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]\text{
is small}.$ (C.2)

Indeed, this quantity is of order $\operatorname{\widetilde{\mathcal{O}}}(d)$
for all $i\in[m]$ and $h\in[H]$ w.p.
$1-\operatorname{\widetilde{\mathcal{O}}}(\delta)$: In Lemma C.8, we imitate
Lemma 10 of Cui et al. (2023) and conclude that Equation C.2 is of order
$\operatorname{\widetilde{\mathcal{O}}}(d)$ for any fixed $i\in[m]$ and
$h\in[H]$ w.p. $1-\delta/(2mH)$; taking a union bound then gives the
aforementioned fact.

To summarize, we have

$\displaystyle\quad\sum_{t=1}^{T}\sum_{i=1}^{m}\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{t}}\left[\operatornamewithlimits{\mathbb{E}}_{{\textsc{Gap}}}[{\textsc{Gap}}_{t}^{i}(s)]\right]$
$\displaystyle=\operatorname{\widetilde{\mathcal{O}}}\left(\sum_{t=1}^{T}\left(\frac{\eta_{t}^{-1}}{t}+d\frac{\beta_{1,t}^{-1}}{t}\right)+\sup_{t\in[T]}\left(t\eta_{t}H^{2}+t\beta_{1,t}\right)d+\sup_{t\in[T]}\left(\sqrt{d}H+\beta_{2,t}\sqrt{\gamma_{t}^{-1}t}\right)\sqrt{dT}\right),$

and we need to ensure that
$\eta_{t}=\Omega(\max\\{\frac{\sqrt{\gamma}_{t}}{H},\frac{\gamma_{t}}{\beta_{1,t}+\beta_{2,t}}\\})$,
${\beta_{1,t}}=\widetilde{\Omega}(\frac{dH}{\sqrt{t}})$,
$\beta_{2,t}=\widetilde{\Omega}(\frac{H}{t})$, and
$\gamma_{t}=\operatorname{\widetilde{\mathcal{O}}}(\frac{d}{t})$. Setting
$\eta_{t}=\widetilde{\Theta}(\frac{\sqrt{d}}{\sqrt{t}H})$,
${\beta_{1,t}}=\widetilde{\Omega}(\frac{dH}{\sqrt{t}})$,
$\beta_{2,t}=\widetilde{\Omega}(\frac{H}{t})$, and
$\gamma_{t}=\operatorname{\widetilde{\mathcal{O}}}(\frac{d}{t})$ gives

$\displaystyle\quad\sum_{t=1}^{T}\sum_{i=1}^{m}\operatornamewithlimits{\mathbb{E}}_{s\sim_{h}\widetilde{\pi}_{t}}\left[\operatornamewithlimits{\mathbb{E}}_{{\textsc{Gap}}}[{\textsc{Gap}}_{t}^{i}(s)]\right]$
$\displaystyle\leq
m\times\operatorname{\widetilde{\mathcal{O}}}\left(\sum_{t=1}^{T}\left(\frac{H}{\sqrt{dt}}+\frac{1}{H\sqrt{t}}\right)+(\sqrt{d}H\sqrt{T}+dH\sqrt{T})d+(\sqrt{d}H+H/\sqrt{d})\sqrt{dT}\right)$
$\displaystyle=\operatorname{\widetilde{\mathcal{O}}}(md^{2}H\sqrt{T}),$

as claimed. ∎

######  Lemma C.8.

For any agent $i\in[m]$ and layer $h\in[H]$, w.p. $1-\delta/(2mH)$, we have

$\sum_{t=1}^{T}n_{t}\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\widetilde{\pi}_{t}}\left[\frac{1}{t}\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]=\operatorname{\widetilde{\mathcal{O}}}(d).$

###### Proof.

For a $t$ where 4 is violated, recall the definition of
$\widehat{\Sigma}_{t,i}^{\dagger}$ in Equation 4.1 and the definition of
$\Sigma_{t,i}^{\text{cov}}$ in Equation B.6, we know
$\widehat{\Sigma}_{t,i}^{\dagger}=(\Sigma_{t,i}^{\text{cov}}+\gamma I)^{-1}$.
Also recall the choice of $\gamma=\widetilde{\Theta}(\frac{d}{t})$ in
Algorithm 2 and Corollary E.3 by Liu et al. (2023a) that says
$\Sigma_{t,i}\preceq
2\widetilde{\Sigma}_{t,i}^{\text{cov}}+\widetilde{\Theta}(\frac{d}{t})I$, we
have

$\frac{1}{t}\widehat{\Sigma}_{t,i}^{\dagger}=\left(t\Sigma_{t,i}^{\text{cov}}+t\gamma
I\right)^{-1}\preceq\left(t\Sigma_{t,i}+\widetilde{\Theta}(d)I\right)^{-1}=\left(\sum_{s=0}^{t-1}\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\widetilde{\pi}_{s}}[\bm{\phi}(s,a)\bm{\phi}(s,a)^{\mathsf{T}}]+\widetilde{\Theta}(d)I\right)^{-1}.$

Let $\text{Cov}_{h}^{i}(\pi)$ be the true covariance of $\pi$, i.e.,
$\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\pi}[\bm{\phi}(s,a)\bm{\phi}(s,a)^{\mathsf{T}}]$.
Equation C.2 becomes

$\text{\lx@cref{creftypecap~refnum}{eq:matrix version summation
lemma}}\leq\sum_{t=1}^{T}\left\langle
n_{t}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t}),\left(\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})+\widetilde{\Theta}(d)I\right)^{-1}\right\rangle.$

Note that
$\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})=\sum_{s=0}^{t-1}n_{s}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})$
for any $t$ where 4 is violated, thus Equation C.2 can be viewed as a matrix
version of $\sum_{t=I_{t}}(X_{t}/(\sum_{s=0}^{t-1}X_{s}))$ where
$X_{t}=n_{t}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t})$. We use the following
lemma by Zanette and Wainwright (2022, Lemma 11):

######  Lemma C.9 (Lemma 11 by Zanette and Wainwright (2022)).

For a random vector $\bm{\phi}\in\mathbb{R}^{d}$, scalar $\alpha>0$, and PSD
matrix $\Sigma$, suppose that
$\alpha\operatornamewithlimits{\mathbb{E}}[\lVert\bm{\phi}\rVert_{\Sigma^{-1}}^{2}]\leq
L$ where $L\geq e-1$, then

$\alpha\operatornamewithlimits{\mathbb{E}}[\lVert\bm{\phi}\rVert_{\Sigma^{-1}}^{2}]\leq
L\log\frac{\det(\Sigma+\alpha\operatornamewithlimits{\mathbb{E}}[\bm{\phi}\bm{\phi}^{\mathsf{T}}])}{\det(\Sigma)}\leq\alpha
L\operatornamewithlimits{\mathbb{E}}[\lVert\bm{\phi}\rVert_{\Sigma^{-1}}^{2}].$

In our case, we apply Lemma C.9 to all $t=I_{t}$ with $\alpha=n_{t}$,
$\Sigma=\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})+\widetilde{\Theta}(d)I$,
and the distribution as $\bm{\phi}(s,a)$ with
$(s,a)\sim_{h}^{i}\widetilde{\pi}_{t}$. We first calculate
$\alpha\operatornamewithlimits{\mathbb{E}}[\lVert\bm{\phi}\rVert_{\Sigma^{-1}}^{2}]$,
which is bounded by our potential construction and is in analog to Lemma 4 of
Cui et al. (2023):

######  Lemma C.10.

For any $t\in[T]$ where 4 is violated, we have the following w.p.
$1-\delta/(2mHT)$:

$n_{t}\langle\mathrm{Cov}_{h}^{i}(\widetilde{\pi}_{t}),\widehat{\Sigma}_{t,i}^{\dagger}\rangle=n_{t}\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\widetilde{\pi}_{t}}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]=\operatorname{\widetilde{\mathcal{O}}}(1).$

The proof of Lemma C.10 is presented shortly after.

Therefore, when defining
$L=\max_{t\in[T]}n_{t}\langle\mathrm{Cov}_{h}^{i}(\widetilde{\pi}_{t}),\widehat{\Sigma}_{t,i}^{\dagger}\rangle$,
we can conclude from Lemma C.9:

$\left\langle
n_{t}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t}),\left(\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})+\widetilde{\Theta}(d)I\right)^{-1}\right\rangle\leq
L\log\frac{\det(\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})+\widetilde{\Theta}(d)I+n_{t}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t}))}{\det(\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})+\widetilde{\Theta}(d)I)}.$

By telescoping and the fact that
$\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})=\sum_{s<t,s=I_{s}}n_{s}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})$,
we have

$\sum_{t=1}^{T}\left\langle
n_{t}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t}),\left(\sum_{s=0}^{t-1}\text{Cov}_{h}^{i}(\widetilde{\pi}_{s})+\widetilde{\Theta}(d)I\right)^{-1}\right\rangle\leq
L\log\frac{\det(\sum_{t=0}^{T}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t})+\widetilde{\Theta}(d)I)}{\det(\widetilde{\Theta}(d)I)},$

which is bounded by $\operatorname{\widetilde{\mathcal{O}}}(d)$ as
$L=\operatorname{\widetilde{\mathcal{O}}}(1)$ from Lemma C.10,
$\log\det(\sum_{t=0}^{T}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t})+\widetilde{\Theta}(d)I)\leq
d\log\frac{\text{Tr}(\sum_{t=0}^{T}\text{Cov}_{h}^{i}(\widetilde{\pi}_{t})+\widetilde{\Theta}(d)I)}{d}=\operatorname{\widetilde{\mathcal{O}}}(d\log(d+\frac{T}{d}))=\operatorname{\widetilde{\mathcal{O}}}(d)$,
and $\log\det(\widetilde{\Theta}(d)I)\geq 0$. ∎

###### Proof of Lemma C.10.

Recall the potential function definition in Equation 5.3, which says
$64\log\frac{8mHT}{\delta}\cdot\Psi_{t,h}^{i}=\sum_{\tau=1}^{t}\lVert\bm{\phi}(\widetilde{s}_{\tau,h},\widetilde{a}_{\tau,h}^{i})\rVert_{\widehat{\Sigma}_{\tau,i}^{\dagger}}^{2}$.
Suppose that the first time after $t$ that 4 is violated again is in epoch
$t_{1}$, then $\Psi_{t_{1},h}^{i}$ is the first potential to reach
$\Psi_{t,h}^{i}+1$, which means

$\sum_{\tau=t}^{t_{1}-1}\lVert\bm{\phi}(\widetilde{s}_{\tau,h},\widetilde{a}_{\tau,h}^{i})\rVert_{\widehat{\Sigma}_{\tau,i}^{\dagger}}^{2}\leq
64\log\frac{8mHT^{2}}{\delta},\quad\forall h\in[H].$

Fix a single $h\in[H]$. Recall that for all epochs where 4 is not violated, we
directly adopt the previous $\widetilde{\pi}_{t}$ and
$\widehat{\Sigma}_{t,i}^{\dagger}$. Hence,
$\widehat{\Sigma}_{\tau,i}^{\dagger}\equiv\widehat{\Sigma}_{t_{0},i}^{\dagger}$
for all $\tau\in[t,t_{1})$, and all such
$(\widetilde{s}_{\tau,h},\widetilde{a}_{\tau,h}^{i})$’s are also drawn from
the same $\widetilde{\pi}_{t}$. From Lemma E.9 (which is Lemma 48 of Cui et
al. (2023)), we know that

$\displaystyle\quad\langle\mathrm{Cov}_{h}^{i}(\widetilde{\pi}_{t}),\widehat{\Sigma}_{t,i}^{\dagger}\rangle=\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\widetilde{\pi}_{t}}\left[\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}\right]$
$\displaystyle\leq
2\frac{1}{t_{1}-t}\sum_{\tau=t}^{t_{1}-1}\lVert\bm{\phi}(\widetilde{s}_{\tau,h},\widetilde{a}_{\tau,h}^{i})\rVert_{\widehat{\Sigma}_{\tau,i}^{\dagger}}^{2}\leq\frac{128}{t-t_{0}}\log\frac{8mHT^{2}}{\delta},$

w.p. $1-\delta/(2mHT)$. Hiding all logarithmic factors gives our conclusion. ∎

##  Appendix D Proof of the Resulting Sample Complexity (Theorem 4.2)

###### Proof of Theorem 4.2.

We verify the conditions in Theorem 3.2. The first condition, i.e., Equation
A.1, is formalized as Theorem B.1, whose proof is in Appendix B. The second
condition, i.e., Equation A.2, is postponed to Section D.1. The third
condition, i.e., Equation A.3, is justified in Theorem C.1.

Then we can invoke the conclusion from Theorem 3.2 to conclude a sample
complexity of

$\displaystyle\quad\operatorname{\widetilde{\mathcal{O}}}\left(\max\\{\Gamma_{1},\Gamma_{2}\\}\times
m^{2}H^{3}L\epsilon^{-2}\times d_{\text{replay}}\log T\right)$
$\displaystyle=\operatorname{\widetilde{\mathcal{O}}}(m\times m^{2}H^{3}\times
d^{4}H^{2}\epsilon^{-2}\times
dmH)=\operatorname{\widetilde{\mathcal{O}}}(m^{4}d^{5}H^{6}\epsilon^{-2}),$

where $\Gamma_{1}=\Gamma_{2}=m$ (see Algorithms 2 and 3), $L=d^{4}H^{2}$ (from
Theorem C.1), and $d_{\text{replay}}=dmH$ (from Section E.5 of Wang et al.
(2023)). ∎

###  D.1 V-Approx Procedure by Wang et al. (2023) and Its Guarantee

In this section, we introduce the V-Approx procedure by Wang et al. (2023). In
Algorithm 3, we present the algorithm for linear Markov Games (i.e., the
Optimistic-Regress procedure in their Algorithm 3 is replaced by that in
Section E.1).

Algorithm 3 $\textsc{V-Approx}_{h}$ Subroutine for Independent Linear Markov
Games (Wang et al., 2023)

0: Previous-layer policy $\overline{\pi}$, current-layer policy
$\widetilde{\pi}$, next-layer V-function $\overline{V}$, sub-optimality gap
upper-bound Gap, epoch length $K$. Set regularization factor
$\lambda=\operatorname{\mathcal{O}}(\frac{d}{K}\log\frac{dK}{\delta})$.

1: for $i=1,2,\ldots,m$ do

2: for $k=1,2,\ldots,K$ do

3: For each agent $j\neq i$, execute $\overline{\pi}\circ\widetilde{\pi}$; for
agent $i$, execute $\overline{\pi}$ (i.e., the same as Algorithm 2). Record
the trajectory as
$\\{(s_{k,\mathfrak{h}},a_{k,\mathfrak{h}}^{i},\widehat{\ell}_{k,\mathfrak{h}}^{i})\\}_{\mathfrak{h}=1}^{H}$
where
$\widehat{\ell}_{k,h}^{i}\triangleq\widehat{\ell}_{k,\mathfrak{h}}^{i}+\overline{V}^{i}(s_{k,h+1}^{i})$.

4: Calculate
$\widehat{\bm{\theta}}_{h}^{i}=\operatornamewithlimits{\mathrm{argmin}}_{\bm{\theta}}\frac{1}{K}\sum_{k=1}^{K}(\langle\bm{\phi}(s_{k,h},a_{k,h}^{i}),\bm{\theta}\rangle-\ell_{k,h}^{i})+\lambda\lVert\bm{\theta}\rVert_{2}^{2}$.

5: For each $s\in\mathcal{S}_{h}$ and $a\in\mathcal{A}^{i}$, set
$\overline{Q}^{i}(s,a)=\min\\{\langle\bm{\phi}(s,a),\widehat{\bm{\theta}}_{h}^{i}\rangle+\frac{3}{2}\textsc{Gap}^{i}(s),H-h+1\\}$.

6: For each $s\in\mathcal{S}_{h}$, set
$\overline{V}^{i}(s)=\sum_{a\in\mathcal{A}^{i}}\widetilde{\pi}^{i}(a\mid
s)\overline{Q}^{i}(s,a)$.

7: end for

8: end for

9: return $\\{\overline{V}^{i}(\mathcal{S}_{h})\\}_{i\in[m]}$.

Similar to Section E.3 of Wang et al. (2023), we have the following lemma:

######  Lemma D.1.

Consider using Algorithm 3 with some roll-in policy $\overline{\pi}$ and
episode length $K$. Let $(\widetilde{\pi},{\textsc{Gap}})=\textsc{CCE-
Approx}_{h}(\overline{\pi},\overline{V},K)$. Then Algorithm 3 with parameters
$(\overline{\pi},\widetilde{\pi},\overline{V},{\textsc{Gap}},K)$ ensures that
it’s output $\overline{V}(\mathcal{S}_{h})$ satisfies the following with
probability $1-\delta$:

$\displaystyle\overline{V}^{i}(s)\in\bigg{[}\min\bigg{\\{}$
$\displaystyle\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}}\left[\big{(}\ell^{i}+\operatorname{\mathbb{P}}_{h+1}\overline{V}^{i}\big{)}(s,a)\right]+\phantom{2}{\textsc{Gap}}^{i}(s),H-h+1\bigg{\\}},$
$\displaystyle\operatornamewithlimits{\mathbb{E}}_{a\sim\widetilde{\pi}}\left[\big{(}\ell^{i}+\operatorname{\mathbb{P}}_{h+1}\overline{V}^{i}\big{)}(s,a)\right]+2{\textsc{Gap}}^{i}(s)\bigg{]},\quad\forall
i\in[m],s\in\mathcal{S}_{h}.$

###### Proof.

Consider a fixed $i\in[m]$ and $h\in[H]$. By Assumption 2.1, there exists
$\bm{\theta}_{h}^{i}$ such that

$\operatornamewithlimits{\mathbb{E}}[\widehat{\ell}_{k,h}^{i}\mid
s_{k,h},a_{k,h}^{i}]=\langle\bm{\phi}(s_{k,h},a_{k,h}^{i}),\bm{\theta}_{h}^{i}\rangle,\quad\forall
k\in[K].$

Let
$\widetilde{\Sigma}_{i,h}^{\text{reg}}=\frac{1}{K}\sum_{k=1}^{K}\bm{\phi}(s_{k,h},a_{k,h}^{i})\bm{\phi}(s_{k,h},a_{k,h}^{i})^{\mathsf{T}}+\lambda
I$ and
$\xi_{k,h}^{i}=\widehat{\ell}_{k,h}^{i}-\operatornamewithlimits{\mathbb{E}}[\widehat{\ell}_{k,h}^{i}\mid
s_{k,h},a_{k,h}^{i}]$. From Lemma 21 of Wang et al. (2023), we know when
$\lambda=\operatorname{\mathcal{O}}(\frac{d}{K}\log\frac{dK}{\delta})$, with
probability $1-\delta$,

$\left\lVert\sum_{k=1}^{K}\bm{\phi}(s_{k,h},a_{k,h}^{i})\xi_{k,h}^{i}\right\rVert_{(\overline{\Sigma}_{i,h})^{-1}}=\operatorname{\widetilde{\mathcal{O}}}(\sqrt{dH^{2}K}),$
(D.1)

where
$\overline{\Sigma}_{i,h}=\operatornamewithlimits{\mathbb{E}}_{(s,a)\sim_{h}^{i}\overline{\pi}}[\bm{\phi}(s,a)\bm{\phi}(s,a)^{\mathsf{T}}]$
(which is also the expectation of
$\bm{\phi}(s_{k,h},a_{k,h}^{i})\bm{\phi}(s_{k,h},a_{k,h}^{i})^{\mathsf{T}}$).
We also conclude from Lemma 22 of Wang et al. (2023) that
$\widetilde{\Sigma}_{i,h}^{\text{reg}}\succeq\frac{1}{2}(\overline{\Sigma}_{i,h}+\lambda
I)$. Therefore, for any $s\in\mathcal{S}_{h}$ and $a\in\mathcal{A}^{i}$, we
have

$\displaystyle\quad\left\lvert\bm{\phi}(s,a)^{\mathsf{T}}\widehat{\bm{\theta}}^{i}-\operatornamewithlimits{\mathbb{E}}[\widehat{\ell}_{k,h}^{i}\mid
s,a]\right\rvert$
$\displaystyle=\left\lvert\bm{\phi}(s,a)^{\mathsf{T}}(\widetilde{\Sigma}_{i,h}^{\text{reg}})^{-1}\left(\frac{1}{K}\sum_{k=1}^{K}\bm{\phi}(s_{k,h},a_{k,h}^{i})\bm{\phi}(s_{k,h},a_{k,h}^{i})^{\mathsf{T}}-\widetilde{\Sigma}_{i,h}^{\text{reg}}\right)\bm{\theta}_{k,h}^{i}\right\rvert+$
$\displaystyle\quad\frac{1}{K}\left\lvert\bm{\phi}(s,a)^{\mathsf{T}}(\widetilde{\Sigma}_{i,h}^{\text{reg}})^{-1}\sum_{k=1}^{K}\bm{\phi}(s_{k,h},a_{k,h}^{i})\xi_{k,h}^{i}\right\rvert$
$\displaystyle\leq\lVert\bm{\phi}(s,a)\rVert_{(\widetilde{\Sigma}_{i,h}^{\text{reg}})^{-1}}\times\left(\operatorname{\widetilde{\mathcal{O}}}\left(\sqrt{\frac{d}{K}}\right)+\operatorname{\widetilde{\mathcal{O}}}\left(\sqrt{\frac{dH^{2}}{K}}\right)\right),$

where the last step uses both Theorem E.5 and Equation D.1. Noticing that
$\widehat{\Sigma}_{t,i}^{\dagger}$ is also an empirical covariance of policy
$\overline{\pi}$, we can conclude that
$\lVert\bm{\phi}(s,a)\rVert_{(\widetilde{\Sigma}_{i,h}^{\text{reg}})^{-1}}=\operatorname{\mathcal{O}}(\lVert\bm{\phi}(s,a)\rVert_{(\overline{\Sigma}_{i,h}+\lambda
I)^{-1}})=\operatorname{\mathcal{O}}(\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}})$
from Corollaries E.3 and E.4. Consequently, the error in $\overline{V}^{i}(s)$
is no more than

$\displaystyle\quad\sum_{a\in\mathcal{A}^{i}}\widetilde{\pi}^{i}(a\mid
s)\left\lvert\bm{\phi}(s,a)^{\mathsf{T}}\widehat{\bm{\theta}}^{i}-\operatornamewithlimits{\mathbb{E}}[\widehat{\ell}_{k,h}^{i}\mid
s,a]\right\rvert=\operatorname{\widetilde{\mathcal{O}}}\left(\sqrt{\frac{dH^{2}}{K}}\sum_{a\in\mathcal{A}^{i}}\widetilde{\pi}^{i}(a\mid
s)\lVert\bm{\phi}(s,a)\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}\right)$
$\displaystyle=\operatorname{\widetilde{\mathcal{O}}}\left(\sqrt{\frac{dH^{2}}{K}}\frac{1}{K}\sum_{k=1}^{K}\sqrt{\left\lVert\operatornamewithlimits{\mathbb{E}}_{a\sim\pi_{k}^{i}(\cdot\mid
s)}[\bm{\phi}(s,a)]\right\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}}\right)\leq\operatorname{\widetilde{\mathcal{O}}}\left(\frac{1}{K}\sqrt{dH^{2}\sum_{k=1}^{K}\left\lVert\operatornamewithlimits{\mathbb{E}}_{a\sim\pi_{k}^{i}(\cdot\mid
s)}[\bm{\phi}(s,a)]\right\rVert_{\widehat{\Sigma}_{t,i}^{\dagger}}^{2}}\right),$

where the last step used Cauchy-Schwartz. Recall the definition of Gap from
Equation B.2, we can conclude that the total estimation error of V-Approx is
no more than $\frac{1}{2}{\textsc{Gap}}_{t}^{i}(s)$. Our claim then follows
from imitating the remaining arguments of Wang et al. (2023, Section E.3). ∎

##  Appendix E Auxiliary Lemmas

###  E.1 Magnitude-Reduced Estimators

The following lemma characterizes the Magnitude-Reduced Estimator (Dai et al.,
2023).

######  Lemma E.1 (Magnitude-Reduced Estimators (Dai et al., 2023)).

For a random variable $Z$, its magnitude-reduced estimator
$\widehat{Z}\triangleq Z-(Z)_{-}+\operatornamewithlimits{\mathbb{E}}[(Z)_{-}]$
where $(Z)_{-}\triangleq\min\\{Z,0\\}$ satisfies

$\operatornamewithlimits{\mathbb{E}}[\widehat{Z}]=\operatornamewithlimits{\mathbb{E}}[Z],\quad\operatornamewithlimits{\mathbb{E}}[(\widehat{Z})^{2}]\leq
6\operatornamewithlimits{\mathbb{E}}[Z^{2}],\quad\widehat{Z}\geq\operatornamewithlimits{\mathbb{E}}[(Z)_{-}].$

###### Proof.

The first conclusion follows from
$\operatornamewithlimits{\mathbb{E}}[\widehat{Z}]=\operatornamewithlimits{\mathbb{E}}[Z]-\operatornamewithlimits{\mathbb{E}}[(Z)_{-}]+\operatornamewithlimits{\mathbb{E}}[\operatornamewithlimits{\mathbb{E}}[(Z)_{-}]]=\operatornamewithlimits{\mathbb{E}}[Z]$.

For the second conclusion, by definition of $\widehat{Z}$,
$\operatornamewithlimits{\mathbb{E}}[(\widehat{Z})^{2}]=\operatornamewithlimits{\mathbb{E}}[(Z-(Z)_{-}+\operatornamewithlimits{\mathbb{E}}[(Z)_{-}])^{2}]\leq
2(\operatornamewithlimits{\mathbb{E}}[Z^{2}]+\operatornamewithlimits{\mathbb{E}}[(Z)_{-}^{2}]+\operatornamewithlimits{\mathbb{E}}[(Z)_{-}]^{2})$.
As $(Z)_{-}^{2}=\min\\{Z,0\\}^{2}\leq Z^{2}$,
$\operatornamewithlimits{\mathbb{E}}[(Z)_{-}^{2}]\leq\operatornamewithlimits{\mathbb{E}}[Z^{2}]$.
By Jensen’s inequality,
$\operatornamewithlimits{\mathbb{E}}[(Z)_{-}]^{2}\leq\operatornamewithlimits{\mathbb{E}}[(Z)_{-}^{2}]\leq\operatornamewithlimits{\mathbb{E}}[Z^{2}]$.
Hence, we arrive at the conclusion that
$\operatornamewithlimits{\mathbb{E}}[(\widehat{Z})^{2}]\leq
6\operatornamewithlimits{\mathbb{E}}[Z^{2}]$.

The last inequality follows from the fact that $Z-(Z)_{-}$ is $0$ if $Z<0$ and
$Z$ if $Z\geq 0$. Therefore,
$\widehat{Z}=Z-(Z)_{-}+\operatornamewithlimits{\mathbb{E}}[(Z)_{-}]\geq\operatornamewithlimits{\mathbb{E}}[(Z)_{-}]$,
as desired. ∎

###  E.2 Stochastic Matrix Concentration

We then present some stochastic matrix concentration results.

######  Lemma E.2 (Lemma A.4 by Dai et al. (2023)).

If $H_{1},H_{2},\ldots,H_{n}$ are i.i.d. $d$-dimensional PSD matrices such
that for all $i$: i) $\operatornamewithlimits{\mathbb{E}}[H_{i}]=H$, ii)
$H_{i}\preceq I$ a.s., and iii)
$H\succeq\frac{1}{dn}\left(\log\frac{d}{\delta}\right)I$, then

$-\sqrt{\frac{d}{n}\log\frac{d}{\delta}}H^{1/2}\preceq\frac{1}{n}\sum_{i=1}^{n}H_{i}-H\preceq\sqrt{\frac{d}{n}\log\frac{d}{\delta}}H^{1/2}\quad\text{with
probability }1-2\delta.$

The first corollary of Lemma E.2 is derived by Liu et al. (2023a, Corollary
10).

######  Corollary E.3.

If $H_{1},H_{2},\ldots,H_{n}$ are i.i.d. $d$-dimensional PSD matrices such
that for all $i$: i) $\operatornamewithlimits{\mathbb{E}}[H_{i}]=H$, and ii)
$H_{i}\preceq cI$ a.s. for some positive constant $c>0$, then

$H\preceq\frac{2}{n}\sum_{i=1}^{n}H_{i}+3c\cdot\frac{d}{n}\log\left(\frac{d}{\delta}\right)I\quad\text{with
probability }1-\delta.$

The second corollary is the opposite direction of Corollary E.3.

######  Corollary E.4.

For $H_{1},H_{2},\ldots,H_{n}$ i.i.d. PSD with expectation $H$ such that
$H_{i}\preceq cI$ a.s. for all $i$,

$\frac{1}{n}\sum_{i=1}^{n}H_{i}\preceq\frac{3}{2}H+3c\cdot\frac{d}{2n}\log\left(\frac{d}{\delta}\right)I\quad\text{with
probability }1-\delta.$

###### Proof.

The proof mostly follows from Corollary 10 of Liu et al. (2023a). Using the
fact that $H^{1/2}\preceq\frac{k}{2}H+\frac{1}{2k}$ for any $k>0$, we know
from Lemma E.2 that under the same conditions of Lemma E.2,

$\frac{1}{n}\sum_{i=1}^{n}H_{i}-H\preceq\sqrt{\frac{d}{n}\log\frac{d}{\delta}}H^{1/2}\preceq\frac{1}{2}H+\frac{d}{2n}\left(\log\frac{d}{\delta}\right)I\quad\text{with
probability }1-\delta.$

In other words,

$\frac{1}{n}\sum_{i=1}^{n}H_{i}\preceq\frac{3}{2}H+\frac{d}{2n}\left(\log\frac{d}{\delta}\right)I\quad\text{with
probability }1-\delta.$ (E.1)

Now we show Corollary E.4. For the case where
$\frac{d}{n}\log\frac{d}{\delta}\leq 1$, define
$\widetilde{H}_{i}=\frac{1}{2c}H_{i}+\frac{d}{2n}\left(\log\frac{d}{\delta}\right)I$.
Then
$\widetilde{H}_{i}\preceq\frac{1}{2c}cI+\frac{d}{2n}\left(\log\frac{d}{\delta}\right)I\preceq
I$. Moreover,
$\widetilde{H}=\operatornamewithlimits{\mathbb{E}}[\widetilde{H}_{i}]=\frac{1}{2c}H+\frac{d}{2n}\left(\log\frac{d}{\delta}\right)I$
also ensures
$\widetilde{H}\succeq\frac{1}{dn}\left(\log\frac{d}{\delta}\right)I$. Hence,
applying Equation E.1 to
$\widetilde{H}_{1},\widetilde{H}_{2},\ldots,\widetilde{H}_{n}$ gives

$\frac{1}{n}\sum_{i=1}^{n}\widetilde{H}_{i}\preceq\frac{3}{2}\widetilde{H}+\frac{d}{2n}\left(\log\frac{d}{\delta}\right)I\quad\text{with
probability }1-\delta.$

By the definitions of $\widetilde{H}_{i}$ and $\widetilde{H}$, we further have
the following, which shows our claim:

$\frac{1}{n}\sum_{i=1}^{n}H_{i}\preceq\frac{3}{2}\widetilde{H}+3c\cdot\frac{d}{2n}\left(\log\frac{d}{\delta}\right)I\quad\text{with
probability }1-\delta.$

The case of $\frac{d}{n}\log\frac{d}{\delta}>1$ is trivial because
$H_{i}\preceq
cI\preceq\frac{3}{2}c\left(\frac{d}{n}\log\frac{d}{\delta}\right)I$. ∎

A key fact from the above corollaries is Lemma 14 of Liu et al. (2023a), which
we include below.

######  Theorem E.5 (Lemma 14 of Liu et al. (2023a)).

For a $d$-dimensional distribution $\mathcal{D}$, let
$\bm{\phi}_{1},\bm{\phi}_{2},\ldots,\bm{\phi}_{n}$ be i.i.d. samples from
$\mathcal{D}$. Define
$\Sigma=\operatornamewithlimits{\mathbb{E}}_{\bm{\phi}\sim\mathcal{D}}[\bm{\phi}\bm{\phi}^{\mathsf{T}}]$
and
$\widetilde{\Sigma}=\frac{1}{n}\sum_{i=1}^{n}\bm{\phi}_{i}\bm{\phi}_{i}^{\mathsf{T}}$.
If $\widehat{\Sigma}^{\dagger}=(\widetilde{\Sigma}+\gamma I)^{-1}$ where
$\gamma=5\frac{d}{n}\log\frac{6d}{\delta}$, then with probability $1-\delta$,
we have

$\left\lVert(\gamma
I+\widetilde{\Sigma}-\Sigma)\bm{\theta}\right\rVert_{\widehat{\Sigma}^{\dagger}}^{2}=\operatorname{\mathcal{O}}\left(\frac{d}{n}\log\frac{d}{\delta}\right),\quad\forall\lVert\bm{\theta}\rVert_{2}\leq
1.$

###  E.3 Adaptive Freedman Inequality

In this paper, we will make use of the Adaptive Freedman Inequality proposed
by Lee et al. (2020, Theorem 2.2) and improved by Zimmert and Lattimore (2022,
Theorem 9), stated as follows.

######  Lemma E.6 (Theorem 9 of Zimmert and Lattimore (2022)).

For a sequence of martingale differences $\\{X_{i}\\}_{i=1}^{n}$ adapted to
the filtration $(\mathcal{F}_{i})_{i=0}^{n}$, suppose that
$\operatornamewithlimits{\mathbb{E}}[\lvert
X_{i}\rvert\mid\mathcal{F}_{i-1}]<\infty$ a.s. Then

$\sum_{i=1}^{n}X_{i}\leq
3\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]\log\frac{C}{\delta}}+2\max_{i=1,2,\ldots,n}X_{i}\log\frac{C}{\delta},\quad\text{with
probability }1-\delta,$

where

$C=2\max\left\\{1,\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]},\max_{i=1,2,\ldots,n}X_{i}\right\\}.$

A direct corollary of Lemma E.6 is the following lemma:

######  Lemma E.7.

For a sequence of random variables $\\{X_{i}\\}_{i=1}^{n}$ adapted to the
filtration $(\mathcal{F}_{i})_{i=0}^{n}$, let the conditional expectation of
$X_{i}$ be
$\mu_{i}\triangleq\operatornamewithlimits{\mathbb{E}}[X_{i}\mid\mathcal{F}_{i-1}]$.
Suppose that $\operatornamewithlimits{\mathbb{E}}[\lvert
X_{i}\rvert\mid\mathcal{F}_{i-1}]<\infty$ a.s. Then

$\sum_{i=1}^{n}(X_{i}-\mu_{i})\leq
3\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]}\log\frac{C}{\delta}+2\max_{i=1,2,\ldots,n}X_{i}\log\frac{C}{\delta},\quad\text{with
probability }1-\delta,$

where

$C=2\max\left\\{1,\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]},\max_{i=1,2,\ldots,n}X_{i}\right\\}.$

###### Proof.

We apply Lemma E.6 to the martingale difference sequence
$\\{X_{i}-\mu_{i}\\}_{i=1}^{n}$, giving

$\sum_{i=1}^{n}(X_{i}-\mu_{i})\leq
3\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[(X_{i}-\mu)^{2}\mid\mathcal{F}_{i-1}]\log\frac{C}{\delta}}+2\max_{i=1,2,\ldots,n}(X_{i}-\mu_{i})\log\frac{C}{\delta},\quad\text{with
probability }1-\delta.$

It is clear that $\max(X_{i}-\mu_{i})\leq\max
X_{i}+\sqrt{\sum_{i=1}^{n}\mu_{i}^{2}}$. Furthermore, we know that
$\operatornamewithlimits{\mathbb{E}}[(X_{i}-\mu_{i})^{2}\mid\mathcal{F}_{i-1}]=\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]-\mu_{i}^{2}$.
Putting these two parts together gives our conclusion. ∎

We also give the following variant of Lemma E.7:

######  Lemma E.8.

For a sequence of random variables $\\{X_{i}\\}_{i=1}^{n}$ adapted to the
filtration $(\mathcal{F}_{i})_{i=0}^{n}$, let the conditional expectation of
$X_{i}$ be
$\mu_{i}\triangleq\operatornamewithlimits{\mathbb{E}}[X_{i}\mid\mathcal{F}_{i-1}]$.
Suppose that $\operatornamewithlimits{\mathbb{E}}[\lvert
X_{i}\rvert\mid\mathcal{F}_{i-1}]<\infty$ a.s. Then

$\left\lvert\sum_{i=1}^{n}(X_{i}-\mu_{i})\right\rvert\leq
8\sqrt{2}\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]+\sum_{i=1}^{n}X_{i}^{2}}\log\frac{C}{\delta},\quad\text{with
probability }1-\delta,$

where

$C=2\sqrt{2}\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]+\sum_{i=1}^{n}X_{i}^{2}}.$

###### Proof.

Applying Lemma E.6 to the martingale difference sequence
$\\{X_{i}-\mu_{i}\\}_{i=1}^{n}$, the following inequality holds with
probability $1-\delta$:

$\sum_{i=1}^{n}(X_{i}-\mu_{i})\leq
3\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[(X_{i}-\mu_{i})^{2}\mid\mathcal{F}_{i-1}]\log\frac{C^{\prime}}{\delta}}+2\max_{i=1,2,\ldots,n}\\{X_{i}-\mu_{i}\\}\log\frac{C^{\prime}}{\delta},$

where

$C^{\prime}=2\max\left\\{1,\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[(X_{i}-\mu_{i})^{2}\mid\mathcal{F}_{i-1}]},\max_{i=1,2,\ldots,n}\\{X_{i}-\mu_{i}\\}\right\\}.$

Utilizing the fact that $(X_{i}-\mu_{i})^{2}\leq 2(X_{i}^{2}+\mu_{i}^{2})$ for
all $i$, we have

$\max_{i=1,2,\ldots,n}\\{X_{i}-\mu_{i}\\}\leq\sqrt{2\sum_{i=1}^{n}(X_{i}^{2}+\mu_{i}^{2})}.$

Hence, we can write

$\displaystyle\sum_{i=1}^{n}(X_{i}-\mu_{i})$ $\displaystyle\leq
4\sqrt{2}\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[(X_{i}-\mu_{i})^{2}\mid\mathcal{F}_{i-1}]+\sum_{i=1}^{n}(X_{i}^{2}+\mu_{i}^{2})}\log\frac{C^{\prime}}{\delta}$
$\displaystyle=4\sqrt{2}\sqrt{\sum_{i=1}^{n}\left(\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]-\mu_{i}^{2}\right)+\sum_{i=1}^{n}(X_{i}^{2}+\mu_{i}^{2})}\log\frac{C^{\prime}}{\delta}$
$\displaystyle=4\sqrt{2}\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]+\sum_{i=1}^{n}X_{i}^{2}}\log\frac{C^{\prime}}{\delta}.$

Similarly, $C^{\prime}\leq
2\sqrt{2}\sqrt{\sum_{i=1}^{n}\operatornamewithlimits{\mathbb{E}}[X_{i}^{2}\mid\mathcal{F}_{i-1}]+\sum_{i=1}^{n}X_{i}^{2}}=C$.
By exactly the same arguments, the same inequality also holds for
$\sum_{i=1}^{n}(\mu_{i}-X_{i})$. Our conclusion then follows. ∎

###  E.4 Relative Concentration Bounds

######  Lemma E.9 (Lemma 48 by Cui et al. (2023)).

Let $X_{1},X_{2},\ldots$ be i.i.d. random variables supported in $[0,1]$ and
let $\widehat{S}_{n}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$. Let $n$ be the stopping
time that $n=\min_{n}\\{n\mid\sum_{i=1}^{n}X_{i}\geq
64\log(4n_{\max})/\delta\\}$. Suppose that $n\leq n_{\max}$, then w.p.
$1-\delta$,
$\frac{1}{2}\widehat{S}_{n}\leq\operatornamewithlimits{\mathbb{E}}[X]\leq\frac{3}{2}\widehat{S}_{n}$.

###  E.5 EXP3 Regret Guarantee

The following lemma is a classical result for the EXP3 algorithm. For
completeness, we also include the proof by Dai et al. (2023, Lemma C.1) here.

######  Lemma E.10.

Let $x_{0},x_{1},x_{2},\ldots,x_{T}\in\mathbb{R}^{A}$ be defined as

$x_{t+1,i}=\left.\left(x_{t,i}\exp(-\eta
c_{t,i})\right)\middle/\left(\sum_{i^{\prime}=1}^{A}x_{t,i^{\prime}}\exp(-\eta
c_{t,i^{\prime}})\right)\right.,\quad\forall 0\leq t<T,$

where $c_{t}\in\mathbb{R}^{A}$ is the loss corresponding to the $t$-th
iteration. Suppose that $\eta c_{t,i}\geq-1$ for all $t\in[T]$ and $i\in[A]$.
Then

$\sum_{t=1}^{T}\langle x_{t}-y,c_{t}\rangle\leq\frac{\log
A}{\eta}+\eta\sum_{t=1}^{T}\sum_{i=1}^{A}x_{t,i}c_{t,i}^{2}$

holds for any distribution $y\in\triangle([A])$ when
$x_{0}=(\frac{1}{A},\frac{1}{A},\ldots,\frac{1}{A})$.

###### Proof.

By linearity, it suffices to prove the inequality for all one-hot $y$’s.
Without loss of generality, let $y=\bm{1}_{i^{\ast}}$ where $i^{\ast}\in[A]$.
Define $C_{t,i}=\sum_{t^{\prime}=1}^{t}c_{t^{\prime},i}$ as the prefix sum of
$c_{t,i}$. Let

$\Phi_{t}=\frac{1}{\eta}\ln\left(\sum_{i=1}^{A}\exp\left(-\eta
C_{t,i}\right)\right),$

then by definition of $x_{t}$, we have

$\displaystyle\Phi_{t}-\Phi_{t-1}$
$\displaystyle=\frac{1}{\eta}\ln\left(\frac{\sum_{i=1}^{A}\exp(-\eta
C_{t,i})}{\sum_{i=1}^{A}\exp(-\eta
C_{t-1,i})}\right)=\frac{1}{\eta}\ln\left(\sum_{i=1}^{A}x_{t,i}\exp(-\eta
c_{t,i})\right)$
$\displaystyle\overset{(a)}{\leq}\frac{1}{\eta}\ln\left(\sum_{i=1}^{A}x_{t,i}(1-\eta
c_{t,i}+\eta^{2}c_{t,i}^{2})\right)=\frac{1}{\eta}\ln\left(1-\eta\langle
x_{t},c_{t}\rangle+\eta^{2}\sum_{i=1}^{A}x_{t,i}c_{t,i}^{2}\right)$
$\displaystyle\overset{(b)}{\leq}-\langle
x_{t},c_{t}\rangle+\eta\sum_{i=1}^{A}x_{t,i}c_{t,i}^{2},$

where (a) used $\exp(-x)\leq 1-x+x^{2}$ for all $x\geq-1$ and (b) used
$\ln(1+x)\leq x$ (again for all $x\geq-1$). Therefore, summing over
$t=1,2,\ldots,T$ gives

$\displaystyle\sum_{t=1}^{T}\langle x_{t},c_{t}\rangle$
$\displaystyle\leq\Phi_{0}-\Phi_{T}+\eta\sum_{t=1}^{T}\sum_{i=1}^{A}x_{t,i}c_{t,i}^{2}$
$\displaystyle\leq\frac{\ln N}{\eta}-\frac{1}{\eta}\ln\left(\exp(-\eta
C_{T,i^{\ast}})\right)+\eta\sum_{t=1}^{T}\sum_{i=1}^{N}p_{t}(i)\ell_{t}^{2}(i)$
$\displaystyle\leq\frac{\ln
A}{\eta}+L_{T}(i^{\ast})+\eta\sum_{t=1}^{T}\sum_{i=1}^{A}x_{t,i}c_{t,i}^{2}.$

Moving $C_{t,i^{\ast}}$ to the LHS then shows the inequality for
$y=\bm{1}_{i^{\ast}}$. The result then extends to all $y\in\triangle([A])$ by
linearity. ∎