N^{\prime}$ decides a distribution $\pi_{i,\theta_{i}}\in\Delta(A_{i})$. A
type profile $\theta\in\Theta$ sampled from $\rho\in\Delta(\Theta)$ determines
the active players, whose actions $a_{i}\in A_{i}$ are independently sampled
from $\pi_{i,\theta_{i}}$ for each $i\in N$. Therefore, the action profile of
the active players follows a type-wise product distribution
$\pi\in\Pi_{\mathsf{Prod}}$. Recall that we call $\pi\in\Delta(A)^{\Theta}$ a
type-wise product distribution if there exists some
$\pi_{i,\theta_{i}}\in\Delta(A_{i})$ for each $i\in N$ and
$\theta_{i}\in\Theta_{i}$ such that $\pi(\theta;a)=\prod_{i\in
N}\pi_{i,\theta_{i}}(a_{i})$ for every $\theta\in\Theta$ and $a\in A$. We
define an approximate version of Bayes Nash equilibria in the agent normal
form as follows.

######  Definition 2.25 ($\epsilon$-Approximate Bayes Nash equilibria
($\epsilon$-BNEs) in the agent normal form).

For any $\epsilon\geq 0$, a type-wise product distribution
$\pi\in\Pi_{\mathsf{Prod}}\subseteq\Delta(A)^{\Theta}$ is an
$\epsilon$-approximate Bayes Nash equilibria in the agent normal form if for
any $i\in N$ and $\phi\colon\Theta_{i}\times A_{i}\to A_{i}$, it holds that

$\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{a\sim\pi(\theta)}\left[v_{i}(\theta;a)\right]\right]\geq\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{a\sim\pi(\theta)}\left[v_{i}(\theta;\phi(\theta_{i},a_{i}),a_{-i})\right]\right]-\epsilon.$
($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$)

Let $\Pi_{\mathsf{BNE}}^{\epsilon}\subseteq\Delta(A)^{\Theta}$ be the set of
all $\epsilon$-approximate Bayes Nash equilibria in the agent normal form.

Here we show the equivalence of $\Sigma_{\mathsf{BNE}}^{\epsilon}$ and
$\Pi_{\mathsf{BNE}}^{\epsilon}$. This is an approximate version of the well-
known fact that Nash equilibria in the strategic form and the agent normal
form are equivalent (Harsanyi, 1967), but we provide the proof for
completeness.

######  Proposition 2.26.

For any distribution $\sigma\in\Sigma_{\mathsf{BNE}}^{\epsilon}$, its
corresponding type-wise distribution satisfies
$\eta(\sigma)\in\Pi_{\mathsf{BNE}}^{\epsilon}$. Conversely, for any type-wise
distribution $\pi\in\Pi_{\mathsf{BNE}}^{\epsilon}$, there exists a
distribution $\sigma\in\Sigma_{\mathsf{BNE}}^{\epsilon}$ such that
$\eta(\sigma)=\pi$.

###### Proof.

Let $\sigma\in\Sigma_{\mathsf{BNE}}^{\epsilon}$ be any $\epsilon$-BNE in the
strategic form and $\pi=\eta(\sigma)$. First, we show that $\pi$ is a type-
wise product distribution. Since $\sigma\in\Sigma_{\mathsf{Prod}}$, there
exists $\sigma_{i}\in\Delta(S_{i})$ for each $i\in N$ such that
$\sigma(s)=\prod_{i=1}^{n}\sigma_{i}(s_{i})$ holds for every $s\in S$. For
each $i\in N$ and $\theta_{i}\in\Theta_{i}$, define
$\pi_{i,\theta_{i}}\in\Delta(A_{i})$ by
$\pi_{i,\theta_{i}}(a_{i})=\Pr_{s_{i}\sim\sigma_{i}}(s_{i}(\theta_{i})=a_{i})$
for each $a_{i}\in A_{i}$. Then

$\pi(\theta;a)=\eta(\sigma)(\theta;a)=\Pr_{s\sim\sigma}(s(\theta)=a)=\prod_{i\in
N}\Pr_{s_{i}\sim\sigma_{i}}(s_{i}(\theta_{i})=a_{i})=\prod_{i\in
N}\pi_{i,\theta_{i}}(a_{i})$

for every $\theta\in\Theta$ and $a\in A$, which implies
$\pi\in\Pi_{\mathsf{Prod}}$.

Next, we show the incentive constraint ($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$)
for each $i\in N$ and $\phi\colon\Theta_{i}\times A_{i}\to A_{i}$. We use the
incentive constraint ($\mathrm{IC}_{\mathrm{BNE}}$) for
$\phi_{\mathsf{SF}}\colon S_{i}\to S_{i}$ defined by
$(\phi_{\mathsf{SF}}(s_{i}))(\theta_{i})=\phi(\theta_{i},s_{i}(\theta_{i}))$
for each $\theta_{i}\in\Theta_{i}$. Since $\eta(\sigma)=\pi$ implies that
$s(\theta)$ conforms to $\pi(\theta)\in\Delta(A)$, the left-hand side of
($\mathrm{IC}_{\mathrm{BNE}}$) equals the left-hand side of
($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$). The right-hand side of
($\mathrm{IC}_{\mathrm{BNE}}$) equals

$\displaystyle\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{s\sim\sigma}\left[v_{i}(\theta;(\phi_{\mathsf{SF}}(s_{i}))(\theta_{i}),s_{-i}(\theta_{-i}))\right]\right]-\epsilon$
$\displaystyle=\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{s\sim\sigma}\left[v_{i}(\theta;\phi(\theta_{i},s_{i}(\theta_{i})),s_{-i}(\theta_{-i}))\right]\right]-\epsilon$
(since
$(\phi_{\mathsf{SF}}(s_{i}))(\theta_{i})=\phi(\theta_{i},s_{i}(\theta_{i}))$)
$\displaystyle=\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{a\sim\pi(\theta)}\left[v_{i}(\theta;\phi(\theta_{i},a_{i}),a_{-i})\right]\right]-\epsilon,$
(since $s(\theta)$ conforms to $\pi(\theta)$)

which coincides with the right-hand side of
($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$). Therefore, $\pi$ is an $\epsilon$-BNE
in the agent normal form.

Conversely, let $\pi\in\Pi_{\mathsf{BNE}}^{\epsilon}$ be any $\epsilon$-BNE in
the agent normal form. Since $\pi$ is a type-wise product distribution, there
exists $\pi_{i,\theta_{i}}\in\Delta(A_{i})$ for each $i\in N$ and
$\theta_{i}\in\Theta_{i}$ such that $\pi(\theta;a)=\prod_{i\in
N}\pi_{i,\theta_{i}}(a_{i})$ for every $\theta\in\Theta$ and $a\in A$. We can
define the corresponding $\sigma\in\Delta(S)$ by $\sigma(s)=\prod_{i\in
N}\prod_{\theta_{i}\in\Theta_{i}}\pi_{i,\theta_{i}}(s_{i}(\theta_{i}))$ for
every $s\in S$. Then

$\eta(\sigma)(\theta;a)=\Pr_{s\sim\sigma}(s(\theta)=a)=\prod_{i\in
N}\pi_{i,\theta_{i}}(a_{i})=\pi(\theta;a)$

for every $\theta\in\Theta$ and $a\in A$, which implies $\eta(\sigma)=\pi$.

Next, we show $\sigma\in\Sigma_{\mathsf{BNE}}^{\epsilon}$ by proving
$\sigma\in\Sigma_{\mathsf{Prod}}$ and the incentive constraint
($\mathrm{IC}_{\mathrm{BNE}}$) holds for any $i\in N$ and
$\phi_{\mathsf{SF}}\colon S_{i}\to S_{i}$. We can see
$\sigma\in\Sigma_{\mathsf{Prod}}$ by expressing $\sigma$ as
$\sigma(s)=\prod_{i\in N}\sigma_{i}(s_{i})$ for every $s\in S$ where
$\sigma_{i}\in\Delta(S_{i})$ is defined by
$\sigma_{i}(s_{i})=\prod_{\theta_{i}\in\Theta_{i}}\pi_{i,\theta_{i}}(s_{i}(\theta_{i}))$
for every $s_{i}\in S_{i}$. We then prove that ($\mathrm{IC}_{\mathrm{BNE}}$)
holds for any $i\in N$ and $\phi_{\mathsf{SF}}\colon S_{i}\to S_{i}$ by using
($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$) for $\phi\colon\Theta_{i}\times
A_{i}\to A_{i}$ defined by

$\phi(\theta_{i},a_{i})\in\operatorname*{argmax}_{a^{\prime}_{i}\in
A_{i}}\mathop{\mathbb{E}}_{\theta_{-i}\sim\rho|\theta_{i}}\left[\mathop{\mathbb{E}}_{s_{-i}\sim\sigma_{-i}}\left[v_{i}(\theta;a^{\prime}_{i},s_{-i}(\theta_{-i}))\right]\right]$

for each $\theta_{i}\in\Theta_{i}$ and $a_{i}\in A_{i}$, where
$\sigma_{-i}\in\Delta(S_{-i})$ is the product distribution that independently
generates $s_{j}\sim\sigma_{j}$ for each $j\in N\setminus\\{i\\}$. Note that
$\phi(\theta_{i},\cdot)$ can be a constant function. Since $\eta(\sigma)=\pi$,
the left-hand side of ($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$) equals the left-
hand side of ($\mathrm{IC}_{\mathrm{BNE}}$). The right-hand side of
($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$) is bounded as

$\displaystyle\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{a\sim\pi(\theta)}\left[v_{i}(\theta;\phi(\theta_{i},a_{i}),a_{-i})\right]\right]-\epsilon$
$\displaystyle=\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{s_{-i}\sim\sigma_{-i}}\left[v_{i}(\theta;\phi(\theta_{i},s_{i}(\theta_{i})),s_{-i}(\theta_{-i}))\right]\right]-\epsilon$
(since $s(\theta)$ conforms to $\pi(\theta)$)
$\displaystyle=\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{\theta_{-i}\sim\rho|\theta_{i}}\left[\mathop{\mathbb{E}}_{s_{-i}\sim\sigma_{-i}}\left[v_{i}(\theta;\phi(\theta_{i},s_{i}(\theta_{i})),s_{-i}(\theta_{-i}))\right]\right]\right]-\epsilon$
$\displaystyle=\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\max_{a^{\prime}_{i}\in
A_{i}}\mathop{\mathbb{E}}_{\theta_{-i}\sim\rho|\theta_{i}}\left[\mathop{\mathbb{E}}_{s_{-i}\sim\sigma_{-i}}\left[v_{i}(\theta;a^{\prime}_{i},s_{-i}(\theta_{-i}))\right]\right]\right]-\epsilon$
(from the definition of $\phi$)
$\displaystyle\geq\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{s_{i}\sim\sigma_{i}}\left[\mathop{\mathbb{E}}_{\theta_{-i}\sim\rho|\theta_{i}}\left[\mathop{\mathbb{E}}_{s_{-i}\sim\sigma_{-i}}\left[v_{i}(\theta;(\phi_{\mathsf{SF}}(s_{i}))(\theta_{i}),s_{-i}(\theta_{-i}))\right]\right]\right]\right]-\epsilon$
$\displaystyle=\mathop{\mathbb{E}}_{\theta\sim\rho}\left[\mathop{\mathbb{E}}_{s\sim\sigma}\left[v_{i}(\theta;(\phi_{\mathsf{SF}}(s_{i}))(\theta_{i}),s_{-i}(\theta_{-i}))\right]\right]-\epsilon,$

which implies ($\mathrm{IC}_{\mathrm{BNE}}$) for any $\phi_{\mathsf{SF}}\colon
S_{i}\to S_{i}$. ∎

Finally, we relate the classes of Bayes correlated equilibria to Bayes Nash
equilibria. The following proposition shows that if a type-wise product
distribution is contained in each class of Bayes correlated equilibria, it is
a Bayes Nash equilibrium.

######  Proposition 2.27.

$\Pi_{\mathsf{SF}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}=\Pi_{\mathsf{ANF}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}=\Pi_{\mathsf{Com}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}=\Pi_{\mathsf{BS}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}=\Pi_{\mathsf{BNE}}^{\epsilon}$.

###### Proof.

From Propositions 2.20 and 2.23, $\Pi_{\mathsf{SF}}^{\epsilon}$ is a subset of
$\Pi_{\mathsf{ANF}}^{\epsilon}$, $\Pi_{\mathsf{Com}}^{\epsilon}$, and
$\Pi_{\mathsf{BS}}^{\epsilon}$. Moreover, $\Pi_{\mathsf{BS}}^{\epsilon}$ is a
superset of $\Pi_{\mathsf{SF}}^{\epsilon}$, $\Pi_{\mathsf{ANF}}^{\epsilon}$,
and $\Pi_{\mathsf{Com}}^{\epsilon}$. Therefore, it is sufficient to show that
$\Pi_{\mathsf{BNE}}^{\epsilon}\subseteq\Pi_{\mathsf{SF}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}$
and
$\Pi_{\mathsf{BS}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}\subseteq\Pi_{\mathsf{BNE}}^{\epsilon}$.

First, we prove
$\Pi_{\mathsf{BNE}}^{\epsilon}\subseteq\Pi_{\mathsf{SF}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}$.
Suppose $\pi\in\Pi_{\mathsf{BNE}}^{\epsilon}$. From Proposition 2.26, there
exists $\sigma\in\Sigma_{\mathsf{BNE}}^{\epsilon}$ such that
$\eta(\sigma)=\pi$. Since this $\sigma$ satisfies
($\mathrm{IC}_{\mathrm{BNE}}$) for each $i\in N$ and $\phi_{\mathsf{SF}}\colon
S_{i}\to S_{i}$, which is equivalent to ($\mathrm{IC}_{\mathrm{SF}}$). Hence,
$\sigma\in\Sigma_{\mathsf{SF}}^{\epsilon}$, and then
$\pi=\eta(\sigma)\in\Pi_{\mathsf{SF}}^{\epsilon}$. Moreover, from the
definition of $\epsilon$-BNEs in the agent normal form, $\pi$ is a type-wise
product distribution, which implies
$\Pi_{\mathsf{BNE}}^{\epsilon}\subseteq\Pi_{\mathsf{SF}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}$.

Next, we prove
$\Pi_{\mathsf{BS}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}\subseteq\Pi_{\mathsf{BNE}}^{\epsilon}$.
Suppose $\pi\in\Pi_{\mathsf{BS}}^{\epsilon}\cap\Pi_{\mathsf{Prod}}$. Since
$\pi\in\Pi_{\mathsf{BS}}^{\epsilon}$, the incentive constraint
($\mathrm{IC}_{\mathrm{BS}}$) holds for each $i\in N$ and
$\phi\colon\Theta_{i}\times A_{i}$, which is equivalent to
($\mathrm{IC}^{\prime}_{\mathrm{BNE}}$). Moreover, $\pi$ is a type-wise
product distribution since $\pi\in\Pi_{\mathsf{Prod}}$. From the definition of
$\epsilon$-BNEs in the agent normal form, we obtain
$\pi\in\Pi_{\mathsf{BNE}}^{\epsilon}$. ∎

##  3 Algorithm for minimizing untruthful swap regret

In this section, we describe an efficient algorithm for minimizing untruthful
swap regret, which leads to efficient computation of approximate communication
equilibria. In this section, we focus on the problem that a player $i\in N$ is
faced with, and therefore, the subscript $i$ for $A_{i}$, $a_{i}$,
$\Theta_{i}$, $\theta_{i}$, $\pi_{i}^{t}$, and $R_{\mathsf{US},i}^{T}$ is not
essential in this section. We put the subscript $i$ just for notational
consistency.

We derive the algorithm in three steps: First, we reduce untruthful swap
regret minimization to a $\Phi$-regret minimization problem. Then we apply the
$\Phi$-regret minimization framework developed by Gordon et al. (2008) and
reduce it to an online linear optimization problem. Finally, to obtain a
regret upper bound optimal up to a multiplicative constant, we further
decompose it to small external regret minimization problems. The final
algorithm is described in Algorithm 3.

Input: The set of types $\Theta_{i}$ and the set of actions $A_{i}$ are
specified in advance. The reward vector $u_{i}^{t}\in[0,1]^{\Theta_{i}\times
A_{i}}$ is given at the end of each round $t\in[T]$.

Initialize subroutines as follows:

  * •

let $\mathcal{E}_{\theta_{i}}$ be a multiplicative weights algorithm with
decision space $\Theta_{i}$ for each $\theta_{i}\in\Theta_{i}$;

* •

let $\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$ be a
multiplicative weights algorithm with the doubling trick (Cesa-Bianchi et al.,
1997, Section 4.6) with decision space $A_{i}$ for each
$\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ and $a^{\prime}_{i}\in A_{i}$;

for  _each round $t=1,\dots,T$_ do

Let $w^{t}_{\theta_{i}}\in\Delta(\Theta_{i})$ be the output of
$\mathcal{E}_{\theta_{i}}$ in round $t$ for each $\theta_{i}\in\Theta_{i}$;

Let $y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}\in\Delta(A_{i})$ be
the output of $\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$ in
round $t$ for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ and
$a^{\prime}_{i}\in A_{i}$;

Define $Q^{t}\in[0,1]^{(\Theta_{i}\times A_{i})\times(\Theta_{i}\times
A_{i})}$ by
$Q^{t}((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i}))=w^{t}_{\theta_{i}}(\theta^{\prime}_{i})y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})$
for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ and
$a_{i},a^{\prime}_{i}\in A_{i}$;

Compute an eigenvector $x^{t}\in\mathbb{R}^{\Theta_{i}\times A_{i}}$ of
$Q^{t}$ such that $Q^{t}x^{t}=x^{t}$ and
$(x^{t})^{\top}\mathbf{1}=|\Theta_{i}|$;

Decide the output $\pi_{i}^{t}\in\Delta(A_{i})^{\Theta_{i}}$ by
$\pi_{i}^{t}(\theta_{i};a_{i})=x^{t}(\theta_{i},a_{i})$ for each
$\theta_{i}\in\Theta_{i}$ and $a_{i}\in A_{i}$;

Observe reward vector $u_{i}^{t}\in[0,1]^{\Theta_{i}\times A_{i}}$ and feed
reward vectors to subroutines as follows:

  * •

feed $\displaystyle\sum_{a_{i},a^{\prime}_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})\pi_{i}^{t}(\theta^{\prime}_{i};a^{\prime}_{i})\rho_{i}(\theta_{i})u_{i}^{t}(\theta_{i},a_{i})$
as the reward for decision $\theta^{\prime}_{i}\in\Theta_{i}$

to subroutine $\mathcal{E}_{\theta_{i}}$ for each $\theta_{i}\in\Theta_{i}$;

* •

feed
$\displaystyle\pi_{i}^{t}(\theta^{\prime}_{i};a^{\prime}_{i})\rho_{i}(\theta_{i})u_{i}^{t}(\theta_{i},a_{i})$
as the reward for decision $a_{i}\in A_{i}$ to subroutine
$\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$

for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ and $a^{\prime}_{i}\in
A_{i}$;

end for

Algorithm 3 Algorithm for minimizing untruthful swap regret

###  3.1 Reduction to $\Phi$-regret minimization

First, we interpret untruthful swap regret minimization as $\Phi$-regret
minimization with decision space $\mathcal{X}\subseteq[0,1]^{\Theta_{i}\times
A_{i}}$ instead of $\Delta(A_{i})^{\Theta_{i}}$, where

$\mathcal{X}=\left\\{x\in[0,1]^{\Theta_{i}\times
A_{i}}\;\middle|\;\sum_{a_{i}\in
A_{i}}x(\theta_{i},a_{i})=1~{}(\forall\theta_{i}\in\Theta_{i})\right\\}$ (5)

is the set of vectors corresponding to $\Delta(A_{i})^{\Theta_{i}}$. Each
$\pi_{i}\in\Delta(A_{i})^{\Theta_{i}}$ is associated to some $x\in\mathcal{X}$
by $x(\theta_{i},a_{i})=\pi_{i}(\theta_{i};a_{i})$ for each
$\theta_{i}\in\Theta_{i}$ and $a_{i}\in A_{i}$. Let $x^{t}\in\mathcal{X}$ be
the output of the algorithm in each round $t\in[T]$ that corresponds to
$\pi_{i}^{t}$. Let $\bar{u}^{t}\in[0,1]^{\Theta_{i}\times A_{i}}$ be the
reward vector weighted by prior probabilities $\rho_{i}$, i.e.,
$\bar{u}^{t}(\theta_{i},a_{i})=\rho_{i}(\theta_{i})u_{i}^{t}(\theta_{i},a_{i})$
for each $\theta_{i}\in\Theta_{i}$ and $a_{i}\in A_{i}$.

Now we prove that the competitor is supposed to choose an optimal
transformation of all $(x^{t})_{t=1}^{T}$ from the set of linear
transformations defined by

$\mathcal{Q}=\left\\{Q\in[0,1]^{(\Theta_{i}\times
A_{i})\times(\Theta_{i}\times A_{i})}\;\middle|\;\begin{array}[]{l}\text{there
exists some $W\in[0,1]^{\Theta_{i}\times\Theta_{i}}$ such that}\\\
\sum_{\theta^{\prime}_{i}\in\Theta_{i}}W(\theta_{i},\theta^{\prime}_{i})=1~{}\text{($\forall\theta_{i}\in\Theta_{i}$)
and}\\\ \sum_{a_{i}\in
A_{i}}Q((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i}))=W(\theta_{i},\theta^{\prime}_{i})~{}\text{($\forall\theta_{i},\theta^{\prime}_{i}\in\Theta_{i},a^{\prime}_{i}\in
A_{i}$)}\end{array}\right\\}.$ (6)

######  Lemma 3.1.

The untruthful swap regret can be written as

$R_{\mathsf{US},i}=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Qx^{t},\bar{u}^{t}\rangle-\sum_{t=1}^{T}\langle x^{t},\bar{u}^{t}\rangle.$

###### Proof.

The expected reward for the algorithm is

$\displaystyle\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{a_{i}\sim\pi_{i}^{t}(\theta_{i})}\left[u_{i}^{t}(\theta_{i},a_{i})\right]\right]=\sum_{t=1}^{T}\sum_{\theta_{i}\in\Theta_{i}}\rho_{i}(\theta_{i})\sum_{a_{i}\in
A_{i}}\pi_{i}^{t}(\theta_{i};a_{i})u_{i}^{t}(\theta_{i},a_{i})=\sum_{t=1}^{T}\langle
x^{t},\bar{u}^{t}\rangle.$

Next, we express the competitor’s transformation that uses
$\psi\colon\Theta_{i}\to\Theta_{i}$ and $\phi\colon\Theta_{i}\times A_{i}\to
A_{i}$ as a linear transformation. Given
$\pi^{t}_{i}\in\Delta(A_{i})^{\Theta_{i}}$, the competitor’s expected reward
in each round $t\in[T]$ is

$\displaystyle\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{a_{i}\sim\pi_{i}^{t}(\psi(\theta_{i}))}\left[u_{i}^{t}(\theta_{i},\phi(\theta_{i},a_{i}))\right]\right]$
$\displaystyle=\sum_{\theta_{i}\in\Theta_{i}}\rho_{i}(\theta_{i})\sum_{a_{i}\in
A_{i}}\pi_{i}^{t}(\psi(\theta_{i});a_{i})u_{i}^{t}(\theta_{i},\phi(\theta_{i},a_{i}))$
$\displaystyle=\sum_{\theta_{i}\in\Theta_{i}}\sum_{a_{i}\in
A_{i}}x^{t}(\psi(\theta_{i}),a_{i})\bar{u}^{t}(\theta_{i},\phi(\theta_{i},a_{i}))$
$\displaystyle=\left\langle Q_{\psi}x^{t},Q_{\phi}\bar{u}^{t}\right\rangle,$

where $Q_{\psi},Q_{\phi}\in[0,1]^{(\Theta_{i}\times
A_{i})\times(\Theta_{i}\times A_{i})}$ are the matrices defined as follows.

  * •

The linear transformation $Q_{\psi}$ for $x^{t}$ is defined as the Kronecker
product $Q_{\psi}=W_{\psi}\otimes I$ of the zero-one stochastic matrix
$W_{\psi}\in\\{0,1\\}^{\Theta_{i}\times\Theta_{i}}$, where
$W_{\psi}(\theta_{i},\theta^{\prime}_{i})=1$ if
$\theta^{\prime}_{i}=\psi(\theta_{i})$ and $0$ otherwise, and the identity
matrix $I\in\\{0,1\\}^{A_{i}\times A_{i}}$.

  * •

The linear transformation $Q_{\phi}$ for $\bar{u}^{t}$ is defined as the block
diagonal matrix, where each block
$Q_{\phi(\theta_{i},\cdot)}\in\\{0,1\\}^{A_{i}\times A_{i}}$ corresponding to
$\theta_{i}\in\Theta_{i}$ is the zero-one stochastic matrix defined by
$Q_{\phi(\theta_{i},\cdot)}(a_{i},a^{\prime}_{i})=1$ if
$a^{\prime}_{i}=\phi(\theta_{i},a_{i})$ and $0$ otherwise.

Since $\left\langle
Q_{\psi}x^{t},Q_{\phi}\bar{u}^{t}\right\rangle=\left\langle\left(Q_{\phi}^{\top}Q_{\psi}\right)x^{t},\bar{u}^{t}\right\rangle$,
the competitor can be interpreted as transforming $x^{t}$ by using matrix
$Q_{\phi}^{\top}Q_{\psi}$, which we denote by $Q_{\psi,\phi}$. Hence, the set
of all possible transformations for the competitor is

$\mathcal{Q}^{\prime}=\left\\{Q_{\psi,\phi}\;\middle|\;\psi\colon\Theta_{i}\to\Theta_{i},\phi\colon\Theta_{i}\times
A_{i}\to A_{i}\right\\}.$

Next, we prove that $\mathcal{Q}$ equals the convex hull of
$\mathcal{Q}^{\prime}$. For each $\psi$ and $\phi$, by a simple calculation,
we can see that each entry is
$Q_{\psi,\phi}((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i}))=1$ if
$\theta^{\prime}_{i}=\psi(\theta_{i})$ and
$a_{i}=\phi(\theta_{i},a^{\prime}_{i})$, and $0$ otherwise. All the
constraints (6) for $\mathcal{Q}$ are satisfied by
$Q_{\psi,\phi}\in\mathcal{Q}$ for any $\psi$ and $\phi$. The convex hull is
therefore a subset of $\mathcal{Q}$.

Conversely, we show that any $Q\in\mathcal{Q}$ can be expressed as a convex
combination of $Q_{\psi,\phi}$. Fix any $Q\in\mathcal{Q}$. We can regard $Q$
as a block matrix with block
$Q_{\theta_{i},\theta^{\prime}_{i}}\in[0,1]^{A_{i}\times A_{i}}$ for each
$\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$. From the definition of
$\mathcal{Q}$, there exists some stochastic matrices
$W\in[0,1]^{\Theta_{i}\times\Theta_{i}}$ and
$\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}\in[0,1]^{A_{i}\times A_{i}}$ for
each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ such that
$Q_{\theta_{i},\theta^{\prime}_{i}}^{\top}=W(\theta_{i},\theta^{\prime}_{i})\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}$
for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$. Since any stochastic
matrix is a convex combination of zero-one stochastic matrices, there exists
some distribution $\gamma$ over all possible $\psi$ such that
$W=\sum_{\psi}\gamma(\psi)W_{\psi}$. Similarly, for each
$\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$, there exists some distribution
$\kappa_{\theta_{i},\theta^{\prime}_{i}}$ over all possible
$\phi(\theta_{i},\cdot)$ such that
$\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}=\sum_{\phi(\theta_{i},\cdot)}\kappa_{\theta_{i},\theta^{\prime}_{i}}(\phi(\theta_{i},\cdot))Q_{\phi(\theta_{i},\cdot)}$.
Each entry of $Q$ is

$\displaystyle Q((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i}))$
$\displaystyle=W(\theta_{i},\theta^{\prime}_{i})\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}(a^{\prime}_{i},a_{i})$
$\displaystyle=\left(\sum_{\psi}\gamma(\psi)W_{\psi}(\theta_{i},\theta^{\prime}_{i})\right)\left(\sum_{\phi(\theta_{i},\cdot)}\kappa_{\theta_{i},\theta^{\prime}_{i}}(\phi(\theta_{i},\cdot))Q_{\phi(\theta_{i},\cdot)}(a^{\prime}_{i},a_{i})\right)$
$\displaystyle=\left(\sum_{\psi}\gamma(\psi)\mathbf{1}_{\\{\theta^{\prime}_{i}=\psi(\theta_{i})\\}}\right)\left(\sum_{\phi(\theta_{i},\cdot)}\kappa_{\theta_{i},\theta^{\prime}_{i}}(\phi(\theta_{i},\cdot))\mathbf{1}_{\\{a_{i}=\phi(\theta_{i},a^{\prime}_{i})\\}}\right)$
$\displaystyle=\Pr_{\psi\sim\gamma}\left(\theta^{\prime}_{i}=\psi(\theta_{i})\right)\Pr_{\phi(\theta_{i},\cdot)\sim\kappa_{\theta_{i},\theta^{\prime}_{i}}}\left(a_{i}=\phi(\theta_{i},a^{\prime}_{i})\right).$

We consider a distribution that generates $\psi$ and $\phi$ with probability
$\gamma({\psi})\prod_{\theta_{i}\in\Theta_{i}}\kappa_{\theta_{i},\psi(\theta_{i})}(\phi(\theta_{i},\cdot))$.
That is, $\psi$ is generated from $\gamma$ and then each
$\phi(\theta_{i},\cdot)$ is generated from
$\kappa_{\theta_{i},\psi(\theta_{i})}$ independently for each
$\theta_{i}\in\Theta_{i}$. The expected value of each entry according to this
distribution is

$\displaystyle\mathop{\mathbb{E}}_{\psi,\phi}\left[Q_{\psi,\phi}((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i}))\right]$
$\displaystyle=\Pr_{\psi,\phi}\left(\theta^{\prime}_{i}=\psi(\theta_{i}),a_{i}=\phi(\theta_{i},a^{\prime}_{i})\right)$
$\displaystyle=\Pr_{\psi\sim\gamma}\left(\theta^{\prime}_{i}=\psi(\theta_{i})\right)\Pr_{\phi(\theta_{i},\cdot)\sim\kappa_{\theta_{i},\theta^{\prime}_{i}}}\left(a_{i}=\phi(\theta_{i},a^{\prime}_{i})\right)$
$\displaystyle=Q((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i})).$

Since every $Q\in\mathcal{Q}$ can be expressed as a convex combination of some
matrices in $\mathcal{Q}^{\prime}$, we can see that $\mathcal{Q}$ is a subset
of the convex hull of $\mathcal{Q}^{\prime}$. We conclude that $\mathcal{Q}$
equals the convex hull of $\mathcal{Q}^{\prime}$.

The competitor’s expected reward is

$\displaystyle\max_{\psi\colon\Theta_{i}\to\Theta_{i}}\max_{\phi\colon\Theta_{i}\times
A_{i}\to
A_{i}}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{a_{i}\sim\pi_{i}^{t}(\psi(\theta_{i}))}\left[u_{i}^{t}(\theta_{i},\phi(\theta_{i},a_{i}))\right]\right]$
$\displaystyle=\max_{\psi\colon\Theta_{i}\to\Theta_{i}}\max_{\phi\colon\Theta_{i}\times
A_{i}\to A_{i}}\sum_{t=1}^{T}\left\langle
Q_{\psi,\phi}x^{t},\bar{u}^{t}\right\rangle$
$\displaystyle=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Qx^{t},\bar{u}^{t}\rangle,$

where the last equality holds because $\langle Qx^{t},\bar{u}^{t}\rangle$ is
linear in terms of $Q$, and $\mathcal{Q}$ is the convex hull of
$Q_{\psi,\phi}$ for all $\psi$ and $\phi$. ∎

###  3.2 Reduction to online linear optimization

We apply the framework developed by Gordon et al. (2008) that reduces
$\Phi$-regret minimization to fixed point computation and online linear
optimization. First, we show that each $Q\in\mathcal{Q}$ has a fixed point in
$\mathcal{X}$.

######  Lemma 3.2.

For every $Q\in\mathcal{Q}$, there exists $x\in\mathcal{X}$ such that $Qx=x$.

###### Proof.

We prove this lemma by using Brouwer’s fixed point theorem, which claims that
any continuous function that maps a compact convex set to itself has a fixed
point. Since $\mathcal{X}$ is a product of probability simplices, it is
compact and convex. In addition, $Q$ is continuous since it is a matrix. Thus
it is sufficient to prove that $Q$ maps every $x\in\mathcal{X}$ to a vector in
$\mathcal{X}$. Let $x\in\mathcal{X}$ be an arbitrary vector. Let
$x_{\theta_{i}}$ be the block of $x$ corresponding to $\theta_{i}$ and
$Q_{\theta_{i},\theta^{\prime}_{i}}$ be the block of $Q$ corresponding to
$\theta_{i},\theta^{\prime}_{i}$. Then $x_{\theta_{i}}\in\Delta(A_{i})$ is a
stochastic vector for each $\theta_{i}\in\Theta_{i}$. From the definition of
$\mathcal{Q}$, there exists some stochastic matrices
$W\in[0,1]^{\Theta_{i}\times\Theta_{i}}$ and
$\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}\in[0,1]^{A_{i}\times A_{i}}$ for
each $\theta_{i},\theta^{\prime}_{i}$ such that
$Q_{\theta_{i},\theta^{\prime}_{i}}^{\top}=W(\theta_{i},\theta^{\prime}_{i})\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}$
for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$. Since
$\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}^{\top}x_{\theta^{\prime}_{i}}\in\Delta(A_{i})$
is also a stochastic vector, each block of $Qx$ corresponding to
$\theta_{i}\in\Theta_{i}$ is

$\sum_{\theta^{\prime}_{i}\in\Theta_{i}}Q_{\theta_{i},\theta^{\prime}_{i}}x_{\theta^{\prime}_{i}}=\sum_{\theta^{\prime}_{i}\in\Theta_{i}}W(\theta_{i},\theta^{\prime}_{i})\left(\tilde{Q}_{\theta_{i},\theta^{\prime}_{i}}^{\top}x_{\theta^{\prime}_{i}}\right).$

This is a convex sum of stochastic vectors, hence a stochastic vector in
$\Delta(A_{i})$. This implies $Qx\in\mathcal{X}$ for any $x\in\mathcal{X}$.
From Brouwer’s fixed point theorem, there exists a fixed point
$x\in\mathcal{X}$ such that $Qx=x$. ∎

Next, we show that this fixed point can be obtained by eigenvector
computation. As described later, all the subroutines are variants of the
multiplicative weights, and therefore, all entries of their outputs are
positive. We can assume that each entry of $Q^{t}$, which is computed as a
product of the subroutines’ outputs, is positive for every $t\in[T]$.

######  Lemma 3.3.

If all entries of $Q\in\mathcal{Q}$ are positive, then we can compute
$x\in\mathcal{X}$ such that $Qx=x$ in time polynomial in $|\Theta_{i}|$ and
$|A_{i}|$.

###### Proof.

We apply the Perron–Frobenius theorem, which claims that any positive matrix
has an eigenvalue whose eigenspace is $1$-dimensional, and any positive
eigenvector is an eigenvector corresponding to this eigenvalue. From Lemma
3.2, there exists some $x\in\mathcal{X}$ such that $Qx=x$, which implies that
$Q$ has eigenvector $1$, and $x$ is its corresponding eigenvector. Since $Q$
is a positive matrix and $x$ is a non-negative non-zero vector, $Qx=x$ is also
a positive vector. From the Perron–Frobenius thereom, the eigenspace
corresponding to eigenvalue $1$ is $1$-dimensional and contains only a
multiple of $x\in\mathcal{X}$. We can obtain $x\in\mathcal{X}$ by computing an
eigendecomposition of $Q$ and appropriately scaling the eigenvector
corresponding to eigenvalue $1$. Since $Q$ is a
$|\Theta_{i}||A_{i}|\times|\Theta_{i}||A_{i}|$ matrix, its eigendecomposition
can be computed in $O(|\Theta_{i}|^{\omega}|A_{i}|^{\omega})$ time, where
$\omega$ is the exponent of matrix multiplication. ∎

By using this fixed point computation, we can solve untruthful swap regret
minimization with a subroutine for online linear optimization with decision
space $\mathcal{Q}$. Let $Q^{t}\in\mathcal{Q}$ be the subroutine’s output in
round $t\in[T]$. Then compute a fixed point $x^{t}\in\mathcal{Q}$ that
satisfies $Q^{t}x^{t}=x^{t}$, and let $x^{t}$ be the decision for round $t$.
For the subroutine, feed reward $U^{t}\in[0,1]^{(\Theta_{i}\times
A_{i})\times(\Theta_{i}\times A_{i})}$ defined by
$U^{t}((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i}))=\bar{u}^{t}(\theta_{i},a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})$
for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ and
$a_{i},a^{\prime}_{i}\in A_{i}$. We define external regret for this subroutine
as

$R^{T}_{\mathcal{Q}}=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Q,U^{t}\rangle-\sum_{t=1}^{T}\langle Q^{t},U^{t}\rangle.$

Then we show that untruthful swap regret $R_{\mathsf{US},i}^{T}$ equals this
subroutine’s external regret $R^{T}_{\mathcal{Q}}$.

######  Lemma 3.4.

$R_{\mathsf{US},i}^{T}=R^{T}_{\mathcal{Q}}$.

###### Proof.

From the definition of $x^{t}$, it holds that $Q^{t}x^{t}=x^{t}$ for each
$t\in[T]$. From the definition of $U^{t}$, the algorithm’s expected reward is

$\displaystyle\sum_{t=1}^{T}\langle
Q^{t},U^{t}\rangle=\sum_{t=1}^{T}\left\langle
Q^{t},\bar{u}^{t}\left(x^{t}\right)^{\top}\right\rangle=\sum_{t=1}^{T}\left\langle
Q^{t}x^{t},\bar{u}^{t}\right\rangle=\sum_{t=1}^{T}\left\langle
x^{t},\bar{u}^{t}\right\rangle,$

where the last equality is due to $Q^{t}x^{t}=x^{t}$ for each $t\in[T]$.
Similarly, the competitor’s expected reward is

$\displaystyle\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Q,U^{t}\rangle=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\left\langle
Q,\bar{u}^{t}\left(x^{t}\right)^{\top}\right\rangle=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\left\langle
Qx^{t},\bar{u}^{t}\right\rangle.$

Therefore, we obtain

$\displaystyle R^{T}_{\mathcal{Q}}=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Q,U^{t}\rangle-\sum_{t=1}^{T}\langle
Q^{t},U^{t}\rangle=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Qx^{t},\bar{u}^{t}\rangle-\sum_{t=1}^{T}\langle
x^{t},\bar{u}^{t}\rangle=R_{\mathsf{US},i},$

where the last equality is due to Lemma 3.1. ∎

###  3.3 Decomposition into small external regret minimization problems

Next, we reduce online linear optimization with decision space $\mathcal{Q}$
to small external regret minimization problems. For each
$\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ and $a^{\prime}_{i}\in A_{i}$,
we use a subroutine
$\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$ with decision
space $A_{i}$. Moreover, for each $\theta_{i}\in\Theta_{i}$, we use a
subroutine $\mathcal{E}_{\theta_{i}}$ with decision space $\Theta_{i}$. In
total, we use $|A_{i}||\Theta_{i}|^{2}+|\Theta_{i}|$ subroutines.

The reduction proceeds as follows. Let
$y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}\in\Delta(A_{i})$ be the
output of $\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$ and
$w^{t}_{\theta_{i}}\in\Delta(\Theta_{i})$ the output of
$\mathcal{E}_{\theta_{i}}$ in round $t\in[T]$. According to these outputs, we
set
$Q^{t}((\theta_{i},a_{i}),(\theta^{\prime}_{i},a^{\prime}_{i}))=w^{t}_{\theta_{i}}(\theta^{\prime}_{i})y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})$
for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$ and
$a_{i},a^{\prime}_{i}\in A_{i}$. Note that this $Q^{t}$ is contained in
$\mathcal{Q}$, which can be checked by setting
$W(\theta_{i},\theta^{\prime}_{i})=w^{t}_{\theta_{i}}(\theta^{\prime}_{i})$
for each $\theta_{i},\theta^{\prime}_{i}\in\Theta_{i}$.

In each round $t\in[T]$, based on the observed reward
$U^{t}=\bar{u}^{t}(x^{t})^{\top}$, we feed the reward for each subroutine as
follows. For each
$\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$, the reward for
decision $a_{i}\in A_{i}$ is
$x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}_{i}^{t}(\theta_{i},a_{i})$.
The external regret $R_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}^{T}$
for $\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$ is defined
as

$R_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}^{T}=\max_{a^{*}_{i}\in
A_{i}}\sum_{t=1}^{T}x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a^{*}_{i})-\sum_{t=1}^{T}\sum_{a_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i}).$

For each $\mathcal{E}_{\theta_{i}}$, the reward for decision
$\theta^{\prime}_{i}\in\Theta_{i}$ is $\sum_{a_{i},a^{\prime}_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i})$.
The external regret $R_{\theta_{i}}^{T}$ for $\mathcal{E}_{\theta_{i}}$ is
defined as

$\displaystyle R_{\theta_{i}}^{T}$
$\displaystyle=\max_{\theta^{*}_{i}\in\Theta_{i}}\sum_{t=1}^{T}\sum_{a_{i},a^{\prime}_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{*}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{*}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i})$
$\displaystyle-\sum_{t=1}^{T}\sum_{\theta^{\prime}_{i}\in\Theta_{i}}w_{\theta_{i}}(\theta^{\prime}_{i})\sum_{a_{i},a^{\prime}_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i}).$

The external regret for online linear optimization with decision space
$\mathcal{Q}$ is bounded by the sum of the external regrets for these
subroutines as follows.

######  Lemma 3.5.

$R^{T}_{\mathcal{Q}}\leq\sum_{\theta_{i}\in\Theta_{i}}R^{T}_{\theta_{i}}+\sum_{\theta_{i}\in\Theta_{i}}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}.$

###### Proof.

Recall that $U^{t}=\bar{u}^{t}(x^{t})^{\top}$. Since each extreme point of
$\mathcal{Q}$ corresponds to a matrix $(Q_{\phi}^{\top}Q_{\psi})$ for some
$\psi$ and $\phi$, we obtain

$\displaystyle\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle Q,U^{t}\rangle$
$\displaystyle=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Qx^{t},\bar{u}^{t}\rangle$
$\displaystyle=\max_{\psi\colon\Theta_{i}\to\Theta_{i}}\max_{\phi\colon\Theta_{i}\times
A_{i}\to A_{i}}\sum_{t=1}^{T}\langle Q_{\psi}x^{t},Q_{\phi}\bar{u}^{t}\rangle$
$\displaystyle=\max_{\psi\colon\Theta_{i}\to\Theta_{i}}\max_{\phi\colon\Theta_{i}\times
A_{i}\to A_{i}}\sum_{\theta_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}\sum_{t=1}^{T}x^{t}(\psi(\theta_{i}),a^{\prime}_{i})\bar{u}^{t}(\theta_{i},\phi(\theta_{i},a^{\prime}_{i}))$
$\displaystyle=\sum_{\theta_{i}\in\Theta_{i}}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}\max_{a_{i}\in
A_{i}}\sum_{t=1}^{T}x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i})$
$\displaystyle=\sum_{\theta_{i}\in\Theta_{i}}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}\left\\{\sum_{t=1}^{T}\sum_{a_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i})+R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}\right\\}$
(due to the definition of
$R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$)
$\displaystyle\leq\sum_{\theta_{i}\in\Theta_{i}}\left\\{\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{t=1}^{T}\sum_{a^{\prime}_{i}\in
A_{i}}\sum_{a_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i})+\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}\right\\}$
$\displaystyle=\sum_{\theta_{i}\in\Theta_{i}}\left\\{\sum_{t=1}^{T}\sum_{\theta^{\prime}_{i}\in\Theta_{i}}w^{t}_{\theta_{i}}(\theta^{\prime}_{i})\sum_{a^{\prime}_{i}\in
A_{i}}\sum_{a_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i})+R^{T}_{\theta_{i}}+\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}\right\\}$ (due to
the definition of $R^{T}_{\theta_{i}}$) $\displaystyle=\sum_{t=1}^{T}\langle
Q^{t},U^{t}\rangle+\sum_{\theta_{i}\in\Theta_{i}}R^{T}_{\theta_{i}}+\sum_{\theta_{i}\in\Theta_{i}}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}},$ (due to the
definition of $Q^{t}$ and $U^{t}$)

which yields an upper bound on
$R^{T}_{\mathcal{Q}}=\max_{Q\in\mathcal{Q}}\sum_{t=1}^{T}\langle
Q,U^{t}\rangle-\sum_{t=1}^{T}\langle Q^{t},U^{t}\rangle$. ∎

To obtain an upper bound on untruthful swap regret, we use the following upper
bounds for external regret minimization. These algorithms are based on the
multiplicative weights, and their output is always a positive vector.

######  Theorem 3.6 ((Cesa-Bianchi and Lugosi, 2006, Theorem 2.2)).

For an online learning problem with rewards in $[0,1]$, there exists an
algorithm such that its external regret is bounded above by
$\sqrt{\frac{1}{2}T\log d}$, where $d$ is the number of possible decisions.

######  Theorem 3.7 ((Cesa-Bianchi et al., 1997, Theorem 4.6.3)).

For an online learning problem with rewards in $[0,1]$, there exists an
algorithm such that its external regret is bounded above by $6\sqrt{u^{*}\log
d}+2\log d$, where $d$ is the number of possible decisions and $u^{*}$ is the
sum of rewards for an optimal fixed decision over $T$ rounds.141414For
simplicity, the constants are not optimized. We can instead use an algorithm
with adaptive step size proposed by Auer et al. (2002).

These three-step reduction yields the algorithm described in Algorithm 3.
Finally, we obtain an upper bound on untruthful swap regret as follows.

######  Theorem 3.8.

The untruthful swap regret of Algorithm 3 is bounded as

$R_{\mathsf{US},i}^{T}\leq\sqrt{\frac{1}{2}T\log|\Theta_{i}|}+6\sqrt{T|A_{i}|\log|A_{i}|}+2|A_{i}|\log|A_{i}|.$

###### Proof.

From Lemmas 3.4 and 3.5, the untruthful swap regret of Algorithm 3 is bounded
as

$R_{\mathsf{US},i}^{T}=R^{T}_{\mathcal{Q}}\leq\sum_{\theta_{i}\in\Theta_{i}}R^{T}_{\theta_{i}}+\sum_{\theta_{i}\in\Theta_{i}}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}.$

Since the reward input to $\mathcal{E}_{\theta_{i}}$ is bounded above by

$\max_{t\in[T]}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a_{i},a^{\prime}_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}^{t}(\theta_{i},a_{i})\leq\max_{t\in[T]}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a_{i},a^{\prime}_{i}\in
A_{i}}y^{t}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}(a_{i})x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\rho_{i}(\theta_{i})=\rho_{i}(\theta_{i}),$

we can obtain the regret upper bound
$R^{T}_{\theta_{i}}\leq\rho_{i}(\theta_{i})\sqrt{\frac{1}{2}T\log|\Theta_{i}|}$
from Theorem 3.6. Since the reward input to
$\mathcal{E}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$ is similarly
bounded above by $\rho_{i}(\theta_{i})$ and the total reward for each
$a_{i}\in A_{i}$ is bounded above as

$\sum_{t=1}^{T}x^{t}(\theta^{\prime}_{i},a^{\prime}_{i})\bar{u}_{i}^{t}(\theta_{i},a_{i})\leq\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{\prime}_{i};a^{\prime}_{i})\rho_{i}(\theta_{i})=\rho_{i}(\theta_{i})\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{\prime}_{i};a^{\prime}_{i}),$

we can obtain a regret upper bound
$R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}=6\rho_{i}(\theta_{i})\sqrt{\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{\prime}_{i};a^{\prime}_{i})\log|A_{i}|}+2\rho_{i}(\theta_{i})\log|A_{i}|$.
By the Cauchy–Schwarz inequality, we have $\sum_{a^{\prime}_{i}\in
A_{i}}1\cdot\sqrt{\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{\prime}_{i};a^{\prime}_{i})}\leq\sqrt{|A_{i}|\sum_{a^{\prime}_{i}\in
A_{i}}\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{\prime}_{i};a^{\prime}_{i})}=\sqrt{|A_{i}|T}$.
We thus obtain

$\displaystyle\sum_{\theta_{i}\in\Theta_{i}}R^{T}_{\theta_{i}}+\sum_{\theta_{i}\in\Theta_{i}}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\sum_{a^{\prime}_{i}\in
A_{i}}R^{T}_{\theta_{i},\theta^{\prime}_{i},a^{\prime}_{i}}$
$\displaystyle\leq\sum_{\theta_{i}\in\Theta_{i}}\rho_{i}(\theta_{i})\sqrt{\frac{1}{2}T\log|\Theta_{i}|}+\sum_{\theta_{i}\in\Theta_{i}}\max_{\theta^{\prime}_{i}\in\Theta_{i}}\rho_{i}(\theta_{i})\left(6\sqrt{T|A_{i}|\log|A_{i}|}+2|A_{i}|\log|A_{i}|\right)$
$\displaystyle=\sqrt{\frac{1}{2}T\log|\Theta_{i}|}+6\sqrt{T|A_{i}|\log|A_{i}|}+2|A_{i}|\log|A_{i}|.\qed$

###  3.4 Application to equilibrium computation

Now we apply the algorithm for untruthful swap regret minimization to
equilibrium computation. Theorem 2.17 claims that if each player minimizes the
untruthful swap regret, then the dynamics converge to an approximate
communication equilibrium with strategy representability. However, exactly
simulating the dynamics requires the exact evaluation of rewards $u_{i}^{t}$,
which needs exponential time in general. Instead, we estimate these values by
random sampling and bound the error by using Hœffding’s inequality.

######  Corollary 3.9.

For any $\epsilon>0$, there exists an algorithm that outputs a succinct
representation of an $\epsilon$-approximate communication equilibrium with
strategy representability with probability at least $1-\delta$ and runs in
time polynomial in $n$, $\max_{i\in N}|\Theta_{i}|$, $\max_{i\in N}|A_{i}|$,
$1/\epsilon$, and $\log(1/\delta)$ with an oracle for utility functions.

###### Proof.

We estimate the value of $u_{i}^{t}(\theta_{i},a_{i})$ for each $i\in N$,
$t\in[T]$, $\theta_{i}\in\Theta_{i}$, and $a_{i}\in A_{i}$ by generating
$\frac{8}{\epsilon^{2}}\log\frac{2nT\max_{i\in N}|\Theta_{i}||A_{i}|}{\delta}$
samples of $\theta_{-i}\sim\rho|\theta_{i}$ and
$a_{-i}\sim\pi^{t}_{-i}(\theta_{-i})$ and taking the average of
$v_{i}(\theta_{i},\theta_{-i};a_{i},a_{-i})$, where $T$ will be set later. Let
$\tilde{u}_{i}^{t}(\theta_{i},a_{i})$ be this estimation. By using Hœffding’s
inequality, we have

$\displaystyle\Pr\left(\left|u_{i}^{t}(\theta_{i},a_{i})-\tilde{u}_{i}^{t}(\theta_{i},a_{i})\right|\geq\frac{\epsilon}{4}\right)$
$\displaystyle\leq
2\exp\left(-\frac{2\epsilon^{2}}{16}\cdot\frac{8}{\epsilon^{2}}\log\frac{2nT\max_{i\in
N}|\Theta_{i}||A_{i}|}{\delta}\right)$
$\displaystyle\leq\frac{\delta}{nT\max_{i\in N}(|\Theta_{i}||A_{i}|)}$

for each $i\in N$, $t\in[T]$, $\theta_{i}\in\Theta_{i}$, and $a_{i}\in A_{i}$.
By the union bound, with probability at least $1-\delta$, the additive errors
of all the rewards are at most $\epsilon/4$.

We apply Algorithm 3 to these estimated rewards. For each player $i\in N$, by
using the upper bound on untruthful swap regret in Theorem 3.8, we obtain

$\displaystyle\frac{R_{\mathsf{US},i}}{T}=\frac{1}{T}\max_{\psi\colon\Theta_{i}\to\Theta_{i}}\max_{\phi\colon\Theta_{i}\times
A_{i}\to
A_{i}}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{a_{i}\sim\pi_{i}^{t}(\psi(\theta_{i}))}\left[u_{i}^{t}(\theta_{i},\phi(\theta_{i},a_{i}))\right]-\mathop{\mathbb{E}}_{a_{i}\sim\pi_{i}^{t}(\theta_{i})}\left[u_{i}^{t}(\theta_{i},a_{i})\right]\right]$
$\displaystyle\leq\frac{1}{T}\left\\{\max_{\psi\colon\Theta_{i}\to\Theta_{i}}\max_{\phi\colon\Theta_{i}\times
A_{i}\to
A_{i}}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{a_{i}\sim\pi_{i}^{t}(\psi(\theta_{i}))}\left[\tilde{u}_{i}^{t}(\theta_{i},\phi(\theta_{i},a_{i}))\right]-\mathop{\mathbb{E}}_{a_{i}\sim\pi_{i}^{t}(\theta_{i})}\left[\tilde{u}_{i}^{t}(\theta_{i},a_{i})\right]\right]+T\cdot\frac{\epsilon}{2}\right\\}$
$\displaystyle\leq\sqrt{\frac{1}{2T}\log|\Theta_{i}|}+6\sqrt{\frac{|A_{i}|\log|A_{i}|}{T}}+\frac{2}{T}|A_{i}|\log|A_{i}|+\frac{\epsilon}{2}$
$\displaystyle\leq\epsilon,$

where we set $T=\max\\{\frac{18}{\epsilon^{2}}\log(\max_{i\in
N}|\Theta_{i}|),\frac{1296}{\epsilon^{2}}\max_{i\in N}|A_{i}|\log|A_{i}|\\}$.
From Theorem 2.17, $\pi$ is an $\epsilon$-approximate communication
equilibrium with strategy representability. ∎

##  4 Lower bound for untruthful swap regret

Here we show an $\Omega(\sqrt{T\log|\Theta_{i}|})$ lower bound on untruthful
swap regret. As in the previous section, this section focuses on an online
learning problem with stochastic types for a single player $i\in N$. The
subscript $i$ for $A_{i}$, $a_{i}$, $\Theta_{i}$, $\theta_{i}$, $\pi_{i}^{t}$,
and $R_{\mathsf{US},i}^{T}$ is not essential in this section, but we put it
for notational consistency.

Since a special case of our setting (the case of $|\Theta_{i}|=1$) is swap
regret minimization, an $\Omega(\sqrt{T|A_{i}|\log|A_{i}|})$ lower bound given
by Ito (2020) can be applied. Combining it with our lower bound, we can argue
that the leading term of our upper bound is tight up to a multiplicative
constant.

The main theorem of this section is stated as follows.

######  Theorem 4.1.

Assume $|A_{i}|=2$, $|\Theta_{i}|=2^{B+1}$ for some $B\in\mathbb{Z}$, and $T$
is a multiple of $B=\log_{2}|\Theta_{i}|-1$. If $T\geq
2^{-49}|\Theta_{i}|^{2}\log_{2}|\Theta_{i}|$, then for any randomized
algorithm, there exists an oblivious adversary for which the untruthful swap
regret of the algorithm is at least $2^{-28}\sqrt{T\log_{2}|\Theta_{i}|}$.

The assumption of $T=\Omega(|\Theta_{i}|^{2}\log|\Theta_{i}|)$ is essentially
used in the proofs. The other assumptions on $|A_{i}|$, $|\Theta_{i}|$, and
$T$ are just for simplicity of the proofs and only affect the multiplicative
constants.

We want to prove that for any randomized algorithm, there exists a
deterministic adversary for which the algorithm’s untruthful swap regret is
lower bounded. From Yao’s minimax principle, it is sufficient to show there
exists a randomized adversary for which any deterministic algorithm’s expected
untruthful swap regret is lower bounded. In the following, we construct such a
randomized adversary.

Let $A_{i}=\\{\alpha_{0},\alpha_{1}\\}$ be the set of actions and
$\rho_{i}\in\Delta(\Theta_{i})$ the uniform distribution over $\Theta_{i}$.
The set of time rounds $[T]$ is partitioned into $B$ blocks of equal length
$L=T/B$, where $B=\log_{2}|\Theta_{i}|-1$. For each $b\in[B]$, we denote the
$b$th block by $\mathcal{T}_{b}=\\{t\in[T]\mid(b-1)L<t\leq bL\\}$.

The set of types $\Theta_{i}$ is partitioned into $\Theta^{\prime}_{i}$ of
size $2^{B}$ and $\Theta^{\prime\prime}_{i}$ of size $2^{B}$. The rewards for
types $\Theta^{\prime}_{i}$ are determined by a bijection
$\zeta\colon\Theta^{\prime}_{i}\to\\{0,1\\}^{B}$ that associates each type in
$\theta^{\prime}_{i}\in\Theta^{\prime}_{i}$ with binary sequence
$\zeta(\theta^{\prime}_{i})$ of length $B$. A bijection $\zeta$ is latently
generated from the uniform distribution over all such bijections and unknown
to the algorithm in the beginning. For each time round $t\in\mathcal{T}_{b}$
in the $b$th block, the reward $u_{i}^{t}(\theta_{i},\alpha_{0})$ is defined
by $\zeta$ such that
$u_{i}^{t}(\theta^{\prime}_{i},\alpha_{0})=\zeta(\theta^{\prime}_{i})(b)$ for
each $\theta^{\prime}_{i}\in\Theta^{\prime}_{i}$. On the other hand, the
rewards for types $\Theta^{\prime\prime}_{i}$ are determined by a random map
$\xi\colon\Theta^{\prime\prime}_{i}\to\\{0,1\\}^{T}$. For each
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ and $t\in[T]$, the
reward
$u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha_{0})=\xi(\theta^{\prime\prime}_{i})(t)$
independently follows the uniform distribution over $\\{0,1\\}$. For both
$\Theta^{\prime}_{i}$ and $\Theta^{\prime\prime}_{i}$, the reward for
$\alpha_{1}$ is defined by flipping the reward for $\alpha_{0}$, i.e.,
$u_{i}^{t}(\theta_{i},\alpha_{1})=1-u_{i}^{t}(\theta_{i},\alpha_{0})$ for
every type $\theta_{i}\in\Theta_{i}$ and round $t\in[T]$. See Figure 2 for an
illustration.

Once $\zeta$ and $\xi$ are fixed, the problem instance is determined. Then,
since the algorithm is deterministic, the algorithm’s decisions
$(\pi_{i}^{t})_{t\in[T]}$ are also determined. Furthermore, since in each
round $t\in[T]$, the algorithm decides $\pi_{i}^{t}$ according to the rewards
observed so far, $\pi_{i}^{t}$ is deterministic if
$(\zeta(\theta^{\prime}_{i})(b))_{\theta^{\prime}_{i}\in\Theta^{\prime}_{i},b\in[\lceil(t-1)/L\rceil]}$
and
$(\xi(\theta^{\prime\prime}_{i})(t^{\prime}))_{\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i},t^{\prime}\in[t-1]}$
are fixed.

The untruthful swap regret $R_{\mathsf{US},i}^{T}$ depends on the problem
instance parametrized by $\zeta$ and $\xi$. We will develop an
$\Omega(\sqrt{T\log|\Theta_{i}|})$ lower bound on the expected value
$\mathop{\mathbb{E}}_{\zeta,\xi}\left[R_{\mathsf{US},i}^{T}\right]$. This
lower bound implies that there exists some $\zeta$ and $\xi$ such that
$R_{\mathsf{US},i}^{T}=\Omega(\sqrt{T\log|\Theta_{i}|})$, which leads to the
theorem.

###  4.1 Analysis for randomly branching rewards

The goal of this subsection is to prove that the algorithm with low untruthful
swap regret must make significantly different decisions for types
$\Theta^{\prime}_{i}$ (Lemma 4.4). Toward this goal, we first show that the
algorithm must select $\alpha_{0}$ or $\alpha_{1}$ for the type with all $0$
or all $1$ binary sequence, respectively (Lemma 4.2). We then show that the
algorithm must make significantly different decisions for “adjacent” types
(Lemma 4.3). By taking the expectation over $\zeta$ and $\xi$, we prove Lemma
4.4.

First, we prove that if the untruthful swap regret is small, for the type
$\theta^{0}_{i}\in\Theta^{\prime}_{i}$ with $\zeta(\theta^{0}_{i})=00\cdots
00$, the algorithm must choose $\alpha_{0}$ for most of the rounds. Similarly,
for the type $\theta^{1}_{i}\in\Theta^{\prime}_{i}$ with
$\zeta(\theta^{1}_{i})=11\cdots 11$, the algorithm must choose $\alpha_{1}$
for most of the rounds.

######  Lemma 4.2.

Fix $\zeta$ and $\xi$. For $\theta^{0}_{i}\in\Theta^{\prime}_{i}$ such that
$\zeta(\theta^{0}_{i})(b)=0$ for all $b\in[B]$, it must hold that
$\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{0}_{i};\alpha_{0})\geq
T-|\Theta_{i}|R_{\mathsf{US},i}^{T}$. For
$\theta^{1}_{i}\in\Theta^{\prime}_{i}$ such that $\zeta(\theta^{1}_{i})(b)=1$
for all $b\in[B]$, it must hold that
$\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{1}_{i};\alpha_{1})\geq
T-|\Theta_{i}|R_{\mathsf{US},i}^{T}$.

###### Proof.

Let $\theta^{0}_{i}\in\Theta^{\prime}_{i}$ be the type satisfying
$\zeta(\theta^{0}_{i})(b)=0$ for all $b\in[B]$. We consider $\psi$ and $\phi$
in the definition of untruthful swap regret such that
$\psi(\theta^{0}_{i})=\theta^{0}_{i}$ and
$\phi(\theta^{0}_{i},\alpha_{0})=\phi(\theta^{0}_{i},\alpha_{1})=\alpha_{0}$.
Let $\psi(\theta_{i})=\theta_{i}$ and $\phi(\theta_{i},\alpha)=\alpha$ for all
the other types $\theta_{i}\in\Theta_{i}$ and any action $\alpha\in A_{i}$. We
thus obtain

$\displaystyle R_{\mathsf{US},i}^{T}$
$\displaystyle=\max_{\psi\colon\Theta_{i}\to\Theta_{i}}\max_{\phi\colon\Theta_{i}\times
A_{i}\to
A_{i}}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\theta_{i}\sim\rho_{i}}\left[\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\psi(\theta_{i}))}\left[u_{i}^{t}(\theta,\phi(\theta_{i},\alpha))\right]-\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta_{i})}\left[u_{i}^{t}(\theta_{i},\alpha)\right]\right]$
$\displaystyle\geq\frac{1}{|\Theta_{i}|}\sum_{t=1}^{T}\left\\{u_{i}^{t}(\theta^{0}_{i},\alpha_{0})-\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{0}_{i})}\left[u_{i}^{t}(\theta^{0}_{i},\alpha)\right]\right\\}.$

Since $\zeta(\theta^{0}_{i})(b)=0$ for all $b\in[B]$, we have
$u_{i}^{t}(\theta^{0}_{i},\alpha_{0})=1$ for all $t\in[T]$, which implies

$R_{\mathsf{US},i}^{T}\geq\frac{1}{|\Theta_{i}|}\left\\{T-\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{0}_{i};\alpha_{0})\right\\}.$

Rearranging this inequality yields
$\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{0}_{i};\alpha_{0})\geq
T-|\Theta_{i}|R_{\mathsf{US},i}^{T}$. By applying the same argument to
$\theta^{1}_{i}\in\Theta^{\prime}_{i}$ such that $\zeta(\theta^{1}_{i})(b)=1$
for all $b\in[B]$, we obtain
$\sum_{t=1}^{T}\pi_{i}^{t}(\theta^{1}_{i};\alpha_{1})\geq
T-|\Theta_{i}|R_{\mathsf{US},i}^{T}$. ∎

Y1.0e0]pt$\nu_{\zeta}(\theta_{i},b_{1})$Y1.0e0]pt$\nu_{\zeta}(\theta_{i},b_{2})$Y1.0e0]pt$\theta_{i}=\nu_{\zeta}(\theta_{i},b_{3})=\nu_{\zeta}(\theta_{i},b^{\prime}_{4})$Y1.0e0]pt$\nu_{\zeta}(\theta_{i},b^{\prime}_{3})$Y1.0e0]pt$\nu_{\zeta}(\theta_{i},b^{\prime}_{2})$Y1.0e0]pt$\nu_{\zeta}(\theta_{i},b^{\prime}_{1})$111110100000111100111000110000$b^{\prime}_{1}$$b_{1}$$b^{\prime}_{2}$$b^{\prime}_{3}$$b_{2}$$\zeta(\cdot)$
Figure 4: An example of the definition of $\nu_{\zeta}$. Given
$\theta_{i}\in\Theta^{\prime}_{i}$, we denote the block indices corresponding
to $0$ and $1$ by $b_{1},b_{2},\dots,b_{B_{0}}$ and
$b^{\prime}_{1},b^{\prime}_{2},\dots,b^{\prime}_{B_{1}}$, respectively. We
define the series of types
$\nu_{\zeta}(\theta_{i},b_{1}),\nu_{\zeta}(\theta_{i},b_{2}),\dots,\nu_{\zeta}(\theta_{i},b_{B_{0}}),\nu_{\zeta}(\theta_{i},b_{B_{0}+1})=\theta_{i}$
such that their corresponding binary sequences gradually change from $11\cdots
11$ to $\zeta(\theta_{i})$. Similarly, we define the series of types
$\nu_{\zeta}(\theta_{i},b^{\prime}_{1}),\nu_{\zeta}(\theta_{i},b^{\prime}_{2}),\dots,\nu_{\zeta}(\theta_{i},b^{\prime}_{B_{1}}),\nu_{\zeta}(\theta_{i},b^{\prime}_{B_{1}+1})=\theta_{i}$
such that their corresponding binary sequences gradually change from $00\cdots
00$ to $\zeta(\theta_{i})$.

The previous lemma shows that for the type with $\zeta(\theta_{i})=00\cdots
00$ or $\zeta(\theta_{i})=11\cdots 11$, the algorithm must choose the optimal
action for most of the rounds. For the other types, we cannot prove a similar
claim since there exists a counterexample (see Section 1.2). However, we can
show that the algorithm must make sufficiently different decisions for some
pair of “adjacent” types.

Fix any $\theta_{i}\in\Theta^{\prime}_{i}$. To define the adjacency for
$\theta_{i}$, we define a sequence of types as follows (see Figure 4 for
example). Let $B_{0}$ and $B_{1}$ be the numbers of blocks $b\in[B]$ such that
$\zeta(\theta_{i})(b)=0$ and $\zeta(\theta_{i})(b)=1$, respectively. We define
the sorted indices $b_{1}\leq b_{2}\leq\dots\leq b_{B_{0}}$ of blocks such
that $\zeta(\theta_{i})(b_{k})=0$ for each $k\in[B_{0}]$. Similarly, we define
the sorted indices $b^{\prime}_{1}\leq b^{\prime}_{2}\leq\dots\leq
b^{\prime}_{B_{1}}$ of blocks such that $\zeta(\theta_{i})(b^{\prime}_{l})=1$
for each $l\in[B_{1}]$. For notational convenience, we define
$b_{0}=b^{\prime}_{0}=0$ and $b_{B_{0}+1}=b^{\prime}_{B_{1}+1}=B+1$.

For each $k=1,2,\dots,B_{0}+1$, we define the type
$\nu_{\zeta}(\theta_{i},b_{k})\in\Theta^{\prime}_{i}$ such that
$\zeta(\nu_{\zeta}(\theta_{i},b_{k}))$ is the binary sequence whose first
$b_{k-1}$ bits are identical to the prefix of $\zeta(\theta_{i})$ and the
remaining bits are all $1$, i.e.,
$\zeta(\nu_{\zeta}(\theta_{i},b_{k}))(b)=\zeta(\theta_{i})(b)$ for each $b\leq
b_{k-1}$ and $\zeta(\nu_{\zeta}(\theta_{i},b_{k}))(b)=1$ for each $b>b_{k-1}$.
Similarly, for each $l=1,2,\dots,B_{1}+1$, we define the type
$\nu_{\zeta}(\theta_{i},b^{\prime}_{l})\in\Theta^{\prime}_{i}$ such that
$\zeta(\nu_{\zeta}(\theta_{i},b^{\prime}_{l}))$ is the binary sequence whose
first $b^{\prime}_{l-1}$ bits are identical to the prefix of
$\zeta(\theta_{i})$ and the remaining bits are all $0$.

In the following lemma, we show that the algorithm must make significantly
different decisions for $\theta_{i}$ and $\nu_{\zeta}(\theta_{i},b)$ in each
block $b\in[B]$ if $R_{\mathsf{US},i}^{T}$ is small.

######  Lemma 4.3.

Fix $\zeta$ and $\xi$. Let $\theta_{i}\in\Theta^{\prime}_{i}$ be an arbitrary
type. Then it holds that

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})\right\\}+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b^{\prime}_{l});\alpha_{1})\right\\}\geq\frac{T}{2}-2|\Theta_{i}|R_{\mathsf{US},i}^{T}.$

###### Proof.

We consider $\psi$ in the definition of untruthful swap regret such that
$\psi(\nu(\theta_{i},b_{k+1}))=\nu(\theta_{i},b_{k})$ for each $k\in[B_{0}]$.
Let $\psi(\theta_{i})=\theta_{i}$ for all the other types
$\theta_{i}\in\Theta_{i}$. We use the identity map for actions, i.e.,
$\phi(\theta_{i},\alpha)=\alpha$ for all types $\theta_{i}\in\Theta_{i}$ and
actions $\alpha\in A_{i}$. Then we obtain a lower bound on the untruthful swap
regret as

$\displaystyle R_{\mathsf{US},i}^{T}$
$\displaystyle\geq\frac{1}{|\Theta_{i}|}\sum_{k=1}^{B_{0}}\sum_{t=1}^{T}\left\\{\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k}))}\left[u_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}),\alpha)\right]-\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}))}\left[u_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}),\alpha)\right]\right\\}.$
(7)

From the definition of $\nu_{\zeta}(\theta_{i},b_{k+1})$, the binary sequence
$\zeta(\nu_{\zeta}(\theta_{i},b_{k+1}))$ is identical to $\zeta(\theta_{i})$
for the first $b_{k}$ blocks and all $1$ for the remaining $B-b_{k}$ blocks.
This implies that $u_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}),\alpha_{0})=1$
for all blocks with indices $b_{1},b_{2},\dots,b_{k}$, and
$u_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}),\alpha_{1})=1$ for all blocks with
indices $b_{k+1},b_{k+2}\dots,b_{B_{0}}$ and
$b^{\prime}_{1},b^{\prime}_{2},\dots,b^{\prime}_{B_{1}}$. Each term on the
right-hand side of (7) for $k\in[B_{0}]$ can be decomposed as

$\displaystyle\sum_{t=1}^{T}\left\\{\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k}))}\left[u_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}),\alpha)\right]-\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}))}\left[u_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1}),\alpha)\right]\right\\}$
$\displaystyle=\underbrace{\sum_{k^{\prime}=1}^{k}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{0})\right\\}}_{(A)}$
$\displaystyle\quad+\underbrace{\sum_{k^{\prime}=k+1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{1})\right\\}}_{(B)}$
$\displaystyle\quad+\underbrace{\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{1})\right\\}}_{(C)}.$

We take the summation of these terms over all $k=1,\dots,B_{0}$. The sum of
(A) for all $k=1,\dots,B_{0}$ is

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{k^{\prime}=1}^{k}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{0})\right\\}$
$\displaystyle=\sum_{k^{\prime}=1}^{B_{0}}\sum_{k=k^{\prime}}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{0})\right\\}$
$\displaystyle=\sum_{k^{\prime}=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k^{\prime}});\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{B_{0}+1});\alpha_{0})\right\\},$

where the first equality is obtained by changing the order of summations and
the second equality is obtained by the telescoping sum. Similarly, the sum of
(B) for all $k=1,\dots,B_{0}$ is

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{k^{\prime}=k+1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{1})\right\\}$
$\displaystyle=\sum_{k^{\prime}=1}^{B_{0}}\sum_{k=1}^{k^{\prime}-1}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{1})\right\\}$
$\displaystyle=\sum_{k^{\prime}=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k^{\prime}}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k^{\prime}});\alpha_{1})\right\\}.$

By using the telescoping sum, the sum of (C) for all $k=1,\dots,B_{0}$ is

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k+1});\alpha_{1})\right\\}$
$\displaystyle=\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{B_{0}+1});\alpha_{1})\right\\}.$

By substituting these terms into (7), we obtain

$\displaystyle|\Theta_{i}|R_{\mathsf{US},i}^{T}\geq\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})-\pi_{i}^{t}(\theta_{i};\alpha_{0})+\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})\right\\}$
$\displaystyle+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})-\pi_{i}^{t}(\theta_{i};\alpha_{1})\right\\},$

where we used $\nu_{\zeta}(\theta_{i},b_{B_{0}+1})=\theta_{i}$. Recall
$\zeta(\nu_{\zeta}(\theta_{i},b_{1}))(b)=1$ for all $b\in[B]$. From Lemma 4.2,
we have

$\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})\geq
T-|\Theta_{i}|R_{\mathsf{US},i}^{T}.$

By summing these two inequalities and rearranging, we obtain

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})+\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})\right\\}+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\pi_{i}^{t}(\theta_{i};\alpha_{1})\geq
T-2|\Theta_{i}|R_{\mathsf{US},i}^{T},$

where we removed
$\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})$
and
$\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{1});\alpha_{1})$
from both sides. Finally, by using
$\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})+\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{1})=1$
for each $t\in[T]$, we obtain

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-2\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})+1\right\\}+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\pi_{i}^{t}(\theta_{i};\alpha_{1})$
$\displaystyle\geq T-2|\Theta_{i}|R_{\mathsf{US},i}^{T}.$

By using the symmetric analysis, we obtain

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\pi_{i}^{t}(\theta_{i};\alpha_{0})+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{1})-2\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b^{\prime}_{l});\alpha_{1})+1\right\\}\geq
T-2|\Theta_{i}|R_{\mathsf{US},i}^{T}.$

By summing these two inequalities, we obtain

$\displaystyle\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\left\\{2\pi_{i}^{t}(\theta_{i};\alpha_{0})-2\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})+1\right\\}+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{2\pi_{i}^{t}(\theta_{i};\alpha_{1})-2\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b^{\prime}_{l});\alpha_{1})+1\right\\}$
$\displaystyle\geq 2T-4|\Theta_{i}|R_{\mathsf{US},i}^{T}.$

Since
$\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}1+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}1=\sum_{t\in[T]}1=T$,
by dividing both sides by $2$, we complete the proof. ∎

The previous lemma claims that compared to the decisions for the adjacent type
$\nu_{\zeta}(\theta_{i},b)$, the algorithm must choose the optimal action for
type $\theta_{i}$ more frequently in each block $b\in[B]$. The next lemma
compares the algorithm’s decisions in block $b\in[B]$ for types whose binary
sequences first branch in block $b$, not only adjacent types.

For each $b\in[B]$ and a prefix $p\in\\{0,1\\}^{b-1}$, let $\mathcal{I}_{p,1}$
and $\mathcal{I}_{p,1}$ be the sets of types whose corresponding binary
sequences have the prefix $p$ and the next bit is $0$ or $1$, respectively.
Formally, we define
$\mathcal{I}_{p,0}=\\{\theta_{i}\in\Theta^{\prime}_{i}\mid\zeta(\theta_{i})(b^{\prime})=p(b^{\prime})~{}(\forall
b^{\prime}<b),~{}\zeta(\theta_{i})(b)=0\\}$ and
$\mathcal{I}_{p,1}=\\{\theta_{i}\in\Theta^{\prime}_{i}\mid\zeta(\theta_{i})(b^{\prime})=p(b^{\prime})~{}(\forall
b^{\prime}<b),~{}\zeta(\theta_{i})(b)=1\\}$. Note that $\mathcal{I}_{p,0}$ and
$\mathcal{I}_{p,1}$ are random variables determined by $\zeta_{b}$. Let
$\mathcal{I}_{p}=\mathcal{I}_{p,0}\cup\mathcal{I}_{p,1}$ be their union, which
is determined by $\zeta_{b-1}$.

In block $b$, the optimal action is $\alpha_{0}$ for types in
$\mathcal{I}_{p,0}$ and $\alpha_{1}$ for types in $\mathcal{I}_{p,1}$. In the
following lemma, we show that the average decisions for $\mathcal{I}_{p,0}$
and $\mathcal{I}_{p,1}$ are sufficiently different with some constant
probability.

######  Lemma 4.4.

Assume

$\mathop{\mathbb{E}}_{\zeta,\xi}\left[R_{\mathsf{US},i}^{T}\right]<2^{-28}\sqrt{T\log_{2}|\Theta_{i}|}.$

Then it holds that

$\displaystyle\Pr_{\begin{subarray}{c}b\sim[B],\zeta_{b},\xi_{b-1},\\\
p\sim\\{0,1\\}^{b-1}\end{subarray}}\left(\mathop{\mathbb{E}}_{\xi_{b}}\left[\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]\geq\frac{L}{8}\right)\geq\frac{1}{8}.$

###### Proof.

Since Lemma 4.3 holds for any $\theta_{i}\in\Theta^{\prime}_{i}$, it holds in
expectation for any distribution of $\theta_{i}$. In this proof, assuming that
$\theta_{i}$ follows the uniform distribution over $\Theta^{\prime}_{i}$, we
take the expectation of Lemma 4.3 with respect to $\zeta$, $\xi$, and
$\theta_{i}$.

The expected value of the right-hand side of Lemma 4.3 is bounded as

$\displaystyle\mathop{\mathbb{E}}_{\zeta,\xi,\theta_{i}}\left[\frac{T}{2}-2|\Theta_{i}|R_{\mathsf{US},i}^{T}\right]=\frac{T}{2}-2|\Theta_{i}|\mathop{\mathbb{E}}_{\zeta,\xi}\left[R_{\mathsf{US},i}^{T}\right]\geq\frac{T}{4},$
(8)

where the inequality is due to the assumptions
$\mathop{\mathbb{E}}_{\zeta,\xi}\left[R_{\mathsf{US},i}^{T}\right]<2^{-28}\sqrt{T\log_{2}|\Theta_{i}|}$
and $T\geq 2^{-49}|\Theta_{i}|^{2}\log_{2}|\Theta_{i}|$.

The expected value of the left-hand side of Lemma 4.3 can be decomposed for
each block as

$\displaystyle\mathop{\mathbb{E}}_{\zeta,\xi,\theta_{i}}\left[\sum_{k=1}^{B_{0}}\sum_{t\in\mathcal{T}_{b_{k}}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b_{k});\alpha_{0})\right\\}+\sum_{l=1}^{B_{1}}\sum_{t\in\mathcal{T}_{b^{\prime}_{l}}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{1})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b^{\prime}_{l});\alpha_{1})\right\\}\right]$
$\displaystyle=\sum_{b=1}^{B}\left\\{\Pr_{\zeta,\xi,\theta_{i}}(\zeta(\theta_{i})(b)=0)\mathop{\mathbb{E}}_{\zeta,\xi,\theta_{i}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b);\alpha_{0})\right\\}\;\middle|\;\zeta(\theta_{i})(b)=0\right]\right.$
$\displaystyle\qquad+\left.\Pr_{\zeta,\xi,\theta_{i}}(\zeta(\theta_{i})(b)=1)\mathop{\mathbb{E}}_{\zeta,\xi,\theta_{i}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b);\alpha_{0})-\pi_{i}^{t}(\theta_{i};\alpha_{0})\right\\}\;\middle|\;\zeta(\theta_{i})(b)=1\right]\right\\},$
(9)

where we used
$\pi_{i}^{t}(\theta_{i};\alpha_{0})+\pi_{i}^{t}(\theta_{i};\alpha_{1})=1$ and
$\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b);\alpha_{0})+\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b);\alpha_{1})=1$
for each $t\in[T]$. We take the expectation separately for each $b\in[B]$.

First, we take the expectation conditioned on observations from the first
block to the $b$th block. Let $\zeta_{b}$ and $\xi_{b}$ be the part of $\zeta$
and $\xi$ that is revealed until the end of block $b\in[B]$. Formally, we
define
$\zeta_{b}=(\zeta(\theta_{i})(b^{\prime}))_{\theta_{i}\in\Theta^{\prime}_{i},b^{\prime}\in[b]}$
and
$\xi_{b}=(\xi(\theta_{i})(t))_{\theta_{i}\in\Theta^{\prime\prime}_{i},t\in[bL]}$.
If we condition on $\zeta_{b}$ and $\xi_{b}$, the algorithm’s outputs
$(\pi_{i}^{t})_{t\in[bL]}$ until the end of block $b$ are deterministic.
Therefore, conditioned on $\zeta_{b}$, $\xi_{b}$, and $\theta_{i}$, only
$\nu_{\zeta}(\theta_{i},b)$ is stochastic in the term of which we take the
expectation in (9). Recall that $\nu_{\zeta}(\theta_{i},b)$ is defined to be
the type with the corresponding binary sequence equal to $\zeta(\theta_{i})$
before block $b-1$ and all $1$ (or $0$) after block $b$ if
$\zeta(\theta_{i})(b)$ is $0$ (or $1$, respectively). Let
$p\in\\{0,1\\}^{b-1}$ be a random variable that represents the prefix of
$\zeta(\theta_{i})$. Since $\zeta$ revealed after block $b$ is uniformly
distributed, if the $b$th bit $\zeta(\theta_{i})(b)$ is $0$, then
$\nu_{\zeta}(\theta_{i},b)$ is distributed uniformly over $\mathcal{I}_{p,1}$.
We thus obtain

$\displaystyle\mathop{\mathbb{E}}_{\zeta,\xi}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b);\alpha_{0})\right\\}\;\middle|\;\zeta_{b},\xi_{b}\right]=\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{0})\right]\right\\}.$
(10)

Next, we take the expectation over $\theta_{i}$ conditioned on $\zeta_{b}$ and
$\xi_{b}$. Since $\theta_{i}$ is uniformly distributed over
$\Theta^{\prime}_{i}$, the prefix $p$ follows the uniform distribution over
$\\{0,1\\}^{b-1}$. Then we obtain

$\displaystyle\mathop{\mathbb{E}}_{\theta_{i}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{0})\right]\right\\}\;\middle|\;\zeta(\theta_{i})(b)=0,\zeta_{b},\xi_{b}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{p\sim\\{0,1\\}^{b-1}}\left[\mathop{\mathbb{E}}_{\theta_{i}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{0})\right]\right\\}\;\middle|\;\zeta(\theta_{i})(b)=0,\text{$p$
is a prefix of $\zeta(\theta_{i})$},\zeta_{b},\xi_{b}\right]\right]$
$\displaystyle=\mathop{\mathbb{E}}_{p\sim\\{0,1\\}^{b-1}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\right\\}\right].$
(11)

Finally, we take the expectation over $\zeta_{b}$ and $\xi_{b}$, which
determine $\pi_{i}^{t}$ for each $t\in[bL]$ and the partition
$(\mathcal{I}_{p,0},\mathcal{I}_{p,1})$ for each $p\in\\{0,1\\}^{b-1}$. By
combining it with (10) and (11), we obtain

$\displaystyle\mathop{\mathbb{E}}_{\zeta,\xi,\theta_{i}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\theta_{i};\alpha_{0})-\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b);\alpha_{0})\right\\}\;\middle|\;\zeta(\theta_{i})(b)=0\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\zeta,\xi,p\sim\\{0,1\\}^{b-1}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\right\\}\right].$

By applying the same argument to the case of $\zeta(\theta_{i})(b)=1$, we
obtain

$\displaystyle\mathop{\mathbb{E}}_{\zeta,\xi,\theta_{i}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\pi_{i}^{t}(\nu_{\zeta}(\theta_{i},b);\alpha_{0})-\pi_{i}^{t}(\theta_{i};\alpha_{0})\right\\}\;\middle|\;\zeta(\theta_{i})(b)=1\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\zeta,\xi,p\sim\\{0,1\\}^{b-1}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\right\\}\right].$

By plugging these expected values into (9) and bounding it by the right-hand
side (8), we obtain

$\displaystyle\sum_{b\in[B]}\mathop{\mathbb{E}}_{\zeta,\xi,p\sim\\{0,1\\}^{b-1}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\right\\}\right]\geq\frac{T}{4}.$

By dividing both sides by $B$ and taking the conditional expectation, we
obtain

$\displaystyle\mathop{\mathbb{E}}_{b\sim[B],\zeta_{b},\xi_{b-1},p\sim\\{0,1\\}^{b-1}}\left[\mathop{\mathbb{E}}_{\zeta,\xi}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\right\\}\;\middle|\;\zeta_{b},\xi_{b-1}\right]\right]\geq\frac{L}{4}.$

Since $\mathcal{I}_{p,0}$, $\mathcal{I}_{p,1}$, and
$(\pi_{i}^{t})_{t\in\mathcal{T}_{b}}$ are determined only by $\zeta_{b}$ and
$\xi_{b}$, we can replace the expectation with respect to $\zeta$ and $\xi$ by
the expectation with respect to $\xi_{b}$. By applying Lemma 4.5 proved below,
we complete the proof. ∎

In this proof, we used the following lemma.

######  Lemma 4.5.

Fix $x,y\in\mathbb{R}$ such that $0<y<x$. Let $X$ be a random variable whose
value is at most $x$. If $\mathop{\mathbb{E}}[X]\geq y$, then $\Pr(X\geq
y/2)\geq\frac{y}{2x}$.

###### Proof.

By Markov’s inequality to $x-X$, for any $\epsilon>0$, we obtain

$\Pr\left(X\leq\frac{y}{2}+\epsilon\right)=\Pr\left(x-X\geq
x-\frac{y}{2}-\epsilon\right)\leq\frac{\mathop{\mathbb{E}}[x-X]}{x-\frac{y}{2}-\epsilon}\leq\frac{x-y}{x-\frac{y}{2}-\epsilon}=1-\frac{\frac{y}{2}-\epsilon}{x-\frac{y}{2}-\epsilon}$

By setting sufficiently small $\epsilon\in(0,\frac{y^{2}}{4x-2y})$, we obtain
$\Pr\left(X\leq\frac{y}{2}+\epsilon\right)\leq 1-\frac{y}{2x}$. By considering
the complementary event, we obtain $\Pr(X\geq
y/2)\geq\Pr(X>y/2+\epsilon)\geq\frac{y}{2x}$. ∎

###  4.2 Assignment of types

The goal of this subsection is to define an assignment
$\psi^{\prime}_{\zeta,\xi}\colon\Theta^{\prime\prime}_{i}\to\Theta^{\prime}_{i}$
such that against the reward sequence for each
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$, the decision for
$\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})\in\Theta^{\prime}_{i}$
achieves significantly better than $T/2$. In the previous subsection, we
showed that if the expected untruthful swap regret is small, the algorithm
must take decisions different for
$\mathcal{I}_{p,0}\subseteq\Theta^{\prime}_{i}$ and
$\mathcal{I}_{p,1}\subseteq\Theta^{\prime}_{i}$ with some constant probability
(Lemma 4.4). We consider assigning these decisions to the rewards for each
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$. Since these rewards
are determined by the independent random variables $\xi$, the total reward
obtained by any decision is $L/2$ in expectation for every block. Intuitively,
if the decisions for $\mathcal{I}_{p,0}$ and $\mathcal{I}_{p,1}$ are
sufficiently different, then the better one fits the rewards for
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$, thus achieving the
expected reward $L/2+\Omega(\sqrt{L})$ due to anti-concentration.

A simple but failed approach is to decide
$\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})$ independently for each
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$. For each $\zeta$ and
$\xi$, this approach iteratively selects $\mathcal{I}_{p,0}$ or
$\mathcal{I}_{p,1}$ whose average decision achieves better for the rewards of
$\theta^{\prime\prime}_{i}$ as follows. First, let $p$ be the empty sequence.
For each $b=1,2,\dots,B$, we assign $\theta^{\prime\prime}_{i}$ to $0$ if the
average decision for $\mathcal{I}_{p,0}$ is better than that for
$\mathcal{I}_{p,1}$ against the reward sequence of
$\theta^{\prime\prime}_{i}$, i.e.,

$\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]\geq\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]$

and $1$ otherwise, and we then add the selected $0$ or $1$ to the end of $p$.
Finally, we set
$\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})=\zeta^{-1}(p)$, where
$\zeta^{-1}\colon\\{0,1\\}^{B}\to\Theta^{\prime}_{i}$ is the inverse map of
the bijection $\zeta$. This assignment process is done for each
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ independently. This
approach has the following two issues.

  * •

Since the assignment is independent for each
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$, the assigned types
$(\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i}))_{\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}}$
might be unbalanced, that is, for some $\zeta_{b-1}$, $\xi_{b-1}$, and
$p\in\\{0,1\\}^{b-1}$, there is no
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ that is assigned to
$\mathcal{I}_{p,0}$ or $\mathcal{I}_{p,1}$ conditioned on $\zeta_{b-1}$ and
$\xi_{b-1}$. If the average decisions for $\mathcal{I}_{p,0}$ and
$\mathcal{I}_{p,1}$ are sufficiently different for all $p\in\\{0,1\\}^{b-1}$
with any $b\in[B]$, then this assignment is enough. However, Lemma 4.4
guarantees this condition only with a constant fraction of $p$ and $b$. If the
algorithm is manipulatively designed, this condition may fail to hold with a
significant probability for each $\zeta_{b-1}$, $\xi_{b-1}$, and $p$ that
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ is assigned to.

  * •

The assignment for each block is decided according to the average decisions
for $\mathcal{I}_{p,0}$ and $\mathcal{I}_{p,1}$. However, to obtain a lower
bound on the untruthful swap regret, we need to prove a lower bound for the
decision for $\psi_{\zeta,\xi}(\theta^{\prime\prime}_{i})$, not the average
decision for $\mathcal{I}_{p,0}$ or $\mathcal{I}_{p,1}$. The selection of
$\psi_{\zeta,\xi}(\theta^{\prime\prime}_{i})$ from $\mathcal{I}_{p,0}$ or
$\mathcal{I}_{p,1}$ depends on the assignment in the future blocks
$b,b+1,\dots,B$. If the algorithm is manipulatively designed, the distribution
of $\psi_{\zeta,\xi}(\theta^{\prime\prime}_{i})$ can be far from the uniform
distribution over $\mathcal{I}_{p,0}$ or $\mathcal{I}_{p,1}$.

To overcome these two obstacles, we use another definition of
$\psi^{\prime}_{\zeta,\xi}$. The assignment process for each $\zeta$ and $\xi$
proceeds as follows. Let $\mathcal{J}=\Theta^{\prime\prime}_{i}$, which is
supposed to be $\mathcal{J}_{p}$ with the empty sequence $p$. For each
$b=1,2,\dots,B$ and each $p\in\\{0,1\\}^{b-1}$, we partition $\mathcal{J}_{p}$
into two subsets $\mathcal{J}_{p,0}$ and $\mathcal{J}_{p,1}$ of equal size. To
decide this partition, we add an arbitrary index for each type in
$\mathcal{J}_{p}$ as $\mathcal{J}_{p}=\\{j_{1},j_{2},\dots,j_{2^{B-b+1}}\\}$.
For each $k\in[2^{B-b}]$, we add one of $\\{j_{2k-1},j_{2k}\\}$ into
$\mathcal{J}_{p,0}$ and the other into $\mathcal{J}_{p,1}$. Conditioned on
$\zeta_{b}$ and $\xi_{b-1}$, we consider the distribution of

$\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(j_{2k-1},\alpha)-u_{i}^{t}(j_{2k},\alpha)\right]\right]-\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(j_{2k-1},\alpha)-u_{i}^{t}(j_{2k},\alpha)\right]\right],$
(12)

whose randomness comes from the randomness of $\xi_{b}$. This value compares
the average decisions for $\mathcal{I}_{p,0}$ and $\mathcal{I}_{p,1}$ in terms
of the performance difference for the rewards of $j_{2k-1}$ and $j_{2k}$. For
the upper $50\%$ of this distribution, we set $j_{2k-1}\in\mathcal{J}_{p,0}$
and $j_{2k}\in\mathcal{J}_{p,1}$. For the lower $50\%$ of this distribution,
we set $j_{2k-1}\in\mathcal{J}_{p,1}$ and $j_{2k}\in\mathcal{J}_{p,0}$. Since
this is a discrete distribution, there might be arbitrariness in how to divide
the mass on the median, but any division is allowed. In the end of this
process, for each $p\in\\{0,1\\}^{B}$, the assigned type
$\mathcal{J}_{p}\subseteq\Theta^{\prime\prime}_{i}$ is a singleton. Recall
that $\mathcal{I}_{p}$ is also a singleton for each $p\in\\{0,1\\}^{B}$. For
each $p\in\\{0,1\\}^{B}$, we define
$\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})=\theta^{\prime}_{i}$,
where $\theta^{\prime}_{i}\in\mathcal{I}_{p}$ and
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p}$ are the unique element of
$\mathcal{I}_{p}$ and $\mathcal{J}_{p}$, respectively.

This assignment addresses the two issues described above as follows.

  * •

The first issue is caused when
$(\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i}))_{\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}}$
is unbalanced over $\Theta^{\prime}_{i}$. To avoid this issue, we consider all
types in $\Theta^{\prime\prime}_{i}$ at the same time and partition them into
equally sized subsets in each block. This guarantees that
$\psi^{\prime}_{\zeta,\xi}\colon\Theta^{\prime\prime}_{i}\to\Theta^{\prime}_{i}$
is always a bijection. Therefore, for any $b\in[B]$, $p\in\\{0,1\\}^{b-1}$,
$\zeta_{b-1}$, and $\xi_{b-1}$ such that the average decisions are
sufficiently different for $\mathcal{I}_{p,0}$ and $\mathcal{I}_{p,1}$, there
is some $\theta^{\prime\prime}_{i}$ assigned to it.

  * •

The second issue is addressed by assigning each type in $\mathcal{J}_{p}$ to
$\mathcal{J}_{p,0}$ and $\mathcal{J}_{p,1}$ with equal probability. Since this
partition applies recursively,
$\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})$ follows the uniform
distribution over $\mathcal{I}_{p}$. This is formally stated in the following
lemma.

######  Lemma 4.6.

Let $b\in[B]$ be an arbitrary block index. Let $\zeta_{b}$ and $\xi_{b}$ be
any realization of $\zeta$ and $\xi$ for the first $b$ blocks. Let
$p\in\\{0,1\\}^{b}$ be an arbitrary bit sequence of length $b$. For any pair
of $\theta^{\prime}_{i}\in\mathcal{I}_{p}$ and
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p}$, it holds that

$\Pr_{\zeta,\xi}\left(\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})=\theta^{\prime}_{i}\;\middle|\;\zeta_{b},\xi_{b}\right)=\frac{1}{2^{B-b}}.$

###### Proof.

Fix any $b\in[B]$, $\zeta_{b}$, $\xi_{b}$, $p\in\\{0,1\\}^{b}$,
$\theta^{\prime}_{i}\in\mathcal{I}_{p}$, and
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p}$. Let $\mathcal{F}_{b^{\prime}}$
be the event that $\theta^{\prime}_{i}$ and
$\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})$ are in the same
partition in the $b^{\prime}$th block. Formally, $\mathcal{F}_{b^{\prime}}$ is
the event that $\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}}$ and
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}$ hold for some
$p^{\prime}\in\\{0,1\\}^{b^{\prime}}$. By induction, we prove

$\Pr_{\zeta,\xi}\left(\mathcal{F}_{b^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right)=\frac{1}{2^{b^{\prime}-b}}$
(13)

for each $b^{\prime}\in[B]$ such that $b\leq b^{\prime}\leq B$.

For the case of $b^{\prime}=b$, since $\theta^{\prime}_{i}\in\mathcal{I}_{p}$
and $\theta^{\prime\prime}_{i}\in\mathcal{J}_{p}$, we obtain

$\Pr_{\zeta,\xi}\left(\mathcal{F}_{b}\;\middle|\;\zeta_{b},\xi_{b}\right)=1,$

which proves the base case.

Fix any $b^{\prime}\in[B]$ such that $b\leq b^{\prime}\leq B-1$. Assume (13)
holds for $b^{\prime}$. For any $p^{\prime}\in\\{0,1\\}^{b^{\prime}}$ that has
$p$ as a prefix, we have

$\displaystyle\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},0}\;\middle|\;\zeta_{b},\xi_{b}\right)$
$\displaystyle=\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right)$
$\displaystyle\times\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0}\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right)\Pr_{\zeta,\xi}\left(\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},0}\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right).$
(14)

Conditioned on $\zeta_{b^{\prime}}$ and $\xi_{b^{\prime}}$, whether
$\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0}$ or
$\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},1}$ holds is determined only by
the randomness of the $(b^{\prime}+1)$th block of $\zeta$. The second factor
of (14) is

$\displaystyle\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0}\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right)$
$\displaystyle=\mathop{\mathbb{E}}_{\zeta_{b^{\prime}},\xi_{b^{\prime}}}\left[\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0}\;\middle|\;\zeta_{b^{\prime}},\xi_{b^{\prime}},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right)\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\zeta_{b^{\prime}},\xi_{b^{\prime}}}\left[\frac{1}{2}\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right]$
$\displaystyle=\frac{1}{2}.$ (15)

Conditioned on $\zeta_{b^{\prime}+1}$ and $\xi_{b^{\prime}}$, whether
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},0}$ or
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},1}$ is determined only by
the randomness of $\xi_{b^{\prime}+1}$. Since we decide it according to
whether the realized $\xi_{b^{\prime}+1}$ is in the upper $50\%$ or lower
$50\%$ of the distribution of some random variable, the third factor of (14)
is

$\displaystyle\Pr_{\zeta,\xi}\left(\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},0}\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right)$
$\displaystyle=\mathop{\mathbb{E}}_{\zeta_{b^{\prime}+1},\xi_{b^{\prime}}}\left[\Pr_{\zeta,\xi}\left(\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},0}\;\middle|\;\zeta_{b^{\prime}+1},\xi_{b^{\prime}},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right)\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\zeta_{b^{\prime}+1},\xi_{b^{\prime}}}\left[\frac{1}{2}\;\middle|\;\zeta_{b},\xi_{b},\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\right]$
$\displaystyle=\frac{1}{2}.$ (16)

By plugging (15) and (16) into (14), we obtain

$\displaystyle\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},0}\;\middle|\;\zeta_{b},\xi_{b}\right)=\frac{1}{4}\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right).$

In the same way, we can obtain

$\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},1},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},1}\;\middle|\;\zeta_{b},\xi_{b}\right)=\frac{1}{4}\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right).$

Then the probability of $\mathcal{F}_{b^{\prime}+1}$ is

$\displaystyle\Pr_{\zeta,\xi}\left(\mathcal{F}_{b^{\prime}+1}\;\middle|\;\zeta_{b},\xi_{b}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}p^{\prime}\in\\{0,1\\}^{b^{\prime}+1}\end{subarray}}\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}p^{\prime}\in\\{0,1\\}^{b^{\prime}}\end{subarray}}\left\\{\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},0},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},0}\;\middle|\;\zeta_{b},\xi_{b}\right)+\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime},1},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime},1}\;\middle|\;\zeta_{b},\xi_{b}\right)\right\\}$
$\displaystyle=\sum_{\begin{subarray}{c}p^{\prime}\in\\{0,1\\}^{b^{\prime}}\end{subarray}}\left\\{\frac{1}{4}\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right)+\frac{1}{4}\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right)\right\\}$
$\displaystyle=\frac{1}{2}\sum_{\begin{subarray}{c}p^{\prime}\in\\{0,1\\}^{b^{\prime}}\end{subarray}}\Pr_{\zeta,\xi}\left(\theta^{\prime}_{i}\in\mathcal{I}_{p^{\prime}},\theta^{\prime\prime}_{i}\in\mathcal{J}_{p^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right)$
$\displaystyle=\frac{1}{2}\Pr_{\zeta,\xi}\left(\mathcal{F}_{b^{\prime}}\;\middle|\;\zeta_{b},\xi_{b}\right)$
$\displaystyle=\frac{1}{2}\cdot\frac{1}{2^{b^{\prime}-b}}$ (from the induction
hypothesis) $\displaystyle=\frac{1}{2^{b^{\prime}-b+1}},$

which proves the induction step.

By induction, (13) holds for each $b\leq b^{\prime}\leq B$. By considering the
case of $b^{\prime}=B$, we obtain

$\Pr_{\zeta,\xi}\left(\mathcal{F}_{B}\;\middle|\;\zeta_{b},\xi_{b}\right)=\frac{1}{2^{B-b}}.$

From the definition of $\psi^{\prime}_{\zeta,\xi}$, the event
$\mathcal{F}_{B}$ implies
$\psi^{\prime}_{\zeta,\xi}(\theta^{\prime\prime}_{i})=\theta^{\prime}_{i}$,
which completes the proof. ∎

###  4.3 Analysis of the expected reward in each block

In Section 4.1, we showed that the average decisions for $\mathcal{I}_{p,0}$
and $\mathcal{I}_{p,1}$ are sufficiently different with a constant
probability. In Section 4.2, we defined the assignment
$\psi^{\prime}_{\zeta,\xi}\colon\Theta^{\prime\prime}_{i}\to\Theta^{\prime}_{i}$
such that $\mathcal{J}_{p,0}$ and $\mathcal{J}_{p,1}$ correspond to
$\mathcal{I}_{p,0}$ and $\mathcal{I}_{p,1}$ in each block, respectively. The
next lemma claims that if the average decisions for $\mathcal{I}_{p,0}$ and
$\mathcal{I}_{p,1}$ are sufficiently different, the average decisions for
$\mathcal{I}_{p,0}$ and $\mathcal{I}_{p,1}$ achieve $L/2+\Omega(\sqrt{L})$ for
the rewards of $\mathcal{J}_{p,0}$ and $\mathcal{J}_{p,1}$, respectively.

The proof proceeds in the following steps. First, by introducing variables
$Y_{\theta^{\prime\prime}_{i}}^{t}$ and $Z_{\theta^{\prime\prime}_{i}}^{t}$
for each $\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ and
$t\in\mathcal{T}_{b}$, we express the expected value achieved by the
assignment as (18). The first term of (18) is equal to $L/2$ as shown in (19).
The remaining term of (18) can be written as a random walk term
$D_{k}^{t_{\mathrm{max}}}$ with a sign $h_{k}(\xi_{b})$ as shown in (21). To
bound it by a term without $h_{k}(\xi_{b})$, we define a more tractable
$h^{\prime}_{k}(\xi_{b})$ and obtain (22). We bound (22) by using Doob’s
optional stopping theorem. Combining all these inequalities, we prove the
following lemma.

######  Lemma 4.7.

Let $b\in[B]$ be an arbitrary block index. Let $\zeta_{b}$ be any partial
realization of $\zeta$ revealed until the end of the $b$th block. Let
$\xi_{b-1}$ be any partial realization of $\xi$ revealed until the end of the
$(b-1)$th block. Let $p\in\\{0,1\\}^{b-1}$ be an arbitrary bit sequence of
length $b-1$. Let $c\in[0,1]$ be an arbitrary non-negative constant. If

$\mathop{\mathbb{E}}_{\xi_{b}}\left[\sum_{t\in\mathcal{T}_{b}}\left|\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\right|\;\middle|\;\zeta_{b},\xi_{b-1}\right]\geq
cL,$

then

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[\frac{1}{2}\mathop{\mathbb{E}}_{\begin{subarray}{c}\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}\\\
\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,0}\end{subarray}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\begin{subarray}{c}\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}\\\
\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,1}\end{subarray}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle\geq\frac{L}{2}+2^{-10}c^{9/2}\sqrt{L}.$ (17)

###### Proof.

Fix $b\in[B]$ and $p\in\\{0,1\\}^{b-1}$. We define random variables

$X_{0}^{t}=\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{0})\right]\qquad\text{and}\qquad
X_{1}^{t}=\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{0})\right]$

that represent the average decisions for $\mathcal{I}_{p,0}$ and
$\mathcal{I}_{p,1}$ for each $t\in\mathcal{T}_{b}$. Note that they are
deterministic if $\zeta_{b}$ and $\xi_{b}$ are fixed. If we apply the average
decision for $\mathcal{I}_{p,0}$ to the rewards for each
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p}$, the expected total reward in
round $t\in\mathcal{T}_{b}$ is

$\displaystyle\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{0})u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha_{0})+\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{1})u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha_{1})\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{0})\right]u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha_{0})+\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta^{\prime}_{i};\alpha_{1})\right]u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha_{1})$
$\displaystyle=X_{0}^{t}\xi(\theta^{\prime\prime}_{i})(t)+(1-X_{0}^{t})(1-\xi(\theta^{\prime\prime}_{i})(t)).$

Similarly, if we apply the average decision for $\mathcal{I}_{p,1}$, the
expected total reward is

$\displaystyle\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]=X_{1}^{t}\xi(\theta^{\prime\prime}_{i})(t)+(1-X_{1}^{t})(1-\xi(\theta^{\prime\prime}_{i})(t)).$

For each $\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ and
$t\in\mathcal{T}_{b}$, we define random variables

$Y_{\theta^{\prime\prime}_{i}}^{t}=\frac{X_{0}^{t}+X_{1}^{t}}{2}\xi(\theta^{\prime\prime}_{i})(t)+\left(1-\frac{X_{0}^{t}+X_{1}^{t}}{2}\right)(1-\xi(\theta^{\prime\prime}_{i})(t))$

and

$Z_{\theta^{\prime\prime}_{i}}^{t}=\frac{X_{0}^{t}-X_{1}^{t}}{2}\xi(\theta^{\prime\prime}_{i})(t)-\frac{X_{0}^{t}-X_{1}^{t}}{2}(1-\xi(\theta^{\prime\prime}_{i})(t)),$

which are determined by $\zeta_{b}$ and $\xi_{b}$. The total reward of the
average decisions for $\mathcal{I}_{p,0}$ in block $b$ is

$\displaystyle\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]$
$\displaystyle=\sum_{t\in\mathcal{T}_{b}}\left\\{X^{t}_{0}\xi(\theta^{\prime\prime}_{i})(t)+(1-X^{t}_{0})(1-\xi(\theta^{\prime\prime}_{i})(t))\right\\}$
$\displaystyle=\sum_{t\in\mathcal{T}_{b}}(Y_{\theta^{\prime\prime}_{i}}^{t}+Z_{\theta^{\prime\prime}_{i}}^{t}).$

Similarly, the total reward of the average decisions for $\mathcal{I}_{p,1}$
is

$\displaystyle\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]$
$\displaystyle=\sum_{t\in\mathcal{T}_{b}}\left\\{X_{1}^{t}\xi(\theta^{\prime\prime}_{i})(t)+(1-X_{1}^{t})(1-\xi(\theta^{\prime\prime}_{i})(t))\right\\}$
$\displaystyle=\sum_{t\in\mathcal{T}_{b}}(Y_{\theta^{\prime\prime}_{i}}^{t}-Z_{\theta^{\prime\prime}_{i}}^{t}).$

The left-hand side of the inequality (17) is

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[\frac{1}{2}\mathop{\mathbb{E}}_{\begin{subarray}{c}\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}\\\
\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,0}\end{subarray}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\begin{subarray}{c}\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}\\\
\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,1}\end{subarray}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}(Y_{\theta^{\prime\prime}_{i}}^{t}+Z_{\theta^{\prime\prime}_{i}}^{t})\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}(Y_{\theta^{\prime\prime}_{i}}^{t}-Z_{\theta^{\prime\prime}_{i}}^{t})\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p}}\left[\sum_{t\in\mathcal{T}_{b}}Y_{\theta^{\prime\prime}_{i}}^{t}\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}Z_{\theta^{\prime\prime}_{i}}^{t}\right]-\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}Z_{\theta^{\prime\prime}_{i}}^{t}\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right],$
(18)

where the second equality is due to
$\mathcal{J}_{p}=\mathcal{J}_{p,0}\cup\mathcal{J}_{p,1}$.

The first term of (18) is

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p}}\left[\sum_{t\in\mathcal{T}_{b}}Y_{\theta^{\prime\prime}_{i}}^{t}\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\frac{X_{0}^{t}+X_{1}^{t}}{2}\xi(\theta^{\prime\prime}_{i})(t)+\left(1-\frac{X_{0}^{t}+X_{1}^{t}}{2}\right)(1-\xi(\theta^{\prime\prime}_{i})(t))\right\\}\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\xi_{b}}\left[\frac{X_{0}^{t}+X_{1}^{t}}{2}\xi(\theta^{\prime\prime}_{i})(t)+\left(1-\frac{X_{0}^{t}+X_{1}^{t}}{2}\right)(1-\xi(\theta^{\prime\prime}_{i})(t))\;\middle|\;\zeta_{b},\xi_{b-1}\right]\right].$

Here we note that $\mathcal{J}_{p}$ is determined by $\zeta_{b-1}$ and
$\xi_{b-1}$. Since $X_{0}^{t}$ and $X_{1}^{t}$ are determined by the algorithm
before $\xi(\theta^{\prime\prime}_{i})(t)$ is revealed,
$\frac{X_{0}^{t}+X_{1}^{t}}{2}$ and $\xi(\theta^{\prime\prime}_{i})(t)$ are
independent. Then we can take the expectation of
$\frac{X_{0}^{t}+X_{1}^{t}}{2}$ and $\xi(\theta^{\prime\prime}_{i})(t)$
separately. It is also the case for $1-\frac{X_{0}^{t}+X_{1}^{t}}{2}$ and
$1-\xi(\theta^{\prime\prime}_{i})(t)$. Since each entry of $\xi$ follows the
uniform distribution over $\\{0,1\\}$ independently,
$\mathop{\mathbb{E}}_{\xi_{b}}\left[\xi(\theta^{\prime\prime}_{i})(t)\;\middle|\;\zeta_{b},\xi_{b-1}\right]=\mathop{\mathbb{E}}_{\xi_{b}}\left[1-\xi(\theta^{\prime\prime}_{i})(t)\;\middle|\;\zeta_{b},\xi_{b-1}\right]=1/2$.
We thus obtain

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p}}\left[\sum_{t\in\mathcal{T}_{b}}Y_{\theta^{\prime\prime}_{i}}^{t}\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p}}\left[\sum_{t\in\mathcal{T}_{b}}\left\\{\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[\frac{X_{0}^{t}+X_{1}^{t}}{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[1-\frac{X_{0}^{t}+X_{1}^{t}}{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]\right\\}\right]$
$\displaystyle=\frac{|\mathcal{T}_{b}|}{2}$ $\displaystyle=\frac{L}{2}.$ (19)

Next, we give a lower bound on the second and third terms of (18). Since
$Z_{\theta^{\prime\prime}_{i}}^{t}$ can be expressed as

$Z_{\theta^{\prime\prime}_{i}}^{t}=\frac{X_{0}^{t}-X_{1}^{t}}{2}\xi(\theta^{\prime\prime}_{i})(t)-\frac{X_{0}^{t}-X_{1}^{t}}{2}(1-\xi(\theta^{\prime\prime}_{i})(t))=\begin{cases}\frac{X_{0}^{t}-X_{1}^{t}}{2}&\text{if
$\xi(\theta^{\prime\prime}_{i})(t)=1$}\\\
-\frac{X_{0}^{t}-X_{1}^{t}}{2}&\text{if
$\xi(\theta^{\prime\prime}_{i})(t)=0$},\end{cases}$

the cumulative sum $\left(\sum_{t^{\prime}\in\mathcal{T}_{b}\colon
t^{\prime}\leq
t}Z_{\theta^{\prime\prime}_{i}}^{t^{\prime}}\right)_{t\in\mathcal{T}_{b}}$ can
be regarded as a random walk with varying step size
$\left|\frac{X_{0}^{t}-X_{1}^{t}}{2}\right|$ for each
$\theta^{\prime\prime}_{i}\in\mathcal{J}_{p}$. The step size in round
$t\in\mathcal{T}_{b}$ is determined by the algorithm that has not observed
$\xi(\theta^{\prime\prime}_{i})(t)$ for any
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ yet. Since
$X_{0}^{t}\in[0,1]$ and $X_{1}^{t}\in[0,1]$, the step size is bounded as
$\left|\frac{X_{0}^{t}-X_{1}^{t}}{2}\right|\in\left[0,\frac{1}{2}\right]$ for
each $t\in\mathcal{T}_{b}$.

Recall that how to partition $\\{j_{2k-1},j_{2k}\\}$ into $\mathcal{J}_{p,0}$
and $\mathcal{J}_{p,1}$ is determined independently for each $k\in[2^{B-b}]$.
This is decided by the value of (12), which can be expressed as

$\displaystyle\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(j_{2k-1},\alpha)-u_{i}^{t}(j_{2k},\alpha)\right]\right]-\mathop{\mathbb{E}}_{\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(j_{2k-1},\alpha)-u_{i}^{t}(j_{2k},\alpha)\right]\right]$
$\displaystyle=\left\\{\sum_{t\in\mathcal{T}_{b}}\left(Y_{j_{2k-1}}^{t}+Z_{j_{2k-1}}^{t}\right)-\sum_{t\in\mathcal{T}_{b}}\left(Y_{j_{2k}}^{t}+Z_{j_{2k}}^{t}\right)\right\\}-\left\\{\sum_{t\in\mathcal{T}_{b}}\left(Y_{j_{2k-1}}^{t}-Z_{j_{2k-1}}^{t}\right)-\sum_{t\in\mathcal{T}_{b}}\left(Y_{j_{2k}}^{t}-Z_{j_{2k}}^{t}\right)\right\\}$
$\displaystyle=2\sum_{t\in\mathcal{T}_{b}}\left(Z_{j_{2k-1}}^{t}-Z_{j_{2k}}^{t}\right).$

By considering the distribution of this value conditioned on $\zeta_{b}$ and
$\xi_{b-1}$, we set $j_{2k-1}\in\mathcal{J}_{p,0}$ for the upper half of this
distribution and $j_{2k-1}\in\mathcal{J}_{p,1}$ for the lower half. We define
the function $h_{k}$ such that $h_{k}(\xi_{b})=1$ if
$j_{2k-1}\in\mathcal{J}_{p,0}$ and $h_{k}(\xi_{b})=-1$ if
$j_{2k-1}\in\mathcal{J}_{p,1}$. Note that $h_{k}(\xi_{b})$ might be random on
the median of the distribution.

Let $D_{k}^{t}=\sum_{t^{\prime}\in\mathcal{T}_{b}\colon t^{\prime}\leq
t}\left(Z_{j_{2k-1}}^{t^{\prime}}-Z_{j_{2k}}^{t^{\prime}}\right)$ be half of
the cumulative sum of this value until round $t$. From the definition of
$Z_{\theta^{\prime\prime}_{i}}^{t}$, we have

$D_{k}^{t}=\begin{cases}D_{k}^{t-1}&\text{with probability $1/2$ (if
$\xi(j_{2k-1})(t)=\xi(j_{2k})(t)$)}\\\
D_{k}^{t-1}+(X_{0}^{t}-X_{1}^{t})&\text{with probability $1/4$ (if
$\xi(j_{2k-1})(t)=1$ and $\xi(j_{2k})(t)=0$)}\\\
D_{k}^{t-1}-(X_{0}^{t}-X_{1}^{t})&\text{with probability $1/4$ (if
$\xi(j_{2k-1})(t)=0$ and $\xi(j_{2k})(t)=1$)},\end{cases}$ (20)

where $X_{0}^{t}-X_{1}^{t}$ is determined by the algorithm that has not
observed $\xi(j_{2k-1})(t)$ and $\xi(j_{2k})(t)$ yet.

The second and third terms of (18) are expressed as

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}Z_{\theta^{\prime\prime}_{i}}^{t}\right]-\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}Z_{\theta^{\prime\prime}_{i}}^{t}\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\frac{1}{2^{B-b}}\sum_{k=1}^{2^{B-b}}\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})\left\\{\sum_{t\in\mathcal{T}_{b}}Z_{j_{2k-1}}^{t}-\sum_{t\in\mathcal{T}_{b}}Z_{j_{2k}}^{t}\right\\}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\frac{1}{2^{B-b+1}}\sum_{k=1}^{2^{B-b}}\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right],$
(21)

where ${t_{\mathrm{max}}}=\max\mathcal{T}_{b}$ is the index of the last round
in block $b$.

In the remaining part of the proof, we fix $k\in[2^{B-b}]$. Let $\mathcal{F}$
be the event that $\left|D_{k}^{t}\right|>\frac{\sqrt{c^{3}L}}{4}$ for some
$t\in\mathcal{T}_{b}$. Let $\mathcal{F}_{+}$ be the event that
$D_{k}^{t}>\frac{\sqrt{c^{3}L}}{4}$ for some $t\in\mathcal{T}_{b}$ and
$\mathcal{F}_{-}$ the event that $D_{k}^{t}<\frac{\sqrt{c^{3}L}}{4}$ for some
$t\in\mathcal{T}_{b}$. Since
$\Pr_{\xi_{b}}(\mathcal{F}\mid\zeta_{b},\xi_{b-1})\leq\Pr_{\xi_{b}}(\mathcal{F}_{+}\mid\zeta_{b},\xi_{b-1})+\Pr_{\xi_{b}}(\mathcal{F}_{-}\mid\zeta_{b},\xi_{b-1})$,
one of $\mathcal{F}_{+}$ or $\mathcal{F}_{-}$ happens with probability at
least $\Pr_{\xi_{b}}(\mathcal{F}\mid\zeta_{b},\xi_{b-1})/2$. Assume
$\Pr_{\xi_{b}}(\mathcal{F}_{+}\mid\zeta_{b},\xi_{b-1})\geq\Pr_{\xi_{b}}(\mathcal{F}\mid\zeta_{b},\xi_{b-1})/2$
without loss of generality. For the case of
$\Pr_{\xi_{b}}(\mathcal{F}_{-}\mid\zeta_{b},\xi_{b-1})\geq\Pr_{\xi_{b}}(\mathcal{F}\mid\zeta_{b},\xi_{b-1})/2$,
we can prove the statement in the same way.

We define $h^{\prime}_{k}$ as follows.

  * •

First, we consider the case of $\Pr(\mathcal{F}_{+})\geq 0.5$. In this case,
we set $h^{\prime}_{k}(\xi_{b})=1$ for the upper part of
$0.5/\Pr(\mathcal{F}_{+})$ on the distribution of $D_{k}^{t_{\mathrm{max}}}$
conditioned on $\zeta_{b}$, $\xi_{b-1}$, and $\mathcal{F}_{+}$. We set
$h^{\prime}_{k}(\xi_{b})=-1$ for the remaining part of $\mathcal{F}_{+}$ and
the complementary event $\mathcal{F}_{+}^{c}$.

  * •

Next, we consider the case of $\Pr(\mathcal{F}_{+})<0.5$. If $\mathcal{F}_{+}$
holds, we set $h^{\prime}_{k}(\xi_{k})=1$. If $\mathcal{F}_{+}$ does not hold,
we decide $h^{\prime}_{k}(\xi_{k})=1$ or $h^{\prime}_{k}(\xi_{k})=-1$ by
considering the distribution of $D_{k}^{t_{\mathrm{max}}}$. For the upper part
of probability $(0.5-\Pr(\mathcal{F}_{+}))/(1-\Pr(\mathcal{F}_{+}))$ on the
distribution of $D_{k}^{t_{\mathrm{max}}}$ conditioned on
$\mathcal{F}_{+}^{c}$, we set $h^{\prime}_{k}(\xi_{b})=1$. For the lower part
of probability $0.5/(1-\Pr(\mathcal{F}_{+}))$, we set
$h^{\prime}_{k}(\xi_{b})=-1$.

In both cases, the mass on the boundary can be arbitrarily partitioned so that
the above constraint is satisfied. Note that $h^{\prime}_{k}$ satisfies the
constraint
$\Pr_{\xi_{b}}(h^{\prime}_{k}(\xi_{b})=1\mid\zeta_{b},\xi_{b-1})=0.5$. Since
$h_{k}$ maximizes
$\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
under this constraint, we have

$\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]\geq\mathop{\mathbb{E}}_{\xi_{b}}\left[h^{\prime}_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right].$

In the following, we prove a lower bound

$\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]\geq\frac{1}{2}\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
(22)

on each term of (21). Since $D_{k}^{t}$ is a random walk specified as (20), it
is a martingale. Therefore,
$\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]=0$.
From the optimality of $h_{k}$, the left hand side of (22) is non-negative. If
$\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]<0$,
(22) immediately follows. In the following, assuming
$\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]\geq
0$, we prove (22) for each case separately. Let $D_{k}^{*}$ be the maximum
value of $D_{k}^{t_{\mathrm{max}}}$ when $h^{\prime}_{k}(\xi_{b})=-1$ and
$\mathcal{F}_{+}^{c}$.

  * •

First, we consider the case of $\Pr(\mathcal{F}_{+})\geq 0.5$. It holds that

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=-1\right],$

where we used the fact that the probabilities of $h^{\prime}_{k}(\xi_{b})=1$
and $h^{\prime}_{k}(\xi_{b})=-1$ are both $1/2$. Combining it with
$\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]=0$,
we obtain

$\displaystyle\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right]=-\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=-1\right].$

We thus obtain

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle\geq\mathop{\mathbb{E}}_{\xi_{b}}\left[h^{\prime}_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
(due to the optimality of $h_{k}$)
$\displaystyle=\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right]-\frac{1}{2}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=-1\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right]$
$\displaystyle\geq\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
(since $h^{\prime}_{k}(\xi_{b})=1$ holds for the upper part of
$\mathcal{F}_{+}$)
$\displaystyle\geq\frac{1}{2}\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right].$

  * •

If $\Pr(\mathcal{F}_{+})<0.5$ and $D^{*}_{k}\geq 0$, the former part of the
proof in the previous case also applies to this case. The remaining part is

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle\geq\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right]$
$\displaystyle=\Pr_{\xi_{b}}\left(\mathcal{F}_{+}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+},h^{\prime}_{k}(\xi_{b})=1\right]$
$\displaystyle\qquad+\Pr_{\xi_{b}}\left(\mathcal{F}^{c}_{+}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=1\right]$
$\displaystyle\geq\Pr_{\xi_{b}}\left(\mathcal{F}_{+}\;\middle|\;\zeta_{b},\xi_{b-1},h^{\prime}_{k}(\xi_{b})=1\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+},h^{\prime}_{k}(\xi_{b})=1\right]$
$\displaystyle=\frac{\Pr_{\xi_{b}}\left(\mathcal{F}_{+}\;\middle|\;\zeta_{b},\xi_{b-1}\right)}{\Pr_{\xi_{b}}\left(h^{\prime}_{k}(\xi_{b})=1\;\middle|\;\zeta_{b},\xi_{b-1}\right)}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
$\displaystyle=2\Pr_{\xi_{b}}\left(\mathcal{F}_{+}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
$\displaystyle\geq\frac{1}{2}\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right].$

The first inequality is due to the non-negativity of
$D_{k}^{t_{\mathrm{max}}}$ conditioned on $\mathcal{F}^{c}_{+}$ and
$h^{\prime}_{k}(\xi_{b})=1$, which is implied by $D_{k}^{*}\geq 0$. The second
equality holds because $\mathcal{F}_{+}$ holds only when
$h^{\prime}_{k}(\xi_{b})=1$. The last inequality is due to the assumption
$\Pr_{\xi_{b}}(\mathcal{F}_{+}\mid\zeta_{b},\xi_{b-1})\geq\Pr_{\xi_{b}}(\mathcal{F}\mid\zeta_{b},\xi_{b-1})/2$.

  * •

If $\Pr(\mathcal{F}_{+})<0.5$ and $D^{*}_{k}<0$, we obtain

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle\geq\mathop{\mathbb{E}}_{\xi_{b}}\left[h^{\prime}_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
(due to the optimality of $h_{k}$)
$\displaystyle=\Pr_{\xi_{b}}\left(\mathcal{F}_{+}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
$\displaystyle\qquad+\Pr_{\xi_{b}}\left(\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=1\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=1\right]$
$\displaystyle\qquad-\Pr_{\xi_{b}}\left(\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=-1\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=-1\right]$
$\displaystyle\geq\Pr_{\xi_{b}}\left(\mathcal{F}_{+}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
$\displaystyle\qquad+\Pr_{\xi_{b}}\left(\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=1\;\middle|\;\zeta_{b},\xi_{b-1}\right)D_{k}^{*}-\Pr_{\xi_{b}}\left(\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=-1\;\middle|\;\zeta_{b},\xi_{b-1}\right)D_{k}^{*}$
$\displaystyle\geq\Pr_{\xi_{b}}\left(\mathcal{F}_{+}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
$\displaystyle\geq\frac{1}{2}\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right].$

The second inequality is due to the definition of $D_{k}^{*}$. The third
inequality is due to the negativity of $D_{k}^{*}$ and
$\Pr_{\xi_{b}}\left(\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=1\;\middle|\;\zeta_{b},\xi_{b-1}\right)\leq\Pr_{\xi_{b}}\left(\mathcal{F}_{+}^{c},h^{\prime}_{k}(\xi_{b})=-1\;\middle|\;\zeta_{b},\xi_{b-1}\right)$.

We thus proved (22). In the remaining part of the proof, we give a lower bound
on each of
$\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)$ and
$\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$.

First, we show that the expected value of $D_{k}^{t_{\mathrm{max}}}$ is at
least $\frac{\sqrt{c^{3}L}}{4}$ conditioned on $\mathcal{F}_{+}$. Let
$t^{*}_{+}$ be the first time round that
$D^{t}_{k}\geq\frac{\sqrt{c^{3}L}}{4}$ holds, which is well-defined
conditioned on $\mathcal{F}_{+}$. For each $t\in\mathcal{T}_{b}$, if we
condition on $\mathcal{F}_{+}$ and $t_{+}^{*}=t$, we have

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t^{\prime}+1}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+},t_{+}^{*}=t\right]=\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t^{\prime}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+},t_{+}^{*}=t\right]$

for any $t^{\prime}\geq t$ because whether the events $\mathcal{F}_{+}$ and
$t^{*}=t$ hold is determined until round $t^{\prime}$. By considering the
expected value for different $t_{+}^{*}$ separately,

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
$\displaystyle=\sum_{t\in\mathcal{T}_{b}}\Pr_{\xi_{b}}\left(t_{+}^{*}=t\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+},t_{+}^{*}=t\right]$
$\displaystyle=\sum_{t\in\mathcal{T}_{b}}\Pr_{\xi_{b}}\left(t_{+}^{*}=t\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+},t_{+}^{*}=t\right]$
$\displaystyle\geq\sum_{t\in\mathcal{T}_{b}}\Pr_{\xi_{b}}(t_{+}^{*}=t\mid\mathcal{F}_{+})~{}\frac{\sqrt{c^{3}L}}{4}$
$\displaystyle=\frac{\sqrt{c^{3}L}}{4}.$ (23)

Next, we provide a lower bound on
$\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)$ by
using the assumption

$\mathop{\mathbb{E}}_{\xi_{b}}\left[\sum_{t\in\mathcal{T}_{b}}\left|\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,0}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]-\mathop{\mathbb{E}}_{\theta_{i}\sim\mathcal{I}_{p,1}}\left[\pi_{i}^{t}(\theta_{i};\alpha_{0})\right]\right|\;\middle|\;\zeta_{b},\xi_{b-1}\right]\geq
cL.$

Using random variables $X_{0}^{t}$ and $X_{1}^{t}$, this assumption can be
written as

$\mathop{\mathbb{E}}_{t\sim\mathcal{T}_{b},\xi_{b}}\left[\left|X_{0}^{t}-X_{1}^{t}\right|\;\middle|\;\zeta_{b},\xi_{b-1}\right]\geq
c.$

By applying Lemma 4.5, we obtain

$\Pr_{t\sim\mathcal{T}_{b},\xi_{b}}\left(\left(X_{0}^{t}-X_{1}^{t}\right)^{2}\geq\frac{c^{2}}{4}\;\middle|\;\zeta_{b},\xi_{b-1}\right)=\Pr_{t\sim\mathcal{T}_{b},\xi_{b}}\left(\left|X_{0}^{t}-X_{1}^{t}\right|\geq\frac{c}{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\geq\frac{c}{2}.$

We thus obtain

$\mathop{\mathbb{E}}_{\xi_{b}}\left[\sum_{t\in\mathcal{T}_{b}}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]=L\mathop{\mathbb{E}}_{t\sim\mathcal{T}_{b},\xi_{b}}\left[\left(X_{0}^{t}-X_{1}^{t}\right)^{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]=L\cdot\frac{c}{2}\cdot\frac{c^{2}}{4}\geq\frac{c^{3}L}{8}.$
(24)

We show that a stochastic process
$(D_{k}^{t})^{2}-\frac{1}{2}\sum_{t^{\prime}\in\mathcal{T}_{b}\colon
t^{\prime}\leq t}\left(X_{0}^{t^{\prime}}-X_{1}^{t^{\prime}}\right)^{2}$ for
$t\in\mathcal{T}_{b}$ is a martingale. We denote by $\mathcal{F}_{t}$ all the
events that happen until the end of time round $t$. Conditioned on
$\mathcal{F}_{t-1}$, the expected difference is

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t})^{2}-\frac{1}{2}\sum_{t^{\prime}\in\mathcal{T}_{b}\colon
t^{\prime}\leq
t}\left(X_{0}^{t^{\prime}}-X_{1}^{t^{\prime}}\right)^{2}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{t-1}\right]-\left\\{(D_{k}^{t-1})^{2}-\frac{1}{2}\sum_{t^{\prime}\in\mathcal{T}_{b}\colon
t^{\prime}\leq
t-1}\left(X_{0}^{t^{\prime}}-X_{1}^{t^{\prime}}\right)^{2}\right\\}$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t})^{2}-(D_{k}^{t-1})^{2}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{t-1}\right]-\frac{1}{2}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t}-D_{k}^{t-1})(D_{k}^{t}+D_{k}^{t-1})\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{t-1}\right]-\frac{1}{2}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t}-D_{k}^{t-1})(2D_{k}^{t-1}+(D_{k}^{t}-D_{k}^{t-1}))\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{t-1}\right]-\frac{1}{2}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}$
$\displaystyle=2D_{k}^{t-1}\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t}-D_{k}^{t-1}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{t-1}\right]+\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t}-D_{k}^{t-1})^{2}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{t-1}\right]-\frac{1}{2}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}$
$\displaystyle=0+\frac{1}{2}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}-\frac{1}{2}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}$
(since (20)) $\displaystyle=0.$

We define the random variable $t^{*}\in\mathcal{T}_{b}$ such that

$t^{*}=\begin{cases}\min\left\\{t\in\mathcal{T}_{b}\;\middle|\;|D_{k}^{t}|\geq\frac{\sqrt{c^{3}L}}{4}\right\\}&\text{if
$\mathcal{F}$ holds}\\\ {t_{\mathrm{max}}}&\text{otherwise}\end{cases}$

is the time round when $|D_{k}^{t}|$ exceeds $\frac{\sqrt{c^{3}L}}{4}$ for the
first time if $\mathcal{F}$ holds. Since the stopping time $t^{*}$ is bounded
above by ${t_{\mathrm{max}}}$, we can apply Doob’s optional stopping theorem
to the martingale defined above and obtain

$\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t^{*}})^{2}-\sum_{t\in\mathcal{T}_{b}\colon
t\leq
t^{*}}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]=0.$

Since $\sum_{t\in\mathcal{T}_{b}\colon
t>t^{*}}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}$ is $0$ if $\mathcal{F}$ does not
hold and bounded above by $L$ if $\mathcal{F}$ holds, we have

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[\sum_{t\in\mathcal{T}_{b}}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[\sum_{t\in\mathcal{T}_{b}\colon
t\leq
t^{*}}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]+\mathop{\mathbb{E}}_{\xi_{b}}\left[\sum_{t\in\mathcal{T}_{b}\colon
t>t^{*}}\left(X_{0}^{t}-X_{1}^{t}\right)^{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t^{*}})^{2}\;\middle|\;\zeta_{b},\xi_{b-1}\right]+\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)L$
$\displaystyle=\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t^{*}})^{2}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}\right]+\Pr_{\xi_{b}}\left(\mathcal{F}^{c}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[(D_{k}^{t^{*}})^{2}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}^{c}\right]+\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)L$
$\displaystyle\leq\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\left(\frac{\sqrt{c^{3}L}}{4}+1\right)^{2}+\Pr_{\xi_{b}}\left(\mathcal{F}^{c}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\left(\frac{\sqrt{c^{3}L}}{4}\right)^{2}+\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)L$
$\displaystyle\leq
4L\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)+\frac{c^{3}L}{16},$

where we used $c\leq 1$, $\sqrt{L}\leq L$, $L\geq 1$, and
$\Pr_{\xi_{b}}\left(\mathcal{F}^{c}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\leq
1$ for the last inequality. Combining it with (24), we obtain

$\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\geq\frac{c^{3}L/8-c^{3}L/16}{4L}=\frac{c^{3}}{64}.$
(25)

Plugging (23) and (25) into (22), we obtain

$\displaystyle\mathop{\mathbb{E}}_{\xi_{b}}\left[\frac{1}{2}\mathop{\mathbb{E}}_{\begin{subarray}{c}\theta^{\prime}_{i}\sim\mathcal{I}_{p,0}\\\
\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,0}\end{subarray}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\begin{subarray}{c}\theta^{\prime}_{i}\sim\mathcal{I}_{p,1}\\\
\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,1}\end{subarray}}\left[\sum_{t\in\mathcal{T}_{b}}\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\xi_{b}}\left[\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p}}\left[\sum_{t\in\mathcal{T}_{b}}Y_{\theta^{\prime\prime}_{i}}^{t}\right]+\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,0}}\left[\sum_{t\in\mathcal{T}_{b}}Z_{\theta^{\prime\prime}_{i}}^{t}\right]-\frac{1}{2}\mathop{\mathbb{E}}_{\theta^{\prime\prime}_{i}\sim\mathcal{J}_{p,1}}\left[\sum_{t\in\mathcal{T}_{b}}Z_{\theta^{\prime\prime}_{i}}^{t}\right]\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
(since (18))
$\displaystyle=\frac{L}{2}+\frac{1}{2^{B-b+1}}\sum_{k=1}^{2^{B-b}}\mathop{\mathbb{E}}_{\xi_{b}}\left[h_{k}(\xi_{b})D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1}\right]$
(since (19) and (21))
$\displaystyle\geq\frac{L}{2}+\frac{1}{2^{B-b+1}}\sum_{k=1}^{2^{B-b}}\frac{1}{2}\Pr_{\xi_{b}}\left(\mathcal{F}\;\middle|\;\zeta_{b},\xi_{b-1}\right)\mathop{\mathbb{E}}_{\xi_{b}}\left[D_{k}^{t_{\mathrm{max}}}\;\middle|\;\zeta_{b},\xi_{b-1},\mathcal{F}_{+}\right]$
(since (22))
$\displaystyle\geq\frac{L}{2}+\frac{1}{2^{B-b+1}}\sum_{k=1}^{2^{B-b}}\frac{1}{2}\cdot\frac{c^{3}}{64}\cdot\frac{\sqrt{c^{3}L}}{4}$
(since (23) and (25)) $\displaystyle=\frac{L}{2}+2^{-10}c^{9/2}\sqrt{L},$

which completes the proof. ∎

###  4.4 Proof of lower bound

Finally, we prove the theorem using Lemmas 4.6, 4.4 and 4.7.

###### Proof of Theorem 4.1.

Since the rewards for type
$\theta^{\prime\prime}_{i}\in\Theta^{\prime\prime}_{i}$ are determined by
independent Bernoulli random variables $\xi$, and therefore the expected
reward obtained by the algorithm for each round is equal to $1/2$. Formally,
since the algorithm’s decision $\pi_{i}^{t}(\theta^{\prime\prime}_{i})$ is
independent from
$u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha_{0})=1-u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha_{1})=\xi(\theta^{\prime\prime}_{i})(t)$,
the expected reward is

$\displaystyle\mathop{\mathbb{E}}_{\zeta,\xi}\left[\mathop{\mathbb{E}}_{\alpha\sim\pi_{i}^{t}(\theta^{\prime\prime}_{i})}\left[u_{i}^{t}(\theta^{\prime\prime}_{i},\alpha)\right]\right]$