$\Delta^{t}\mathrel{\mathop{:}}=\frac{1}{2}\left((\lambda^{t})^{2}-(\lambda^{t-1})^{2}\right)$
be the drift of the consecutive dual updates. Then,

$\begin{array}[]{rcl}\Delta^{t}&=&\displaystyle\frac{1}{2}\left((\lambda^{t})^{2}-(\lambda^{t-1})^{2}\right)\\\\[5.69046pt]
&=&\displaystyle\frac{1}{2}\left(\max\\!^{2}\Big{(}\lambda^{t-1}\,+\,\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle+\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle-b\big{)},\;0\Big{)}-(\lambda^{t-1})^{2}\right)\\\\[5.69046pt]
&\leq&\displaystyle\lambda^{t-1}\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle+\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle-b\big{)}\,+\,\frac{1}{2}\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle+\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle-b\big{)}^{2}\\\\[5.69046pt]
&\leq&\displaystyle\lambda^{t-1}\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle+\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle-b\big{)}\,+\,2L^{2}\end{array}$
(32)

where the first inequality is due to $\max^{2}(x,0)\leq x^{2}$ and we apply
$\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle$,
$\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle$, $b\in[0,L]$ in the last
inequality. Adding (32) to (31) from both sides of the inequalities without
changing the inequality direction yields

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\Delta^{t}\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle+\langle{q_{2}^{\star}},{h^{t-1}}\rangle-b\big{)}\,+\,2L^{2}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})+D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})\,-\,D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\,-\,D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}.\end{array}$
(33)

However,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&=&V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}-\widetilde{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\,+\,V\,\big{\langle}{\widetilde{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\,+\,V\,\big{\langle}{\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widetilde{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\,+\,V\,\big{\langle}{\widehat{q}_{1}^{\,t-1}\cdot\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\,+\,\eta^{-1}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})\,+\,\eta^{-1}D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\\\\[5.69046pt]
&\geq&-\,V\,\left\|{\widehat{q}_{2}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}\,-\,V\left\|{\widehat{q}_{2}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}\\\\[5.69046pt]
&&\,-\,V\,\left\|{\widehat{q}_{1}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widehat{q}_{2}^{\,t-1}-\widetilde{q}_{2}^{\,t-1}}\right\|_{1}\,-\,V\,\left\|{\widehat{q}_{1}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\\\\[5.69046pt]
&&\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}^{2}\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}}\right\|_{1}\\\\[5.69046pt]
&\geq&-\,V\,\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}\,-\,2\theta
VL\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}^{2}\\\\[5.69046pt]
&&\,-\,2\theta
VL\,-\,V\,\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}}\right\|_{1}\\\\[5.69046pt]
&\geq&\,-\,4\theta VL\,-\,\eta V^{2}L\end{array}$

where we apply the Hölder’s inequality and Lemma 11.3 in the first inequality,
the second inequality is due to that

$\begin{array}[]{rcl}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}&=&\displaystyle\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\left|(1-\theta)\widehat{q}_{1}^{\,t-1}(x,a)+\theta\frac{1}{|X_{\ell}||A|}-\widehat{q}_{1}^{\,t-1}(x,a)\right|\\\\[5.69046pt]
&\leq&\displaystyle\theta\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\widehat{q}_{1}^{\,t-1}(x,a)+\theta\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\frac{1}{|X_{\ell}||A|}\\\\[5.69046pt]
&=&2\theta L\end{array}$

and $\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t-1}}\|_{1}\leq 2\theta
L$ that can be proved similarly, and the last inequality is due to
$-bx+ax^{2}\geq-b^{2}/(4a)$ for any $a$, $b>0$. Therefore, we take the lower
bound above for the left-hand side of (33),

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\Delta^{t}\,-\,4\theta VL\,-\,\eta
V^{2}L\\\\[5.69046pt] &&\\!\\!\\!\\!\\!\\!\leq
V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle+\langle{q_{2}^{\star}},{h^{t-1}}\rangle-b\big{)}\,+\,2L^{2}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widetilde{q}_{1}^{t-1})+D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}.\end{array}$
(34)

By Lemma 11.5,

$\begin{array}[]{rcl}D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})&=&D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})+D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\\\\[5.69046pt]
&\leq&\theta
L\log(|X||A|)+D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\end{array}$

and, similarly,

$D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\;\leq\;\theta
L\log(|Y||B|)+D(q_{2}^{\star},\widehat{q}_{2}^{\,t-1})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t}).$

We now simplify (34) into

$\begin{array}[]{rcl}\Delta^{t}&\leq&V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle+\langle{q_{2}^{\star}},{h^{t-1}}\rangle-b\big{)}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})+D(q_{2}^{\star},\widehat{q}_{2}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\theta
L\big{(}\log(|X||A|)+\log(|Y||B|)\big{)}\,+\,2L^{2}\,+\,4\theta VL\,+\,\eta
V^{2}L\end{array}$

which leads to the desired result by summing it up from $t=1$ to $T$,

$\begin{array}[]{rcl}\displaystyle\sum_{t\,=\,1}^{T}\Delta^{t}&\leq&\displaystyle
V\sum_{t\,=\,1}^{T}\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\sum_{t\,=\,1}^{T}\lambda^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle+\langle{q_{2}^{\star}},{h^{t-1}}\rangle-b\big{)}\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\sum_{t\,=\,1}^{T}\big{(}D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})+D(q_{2}^{\star},\widehat{q}_{2}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\theta
LT\big{(}\log(|X||A|)+\log(|Y||B|)\big{)}\,+\,2L^{2}T\,+\,4\theta VLT\,+\,\eta
V^{2}LT\\\\[5.69046pt] &\leq&\displaystyle
V\sum_{t\,=\,1}^{T}\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\sum_{t\,=\,1}^{T}\lambda^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle+\langle{q_{2}^{\star}},{h^{t-1}}\rangle-b\big{)}\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widehat{q}_{1}^{\,0})+D(q_{2}^{\star},\widehat{q}_{2}^{\,0})\big{)}\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\theta
LT\big{(}\log(|X||A|)+\log(|Y||B|)\big{)}\,+\,2L^{2}T\,+\,4\theta VLT\,+\,\eta
V^{2}LT\end{array}$

which leads to the desired result by noting that

$D(q_{1}^{\star},\widehat{q}_{1}^{\,0})\;\leq\;L\log(|X||A|),\;D(q_{2}^{\star},\widehat{q}_{2}^{\,0})\;\leq\;L\log(|Y||B|),\;\text{
and }\;\sum_{t\,=\,1}^{T}\Delta^{t}\;\geq\;0.$

##  12 Proofs of Lemma 7.4 and Lemma 7.5

We first present the boundedness of the dual update $\lambda^{t}$ in Lemma
7.4. Our proof is based on a new drift analysis in Lemma 15.1 that has been
established in Yu et al. (2017) for providing a high probability bound for
stochastic processes.

######  Proof 12.1 (Proof of Lemma 7.4).

Let ${\mathcal{F}}^{t}$ be an $\sigma$-algebra that is generated by the state-
action sequence, reward/utility functions for both players up to episode $t$.
At the beginning, ${\mathcal{F}}^{0}=\\{\emptyset,\Omega\\}$. We have a
discrete-time random process $\\{\lambda^{t},t\geq 0\\}$ that adapts to
${\mathcal{F}}^{t}$. It suffices to check all assumptions in Lemma 15.1.

By the dual update (10),

$\begin{array}[]{rcl}\left|\lambda^{t+1}-\lambda^{t}\right|&=&\left|\max\\!\Big{(}\lambda^{t}\,+\,\big{(}\langle{\widehat{q}_{1}^{\,t+1}},{g^{t}}\rangle+\langle{\widehat{q}_{2}^{\,t+1}},{h^{t}}\rangle-b\big{)},\;0\Big{)}-\lambda^{t}\right|\\\\[5.69046pt]
&\leq&\left|\langle{\widehat{q}_{1}^{\,t+1}},{g^{t}}\rangle+\langle{\widehat{q}_{2}^{\,t+1}},{h^{t}}\rangle-b\right|\\\\[5.69046pt]
&\leq&2L\end{array}$

where the first inequality is clear from two cases for $\max(\cdot)$ and the
second inequality is due to $\langle{\widehat{q}_{1}^{\,t+1}},{g^{t}}\rangle$,
$\langle{\widehat{q}_{2}^{\,t+1}},{h^{t}}\rangle\in[0,L]$, $b\in[0,2L]$.
Consequently,

$\lambda^{t+t_{0}}-\lambda^{t}\;=\;\sum_{s\,=\,t}^{t+t_{0}-1}\big{(}\lambda^{s+1}-\lambda^{s}\big{)}\;\leq\;\sum_{s\,=\,t}^{t+t_{0}-1}\left|\lambda^{s+1}-\lambda^{s}\right|\;\leq\;2t_{0}L$
(35)

which leads to
$\mathbb{E}[\,\lambda^{t+t_{0}}-\lambda^{t}\,|\,{\mathcal{F}}^{t}\,]\leq
2t_{0}L$. It is convenient to take $\delta_{\max}=2L$ in Lemma 15.1.

We next determine the validity of other assumptions in Lemma 15.1. Let us
denote the event in Lemma 3.1 by $\mathcal{E}_{\text{good}}$ and we have
$P(\mathcal{E}_{\text{good}})\geq 1-\delta$. We recall that the proof of Lemma
7.3 remains to be valid if we replace $q_{1}^{\star}$ by $\bar{q}_{1}$ and
$q_{2}^{\star}$ by $\bar{q}_{2}$ starting from (31). By doing so, it is ready
to obtain a similar result as (34): under the good event
$\mathcal{E}_{\text{good}}$ it holds for any $\tau$ that

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\Delta^{\tau}\,-\,4\theta
VL\,-\,\eta V^{2}L\\\\[5.69046pt]
&\leq&V\,\big{\langle}{\bar{q}_{1}\cdot\widehat{q}_{2}^{\,\tau-1}-\widehat{q}_{1}^{\,\tau-1}\cdot\bar{q}_{2}},{r^{\tau-1}}\big{\rangle}\,+\,\lambda^{\tau-1}\big{(}\langle{\bar{q}_{1}},{g^{\tau-1}}\rangle+\langle{\bar{q}_{2}},{h^{\tau-1}}\rangle-b\big{)}\,+\,2L^{2}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(\bar{q}_{1},\widetilde{q}_{1}^{\,\tau-1})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,\tau-1})-D(\bar{q}_{1},\widehat{q}_{1}^{\,\tau})-D(\bar{q}_{2},\widehat{q}_{2}^{\,\tau})\big{)}\end{array}$

or, equivalently,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!(\lambda^{\tau})^{2}\,-\,(\lambda^{\tau-1})^{2}\\\\[5.69046pt]
&\leq&2V\,\big{\langle}{\bar{q}_{1}\cdot\widehat{q}_{2}^{\,\tau-1}-\widehat{q}_{1}^{\,\tau-1}\cdot\bar{q}_{2}},{r^{\tau-1}}\big{\rangle}\,+\,2\lambda^{\tau-1}\big{(}\langle{\bar{q}_{1}},{g^{\tau-1}}\rangle+\langle{\bar{q}_{2}},{h^{\tau-1}}\rangle-b\big{)}\,+\,4L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}\big{(}D(\bar{q}_{1},\widetilde{q}_{1}^{\,\tau-1})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,\tau-1})-D(\bar{q}_{1},\widehat{q}_{1}^{\,\tau})-D(\bar{q}_{2},\widehat{q}_{2}^{\,\tau})\big{)}\,+\,8\theta
VL\,+\,2\eta V^{2}L.\end{array}$ (36)

We note that
$|\langle{\bar{q}_{1}\cdot\widehat{q}_{2}^{\,\tau}-\widehat{q}_{1}^{\,\tau}\cdot\bar{q}_{2}},{r^{\tau}}\rangle|\leq
L$. By summing both sides of (36) from $\tau=t+1$ to $\tau=t+t_{0}$,

$\begin{array}[]{rcl}(\lambda^{t+t_{0}})^{2}\,-\,(\lambda^{t})^{2}&\leq&\displaystyle
2t_{0}VL\,+\,\sum_{\tau\,=\,t}^{t+t_{0}-1}2\lambda^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle+\langle{\bar{q}_{2}},{h^{\tau}}\rangle-b\big{)}\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}\big{(}D(\bar{q}_{1},\widetilde{q}_{1}^{\,t})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,t})\big{)}\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\end{array}$

where we omit two non-positive terms. Taking the conditional expectation given
${\mathcal{F}}^{t}$ and $\mathcal{E}_{\text{good}}$ yields,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}\left[(\lambda^{t+t_{0}})^{2}\,-\,(\lambda^{t})^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&\displaystyle
2t_{0}VL\,+\,\sum_{\tau\,=\,t}^{t+t_{0}-1}2\mathbb{E}\left[\lambda^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle+\langle{\bar{q}_{2}},{h^{\tau}}\rangle-b\big{)}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}\mathbb{E}\left[D(\bar{q}_{1},\widetilde{q}_{1}^{\,t})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,t})\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt] &\leq&\displaystyle
2t_{0}VL\,-\,2\xi\sum_{\tau\,=\,t}^{t+t_{0}-1}\mathbb{E}\left[\lambda^{\tau}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt] &\leq&\displaystyle 2t_{0}VL\,-\,2\xi
t_{0}\mathbb{E}\left[\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,2\xi
t_{0}(t_{0}-1)L\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\end{array}$ (37)

where the second inequality is due to Lemma 11.5 and the fact: by the law of
total expectation, for any $\tau\geq t$,
${\mathcal{F}}^{t}\subset{\mathcal{F}}^{\tau}$ and

$\begin{array}[]{rcl}\mathbb{E}\left[\lambda^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle+\langle{\bar{q}_{2}},{h^{\tau}}\rangle-b\big{)}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]&=&\mathbb{E}\left[\mathbb{E}\left[\lambda^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle+\langle{\bar{q}_{2}},{h^{\tau}}\rangle-b\big{)}\,|\,{\mathcal{F}}^{\tau}\right]\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&=&\mathbb{E}\left[\lambda^{\tau}\mathbb{E}\left[\langle{\bar{q}_{1}},{g^{\tau}}\rangle+\langle{\bar{q}_{2}},{h^{\tau}}\rangle-b\right]\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&=&\mathbb{E}\left[\langle{\bar{q}_{1}},{g^{\tau}}\rangle+\langle{\bar{q}_{2}},{h^{\tau}}\rangle-b\right]\mathbb{E}\left[\lambda^{\tau}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&\,-\,\xi\,\mathbb{E}\left[\lambda^{\tau}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\end{array}$

where the inequality is due to the strict feasibility assumption on
$(\bar{q}_{1},\bar{q}_{2})$; the last inequality is due to that

$\sum_{\tau\,=\,t}^{t+t_{0}-1}\mathbb{E}\left[\lambda^{\tau}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\;\geq\;\sum_{\tau\,=\,t}^{t+t_{0}-1}\mathbb{E}\left[\lambda^{t}-2(\tau-t)L\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\;=\;\sum_{\tau\,=\,0}^{t_{0}-1}\mathbb{E}\left[\lambda^{t}-2\tau
L\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]$

which follows the fact $\lambda^{\tau}\geq\lambda^{t}-2(\tau-t)L$ for any
$\tau\geq t\geq 0$ if we note that $|\lambda^{t+1}-\lambda^{t}|\leq 2L$.
Hence, we can simplify (37) as

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}\left[(\lambda^{t+t_{0}})^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&\displaystyle\mathbb{E}\left[(\lambda^{t})^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,2\xi
t_{0}\mathbb{E}\left[\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,2\xi
t_{0}^{2}L\,+\,4t_{0}L^{2}\,+\,2t_{0}VL\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt]
&\leq&\displaystyle\mathbb{E}\left[(\lambda^{t})^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\xi
t_{0}\mathbb{E}\left[\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\xi
t_{0}\Theta\,+\,2\xi t_{0}^{2}L\,+\,4t_{0}L^{2}\,+\,2t_{0}VL\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt]
&=&\displaystyle\mathbb{E}\left[(\lambda^{t})^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\xi
t_{0}\mathbb{E}\left[\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\frac{1}{2}\xi^{2}t_{0}^{2}\\\\[5.69046pt]
&\leq&\displaystyle\left(\mathbb{E}\left[\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]-\frac{1}{2}\xi
t_{0}\right)^{2}\end{array}$

where we apply $\lambda^{t}\geq\Theta$ for the second inequality and we take
$\Theta$ in Lemma 15.1,

$\Theta\;=\;\frac{1}{2}\xi t_{0}+2t_{0}L\,+\,\frac{4L^{2}+8\theta VL+2\eta
V^{2}L+2VL}{\xi}\,+\,\frac{2L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))}{t_{0}\xi\eta}.$

Taking the square root and applying the Jensen’s inequality yield

$\mathbb{E}\left[\lambda^{t+t_{0}}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\;\leq\;\sqrt{\mathbb{E}\left[(\lambda^{t+t_{0}})^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]}\;\leq\;\mathbb{E}\left[\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]-\frac{1}{2}\xi
t_{0}$

which shows that
$\mathbb{E}\left[\lambda^{t+t_{0}}-\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\leq-\frac{1}{2}\xi
t_{0}$. Application of law of total expectation to this inequality and (35)
with $\delta<\frac{1}{12}$ yields

$\begin{array}[]{rcl}\mathbb{E}\left[\lambda^{t+t_{0}}-\lambda^{t}\,|\,{\mathcal{F}}^{t}\right]&=&P(\mathcal{E}_{\text{good}})\mathbb{E}\left[\lambda^{t+t_{0}}-\lambda^{t}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,P(\bar{\mathcal{E}}_{\text{good}})\mathbb{E}\left[\lambda^{t+t_{0}}-\lambda^{t}\,|\,{\mathcal{F}}^{t},\bar{\mathcal{E}}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&-\dfrac{1}{2}\xi
t_{0}\times(1-\delta)\,+\,2t_{0}L\times\delta\\\\[5.69046pt]
&\leq&-\dfrac{1}{4}\xi t_{0}\end{array}$

which verifies the assumption of Lemma 15.1 if we take $\zeta=\xi/4$.

We now have verified all assumptions of Lemma 15.1 with appropriate parameters
$\Theta$, $\delta_{\max}$, $\zeta$. For episode $t$, with probability
$1-\delta$ it holds that

$\begin{array}[]{rcl}\lambda^{t}&\leq&\displaystyle\Theta+t_{0}\delta_{\max}+t_{0}\frac{4\delta_{\max}^{2}}{\zeta}\log\left(\frac{8\delta_{\max}^{2}}{\zeta}\right)+t_{0}\frac{4\delta_{\max}^{2}}{\zeta}\log\frac{1}{\delta}.\end{array}$

We complete the proof by taking a union bound over $t=1,\cdots,T$.

With Lemma 7.4 in place, we are ready to prove Lemma 7.5.

######  Proof 12.2 (Proof of Lemma 7.5).

Let
$Z^{t}\mathrel{\mathop{:}}=\sum_{\tau\,=\,0}^{t-1}\lambda^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle+\langle{q_{2}^{\star}},{h^{\tau}}\rangle-b\big{)}$.
We note that

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}\left[Z^{t}\,|\,{\mathcal{F}}^{t-1}\right]\\\\[5.69046pt]
&=&\displaystyle\mathbb{E}\left[\sum_{\tau\,=\,0}^{t-1}\lambda^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle+\langle{q_{2}^{\star}},{h^{\tau}}\rangle-b\big{)}\,\bigg{|}\,{\mathcal{F}}^{t-1}\right]\\\\[5.69046pt]
&=&\displaystyle\mathbb{E}\left[\sum_{\tau\,=\,0}^{t-2}\lambda^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle+\langle{q_{2}^{\star}},{h^{\tau}}\rangle-b\big{)}\,\bigg{|}\,{\mathcal{F}}^{t-1}\right]\,+\,\lambda^{t-1}\mathbb{E}\left[\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle+\langle{q_{2}^{\star}},{h^{t-1}}\rangle-b\big{)}\,|\,{\mathcal{F}}^{t-1}\right]\\\\[5.69046pt]
&\leq&\displaystyle\mathbb{E}\left[\sum_{\tau\,=\,0}^{t-2}\lambda^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle+\langle{q_{2}^{\star}},{h^{\tau}}\rangle-b\big{)}\,\bigg{|}\,{\mathcal{F}}^{t-1}\right]\\\\[11.38092pt]
&=&\mathbb{E}\left[Z^{t-1}\right]\end{array}$

where the inequality is because of
$\mathbb{E}\left[\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle+\langle{q_{2}^{\star}},{h^{t-1}}\rangle-b\big{)}\,|\,{\mathcal{F}}^{t-1}\right]=\langle{q_{1}^{\star}},{g}\rangle+\langle{q_{2}^{\star}},{h}\rangle-b\leq
0$. Hence, $\\{Z^{t},t\geq 0\\}$ a supermartingale.

We also note that
$\left|Z^{t+1}-Z^{t}\right|=\lambda^{t}\left|\langle{q_{1}^{\star}},{g^{t}}\rangle+\langle{q_{2}^{\star}},{h^{t}}\rangle-b\right|\leq
2\lambda^{t}L$. Thus, if $|Z^{t+1}-Z^{t}|>c$ for some $c\in\mathbb{R}^{+}$,
then $\lambda^{t}>c/(2L)$. Let $Y^{t}\mathrel{\mathop{:}}=\lambda^{t}-c/(2L)$.
Therefore,

$\\{|Z^{t+1}-Z^{t}|>c\\}\;\subset\;\\{Y^{t}>0\\}.$

By Lemma 15.2,

$P\left(\sum_{t\,=\,0}^{T-1}\lambda^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle+\langle{q_{2}^{\star}},{h^{t}}\rangle-b\big{)}\geq
z\right)\;\leq\;{\rm
e}^{-z^{2}/(2c^{2}T)}\,+\,\sum_{\tau\,=\,0}^{T-1}P\left(\lambda^{t}>\frac{c}{2L}\right).$
(38)

By Lemma 7.4, with probability $1-\delta$ it holds for any $t$ that

$\lambda^{t}\;\leq\;\displaystyle\Theta+2t_{0}L+t_{0}\frac{64L^{2}}{\xi}\log\left(\frac{128L^{2}}{\xi}\right)+t_{0}\frac{64L^{2}}{\xi}\log\frac{1}{\delta}$

or, equivalently,

$P\left(\lambda^{t}\;\geq\;\displaystyle\Theta+2t_{0}L+t_{0}\frac{64L^{2}}{\xi}\log\left(\frac{128L^{2}}{\xi}\right)+t_{0}\frac{64L^{2}}{\xi}\log\frac{1}{\delta}\right)\;\leq\;\delta.$

If we take

$c\;=\;2\Theta
L+4t_{0}L^{2}+t_{0}\frac{128L^{3}}{\xi}\log\left(\frac{128L^{2}}{\xi}\right)+t_{0}\frac{128L^{3}}{\xi}\log\frac{1}{\delta}\;\text{
and }\;z\;=\;\sqrt{2Tc^{2}\log(1/(\delta T))}$

then (38) becomes

$P\left(\sum_{t\,=\,0}^{T-1}\lambda^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle+\langle{q_{2}^{\star}},{h^{t}}\rangle-b\big{)}\geq
z\right)\;\leq\;2\delta T$

which proves the desired result.

##  13 Proof of Theorem 7.9

By the dual update (10),

$\begin{array}[]{rcl}\lambda^{t}&=&\max\\!\Big{(}\lambda^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t},g^{t-1}\right\rangle+\left\langle\widehat{q}_{2}^{\,t},h^{t-1}\right\rangle-b\,\big{)},\;0\Big{)}\\\\[5.69046pt]
&\geq&\lambda^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t},g^{t-1}\right\rangle+\left\langle\widehat{q}_{2}^{\,t},h^{t-1}\right\rangle-b\,\big{)}\\\\[5.69046pt]
&=&\lambda^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t-1},g^{t-1}\right\rangle+\left\langle\widehat{q}_{2}^{\,t-1},h^{t-1}\right\rangle-b\,\big{)}\,+\,\left\langle\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1},g^{t-1}\right\rangle\,+\,\left\langle\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1},h^{t-1}\right\rangle\\\\[5.69046pt]
&\geq&\lambda^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t-1},g^{t-1}\right\rangle+\left\langle\widehat{q}_{2}^{\,t-1},h^{t-1}\right\rangle-b\,\big{)}\,-\,\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}\,-\,\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\end{array}$
(39)

where the last inequality is due to:
$\langle{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}},{g^{t-1}}\rangle\leq\|\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}\|_{1}\|g^{t-1}\|_{\infty}$,
$\langle{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}},{h^{t-1}}\rangle\leq\|\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}\|_{1}\|h^{t-1}\|_{\infty}$,
and $\|g^{t-1}\|_{\infty}$, $\|h^{t-1}\|_{\infty}\in[0,1]$. We note that
$\lambda^{0}=0$ from the initialization. Summing up both sides of (39) from
$t=1$ to $t=T$ leads to

$\sum_{t\,=\,0}^{T-1}\big{(}\left\langle\widehat{q}_{1}^{\,t},g^{t}\right\rangle+\left\langle\widehat{q}_{2}^{\,t},h^{t}\right\rangle-b\,\big{)}\;\leq\;\lambda^{T}\,+\,\sum_{t\,=\,1}^{T}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right).$
(40)

We recall $\widehat{q}_{1}^{\,t}\in\Delta(k_{1}^{t})$,
$\widehat{q}_{2}^{\,t}\in\Delta(k_{2}^{t})$ in the primal update (8) and
$\Delta(k_{1}^{t})$ and $\Delta(k_{2}^{t})$ in the confidence sets (11). To
bound
$\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}$,
we consider two cases: (i) $k_{1}^{t}=k_{1}^{t-1}$ and
$k_{2}^{t}=k_{2}^{t-1}$; (ii) either $k_{1}^{t}\neq k_{1}^{t-1}$ or
$k_{2}^{t}\neq k_{2}^{t-1}$.

Case (i). In this case, we have: $\widehat{q}_{1}^{\,t}$,
$\widehat{q}_{1}^{\,t-1}\in\Delta(k_{1}^{t})$, $\widehat{q}_{2}^{\,t}$,
$\widehat{q}_{2}^{\,t-1}\in\Delta(k_{2}^{t})$. We begin with the primal update
(8) and apply Lemma 11.1 with,

$f(x,y)|_{x\,=\,q_{1},\,y\,=\,q_{2}}\;=\;V\,\big{\langle}{q_{1}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot
q_{2}},{r^{t-1}}\big{\rangle}\,+\,\lambda^{t-1}\langle{q_{1}},{g^{t-1}}\rangle\,-\,\lambda^{t-1}\langle{q_{2}},{h^{t-1}}\rangle$

and $x^{\star}=\widehat{q}_{1}^{\,t}$, $y^{\star}=\widehat{q}_{2}^{\,t}$,
$x^{\prime}=\widetilde{q}_{1}^{\,t-1}$,
$y^{\prime}=\widetilde{q}_{2}^{\,t-1}$, $x=\widetilde{q}_{1}^{\,t-1}$, and
$y=\widetilde{q}_{2}^{\,t-1}$. Thus,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot\widetilde{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\,+\,\lambda^{t-1}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle\,-\,\lambda^{t-1}\langle{\widetilde{q}_{2}^{\,t-1}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{\widetilde{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\lambda^{t-1}\langle{\widetilde{q}_{1}^{\,t-1}},{g^{t-1}}\rangle\,-\,\lambda^{t-1}\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\,-\,\eta^{-1}\big{(}D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\big{)}.\end{array}$

or, equivalently,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\,+\,\eta^{-1}\big{(}D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{(\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t})\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot(\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1})},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\,+\,\lambda^{t-1}\langle{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle\,+\,\lambda^{t-1}\langle{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle.\end{array}$
(41)

We note that
$\langle{(\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t})\cdot\widehat{q}_{2}^{\,t-1}},{r^{t-1}}\rangle\leq\|(\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t})\cdot\widehat{q}_{2}^{\,t-1}\|_{1}\|{r^{t-1}}\|_{\infty}\leq\|\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}\|_{1}$,
and, similarly,
$\langle\widehat{q}_{1}^{\,t-1}\cdot(\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}),{r^{t-1}}\rangle\leq\|\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}\|_{1}$.
Thus, we can reduce (41) into

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\,+\,\eta^{-1}\big{(}D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&\leq&(V+\lambda^{t-1})\left(\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}+\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\right)\end{array}$

where the left-hand side can be lower bounded by Lemma 11.3,

$D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})\;\geq\;L^{-1}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}^{2}$
$D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\;\geq\;L^{-1}\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}^{2}.$

Then, we apply the inequality $(x+y)^{2}\leq 2(x^{2}+y^{2})$ and cancel a non-
negative term to obtain

$\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}+\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\;\leq\;2\eta
L(V+\lambda^{t-1}).$ (42)

By the definition of $\widetilde{q}_{1}^{\,t-1}$ and
$\widetilde{q}_{2}^{\,t-1}$,

$\begin{array}[]{rcl}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}&=&\displaystyle\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\left|(1-\theta)\widehat{q}_{1}^{\,t-1}(x,a)+\theta\frac{1}{|X_{\ell}||A|}-\widehat{q}_{1}^{\,t}(x,a)\right|\\\\[5.69046pt]
&\geq&\displaystyle\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\left((1-\theta)\left|\widehat{q}_{1}^{\,t-1}(x,a)-\widehat{q}_{1}^{\,t}(x,a)\right|-\theta\left(\frac{1}{|X_{\ell}||A|}+\widehat{q}_{1}^{\,t}(x,a)\right)\right)\\\\[5.69046pt]
&=&(1-\theta)\left\|{\widehat{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}-2\theta
L.\end{array}$

Similarly, we have
$\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\|_{1}\leq(1-\theta)\|{\widehat{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\|_{1}-2\theta
L$. Thus, we can further reduce (42) into

$\left\|{\widehat{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}+\|{\widehat{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\|_{1}\;\leq\;2\eta(1-\theta)^{-1}L(V+\lambda^{t-1})+4\theta(1-\theta)^{-1}L.$
(43)

Case (ii). In this case, either $\widehat{q}_{1}^{\,t}$,
$\widehat{q}_{1}^{\,t-1}$ or $\widehat{q}_{2}^{\,t}$,
$\widehat{q}_{2}^{\,t-1}$ might not have the same domain. For instance, when
$k_{1}^{t}>k_{1}^{t-1}$, it is possible that $\Delta(k_{1}^{t})$ becomes
different from $\Delta(k_{1}^{t-1})$. We note that $k_{1}^{t}>k_{1}^{t-1}$
only happens when episode $t$ is the first one that belongs to epoch
$k_{1}^{t}$. By Lemma 15.4, $k_{1}^{T}\leq\sqrt{T|X||A|}\log(8T/(|X||A|))$ and
$k_{2}^{T}\leq\sqrt{T|Y||B|}\log(8T/(|Y||B|))$ if we are given
$T\geq\max(|X||A|,|Y||B|)$.

We now combine two cases above for (40),

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\displaystyle\sum_{t\,=\,1}^{T}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\\\\[5.69046pt]
&=&\displaystyle\sum_{\begin{subarray}{c}1\,\leq\,t\,\leq\,T\\\
k_{1}^{t}\,=\,k_{1}^{k-1}\,\wedge\,k_{2}^{t}\,=\,k_{2}^{k-1}\end{subarray}}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\\\\[5.69046pt]
&&\displaystyle\,+\,\sum_{\begin{subarray}{c}1\,\leq\,t\,\leq\,T\\\
k_{1}^{t}\,=\,k_{1}^{k-1}\,\vee\,k_{2}^{t}\,=\,k_{2}^{k-1}\end{subarray}}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\\\\[5.69046pt]
&\leq&\displaystyle\sum_{\begin{subarray}{c}1\,\leq\,t\,\leq\,T\\\
k_{1}^{t}\,=\,k_{1}^{k-1}\,\wedge\,k_{2}^{t}\,=\,k_{2}^{k-1}\end{subarray}}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\,+\,2L(k_{1}^{T}+k_{2}^{T})\\\\[5.69046pt]
&\leq&\displaystyle
2\eta(1-\theta)^{-1}L\sum_{t\,=\,1}^{T}(V+\lambda^{t-1})+4\theta(1-\theta)^{-1}LT+2L(k_{1}^{T}+k_{2}^{T})\end{array}$

where the first inequality is due to:
$\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}\leq 2L$
and $\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\leq
2L$, and we apply (43) from the case (i) for the last inequality. Using the
bounds on $k_{1}^{T}$, $k_{2}^{T}$ in the case (ii), we conclude the desired
bound for (40),

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\displaystyle\sum_{t\,=\,0}^{T-1}\big{(}\left\langle\widehat{q}_{1}^{\,t},g^{t}\right\rangle+\left\langle\widehat{q}_{2}^{\,t},h^{t}\right\rangle-b\,\big{)}\\\\[5.69046pt]
&\leq&\displaystyle\lambda^{T}\,+\,\frac{2\eta
L}{1-\theta}\sum_{t\,=\,1}^{T}\lambda^{t-1}+\frac{2\eta
V+4\theta}{1-\theta}LT\\\\[5.69046pt]
&&\displaystyle+2L\left(\sqrt{T|X||A|}\log(8T/(|X||A|))+\sqrt{T|Y||B|}\log(8T/(|Y||B|))\right).\end{array}$

We complete the proof by noting $\lambda^{0}=0$, $V=L\sqrt{T}$, $\eta=1/(TL)$,
and $\theta=1/T$.

##  14 Constrained MGs with Side Constraints

In this section, we present a special case of Problem (4) that is described as
a zero-sum MG with side constraint (Singh and Hemachandra, 2014). Having
defined episodic MDPs and occupancy measures in Section 2, we can formulate a
constrained minimax problem in which the objective function is a sum of the
expected total rewards over $T$ episodes and the constraint is on two agent’
expected total utilities,

$\begin{array}[]{rcl}\operatorname*{minimize}\limits_{q_{1}\,\in\,\Delta(P_{1})}\,\,\operatorname*{maximize}\limits_{q_{2}\,\in\,\Delta(P_{2})}&&\\!\\!\\!\\!\displaystyle\sum_{t\,=\,0}^{T-1}\left\langle
q_{1}\cdot q_{2},r^{t}\right\rangle\\\\[11.38092pt]
\operatorname*{subject~{}to}&&\\!\\!\\!\\!\left\langle
q_{1},g\right\rangle\;\leq\;b_{1}\;\text{ and }\;\left\langle
q_{2},h\right\rangle\;\leq\;b_{2}\end{array}$ (44)

where we take $b_{1}$, $b_{2}\in(0,L]$ to avoid trivial cases since we note
that $\langle{q_{1}},{g}\rangle$, $\langle{q_{2}},{h}\rangle\in[0,L]$. The
side constraint corresponds to the limited use of budget/resource for each
player. It is straightforward to generalize it to account for multiple
constraints. When the transitions $P_{1}$ and $P_{2}$ are known, the occupancy
measure sets $\Delta(P_{1})$ and $\Delta(P_{2})$ define convex polytopes on
$q_{1}$ and $q_{2}$.

Let $(q_{1}^{\star},q_{2}^{\star})$ be a solution to Problem (44) in
hindsight. The existence of $(q_{1}^{\star},q_{2}^{\star})$ is well-known
under compactness of the constraint sets (Neumann, 1928; Rosen, 1965). Since
two constraints are decoupled, it is natural to define the usual Nash
equilibrium via two conditions (Altman and Shwartz, 2000; Daskalakis et al.,
2021): (i) $\sum_{t\,=\,0}^{T-1}\langle q_{1}^{\star}\cdot
q_{2}^{\star},r^{t}\rangle\leq\sum_{t\,=\,0}^{T-1}\langle q_{1}\cdot
q_{2}^{\star},r^{t}\rangle$ for any $q_{1}\in\Delta(P_{1})$ satisfying
$\langle{q_{1}},{g}\rangle\leq b_{1}$; (ii) $\sum_{t\,=\,0}^{T-1}\langle
q_{1}^{\star}\cdot q_{2},r^{t}\rangle\leq\sum_{t\,=\,0}^{T-1}\langle
q_{1}^{\star}\cdot q_{2}^{\star},r^{t}\rangle$ for any $q_{2}\in\Delta(P_{2})$
satisfying $\left\langle q_{2},h\right\rangle\leq b_{2}$. With this solution
concept, we define the regret for any algorithm that plays the game for $T$
episodes by

$\text{Regret}(T)\;=\;\sum_{t\,=\,0}^{T-1}\left(\left\langle q_{1}^{t}\cdot
q_{2}^{\star},r^{t}\right\rangle-\left\langle q_{1}^{\star}\cdot
q_{2}^{t},r^{t}\right\rangle\right)$ (45)

where two players take policies $\pi^{t}$ and $\mu^{t}$ in episode $t$ and
they define occupancy measures $q_{1}^{t}$ and $q_{2}^{t}$ under the true
transitions $P_{1}$ and $P_{2}$.

To measure the constraint satisfaction, we introduce the violation as a non-
negative part of accumulated constraint violations
$\langle{q_{1}^{t}},{g}\rangle-b_{1}$ and $\langle{q_{2}^{t}},{h}\rangle-
b_{2}$ over $T$ episodes,

$\\!\\!\\!\\!\text{Violation}_{1}(T)\,=\,\left[\sum_{t\,=\,0}^{T-1}\left(\left\langle
q_{1}^{t},g^{t}\right\rangle-b_{1}\right)\right]_{+}\,\text{ and
}\,\text{Violation}_{2}(T)\,=\,\left[\sum_{t\,=\,0}^{T-1}\left(\left\langle
q_{2}^{t},h^{t}\right\rangle-b_{2}\right)\right]_{+}.$ (46)

We next make an assumption that guarantees the existence of constrained Nash
equilibrium (Altman and Shwartz, 2000).

######  Assumption 2 (Feasibility)

There exists a joint policy $(\bar{\pi},\bar{\mu})$ associated to the
occupancy measure $(\bar{q}_{1},\bar{q}_{2})$ and $\xi>0$ such that
$\left\langle\bar{q}_{1},g\right\rangle+\xi\leq b_{1}$ and
$\left\langle\bar{q}_{2},h\right\rangle+\xi\leq b_{1}$.

###  14.1 Algorithm and Performance Guarantees

We now are ready to specialize Algorithm 1 to Problem (44). The only change is
to replace the primal-dual update (8) and (10) by the following optimistic
primal-dual mirror descent step.

Let us recall that the occupancy measures $q_{1}^{t}$ for the min-player and
$q_{2}^{t}$ for the max-player are defined over the true transitions $P_{1}$
and $P_{2}$ in episode $t$. The primal update of our algorithm maintains two
occupancy measures $\widehat{q}_{1}^{\,t}$, $\widehat{q}_{2}^{\,t}$ to
estimate $q_{1}^{t}$, $q_{2}^{t}$, separately. Although
$\widehat{q}_{1}^{\,t}$, $\widehat{q}_{2}^{\,t}$ do not necessarily come from
the true transitions $P_{1}$, $P_{2}$, they propose a min-policy $\pi^{t}$ for
the min-player and a max-policy $\mu^{t}$ for the max-player given by (7).

We can revise our Lagrangian-based design to update estimates
$\widehat{q}_{1}^{\,t}$ and $\widehat{q}_{2}^{\,t}$ as follows. Assume that
the transitions $P_{1}$ and $P_{2}$ are known. We consider a one-episode
constrained minimax problem based on reward/utility functions: $r^{t-1}$,
$g^{t-1}$, $h^{t-1}$, revealed at the end of episode $t-1$,

$\begin{array}[]{rcl}\operatorname*{minimize}\limits_{q_{1}\,\in\,\Delta(P_{1})}\,\,\operatorname*{maximize}\limits_{q_{2}\,\in\,\Delta(P_{2})}&&\\!\\!\\!\\!\left\langle
q_{1}\cdot q_{2},r^{t-1}\right\rangle\\\\[8.5359pt]
\operatorname*{subject~{}to}&&\\!\\!\\!\\!\left\langle
q_{1},g^{t-1}\right\rangle\;\leq\;b_{1}\;\text{ and }\;\left\langle
q_{2},h^{t-1}\right\rangle\;\leq\;b_{2}\end{array}$

where $\Delta(P_{1})$ and $\Delta(P_{2})$ are sets of valid occupancy measures
under $P_{1}$ and $P_{2}$, respectively. We apply the method of Lagrange
multipliers (Bertsekas, 2014) to deal with constraints by formulating a
generalized Lagrangian-based function,

$\begin{array}[]{rcl}L^{t}(q_{1},q_{2};\lambda_{1},\lambda_{2})&\mathrel{\mathop{:}}=&\langle{q_{1}\cdot
q_{2}},{r^{t-1}}\rangle\,+\,\lambda_{1}\big{(}\langle{q_{1}},{g^{t-1}}\rangle-
b_{1}\big{)}\,-\,\lambda_{2}\big{(}\langle{q_{2}},{h^{t-1}}\rangle-
b_{2}\big{)}\end{array}$

where $q_{1}$ is the first primal variable for the min-player, $q_{2}$ is the
second primal variable for the max-player, and $\lambda_{1}$, $\lambda_{2}\geq
0$ work as the Lagrange multiplier or the dual variable in penalizing the min-
player/max-player via the first/second $\lambda$-term. Once we update
$\lambda_{1}=\lambda_{1}^{t-1}$ and $\lambda_{2}=\lambda_{2}^{t-1}$ from the
last episode, we reach a constrained saddle-point problem,

$\operatorname*{minimize}_{q_{1}\,\in\,\Delta(P_{1})}\,\operatorname*{maximize}_{q_{2}\,\in\,\Delta(P_{2})}\;\;L^{t}(q_{1},q_{2};\lambda_{1}^{t-1},\lambda_{2}^{t-1}).$

However, it is not feasible to take the domains $\Delta(P_{1})$ and
$\Delta(P_{2})$ since the true transitions $P_{1}$ and $P_{2}$ are unknown.
Instead, we use their optimistic estimates $\Delta(k_{1}^{t})$ and
$\Delta(k_{2}^{t})$ in sense that $q_{1}^{t}\in\Delta(k_{1}^{t})$ and
$q_{2}^{t}\in\Delta(k_{2}^{t})$ hold with high probability; see Lemma 3.1.
Denote
$\widehat{q}^{\,t}\mathrel{\mathop{:}}=(\widehat{q}_{1}^{\,t},\widehat{q}_{2}^{\,t})$.
By the linear approximation of $L^{t}(q_{1},q_{2};\lambda^{t-1})$ at the
previous iterate $(q_{1}^{t-1},q_{2}^{t-1})$, we update the primal variable
via an online mirror descent step over the optimistic domains of $q_{1}$ and
$q_{2}$,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\widehat{q}^{t}\,\leftarrow\,\displaystyle\operatorname*{argmin}_{q_{1}\,\in\,\Delta(k_{1}^{t})}\operatorname*{argmax}_{q_{2}\,\in\,\Delta(k_{2}^{t})}\Big{(}V\,\big{\langle}{q_{1}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot
q_{2}},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\,+\,\lambda_{1}^{t-1}\langle{q_{1}},{g^{t-1}}\rangle\,-\,\lambda_{2}^{t-1}\langle{q_{2}},{h^{t-1}}\rangle\,+\,\displaystyle\eta^{-1}D\big{(}q\,|\,\widetilde{q}^{\,t-1}\big{)}\Big{)}\end{array}$
(47)

where $V$, $\eta>0$ are some regularization parameters, $D(\cdot\,|\,\cdot)$
is the unnormalized Kullback-Leibler divergence with a slightly abuse in a way
that
$D(q\,|\,q^{\prime})\mathrel{\mathop{:}}=D(q_{1}\,|\,q_{1}^{\prime})-D(q_{2}\,|\,q_{2}^{\prime})$,
$\widetilde{q}_{1}^{\,t-1}$ and $\widetilde{q}_{2}^{\,t-1}$ are mixing
policies given by (9). The unnormalized Kullback-Leibler (KL) divergence
between two distributions $p$, $q$ is defined by
$D(p\,|\,q)\mathrel{\mathop{:}}=\sum_{i}p_{i}\ln\frac{p_{i}}{q_{i}}-\sum_{i}(p_{i}-q_{i})$.
Moreover, (47) has an efficient update that is similar as the one in Appendix
8.

Once we obtain $\widehat{q}^{\,t}$, we next perform the dual update. We treat
two $\lambda$-related regularization terms in
$L^{t}(\widehat{q}_{1}^{\,t},\widehat{q}_{2}^{\,t};\lambda_{1},\lambda_{2})$,
separately. The dual update works for each player in the usual way by adding
up all past constraint violations,

$\lambda_{1}^{t}\;=\;\max\big{(}\lambda_{1}^{t-1}\,+\,(\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle-
b_{1}\,),\,0\big{)}\;\,\text{ and
}\;\,\lambda_{2}^{t}\;=\;\max\big{(}\lambda_{2}^{t-1}\,+\,(\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle-
b_{2}\,),\,0\big{)}.$ (48)

The dual update (48) increases $\lambda_{1}^{t-1}$ when
$\widehat{q}_{1}^{\,t}$ violates the approximate constraint
$\langle{q_{1}},{g^{t-1}}\rangle\leq b_{1}$; it is similar for
$\lambda_{2}^{t-1}$. Once we replace the primal-dual update (8) and (10) in
line 4 of Algorithm 1 by (47) and (48), we obtain a new version of Algorithm 1
for Problem (44).

Similar to Theorem 4.1, we have the following bounds on the regret and the
constraint violation.

######  Theorem 14.1 (Regret Bound and Constraint Violation).

Let Assumption 2 hold. Fix $p\in\left(0,1\right)$ and
$T\geq\max(|X||A|,|B||Y|)$. In Algorithm 1 with the primal-dual update (47)
and (48), we set $V=L\sqrt{T}$, $\eta=1/(TL)$, and $\theta=1/T$. Then, the
regret (5) and the constraint violation (6) satisfy

$\begin{array}[]{rcl}\text{Regret}(T)&\leq&\widetilde{O}\big{(}(|X|+|Y|)L\sqrt{T(|A|+|B|)}\big{)}\\\\[5.69046pt]
\text{Violation}_{1}(T),\text{Violation}_{2}(T)&\leq&\widetilde{O}\big{(}(|X|+|Y|)L\sqrt{T(|A|+|B|)}\big{)}\end{array}$

with probability $1-p$, where $\widetilde{O}(\cdot)$ hides factor
$\log\tfrac{1}{p}$.

We analyze Algorithm 1 with the primal-dual update (47) and (48) by following
the proof idea in Appendix 7. For completeness, we provide proof details in
next two sections.

###  14.2 Regret Analysis

We recall that our algorithm maintains the occupancy measures
$(\widehat{q}_{1}^{\,t},\widehat{q}_{2}^{\,t})$ for estimating policies
$(\pi^{t},\mu^{t})$ and Problem (44) defines the comparison solution
$(q_{1}^{\star},q_{2}^{\star})$ in hindsight. We decompose the regret (45) as
follows,

$\begin{array}[]{rcl}\text{Regret}(T)&=&\displaystyle\underbrace{\sum_{t\,=\,0}^{T-1}\big{\langle}{\widehat{q}_{1}^{\,t}\cdot
q_{2}^{\star}-q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t}},{r^{t}}\big{\rangle}}_{\widehat{\text{Regret}}(T)}\,+\,\underbrace{\sum_{t\,=\,0}^{T-1}\left\langle(q_{1}^{t}-\widehat{q}_{1}^{\,t})\cdot
q_{2}^{\star},r^{t}\right\rangle}_{\text{Error}_{1}}\,+\,\underbrace{\sum_{t\,=\,0}^{T-1}\left\langle
q_{1}^{\star}\cdot(\widehat{q}_{2}^{\,t}-q_{2}^{t}),r^{t}\right\rangle}_{\text{Error}_{2}}\end{array}$

where ${\text{Error}_{1}}$ is the error of using $\widehat{q}_{1}^{\,t}$ for
the min-player and ${\text{Error}_{2}}$ is the error of using
$\widehat{q}_{2}^{\,t}$ for the max-player. By the occupancy measures in
Algorithm 1, ${\text{Error}_{1}}$ and ${\text{Error}_{2}}$ take the bounds in
Lemma 7.2. However, we need to develop a new upper bound for
${\widehat{\text{Regret}}(T)}$ as follows.

######  Lemma 14.2.

Fix $\delta\in(0,1)$. Then, with probability $1-\delta$,

$\begin{array}[]{rcl}\displaystyle{\widehat{\text{Regret}}(T)}&\leq&\displaystyle
V^{-1}\sum_{t\,=\,0}^{T-1}\left(\lambda_{1}^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle-
b_{1}\big{)}\,+\,\lambda_{2}^{t}\big{(}\langle{q_{2}^{\star}},{h^{t}}\rangle-
b_{2}\big{)}\right)\\\\[5.69046pt] &&\displaystyle\,+\,(\eta V)^{-1}L(1+\theta
T)\big{(}\log(|X||A|)+\log(|Y||B|)\big{)}\,+\,(2V^{-1}L+4\theta+\eta
V)LT.\end{array}$

######  Proof 14.3.

By Lemma 3.1, with probability $1-\delta$ it holds that

$\Delta(P_{1})\;\subset\;\cap_{t\,=\,0}^{T-1}\Delta(k_{1}^{t})\;\text{ and
}\;\Delta(P_{2})\;\subset\;\cap_{t\,=\,0}^{T-1}\Delta(k_{2}^{t}).$

We note that the solution $(q_{1}^{\star},q_{2}^{\star})$ in hindsight to
Problem (44) satisfies $q_{1}^{\star}\in\Delta(P_{1})$ and
$q_{2}^{\star}\in\Delta(P_{2})$. Hence,
$q_{1}^{\star}\in\cap_{t\,=\,0}^{T-1}\Delta(k_{1}^{t})$ and
$q_{2}^{\star}\in\Delta(P_{2})\cap_{t\,=\,0}^{T-1}\Delta(k_{2}^{t})$ with
probability $1-\delta$. For episode $t$, we apply Lemma 11.1 to the primal
update (47) with

$f(x,y)|_{x\,=\,q_{1},\,y\,=\,q_{2}}\;=\;V\,\big{\langle}{q_{1}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot
q_{2}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{q_{1}},{g^{t-1}}\rangle\,-\,\lambda_{2}^{t-1}\langle{q_{2}},{h^{t-1}}\rangle$

and $x^{\star}=\widehat{q}_{1}^{\,t}$, $y^{\star}=\widehat{q}_{2}^{\,t}$,
$x^{\prime}=\widetilde{q}_{1}^{\,t-1}$,
$y^{\prime}=\widetilde{q}_{2}^{\,t-1}$, $x=q_{1}^{\star}$, and
$y=q_{2}^{\star}$. Thus, with probability $1-\delta$ it holds for any $t$ that

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle\,-\,\lambda_{2}^{t-1}\langle{q_{2}^{\star}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{q_{1}^{\star}},{g^{t-1}}\rangle\,-\,\lambda_{2}^{t-1}\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})\,+\,D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})\,-\,D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\,-\,D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}\end{array}$

or, equivalently,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle\,+\,\lambda_{2}^{t-1}\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{q_{1}^{\star}},{g^{t-1}}\rangle\,+\,\lambda_{2}^{t-1}\langle{q_{2}^{\star}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})\,+\,D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})\,-\,D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\,-\,D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}.\end{array}$
(49)

Let
$\Delta_{1}^{t}\mathrel{\mathop{:}}=\frac{1}{2}\left((\lambda_{1}^{t})^{2}-(\lambda_{1}^{t-1})^{2}\right)$
be the drift of the first consecutive dual updates. Then,

$\begin{array}[]{rcl}\Delta_{1}^{t}&=&\displaystyle\frac{1}{2}\left((\lambda_{1}^{t})^{2}-(\lambda_{1}^{t-1})^{2}\right)\\\\[5.69046pt]
&=&\displaystyle\frac{1}{2}\left(\max\\!^{2}\Big{(}\lambda_{1}^{t-1}\,+\,\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle-
b_{1}\big{)},\;0\Big{)}-(\lambda_{1}^{t-1})^{2}\right)\\\\[5.69046pt]
&\leq&\displaystyle\lambda_{1}^{t-1}\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle-
b_{1}\big{)}\,+\,\frac{1}{2}\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle-
b_{1}\big{)}^{2}\\\\[5.69046pt]
&\leq&\displaystyle\lambda_{1}^{t-1}\big{(}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle-
b_{1}\big{)}\,+\,L^{2}\end{array}$ (50)

where the first inequality is due to $\max^{2}(x,0)\leq x^{2}$ and we apply
$\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle\in[0,L]$, $b_{1}\in[0,L]$ in
the last inequality. Similarly, if we let
$\Delta_{2}^{t}\mathrel{\mathop{:}}=\frac{1}{2}\left((\lambda_{2}^{t})^{2}-(\lambda_{2}^{t-1})^{2}\right)$,
then

$\Delta_{2}^{t}\;\leq\;\lambda_{2}^{t-1}\big{(}\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle-
b_{2}\big{)}\,+\,L^{2}.$ (51)

Adding (50) and (51) to (49) from both sides of the inequalities without
changing the inequality direction yields

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\Delta_{1}^{t}\,+\,\Delta_{2}^{t}\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle-
b_{1}\big{)}\,+\,\lambda_{2}^{t-1}\big{(}\langle{q_{2}^{\star}},{h^{t-1}}\rangle-
b_{2}\big{)}\,+\,2L^{2}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})+D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})\,-\,D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\,-\,D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}.\end{array}$
(52)

However,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&=&V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}-\widetilde{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\,+\,V\,\big{\langle}{\widetilde{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\,+\,V\,\big{\langle}{\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widetilde{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\,+\,V\,\big{\langle}{\widehat{q}_{1}^{\,t-1}\cdot\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\,+\,\eta^{-1}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})\,+\,\eta^{-1}D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\\\\[5.69046pt]
&\geq&-\,V\,\left\|{\widehat{q}_{2}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}\,-\,V\left\|{\widehat{q}_{2}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}\\\\[5.69046pt]
&&\,-\,V\,\left\|{\widehat{q}_{1}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widehat{q}_{2}^{\,t-1}-\widetilde{q}_{2}^{\,t-1}}\right\|_{1}\,-\,V\,\left\|{\widehat{q}_{1}^{\,t-1}\cdot
r^{t-1}}\right\|_{\infty}\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\\\\[5.69046pt]
&&\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}^{2}\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}}\right\|_{1}\\\\[5.69046pt]
&\geq&-\,V\,\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}\,-\,2\theta
VL\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{1}^{\,t}-\widetilde{q}_{1}^{\,t-1}}\right\|_{1}^{2}\\\\[5.69046pt]
&&\,-\,2\theta
VL\,-\,V\,\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\,+\,(2\eta
L)^{-1}\left\|{\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}}\right\|_{1}\\\\[5.69046pt]
&\geq&\,-\,4\theta VL\,-\,\eta V^{2}L\end{array}$

where we apply the Hölder’s inequality and Lemma 11.3 in the first inequality,
the second inequality is due to that

$\begin{array}[]{rcl}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}&=&\displaystyle\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\left|(1-\theta)\widehat{q}_{1}^{\,t-1}(x,a)+\theta\frac{1}{|X_{\ell}||A|}-\widehat{q}_{1}^{\,t-1}(x,a)\right|\\\\[5.69046pt]
&\leq&\displaystyle\theta\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\widehat{q}_{1}^{\,t-1}(x,a)+\theta\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\frac{1}{|X_{\ell}||A|}\\\\[5.69046pt]
&=&2\theta L\end{array}$

and $\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t-1}}\|_{1}\leq 2\theta
L$ that can be proved similarly, and the last inequality is due to
$-bx+ax^{2}\geq-b^{2}/(4a)$ for any $a$, $b>0$. Therefore, we take the lower
bound above for the left-hand side of (52),

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\Delta_{1}^{t}\,+\,\Delta_{2}^{t}\,-\,4\theta
VL\,-\,\eta V^{2}L\\\\[5.69046pt]
&\leq&V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle-
b_{1}\big{)}\,+\,\lambda_{2}^{t-1}\big{(}\langle{q_{2}^{\star}},{h^{t-1}}\rangle-
b_{2}\big{)}\,+\,2L^{2}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widetilde{q}_{1}^{t-1})+D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}.\end{array}$
(53)

By Lemma 11.5,

$\begin{array}[]{rcl}D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})&=&D(q_{1}^{\star},\widetilde{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})+D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\\\\[5.69046pt]
&\leq&\theta
L\log(|X||A|)+D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})\end{array}$

and, similarly,

$D(q_{2}^{\star},\widetilde{q}_{2}^{\,t-1})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\;\leq\;\theta
L\log(|Y||B|)+D(q_{2}^{\star},\widehat{q}_{2}^{\,t-1})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t}).$

We now simplify (53) into

$\begin{array}[]{rcl}\Delta_{1}^{t}\,+\,\Delta_{2}^{t}&\leq&V\,\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle-
b_{1}\big{)}\,+\,\lambda_{2}^{t-1}\big{(}\langle{q_{2}^{\star}},{h^{t-1}}\rangle-
b_{2}\big{)}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})+D(q_{2}^{\star},\widehat{q}_{2}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\theta
L\big{(}\log(|X||A|)+\log(|Y||B|)\big{)}\,+\,2L^{2}\,+\,4\theta VL\,+\,\eta
V^{2}L\end{array}$

which leads to the desired result by summing it up from $t=1$ to $T$,

$\begin{array}[]{rcl}\displaystyle\sum_{t\,=\,1}^{T}\big{(}\Delta_{1}^{t}+\Delta_{2}^{t}\big{)}&\leq&\displaystyle
V\sum_{t\,=\,1}^{T}\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\displaystyle\,+\,\sum_{t\,=\,1}^{T}\left(\lambda_{1}^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle-
b_{1}\big{)}+\lambda_{2}^{t-1}\big{(}\langle{q_{2}^{\star}},{h^{t-1}}\rangle-
b_{2}\big{)}\right)\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\sum_{t\,=\,1}^{T}\big{(}D(q_{1}^{\star},\widehat{q}_{1}^{\,t-1})+D(q_{2}^{\star},\widehat{q}_{2}^{\,t-1})-D(q_{1}^{\star},\widehat{q}_{1}^{\,t})-D(q_{2}^{\star},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\theta
LT\big{(}\log(|X||A|)+\log(|Y||B|)\big{)}\,+\,2L^{2}T\,+\,4\theta VLT\,+\,\eta
V^{2}LT\\\\[5.69046pt] &\leq&\displaystyle
V\sum_{t\,=\,1}^{T}\big{\langle}{q_{1}^{\star}\cdot\widehat{q}_{2}^{\,t-1}-\widehat{q}_{1}^{\,t-1}\cdot
q_{2}^{\star}},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\displaystyle\,+\,\sum_{t\,=\,1}^{T}\left(\lambda_{1}^{t-1}\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle-
b_{1}\big{)}+\lambda_{2}^{t-1}\big{(}\langle{q_{2}^{\star}},{h^{t-1}}\rangle-
b_{2}\big{)}\right)\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\big{(}D(q_{1}^{\star},\widehat{q}_{1}^{\,0})+D(q_{2}^{\star},\widehat{q}_{2}^{\,0})\big{)}\\\\[5.69046pt]
&&\displaystyle\,+\,\eta^{-1}\theta
LT\big{(}\log(|X||A|)+\log(|Y||B|)\big{)}\,+\,2L^{2}T\,+\,4\theta VLT\,+\,\eta
V^{2}LT\end{array}$

which leads to the desired result by noting that

$D(q_{1}^{\star},\widehat{q}_{1}^{\,0})\;\leq\;L\log(|X||A|),\;D(q_{2}^{\star},\widehat{q}_{2}^{\,0})\;\leq\;L\log(|Y||B|),\;\text{
and
}\;\sum_{t\,=\,1}^{T}\big{(}\Delta_{1}^{t}+\Delta_{2}^{t}\big{)}\;\geq\;0.$

To analyze the bound in Lemma 14.2, in Lemma 14.4, we next utilize a new drift
bound from Lemma 15.1 to establish the boundedness of
$\lambda^{t}\mathrel{\mathop{:}}=(\lambda_{1}^{t},\lambda_{2}^{t})$ first.
Then, we apply a general Azuma-Hoeffding inequality for supermartingales in
Lemma 14.6.

######  Lemma 14.4.

Let Assumption 2 hold. Fix $\delta\in(0,1)$. For any integer $t_{0}>0$, with
probability $1-T\delta$,

$\left\|{\lambda^{t}}\right\|\;\leq\;\displaystyle\Theta+2t_{0}L+t_{0}\frac{64L^{2}}{\xi}\log\left(\frac{128L^{2}}{\xi}\right)+t_{0}\frac{64L^{2}}{\xi}\log\frac{1}{\delta}$

for all $t=1,\ldots,T$, where $\xi>0$ and

$\begin{array}[]{rcl}\Theta&\mathrel{\mathop{:}}=&t_{0}\left(\tfrac{1}{2}\xi+2L\right)\,+\,\tfrac{4L^{2}+(8\theta+2\eta
V+2)VL}{\xi}\,+\,\tfrac{2L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))}{t_{0}\xi\eta}.\end{array}$

######  Proof 14.5.

Let ${\mathcal{F}}^{t}$ be an $\sigma$-algebra that is generated by the state-
action sequence, reward/utility functions for both players up to episode $t$.
At the beginning, ${\mathcal{F}}^{0}=\\{\emptyset,\Omega\\}$. We have a
discrete-time random process $\\{\left\|{\lambda^{t}}\right\|,t\geq 0\\}$ that
adapts to ${\mathcal{F}}^{t}$. It suffices to check all assumptions in Lemma
15.1.

By the dual update (48),

$\begin{array}[]{rcl}\left|\lambda_{1}^{t+1}-\lambda_{1}^{t}\right|&=&\left|\max\\!\Big{(}\lambda_{1}^{t}\,+\,\big{(}\langle{\widehat{q}_{1}^{\,t+1}},{g^{t}}\rangle-
b_{1}\big{)},\;0\Big{)}-\lambda_{1}^{t}\right|\\\\[5.69046pt]
&\leq&\left|\langle{\widehat{q}_{1}^{\,t+1}},{g^{t}}\rangle-
b_{1}\right|\\\\[5.69046pt] &\leq&L\end{array}$

where the first inequality is clear from two cases for $\max(\cdot)$ and the
second inequality is due to
$\langle{\widehat{q}_{1}^{\,t+1}},{g^{t}}\rangle\in[0,L]$, $b_{1}\in[0,L]$.
Similarly, $\left|\lambda_{2}^{t+1}-\lambda_{2}^{t}\right|\leq L$. Hence,

$\left|\left\|{\lambda^{t+1}}\right\|-\left\|{\lambda^{t}}\right\|\right|\;\leq\;\left\|{\lambda^{t+1}-\lambda^{t}}\right\|\;=\;\sqrt{(\lambda_{1}^{t+1}-\lambda_{1}^{t})^{2}+(\lambda_{2}^{t+1}-\lambda_{2}^{t})^{2}}\;\leq\;{2}L.$

Consequently,

$\left\|{\lambda}\right\|^{t+t_{0}}-\left\|{\lambda}\right\|^{t}\;=\;\sum_{s\,=\,t}^{t+t_{0}-1}\big{(}\left\|{\lambda}\right\|^{s+1}-\left\|{\lambda}\right\|^{s}\big{)}\;\leq\;\sum_{s\,=\,t}^{t+t_{0}-1}\left|\left\|{\lambda}\right\|^{s+1}-\left\|{\lambda}\right\|^{s}\right|\;\leq\;2t_{0}L$
(54)

which leads to
$\mathbb{E}[\,\left\|{\lambda}\right\|^{t+t_{0}}-\left\|{\lambda}\right\|^{t}\,|\,{\mathcal{F}}^{t}\,]\leq
2t_{0}L$. It is convenient to take $\delta_{\max}=2L$ in Lemma 15.1.

We next determine the validity of other assumptions in Lemma 15.1. Let us
denote the event in Lemma 3.1 by $\mathcal{E}_{\text{good}}$ and we have
$P(\mathcal{E}_{\text{good}})\geq 1-\delta$. Let
$\Delta^{t}\mathrel{\mathop{:}}=\frac{1}{2}\big{(}\left\|{\lambda^{t}}\right\|^{2}-\left\|{\lambda^{t-1}}\right\|^{2}\big{)}$.
Clearly, $\Delta^{t}=\Delta_{1}^{t}+\Delta_{2}^{t}$. We recall that the proof
of Lemma 7.3 remains to be valid if we replace $q_{1}^{\star}$ by
$\bar{q}_{1}$ and $q_{2}^{\star}$ by $\bar{q}_{2}$ starting from (49). By
doing so, it is ready to obtain a similar result as (53): under the good event
$\mathcal{E}_{\text{good}}$ it holds for any $\tau$ that

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\Delta^{\tau}\,-\,4\theta
VL\,-\,\eta V^{2}L\\\\[5.69046pt]
&\leq&V\,\big{\langle}{\bar{q}_{1}\cdot\widehat{q}_{2}^{\,\tau-1}-\widehat{q}_{1}^{\,\tau-1}\cdot\bar{q}_{2}},{r^{\tau-1}}\big{\rangle}\,+\,\lambda_{1}^{\tau-1}\big{(}\langle{\bar{q}_{1}},{g^{\tau-1}}\rangle-
b_{1}\big{)}\,+\,\lambda_{2}^{\tau-1}\big{(}\langle{\bar{q}_{2}},{h^{\tau-1}}\rangle-
b_{2}\big{)}\,+\,2L^{2}\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(\bar{q}_{1},\widetilde{q}_{1}^{\,\tau-1})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,\tau-1})-D(\bar{q}_{1},\widehat{q}_{1}^{\,\tau})-D(\bar{q}_{2},\widehat{q}_{2}^{\,\tau})\big{)}.\end{array}$

or, equivalently,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\left\|{\lambda^{\tau}}\right\|^{2}\,-\,\left\|{\lambda^{\tau-1}}\right\|^{2}\\\\[5.69046pt]
&\leq&2V\,\big{\langle}{\bar{q}_{1}\cdot\widehat{q}_{2}^{\,\tau-1}-\widehat{q}_{1}^{\,\tau-1}\cdot\bar{q}_{2}},{r^{\tau-1}}\big{\rangle}\,+\,2\lambda_{1}^{\tau-1}\big{(}\langle{\bar{q}_{1}},{g^{\tau-1}}\rangle-
b_{1}\big{)}\,+\,2\lambda_{2}^{\tau-1}\big{(}\langle{\bar{q}_{2}},{h^{\tau-1}}\rangle-
b_{2}\big{)}\,+\,4L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}\big{(}D(\bar{q}_{1},\widetilde{q}_{1}^{\,\tau-1})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,\tau-1})-D(\bar{q}_{1},\widehat{q}_{1}^{\,\tau})-D(\bar{q}_{2},\widehat{q}_{2}^{\,\tau})\big{)}\,+\,8\theta
VL\,+\,2\eta V^{2}L.\end{array}$ (55)

We note that
$|\langle{\bar{q}_{1}\cdot\widehat{q}_{2}^{\,\tau}-\widehat{q}_{1}^{\,\tau}\cdot\bar{q}_{2}},{r^{\tau}}\rangle|\leq
L$. By summing both sides of (55) from $\tau=t+1$ to $\tau=t+t_{0}$,

$\begin{array}[]{rcl}\left\|{\lambda^{t+t_{0}}}\right\|^{2}\,-\,\left\|{\lambda^{t}}\right\|^{2}&\leq&\displaystyle
2t_{0}VL\,+\,2\sum_{\tau\,=\,t}^{t+t_{0}-1}\left(\lambda_{1}^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{\bar{q}_{2}},{h^{\tau}}\rangle-
b_{2}\big{)}\right)\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}\big{(}D(\bar{q}_{1},\widetilde{q}_{1}^{\,t})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,t})\big{)}\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\end{array}$

where we omit two non-positive terms. Taking the conditional expectation given
${\mathcal{F}}^{t}$ and $\mathcal{E}_{\text{good}}$ yields,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|^{2}\,-\,\left\|{\lambda^{t}}\right\|^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&\displaystyle
2t_{0}VL\,+\,2\sum_{\tau\,=\,t}^{t+t_{0}-1}\mathbb{E}\left[\lambda_{1}^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{\bar{q}_{2}},{h^{\tau}}\rangle-
b_{2}\big{)}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}\mathbb{E}\left[D(\bar{q}_{1},\widetilde{q}_{1}^{\,t})+D(\bar{q}_{2},\widetilde{q}_{2}^{\,t})\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt] &\leq&\displaystyle
2t_{0}VL\,-\,2\xi\sum_{\tau\,=\,t}^{t+t_{0}-1}\mathbb{E}\left[\left\|{\lambda^{\tau}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt] &\leq&\displaystyle 2t_{0}VL\,-\,2\xi
t_{0}\mathbb{E}\left[\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,2\xi
t_{0}(t_{0}-1)L\,+\,4t_{0}L^{2}\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\end{array}$ (56)

where the second inequality is due to Lemma 11.5 and the fact: by the law of
total expectation, for any $\tau\geq t$,
${\mathcal{F}}^{t}\subset{\mathcal{F}}^{\tau}$ and

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}\left[\lambda_{1}^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{\bar{q}_{2}},{h^{\tau}}\rangle-
b_{2}\big{)}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&=&\mathbb{E}\left[\mathbb{E}\left[\lambda_{1}^{\tau}\big{(}\langle{\bar{q}_{1}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{\bar{q}_{2}},{h^{\tau}}\rangle-
b_{2}\big{)}\,|\,{\mathcal{F}}^{\tau},\mathcal{E}_{\text{good}}\right]\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&=&\mathbb{E}\left[\lambda_{1}^{\tau}\mathbb{E}\left[\langle{\bar{q}_{1}},{g^{\tau}}\rangle-
b_{1}\right]\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,\mathbb{E}\left[\lambda_{2}^{\tau}\mathbb{E}\left[\langle{\bar{q}_{2}},{h^{\tau}}\rangle-
b_{2}\right]\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&=&\mathbb{E}\left[\langle{\bar{q}_{1}},{g^{\tau}}\rangle-
b_{1}\right]\mathbb{E}\left[\lambda_{1}^{\tau}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,\mathbb{E}\left[\langle{\bar{q}_{2}},{h^{\tau}}\rangle-
b_{2}\right]\mathbb{E}\left[\lambda_{2}^{\tau}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&\,-\,\xi\,\mathbb{E}\left[\lambda_{1}^{\tau}+\lambda_{2}^{\tau}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&\,-\,\xi\,\mathbb{E}\left[\left\|{\lambda^{\tau}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\end{array}$

where the inequality is due to the strict feasibility assumption on
$(\bar{q}_{1},\bar{q}_{2})$; the last inequality is due to that

$\begin{array}[]{rcl}\displaystyle\sum_{\tau\,=\,t}^{t+t_{0}-1}\mathbb{E}\left[\left\|{\lambda^{\tau}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]&\geq&\displaystyle\sum_{\tau\,=\,t}^{t+t_{0}-1}\mathbb{E}\left[\left\|{\lambda^{t}}\right\|-2(\tau-t)L\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&=&\displaystyle\sum_{\tau\,=\,0}^{t_{0}-1}\mathbb{E}\left[\left\|{\lambda^{t}}\right\|-2\tau
L\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\end{array}$

which follows the fact
$\left\|{\lambda^{\tau}}\right\|\geq\left\|{\lambda^{t}}\right\|-2(\tau-t)L$
for any $\tau\geq t\geq 0$ if we note that
$\left|\left\|{\lambda^{t+1}}\right\|-\left\|{\lambda^{t}}\right\|\right|\leq
2L$. Hence, we can simplify (56) as

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&\displaystyle\mathbb{E}\left[\left\|{\lambda^{t}}\right\|^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,2\xi
t_{0}\mathbb{E}\left[\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,+\,2\xi
t_{0}^{2}L\,+\,4t_{0}L^{2}\,+\,2t_{0}VL\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt]
&\leq&\displaystyle\mathbb{E}\left[\left\|{\lambda^{t}}\right\|^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\xi
t_{0}\mathbb{E}\left[\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\xi
t_{0}\Theta\,+\,2\xi t_{0}^{2}L\,+\,4t_{0}L^{2}\,+\,2t_{0}VL\\\\[5.69046pt]
&&\,+\,2\eta^{-1}L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))\,+\,8t_{0}\theta
VL\,+\,2t_{0}\eta V^{2}L\\\\[5.69046pt]
&=&\displaystyle\mathbb{E}\left[\left\|{\lambda^{t}}\right\|^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\xi
t_{0}\mathbb{E}\left[\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\,-\,\frac{1}{2}\xi^{2}t_{0}^{2}\\\\[5.69046pt]
&\leq&\displaystyle\left(\mathbb{E}\left[\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]-\frac{1}{2}\xi
t_{0}\right)^{2}\end{array}$

where we apply $\lambda^{t}\geq\Theta$ for the second inequality and we take
$\Theta$ in Lemma 15.1,

$\Theta\;=\;\frac{1}{2}\xi t_{0}+2t_{0}L\,+\,\frac{4L^{2}+8\theta VL+2\eta
V^{2}L+2VL}{\xi}\,+\,\frac{2L(\log(|X||A|/\theta)+\log(|Y||B|/\theta))}{t_{0}\xi\eta}.$

Taking the square root and applying the Jensen’s inequality yield

$\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\;\leq\;\sqrt{\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|^{2}\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]}\;\leq\;\left\|{\lambda^{t}}\right\|-\frac{1}{2}\xi
t_{0}$

which shows that
$\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|-\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\leq-\frac{1}{2}\xi
t_{0}$. Application of law of total expectation to this inequality and (54)
with $\delta<\frac{1}{12}$ yields

$\begin{array}[]{rcl}\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|-\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t}\right]&=&P(\mathcal{E}_{\text{good}})\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|-\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\mathcal{E}_{\text{good}}\right]\\\\[5.69046pt]
&&+\,P(\bar{\mathcal{E}}_{\text{good}})\mathbb{E}\left[\left\|{\lambda^{t+t_{0}}}\right\|-\left\|{\lambda^{t}}\right\|\,|\,{\mathcal{F}}^{t},\bar{\mathcal{E}}_{\text{good}}\right]\\\\[5.69046pt]
&\leq&-\dfrac{1}{2}\xi
t_{0}\times(1-\delta)\,+\,2t_{0}L\times\delta\\\\[5.69046pt]
&\leq&-\dfrac{1}{4}\xi t_{0}\end{array}$

which verifies the assumption of Lemma 15.1 if we take $\zeta=\xi/4$.

We now have verified all assumptions of Lemma 15.1 with appropriate parameters
$\Theta$, $\delta_{\max}$, $\zeta$. For episode $t$, with probability
$1-\delta$ it holds that

$\begin{array}[]{rcl}\left\|{\lambda^{t}}\right\|&\leq&\displaystyle\Theta+t_{0}\delta_{\max}+t_{0}\frac{4\delta_{\max}^{2}}{\zeta}\log\left(\frac{8\delta_{\max}^{2}}{\zeta}\right)+t_{0}\frac{4\delta_{\max}^{2}}{\zeta}\log\frac{1}{\delta}.\end{array}$

We complete the proof by taking a union bound over $t=1,\cdots,T$.

######  Lemma 14.6.

Let Assumption 2 hold. Fix $\delta\in(0,1)$. For any integer $t_{0}>0$, with
probability $1-2T\delta$,

$\sum_{t\,=\,0}^{T-1}\left(\lambda_{1}^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle-
b_{1}\big{)}+\lambda_{2}^{t}\big{(}\langle{q_{2}^{\star}},{h^{t}}\rangle-
b_{2}\big{)}\right)\;\leq\;\sqrt{2Tc^{2}\log(1/(\delta T))}$

where $c\mathrel{\mathop{:}}=2\Theta
L+4t_{0}L^{2}+\tfrac{128t_{0}L^{3}}{\xi}\left(\log\left(\tfrac{128L^{2}}{\xi}\right)+\log\tfrac{1}{\delta}\right)$
and $\xi>0$.

######  Proof 14.7.

Let
$Z^{t}\mathrel{\mathop{:}}=\sum_{\tau\,=\,0}^{t-1}\left(\lambda_{1}^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{q_{2}^{\star}},{h^{\tau}}\rangle-
b_{2}\big{)}\right)$. We note that

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{E}\left[Z^{t}\,|\,{\mathcal{F}}^{t-1}\right]\\\\[5.69046pt]
&=&\displaystyle\mathbb{E}\left[\sum_{\tau\,=\,0}^{t-1}\left(\lambda_{1}^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{q_{2}^{\star}},{h^{\tau}}\rangle-
b_{2}\big{)}\right)\,\bigg{|}\,{\mathcal{F}}^{t-1}\right]\\\\[5.69046pt]
&=&\displaystyle\mathbb{E}\left[\sum_{\tau\,=\,0}^{t-2}\left(\lambda_{1}^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{q_{2}^{\star}},{h^{\tau}}\rangle-
b_{2}\big{)}\right)\,\bigg{|}\,{\mathcal{F}}^{t-1}\right]\\\\[5.69046pt]
&&\,+\,\lambda_{1}^{t-1}\mathbb{E}\left[\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle-
b_{1}\big{)}\,|\,{\mathcal{F}}^{t-1}\right]\,+\,\lambda_{2}^{t-1}\mathbb{E}\left[\big{(}\langle{q_{2}^{\star}},{h^{t-1}}\rangle-
b_{2}\big{)}\,|\,{\mathcal{F}}^{t-1}\right]\\\\[5.69046pt]
&\leq&\displaystyle\mathbb{E}\left[\sum_{\tau\,=\,0}^{t-2}\left(\lambda_{1}^{\tau}\big{(}\langle{q_{1}^{\star}},{g^{\tau}}\rangle-
b_{1}\big{)}+\lambda_{2}^{\tau}\big{(}\langle{q_{2}^{\star}},{h^{\tau}}\rangle-
b_{2}\big{)}\right)\,\bigg{|}\,{\mathcal{F}}^{t-1}\right]\\\\[11.38092pt]
&=&\mathbb{E}\left[Z^{t-1}\right]\end{array}$

where the inequality is because of
$\mathbb{E}\left[\big{(}\langle{q_{1}^{\star}},{g^{t-1}}\rangle-
b_{1}\big{)}\,|\,{\mathcal{F}}^{t-1}\right]=\langle{q_{1}^{\star}},{g}\rangle-
b_{1}\leq 0$ and
$\mathbb{E}\left[\big{(}\langle{q_{2}^{\star}},{h^{t-1}}\rangle-
b_{1}\big{)}\,|\,{\mathcal{F}}^{t-1}\right]\leq\langle{q_{2}^{\star}},{h}\rangle-
b_{2}\leq 0$. Hence, $\\{Z^{t},t\geq 0\\}$ a supermartingale.

We also note that

$\left|Z^{t+1}-Z^{t}\right|\;=\;\lambda_{1}^{t}\left|\langle{q_{1}^{\star}},{g^{t}}\rangle-
b_{1}\right|+\lambda_{2}^{t}\left|\langle{q_{2}^{\star}},{h^{t}}\rangle-
b_{2}\right|\;\leq\;2\left\|{\lambda^{t}}\right\|L$

Thus, if $|Z^{t+1}-Z^{t}|>c$ for some $c\in\mathbb{R}^{+}$, then
$\left\|{\lambda^{t}}\right\|>c/(2L)$. Let
$Y^{t}\mathrel{\mathop{:}}=\left\|{\lambda^{t}}\right\|-c/(2L)$. Therefore,

$\\{|Z^{t+1}-Z^{t}|>c\\}\;\subset\;\\{Y^{t}>0\\}.$

By Lemma 15.2,

$P\left(\sum_{t\,=\,0}^{T-1}\left(\lambda_{1}^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle-
b_{1}\big{)}+\lambda_{2}^{t}\big{(}\langle{q_{2}^{\star}},{h^{t}}\rangle-
b_{2}\big{)}\right)\geq z\right)\;\leq\;{\rm
e}^{-z^{2}/(2c^{2}T)}\,+\,\sum_{\tau\,=\,0}^{T-1}P\left(\left\|{\lambda^{t}}\right\|>\frac{c}{2L}\right).$
(57)

By Lemma 14.4, with probability $1-\delta$ it holds for any $t$ that

$\left\|{\lambda^{t}}\right\|\;\leq\;\displaystyle\Theta+2t_{0}L+t_{0}\frac{64L^{2}}{\xi}\log\left(\frac{128L^{2}}{\xi}\right)+t_{0}\frac{64L^{2}}{\xi}\log\frac{1}{\delta}$

or, equivalently,

$P\left(\left\|{\lambda^{t}}\right\|\;\geq\;\displaystyle\Theta+2t_{0}L+t_{0}\frac{64L^{2}}{\xi}\log\left(\frac{128L^{2}}{\xi}\right)+t_{0}\frac{64L^{2}}{\xi}\log\frac{1}{\delta}\right)\;\leq\;\delta.$

If we take

$c\;=\;2\Theta
L+4t_{0}L^{2}+t_{0}\frac{128L^{3}}{\xi}\log\left(\frac{128L^{2}}{\xi}\right)+t_{0}\frac{128L^{3}}{\xi}\log\frac{1}{\delta}\;\text{
and }\;z\;=\;\sqrt{2Tc^{2}\log(1/(\delta T))}$

then (57) becomes

$P\left(\sum_{t\,=\,0}^{T-1}\left(\lambda_{1}^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle-
b_{1}\big{)}+\lambda_{2}^{t}\big{(}\langle{q_{2}^{\star}},{h^{t}}\rangle-
b_{2}\big{)}\right)\geq z\right)\;\leq\;2\delta T$

which proves the desired result.

We now ready to conclude a bound on ${\widehat{\text{Regret}}(T)}$ by
combining Lemma 14.6 and Lemma 14.2.

######  Theorem 14.8.

Let Assumption 2 hold. Fix $T\geq\max(|X||A|,|B||Y|)$. Let $V=L\sqrt{T}$,
$\eta=1/(TL)$, $t_{0}=\sqrt{T}$, and $\theta=1/T$. Then, with probability
$1-2T\delta$ it holds that

${\widehat{\text{Regret}}(T)}\;\leq\;\widetilde{O}\big{(}{(|X|+|Y|)L\sqrt{T}}\big{)}.$

######  Proof 14.9.

Using the given parameters $V$, $\eta$, $t_{0}$, and $\theta$ for Lemma 14.2,
${\widehat{\text{Regret}}(T)}$ is upper bounded by
$\frac{1}{L\sqrt{T}}\sum_{t\,=\,0}^{T-1}\left(\lambda_{1}^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle-
b_{1}\big{)}+\lambda_{2}^{t}\big{(}\langle{q_{2}^{\star}},{h^{t}}\rangle-
b_{2}\big{)}\right)+\widetilde{O}(L\sqrt{T})$ with probability $1-\delta$. We
note that $\Theta\leq\widetilde{O}(L^{2}\sqrt{T})$ and
$T\geq\max(|X||A|,|B||Y|)$. Using parameters in Lemma 14.6, with probability
$1-2T\delta$,

$\sum_{t\,=\,0}^{T-1}\left(\lambda_{1}^{t}\big{(}\langle{q_{1}^{\star}},{g^{t}}\rangle-
b_{1}\big{)}+\lambda_{2}^{t}\big{(}\langle{q_{2}^{\star}},{h^{t}}\rangle-
b_{2}\big{)}\right)\;\leq\;\widetilde{O}(L^{3}T).$

We complete the proof by noting $L\leq|X|+|Y|$.

We conclude the regret bound in Theorem 14.1 by combining Lemma 7.2 and
Theorem 14.8, and $\delta=p/(2T)$.

###  14.3 Constraint Violation Analysis

We begin with a decomposition using the auxiliary occupancy measures
$(q_{1}^{t},q_{2}^{t})$. By inserting
$\langle\widehat{q}_{1}^{\,t},g^{t}\rangle$ and
$\langle\widehat{q}_{2}^{\,t},h^{t}\rangle$ into $\text{Violation}_{1}(T)$ and
$\text{Violation}_{2}(T)$, we have

$\begin{array}[]{rcl}\text{Violation}_{1}(T)&=&\underbrace{\left[\sum_{t\,=\,0}^{T-1}\left(\left\langle\widehat{q}_{1}^{\,t},g^{t}\right\rangle-
b_{1}\right)\right]_{+}}_{\widehat{\text{Violation}_{1}}(T)}\,+\,\underbrace{\sum_{t\,=\,0}^{T-1}\left\langle
q_{1}^{t}-\widehat{q}_{1}^{\,t},g^{t}\right\rangle}_{\text{Error}_{3}}\end{array}$
$\begin{array}[]{rcl}\text{Violation}_{2}(T)&=&\underbrace{\left[\sum_{t\,=\,0}^{T-1}\left(\left\langle\widehat{q}_{2}^{\,t},h^{t}\right\rangle-
b_{2}\right)\right]_{+}}_{\widehat{\text{Violation}_{2}}(T)}\,+\,\underbrace{\sum_{t\,=\,0}^{T-1}\left\langle
q_{2}^{t}-\widehat{q}_{2}^{\,t},h^{t}\right\rangle}_{\text{Error}_{4}}.\end{array}$

For ${\text{Error}_{3}}$ and ${\text{Error}_{4}}$, we have the same bounds in
Lemma 7.8. We next bound ${\widehat{\text{Violation}_{1}}(T)}$ and
${\widehat{\text{Violation}_{2}}(T)}$ by applying the epoch property (Jaksch
et al., 2010); see a proof in Appendix 13.

######  Theorem 14.10.

Let $V=L\sqrt{T}$, $\eta=1/(TL)$, $t_{0}=\sqrt{T}$, and $\theta=1/T$. Then,

$\begin{array}[]{rcl}{\widehat{\text{Violation}_{1}}(T)},{\widehat{\text{Violation}_{2}}(T)}&\leq&\displaystyle\left\|{\lambda^{T}}\right\|\,+\,\frac{2}{T-1}\sum_{t\,=\,1}^{T}\left\|{\lambda^{t-1}}\right\|\,+\,\widetilde{O}\big{(}L\sqrt{T(|X||A|+|Y||B|)}\big{)}.\end{array}$

######  Proof 14.11.

By the dual update (48),

$\begin{array}[]{rcl}\lambda_{1}^{t}&=&\max\\!\Big{(}\lambda_{1}^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t},g^{t-1}\right\rangle-
b_{1}\,\big{)},\;0\Big{)}\\\\[5.69046pt]
&\geq&\lambda_{1}^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t},g^{t-1}\right\rangle-
b_{1}\,\big{)}\\\\[5.69046pt]
&=&\lambda_{1}^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t-1},g^{t-1}\right\rangle-
b_{1}\,\big{)}\,+\,\left\langle\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1},g^{t-1}\right\rangle\\\\[5.69046pt]
&\geq&\lambda_{1}^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{1}^{\,t-1},g^{t-1}\right\rangle-
b_{1}\,\big{)}\,-\,\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}\end{array}$
(58a) where the last inequality is due to:
$\langle{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}},{g^{t-1}}\rangle\leq\|\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}\|_{1}\|g^{t-1}\|_{\infty}$,
and $\|g^{t-1}\|_{\infty}\in[0,1]$. Similarly,
$\lambda_{2}^{t}\;\geq\;\lambda_{2}^{t-1}\,+\,\big{(}\left\langle\widehat{q}_{2}^{\,t-1},h^{t-1}\right\rangle-
b_{2}\,\big{)}\,-\,\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}.$
(58b)

We note that $\lambda_{1}^{0}=\lambda_{2}^{0}=0$ from the initialization.
Summing up both sides of (58a) from $t=1$ to $t=T$ leads to

$\sum_{t\,=\,0}^{T-1}\big{(}\left\langle\widehat{q}_{1}^{\,t},g^{t}\right\rangle-
b_{1}\,\big{)}\;\leq\;\lambda_{1}^{T}\,+\,\sum_{t\,=\,1}^{T}\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}.$
(59a) Similarly,
$\sum_{t\,=\,0}^{T-1}\big{(}\left\langle\widehat{q}_{2}^{\,t},h^{t}\right\rangle-
b_{2}\,\big{)}\;\leq\;\lambda_{2}^{T}\,+\,\sum_{t\,=\,1}^{T}\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}.$
(59b)

Hence,

${\widehat{\text{Violation}_{1}}(T)},{\widehat{\text{Violation}_{2}}(T)}\;\leq\;\left\|{\lambda^{T}}\right\|\,+\,\sum_{t\,=\,1}^{T}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}\right).$
(60)

We recall $\widehat{q}_{1}^{\,t}\in\Delta(k_{1}^{t})$,
$\widehat{q}_{2}^{\,t}\in\Delta(k_{2}^{t})$ in the primal update (47) and
$\Delta(k_{1}^{t})$ and $\Delta(k_{2}^{t})$ in the confidence sets (11). To
bound
$\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}$,
we consider two cases: (i) $k_{1}^{t}=k_{1}^{t-1}$ and
$k_{2}^{t}=k_{2}^{t-1}$; (ii) either $k_{1}^{t}\neq k_{1}^{t-1}$ or
$k_{2}^{t}\neq k_{2}^{t-1}$.

Case (i). In this case, we have: $\widehat{q}_{1}^{\,t}$,
$\widehat{q}_{1}^{\,t-1}\in\Delta(k_{1}^{t})$, $\widehat{q}_{2}^{\,t}$,
$\widehat{q}_{2}^{\,t-1}\in\Delta(k_{2}^{t})$. We begin with the primal update
(8) and apply Lemma 11.1 with,

$f(x,y)|_{x\,=\,q_{1},\,y\,=\,q_{2}}\;=\;V\,\big{\langle}{q_{1}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot
q_{2}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{q_{1}},{g^{t-1}}\rangle\,-\,\lambda_{2}^{t-1}\langle{q_{2}},{h^{t-1}}\rangle$

and $x^{\star}=\widehat{q}_{1}^{\,t}$, $y^{\star}=\widehat{q}_{2}^{\,t}$,
$x^{\prime}=\widetilde{q}_{1}^{\,t-1}$,
$y^{\prime}=\widetilde{q}_{2}^{\,t-1}$, $x=\widetilde{q}_{1}^{\,t-1}$, and
$y=\widetilde{q}_{2}^{\,t-1}$. Thus,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!V\,\big{\langle}{\widehat{q}_{1}^{\,t}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot\widetilde{q}_{2}^{\,t-1}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle\,-\,\lambda_{2}^{t-1}\langle{\widetilde{q}_{2}^{\,t-1}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\,+\,\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{\widetilde{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot\widehat{q}_{2}^{\,t}},{r^{t-1}}\big{\rangle}\,+\,\lambda_{1}^{t-1}\langle{\widetilde{q}_{1}^{\,t-1}},{g^{t-1}}\rangle\,-\,\lambda_{2}^{t-1}\langle{\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle\\\\[5.69046pt]
&&\,-\,\eta^{-1}\big{(}D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\big{)}.\end{array}$

or, equivalently,

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\,+\,\eta^{-1}\big{(}D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&\leq&V\,\big{\langle}{(\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t})\cdot\widehat{q}_{2}^{\,t-1}+\widehat{q}_{1}^{\,t-1}\cdot(\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1})},{r^{t-1}}\big{\rangle}\\\\[5.69046pt]
&&\,+\,\lambda_{1}^{t-1}\langle{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}},{g^{t-1}}\rangle\,+\,\lambda_{2}^{t-1}\langle{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}},{h^{t-1}}\rangle.\end{array}$
(61)

We note that
$\langle{(\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t})\cdot\widehat{q}_{2}^{\,t-1}},{r^{t-1}}\rangle\leq\|(\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t})\cdot\widehat{q}_{2}^{\,t-1}\|_{1}\|{r^{t-1}}\|_{\infty}\leq\|\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}\|_{1}$,
and, similarly,
$\langle\widehat{q}_{1}^{\,t-1}\cdot(\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}),{r^{t-1}}\rangle\leq\|\widehat{q}_{2}^{\,t}-\widetilde{q}_{2}^{\,t-1}\|_{1}$.
Thus, we can reduce (61) into

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\eta^{-1}\big{(}D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})\big{)}\,+\,\eta^{-1}\big{(}D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\big{)}\\\\[5.69046pt]
&\leq&(V+\lambda_{1}^{t-1})\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}\,+\,(V+\lambda_{2}^{t-1})\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\\\\[5.69046pt]
&\leq&(V+\left\|{\lambda^{t-1}}\right\|)\left(\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}+\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\right)\end{array}$

where the left-hand side can be lower bounded by Lemma 11.3,

$D(\widehat{q}_{1}^{\,t},\widetilde{q}_{1}^{\,t-1})+D(\widetilde{q}_{1}^{\,t-1},\widehat{q}_{1}^{\,t})\;\geq\;L^{-1}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}^{2}$
$D(\widehat{q}_{2}^{\,t},\widetilde{q}_{2}^{\,t-1})+D(\widetilde{q}_{2}^{\,t-1},\widehat{q}_{2}^{\,t})\;\geq\;L^{-1}\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}^{2}.$

Then, we apply the inequality $(x+y)^{2}\leq 2(x^{2}+y^{2})$ and cancel a non-
negative term to obtain

$\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}+\left\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\right\|_{1}\;\leq\;2\eta
L(V+\left\|{\lambda^{t-1}}\right\|).$ (62)

By the definition of $\widetilde{q}_{1}^{\,t-1}$ and
$\widetilde{q}_{2}^{\,t-1}$,

$\begin{array}[]{rcl}\left\|{\widetilde{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}&=&\displaystyle\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\left|(1-\theta)\widehat{q}_{1}^{\,t-1}(x,a)+\theta\frac{1}{|X_{\ell}||A|}-\widehat{q}_{1}^{\,t}(x,a)\right|\\\\[5.69046pt]
&\geq&\displaystyle\sum_{\ell\,=\,0}^{L-1}\sum_{x\,\in\,X_{\ell}}\sum_{a\,\in\,A}\left((1-\theta)\left|\widehat{q}_{1}^{\,t-1}(x,a)-\widehat{q}_{1}^{\,t}(x,a)\right|-\theta\left(\frac{1}{|X_{\ell}||A|}+\widehat{q}_{1}^{\,t}(x,a)\right)\right)\\\\[5.69046pt]
&=&(1-\theta)\left\|{\widehat{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}-2\theta
L.\end{array}$

Similarly, we have
$\|{\widetilde{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\|_{1}\leq(1-\theta)\|{\widehat{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\|_{1}-2\theta
L$. Thus, we can further reduce (62) into

$\left\|{\widehat{q}_{1}^{\,t-1}-\widehat{q}_{1}^{\,t}}\right\|_{1}+\|{\widehat{q}_{2}^{\,t-1}-\widehat{q}_{2}^{\,t}}\|_{1}\;\leq\;2\eta(1-\theta)^{-1}L(V+\left\|{\lambda^{t-1}}\right\|)+4\theta(1-\theta)^{-1}L.$
(63)

Case (ii). In this case, either $\widehat{q}_{1}^{\,t}$,
$\widehat{q}_{1}^{\,t-1}$ or $\widehat{q}_{2}^{\,t}$,
$\widehat{q}_{2}^{\,t-1}$ might not have the same domain. For instance, when
$k_{1}^{t}>k_{1}^{t-1}$, it is possible that $\Delta(k_{1}^{t})$ becomes
different from $\Delta(k_{1}^{t-1})$. We note that $k_{1}^{t}>k_{1}^{t-1}$
only happens when episode $t$ is the first one that belongs to epoch
$k_{1}^{t}$. By Lemma 15.4, $k_{1}^{T}\leq\sqrt{T|X||A|}\log(8T/(|X||A|))$ and
$k_{2}^{T}\leq\sqrt{T|Y||B|}\log(8T/(|Y||B|))$ if we are given
$T\geq\max(|X||A|,|Y||B|)$.

We now combine two cases above for (60),

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\displaystyle\sum_{t\,=\,1}^{T}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\\\\[5.69046pt]
&=&\displaystyle\sum_{\begin{subarray}{c}1\,\leq\,t\,\leq\,T\\\
k_{1}^{t}\,=\,k_{1}^{k-1}\,\wedge\,k_{2}^{t}\,=\,k_{2}^{k-1}\end{subarray}}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\\\\[5.69046pt]
&&\displaystyle\,+\,\sum_{\begin{subarray}{c}1\,\leq\,t\,\leq\,T\\\
k_{1}^{t}\,=\,k_{1}^{k-1}\,\vee\,k_{2}^{t}\,=\,k_{2}^{k-1}\end{subarray}}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\\\\[5.69046pt]
&\leq&\displaystyle\sum_{\begin{subarray}{c}1\,\leq\,t\,\leq\,T\\\
k_{1}^{t}\,=\,k_{1}^{k-1}\,\wedge\,k_{2}^{t}\,=\,k_{2}^{k-1}\end{subarray}}\left(\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}+\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\right)\,+\,2L(k_{1}^{T}+k_{2}^{T})\\\\[5.69046pt]
&\leq&\displaystyle
2\eta(1-\theta)^{-1}L\sum_{t\,=\,1}^{T}(V+\left\|{\lambda^{t-1}}\right\|)+4\theta(1-\theta)^{-1}LT+2L(k_{1}^{T}+k_{2}^{T})\end{array}$

where the first inequality is due to:
$\left\|{\widehat{q}_{1}^{\,t}-\widehat{q}_{1}^{\,t-1}}\right\|_{1}\leq 2L$
and $\left\|{\widehat{q}_{2}^{\,t}-\widehat{q}_{2}^{\,t-1}}\right\|_{1}\leq
2L$, and we apply (63) from the case (i) for the last inequality. Using the
bounds on $k_{1}^{T}$, $k_{2}^{T}$ in the case (ii), we conclude the desired
bound for (60),

$\begin{array}[]{rcl}&&\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\displaystyle{\widehat{\text{Violation}_{1}}(T)},{\widehat{\text{Violation}_{2}}(T)}\\\\[5.69046pt]
&\leq&\displaystyle\left\|{\lambda^{T}}\right\|\,+\,\frac{2\eta
L}{1-\theta}\sum_{t\,=\,1}^{T}\left\|{\lambda^{t-1}}\right\|+\frac{2\eta
V+4\theta}{1-\theta}LT\\\\[5.69046pt]
&&\displaystyle+2L\left(\sqrt{T|X||A|}\log(8T/(|X||A|))+\sqrt{T|Y||B|}\log(8T/(|Y||B|))\right).\end{array}$

We complete the proof by noting $\lambda_{1}^{0}=\lambda_{2}^{0}=0$,
$V=L\sqrt{T}$, $\eta=1/(TL)$, and $\theta=1/T$.

To get the violation bound, we apply Lemma 14.4 to Theorem 14.10, use Lemma
7.8, and take $\delta=p/(2T)$.

##  15 Supporting Lemmas

We collect some useful lemmas in literature for the convenience of reading our
paper.

The following drift analysis of stochastic processes is useful in the
constraint violation analysis.

######  Lemma 15.1.

(Yu et al., 2017) Let $\\{Z^{t},t\geq 0\\}$ be a discrete-time stochastic
process that is adapted to a filtration $\\{{\mathcal{F}}^{t},t\geq 0\\}$ with
$Z^{0}=0$ and ${\mathcal{F}}^{0}=\\{\emptyset,\Omega\\}$. Assume that there
exists $t_{0}\in\mathbb{Z}^{+}$, $\Theta\in\mathbb{R}^{+}$,
$\delta_{\max}\in\mathbb{R}^{+}$, and $\zeta\in(0,\delta_{\max}]$ such that
for all $t\geq 1$,

$\left|Z^{t+1}-Z^{t}\right|\;\leq\;\delta_{\max}\;\text{ and
}\;\mathbb{E}\left[Z^{t+t_{0}}-Z^{t}\,|\,{\mathcal{F}}^{t}\right]\;\leq\;\begin{cases}t_{0}\,\delta_{\max}\;\;\text{
when }Z^{t}\leq\Theta\\\\[5.69046pt] -\,t_{0}\,\zeta\;\;\;\;\text{ otherwise
}Z^{t}\geq\Theta.\end{cases}$

Then, with probability $1-\delta$ it holds for any $t$ that

$Z^{t}\;\leq\;\Theta+t_{0}\delta_{\max}+t_{0}\frac{4\delta_{\max}^{2}}{\zeta}\log\left(\frac{8\delta_{\max}^{2}}{\zeta}\right)+t_{0}\frac{4\delta_{\max}^{2}}{\zeta}\log\frac{1}{\delta}.$

A general Azuma-Hoeffding inequality for supermartingales with unbounded
differences is given as follows.

######  Lemma 15.2.

(Yu et al., 2017) Let $\\{Z^{t},t\geq 0\\}$ be a supermartingale that is
adapted to a filtration $\\{{\mathcal{F}}^{t},t\geq 0\\}$ with $Z^{0}=0$ and
${\mathcal{F}}^{0}=\\{\emptyset,\Omega\\}$. Let $\\{Y^{t},t\geq 0\\}$ be a
discrete-time stochastic process that is adapted to a filtration
$\\{{\mathcal{F}}^{t},t\geq 0\\}$. Assume that there exists a constant
$c\in\mathbb{R}^{+}$ such that $\\{|Z^{t+1}-Z^{t}|>c\\}\subset\\{Y^{t}>0\\}$
for any $t\geq 0$. Then, for any $z\in\mathbb{R}^{+}$ and $t\geq 1$,

$P(Z^{t}\geq z)\;\leq\;{\rm
e}^{-z^{2}/(2c^{2}t)}\,+\,\sum_{\tau\,=\,0}^{t-1}P(Y^{t}>0).$

The following two lemmas are useful in the epoch analysis.

######  Lemma 15.3.

(Jaksch et al., 2010) Let a sequence of positive numbers be
$x_{1},\ldots,x_{n}$. Assume that $0\leq x_{k}\leq
X_{k-1}\mathrel{\mathop{:}}=\max(1,\sum_{i\,=\,1}^{k-1}x_{i})$ for $1\leq
k\leq n$. Then,

$\sum_{k\,=\,1}^{n}\frac{x_{k}}{\sqrt{X_{k-1}}}\;\leq\;(\sqrt{2}+1)\sqrt{X_{n}}.$

######  Lemma 15.4.

(Jaksch et al., 2010) Assume that $T\geq\max(|X||A|,|Y||B|)$. Then, the epochs
$k_{1}^{T}$ and $k_{2}^{T}$ for episode $T$

$k_{1}^{T}\;\leq\;|X||A|\log\left(\frac{8T}{|X||A|}\right)\;\leq\;\sqrt{T|X||A|}\log\left(\frac{8T}{|X||A|}\right)$
$k_{2}^{T}\;\leq\;|Y||B|\log\left(\frac{8T}{|Y||B|}\right)\;\leq\;\sqrt{T|Y||B|}\log\left(\frac{8T}{|Y||B|}\right).$