$\displaystyle\bm{C}^{t-}_{j,\ast}\mathrel{:\mkern-0.25mu=}\left(\\!\begin{array}[]{c@{\hspace{2.5mm}}c@{\hspace{2.5mm}}c|c@{\hspace{2.5mm}}c@{\hspace{2.5mm}}c|c@{\hspace{1mm}}c@{\hspace{1mm}}c}\frac{1}{\lambda_{1}^{t}}\hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&\\\ \hfil\hskip 7.11317pt&\ddots\hfil\hskip 7.11317pt&&\hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&\\\ \hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&\frac{1}{\lambda_{m}^{t}}&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&\\\\[5.69054pt] \hline\cr\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&0\hfil\hskip 7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\ddots\hfil\hskip
7.11317pt&&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\\\\[2.84526pt]
\hfil\hskip 7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&0&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\\\\[2.84526pt]
\hline\cr\hfil\hskip 7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&\\\\[-8.53581pt] \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&\frac{1}{\lambda^{t}_{m+1}}\bm{C}^{t-}_{k_{m+1}}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\ \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\frac{1}{\lambda^{t}_{n}}\bm{C}^{t-}_{k_{n}}\\\
\end{array}\\!\right)$

is a generalized inverse for the autocorrelation matrix $\bm{C}^{t}_{j}$
defined in Lemma 13. The matrix is well defined in virtue of 1.

###### Proof.

Let $\bm{C}^{t-}_{j}$ be the matrix proposed by the statement. Using Lemma 13,

$\displaystyle\bm{C}^{t}_{j}\,\bm{C}^{t-}_{j}\,\bm{C}^{t}_{j}$
$\displaystyle=\bm{C}^{t}_{j}\left(\\!\begin{array}[]{c@{\hspace{2.5mm}}c@{\hspace{2.5mm}}c|c@{\hspace{2.5mm}}c@{\hspace{2.5mm}}c|c@{\hspace{1mm}}c@{\hspace{1mm}}c}\frac{1}{\lambda_{1}^{t}}\hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&\\\ \hfil\hskip 7.11317pt&\ddots\hfil\hskip 7.11317pt&&\hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&\\\ \hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&\frac{1}{\lambda_{m}^{t}}&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&\\\\[5.69054pt] \hline\cr\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&0\hfil\hskip 7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\ddots\hfil\hskip
7.11317pt&&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\\\\[2.84526pt]
\hfil\hskip 7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&0&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\\\\[2.84526pt]
\hline\cr\hfil\hskip 7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&\\\\[-8.53581pt] \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&\frac{1}{\lambda^{t}_{1}}\bm{C}^{t-}_{k_{m+1}}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\ \hfil\hskip
7.11317pt&\hfil\hskip 7.11317pt&&\hfil\hskip 7.11317pt&\hfil\hskip
7.11317pt&&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\frac{1}{\lambda^{t}_{n}}\bm{C}^{t-}_{k_{n}}\\\
\end{array}\\!\right)\left(\\!\begin{array}[]{c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c}\lambda^{t}_{1}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt\\\ \hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{m}\hfil\hskip
1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt\\\\[2.84526pt] \hline\cr\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip 2.84526pt\\\\[-8.53581pt]
\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\lambda^{t}_{m+1}\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\lambda^{t}_{m+1}({\bm{x}}^{t}_{k_{m+1}})^{\\!\top}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\\[-2.84526pt]
\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{n}\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\lambda^{t}_{n}({\bm{x}}^{t}_{k_{n}})^{\\!\top}\\\\[2.84526pt]
\hline\cr\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt\\\\[-8.53581pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\lambda^{t}_{m+1}{\bm{x}}^{t}_{k_{m+1}}\\!\\!\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\lambda^{t}_{m+1}\bm{C}^{t}_{k_{m+1}}\\!\\!\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{n}{\bm{x}}^{t}_{k_{n}}\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\\!\\!\\!\lambda^{t}_{n}\bm{C}^{t}_{k_{n}}\end{array}\\!\right)$
$\displaystyle=\left(\\!\begin{array}[]{c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c}\lambda^{t}_{1}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt\\\ \hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{m}\hfil\hskip
1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt\\\\[2.84526pt] \hline\cr\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip 2.84526pt\\\\[-8.53581pt]
\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\lambda^{t}_{m+1}\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\lambda^{t}_{m+1}({\bm{x}}^{t}_{k_{m+1}})^{\\!\top}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\\[-2.84526pt]
\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{n}\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\lambda^{t}_{n}({\bm{x}}^{t}_{k_{n}})^{\\!\top}\\\\[2.84526pt]
\hline\cr\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt\\\\[-8.53581pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\lambda^{t}_{m+1}{\bm{x}}^{t}_{k_{m+1}}\\!\\!\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\lambda^{t}_{m+1}\bm{C}^{t}_{k_{m+1}}\\!\\!\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{n}{\bm{x}}^{t}_{k_{n}}\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\\!\\!\\!\lambda^{t}_{n}\bm{C}^{t}_{k_{n}}\end{array}\\!\right)\left(\\!\begin{array}[]{c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c}1\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt\\\ \hfil\hskip 2.84526pt&\ddots\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt\\\
\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&1\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt\\\ \hline\cr\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt&0\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&0\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\\\\[2.84526pt]
\hline\cr\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt\\\\[-8.53581pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\bm{C}^{t-}_{k_{m+1}}{\bm{x}}^{t}_{k_{m+1}}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\bm{C}^{t-}_{k_{m+1}}\bm{C}^{t}_{k_{m+1}}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip
2.84526pt&\bm{C}^{t-}_{k_{n}}{\bm{x}}^{t}_{k_{n}}\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\bm{C}^{t-}_{k_{n}}\bm{C}^{t}_{k_{n}}\end{array}\\!\right)$
$\displaystyle=\left(\\!\begin{array}[]{c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|c@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{.5mm}}|@{\hspace{1mm}}c@{\hspace{1mm}}c@{\hspace{1mm}}c}\lambda^{t}_{1}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt\\\ \hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{m}\hfil\hskip
1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt\\\\[2.84526pt] \hline\cr\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip 2.84526pt\\\\[-8.53581pt]
\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\lambda^{t}_{m+1}\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\lambda^{t}_{m+1}({\bm{x}}^{t}_{k_{m+1}})^{\\!\top}\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\\[-2.84526pt]
\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{n}\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\lambda^{t}_{n}({\bm{x}}^{t}_{k_{n}})^{\\!\top}\\\\[2.84526pt]
\hline\cr\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\hfil\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt\\\\[-8.53581pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
1.42262pt&\lambda^{t}_{m+1}{\bm{x}}^{t}_{k_{m+1}}\\!\\!\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\lambda^{t}_{m+1}\bm{C}^{t}_{k_{m+1}}\\!\\!\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\\\\[-2.84526pt] \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\ddots\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt\vrule\hskip
2.84526pt&\hfil\hskip 2.84526pt&\ddots\hfil\hskip 2.84526pt&\\\ \hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip 1.42262pt&\hfil\hskip
2.84526pt&\hfil\hskip 2.84526pt&\lambda^{t}_{n}{\bm{x}}^{t}_{k_{n}}\hfil\hskip
1.42262pt\vrule\hskip 2.84526pt&\hfil\hskip 2.84526pt&\hfil\hskip
2.84526pt&\\!\\!\\!\lambda^{t}_{n}\bm{C}^{t}_{k_{n}}\end{array}\\!\right)=\bm{C}^{t}_{j},$

where we used Lemmas 10 and 11 in the third equality. This concludes the
proof. ∎

######  Proposition 6.

Let $k\in\mathcal{K}$ be an observation point, and let
$\mathcal{C}_{k}=\\{j_{1},\dots,j_{n}\\}$ be the decision points immediately
reachable after $k$. Finally, for all $i=1,\dots,n$, let $\bm{C}^{t-}_{j_{i}}$
be any generalized invers for $\bm{C}^{t}_{j_{i}}$, and let

$\displaystyle\bm{\mu}^{t}_{k}\mathrel{:\mkern-0.25mu=}\begin{pmatrix}\bm{C}^{t-}_{j_{1}}\,{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\ \bm{C}^{t-}_{j_{n}}\,{\bm{x}}^{t}_{j_{n}}\end{pmatrix}.$

The matrix

$\displaystyle\bm{C}_{k,\ast}^{t-}\mathrel{:\mkern-0.25mu=}\begin{pmatrix}\bm{C}^{t-}_{j_{1}}\\!\\!\\!&&\\\
&\ddots&\\\ &&\\!\\!\\!\bm{C}^{t-}_{j_{n}}\
\end{pmatrix}-\frac{n-1}{n^{2}}\cdot\bm{\mu}^{t}_{k}(\bm{\mu}^{t}_{k})^{\\!\top}.$

is a generalized inverse for the autocorrelation matrix $\bm{C}^{t}_{k}$
defined in Lemma 14.

###### Proof.

In order to reduce the notational burden, let

$\bm{C}^{t\,\sim}_{k}\mathrel{:\mkern-0.25mu=}\begin{pmatrix}\bm{C}^{t-}_{j_{1}}&&\\\
&\ddots&\\\ &&\bm{C}^{t-}_{j_{n}}\ \end{pmatrix}.$

With that, we have

$\displaystyle\bm{C}^{t}_{k}\,\bm{C}^{t\,\sim}_{k}\,\bm{C}^{t}_{k}$
$\displaystyle=\begin{pmatrix}\bm{C}^{t}_{j_{1}}&\cdots&{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}\\\
\vdots&\ddots&\vdots\\\\[2.84526pt]
{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&\cdots&\bm{C}^{t}_{j_{n}}\end{pmatrix}\begin{pmatrix}\bm{C}^{t-}_{j_{1}}&&\\\
&\ddots&\\\ &&\bm{C}^{t-}_{j_{n}}\
\end{pmatrix}\begin{pmatrix}\bm{C}^{t}_{j_{1}}&\cdots&{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}\\\
\vdots&\ddots&\vdots\\\\[2.84526pt]
{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&\cdots&\bm{C}^{t}_{j_{n}}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\bm{C}^{t}_{j_{1}}&\cdots&{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}\\\
\vdots&\ddots&\vdots\\\\[2.84526pt]
{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&\cdots&\bm{C}^{t}_{j_{n}}\end{pmatrix}\begin{pmatrix}\bm{C}^{t-}_{j_{1}}\,\bm{C}^{t}_{j_{1}}&\cdots&\bm{C}^{t-}_{j_{1}}\,{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}\\\
\vdots&\ddots&\vdots\\\\[2.84526pt]
\bm{C}^{t-}_{j_{n}}\,{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&\cdots&\bm{C}^{t-}_{j_{n}}\,\bm{C}^{t}_{j_{n}}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\bm{C}^{t}_{j_{1}}+(n-1)\,{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&n\,{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{2}})^{\\!\top}&\cdots&n\,{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}\\\\[2.84526pt]
n\,{\bm{x}}^{t}_{j_{2}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&\bm{C}^{t}_{j_{2}}+(n-1)\,{\bm{x}}^{t}_{j_{2}}({\bm{x}}^{t}_{j_{2}})^{\\!\top}&\cdots&n\,{\bm{x}}^{t}_{j_{2}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}\\\
\vdots&\vdots&\ddots&\vdots\\\\[2.84526pt]
n\,{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&n\,{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{2}})^{\\!\top}&\cdots&\bm{C}^{t}_{j_{n}}+(n-1)\,{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}&\end{pmatrix}$
$\displaystyle=\bm{C}^{t}_{k}+(n-1)\,{\bm{x}}^{t}_{k}({\bm{x}}^{t}_{k})^{\\!\top},$
(32)

where we repeatedly used Lemmas 10 and 11. At the same time, we have

$\displaystyle\bm{C}^{t}_{k}\,\bm{\mu}^{t}_{k}$
$\displaystyle=\begin{pmatrix}\bm{C}^{t}_{j_{1}}&\cdots&{\bm{x}}^{t}_{j_{1}}({\bm{x}}^{t}_{j_{n}})^{\\!\top}\\\
\vdots&\ddots&\vdots\\\\[2.84526pt]
{\bm{x}}^{t}_{j_{n}}({\bm{x}}^{t}_{j_{1}})^{\\!\top}&\cdots&\bm{C}^{t}_{j_{n}}\end{pmatrix}\begin{pmatrix}\bm{C}^{t-}_{j_{1}}{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\
\bm{C}^{t-}_{j_{n}}{\bm{x}}^{t}_{j_{n}}\end{pmatrix}=\begin{pmatrix}n\,{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\ n\,{\bm{x}}^{t}_{j_{n}}\end{pmatrix}=n\,{\bm{x}}^{t}_{k},$ (33)

where again we used Lemmas 10 and 11. Putting (32) and (33) together, we
obtain

$\displaystyle\bm{C}^{t}_{k}\left(\bm{C}^{t\,\sim}_{k}-\frac{n-1}{n^{2}}\cdot\bm{\mu}^{t}_{k}(\bm{\mu}^{t}_{k})^{\\!\top}\right)\bm{C}^{t}_{k}=\bm{C}^{t}_{k}+(n-1)\,{\bm{x}}^{t}_{k}({\bm{x}}^{t}_{k})^{\\!\top}-(n-1)\,{\bm{x}}^{t}_{k}({\bm{x}}^{t}_{k})^{\\!\top}=\bm{C}^{t}_{k},$

as we wanted to show. ∎

##  Appendix E Loss Estimate

See 1

###### Proof.

For all $\bm{z}\in\operatorname{dir}\Pi$,

$\displaystyle\bm{z}^{\\!\top}\mathbb{E}_{t}[\tilde{\bm{\ell}}^{t}]$
$\displaystyle=\bm{z}^{\\!\top}\mathbb{E}_{t}\left[((\bm{y}^{t})^{\\!\top}\\!\bm{\ell}^{t})\,\bm{C}^{t-}\,\bm{y}^{t}\right]+\bm{z}^{\top}\mathbb{E}_{t}[\bm{b}^{t}]$
$\displaystyle=\bm{z}^{\\!\top}\mathbb{E}_{t}\left[\bm{C}^{t-}\,\bm{y}^{t}(\bm{y}^{t})^{\\!\top}\,\bm{\ell}^{t}\right]$
$\displaystyle=\bm{z}^{\\!\top}\bm{C}^{t-}\,\bm{C}^{t}\bm{\ell}^{t}.$

Using the inclusion $\operatorname{dir}\Pi\subseteq\operatorname{span}\Pi$
together with Lemma 10 gives the statement. ∎

Propositions 5 and 6 give explicit formulas for inductively constructing a
generalized inverse $\bm{C}_{\ast}^{t-}$ of the autocorrelation matrix
$\bm{C}^{t}$ of the natural sampling scheme for sequential decision processes
needed in Proposition 1.

In the next subsection we focus on studying the particular orthogonal vector
$\bm{b}^{t}_{*}$ that we use in our algorithm.

###  E.1 Orthogonal Vector

The primary role of the orthogonal vector $\bm{b}^{t}$ is to prevent the
subtraction $-(n-1)/n\bm{\mu}_{k}^{t}$ in Proposition 6 from creating negative
entries in the loss estimate. It is important to prevent negative entries in
the loss estimate because our refined local-norm-based bound for the online
mirror descent algorithm paired with the dilated entropy DGF (Theorem 1) is
contingent on it.

The insight that we use in the construction of $\bm{b}_{*}^{t}$ is that the
vector $\bm{\mu}_{k}^{t}$ in Proposition 6 is orthogonal to
$\operatorname{dir}\Pi_{k}$ for all $k\in\mathcal{K}$ because of Lemma 11. So,
we construct the vector $\bm{b}^{t}\perp\operatorname{dir}\Pi$ inductively to
cancel the effect of all $\bm{\mu}_{k}^{t}$, as follows:

  * •

Consider a decision point $j\in\mathcal{J}$. Let $\\{a_{1},\dots,a_{m}\\}$ at
$j$ be the terminal actions, and let the remaining actions
$\\{a_{m+1},\dots,a_{n}\\}$ be non-terminal, leading to observation nodes
$k_{m+1},\dots,k_{n}$ respectively. Furthermore, let the $a$ be the action
that was selected at $j$ by the pure sequence-form strategy $\bm{y}^{t}$. If
$a\leq m$, we let

$\bm{b}_{j,*}^{t}=\left(\frac{1}{\lambda^{t}_{a}}(N_{j}-1)\bm{e}_{a},\bm{0},\dots,\bm{0}\right).$
(34)

Otherwise, $a\in\\{m+1,\dots,n\\}$ is a non-terminal action, and we
recursively let

$\bm{b}_{j,*}^{t}=\left(\frac{1}{\lambda^{t}_{a}}(N_{j}-N_{k_{a}})\bm{e}_{a},\bm{0},\dots,\frac{1}{\lambda^{t}_{a}}\bm{b}^{t}_{k_{a},*},\bm{0}\right).$
(35)

So, in particular, at all terminal decision points $j\in\mathcal{J}$ we have
$\bm{b}^{t}_{j}=\bm{0}$ since $N_{j}=1$.

  * •

At all observation points $k\in\mathcal{K}$, we let

$\bm{b}^{t}_{k,*}=(\bm{b}^{t}_{j_{1},*},\dots,\bm{b}^{t}_{j_{n},*})+\frac{n-1}{n}\bm{\mu}^{t}_{k},$
(36)

where $\\{j_{1},\dots,j_{n}\\}=S_{k}$.

The vector $\bm{b}_{*}^{t}$ we just defined satisfies the following property.

######  Lemma 15.

At all times $t$ and for all nodes $v\in\mathcal{J}\cup\mathcal{K}$,

$\mathbb{E}_{t}[\bm{b}^{t}_{v,*}]^{\top}\bm{z}_{v}=N_{v}-1\qquad\forall\,\bm{z}_{v}\in
Q_{v}.$

###### Proof.

We prove the lemma by induction on the structure of the decision process:

  * •

First case: $v\in\mathcal{J}$ is a terminal decision point. In this case
$N_{v}=1$. Furthermore, by construction $\bm{b}^{t}_{v,*}=\bm{0}$, so
$\mathbb{E}_{t}[\bm{b}_{v,*}^{t}]^{\top}\bm{z}_{v}=0=N_{v}-1$.

  * •

Second case: $v\in\mathcal{J}$ is a (generic) decision point. In this case,
taking the expectation of $\bm{b}_{v}^{t}$ (Equations 34 and 35) over all
possible choices of action $a$ at $v$ (action $a$ is chosen with probability
$\lambda^{t}_{a}$, yields

$\mathbb{E}[\bm{b}_{v,*}^{t}]=\left(N_{v}-1,\dots,N_{v}-1,N_{v}-N_{k_{m+1}},\dots,N_{v}-N_{k_{n}},\mathbb{E}_{t}[\bm{b}_{k_{m+1},*}^{t}],\dots,\mathbb{E}_{t}[\bm{b}_{k_{n},*}^{t}]\right).$

From (6), any $\bm{z}_{v}\in Q_{v}$ can be written in the from
$(\lambda^{\prime}_{1},\dots,\lambda^{\prime}_{n},\lambda^{\prime}_{m+1}\bm{z}_{k_{m+1}},\dots,\lambda^{\prime}_{n}\bm{z}_{k_{n}})$
for appropriate
$(\lambda^{\prime}_{1},\dots,\lambda^{\prime}_{n})\in\Delta^{n}$ and
$\bm{z}_{k_{i}}\in Q_{k_{i}}$ for $i\in\\{m+1,\dots,n\\}$. So,

$\mathbb{E}[\bm{b}^{t}_{v,*}]^{\top}\bm{z}_{v}=\sum_{i=1}^{m}(N_{v}-1)\lambda^{\prime}_{i}+\sum_{i=m+1}^{n}\left(\lambda^{\prime}_{i}(N_{v}-N_{k_{i}})+\lambda^{\prime}_{i}\mathbb{E}[\bm{b}^{t}_{k_{i},*}]^{\top}\bm{z}_{k_{i}}\right).$

Finally, using the inductive hypothesis
$\mathbb{E}[\bm{b}^{t}_{k_{i},*}]^{\top}\bm{z}_{k_{i}}=N_{k_{i}}-1$ for all
$i\in\\{m+1,\dots,n\\}$,

$\displaystyle\mathbb{E}[\bm{b}^{t}_{v,*}]^{\top}\bm{z}_{v}$
$\displaystyle=\sum_{i=1}^{m}(N_{v}-1)\lambda^{\prime}_{i}+\sum_{i=m+1}^{n}(N_{v}-N_{k_{i}})+(N_{k_{i}}-1)$
$\displaystyle=\sum_{i=1}^{m}(N_{v}-1)\lambda^{\prime}_{i}+\sum_{i=m+1}^{n}\lambda^{\prime}_{i}(N_{v}-1)=N_{v}-1,$

where we used the fact that
$(\lambda^{\prime}_{1},\dots,\lambda^{\prime}_{n})\in\Delta^{n}$ in the last
equality.

  * •

Third case: $v\in\mathcal{K}$ is an observation point. In this case, the
expectation of $\bm{b}_{v}^{t}$ (Equation 36) is

$\mathbb{E}[\bm{b}^{t}_{v,*}]=(\mathbb{E}[\bm{b}^{t}_{j_{1},*}],\dots\mathbb{E}[\bm{b}^{t}_{j_{n},*}])+\frac{n-1}{n}\bm{\mu}_{k}^{t}.$

So, using the inductive hypothesis and Lemma 11, we find that

$\mathbb{E}[\bm{b}^{t}_{v,*}]^{\top}\bm{z}_{v}=\sum_{i=1}^{n}(N_{j_{i}}-1)+\frac{n-1}{n}\cdot
n=-1+\sum_{i=1}^{n}N_{j_{i}}.$

Using the fact that $N_{v}=\sum_{i=1}^{n}N_{j_{i}}$ yields the statement.∎

Since any point in $\operatorname{dir}\Pi$ is the difference of two points in
$Q$, Lemma 15 immediately implies the following.

######  Corollary 3.

At all times $t$,
$\mathbb{E}_{t}[\bm{b}^{t}_{v,*}]\perp\bm{z}_{v}\quad\forall\bm{z}_{v}\in\operatorname{dir}\Pi.$

So, our (inductive) construction of $\bm{b}^{t}$ satisfies the requirements of
Proposition 1. Below we will show that it always leads to non-negative loss
estimates.

###  E.2 Algorithm for Constructing the Loss Estimate in Linear Time

Let $l^{t}\mathrel{:\mkern-0.25mu=}(\bm{\ell}^{t})^{\top}\bm{y}^{t}$ denote
the bandit feedback (loss evaluation) received at time $t$ by the decision
maker. In this section, we will show that the unbiased loss estimate
$\tilde{\bm{\ell}}^{t}=l^{t}\cdot\bm{C}^{t-}\bm{y}^{t}+\bm{b}^{t}$, as defined
in Proposition 1, can be inductively computed in linear time in the size of
the decision process as in Algorithm 3 (which is a copy of the algorithm in
the body of the paper).

1 $\tilde{\bm{\ell}}^{t}\leftarrow\bm{0}\in\mathbb{R}_{>0}^{|\Sigma|}$

2 subroutine  _$\textsc{Traverse}(v,\alpha_{v})$_

3 if  _$v\in\mathcal{K}$_ then

4 for  _$s\in S_{v}$_ do

5
$\displaystyle\textsc{Traverse}\left(\rho(v,s),\frac{\alpha_{v}}{|S_{v}|}+\frac{|S_{v}|-1}{|S_{v}|}(1-l)y^{t}_{p_{v}}\right)$

6

7 else [$\triangleright$ that is, $v\in\mathcal{J}$]

8 for  _$a\in A_{v}$_ do

9 if  _$\rho(v,a)\neq\diamond$_ then

10
$\displaystyle\bm{\ell}^{t}_{ja}\leftarrow\frac{y^{t}_{va}}{{x}^{t}_{va}}(N_{v}-N_{\rho(v,a)})$

11
$\displaystyle\textsc{Traverse}\left(\rho(v,a),\frac{{x}_{p_{v}}}{{x}_{va}}\alpha_{v}\right)$

12

13 else if  _$\rho(v,a)=\diamond$_ then

14
$\displaystyle\bm{\ell}^{t}_{ja}\leftarrow\frac{\alpha_{v}}{{x}^{t}_{p_{v}}}+\frac{y^{t}_{va}}{{x}^{t}_{va}}(l+N_{v}-1)$

15

$\textsc{Traverse}(r,0)$

[$\triangleright$ $r$: root of the decision process]

16 return $\tilde{\bm{\ell}}^{t}$

Algorithm 7 $\textsc{LossEstimate}(l,{\bm{x}}^{t},\bm{y}^{t})$

See 2

###### Proof.

Our construction revolves around the following quantity, indexed over nodes
$v\in\mathcal{J}\cup\mathcal{K}$:

$\bm{h}^{t}_{v}(\alpha)\mathrel{:\mkern-0.25mu=}\frac{y^{t}_{p_{v}}}{{x}^{t}_{p_{v}}}\,\tilde{\bm{\ell}}^{t}_{v}+\frac{\alpha}{{x}^{t}_{p_{v}}}\bm{C}_{v,*}^{t-}{\bm{x}}_{v}^{t}=l^{t}\cdot\frac{y^{t}_{p_{v}}}{{x}^{t}_{p_{v}}}\bm{C}_{v,*}^{t-}\,\bm{y}_{v}^{t}+\beta\,\bm{b}_{v,*}^{t}+\frac{\alpha}{{x}^{t}_{p_{v}}}\bm{C}_{v,*}^{t-}{\bm{x}}_{v}^{t}.$

The loss estimate $\tilde{\bm{\ell}}^{t}$ coincides with $\bm{h}_{r}^{t}(0)$
where $r$ is the root of the sequential decision problem. We now show that
$\bm{h}^{t}_{v}(\alpha,\beta)$ can be constructed inductively over the
structure of the sequential decision process:

  * •

If $v\in\mathcal{J}$ is a decision node, let $\\{a_{1},\dots,a_{m}\\}$ be the
terminal actions at $v$, and let $\\{a_{m+1},\dots,a_{n}\\}$ be the non-
terminal actions at $v$ (if any). Finally, let $k_{i}=\rho(v,a_{i})$ for
$i=m+1,\dots,n$. In accordance with Equation 6,
${\bm{x}}^{t}_{v}=(\lambda_{1}^{t},\dots,\lambda_{n}^{t},\lambda_{k_{m+1}}^{t}{\bm{x}}_{k_{i}}^{t},\dots,\lambda_{k_{n}}^{t}{\bm{x}}_{k_{n}}^{t})$.
Similarly, we let
$y^{t}_{v}=(\nu_{1}^{t},\dots,\nu_{n}^{t},\nu_{k_{m+1}}^{t}\bm{y}_{k_{i}}^{t},\dots,\nu_{k_{n}}^{t}\bm{y}_{k_{n}}^{t})$.

Using Proposition 5 and Equations 34 and 35, we can write

$\displaystyle\allowdisplaybreaks\bm{h}^{t}_{v}(\alpha)$
$\displaystyle=l^{t}\frac{y^{t}_{p_{v}}}{{x}^{t}_{p_{v}}}\begin{pmatrix}\frac{\nu^{t}_{1}}{\lambda^{t}_{1}}\\\
\vdots\\\ \frac{\nu^{t}_{m}}{\lambda^{t}_{m}}\\\ 0\\\ \vdots\\\ 0\\\
\frac{\nu^{t}_{m+1}}{\lambda^{t}_{m+1}}\bm{C}^{t-}_{k_{m+1},*}\bm{y}^{t}_{k_{m+1}}\\\
\vdots\\\
\frac{\nu^{t}_{n}}{\lambda^{t}_{n}}\bm{C}^{t-}_{k_{n},*}\bm{y}^{t}_{k_{n}}\\\
\end{pmatrix}+\frac{y^{t}_{p_{v}}}{{x}^{t}_{p_{v}}}\begin{pmatrix}\frac{\nu^{t}_{1}}{\lambda_{1}^{t}}(N_{v}-1)\\\
\vdots\\\ \frac{\nu^{t}_{m}}{\lambda_{m}^{t}}(N_{v}-1)\\\
\frac{\nu^{t}_{m+1}}{\lambda_{m}^{t}}(N_{v}-N_{k_{m}})\\\ \vdots\\\
\frac{\nu^{t}_{n}}{\lambda_{n}^{t}}(N_{v}-N_{k_{n}})\\\
\frac{\nu^{t}_{m+1}}{\lambda^{t}_{m+1}}\bm{b}^{t}_{k_{m+1},*}\\\ \vdots\\\
\frac{\nu^{t}_{n}}{\lambda^{t}_{n}}\bm{b}^{t}_{k_{n},*}\\\
\end{pmatrix}+\frac{\alpha}{{x}^{t}_{p_{v}}}\begin{pmatrix}1\\\ \vdots\\\ 1\\\
0\\\ \vdots\\\ 0\\\ \bm{C}^{t-}_{k_{m+1},*}{\bm{x}}^{t}_{k_{m+1}}\\\ \vdots\\\
\bm{C}^{t-}_{k_{n},*}{\bm{x}}^{t}_{k_{n}}\\\ \end{pmatrix}$
$\displaystyle=\begin{pmatrix}\frac{\alpha}{{x}^{t}_{p_{v}}}+\frac{y^{t}_{p_{v}}\nu_{1}^{t}}{{x}^{t}_{p_{v}}\lambda^{t}_{1}}(l^{t}+N_{v}-1)\\\
\vdots\\\
\frac{\alpha}{{x}^{t}_{p_{v}}}+\frac{y^{t}_{p_{v}}\nu_{m}^{t}}{{x}^{t}_{p_{v}}\lambda^{t}_{m}}(l^{t}+N_{v}-1)\\\
\frac{y^{t}_{p_{v}}\nu_{m+1}^{t}}{{x}^{t}_{p_{v}}\lambda^{t}_{m+1}}(N_{v}-N_{k_{m+1}})\\\
\vdots\\\
\frac{y^{t}_{p_{v}}\nu_{n}^{t}}{{x}^{t}_{p_{v}}\lambda^{t}_{n}}(N_{v}-N_{k_{n}})\\\
\frac{y^{t}_{p_{v}}\nu_{m+1}^{t}}{{x}^{t}_{p_{v}}\lambda^{t}_{m+1}}(l^{t}\cdot\bm{C}^{t-}_{k_{m+1},*}\bm{y}^{t}_{k_{m+1}}+\bm{b}^{t}_{k_{m+1},*})+\frac{\alpha\lambda^{t}_{m+1}}{{x}^{t}_{p_{v}}\lambda^{t}_{m+1}}\bm{C}^{t-}_{k_{m+1},*}\bm{y}^{t}_{k_{m+1}}\\\
\vdots\\\
\frac{y^{t}_{p_{v}}\nu_{n}^{t}}{{x}^{t}_{p_{v}}\lambda^{t}_{n}}(l^{t}\cdot\bm{C}^{t-}_{k_{n},*}\bm{y}^{t}_{k_{n}}+\bm{b}^{t}_{k_{n},*})+\frac{\alpha\lambda^{t}_{n}}{{x}^{t}_{p_{v}}\lambda^{t}_{n}}\bm{C}^{t-}_{k_{n},*}\bm{y}^{t}_{k_{n}}\\\
\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\frac{\alpha}{{x}^{t}_{p_{v}}}+\frac{y^{t}_{va_{1}}}{{x}^{t}_{va_{1}}}(l^{t}+N_{v}-1)\\\
\vdots\\\
\frac{\alpha}{{x}^{t}_{p_{v}}}+\frac{y^{t}_{va_{m}}}{{x}^{t}_{va_{m}}}(l^{t}+N_{v}-1)\\\
\frac{y^{t}_{va_{m+1}}}{{x}^{t}_{va_{m+1}}}(N_{v}-N_{k_{m+1}})\\\ \vdots\\\
\frac{y^{t}_{va_{n}}}{{x}^{t}_{va_{n}}}(N_{v}-N_{k_{n}})\\\
\bm{h}_{k_{m+1}}^{t}\left(\alpha\lambda^{t}_{m+1}\right)\\\ \vdots\\\
\bm{h}_{k_{n}}^{t}\left(\alpha\lambda^{t}_{n}\right)\\\ \end{pmatrix}$ (37)

  * •

If $v\in\mathcal{K}$ is an observation point, let
$\\{j_{1},\dots,j_{n}\\}=\mathcal{C}_{v}$ be the decision points that are
immediately reachable from $v$. From Equation 8 and Equation 5 we can write
${\bm{x}}^{t}_{v}=({\bm{x}}^{t}_{j_{1}},\dots,{\bm{x}}^{t}_{j_{n}})$ and
$\bm{y}^{t}_{v}=(\bm{y}^{t}_{j_{1}},\dots,\bm{y}^{t}_{j_{n}})$. Using
Proposition 6 and Equation 36, we can recursively expand $\bm{C}^{t-}_{v,*}$
and $\bm{b}^{t}_{v,*}$ and write

$\displaystyle\bm{h}_{v}^{t}(\alpha)$
$\displaystyle=l^{t}\frac{y^{t}_{p_{v}}}{{x}^{t}_{p_{v}}}\begin{pmatrix}\bm{C}^{t-}_{j_{1},*}&&\\\
&\ddots&\\\
&&\bm{C}^{t-}_{j_{n},*}\end{pmatrix}\begin{pmatrix}\bm{y}^{t}_{j_{1}}\\\
\vdots\\\
\bm{y}^{t}_{j_{n}}\end{pmatrix}+\frac{y^{t}_{p_{v}}}{{x}^{t}_{p_{v}}}(1-l^{t})\frac{n-1}{n}\begin{pmatrix}\bm{C}^{t-}_{j_{1},*}{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\ \bm{C}^{t-}_{j_{n},*}{\bm{x}}^{t}_{j_{n}}\\\
\end{pmatrix}+\frac{y^{t}_{p_{v}}}{{x}^{t}_{p_{v}}}\begin{pmatrix}\bm{b}^{t}_{j_{1},*}\\\
\vdots\\\ \bm{b}^{t}_{j_{n},*}\\\ \end{pmatrix}$ $\displaystyle\hskip
284.52756pt+\frac{\alpha}{n{x}^{t}_{p_{v}}}\begin{pmatrix}\bm{C}^{t-}_{j_{1},*}{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\ \bm{C}^{t-}_{j_{n},*}{\bm{x}}^{t}_{j_{n}}\\\ \end{pmatrix}$
$\displaystyle=\begin{pmatrix}\bm{h}_{j_{1}}^{t}\left(\frac{\alpha}{n}+(1-l^{t})\frac{n-1}{n}y^{t}_{p_{v}}\right)\\\
\vdots\\\
\bm{h}_{j_{n}}^{t}\left(\frac{\alpha}{n}+(1-l^{t})\frac{n-1}{n}y^{t}_{p_{v}}\right)\\\
\end{pmatrix}.$ (38)

Equations 37 and 38 together show that $\bm{h}^{t}_{v}(\alpha)$ can be
computed inductively along the structure of the decision problem.

Routine $\textsc{Traverse}(v,\alpha_{v})$ in Algorithm 3 implementes the
recursive construction $\bm{h}^{t}(\alpha)$ by operationalizing Equations 37
and 38 into code. Specifically, for all $v\in\mathcal{J}\cup\mathcal{K}$ and
$\alpha_{v}$, $\textsc{Traverse}(v,\alpha_{v})$ computes
$\bm{h}^{t}_{v}(\alpha_{v})$. Lines 7-12 of Algorithm 7 correspond to Equation
37, while Line 5 corresponds to Equation 38.

Since the algorithm performs constant work per each sequence, the algorithm
runs in linear time in the number of sequences $|\Sigma|$ of the sequential
decision process. ∎

###  E.3 Expected Local Dual Norm of Loss Estimate

We start from a technical lemma.

######  Lemma 16.

For all nodes $v\in\mathcal{J}\cup\mathcal{K}$,

$\|\bm{C}^{t-}_{v,\ast}\,{\bm{x}}_{v}\|_{\ast,{\bm{x}}_{v}}^{2}\leq 2.$

###### Proof.

We prove the slightly stronger bound

$\|\bm{C}^{t-}_{v,\ast}\,{\bm{x}}_{v}\|_{\ast,{\bm{x}}_{v}}^{2}\leq
2-\frac{1}{w_{v}}.$

by induction on the structure of the decision process:

  * •

First case: $v\in\mathcal{J}$ is a terminal decision point. This is the base
case. In this case,
${\bm{x}}^{t}=(\frac{1}{\lambda^{t}_{1}},\dots,\frac{1}{\lambda^{t}_{n}})\in\Delta^{n}$,
and from Proposition 5 we have

$\bm{C}_{v,*}^{t-}=\begin{pmatrix}\frac{1}{\lambda_{1}^{t}}&&\\\ &\ddots&\\\
&&\lambda_{n}^{t}\end{pmatrix}.$

So, using Proposition 5 and Corollary 1,

$\bm{C}^{t-}_{v,\ast}\,{\bm{x}}_{v}=(1,\dots,1)\implies\|\bm{C}^{t-}_{v,\ast}\,{\bm{x}}_{v}\|_{\ast,{\bm{x}}_{v}}^{2}=\sum_{i=1}^{n}\frac{\lambda_{i}^{t}}{w_{v}}=\frac{1}{w_{v}}=\frac{1}{2}\leq
2-\frac{1}{2}=2-\frac{1}{w_{v}}.$

  * •

Second case: $v\in\mathcal{J}$ is a (generic) decision point. In this case,

${\bm{x}}^{t}=(\lambda^{t}_{1},\dots,\lambda^{t}_{n},\lambda^{t}_{m+1}{\bm{x}}^{t}_{k_{m+1}},\dots,\lambda^{t}_{n}{\bm{x}}^{t}_{k_{n}})$

for appropriate $(\lambda^{t}_{1},\dots,\lambda^{t}_{n})\in\Delta^{n}$
(Equation 6). So, using Proposition 5,

$\bm{C}^{t-}_{v,\ast}\,{\bm{x}}_{v}=(1,\dots,1,0,\dots,0,\bm{C}^{t-}_{m+1}{\bm{x}}^{t}_{k_{m+1}},\dots,\bm{C}^{t-}_{n}{\bm{x}}^{t}_{k_{n}}).$

Using Corollary 1, we have

$\displaystyle\|\bm{C}^{t-}_{v,\ast}\|_{\ast,{\bm{x}}_{v}}^{2}$
$\displaystyle=\sum_{i=1}^{n}\frac{\lambda_{i}^{t}}{w_{v}}+\sum_{i=m+1}^{n}\frac{\lambda_{i}^{t}}{w_{v}}\left(({\bm{x}}_{k_{i}}^{t})^{\top}\bm{C}^{t-}_{k_{i},*}{\bm{x}}^{t}_{k_{i}}\right)^{2}+\sum_{i=m+1}^{n}\lambda_{i}^{t}\|\bm{C}^{t-}_{k_{i}}{\bm{x}}^{t}_{k_{i}}\|_{\ast,{\bm{x}}^{t}_{k_{i}}}^{2}$
$\displaystyle=\sum_{i=1}^{n}\frac{\lambda_{i}^{t}}{w_{v}}+\sum_{i=m+1}^{n}\lambda_{i}^{t}\|\bm{C}^{t-}_{k_{i}}{\bm{x}}^{t}_{k_{i}}\|_{\ast,{\bm{x}}^{t}_{k_{i}}}^{2}$
$\displaystyle=\frac{1}{w_{v}}+\sum_{i=m+1}^{n}\lambda_{i}^{t}\|\bm{C}^{t-}_{k_{i}}{\bm{x}}^{t}_{k_{i}}\|_{\ast,{\bm{x}}^{t}_{k_{i}}}^{2}$
$\displaystyle\leq\frac{1}{w_{v}}+\max_{i=m+1}^{n}\|\bm{C}^{t-}_{k_{i}}{\bm{x}}^{t}_{k_{i}}\|_{\ast,{\bm{x}}^{t}_{k_{i}}}^{2}$
$\displaystyle\leq\frac{1}{w_{v}}+\max_{i=m+1}^{n}\left\\{2-\frac{1}{w_{k_{i}}}\right\\}$

where the second equality holds from Lemma 11, the first inequality follows
from using the fact that
$(\lambda^{t}_{1},\dots,\lambda^{t}_{n})\in\Delta^{n}$, and the second
inequality follows from the inductive hypothesis. Using the fact that
$w_{v}\geq 2w_{k_{i}}$ for all $i=m+1,\dots,n$ (Definition 1), we obtain

$\|\bm{C}^{t-}_{v,\ast}\|_{\ast,{\bm{x}}_{v}}^{2}\leq\frac{1}{w_{v}}+2-\frac{2}{w_{v}}=2-\frac{1}{w_{v}},$

completing the inductive step.

  * •

Third case: $v\in\mathcal{K}$ is an observation point. Let
$\\{j_{1},\dots,j_{n}\\}=\mathcal{C}_{v}$. Proposition 6 yields

$\bm{C}^{t-}_{v,*}{\bm{x}}^{t}_{v}=\frac{1}{n}\left(\bm{C}^{t-}_{j_{1},*}{\bm{x}}^{t}_{j_{i}},\dots,\bm{C}^{t-}_{j_{n},*}{\bm{x}}^{t}_{j_{n}}\right).$

So,

$\displaystyle\bm{C}^{t-}_{v,*}{\bm{x}}^{t}_{v}$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}\|\bm{C}^{t-}_{j_{i},*}\|_{\ast,{\bm{x}}^{t}_{j_{i}}}^{2}$
$\displaystyle\leq\frac{1}{n^{2}}\sum_{i=1}^{n}\left(2-\frac{1}{w_{j_{i}}}\right)$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\left(2-\frac{1}{w_{j_{i}}}\right)$
$\displaystyle\leq\max_{i=1}^{n}\left\\{2-\frac{1}{w_{j_{i}}}\right\\}\leq
2-\frac{1}{w_{v}},$

where the last inequality follows from the observation that $w_{j_{i}}\leq
w_{v}$ for all $i=1,\dots,n$. ∎

See 2

###### Proof.

In order to prove the statement, we will prove the slightly stronger statement
that for all $v\in\mathcal{J}\cup\mathcal{K}$ and $\alpha\in[0,1]$,

$\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}_{v}^{t}}^{2}\right]\leq
2N_{v}^{2}+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)N_{v}.$

Our proof is by induction over the sequential decision process structure:

  * •

First case: $v\in\mathcal{J}$ is a terminal decision node. Let
${\bm{x}}^{t}_{v}=(\lambda^{t}_{1},\dots,\lambda^{t}_{n})\in\Delta^{n}$, in
accordance with Equation 7. By the sampling scheme,
$\bm{y}^{t}_{v}=\bm{e}_{a}$ with probability $\lambda^{t}_{a}$. Furthermore,

$\tilde{\bm{\ell}}^{t}_{v}=l^{t}\bm{C}^{t-}_{v,\ast}\bm{y}^{t}_{v}+\bm{b}^{t}_{v,*}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}_{v}^{t}=\begin{pmatrix}\alpha\\\
\vdots\\\ \alpha\end{pmatrix}+\frac{l^{t}}{\lambda^{t}_{a}}\bm{e}_{a}.$

So,

$\displaystyle\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}_{v}^{t}}^{2}\right]$
$\displaystyle=\sum_{i=1}^{n}\lambda^{t}_{i}\left\|\begin{pmatrix}\alpha\\\
\vdots\\\
\alpha\end{pmatrix}+\frac{l^{t}}{\lambda^{t}_{i}}\bm{e}_{i}\right\|_{\ast,{\bm{x}}^{t}_{v}}^{2}$
$\displaystyle=\frac{1}{w_{v}}\sum_{i=1}^{n}\lambda_{i}^{t}\left(\lambda_{i}\left(\alpha+\frac{l^{t}}{\lambda^{t}_{i}}\right)^{2}+\sum_{j\neq
i}\lambda^{t}_{j}\alpha^{2}\right)$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{n}\lambda_{i}^{t}\left(\alpha^{2}+2\alpha\,l^{t}+\frac{(l^{t})^{2}}{\lambda^{t}_{i}}\right)$
$\displaystyle=\frac{1}{2}\left(\alpha^{2}+2\alpha l^{t}+n(l^{t})^{2}\right),$

where the second equality follows from expanding the definition of local dual
norm. Using the hypothesis that $l^{t}\in[0,1]$, for all $\alpha\in[0,1]$ we
find

$\displaystyle\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}_{v}^{t}}^{2}\right]\leq\frac{3+n}{2}\leq
2+n^{2}\leq 2N_{v}^{2}+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)N_{v}.$

  * •

Second case: $v\in\mathcal{K}$. Let $\\{j_{1},\dots,j_{n}\\}=\mathcal{C}_{v}$.
Furthermore, let
${\bm{x}}_{v}^{t}=({\bm{x}}_{j_{1}}^{t},\dots,{\bm{x}}_{j_{n}}^{t})$ and
$\bm{y}_{v}^{t}=(\bm{y}_{j_{1}}^{t},\dots,\bm{y}_{j_{n}}^{t})$ in accordance
with (8) and (5), respectively. Using Proposition 6, we have

$\displaystyle\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}$
$\displaystyle=l^{t}\bm{C}^{t-}_{v,\ast}\bm{y}_{v}^{t}+\bm{b}^{t}_{v}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}$
$\displaystyle=l^{t}\begin{pmatrix}\bm{C}^{t-}_{j_{1},\ast}&&\\\ &\ddots&\\\
&&\bm{C}^{t-}_{j_{n},\ast}\end{pmatrix}\begin{pmatrix}\bm{y}^{t}_{j_{1}}\\\
\vdots\\\
\bm{y}^{t}_{j_{n}}\end{pmatrix}+\begin{pmatrix}\bm{b}^{t}_{j_{1},\ast}\\\
\vdots\\\
\bm{b}^{t}_{j_{n},\ast}\end{pmatrix}+\frac{\alpha+(n-1)(1-l^{t})}{n}\begin{pmatrix}\bm{C}^{t-}_{j_{1},\ast}{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\ \bm{C}^{t-}_{j_{n},\ast}{\bm{x}}^{t}_{j_{n}}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\tilde{\bm{\ell}}^{t}_{j_{1}}\\\ \vdots\\\
\tilde{\bm{\ell}}^{t}_{j_{n}}\end{pmatrix}+\frac{\alpha+(n-1)(1-l^{t})}{n}\begin{pmatrix}\bm{C}^{t-}_{j_{1},\ast}{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\ \bm{C}^{t-}_{j_{n},\ast}{\bm{x}}^{t}_{j_{n}}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\tilde{\bm{\ell}}^{t}_{j_{1}}+\alpha^{\prime}\cdot\bm{C}^{t-}_{j_{1},\ast}{\bm{x}}^{t}_{j_{1}}\\\
\vdots\\\
\tilde{\bm{\ell}}^{t}_{j_{n}}+\alpha^{\prime}\cdot\bm{C}^{t-}_{j_{n},\ast}{\bm{x}}^{t}_{j_{n}}\end{pmatrix},\quad\text{where
}\alpha^{\prime}\mathrel{:\mkern-0.25mu=}\frac{\alpha+(n-1)(1-l^{t})}{n}.$

Using the assumption that $l^{t}\in[0,1]$, for all $\alpha\in[0,1]$ we have
$\alpha^{\prime}\in[0,1]$. Hence, using Corollary 1 we obtain that for all
$\alpha\in[0,1]$,

$\displaystyle\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}$
$\displaystyle=\sum_{i=1}^{n}\|\tilde{\bm{\ell}}^{t}_{j_{i}}+\alpha^{\prime}\cdot\bm{C}^{t-}_{j_{i},\ast}{\bm{x}}^{t}_{j_{i}}\|_{\ast,{\bm{x}}^{t}_{j_{i}}}^{2}$

Taking expectations and using the inductive hypothesis, we have

$\displaystyle\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}\right]$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}^{t}_{j_{i}}+\alpha^{\prime}\cdot\bm{C}^{t-}_{j_{i},\ast}{\bm{x}}^{t}_{j_{i}}\|_{\ast,{\bm{x}}^{t}_{j_{i}}}^{2}\right]$
$\displaystyle\leq\sum_{i=1}^{n}\left(2N_{j_{i}}^{2}+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)N_{j_{i}}\right)$
$\displaystyle\leq
2\left(\sum_{i=1}^{n}N_{j_{i}}\right)^{2}+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)\sum_{i=1}^{n}N_{j_{i}}$
$\displaystyle=2N_{v}^{2}+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)N_{v}.$

  * •

Third case: $v\in\mathcal{J}$ is a generic decision node. Let
$\\{1,\dots,m\\}$ be the terminal decision actions at $v$, and
$\\{m+1,\dots,n\\}$ be the remaining, non-terminal decision actions, leading
to observation points $k_{m+1},\dots,k_{n}$, respectively. Furthermore, let
${\bm{x}}^{t}_{v}=(\lambda_{1},\dots,\lambda_{n},\lambda_{m+1}{\bm{x}}^{t}_{k_{m+1}},\dots,\lambda_{n}{\bm{x}}^{t}_{k_{n}})$
in accordance with Equation 6. Action $a\in\\{1,\dots,n\\}$ is selected with
probability $\lambda_{i}$.

We break the analysis according to whether the sampled action $a$ is terminal
or not.

    * –

If $a$ is terminal, from the definition of $\bm{C}^{t-}_{v,*}$ (Proposition
5), $\bm{b}^{t}_{v,*}$ (Equation 34) and Corollary 1 we have

$\displaystyle\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}$
$\displaystyle=\frac{1}{w_{v}}\sum_{i=1}^{m}\lambda_{i}^{t}\left(\alpha+\frac{\mathds{1}[i=a]}{\lambda_{a}^{t}}N_{v}\right)^{2}$
$\displaystyle\hskip
85.35826pt+\sum_{i=m+1}^{n}\left(\frac{\lambda^{t}_{i}}{w_{v}}(\alpha({\bm{x}}_{k_{i}}^{t})^{\top}\bm{C}^{t-}_{k_{i}}{\bm{x}}_{k_{i}}^{t})^{2}+\lambda^{t}_{i}\|\alpha\bm{C}^{t-}_{k_{i}}{\bm{x}}^{t}_{k_{i}}\|_{\ast,{\bm{x}}^{t}_{k_{i}}}^{2}\right)$
$\displaystyle=\frac{\alpha^{2}}{w_{v}}+\frac{2\alpha}{w_{v}}N_{v}+\frac{N_{v}^{2}}{w_{v}\lambda_{a}^{t}}+\alpha^{2}\sum_{i=m+1}^{n}\lambda_{i}^{t}\|\bm{C}^{t-}_{k_{i}}{\bm{x}}^{t}_{k_{i}}\|_{\ast,{\bm{x}}_{k_{i}}}^{2},$

where we used Lemma 11 and the fact that
$(\lambda_{1}^{t},\dots,\lambda_{n}^{t})\in\Delta^{n}$ in the second equality.
Using Lemma 16, the fact that $w_{v}\geq 2$ for all $v$, and the hypothesis
$\alpha\in[0,1]$, we can bound the squared dual norm as

$\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}\leq
4N_{v}+\frac{N_{v}^{2}}{w_{v}\lambda_{a}^{t}}.$

    * –

If $a$ is terminal, from the definition of $\bm{C}^{t-}_{v,*}$ (Proposition
5), $\bm{b}^{t}_{v,*}$ (Equation 35) and Corollary 1 we have

$\displaystyle\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}$
$\displaystyle=\frac{1}{w_{v}}\left(\sum_{i=1}^{m}\lambda_{i}^{t}\alpha^{2}\right)+\frac{\lambda^{t}_{a}}{w_{v}}\left(\frac{1}{\lambda_{a}^{t}}(N_{v}-N_{\rho(v,a)})+\frac{1}{\lambda_{a}^{t}}({\bm{x}}_{k_{i}}^{t})^{\top}\left(\tilde{\bm{\ell}}^{t}_{k_{a}}+(\alpha\lambda_{a}^{t})\bm{C}^{t-}_{k_{a}}{\bm{x}}_{k_{i}}^{t}\right)\right)^{2}$
$\displaystyle\hskip
28.45274pt+\frac{1}{\lambda^{t}_{a}}\left\|\tilde{\bm{\ell}}^{t}_{k_{a}}+(\alpha\lambda_{a}^{t})\bm{C}^{t-}_{k_{a}}{\bm{x}}_{k_{a}}^{t}\right\|_{\ast,{\bm{x}}^{t}_{k_{a}}}^{2}$
$\displaystyle\hskip
28.45274pt+\sum_{\begin{subarray}{c}i\in\\{m+1,\dots,n\\}\\\ i\neq
a\end{subarray}}\left(\frac{\lambda^{t}_{i}}{w_{v}}(\alpha({\bm{x}}_{k_{i}}^{t})^{\top}\bm{C}^{t-}_{k_{i}}{\bm{x}}_{k_{i}}^{t})^{2}+\lambda^{t}_{i}\|\bm{C}^{t-}_{k_{i}}{\bm{x}}^{t}_{k_{i}}\|_{\ast,{\bm{x}}^{t}_{k_{i}}}^{2}\right)$
(39)

Now,

$(\tilde{\bm{\ell}}^{t}_{k_{a}})^{\top}{\bm{x}}^{t}_{k_{a}}=l^{t}\cdot\bm{y}_{k_{a}}^{t}\bm{C}^{t-}_{k_{a}}{\bm{x}}^{t}_{k_{a}}+(\bm{b}^{t}_{k_{a}})^{\top}{\bm{x}}^{t}_{k_{a}}=l^{t}+N_{k_{a}}-1\leq
N_{k_{a}},$

where we used Lemma 15 together with the hypothesis that $l^{t}\in[0,1]$. So,
using the hypothesis $\alpha\in[0,1]$,

$\displaystyle\frac{\lambda^{t}_{a}}{w_{v}}\left(\frac{1}{\lambda_{a}^{t}}(N_{v}-N_{\rho(v,a)})+\frac{1}{\lambda_{a}^{t}}({\bm{x}}_{k_{i}}^{t})^{\top}\left(\tilde{\bm{\ell}}^{t}_{k_{a}}+(\alpha\lambda_{a}^{t})\bm{C}^{t-}_{k_{a}}{\bm{x}}_{k_{i}}^{t}\right)\right)^{2}$
$\displaystyle\leq\frac{1}{\lambda_{a}^{t}w_{v}}(N_{v}+\alpha\lambda_{a}^{t})^{2}$
$\displaystyle\leq\frac{N_{v}^{2}}{w_{v}\lambda_{a}^{t}}+2N_{v}.$

Substituting that bound into (39), and bounding the remaining terms as in the
previous case (that is, terminal sampled action $a$), we have

$\displaystyle\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}$
$\displaystyle\leq
4N_{v}+\frac{N_{v}^{2}}{w_{v}\lambda_{a}^{t}}+\frac{1}{\lambda_{a}^{t}}\left\|\tilde{\bm{\ell}}^{t}_{k_{a}}+(\alpha\lambda_{a}^{t})\bm{C}^{t-}_{k_{a}}{\bm{x}}_{k_{a}}^{t}\right\|_{\ast,{\bm{x}}^{t}_{k_{a}}}^{2}$

We now take expectations:

$\displaystyle\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}\right]$
$\displaystyle\leq\sum_{a=1}^{m}\lambda_{a}^{t}\left(4N_{v}+\frac{N_{v}^{2}}{w_{v}\lambda_{a}^{t}}\right)$
$\displaystyle\hskip
28.45274pt+\sum_{a=m+1}^{n}\lambda_{a}^{t}\left(4N_{v}+\frac{N_{v}^{2}}{w_{v}\lambda_{a}^{t}}+\frac{1}{\lambda_{a}^{t}}\mathbb{E}_{t}\left[\left\|\tilde{\bm{\ell}}^{t}_{k_{a}}+(\alpha\lambda_{a}^{t})\bm{C}^{t-}_{k_{a}}{\bm{x}}_{k_{a}}^{t}\right\|_{\ast,{\bm{x}}^{t}_{k_{a}}}^{2}\right]\right)$
$\displaystyle\leq
4N_{v}+\frac{N_{v}^{3}}{w_{v}}+\sum_{i=m+1}^{n}\mathbb{E}_{t}\left[\left\|\tilde{\bm{\ell}}^{t}_{k_{a}}+(\alpha\lambda_{a}^{t})\bm{C}^{t-}_{k_{a}}{\bm{x}}_{k_{a}}^{t}\right\|_{\ast,{\bm{x}}^{t}_{k_{a}}}^{2}\right]$
$\displaystyle\leq
4N_{v}+|\Sigma|^{2}\frac{N_{v}}{w_{v}}+\sum_{i=m+1}^{n}\mathbb{E}_{t}\left[\left\|\tilde{\bm{\ell}}^{t}_{k_{a}}+(\alpha\lambda_{a}^{t})\bm{C}^{t-}_{k_{a}}{\bm{x}}_{k_{a}}^{t}\right\|_{\ast,{\bm{x}}^{t}_{k_{a}}}^{2}\right].$

Since $\alpha\lambda_{a}^{t}\in[0,1]$, we can use the inductive hypothesis and
write

$\displaystyle\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}\right]$
$\displaystyle\leq
4N_{v}+|\Sigma|^{2}\frac{N_{v}}{w_{v}}+\sum_{i=m+1}^{n}\left(2-\frac{1}{w_{k_{i}}}\right)|\Sigma|^{2}\frac{N_{k_{i}}}{w_{k_{i}}}+2N_{k_{i}}^{2}$
$\displaystyle\leq
2\left(N_{k_{i}}^{2}+2\sum_{i=m+1}^{n}N_{k_{i}}\right)+\frac{|\Sigma|^{2}}{w_{v}}+|\Sigma|^{2}\left(\sum_{i=m+1}^{n}\left(2-\frac{1}{w_{k_{i}}}+\frac{1}{w_{v}}\right)N_{k_{i}}\right),$

where the second inequality follows from using
$N_{v}=1+\sum_{i=m+1}^{n}N_{k_{i}}$. Using the fact that $1/w_{i}\geq
2/w_{v}$, we further obtain

$\displaystyle\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}\right]$
$\displaystyle\leq
2\left(N_{k_{i}}^{2}+2\sum_{i=m+1}^{n}N_{k_{i}}\right)+|\Sigma|^{2}\left(\sum_{i=m+1}^{n}\left(2-\frac{1}{w_{v}}\right)N_{k_{i}}\right)$
$\displaystyle=2\left(N_{k_{i}}^{2}+2\sum_{i=1}^{n}N_{k_{i}}\right)+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)(N_{v}-1)+\frac{|\Sigma|^{2}}{w_{v}}.$

Since $\frac{1}{w_{v}}\leq 1\leq 2-\frac{1}{w_{v}}$, we can further bound the
right hand side as

$\displaystyle\mathbb{E}_{t}\left[\|\tilde{\bm{\ell}}+\alpha\bm{C}^{t-}_{v,\ast}{\bm{x}}^{t}_{v}\|_{\ast,{\bm{x}}^{t}_{v}}^{2}\right]$
$\displaystyle\leq
2\left(N_{k_{i}}^{2}+2\sum_{i=m+1}^{n}N_{k_{i}}\right)+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)N_{v}$
$\displaystyle\leq
2\left(\sum_{i=m+1}N_{k_{i}}\right)^{2}+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)N_{v}$
$\displaystyle\leq 2N_{v}^{2}+|\Sigma|^{2}\left(2-\frac{1}{w_{v}}\right)N_{v}$

thus completing the inductive step.

Finally, noting that $N_{v}\leq|\Sigma|$ at all $v$ yields the statement. ∎

##  Appendix F Game Instances Used in our Experimental Evaluation

_Matrix game_ is a small matrix game, where the payoff matrix for Player 1 is

$\begin{pmatrix}-1&1\\\ 1&-0.5\\\ 0.9&-1\end{pmatrix}.$

The first and third action of Player 1 have almost opposite payoffs, which
empirically complicates the loss estimate and convergence to the best response
with bandit feedback.

_Kuhn poker_ is a standard benchmark game in the equilibrium-solving community
(Kuhn 1950). In Kuhn poker, the two players put an ante worth $1$ into the pot
at the beginning of the game. Then, each player is privately dealt one card
from a deck that contains only three cards—specifically, jack, queen, and
king. A single round of betting then occurs, with the following rule: first,
Player $1$ decides to either check or bet $1$; then,

  * •

If Player 1 checks, Player 2 may check or raise $1$.

    * –

If Player 2 checks, a showdown occurs; otherwise (that is, Player 2 raises),
Player 1 can fold or call.

      * *

If Player 1 folds the game ends and Player 2 takes the pot; if Player 1 calls
a showdown occurs.

  * •

If Player 1 raises Player 2 may fold or call.

    * –

If Player 2 folds the game ends and Player 1 takes the pot; if Player 2 calls,
a showdown occurs.

If a showdown occurs, the player with the higher card wins the pot and the
game ends.

_Leduc poker_ is another common benchmark game in the equilibrium-finding
community (Southey et al. 2005). It is played with a deck of $3$ unique ranks,
each of which appears exactly twice in the deck. There are two rounds in the
game. In the first round, all players put an ante of $1$ in the pot and are
privately dealt a single card. A round of betting then starts. Player 1 acts
first, and at most two bets are allowed per player. Then, a card is publicly
revealed, and another round of betting takes place, with the same dynamics
described above. After the two betting round, if one of the players has a pair
with the public card, that player wins the pot. Otherwise, the player with the
higher card wins the pot. All bets in the first round are worth $2$, while all
bets in the second round are $4$.

_Goofspiel_ is another popular parametric benchmark game, originally proposed
by Ross (1971). It is a two-player card game, played with three identical
decks of $k$ cards each, whose values range from $1$ to $k$. In our
experiment, we used $k=4$. At the beginning of the game, each player gets
dealt a full deck as their hand, and the third deck (the “prize” deck) is
shuffled and put face down on the board. In each turn, the topmost card from
the prize deck is revealed. Then, each player privately picks a card from
their hand. This card acts as a bid to win the card that was just revealed
from the prize deck. The selected cards are simultaneously revealed, and the
highest one wins the prize card. If the players’ played cards are equal, the
prize card is split. The players’ score are computed as the sum of the values
of the prize cards they have won.

##  Appendix G Hyperparameter Selection for Experimental Evaluation

The AHR algorithm as well as our proposed bandit regret minimizer require us
to choose one step-size parameter. While we could have simply used the
theoretically correct step-size which ensures $\tilde{O}(\sqrt{T})$ expected
regret we experimented by multiplying the step size with a constant $\alpha$.
Multiplying the theoretically correct step-size with a constant does not
effect the asymptotic regret bound. We considered
$\alpha\in\\{0.5,1,2,5,10\\}$. For each choice of $\alpha$ we ran both
algorithm 10 times on each of the two larger games (Goofspiel and Leduc
poker). Figures 3 and 4 show the performance of the algorithm by Abernethy,
Hazan, and Rakhlin (2008) (AHR) and our algorithm for every choice of
$\alpha$.

Figure 3: Average regret over 10 runs of the AHR algorithm using different
step-size multipliers $\alpha$.

Figure 4: Average regret over 10 runs of our algorithm using different step-
size multipliers $\alpha$.

In AHR, for all choices of $\alpha$ we achieve very similar performances. For
our method, the best choices of $\alpha$ seem to be $2$ and $5$.