$\displaystyle\bm{l}^{\prime}_{J_{3}}\leq\mathcal{A}_{J_{3}}{\bm{x}}\leq\bm{u}^{\prime}_{J_{3}}$

Our remaining analysis can be classified into two steps. For the first step,
we show that any variable $\bm{x}$ that satisfies the linear system (7) turns
out to be an optimal solution of $\bar{V}^{K}_{\bm{c}}(\bm{d})$ (7). For the
second step, we show that for $\hat{\bm{x}}^{K}$ that satisfies the linear
system (7), we can find a variable $\bar{\bm{x}}^{K}$ satisfying the linear
system (7) such that (71) holds.

We now prove the first step. Since $\hat{\bm{x}}^{K}$ is an optimal solution
of $\hat{V}^{K}_{t,\bm{c}}$ (7), from the KKT optimality condition, we know
that there exists dual variables $\bm{\mu}_{J_{1}}\geq 0$, $\bm{v}_{J_{2}}\leq
0$ such that

$\mathcal{A}_{J_{1}}^{\top}\bm{\mu}_{J_{1}}+\mathcal{A}_{J_{2}}^{\top}\bm{v}_{J_{2}}=\bm{h}.$

Then, for any $\bm{x}$ that satisfies the linear system (7), we have

$\displaystyle\bm{h}^{\top}\bm{x}$
$\displaystyle=\bm{\mu}^{\top}_{J_{1}}\mathcal{A}_{J_{1}}\bm{x}+\bm{v}^{\top}_{J_{2}}\mathcal{A}_{J_{2}}\bm{x}=\bm{\mu}^{\top}_{J_{1,1}}\mathcal{A}_{J_{1,1}}\bm{x}+\bm{\mu}^{\top}_{J_{1,2}}\mathcal{A}_{J_{1,2}}\bm{x}+\bm{v}^{\top}_{J_{2,1}}\mathcal{A}_{J_{2,1}}\bm{x}+\bm{v}^{\top}_{J_{2,2}}\mathcal{A}_{J_{2,2}}\bm{x}$
$\displaystyle\geq\bm{\mu}^{\top}_{J_{1,1}}\mathcal{A}_{J_{1,1}}\bar{\bm{x}}^{K^{\prime}}+\bm{\mu}^{\top}_{J_{1,2}}\mathcal{A}_{J_{1,2}}\bar{\bm{x}}^{K^{\prime}}+\bm{v}^{\top}_{J_{2,1}}\mathcal{A}_{J_{2,1}}\bar{\bm{x}}^{K^{\prime}}+\bm{v}^{\top}_{J_{2,2}}\mathcal{A}_{J_{2,2}}\bar{\bm{x}}^{K^{\prime}}=\bm{\mu}^{\top}_{J_{1}}\mathcal{A}_{J_{1}}\bar{\bm{x}}^{K^{\prime}}+\bm{v}^{\top}_{J_{2}}\mathcal{A}_{J_{2}}\bar{\bm{x}}^{K^{\prime}}$
$\displaystyle=\bm{h}^{\top}\bar{\bm{x}}^{K^{\prime}}=\bar{V}^{K}_{t,\bm{c}}(\bm{d})$

where the first inequality follows from both $\bm{x}$,
$\bar{\bm{x}}^{K^{\prime}}$ satisfies the linear system (7) and thus
$\mathcal{A}_{J_{1,1}}\bm{x}=\mathcal{A}_{J_{1,1}}\bar{\bm{x}}^{K^{\prime}}=\bm{u}^{\prime\prime}_{J_{1,1}}$,
$\mathcal{A}_{J_{2,1}}\bm{x}=\mathcal{A}_{J_{2,1}}\bar{\bm{x}}^{K^{\prime}}=\bm{l}^{\prime\prime}_{J_{2,1}}$,
$\mathcal{A}_{J_{1,2}}\bar{\bm{x}}^{K^{\prime}}\leq\mathcal{A}_{J_{1,2}}{\bm{x}}$
and
$\mathcal{A}_{J_{2,2}}\bar{\bm{x}}^{K^{\prime}}\geq\mathcal{A}_{J_{2,2}}{\bm{x}}$.

It only remains to show the second step. We prove by exploiting the special
structure of the linear systems (7) and (7). Note that under our setting, we
have

$\mathcal{A}=\begin{bmatrix}&A&\dots&A\\\ &&I_{nK}&\end{bmatrix}$

where $I_{nK}$ denotes an identity matrix with size $nK\times nK$ and
$A=(a_{i,j})_{i\in[m],j\in[n]}\in\mathbb{R}^{m\times n}$. Also, the linear
system (7) can be rewritten as

$\bm{l}^{1}\leq\mathcal{A}\bm{x}\leq\bm{u}^{1}$ (79)

and the linear system (7) can be rewritten as

$\bm{l}^{2}\leq\mathcal{A}\bm{x}\leq\bm{u}^{2}.$ (80)

Then, for the solution $\hat{\bm{x}}^{K}$ of the linear system (80), we
construct $\hat{\bm{y}}\in\mathbb{R}^{n}$ with

$\hat{y}_{j}=\sum_{k=1}^{K}\hat{x}^{K}_{k,j},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall j\in[n].$

It is clear that $\hat{\bm{y}}$ is a solution to the following linear system

$\hat{\bm{l}}^{2}\leq\begin{bmatrix}&A\\\
&I_{n}\end{bmatrix}\bm{y}\leq\hat{\bm{u}}^{2}$ (81)

where $\hat{\bm{l}}^{2}\in\mathbb{R}^{n+m}$ satisfying

$\hat{l}^{2}_{i}=l^{2}_{i},\leavevmode\nobreak\ \forall
i\in[m]\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\hat{l}^{2}_{n+j}=\sum_{k=1}^{K}l^{2}_{j+kn},\leavevmode\nobreak\ \forall
j\in[n]$

and $\hat{\bm{u}}^{2}\in\mathbb{R}^{n+m}$ satisfying

$\hat{u}^{2}_{i}=u^{2}_{i},\leavevmode\nobreak\ \forall
i\in[m]\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\hat{u}^{2}_{n+j}=\sum_{k=1}^{K}u^{2}_{j+kn},\leavevmode\nobreak\ \forall
j\in[n].$

In the same way, we denote by $\hat{\bm{l}}^{1}\in\mathbb{R}^{n+m}$ satisfying

$\hat{l}^{1}_{i}=l^{1}_{i},\leavevmode\nobreak\ \forall
i\in[m]\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\hat{l}^{1}_{n+j}=\sum_{k=1}^{K}l^{1}_{j+kn},\leavevmode\nobreak\ \forall
j\in[n]$

and $\hat{\bm{u}}^{1}\in\mathbb{R}^{n+m}$ satisfying

$\hat{u}^{1}_{i}=u^{1}_{i},\leavevmode\nobreak\ \forall
i\in[m]\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\hat{u}^{1}_{n+j}=\sum_{k=1}^{K}u^{1}_{j+kn},\leavevmode\nobreak\ \forall
j\in[n].$

We consider the linear system

$\hat{\bm{l}}^{1}\leq\begin{bmatrix}&A\\\
&I_{n}\end{bmatrix}\bm{y}\leq\hat{\bm{u}}^{1}$ (82)

From Lemma 6.1, we know that for the solution $\hat{\bm{y}}$ that satisfies
linear system (81), there exists a solution $\bar{\bm{y}}$ that satisfies
linear system (82) and there also exists a constant $\mu$ such that

$\|\hat{\bm{y}}-\bar{\bm{y}}\|_{\infty}\leq\mu\cdot\|(\hat{\bm{l}}^{1},\hat{\bm{u}}^{1})-(\hat{\bm{l}}^{2},\hat{\bm{u}}^{2})\|_{\infty}\leq\mu\cdot\max_{j^{\prime}\in[n]}\\{(p_{j^{\prime}}\cdot
s-d_{j^{\prime}})\\}.$ (83)

Note that here the constant $\mu$ depends solely on $A$ and $I_{n}$ and is
independent of the granularity $K$. We now construct a solution to the linear
system (79) from $\bar{\bm{y}}$ to complete our proof. For each $j\in[n]$ and
each $k\in[K]$, we define

$\bar{x}^{K}_{k,j}=l^{1}_{j+kn}+(\bar{y}_{j}-\hat{l}^{1}_{n+j})\cdot\frac{u^{1}_{j+kn}-l^{1}_{j+kn}}{\hat{u}^{1}_{n+j}-\hat{l}^{1}_{n+j}}.$

It is clear to see that $\bar{\bm{x}}^{K}$ satisfies linear system (79) and
satisfies

$\sum_{k=1}^{K}\bar{x}^{K}_{k,j}=\bar{y}_{j},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall j\in[n].$ (84)

Our proof of the second step is completed from (83), (74) and the fact that
$\bar{\bm{x}}^{K}$ satisfies linear system (79). From the conclusion of the
first step, we know that $\bar{\bm{x}}^{K}$ is an optimal solution to
$\bar{V}^{K}_{\bm{c}}(\bm{d})$ and our proof of 2 is thus completed. $\Halmos$

#### Proof of 3.

For any integer $w$, it is clear to see that $\bar{\bm{q}}^{K_{w}}$ is a
feasible solution to $\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})$ (3.2), which
implies that the limiting point $\bar{\bm{q}}^{\prime}$ is a feasible solution
to $\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})$ (3.2) since the feasible set is
closed. We now prove optimality.

It is direct to see from the construction of the piece-wise linear function
$\hat{G}^{K}_{j}(\cdot)$ that

$\bar{V}^{K_{w}}_{\bm{c}}(\bm{d})=\sum_{j=1}^{n}\sum_{k=1}^{K_{w}}\beta^{K_{w}}_{j,k}\cdot\bar{x}^{K_{w}}_{k,j}\leq\sum_{j=1}^{n}d_{j}\cdot\int^{1}_{q=1-\bar{q}^{K_{w}}_{j}}F^{-1}_{j}(q)dq\leq\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d}).$

where the first inequality follows from the definition
$\bar{q}^{K_{w}}_{j}=\frac{\sum_{k=1}^{K_{w}}\bar{x}^{K_{w}}_{k,j}}{p_{j}\cdot
s}$.

We now show that
$\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})\leq\bar{V}^{K_{w}}_{\bm{c}}(\bm{d})+\frac{(\sum_{j=1}^{n}d_{j})\cdot\max_{j\in[n]}\\{u_{j}\\}}{K_{w}}$.
For an optimal solution $\\{\bar{q}^{*}_{j}\\}_{j=1}^{n}$ of
$\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})$. We construct for any $k\in[K_{w}]$
and $j\in[n]$

$x^{K_{w}}_{k,j}=\left\\{\begin{aligned} &p_{j}\cdot
s\cdot(q^{K_{w}}_{k+1}-q^{K_{w}}_{k}),&&\text{if\leavevmode\nobreak\
}q^{K_{w}}_{k}\geq 1-\bar{q}^{*}_{j}\\\
&\left(q^{K_{w}}_{k+1}-(1-\bar{q}^{*}_{j})\right)\cdot p_{j}\cdot
s,&&\text{if\leavevmode\nobreak\ }q^{K_{w}}_{k}<1-\bar{q}^{*}_{j}\leq
q^{K_{w}}_{k+1}\\\ &0,&&\text{if\leavevmode\nobreak\
}q^{K_{w}}_{k+1}<1-\bar{q}^{*}_{j}.\end{aligned}\right.$

It is clear to see that $\\{x^{K_{w}}_{k,j}\\}$ is a feasible solution to
$\bar{V}^{K_{w}}_{\bm{c}}(\bm{d})$ (7) and it holds that

$\displaystyle\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})$
$\displaystyle=\sum_{j=1}^{n}d_{j}\cdot
G_{j}(\bar{q}^{*}_{j})\leq\sum_{j=1}^{n}d_{j}\cdot\hat{G}^{K_{w}}_{j}(\bar{q}^{*}_{j})+\frac{(\sum_{j=1}^{n}d_{j})\cdot\max_{j\in[n]}\\{u_{j}\\}}{K_{w}-n}$
$\displaystyle=\sum_{j=1}^{n}\sum_{k=1}^{K_{w}}d_{j}\cdot\beta^{K_{w}}_{j,k}\cdot
x^{K_{w}}_{k,j}+\frac{(\sum_{j=1}^{n}d_{j})\cdot\max_{j\in[n]}\\{u_{j}\\}}{K_{w}-n}$
$\displaystyle\leq\bar{V}^{K_{w}}_{\bm{c}}(\bm{d})+\frac{(\sum_{j=1}^{n}d_{j})\cdot\max_{j\in[n]}\\{u_{j}\\}}{K_{w}-n}$

where the first inequality follows from (67). Therefore, we conclude that

$\bar{V}^{K_{w}}_{\bm{c}}(\bm{d})\leq\sum_{j=1}^{n}p_{j}\cdot
s\cdot\int^{1}_{q=1-\bar{q}^{K_{w}}_{j}}F^{-1}_{j}(q)dq\leq\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})\leq\bar{V}^{K_{w}}_{\bm{c}}(\bm{d})+\frac{(\sum_{j=1}^{n}d_{j})\cdot\max_{j\in[n]}\\{u_{j}\\}}{K_{w}-n}.$

Note that

$\sum_{j=1}^{n}d_{j}\cdot\int^{1}_{q=1-\bar{q}^{\prime}_{j}}F^{-1}_{j}(q)dq=\lim_{w\rightarrow\infty}\sum_{j=1}^{n}d_{j}\cdot\int^{1}_{q=1-\bar{q}^{K_{w}}_{j}}F^{-1}_{j}(q)dq.$

We have

$\displaystyle\left|\sum_{j=1}^{n}d_{j}\cdot\int^{1}_{q=1-\bar{q}^{\prime}_{j}}F^{-1}_{j}(q)dq-\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})\right|$
$\displaystyle=\lim_{w\rightarrow\infty}\left|\sum_{j=1}^{n}d_{j}\cdot\int^{1}_{q=1-\bar{q}^{K_{w}}_{j}}F^{-1}_{j}(q)dq-\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})\right|$
$\displaystyle\leq\lim_{w\rightarrow\infty}\frac{(\sum_{j=1}^{n}d_{j})\cdot\max_{j\in[n]}\\{u_{j}\\}}{K_{w}-n}=0$

which implies that $\bar{\bm{q}}^{\prime}$ is an optimal solution to
$\bar{V}^{\mathrm{Semi}}_{\bm{c}}(\bm{d})$ (3.2). Our proof is therefore
completed. $\Halmos$

#### Proof of 1.

Denote by functions

$G_{j}(q):=\int_{q^{\prime}=q}^{1}F^{-1}_{j}(q^{\prime})dq^{\prime},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall j\in[n].$

It is clear that

$G_{j}^{\prime}(q)=-F^{-1}_{j}(q)\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}G_{j}^{\prime\prime}(q)=-\frac{1}{f(q|\bm{a}_{j})}\in[-\frac{1}{\alpha},0].$

Therefore, from the concavity of $G_{j}(\cdot)$, we have

$\int_{q=q_{1}}^{q_{2}}F^{-1}_{j}(q)dq=G_{j}(q_{1})-G_{j}(q_{2})\leq
F^{-1}_{j}(q_{1})\cdot(q_{2}-q_{1})+\frac{(q_{2}-q_{1})^{2}}{\alpha}$

which completes our proof. $\Halmos$

##  8 Missing Proofs for Section 4

#### Proof of Lemma 4.3.

By plugging (35) into (8), we have that

$\displaystyle\text{Myopic}_{t}(\pi,\tilde{\bm{c}}^{\pi}_{t})$
$\displaystyle=\mathbb{E}_{(\tilde{r}_{t},\tilde{\bm{a}}_{t})}\left[\mathbb{E}_{I_{t+1}}[\bar{V}^{\mathrm{Off}}_{\tilde{\bm{c}}^{\pi}_{t}}(I_{t})]-\bar{V}^{\mathrm{Off}}_{\tilde{\bm{c}}^{\pi}_{t}-\tilde{\bm{a}}_{t}\cdot\tilde{x}^{\pi}_{t}}(I_{t+1})]]-\tilde{r}_{t}\cdot\tilde{x}^{\pi}_{t}\right]$
(85)
$\displaystyle=\mathbb{E}_{(\tilde{r}_{t},\tilde{\bm{a}}_{t})}\left[\mathbb{E}_{I_{t+1}}[(\tilde{x}^{\text{round}}_{t}-\tilde{x}^{\pi}_{t})\cdot(\tilde{r}_{t}+\bar{V}^{\mathrm{Off}}_{\tilde{\bm{c}}_{t}^{\pi}-\tilde{\bm{a}}_{t}}(I_{t+1}))+(\tilde{x}^{\pi}_{t}-\tilde{x}^{\text{round}}_{t})\cdot\bar{V}^{\mathrm{Off}}_{\tilde{\bm{c}}_{t}^{\pi}}(I_{t+1})+G_{\tilde{\bm{c}}^{\pi}_{t}}(I_{t})]\right]$
$\displaystyle=\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{(\tilde{r}_{t},\tilde{\bm{a}}_{t})}[(\tilde{x}^{\text{round}}_{t}-\tilde{x}^{\pi}_{t})\cdot(\tilde{r}_{t}-M_{\tilde{\bm{c}}_{t}^{\pi},\tilde{\bm{a}}_{t}}(I_{t+1}))]\right]+\mathbb{E}[G_{\tilde{\bm{c}}_{t}^{\pi}}(I_{t})]$

From the definition of $\tilde{x}^{\text{round}}_{t}$ and
$\tilde{x}^{\pi}_{t}$, we know that
$\tilde{x}^{\text{round}}_{t}-\tilde{x}^{\pi}_{t}\in\\{-1,1\\}$ if and only if
$\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}\leq\tilde{r}_{t}\leq
M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})$ and
$\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}$, or
$M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})\leq\tilde{r}_{t}\leq\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}$
and $\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}$. Thus, we have that

$\displaystyle\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{(\tilde{r}_{t},\tilde{\bm{a}}_{t})}[(\tilde{x}^{\text{round}}_{t}-\tilde{x}^{\pi}_{t})\cdot(\tilde{r}_{t}-M_{\tilde{\bm{c}}_{t}^{\pi},\tilde{\bm{a}}_{t}}(I_{t+1}))]\right]$
(86) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{\tilde{r}_{t}\sim
F(\cdot|\tilde{\bm{a}}_{t})}[\mathbbm{1}_{\\{\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}\leq\tilde{r}_{t}\leq
M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})\\}}\cdot(M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})-\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}})]\right]\right]\cdot\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}$
$\displaystyle+\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{\tilde{r}_{t}\sim
F(\cdot|\tilde{\bm{a}}_{t})}[\mathbbm{1}_{\\{\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}\geq\tilde{r}_{t}\geq
M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})\\}}\cdot(\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}-M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1}))]\right]\right]\cdot\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}$
$\displaystyle\leq$
$\displaystyle\bar{\alpha}\cdot\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[(\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}-M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1}))^{2}\right]\right]\cdot\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}$
$\displaystyle\leq$ $\displaystyle
2\bar{\alpha}\cdot\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[(\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}-\mathbb{E}_{I_{t+1}}[M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})])^{2}\right]$
$\displaystyle+2\bar{\alpha}\cdot\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}\left[(\mathbb{E}_{I_{t+1}}[M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})]-M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1}))^{2}\right]\right]$

where the second inequality follows from Section 4 which implies that the
density of $\tilde{r}_{t}$ is upper bounded by $\bar{\alpha}$ and the third
inequality follows from $(a+b)^{2}\leq 2a^{2}+2b^{2}$ for any $a,b$. Plugging
(86) into (85), we complete our proof of the lemma. $\Halmos$

#### Proof of Lemma 4.5.

Note that we have

$L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})=\frac{\bm{c}^{\top}\bm{\mu}}{s-1}+\mathbb{E}_{\tilde{\bm{a}}}\left[\mathbb{E}_{\tilde{r}\sim
F_{\tilde{\bm{a}}}}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}]^{+}|\tilde{\bm{a}}\right]=\frac{\bm{c}^{\top}\bm{\mu}}{s-1}+\mathbb{E}_{\tilde{\bm{a}}}\left[\int_{\tilde{\bm{a}}^{\top}\bm{\mu}}^{\infty}(\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu})f(r|\tilde{\bm{a}})dr\right]$

which implies that

$\frac{\partial
L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})}{\partial\mu_{i}}=\frac{c_{i}}{s-1}-\mathbb{E}_{\tilde{\bm{a}}}[\tilde{a}_{i}\cdot(1-F(\tilde{\bm{a}}^{\top}\bm{\mu}|\tilde{\bm{a}}))],\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i\in[m]$

and

$\frac{\partial^{2}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})}{\partial\mu_{i}\partial\mu_{i^{\prime}}}=\mathbb{E}_{\tilde{\bm{a}}}[f(\tilde{\bm{a}}^{\top}\bm{\mu}|\tilde{\bm{a}})\cdot\tilde{a}_{i}\cdot\tilde{a}_{i^{\prime}}],\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i,i^{\prime}\in[m]$

where we use $\tilde{a}_{i}$ to denote the $i$-th element of vector
$\tilde{\bm{a}}$. Moreover, note that for any $\bm{\mu}\geq 0$, from Taylor’s
theorem, there exists a $\bm{\mu}^{\prime}$ that lies on the intersection
between $\bm{\mu}$ and $\bm{\mu}^{*}$ such that

$L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})-L^{\mathrm{Fld}}_{\bm{c}}(\mu^{*})=(\bm{\mu}-\bm{\mu}^{*})^{\top}\frac{\partial
L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{*})}{\partial\bm{\mu}}+\frac{1}{2}\cdot(\bm{\mu}-\bm{\mu}^{*})^{\top}\cdot\frac{\partial^{2}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{\prime})}{\partial\bm{\mu}^{2}}\cdot(\bm{\mu}-\bm{\mu}^{*})$

where $\frac{\partial
L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{*})}{\partial\bm{\mu}}=(\frac{\partial
L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{*})}{\partial\mu_{1}},\ldots,\frac{\partial
L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{*})}{\partial\mu_{m}})$, and
$\frac{\partial^{2}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{\prime})}{\partial\bm{\mu}^{2}}$
is the Hessian matrix that equals
$\mathbb{E}_{\tilde{\bm{a}}}[f(\tilde{\bm{a}}^{\top}\bm{\mu}^{\prime}|\tilde{\bm{a}})\cdot\tilde{\bm{a}}\cdot\tilde{\bm{a}}^{\top}]$.
Note that $\Omega$ is assumed to be a convex set in Section 4 and both
$\bm{\mu},\bm{\mu}^{*}\in\Omega$. Then, we have $\bm{\mu}^{\prime}\in\Omega$
and Section 4 implies that
$\mathbb{E}_{\tilde{\bm{a}}}[f(\tilde{\bm{a}}^{\top}\bm{\mu}^{\prime}|\tilde{\bm{a}})]\geq\underline{\alpha}$.
The smallest positive eigenvalue of
$\frac{\partial^{2}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{\prime})}{\partial\bm{\mu}^{2}}$
is therefore lower bounded by $\underline{\alpha}\cdot\underline{\beta}$.
Also, from the optimality of $\bm{\mu}^{*}$, we must have

$(\bm{\mu}-\bm{\mu}^{*})^{\top}\frac{\partial
L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{*})}{\partial\bm{\mu}}\geq 0$

for any $\bm{\mu}\geq 0$. Thus, it holds that

$\frac{\underline{\alpha}\underline{\beta}}{2}\cdot\|\mathcal{P}_{S}(\bm{\mu}-\bm{\mu}^{*})\|_{2}^{2}\leq\frac{1}{2}\cdot(\bm{\mu}-\bm{\mu}^{*})^{\top}\cdot\frac{\partial^{2}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{\prime})}{\partial\bm{\mu}^{2}}\cdot(\bm{\mu}-\bm{\mu}^{*})\leq
L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})-L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu}^{*})$

which completes our proof. $\Halmos$

#### Proof of Lemma 4.6.

From (42), we know that

$\displaystyle
M_{\bm{c},\bm{a}_{t}}(I_{t+1})-\mathbb{E}[M_{\bm{c},\bm{a}_{t}}(I_{t+1})]\leq\bm{a}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\mathbb{E}[\bm{a}^{\top}_{t}\tilde{\bm{\mu}}_{1}],$
$\displaystyle\text{if\leavevmode\nobreak\
}M_{\bm{c},\bm{a}_{t}}(I_{t+1})\geq\mathbb{E}[M_{\bm{c},\bm{a}_{t}}(I_{t+1})]$
$\displaystyle\mathbb{E}[M_{\bm{c},\bm{a}_{t}}(I_{t+1})]-M_{\bm{c},\bm{a}_{t}}(I_{t+1})\leq\mathbb{E}[\bm{a}^{\top}_{t}\tilde{\bm{\mu}}_{2}]-\bm{a}^{\top}_{t}\tilde{\bm{\mu}}_{1},$
$\displaystyle\text{if\leavevmode\nobreak\
}M_{\bm{c},\bm{a}_{t}}(I_{t+1})\leq\mathbb{E}[M_{\bm{c},\bm{a}_{t}}(I_{t+1})]$

which implies that

$\mathrm{Var}(M_{\bm{c},\bm{a}_{t}}(I_{t+1}))\leq
2\mathrm{Var}(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1})+2\mathrm{Var}(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2})+2(\mathbb{E}[\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1}]-\mathbb{E}[\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2}])^{2}$

Note that we have

$\mathrm{Var}(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1})=\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1}+\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{1}])^{2}]\leq
2\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}]+2(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{1}])^{2}$

Similarly, we have

$\mathrm{Var}(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2})=\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}+\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{2}])^{2}]\leq
2\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2})^{2}]+2(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{2}])^{2}$

Also, we have

$\displaystyle(\mathbb{E}[\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2}]-\mathbb{E}[\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1}])^{2}$
$\displaystyle=(\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{2}]-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}+\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1}+\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{1}])^{2}$
$\displaystyle\leq
3(\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{2}]-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2})^{2}+3(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}+3(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{1}])^{2}$

Thus, we have that

$\displaystyle\mathrm{Var}(M_{\bm{c},\bm{a}_{t}}(I_{t+1}))$ $\displaystyle\leq
10(\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{1}]-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}+10(\bm{a}_{t}^{\top}\mathbb{E}[\tilde{\bm{\mu}}_{2}]-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2})^{2}+6(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}$
(87) $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
+4\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}]+4\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2})^{2}]$
$\displaystyle\leq
14\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}]+14\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2})^{2}]+6(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}.$

It only remains to bound the term
$(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}$.
We have the following claim, where the proof is relegated to the end of this
proof.

###### Claim 4

It holds that

$(\bm{a}_{t}^{\top}(\hat{\bm{\mu}}_{1}-\hat{\bm{\mu}}_{2}))^{2}\leq\frac{2}{(s-1)\underline{\alpha}\underline{\beta}}\cdot\bar{d}^{3}\cdot
m^{1/2}\cdot\gamma$

where $\bar{d}=\max_{j\in[n]}\\{\|\bm{a}_{j}\|_{2}\\}$ and
$\gamma=\max_{i\in[m],j\in[n]:a_{j,i}>0}\frac{u_{j}}{a_{j,i}}$.

Therefore, our proof is completed by combining (87) and 4. $\Halmos$

#### Proof of 4.

From Lemma 4.5, by substituting $\hat{\bm{\mu}}_{1}$ into $\bm{\mu}^{*}$, and
substituting $\hat{\bm{\mu}}_{2}$ into $\bm{\mu}$, we have that

$\displaystyle\frac{\underline{\alpha}\underline{\beta}}{2}\cdot\|\mathcal{P}_{S}(\hat{\bm{\mu}}_{2}-\hat{\bm{\mu}}_{1})\|_{2}^{2}$
$\displaystyle\leq
L^{\mathrm{Fld}}_{\bm{c},t+1}(\hat{\bm{\mu}}_{2})-L^{\mathrm{Fld}}_{\bm{c},t+1}(\hat{\bm{\mu}}_{1})=L^{\mathrm{Fld}}_{\bm{c},t+1}(\hat{\bm{\mu}}_{2})-L^{\mathrm{Fld}}_{\bm{c}-\bm{a}_{t},t+1}(\hat{\bm{\mu}}_{2})+L^{\mathrm{Fld}}_{\bm{c}-\bm{a}_{t},t+1}(\hat{\bm{\mu}}_{2})-L^{\mathrm{Fld}}_{\bm{c},t+1}(\hat{\bm{\mu}}_{1})$
$\displaystyle\leq
L^{\mathrm{Fld}}_{\bm{c},t+1}(\hat{\bm{\mu}}_{2})-L^{\mathrm{Fld}}_{\bm{c}-\bm{a}_{t},t+1}(\hat{\bm{\mu}}_{2})=\frac{1}{s-1}\cdot\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2}$

where the second inequality follows from
$L^{\mathrm{Fld}}_{\bm{c}-\bm{a}_{t},t+1}(\hat{\bm{\mu}}_{2})\leq
L^{\mathrm{Fld}}_{\bm{c}-\bm{a}_{t},t+1}(\hat{\bm{\mu}}_{1})\leq
L^{\mathrm{Fld}}_{\bm{c},t+1}(\hat{\bm{\mu}}_{1})$ by noting that
$\hat{\bm{\mu}}_{2}\in\argmin_{\bm{\mu}\geq
0}L^{\mathrm{Fld}}_{\bm{c}-\bm{a}_{t},t+1}(\bm{\mu})$. Thus, we have

$(\bm{a}_{t}^{\top}(\hat{\bm{\mu}}_{2}-\hat{\bm{\mu}}_{1}))^{2}\leq\bar{d}^{2}\cdot\|\mathcal{P}_{S}(\hat{\bm{\mu}}_{2}-\hat{\bm{\mu}}_{1})\|^{2}_{2}\leq\frac{2}{(s-1)\underline{\alpha}\underline{\beta}}\cdot(\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{2})\cdot\bar{d}^{2}\leq\frac{2}{(s-1)\underline{\alpha}\underline{\beta}}\cdot\|\bm{a}_{t}\|_{2}\cdot\|\hat{\bm{\mu}}_{2}\|_{2}\cdot\bar{d}^{2}$

Clearly, we must have $\hat{\mu}_{2,i}\leq\gamma$ for each $i\in[m]$ with
$\gamma=\max_{i\in[m],j\in[n]:a_{j,i}>0}\frac{u_{j}}{a_{j,i}}$, which implies
that $\|\hat{\bm{\mu}}_{2}\|_{2}\leq\sqrt{m}\gamma$. Thus, it holds that

$(\bm{a}_{t}^{\top}(\hat{\bm{\mu}}_{1}-\hat{\bm{\mu}}_{2}))^{2}\leq\frac{2}{(s-1)\underline{\alpha}\underline{\beta}}\cdot\bar{d}^{3}\cdot
m^{1/2}\cdot\gamma$

which completes our proof. $\Halmos$

#### Proof of Lemma 4.7.

We first consider the setting where $\bm{c}\geq\tilde{\bm{a}}_{t}$ and thus
both $\tilde{\bm{\mu}}_{1}$ and $\tilde{\bm{\mu}}_{2}$ are well-defined in
(41). We show that $\tilde{x}^{*}_{t}\neq\tilde{x}^{\text{round}}_{t}$ happens
only if
$\bm{a}^{\top}_{t}\tilde{\bm{\mu}}_{1}\leq\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}$.
Note that the value of $\tilde{x}^{*}_{t}$ can be determined in the following
way:

$\tilde{x}^{*}_{t}=\argmax_{\phi\in[0,1]}\phi\cdot\tilde{r}_{t}+\bar{V}^{\mathrm{Off}}_{\bm{c}-\phi\cdot\tilde{\bm{a}}_{t}}(I_{t+1})-\bar{V}^{\mathrm{Off}}_{\bm{c}}(I_{t+1})$
(88)

Note that for any $\phi\in[0,1]$, we must have

$-\phi\cdot\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}\leq\bar{V}^{\mathrm{Off}}_{\bm{c}-\phi\cdot\tilde{\bm{a}}_{t}}(I_{t+1})-\bar{V}^{\mathrm{Off}}_{\bm{c}}(I_{t+1})\leq-\phi\cdot\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$

which can be proved following the same intuition of Lemma 4.4. Therefore, when
$\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$, we must have
$\tilde{x}^{*}_{t}=\tilde{x}^{\text{round}}_{t}=0$, and when
$\tilde{r}_{t}\geq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}$, we must have
$\tilde{x}^{*}_{t}=\tilde{x}^{\text{round}}_{t}=1$. We conclude that
$G_{\bm{c}}(I_{t})=0$ when
$\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$ or
$\tilde{r}_{t}\geq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}$. We now
assume that
$\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}\leq\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}$
and we further consider two cases as follows:

Case 1: If $\tilde{x}^{\text{round}}_{t}=0$, then we have

$G_{\bm{c}}(I_{t})=\tilde{r}_{t}\cdot\tilde{x}^{*}_{t}+\bar{V}^{\mathrm{Off}}_{\bm{c}-\tilde{\bm{a}}_{t}\cdot\tilde{x}^{*}_{t}}(I_{t+1})-\bar{V}^{\mathrm{Off}}_{\bm{c}}(I_{t+1})$

Note that we have

$\bar{V}^{\mathrm{Off}}_{\bm{c}-\tilde{\bm{a}}_{t}\cdot\tilde{x}^{*}_{t}}(I_{t+1})-\bar{V}^{\mathrm{Off}}_{\bm{c}}(I_{t+1})\leq-\tilde{x}^{*}_{t}\cdot\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$

By noting $\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}$ and
$\tilde{x}^{*}_{t}\leq 1$, we have that

$G_{\bm{c}}(I_{t})\leq\tilde{x}^{*}_{t}\cdot(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1})\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$

which gives us an upper bound for the first case.

Case 2: If $\tilde{x}^{\text{round}}_{t}=1$, then we have

$G_{\bm{c}}(I_{t})=\tilde{r}_{t}\cdot(\tilde{x}^{*}_{t}-1)+\bar{V}^{\mathrm{Off}}_{\bm{c}-\tilde{\bm{a}}_{t}\cdot\tilde{x}^{*}_{t}}(I_{t+1})-\bar{V}^{\mathrm{Off}}_{\bm{c}-\tilde{\bm{a}}_{t}}(I_{t+1}).$

Note that we have

$\bar{V}^{\mathrm{Off}}_{\bm{c}-\tilde{\bm{a}}_{t}\cdot\tilde{x}^{*}_{t}}(I_{t+1})-\bar{V}^{\mathrm{Off}}_{\bm{c}-\tilde{\bm{a}}_{t}}(I_{t+1})\leq(1-\tilde{x}^{*}_{t})\cdot\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}.$

By noting $\tilde{r}_{t}\geq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$ and
$0\leq 1-\tilde{x}^{*}_{t}\leq 1$, we have that

$G_{\bm{c}}(I_{t})\leq(1-\tilde{x}^{*}_{t})\cdot(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1})\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$

which gives us an upper bound for the second case. Therefore, on both cases,
we show that if
$\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}\leq\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}$,
it holds that

$G_{\bm{c}}(I_{t})\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}.$
(89)

which implies that

$\displaystyle\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{\tilde{r}_{t}\sim
F(\cdot|\tilde{\bm{a}}_{t})}[G_{\bm{c}}(I_{t})]\right]\right]$
$\displaystyle\leq\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{\tilde{r}_{t}\sim
F(\cdot|\tilde{\bm{a}}_{t})}[\mathbbm{1}_{\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}\leq\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}}\cdot(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1})]\right]\right]$
$\displaystyle\leq\bar{\alpha}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}\left[(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1})^{2}\right]\right].$

We further note that

$\displaystyle(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1})^{2}$
$\displaystyle=(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{2}+\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1}+\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1})^{2}$
$\displaystyle\leq
3(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{2})^{2}+3(\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1})^{2}+3(\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1}-\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1})^{2}.$

We use 4 to bound the term
$(\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1})^{2}$.
Then, we have

$\mathbb{E}_{I_{t}}\left[G_{\bm{c}}(I_{t})\right]\leq\frac{\kappa_{2}}{s-1}+\kappa_{2}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}[(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1})^{2}]\right]+\kappa_{2}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}[(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{2})^{2}]\right]$
(90)

for a constant $\kappa_{2}$.

We then consider the setting where $\bm{c}\geq\tilde{\bm{a}}_{t}$ does not
hold and only $\tilde{\bm{\mu}}_{1}$ is well-defined in (41). Still, when
$\tilde{r}_{t}\leq\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$, we must have
$\tilde{x}^{*}_{t}=\tilde{x}^{\text{round}}_{t}=0$, which implies
$G_{\bm{c}}(I)=0$. We now assume that
$\tilde{r}_{t}\geq\tilde{\bm{a}}_{t}^{\top}\tilde{\bm{\mu}}_{1}$. Then, since

$-\phi\cdot\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{2}\leq\bar{V}^{\mathrm{Off}}_{\bm{c}-\phi\cdot\tilde{\bm{a}}_{t}}(I_{t+1})-\bar{V}^{\mathrm{Off}}_{\bm{c}}(I_{t+1})\leq-\phi\cdot\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}$

for any $\phi[0,1]$, we have

$G_{\bm{c}}(I_{t})\leq\tilde{x}^{*}_{t}\cdot(\tilde{r}_{t}-\tilde{\bm{a}}_{t}^{\top}\tilde{\bm{\mu}}_{1})\leq\tilde{r}_{t}-\tilde{\bm{a}}_{t}^{\top}\tilde{\bm{\mu}}_{1}$

by noting $\tilde{x}^{*}_{t}\in[0,1]$. Denote by $j_{t}$ as the type of query
$t$. It holds that

$\mathbb{E}_{\tilde{r}_{t}\sim
F(\cdot|\tilde{\bm{a}}_{t})}[G_{\bm{c}}(I_{t})]\leq\frac{1}{2}\cdot(u_{j_{t}}-\bm{a}_{j_{t}}^{\top}\tilde{\bm{\mu}}_{1})^{2}\leq(u_{j_{t}}-\bm{a}_{j_{t}}^{\top}\hat{\bm{\mu}}_{1})^{2}+(\bm{a}_{j_{t}}^{\top}\hat{\bm{\mu}}_{1}-\bm{a}_{j_{t}}^{\top}\tilde{\bm{\mu}}_{1})^{2}\leq
u_{j_{t}}\cdot(u_{j_{t}}-\bm{a}_{j_{t}}^{\top}\hat{\bm{\mu}}_{1})+(\bm{a}_{j_{t}}^{\top}\hat{\bm{\mu}}_{1}-\bm{a}_{j_{t}}^{\top}\tilde{\bm{\mu}}_{1})^{2}.$

It is clear to see that
$\min_{\mu\in\Omega}L^{\mathrm{Fld}}_{\bm{c},t+1}(\mu)$ is the dual problem of
$\max_{\bm{x}}\bar{V}^{\mathrm{Fld}}_{t+1,\bm{c}}$. Denote by
$\bar{\bm{x}}=\\{\bar{x}_{j}(r)\\}\in\text{argmax}_{\bm{x}}\bar{V}^{\mathrm{Fld}}_{t+1,\bm{c}}$
such that $\bar{\bm{x}}$ and $\hat{\bm{\mu}}_{1}$ is an optimal primal-dual
pair. Then, when $c_{i}<a_{j_{t},i}$ for some $i\in[m]$, we must have

$\mathbb{E}_{r\sim
F(\cdot|\bm{a}_{j_{t}})}[\bar{x}_{j_{t}}(r)]\leq\frac{1}{p_{j_{t}}\cdot(s-1)}$

and as a result we have

$\alpha\cdot(u_{j_{t}}-\bm{a}_{j_{t}}^{\top}\tilde{\bm{\mu}}_{1})\leq
P(\bm{a}_{j_{t}}^{\top}\tilde{\bm{\mu}}_{1}\leq r\leq u_{j_{t}}|r\sim
F_{j_{t}})=\mathbb{E}_{r\sim
F(\cdot|\bm{a}_{j_{t}})}[\bar{x}_{j_{t}}(r)]\leq\frac{1}{p_{j_{t}}\cdot(s-1)}$

where $\alpha>0$ is a lower bound on the density function specified in Section
3. Then we have

$\mathbb{E}_{I_{t+1}}\left[\mathbb{E}_{\tilde{r}_{t}\sim
F(\cdot|\tilde{\bm{a}}_{t})}[G_{\bm{c}}(I_{t})]\right]\leq\frac{u_{j_{t}}}{\alpha\cdot
p_{j_{t}}\cdot(s-1)}+\mathbb{E}_{I_{t+1}}[(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1})^{2}].$

Therefore, we have

$\mathbb{E}_{I_{t}}[G_{\bm{c}}(I_{t})]\leq\frac{\kappa_{2}}{s-1}+\kappa_{2}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}[(\tilde{\bm{a}}^{\top}_{t}\tilde{\bm{\mu}}_{1}-\tilde{\bm{a}}^{\top}_{t}\hat{\bm{\mu}}_{1})^{2}]\right]$
(91)

for some constant $\kappa_{2}>0$. Our proof is completed by combining (90) and
(91). $\Halmos$

#### Proof of Lemma 4.8.

From (44), $\mathcal{S}$ refers to the space spanned by $\mathcal{A}$, which
is a subspace of $\mathbb{R}^{m}$. We further denote by $\mathcal{S}^{\bot}$
the orthogonal complement subspace of $S$ in the Euclidean space
$\mathbb{R}^{m}$, i.e., $\mathbb{R}^{m}=\mathcal{S}+\mathcal{S}^{\bot}$ and
$\bm{u}^{\top}\bm{v}=0$ for any $\bm{u}\in\mathcal{S}$ and any
$\bm{v}\in\mathcal{S}^{\bot}$.

Following basics in linear algebra, any vector $\bm{\mu}\in\mathbb{R}^{m}$ can
be decomposed uniquely as $\bm{\mu}=\bm{\mu}_{S}+\bm{\mu}_{S^{\bot}}$, where
$\bm{\mu}_{S}\in\mathcal{S}$ and $\bm{\mu}_{S^{\bot}}\in\mathcal{S}^{\bot}$.
Then the projection of $\bm{\mu}$ to the subspace $\mathcal{S}$ can be given
as $\mathcal{P}_{S}(\bm{\mu})=\bm{\mu}_{S}$. Following this decomposition, for
any $\bm{c}\geq 0$, we have that

$\displaystyle\min_{\bm{\mu}\geq\Omega}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})$
$\displaystyle=\min_{\bm{\mu}_{S}+\bm{\mu}_{S^{\bot}}\in\Omega}\left(\frac{\bm{c}}{T-t}\right)^{\top}\bm{\mu}_{S}+\left(\frac{\bm{c}}{T-t}\right)^{\top}\bm{\mu}_{S^{\bot}}+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}_{S}]^{+}$
$\displaystyle=\min_{\bm{\mu}_{S}\in\mathcal{S}}\left(\frac{\bm{c}}{T-t}\right)^{\top}\bm{\mu}_{S}+h(\bm{\mu}_{S})+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}_{S}]^{+}$

where we note that $\bm{a}^{\top}\bm{\mu}_{S^{\bot}}=0$ for any
$\bm{a}\in\mathcal{A}$ and

$h(\bm{\mu}_{S})=\min_{\bm{\mu}_{S^{\bot}}\in
S^{\bot}}\left(\frac{\bm{c}}{T-t}\right)^{\top}\bm{\mu}_{S^{\bot}}\text{\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ }\bm{\mu}_{S^{\bot}}+\bm{\mu}_{S}\in\Omega.$

Note that if the optimization problem that defines $h(\bm{\mu}_{S})$ is
infeasible for some $\bm{\mu}_{S}$, then we simply set
$h(\bm{\mu}_{S})=+\infty$. Denote by
$\hat{\mathcal{S}}\subset\mathcal{S}\cap\Omega$ the convex set such that
$h(\bm{\mu})$ is finite for all $\bm{\mu}\in\hat{\mathcal{S}}$. Therefore, the
dual problem $\min_{\bm{\mu}\in\Omega}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})$
can be transferred into a minimization problem over the set
$\hat{\mathcal{S}}$, i.e.,

$\min_{\bm{\mu}\in\Omega}L^{\mathrm{Fld}}_{\bm{c},t+1}(\bm{\mu})=\min_{\bm{\mu}\in\hat{\mathcal{S}}}\hat{G}_{\bm{c}}(\bm{\mu}):=\left(\frac{\bm{c}}{T-t}\right)^{\top}\bm{\mu}+h(\bm{\mu})+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}]^{+}$

Following the same way, the minimization of the sample average dual function
$L^{\mathrm{Off}}_{\bm{c},I_{t+1}}(\bm{\mu})$ in (40) can be formulated as

$\min_{\bm{\mu}\in\Omega}L^{\mathrm{Off}}_{\bm{c},I_{t+1}}(\bm{\mu})=\min_{\bm{\mu}\in\hat{\mathcal{S}}}\hat{G}_{\bm{c},I_{t+1}}(\bm{\mu}):=\left(\frac{\bm{c}}{T-t}\right)^{\top}\bm{\mu}+h(\bm{\mu})+\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}[\tilde{r}_{\tau}-\tilde{\bm{a}}^{\top}_{\tau}\bm{\mu}]^{+}.$

We denote by

$\bm{\mu}^{*}(\bm{c}^{\prime})\in\argmin_{\mu\in\hat{\mathcal{S}}}\hat{G}_{\bm{c}^{\prime}}(\bm{\mu})\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\tilde{\bm{\mu}}(\bm{c}^{\prime})\in\argmin_{\bm{\mu}\in\hat{\mathcal{S}}}\hat{G}_{\bm{c}^{\prime},I_{t+1}}(\bm{\mu})$
(92)

for any $\bm{c}^{\prime}\geq 0$, where $\tilde{\bm{\mu}}(\bm{c}^{\prime})$ is
a random variable whose value depends on $I_{t+1}$. Clearly, we have that

$\mu^{*}(\bm{c})=\mathcal{P}_{S}(\hat{\bm{\mu}}_{1}),\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\tilde{\bm{\mu}}(\bm{c})=\mathcal{P}_{S}(\tilde{\bm{\mu}}_{1}).,\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\tilde{\bm{\mu}}(\bm{c}-\bm{a}_{t})=\mathcal{P}_{S}(\tilde{\bm{\mu}}_{2})$
(93)

Thus, in order to bound
$\mathbb{E}[(\bm{a}_{t}^{\top}\tilde{\bm{\mu}}_{1}-\bm{a}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}]$,
it is sufficient to bound

$\mathbb{E}[(\bm{\mu}^{*}(\bm{c}^{\prime})-\tilde{\bm{\mu}}(\bm{c}^{\prime}))^{2}]$
(94)

for any $\bm{c}^{\prime}\geq 0$, where the $\mathbb{E}[\cdot]$ is taken over
$I_{t+1}$. In what follows, we will consider bounding (94). Since we will
assume that $\bm{c}^{\prime}$ is now fixed, for notation simplicity, we will
drop $\bm{c}^{\prime}$ in the expression of $\bm{\mu}^{*}(\bm{c}^{\prime})$,
$\tilde{\bm{\mu}}(\bm{c}^{\prime})$, $\hat{G}_{\bm{c}^{\prime}}(\bm{\mu})$ and
$\hat{G}_{\bm{c}^{\prime},I_{t+1}}(\bm{\mu})$. We simply denote
$\bm{\mu}^{*}$, $\tilde{\bm{\mu}}$, $\hat{G}(\bm{\mu})$ and
$\hat{G}_{I_{t+1}}(\bm{\mu})$.

We first note that the function $h(\bm{\mu})$ is a convex function over
$\bm{\mu}\in\hat{\mathcal{S}}$. We also note that the function $\hat{G}$ is
simply a re-formulation of the function $\hat{L}$ after projecting the
decision variable onto the subspace $\mathcal{S}$. Thus, Lemma 4.5 implies the
following second-order growth condition for the function $\hat{G}$, i.e.,

$\hat{G}(\bm{\mu})-\hat{G}(\bm{\mu}^{*})\geq\frac{\underline{\alpha}\underline{\beta}}{2}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}^{2}\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ any\leavevmode\nobreak\
}\bm{\mu}\in\hat{\mathcal{S}}\subset\mathcal{S}.$ (95)

which implies that $\bm{\mu}^{*}$ is unique. Thus, from Lemma 2.1 in Shapiro
[1992], we know that

$\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}\leq\frac{2}{\underline{\alpha}\underline{\beta}}\cdot\sup_{\bm{\mu}\in\hat{\mathcal{S}}\cap
B(\bm{\mu}^{*},r_{0})}\left\\{\frac{\hat{G}_{I_{t+1}}(\bm{\mu})-\hat{G}(\bm{\mu})-\hat{G}_{I_{t+1}}(\bm{\mu}^{*})+\hat{G}(\bm{\mu}^{*})}{\|\bm{\mu}-\bm{\mu}^{*}\|_{2}}\right\\}$

where $r_{0}=\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}$ and
$B(\bm{\mu}^{*},r_{0})=\\{\bm{\mu}:\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq
r_{0}\\}$. Therefore, in order to further bound
$\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}$, it is sufficient to bound the term

$\sup_{\bm{\mu}\in\hat{\mathcal{S}}\cap
B(\bm{\mu}^{*},r_{0})}\left\\{\frac{\frac{1}{T-t}\sum_{\tau=t+1}^{T}[\tilde{r}_{\tau}-\tilde{\bm{a}}^{\top}_{\tau}\bm{\mu}]^{+}-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}]^{+}-\frac{1}{T-t}\sum_{\tau=t+1}^{T}[\tilde{r}_{\tau}-\tilde{\bm{a}}^{\top}_{\tau}\bm{\mu}^{*}]^{+}+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}^{*}]^{+}}{\|\bm{\mu}-\bm{\mu}^{*}\|_{2}}\right\\}.$

We denote by the function

$g(\bm{\mu},(r,\bm{a})):=[r-\bm{a}^{\top}\bm{\mu}]^{+}+\bar{\alpha}\bar{d}^{2}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}^{2}.$

Moreover, we denote by

$\tilde{\delta}(\bm{\mu})=\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g(\bm{\mu},(\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}))-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g(\bm{\mu},(\tilde{r},\tilde{\bm{a}}))]$
(96)

which is a random variable that depends on $I_{t+1}$. Then, the above upper
bound over $\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}$ can be re-formulated as

$\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}\leq\frac{2}{\underline{\alpha}\underline{\beta}}\cdot\sup_{\bm{\mu}\in\hat{\mathcal{S}}\cap
B(\bm{\mu}^{*},r_{0})}\left\\{\frac{\tilde{\delta}(\bm{\mu})-\tilde{\delta}(\bm{\mu}^{*})}{\|\bm{\mu}-\bm{\mu}^{*}\|_{2}}\right\\}.$

We denote by $\tilde{E}$ the set of $\bm{\mu}$ such that
$\tilde{\delta}(\bm{\mu})$ is non-differentiable. For simplicity, we denote by
$\hat{B}(\bm{\mu}^{*},r_{0})=\hat{\mathcal{S}}\cap B(\bm{\mu}^{*},r_{0})$.
Note that $\tilde{\delta}(\bm{\mu})$ is Liptschitz continuous. Then, from the
mean value theorem for Liptschitz function (Clarke [1990] p41), we have that

$\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\leq\frac{4}{\underline{\alpha}^{2}\underline{\beta}^{2}}\cdot\sup_{\bm{\mu}\in\hat{B}(\bm{\mu}^{*},r_{0})\setminus
E}\\{\|\nabla\tilde{\delta}(\bm{\mu})\|_{2}^{2}\\}=\frac{4}{\underline{\alpha}^{2}\underline{\beta}^{2}}\cdot(\|\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}+\sup_{\bm{\mu}\in\hat{B}(\bm{\mu}^{*},r_{0})\setminus\tilde{E}}\\{\|\nabla\tilde{\delta}(\bm{\mu})-\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}\\})$
(97)

We have the following claim over the term
$\|\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}$, which is proved at the end
of this proof.

###### Claim 5

It holds that

$\mathbb{E}[\|\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}]\leq\frac{\bar{d}^{2}}{T-t}$

where the expectation $\mathbb{E}[\cdot]$ takes over
$I_{t+1}=\\{(\tilde{r}_{t+1},\tilde{\bm{a}}_{t+1}),\dots,(\tilde{r}_{T},\tilde{\bm{a}}_{T})\\}$
that defines $\tilde{\delta}(\cdot)$ in (96).

Regarding the term
$\sup_{\bm{\mu}\in\hat{B}(\bm{\mu}^{*},r_{0})\setminus\tilde{E}}\\{\|\nabla\tilde{\delta}(\bm{\mu})-\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}\\}$,
following the steps in Shapiro [1993], we can show that

$\sup_{\bm{\mu}\in
B(\mu^{*},r_{0})\setminus\tilde{E}}\\{\frac{\|\nabla\tilde{\delta}(\bm{\mu})-\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}}{\frac{1}{\sqrt{T-t}}+r_{0}}\\}\rightarrow
0\text{\leavevmode\nobreak\ in\leavevmode\nobreak\
probability\leavevmode\nobreak\ as\leavevmode\nobreak\ }T-t\rightarrow\infty.$

As a result, there exists a constant $t_{0}$ such that as long as $T-t\geq
t_{0}$, we have that

$\sup_{\bm{\mu}\in\hat{B}(\bm{\mu}^{*},r_{0})\setminus\tilde{E}}\\{\|\nabla\tilde{\delta}(\bm{\mu})-\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}\\}\leq\frac{1}{2}\cdot(\frac{1}{T-t}+r_{0}^{2})$

with a high probability. We formalize the above step in the following claim
for completeness, by making explicit the constant term $t_{0}$, as well as the
“high probability”.

###### Claim 6

It holds that

$P\left(\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq
r_{0}}\frac{\|\nabla\tilde{\delta}(\bm{\mu})-\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}}{\frac{1}{\sqrt{T-t}}+3\bar{\alpha}\bar{d}^{2}\cdot
r_{0}}\geq\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}\right)\leq\delta(\bar{\alpha},\bar{d},m,\gamma)\cdot\frac{\log(T-t)}{(T-t)^{\frac{12}{25}}}$
(98)

as long as $T-t\geq t_{1}(\bar{\alpha},\bar{d})$, where
$\delta_{1}(\bar{\alpha},\bar{d},m,\gamma)$ is a constant that depends solely
on the parameters $\bar{\alpha},\bar{d},m,\gamma$ and
$t_{1}(\bar{\alpha},\bar{d})$ is a constant that depends solely on the
parameters $\bar{\alpha},\bar{d}$.

The proof of 6 is relegated to the end of this proof. Denote by

$\tilde{z}=\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq
r_{0}}\frac{\|\nabla\tilde{\delta}(\bm{\mu})-\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}}{\frac{1}{\sqrt{T-t}}+3\bar{\alpha}\bar{d}^{2}\cdot
r_{0}}.$

We also denote by three events

$\mathcal{E}_{1}=\\{\tilde{z}\leq\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}\\}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\mathcal{E}_{2}=\\{\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}<\tilde{z}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}r_{0}\leq\frac{1}{(T-t)^{\frac{7}{25}}}\\}\leavevmode\nobreak\
\text{\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\
}\mathcal{E}_{3}=\\{\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}<\tilde{z}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }r_{0}>\frac{1}{(T-t)^{\frac{7}{25}}}\\}$

Clearly, we have

$\mathbb{E}[r_{0}^{2}]=P(\mathcal{E}_{1})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{1}]+P(\mathcal{E}_{2})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{2}]+P(\mathcal{E}_{2})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{2}]$
(99)

Now, from (97), 5, and the definition of the event $\mathcal{E}_{1}$, we have

$\displaystyle P(\mathcal{E}_{1})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{1}]$
$\displaystyle\leq\frac{4}{\underline{\alpha}^{2}\underline{\beta}^{2}}\cdot
P(\mathcal{E}_{1})\cdot\mathbb{E}[\|\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}|\mathcal{E}_{1}]+P(\mathcal{E}_{1})\cdot\frac{1}{36\bar{\alpha}^{2}\bar{d}^{4}}\cdot\mathbb{E}\left[\left(\frac{1}{\sqrt{T-t}}+3\bar{\alpha}\bar{d}^{2}\cdot
r_{0}\right)^{2}\mid\mathcal{E}_{1}\right]$ (100)
$\displaystyle\leq\frac{4}{\underline{\alpha}^{2}\underline{\beta}^{2}}\cdot\mathbb{E}[\|\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}]+\frac{1}{2}\cdot
P(\mathcal{E}_{1})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{1}]+\frac{1}{18\bar{\alpha}^{2}\bar{d}^{4}\cdot(T-t)}$

which implies that

$P(\mathcal{E}_{1})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{1}]\leq\frac{8\bar{d}^{2}}{\underline{\alpha}^{2}\underline{\beta}^{2}\cdot(T-t)}+\frac{1}{9\bar{\alpha}\bar{d}^{2}\cdot(T-t)}$
(101)

For the term $P(\mathcal{E}_{2})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{2}]$,
from the definition of the event $\mathcal{E}_{2}$ and 6, we have

$P(\mathcal{E}_{2})\cdot\mathbb{E}[r_{0}^{2}|\mathcal{E}_{2}]\leq
P(\mathcal{E}_{2})\cdot\frac{1}{(T-t)^{\frac{14}{25}}}\leq\delta(\bar{\alpha},\bar{d},m,\gamma)\cdot\frac{\log(T-t)}{(T-t)^{\frac{12}{25}}}\cdot\frac{1}{(T-t)^{\frac{14}{25}}}\leq\frac{1}{T-t}$
(102)

as long as $T-t>t_{2}(\bar{\alpha},\bar{d},m,\gamma)$, where
$t_{2}(\bar{\alpha},\bar{d},m,\gamma)$ is a constant that depends solely on
parameters $\bar{\alpha},\bar{d},m,\gamma$.

We now want to bound the probability that event $\mathcal{E}_{3}$ happens.
Note that we have

$\frac{\underline{\alpha}\underline{\beta}}{2}\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\leq\frac{1}{T-t}\sum_{\tau=t+1}^{T}[\tilde{r}_{\tau}-\tilde{\bm{a}}^{\top}_{\tau}\tilde{\bm{\mu}}]^{+}-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\tilde{\bm{\mu}}]^{+}-\frac{1}{T-t}\sum_{\tau=t+1}^{T}[\tilde{r}_{\tau}-\tilde{\bm{a}}^{\top}_{\tau}\bm{\mu}^{*}]^{+}+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}^{*}]^{+}.$
(103)

By modifying the approach in Li and Ye [2021], we have the following lemma,
which follows Proposition 2 and Proposition 3 of Li and Ye [2021] and is
proved at the end of this proof.

###### Lemma 8.1

It holds that

$P\left(\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|^{2}_{2}\geq\epsilon^{2}\right)\leq
K\cdot\log(\frac{1}{\epsilon})\exp(-\epsilon^{2}(T-t)).$

for a constant $K$ that only depends on parameters
$\underline{\alpha},\underline{\beta},\bar{\alpha},\bar{d}$

By setting $\epsilon=\frac{1}{(T-t)^{\frac{7}{25}}}$ in Lemma 8.1, we have
that

$P(\mathcal{E}_{3})\leq
P\left(\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|^{2}_{2}\geq\left(\frac{1}{(T-t)^{\frac{7}{25}}}\right)^{2}\right)\leq
K^{\prime}\cdot\log(T-t)\cdot\exp(-(T-t)^{\frac{11}{25}})\leq\frac{K^{\prime\prime}}{T-t}$
(104)

as long as $T-t>t_{3}$, where $K^{\prime},K^{\prime\prime},t_{3}$ are
constants. Therefore, combining (99), (101), (102), and (104), we have

$\mathbb{E}[\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}]=\mathbb{E}[r_{0}^{2}]\leq\frac{\delta_{2}}{T-t}$

as long as $T-t>t_{4}$, where $\delta_{2}$ and $t_{4}$ are constants.
Therefore, our proof is completed. $\Halmos$

#### Proof of 5.

Note that

$\nabla\tilde{\delta}(\bm{\mu}^{*})=-\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\tilde{\bm{a}}_{\tau}\cdot\mathbbm{1}_{\\{\tilde{r}_{\tau}\geq\tilde{\bm{a}}_{\tau}^{\top}\bm{\mu}^{*}\\}}+\mathbb{E}_{\tilde{\bm{a}}}[\tilde{\bm{a}}\cdot(1-F(\tilde{\bm{a}}^{\top}\bm{\mu}^{*}|\tilde{\bm{a}}))]$

Clearly, for each $\tau=t+1,\ldots,T$, we have

$\mathbb{E}_{(\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau})}[\tilde{\bm{a}}_{\tau}\cdot\mathbbm{1}_{\\{\tilde{r}_{\tau}\geq\tilde{\bm{a}}_{\tau}^{\top}\bm{\mu}^{*}\\}}]=\mathbb{E}_{\tilde{\bm{a}}}[\tilde{\bm{a}}\cdot(1-F(\tilde{\bm{a}}^{\top}\bm{\mu}^{*}|\tilde{\bm{a}}))].$

Thus, we have

$\mathbb{E}[\|\nabla\tilde{\delta}(\bm{\mu}^{*})\|_{2}^{2}]=\frac{1}{T-t}\cdot\mathrm{Var}(\tilde{\bm{a}}_{\tau}\cdot\mathbbm{1}_{\\{\tilde{r}_{\tau}\geq\tilde{\bm{a}}_{\tau}^{\top}\bm{\mu}^{*}\\}})\leq\frac{\bar{d}^{2}}{T-t}$

which completes our proof. $\Halmos$

#### Proof of 6.

We denote by

$\psi((r,\bm{a}),\bm{\mu})=\nabla g(\bm{\mu},(r,\bm{a}))-\nabla
g(\bm{\mu}^{*},(r,\bm{a}))$

We also denote by

$\lambda(\bm{\mu})=\mathbb{E}_{(r,\bm{a})}[\psi((r,\bm{a}),\bm{\mu})]$

and

$u((r,\bm{a}),\bm{\mu},d)=\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq
d}\|\psi((r,\bm{a}),\bm{\mu})-\psi((r,\bm{a}),\bm{\mu}^{*})\|_{2}$

Clearly, we have that

$\lambda(\bm{\mu}^{*})=0$ (105)

Thus, condition (N-2) in Huber [1967] is satisfied. Also, for any $\bm{\mu}$,
from definition of the functions $\psi$ and $\lambda$, we have that

$\|\lambda(\bm{\mu})\|_{2}=\|2\bar{\alpha}\bar{d}^{2}(\bm{\mu}-\bm{\mu}^{*})+\mathbb{E}_{\tilde{\bm{a}}}[\tilde{\bm{a}}\cdot(F(\tilde{\bm{a}}^{\top}\bm{\mu}|\tilde{\bm{a}})-F(\tilde{\bm{a}}^{\top}\bm{\mu}^{*}|\tilde{\bm{a}}))]\|_{2}$

Note that

$F(\tilde{\bm{a}}^{\top}\bm{\mu}|\tilde{\bm{a}})-F(\tilde{\bm{a}}^{\top}\bm{\mu}^{*}|\tilde{\bm{a}})\leq\bar{\alpha}\cdot|\tilde{\bm{a}}^{\top}\bm{\mu}-\tilde{\bm{a}}^{\top}\bm{\mu}^{*}|\leq\bar{\alpha}\bar{d}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}$

Thus, we have

$\displaystyle\|\lambda(\bm{\mu})\|_{2}$ $\displaystyle\geq
2\bar{\alpha}\bar{d}^{2}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}-\|\mathbb{E}_{\tilde{\bm{a}}}[\tilde{\bm{a}}\cdot(F(\tilde{\bm{a}}^{\top}\bm{\mu}|\tilde{\bm{a}})-F(\tilde{\bm{a}}^{\top}\bm{\mu}|\tilde{\bm{a}}))]\|_{2}$
(106) $\displaystyle\geq
2\bar{\alpha}\bar{d}^{2}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}-\bar{\alpha}\bar{d}^{2}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}=\bar{\alpha}\bar{d}^{2}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}$

for any $d_{0}\geq 0$ and $\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq d_{0}$. Thus, we
verify that condition (N-3) (i) in Huber [1967] holds. Moreover, we have

$\|\psi((r,\bm{a}),\bm{\mu})-\psi((r,\bm{a}),\bm{\mu}^{*})\|_{2}=\|\bm{a}\cdot\mathbbm{1}_{\\{r\geq\bm{a}^{\top}\bm{\mu}^{*}\\}}-\bm{a}\cdot\mathbbm{1}_{\\{r\geq\bm{a}^{\top}\bm{\mu}\\}}\|\leq\|\bm{a}\cdot(\mathbbm{1}_{\\{\bm{a}^{\top}\bm{\mu}\leq
r\leq\bm{a}^{\top}\bm{\mu}^{*}\\}}+\mathbbm{1}_{\\{\bm{a}^{\top}\bm{\mu}^{*}\leq
r\leq\bm{a}^{\top}\bm{\mu}\\}})\|\leq\bar{d}$ (107)

which implies that

$\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[u((\tilde{r},\tilde{\bm{a}}),\bm{\mu},d)]\leq\mathbb{E}_{\tilde{\bm{a}}}[\|\tilde{\bm{a}}\|_{2}\cdot
2\bar{\alpha}\bar{d}d]\leq 2\bar{\alpha}\bar{d}^{2}\cdot d$ (108)

Similarly, we have

$\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[u((\tilde{r},\tilde{\bm{a}}),\bm{\mu},d)^{2}]\leq\mathbb{E}_{\tilde{\bm{a}}}[\|\tilde{\bm{a}}\|_{2}^{2}\cdot
2\bar{\alpha}\bar{d}d]\leq 2\bar{\alpha}\bar{d}^{3}\cdot d$

Thus, we verify conditions (N-3) (ii) and (iii) in Huber [1967] for any
$d_{0}\geq 0$. Clearly,
$\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\psi((\tilde{r},\tilde{\bm{a}}),\bm{\mu}^{*})]$
is finite, which verifies condition (N-4) in Huber [1967]. Thus, denote by

$Z_{T-t}(\bm{\mu},\bm{\mu}^{*})=\frac{\|\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}(\psi((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\mu})-\psi((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\mu}^{*}))-\lambda(\bm{\mu})+\lambda(\bm{\mu}^{*})\|}{\frac{1}{\sqrt{T-t}}+\|\lambda(\bm{\mu})\|_{2}}$

By Lemma 6.4, for any $\epsilon>0$ and any
$\gamma^{\prime}\in(\frac{1}{2},1)$, we have

$\displaystyle P\left(\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|\leq
d_{0}}Z_{T-t}(\bm{\mu},\bm{\mu}^{*})\geq 2\epsilon\right)\leq
2\bar{\alpha}\bar{d}^{3}\epsilon^{-2}(T-t)^{-\gamma^{\prime}}$ (109)
$\displaystyle+(T-t)^{\gamma^{\prime}-1}\left(\frac{2\bar{\alpha}\bar{d}^{3}}{4\bar{\alpha}^{2}\bar{d}^{4}q(1-q)}+\frac{2\bar{\alpha}\bar{d}^{3}}{36\bar{\alpha}^{2}\bar{d}^{4}q^{2}(1-q)^{2}}\right)\left(\frac{\gamma^{\prime}(\log(T-t)+\log
d_{0})}{|\log(1-q)|}+1\right)(2M)^{m}$

as long as $T-t\geq n_{0}$, where $n_{0}$ satisfying
$n_{0}^{\gamma^{\prime}-\frac{1}{2}}=\frac{4\bar{\alpha}\bar{d}^{2}}{\epsilon}$
and $\gamma^{\prime}\in(\frac{1}{2},1)$ is an arbitrary number. Moreover, we
set
$M\geq(6\bar{\alpha}^{2}\bar{d}^{2})/(\epsilon\bar{\alpha}\bar{d}^{2})=6\bar{\alpha}/\epsilon$
and $q=1/M$.

We first specify
$\epsilon=\frac{\underline{\alpha}\underline{\beta}}{24\bar{\alpha}\bar{d}^{2}}$
and $\gamma^{\prime}=13/25$. Then, (109) will become

$\displaystyle P\left(\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|\leq
d_{0}}Z_{T-t}(\bm{\mu},\bm{\mu}^{*})\geq\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}\right)\leq
2\bar{\alpha}\bar{d}^{3}\left(\frac{12\bar{\alpha}\bar{d}^{2}}{\underline{\alpha}\underline{\beta}}\right)^{2}(T-t)^{-\frac{13}{25}}$
(110)
$\displaystyle+(T-t)^{-\frac{12}{25}}\left(\frac{2\bar{\alpha}\bar{d}^{3}}{4\bar{\alpha}^{2}\bar{d}^{4}q(1-q)}+\frac{2\bar{\alpha}\bar{d}^{3}}{36\bar{\alpha}^{2}\bar{d}^{4}q^{2}(1-q)^{2}}\right)\left(\frac{13(\log(T-t)+\log
d_{0})}{25|\log(1-q)|}+1\right)(2M)^{m}$

as long as
$T-t\geq(96\bar{\alpha}^{2}\bar{d}^{4}/(\underline{\alpha}\underline{\beta}))^{50}$,
$M=144\bar{\alpha}^{2}\bar{d}^{2}/(\underline{\alpha}\underline{\beta})$ and
$q=1/M=\underline{\alpha}\underline{\beta}/(144\bar{\alpha}^{2}\bar{d}^{2})$.
Denote by $\delta(\bar{\alpha},\bar{d},m)$ a constant that depends solely on
$\bar{\alpha}$, $\bar{d}$ and $m$, i.e.,

$\delta(\bar{\alpha},\bar{d},m)=2\bar{\alpha}\bar{d}^{3}\left(\frac{12\bar{\alpha}\bar{d}^{2}}{\underline{\alpha}\underline{\beta}}\right)^{2}+\left(\frac{2\bar{\alpha}\bar{d}^{3}}{4\bar{\alpha}^{2}\bar{d}^{4}q(1-q)}+\frac{2\bar{\alpha}\bar{d}^{3}}{36\bar{\alpha}^{2}\bar{d}^{4}q^{2}(1-q)^{2}}\right)\left(\frac{13}{25|\log(1-q)|}+1\right)(2M)^{m}$
(111)

with $M=144\bar{\alpha}^{2}\bar{d}^{2}/(\underline{\alpha}\underline{\beta})$
and
$q=1/M=\underline{\alpha}\underline{\beta}/(144\bar{\alpha}^{2}\bar{d}^{2})$.
Then, from (110), we have

$P\left(\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|\leq
d_{0}}Z_{T-t}(\bm{\mu},\bm{\mu}^{*})\geq\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}\right)\leq\delta(\bar{\alpha},\bar{d},m)\cdot\frac{\log(T-t)+\log
d_{0}}{(T-t)^{\frac{12}{25}}}$ (112)

as long as
$T-t\geq(96\bar{\alpha}^{2}\bar{d}^{4}/(\underline{\alpha}\underline{\beta}))^{50}$.
Note that

$\nabla\delta(\bm{\mu})-\nabla\delta(\bm{\mu}^{*})=\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}(\psi((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\mu})-\psi((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\mu}^{*}))-\lambda(\bm{\mu})+\lambda(\bm{\mu}^{*}).$

We know that (112) implies that

$P\left(\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|\leq
d_{0}}\frac{\|\nabla\delta(\bm{\mu})-\nabla\delta(\bm{\mu}^{*})\|_{2}}{\frac{1}{\sqrt{T-t}}+\|\lambda(\bm{\mu})\|_{2}}\geq\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}\right)\leq\delta(\bar{\alpha},\bar{d},m)\cdot\frac{\log(T-t)+\log
d_{0}}{(T-t)^{\frac{12}{25}}}.$ (113)

From Section 3, we have $\|\tilde{\bm{\mu}}\|_{2}\leq\gamma\sqrt{m}$ and
$\|\bm{\mu}^{*}\|_{2}\leq\gamma\sqrt{m}$, which implies that
$r_{0}=\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}\leq 2\gamma\sqrt{m}$. Therefore,
we can simply set $d_{0}=2\gamma\sqrt{m}$ and we know that $r_{0}$ is always
upper bounded by $d_{0}$, which implies that

$\displaystyle P\left(\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|\leq
r_{0}}\frac{\|\nabla\delta(\bm{\mu})-\nabla\delta(\bm{\mu}^{*})\|_{2}}{\frac{1}{\sqrt{T-t}}+\|\lambda(\bm{\mu})\|_{2}}\geq\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}\right)$
$\displaystyle\leq P\left(\sup_{\|\bm{\mu}-\bm{\mu}^{*}\|\leq
d_{0}}\frac{\|\nabla\delta(\bm{\mu})-\nabla\delta(\bm{\mu}^{*})\|_{2}}{\frac{1}{\sqrt{T-t}}+\|\lambda(\bm{\mu})\|_{2}}\geq\frac{\underline{\alpha}\underline{\beta}}{12\bar{\alpha}\bar{d}^{2}}\right)$
(114)
$\displaystyle\leq\delta(\bar{\alpha},\bar{d},m)\cdot\frac{\log(T-t)+\log(2\gamma\sqrt{m})}{(T-t)^{\frac{12}{25}}}$

where the first inequality follows from $r_{0}\leq d_{0}=2\gamma\sqrt{m}$
almost surely and the second inequality follows from (113) by setting
$d_{0}=2\gamma\sqrt{m}$. Therefore, we denote by
$\delta(\bar{\alpha},\bar{d},m,\gamma)=\delta(\bar{\alpha},\bar{d},m)\cdot\log(2\gamma\sqrt{m})$
and our proof of (98) is completed by noting that

$\|\lambda(\bm{\mu})\|_{2}=\|2\bar{\alpha}\bar{d}^{2}(\bm{\mu}-\bm{\mu}^{*})+\mathbb{E}_{\tilde{\bm{a}}}[\tilde{\bm{a}}\cdot(F(\tilde{\bm{a}}^{\top}\bm{\mu}|\tilde{\bm{a}})-F(\tilde{\bm{a}}^{\top}\bm{\mu}^{*}|\tilde{\bm{a}}))]\|_{2}\leq
3\bar{\alpha}\bar{d}^{2}\cdot\|\bm{\mu}-\bm{\mu}^{*}\|_{2}.$

$\Halmos$

#### Proof of Lemma 8.1.

Following Li and Ye [2021], we denote by

$\phi((r,\bm{a}),\bm{\mu})=-\bm{a}^{\top}\cdot\mathbbm{1}(r>\bm{a}^{\top}\bm{\mu}).$

Then, from Lemma 1 of Li and Ye [2021], we have

$\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\tilde{\bm{\mu}}]^{+}-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\tilde{r}-\tilde{\bm{a}}^{\top}\bm{\mu}^{*}]^{+}=\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\phi((\tilde{r},\tilde{\bm{a}}),\bm{\mu}^{*})]\cdot(\tilde{\bm{\mu}}-\bm{\mu}^{*})+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}\left[\int_{\tilde{\bm{a}}^{\top}\tilde{\bm{\mu}}}^{\tilde{\bm{a}}^{\top}\bm{\mu}^{*}}(\mathbbm{1}(\tilde{r}>v)-\mathbbm{1}(\tilde{r}>\tilde{\bm{a}}^{\top}\bm{\mu}^{*}))dv\right].$
(115)

Also, from Lemma 2 of Li and Ye [2021], we have

$\displaystyle\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}([\tilde{r}_{\tau}-\tilde{\bm{a}}^{\top}_{\tau}\tilde{\bm{\mu}}]^{+}-[\tilde{r}_{\tau}-\tilde{\bm{a}}^{\top}_{\tau}\bm{\mu}^{*}]^{+})=$
$\displaystyle\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\phi((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\mu}^{*})\cdot(\tilde{\bm{\mu}}-\bm{\mu}^{*})$
(116)
$\displaystyle+\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\int_{\tilde{\bm{a}}_{\tau}^{\top}\tilde{\bm{\mu}}}^{\tilde{\bm{a}}_{\tau}^{\top}\bm{\mu}^{*}}(\mathbbm{1}(\tilde{r}_{\tau}>v)-\mathbbm{1}(\tilde{r}_{\tau}>\tilde{\bm{a}}_{\tau}^{\top}\bm{\mu}^{*}))dv$

Plugging (115) and (116) into (103), we have that

$\displaystyle\frac{\underline{\alpha}\underline{\beta}}{2}\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\leq\underbrace{\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\phi((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\mu}^{*})\cdot(\tilde{\bm{\mu}}-\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\phi((\tilde{r},\tilde{\bm{a}}),\bm{\mu}^{*})]\cdot(\tilde{\bm{\mu}}-\bm{\mu}^{*})}_{I}$
(117)
$\displaystyle+\underbrace{\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\int_{\tilde{\bm{a}}_{\tau}^{\top}\tilde{\bm{\mu}}}^{\tilde{\bm{a}}_{\tau}^{\top}\bm{\mu}^{*}}(\mathbbm{1}(\tilde{r}_{\tau}>v)-\mathbbm{1}(\tilde{r}_{\tau}>\tilde{\bm{a}}_{\tau}^{\top}\bm{\mu}^{*}))dv-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}\left[\int_{\tilde{\bm{a}}^{\top}\tilde{\bm{\mu}}}^{\tilde{\bm{a}}^{\top}\bm{\mu}^{*}}(\mathbbm{1}(\tilde{r}>v)-\mathbbm{1}(\tilde{r}>\tilde{\bm{a}}^{\top}\bm{\mu}^{*}))dv\right]}_{II}$

We proceed by bounding the term I and term II separately.
Bound I: by Matrix Hoeffding’s inequality, we have that

$P\left(\|\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\phi((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\phi((\tilde{r},\tilde{\bm{a}}),\bm{\mu}^{*})]\|_{2}\geq\epsilon\right)\leq
m\cdot\exp\left(-\frac{\epsilon^{2}\cdot(T-t)}{\bar{d}^{2}}\right)$

which implies that

$P\left(\left|I\right|\geq\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}\right)\leq
m\cdot\exp\left(-\frac{\epsilon^{2}\cdot(T-t)}{\bar{d}^{2}}\right)$ (118)

Bound II: We define a function

$\eta((r,\bm{a}),\bm{\mu}_{1},\bm{\mu}_{2})=\int_{\bm{a}^{\top}\bm{\mu}_{1}}^{\bm{a}^{\top}\bm{\mu}_{2}}(\mathbbm{1}(r>v)-\mathbbm{1}(r>\bm{a}^{\top}\bm{\mu}^{*}))dv$

for any $\bm{\mu}_{1},\bm{\mu}_{2}\in\hat{\mathcal{S}}$. We have

$II=\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\bm{\mu}^{*})]$
(119)

We utilize a splitting scheme to split the set
$\\{\bm{\mu}:\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq\sqrt{m}\cdot\gamma\\}$ into
disjoint cubes, similar to Huber [1967] and Li and Ye [2021]. It is clear to
see that $\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}\leq\sqrt{m}\cdot\gamma$. The
idea is to divide the region
$\\{\bm{\mu}:\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq\sqrt{m}\cdot\gamma\\}$ into a
slowly increasing number of smaller cubes. We consider the concentric cubes:

$C_{k}=\\{\bm{\mu}:\|\bm{\mu}-\bm{\mu}^{*}\|_{2}\leq(1-q)^{k}\cdot\sqrt{m}\gamma\\},\leavevmode\nobreak\
\leavevmode\nobreak\ k=1,\dots,k_{0}$

where $q$ is a constant such that
$\bar{\alpha}\cdot\bar{d}^{2}\cdot\frac{q(1+q)}{(1-q)^{2}}\leq\frac{\underline{\alpha}\underline{\beta}}{32}$,
and $k_{0}$ is a constants such that
$(1-q)^{k_{0}}\cdot\sqrt{m}\gamma=\epsilon$. We then further divide the region
$C_{k-1}\setminus C_{k}$ into cubes $\\{\Omega_{kl}\\}_{l=1}^{l_{k}}$ with
edges of length $2(1-q)^{k}\cdot q\cdot\sqrt{m}\gamma$ such that the centers
of these cubes $\bm{\xi}_{kl}$ satisfies

$\|\bm{\xi}_{kl}\|_{2}=(1-q)^{k-1}(1-\frac{q}{2})\cdot\sqrt{m}\gamma,\leavevmode\nobreak\
\leavevmode\nobreak\ l=1,\dots,k_{l}.$

In total, there are no more than $k_{0}\cdot(\frac{2}{q})^{m}$ number of
cubes. We now denote by $\tilde{\Omega}$ the cube that contains
$\tilde{\bm{\mu}}$ and denote by $\tilde{\bm{\xi}}$ the center of the cube
$\tilde{\Omega}$. Note that both $\tilde{\Omega}$ and $\tilde{\bm{\xi}}$ are
random, where the randomness arises from $\tilde{\bm{\mu}}$.

$\displaystyle\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\bm{\mu}^{*})]=$
$\displaystyle\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})]$
$\displaystyle+\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\bm{\mu}^{*})]$

which implies that

$\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\bm{\mu}^{*})]\geq\epsilon^{2}+\epsilon\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{8}\right)$
(120) $\displaystyle\leq$ $\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})]\geq\frac{\epsilon^{2}}{2}+\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{16}\right)$
$\displaystyle+P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\bm{\mu}^{*})]\geq\frac{\epsilon^{2}}{2}+\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{16}\right)$

We have the following result.

###### Claim 7

It holds that

$\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})]\geq\frac{\epsilon^{2}}{2}+\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}\|_{2}^{2}}{16}\right)$
$\displaystyle\leq
k_{0}\cdot\left(\frac{2}{q}\right)^{m}\cdot\exp\left(-\frac{\epsilon^{2}(T-t)}{2q^{2}\bar{d}^{2}}\right)$

where $q$ is a constant such that
$\bar{\alpha}\cdot\bar{d}^{2}\cdot\frac{q(1+q)}{(1-q)^{2}}\leq\frac{\underline{\alpha}\underline{\beta}}{32}$,
and $k_{0}$ is a constants such that
$(1-q)^{k_{0}}\cdot\sqrt{m}\gamma=\epsilon$.

We also have the following result.

###### Claim 8

It holds that

$\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\bm{\mu}^{*})]\geq\frac{\epsilon^{2}}{2}+\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{16}\right)$
$\displaystyle\leq
k_{0}\cdot\left(\frac{2}{q}\right)^{m}\cdot\exp\left(-\frac{\epsilon^{2}\cdot(T-t)q^{2}}{2\bar{d}^{2}}\right)$

where $q$ is a constant such that
$\bar{\alpha}\cdot\bar{d}^{2}\cdot\frac{q(1+q)}{(1-q)^{2}}\leq\frac{\underline{\alpha}\underline{\beta}}{32}$,
and $k_{0}$ is a constants such that
$(1-q)^{k_{0}}\cdot\sqrt{m}\gamma=\epsilon$.

Combining 7, 8 and (120), we have that

$\displaystyle
P\left(\text{II}\geq\epsilon^{2}+\epsilon\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{8}\right)$
(121) $\displaystyle=$ $\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\bm{\mu}^{*})]\geq\epsilon^{2}+\epsilon\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{8}\right)$
$\displaystyle\leq$ $\displaystyle
k_{0}\cdot\left(\frac{2}{q}\right)^{m}\cdot\exp\left(-\frac{\epsilon^{2}(T-t)}{2q^{2}\bar{d}^{2}}\right)+k_{0}\cdot\left(\frac{2}{q}\right)^{m}\cdot\exp\left(-\frac{\epsilon^{2}\cdot(T-t)q^{2}}{2\bar{d}^{2}}\right)$

where $q$ is a constant such that
$\bar{\alpha}\cdot\bar{d}^{2}\cdot\frac{q(1+q)}{(1-q)^{2}}\leq\frac{\underline{\alpha}\underline{\beta}}{32}$,
and $k_{0}$ is a constants such that
$(1-q)^{k_{0}}\cdot\sqrt{m}\gamma=\epsilon$. Our bound of the term II is now
completed.

We now use the bound on I and II to prove the probability bound on the event
$\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\geq\epsilon^{2}$. Combining (118)
and (121), we have

$\displaystyle P\left(\text{I}+\text{II}\geq
2\epsilon^{2}+2\epsilon\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{4}\right)$
$\displaystyle\leq$ $\displaystyle
P\left(\text{I}\geq\epsilon^{2}+\epsilon\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{8}\right)+P\left(\text{II}\geq\epsilon^{2}+\epsilon\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{8}\right)$
$\displaystyle\leq$ $\displaystyle
m\cdot\exp\left(-\frac{\epsilon^{2}\cdot(T-t)}{\bar{d}^{2}}\right)+k_{0}\cdot\left(\frac{2}{q}\right)^{m}\cdot\left(\exp\left(-\frac{\epsilon^{2}(T-t)}{2q^{2}\bar{d}^{2}}\right)+\exp\left(-\frac{\epsilon^{2}\cdot(T-t)q^{2}}{2\bar{d}^{2}}\right)\right)$

where $c_{2}$ is a constant. Further note that

$\frac{\underline{\alpha}\underline{\beta}}{2}\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\leq\text{I}+\text{II},$

and

$\frac{\underline{\alpha}\underline{\beta}}{2}\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\geq
2\epsilon^{2}+2\epsilon\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{4}$

implies that

$\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\geq\epsilon^{2}\cdot\frac{4(2+\sqrt{2\underline{\alpha}\underline{\beta}+4})^{2}}{\underline{\alpha}^{2}\underline{\beta}^{2}}.$

Therefore, we have that

$\displaystyle
P\left(\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\geq\epsilon^{2}\cdot\frac{4(2+\sqrt{2\underline{\alpha}\underline{\beta}+4})^{2}}{\underline{\alpha}^{2}\underline{\beta}^{2}}\right)\leq$
$\displaystyle
m\cdot\exp\left(-\frac{\epsilon^{2}\cdot(T-t)}{\bar{d}^{2}}\right)$
$\displaystyle+k_{0}\cdot\left(\frac{2}{q}\right)^{m}\cdot\left(\exp\left(-\frac{\epsilon^{2}(T-t)}{2q^{2}\bar{d}^{2}}\right)+\exp\left(-\frac{\epsilon^{2}\cdot(T-t)q^{2}}{2\bar{d}^{2}}\right)\right)$

By substituting
$\epsilon^{\prime}=\epsilon\cdot\frac{2(2+\sqrt{2\underline{\alpha}\underline{\beta}+4})}{\underline{\alpha}\underline{\beta}}$
and noting that $k_{0}=O(\log(\frac{1}{\epsilon}))$, we have that

$P\left(\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}\geq(\epsilon^{\prime})^{2}\right)\leq
K\cdot\log\left(\frac{1}{\epsilon^{\prime}}\right)\exp\left(-(\epsilon^{\prime})^{2}(T-t)\right)$

for a constant $K$ that only depends on parameters
$\underline{\alpha},\underline{\beta},\bar{\alpha},\bar{d}$, which completes
our proof. $\Halmos$

#### Proof of 7.

We denote by

$g((r,\bm{a}),\bm{\mu}_{1},d)=\sup_{\bm{\mu}_{2}:\|\bm{\mu}_{2}-\bm{\mu}_{1}\|_{2}\leq
d}\eta((r,\bm{a}),\bm{\mu}_{1},\bm{\mu}_{2}).$

Then we have

$\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})]\leq\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\tilde{d})+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]$

where $\tilde{d}$ denotes the edge length of the cube $\tilde{\Omega}$. We now
consider the cubes $\\{\Omega_{kl}\\}$ and the center concentric cubes
$C_{k_{0}}$ separately.
(i). If the cube $\tilde{\Omega}\in\\{\Omega_{kl}\\}$, then, we note that

$\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]\leq\mathbb{E}_{\tilde{\bm{a}}}\left[\sup_{\tilde{\bm{\mu}}_{2}:\|\tilde{\bm{\mu}}_{2}-\tilde{\bm{\xi}}\|_{2}\leq\tilde{d}}\int^{\tilde{\bm{a}}^{\top}\bm{\mu}^{*}}_{\tilde{\bm{a}}^{\top}\tilde{\bm{\mu}}_{2}}\int_{\tilde{\bm{a}}^{\top}\tilde{\bm{\mu}}_{2}}^{\tilde{\bm{a}}^{\top}\tilde{\bm{\xi}}}(\mathbbm{1}(r>v)-\mathbbm{1}(r>\tilde{\bm{a}}^{\top}\bm{\mu}^{*}))dvdF(r|\tilde{\bm{a}})\right]\leq\bar{\alpha}\bar{d}^{2}\cdot\tilde{d}\cdot(\|\bm{\mu}^{*}-\tilde{\bm{\xi}}\|_{2}+\tilde{d})$

By definition, we have $\tilde{d}=q\cdot\|\bm{\mu}^{*}-\tilde{\bm{\xi}}\|_{2}$
and
$\|\bm{\mu}^{*}-\tilde{\bm{\mu}}\|_{2}\geq\|\bm{\mu}^{*}-\tilde{\bm{\xi}}\|_{2}-\tilde{d}$.
Then, we have

$\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]\leq\bar{\alpha}\cdot\bar{d}^{2}\cdot\frac{q(1+q)}{(1-q)^{2}}\cdot\|\bm{\mu}^{*}-\tilde{\bm{\mu}}\|_{2}^{2}\leq\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{32}$

by specifying $q$ such that
$\bar{\alpha}\cdot\bar{d}^{2}\cdot\frac{q(1+q)}{(1-q)^{2}}\leq\frac{\underline{\alpha}\underline{\beta}}{32}$.
(ii). If the cube $\tilde{\Omega}=C_{k_{0}}$, then by noting
$\tilde{\bm{\xi}}=\bm{\mu}^{*}$ and
$(1-q)^{k_{0}}\cdot\sqrt{m}\gamma=\epsilon$, we have that

$\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]\leq\mathbb{E}_{\tilde{\bm{a}}}\left[\sup_{\bm{\mu}_{2}:\|\bm{\mu}_{2}-\tilde{\bm{\xi}}\|_{2}\leq\tilde{d}}\int^{\tilde{\bm{a}}^{\top}\bm{\mu}^{*}}_{\tilde{\bm{a}}^{\top}\bm{\mu}_{2}}\int_{\tilde{\bm{a}}^{\top}\bm{\mu}_{2}}^{\tilde{\bm{a}}^{\top}\tilde{\bm{\xi}}}(\mathbbm{1}(r>v)-\mathbbm{1}(r>\tilde{\bm{a}}^{\top}\bm{\mu}^{*}))dvdF(r|\tilde{\bm{a}})\right]\leq\bar{\alpha}\cdot\bar{d}^{2}\cdot\epsilon^{2}$

Therefore, for both (i) and (ii), it holds that

$\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\mu}},\tilde{\bm{\xi}})]\geq\bar{\alpha}\bar{d}^{2}\epsilon^{2}+\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{16}\right)$
$\displaystyle\leq$ $\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\tilde{d})+\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]\geq\bar{\alpha}\bar{d}^{2}\epsilon^{2}+\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}+\frac{\underline{\alpha}\underline{\beta}\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}^{2}}{16}\right)$
$\displaystyle\leq$ $\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\tilde{d})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]\geq\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}\right)$
$\displaystyle\leq$ $\displaystyle
P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\tilde{d})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]\geq\frac{\epsilon\cdot\tilde{d}}{2q}\right)$

We apply the Hoeffding inequality to bound the above probability for each cube
$\Omega_{kl}$, and $C_{k_{0}}$. It holds that

$g((r,\bm{a}),\bm{\xi}_{kl},d_{kl})\leq\bar{d}\cdot
d_{kl},\leavevmode\nobreak\ \text{and\leavevmode\nobreak\
}g((r,\bm{a}),\bm{\xi}_{k_{0}},d_{k_{0}})\leq\bar{d}\cdot
d_{k_{0}}\leavevmode\nobreak\ \leavevmode\nobreak\ \forall(r,\bm{a})$

where $d_{kl}$ denotes the length of the edge of the cube $\Omega_{kl}$ and
$d_{k_{0}}$ denotes the length of the edge of the cube $C_{k_{0}}$. By
Hoeffding’s inequality, we have

$P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\xi}_{kl},d_{kl})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\bm{\xi}_{kl},d_{kl})]\geq\frac{\epsilon\cdot
d_{kl}}{2q}\right)\leq\exp\left(-\frac{\epsilon^{2}(T-t)}{2q^{2}\bar{d}^{2}}\right)$

for each cube $\Omega_{kl}$, and

$P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\xi}_{k_{0}},d_{k_{0}})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\bm{\xi}_{k_{0}},d_{k_{0}})]\geq\frac{\epsilon\cdot
d_{k_{0}}}{2q}\right)\leq\exp\left(-\frac{\epsilon^{2}(T-t)}{2q^{2}\bar{d}^{2}}\right)$

for the cube $C_{k_{0}}$. Note that

$\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\tilde{\bm{\xi}},\tilde{d})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\tilde{\bm{\xi}},\tilde{d})]\geq\frac{\epsilon\cdot\tilde{d}}{2q}$

implies that

$\frac{1}{T-t}\cdot\sum_{\tau=t}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\xi}_{k_{0}},d_{k_{0}})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\bm{\xi}_{k_{0}},d_{k_{0}})]\geq\frac{\epsilon\cdot
d_{k_{0}}}{2q},$

or there exists at least one $\Omega_{kl}$ such that

$\frac{1}{T-t}\cdot\sum_{\tau=t}^{T}g((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\xi}_{kl},d_{kl})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[g((\tilde{r},\tilde{\bm{a}}),\bm{\xi}_{kl},d_{kl})]\geq\frac{\epsilon\cdot
d_{kl}}{2q}.$

Applying the union bound, our proof is completed. $\Halmos$

#### Proof of 8.

Note that

$\eta((r,\bm{a}),\tilde{\bm{\xi}},\bm{\mu}^{*})\leq\bar{d}\cdot\|\tilde{\bm{\xi}}-\bm{\mu}^{*}\|_{2}$

Then, if $\tilde{\Omega}\in\\{\Omega_{kl}\\}$, we have that

$\eta((r,\bm{a}),\tilde{\bm{\xi}},\bm{\mu}^{*})\leq\bar{d}\cdot\|\tilde{\bm{\xi}}-\bm{\mu}^{*}\|_{2}\leq\frac{\bar{d}\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{q}$

and if $\tilde{\Omega}=C_{k_{0}}$, we have that

$\eta((r,\bm{a}),\tilde{\bm{\xi}},\bm{\mu}^{*})\leq\bar{d}\cdot\|\tilde{\bm{\xi}}-\bm{\mu}^{*}\|_{2}=0$

by noting $\tilde{\bm{\xi}}=\bm{\xi}_{k_{0}}=\bm{\mu}^{*}$. Now, for each
$\Omega_{kl}$, by Hoeffding’s inequality, we have

$P\left(\frac{1}{T-t}\cdot\sum_{\tau=t+1}^{T}\eta((\tilde{r}_{\tau},\tilde{\bm{a}}_{\tau}),\bm{\xi}_{kl},\bm{\mu}^{*})-\mathbb{E}_{(\tilde{r},\tilde{\bm{a}})}[\eta((\tilde{r},\tilde{\bm{a}}),\bm{\xi}_{kl},\bm{\mu}^{*})]\geq\frac{\epsilon\cdot\|\tilde{\bm{\mu}}-\bm{\mu}^{*}\|_{2}}{2}\right)\leq\exp\left(-\frac{\epsilon^{2}\cdot(T-t)q^{2}}{2\bar{d}^{2}}\right).$

Our proof is completed from the union bound over all $\Omega_{kl}$. $\Halmos$

#### Proof of Theorem 4.9.

From (4.3), we have

$\displaystyle\text{Myopic}_{t}(\pi,\tilde{\bm{c}}^{\pi}_{t})\leq$
$\displaystyle
2\bar{\alpha}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}[\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot\mathrm{Var}(M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1}))]+\mathbb{E}_{I_{t}}[G_{\tilde{\bm{c}}_{t}^{\pi}}(I_{t})]$
(122)
$\displaystyle+2\bar{\alpha}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot\left(\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}-\mathbb{E}_{I_{t+1}}[M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})]\right)^{2}\right]$

Then, from Lemma 4.6 and Lemma 4.7, we know that

$\displaystyle\text{Myopic}_{t}(\pi,\tilde{\bm{c}}^{\pi}_{t})\leq$
$\displaystyle\frac{2\bar{\alpha}\kappa_{1}+\kappa_{2}}{T-t}+(2\bar{\alpha}\kappa_{1}+\kappa_{2})\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbb{E}_{I_{t+1}}[(\tilde{\bm{a}}_{t}^{\top}\tilde{\bm{\mu}}_{1}-\tilde{\bm{a}}_{t}^{\top}\hat{\bm{\mu}}_{1})^{2}]\right]$
(123)
$\displaystyle+(2\bar{\alpha}\kappa_{1}+\kappa_{2})\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbbm{1}_{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}}\cdot\mathbb{E}_{I_{t+1}}[(\tilde{\bm{a}}_{t}^{\top}\tilde{\bm{\mu}}_{2}-\tilde{\bm{a}}_{t}^{\top}\hat{\bm{\mu}}_{2})^{2}]\right]$
$\displaystyle+2\bar{\alpha}\cdot\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot\left(\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}-\mathbb{E}_{I_{t+1}}[M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})]\right)^{2}\right]$

where $\tilde{\bm{\mu}}_{1},\tilde{\bm{\mu}}_{2}$ are defined in (41) and
$\hat{\bm{\mu}}_{1},\hat{\bm{\mu}}_{2}$ are defined in (45), with
$\bm{c}=\tilde{\bm{c}}^{\pi}_{t}$. Moreover, from Lemma 4.4 and the definition
of $\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}$ in Algorithm 3, we
know

$\displaystyle\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot\left(\hat{M}_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}-\mathbb{E}_{I_{t+1}}[M_{\tilde{\bm{c}}^{\pi}_{t},\tilde{\bm{a}}_{t}}(I_{t+1})]\right)^{2}\right]\leq\mathbb{E}_{\tilde{\bm{a}}_{t}}\left[\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot\left((\hat{\bm{\mu}}_{1}-\mathbb{E}[\tilde{\bm{\mu}}_{1}])^{2}+(\hat{\bm{\mu}}_{1}-\mathbb{E}[\tilde{\bm{\mu}}_{2}])^{2}\right)\right]$
$\displaystyle\leq\mathbb{E}[(\hat{\bm{\mu}}_{1}-\tilde{\bm{\mu}}_{1})^{2}]+2\cdot\mathbb{E}[(\hat{\bm{\mu}}_{1}-\hat{\bm{\mu}}_{2})^{2}]+2\cdot\mathbb{E}[\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot(\hat{\bm{\mu}}_{2}-\tilde{\bm{\mu}}_{2})^{2}]$

We apply 4 to bound the term
$\mathbb{E}[(\hat{\bm{\mu}}_{1}-\hat{\bm{\mu}}_{2})^{2}]$ and we apply the
“dual convergence” established in Lemma 4.8 to bound
$\mathbb{E}[(\hat{\bm{\mu}}_{1}-\tilde{\bm{\mu}}_{1})^{2}]$ and
$\mathbb{E}[\mathbbm{1}_{\\{\tilde{\bm{c}}^{\pi}_{t}\geq\tilde{\bm{a}}_{t}\\}}\cdot(\hat{\bm{\mu}}_{2}-\tilde{\bm{\mu}}_{2})^{2}]$
at the order of $O(\frac{1}{T-t})$. Therefore, we prove our result. $\Halmos$