\phi(\boldsymbol{A}^{\prime},\boldsymbol{A}^{*}).$ (82)

###### Proof.

  1. 1.

The ‘if’ part. If $\boldsymbol{A}^{*}$ is not an equilibrium state, there
exists at least one $\boldsymbol{a}^{\prime}_{r_{0}}$ which satisfies

$\displaystyle\ \ \underset{\mathbb{P}\in\boldsymbol{\mathcal{P}}_{r_{0}}}{\
\textbf{{max}}\phantom{g}\ }\
\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}\Big{[}f_{r_{0}}(\boldsymbol{a}^{\prime}_{r_{0}},\boldsymbol{a}^{*}_{-{r_{0}}},\boldsymbol{w})\Big{]}$
(83) $\displaystyle<$ $\displaystyle\ \
\underset{\mathbb{P}\in\boldsymbol{\mathcal{P}}_{r_{0}}}{\
\textbf{{max}}\phantom{g}\ }\
\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}\Big{[}f_{r_{0}}(\boldsymbol{a}^{*}_{r_{0}},\boldsymbol{a}^{*}_{-{r_{0}}},\boldsymbol{w})\Big{]}.$

Let $\boldsymbol{A}^{\prime\prime}$ be

$\boldsymbol{A}^{\prime\prime}=[\boldsymbol{a}^{*}_{1},\dots,\boldsymbol{a}^{*}_{r_{0}-1},\boldsymbol{a}^{\prime}_{r_{0}},\boldsymbol{a}^{*}_{r_{0}+1},\dots,\boldsymbol{a}^{*}_{R}]$
(84)

and we could conduct the following contradiction by (83):

$\phi(\boldsymbol{A}^{\prime\prime},\boldsymbol{A}^{*})<\phi(\boldsymbol{A}^{*},\boldsymbol{A}^{*}).$
(85)

  2. 2.

The ‘only if’ part. By the definition of distributionally robust Nash
equilibrium, for any $\boldsymbol{A}^{\prime}$, it holds that

$\displaystyle\ \ \underset{\mathbb{P}\in\boldsymbol{\mathcal{P}}_{r}}{\
\textbf{{max}}\phantom{g}\ }\
\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}\Big{[}f_{r}(\boldsymbol{a}^{\prime}_{r},\boldsymbol{a}^{*}_{-{r}},\boldsymbol{w})\Big{]}$
(86) $\displaystyle\geq$ $\displaystyle\ \
\underset{\mathbb{P}\in\boldsymbol{\mathcal{P}}_{r}}{\
\textbf{{max}}\phantom{g}\ }\
\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}\Big{[}f_{r}(\boldsymbol{a}^{*}_{r},\boldsymbol{a}^{*}_{-{r}},\boldsymbol{w})\Big{]},\
\ \forall\ r\in[R].$

Summing the two sides of the above inequality, we have

$\displaystyle\phi(\boldsymbol{A}^{\prime},\boldsymbol{A}^{*})$
$\displaystyle=$ $\displaystyle\ \
\sum_{r=1}^{R}\underset{\mathbb{P}\in\boldsymbol{\mathcal{P}}_{r}}{\
\textbf{{max}}\phantom{g}\ }\
\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}\Big{[}f_{r}(\boldsymbol{a}^{\prime}_{r},\boldsymbol{a}^{*}_{-{r}},\boldsymbol{w})\Big{]}$
(87) $\displaystyle\geq$ $\displaystyle\ \
\sum_{r=1}^{R}\underset{\mathbb{P}\in\boldsymbol{\mathcal{P}}_{r}}{\
\textbf{{max}}\phantom{g}\ }\
\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}\Big{[}f_{r}(\boldsymbol{a}^{*}_{r},\boldsymbol{a}^{*}_{-{r}},\boldsymbol{w})\Big{]}$
$\displaystyle=$ $\displaystyle\ \
\phi(\boldsymbol{A}^{*},\boldsymbol{A}^{*})$

which implies $\boldsymbol{A}^{*}$ is a global optimal solution as (82).

∎

Based on the Proposition 1, we show the existence results of DRNE for the
adversarial game. This results is an extension of the famous Kakutani’s fixed
point theorem [30].

See 1

###### Proof.

We know that the ‘supremum’ operator will preserve the convexity. Moreover,
with the weakly compactness of $\boldsymbol{\mathcal{P}}_{r}$, the ‘supremum’
operator also preserve the continuity. As a consequence, for any given
$\boldsymbol{a}_{-r}$,
$\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}[f_{r}(\cdot,\boldsymbol{a}_{-r},\boldsymbol{w})]$
is continuous and convex for every
$\mathbb{P}\in\boldsymbol{\mathcal{P}}_{r},r=1,\dots,R$. By the definition of
$\phi$ (81), for any given $\boldsymbol{A}$,
$\phi(\boldsymbol{A}^{\prime},\boldsymbol{A})$ is continuous and convex w.r.t.
any $\boldsymbol{A}^{\prime}$. Besides, the existence of an optimal solution
to

$\underset{\boldsymbol{A}^{\prime}}{\textbf{{min}}}\
\phi(\boldsymbol{A}^{\prime},\boldsymbol{A})$ (88)

with given $\boldsymbol{a}$ is guaranteed by assuming that
$\mathbb{E}_{\boldsymbol{w}\sim\mathbb{P}}[f_{r}(\cdot,\boldsymbol{a}_{-r},\boldsymbol{w})]$
only has finite values.

The remaining part is to show the existence of $\boldsymbol{A}^{*}$ which
satisfies

$\boldsymbol{A}^{*}\in\underset{\boldsymbol{A}^{\prime}}{\textbf{{arg min}}}\
\phi(\boldsymbol{A}^{\prime},\boldsymbol{A}^{*}).$ (89)

Let $\Gamma(\boldsymbol{A})$ be the solution set of $\textbf{{min}}\
\phi(\boldsymbol{A}^{\prime},\boldsymbol{A})$ with given $\boldsymbol{A}$. By
the convexity of $\phi(\cdot,\boldsymbol{A})$, $\Gamma(\boldsymbol{A})$ is a
convex set. $\Gamma(\boldsymbol{A})$ is also a closed set: for any
$\\{\boldsymbol{A}_{t}\\}\rightarrow\boldsymbol{\bar{A}}$ as
$t\rightarrow\infty$ and
$\boldsymbol{A}^{\prime}_{t}\in\Gamma(\boldsymbol{A}_{t})$ with
$\\{\boldsymbol{A}^{\prime}_{t}\\}\rightarrow\boldsymbol{\bar{A}}^{\prime}$,
it holds that

$\boldsymbol{\bar{A}}^{\prime}\in\Gamma(\boldsymbol{\bar{A}}).$ (90)

By [5], $\Gamma(\boldsymbol{A})$ is upper semi-continuous on
$\mathbb{R}^{N\times R}$. With the well-known Kakutani’s fixed point theorem
[30], there exists $\boldsymbol{A}^{*}$ such that

$\boldsymbol{A}^{*}\in\underset{\boldsymbol{A}^{\prime}}{\textbf{{arg min}}}\
\phi(\boldsymbol{A}^{\prime},\boldsymbol{A}^{*}).$ (91)

With Proposition 1, we know $\boldsymbol{A}^{*}$ is a distributionally robust
Nash equilibrium. ∎

## Proof of Theorem 2

In this section, we prove the main technical result for Bernoulli sampling.
First we need the follow well-known results of martingale inequalities.

######  Definition 7.

A martingale is a sequence $\boldsymbol{X}=(x_{1},\dots,x_{T})$ of random
variables with finite means, such that

$\mathbb{E}\big{[}x_{t+1}|x_{1},\dots,x_{t}\big{]}=x_{t},\ \ \forall\
t\in[T].$ (92)

The most basic and well-known concentration result of martingale is the
Azuma’s (or Hoeffding’s) inequality, which asserts that martingales with
bounded differences $|x_{t+1}-x_{t}|$ are well-concentrated around their mean.
However, we need the other concentration inequality which can deal with the
case that the maximum value $M$ of $|x_{t+1}-x_{t}|$ is large, but the maximum
is rarely attained (making the variance much smaller than $M^{2}$) [23, 39,
19]. The martingales that we investigate in this paper depict this behavior.

######  Lemma 1.

Let $\boldsymbol{X}=(x_{1},\dots,x_{T})$ be a martingale and the variance of
$x_{t+1}$ given $x_{1},\dots,x_{t}$ be bounded

$\textbf{{Var}}(x_{t+1}|x_{1},\dots,x_{t})\leq\sigma^{2}_{t+1},\ \ \forall\
t\in[T],$ (93)

where $\sigma_{t}\geq 0$. If there exist a constant $M$ such that

$|x_{t+1}-x_{t}|\leq M,$ (94)

we have

$\mathbb{P}\big{(}\boldsymbol{X}-\mathbb{E}[\boldsymbol{X}]\geq\lambda\big{)}\leq\textbf{{exp}}\left(-\frac{\lambda^{2}}{\sum_{t=1}^{T}\sigma^{2}_{t}+\frac{\lambda
M}{3}}\right),$ (95)

where $\mathbb{E}[\boldsymbol{X}]$ is defined as

$\mathbb{E}[\boldsymbol{X}]=\sum_{t=1}^{T}\mathbb{E}[x_{t}].$ (96)

Particularly,

$\mathbb{P}\Big{(}\big{|}\boldsymbol{X}-\mathbb{E}[\boldsymbol{X}]\big{|}\geq\lambda\Big{)}\leq
2\cdot\textbf{{exp}}\left(-\frac{\lambda^{2}}{\sum_{t=1}^{T}\sigma^{2}_{t}+\frac{\lambda
M}{3}}\right).$ (97)

The following lemmas assert that for any given subset
$\boldsymbol{S}_{\mathcal{A}}$ of the universe $\boldsymbol{\mathcal{C}}$, the
fraction of elements from $\boldsymbol{S}_{\mathcal{A}}$ within the sample
typically does not differ by much from the corresponding fraction among the
whole stream. Lemma 2 corresponds to the Bernoulli sampling. Lemma 3
corresponds to the reservoir sampling.

######  Lemma 2.

For any dynamic stream $\boldsymbol{C}=\\{c_{t}\\}_{t=1}^{\infty}$ from
$\boldsymbol{\mathcal{C}}^{\prime}$, if the parameter of Bernoulli method
$\varrho$ holds that

$\varrho\geq 10\cdot\frac{\textbf{{ln}}(4/\delta)}{\epsilon^{2}T},$ (98)

we have

$\mathbb{P}(|d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C})-d_{\boldsymbol{\mathcal{C}}^{\prime}}(\boldsymbol{C}^{\prime})|\geq\epsilon)\leq\delta,$
(99)

where $\boldsymbol{C}^{\prime}$ is a sequence which is sampled from
$\boldsymbol{C}$ by the Bernoulli method.

###### Proof.

At any given time step $t\in[T]$ along the sampling process, let
$\boldsymbol{C}_{t}=(c_{1},\dots,c_{t})$ be the sequence of pairwise
comparisons submitted to the Bernoulli method until time $t$, and
$\boldsymbol{C}_{t}^{\prime}\subseteq\boldsymbol{C}_{t}$ be a sub-sequence of
the sampled pairwise comparisons from $\boldsymbol{C}_{t}$. Note that
$\boldsymbol{C}_{T}=\boldsymbol{C}$ and
$\boldsymbol{C}^{\prime}_{T}=\boldsymbol{C}^{\prime}$, and hence, to prove the
lemma, we need to show that

$|d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{T})-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{T}^{\prime})|\leq\epsilon.$

Given a $\boldsymbol{\mathcal{C}^{\prime}}$, we define the random variables

$\displaystyle A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \ \frac{\ t}{T}\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t})=\frac{|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t}|}{T},$
(100) $\displaystyle B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$
$\displaystyle=$ $\displaystyle\ \
\frac{|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}^{\prime}_{t}|}{\varrho
T},$ $\displaystyle Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$
$\displaystyle=$ $\displaystyle\ \
B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})-A_{t}({\boldsymbol{\mathcal{C}^{\prime}}}),$

where the intersection between a set $\boldsymbol{\mathcal{C}^{\prime}}$ and a
sequence $\boldsymbol{C}_{t}$ is the sub-sequence of $\boldsymbol{C}_{t}$
consisting of all pairwise comparisons (repetitions are allowed) that also
belong to $\boldsymbol{\mathcal{C}^{\prime}}$. Next we show that
$(Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{T}({\boldsymbol{\mathcal{C}^{\prime}}}))$
is a martingale. Suppose that the $\boldsymbol{C}^{\prime}_{t-1}$ is fixed and
thence the values of
$Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$
are fixed. Now a new pairwise comparison $c_{t}$ is ready to submit. Note that
$c_{t}$ may be either the original data or the comparison perturbed by the
adversary.

If $c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}}$, we have

$\displaystyle A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \ A_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),$ (101)
$\displaystyle B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \ B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),$
$\displaystyle Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \ Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),$

and it holds that

$\mathbb{E}\big{[}\ Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\ \big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}}\
\big{]}=Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$ (102)

When $c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}$, we have

$\displaystyle A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \ A_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+\frac{1}{T},$
(103) $\displaystyle B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$
$\displaystyle=$ $\displaystyle\ \ \begin{cases}\displaystyle
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),&\ \text{if}\ c_{t}\ \text{is not
sampled},\\\\[5.0pt] \displaystyle
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+\frac{1}{\varrho
T},&\text{otherwise.}\end{cases}$ $\displaystyle
Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$ $\displaystyle\ \
\begin{cases}\displaystyle
Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})-\frac{1}{T},&\ \text{if}\ c_{t}\
\text{is not sampled},\\\\[7.5pt] \displaystyle
Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+\frac{1}{\varrho
T}-\frac{1}{T},&\ \text{otherwise.}\end{cases}$

Recall that each pairwise comparison is sampled by the Bernoulli method,
independently, with probability $\varrho$. Therefore, we have that

$\displaystyle\ \ \mathbb{E}\big{[}\
Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\ \big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}\ \big{]}$ (104) $\displaystyle=$
$\displaystyle\ \
Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+\varrho\cdot\left(\frac{1}{\varrho
T}-\frac{1}{T}\right)+(1-\varrho)\cdot\left(-\frac{1}{T}\right)$
$\displaystyle=$ $\displaystyle\ \
Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}).$

Combine the two cases, we know that
$(Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{T}({\boldsymbol{\mathcal{C}^{\prime}}}))$
is a martingale.

Next we will show that the variance of
$Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ conditioned on
$Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$
is bounded by $1/\varrho T^{2}$. If
$c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}}$ and with simple calculation
from (101) and (102), the variance of
$Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ given
$Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$
equals to zeros as

$\textbf{{Var}}(\ Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\ \big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}}\ )=0.$ (105)

When $c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}$, we have

$\displaystyle\ \ \textbf{{Var}}(\ Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\
\big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}\ )$ (106) $\displaystyle=$
$\displaystyle\ \
(1-\varrho)\cdot\left(\frac{1}{T}\right)^{2}+\varrho\cdot\left(\frac{1}{\varrho
T}-\frac{1}{T}\right)^{2}$ $\displaystyle=$ $\displaystyle\ \
\frac{1}{T^{2}}\cdot\left(\frac{1}{\varrho}-1\right)\leq\frac{1}{\varrho
T^{2}}.$

Combine the two cases, we know that the variance of
$Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ conditioned on
$Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$
is bounded by $1/\varrho T^{2}$.

It always holds that

$|Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})-Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})|\leq\textbf{{max}}\left\\{\frac{1}{T},\frac{1}{\varrho
T}-\frac{1}{T}\right\\}\leq\frac{1}{\varrho T}.$ (107)

At last, we complete the proof of this lemma by proving the following two
inequalities for any $\varrho$ satisfying the condition (98).

$\displaystyle\mathbb{P}\left(\
\big{|}A_{T}(\boldsymbol{\mathcal{C}^{\prime}})\
-B_{T}(\boldsymbol{\mathcal{C}^{\prime}})\big{|}\geq\frac{\epsilon}{2}\
\right)\leq\frac{\delta}{2}$ (108a) $\displaystyle\mathbb{P}\left(\
\big{|}B_{T}(\boldsymbol{\mathcal{C}^{\prime}})-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{T}^{\prime})\big{|}\geq\frac{\epsilon}{2}\
\right)\leq\frac{\delta}{2}$ (108b)

We can choose $\lambda=\epsilon/2$, $\sigma^{2}_{t}=1/\varrho T^{2}$ and
$M=1/\varrho T$ and apply Lemma 1 on
$(Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{T}({\boldsymbol{\mathcal{C}^{\prime}}}))$.
As $Z_{0}(\boldsymbol{\mathcal{C}^{\prime}})=0$, we have

$|A_{T}(\boldsymbol{\mathcal{C}^{\prime}})-B_{T}(\boldsymbol{\mathcal{C}^{\prime}})|=|Z_{T}(\boldsymbol{\mathcal{C}^{\prime}})-Z_{0}(\boldsymbol{\mathcal{C}^{\prime}})|,$
(109)

and (108a) will holds that

$\displaystyle\ \ \mathbb{P}\left(\
\big{|}A_{T}(\boldsymbol{\mathcal{C}^{\prime}})-B_{T}(\boldsymbol{\mathcal{C}^{\prime}})\big{|}\geq\frac{\epsilon}{2}\
\right)$ (110) $\displaystyle\leq$ $\displaystyle\ \
2\cdot\textbf{{exp}}\left(-\frac{(\epsilon/2)^{2}}{2T\cdot(1/\varrho
T^{2})+\epsilon/(6\varrho T)}\right)$ $\displaystyle<$ $\displaystyle\ \
2\cdot\textbf{{exp}}\left(-\frac{\epsilon^{2}\varrho T}{9}\right).$

When

$\varrho\geq 9\cdot\frac{\textbf{{ln}}(\delta/4)}{\epsilon^{2}T},$ (111)

the (110) is further bounded by $\delta/2$.

To prove (108b), we observe that

$B_{T}(\boldsymbol{\mathcal{C}^{\prime}})=d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime}_{T})\cdot\frac{|\boldsymbol{C}^{\prime}_{T}|}{\varrho
T},$ (112)

and each pairwise comparison is selected by Bernoulli method with probability
$\varrho$, independently of other pairwise comparison. The size of
$\boldsymbol{C}^{\prime}_{t}$ equals to the expectation of binaomial
distribution $\textbf{{Binaomial}}(T,\varrho)$, regardless of the adversary’s
strategy. Applying the Chernoff inequality with $\delta=\epsilon/2$, we have

$\displaystyle\ \ \mathbb{P}\left(\big{|}|\boldsymbol{C}^{\prime}_{T}|-\varrho
T\big{|}\geq\frac{\epsilon\varrho T}{2}\right)$ (113) $\displaystyle\leq$
$\displaystyle\ \ 2\cdot\textbf{{exp}}\left(-\frac{(\epsilon/2)^{2}\varrho
T}{2+\epsilon/3}\right)$ $\displaystyle<$ $\displaystyle\ \
2\cdot\textbf{{exp}}\left(-\frac{\epsilon^{2}\varrho T}{10}\right).$

When

$\varrho\geq 10\cdot\frac{\textbf{{ln}}(\delta/4)}{\epsilon^{2}T},$ (114)

the above inequality is further bounded by $\delta/2$. Conditioning on this
event ($||\boldsymbol{C}^{\prime}_{t}|-\varrho T|\geq\epsilon\varrho T/2$), we
have

$\displaystyle\ \
\big{|}d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime}_{T})-B_{T}(\boldsymbol{\mathcal{C}^{\prime}})\big{|}$
(115) $\displaystyle=$ $\displaystyle\ \
\left|1-\frac{|\boldsymbol{C}^{\prime}_{T}|}{\varrho T}\right|\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime}_{T})$
$\displaystyle\leq$ $\displaystyle\ \
\left|1-\frac{|\boldsymbol{C}^{\prime}_{T}|}{\varrho
T}\right|\leq\frac{\epsilon}{2},$

where the first inequality follows the fact
$d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime}_{T})$ is always
bounded by $1$, and the second inequality follows form the condition
$||\boldsymbol{C}^{\prime}_{t}|-\varrho T|\geq\epsilon\varrho T/2$. We
complete the proof of (108b).

Indeed, taking a union bound over (108a) and (108b), applying the triangle
inequality and observing that
$A_{T}(\boldsymbol{\mathcal{C}^{\prime}})=d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime}_{T})$,
we obtain the desired conclusion (99). ∎

######  Lemma 3.

For any dynamic stream $\boldsymbol{C}=\\{c_{t}\\}_{t=1}^{\infty}$ from
$\boldsymbol{\mathcal{C}}^{\prime}$, if the parameter of reservoir method
$\varrho$ holds that

$\varrho\geq 2\cdot\frac{\textbf{{ln}}(2/\delta)}{\epsilon^{2}},$ (116)

we have

$\mathbb{P}(|d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C})-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime})|\geq\epsilon)\leq\delta,$
(117)

where $\boldsymbol{C}^{\prime}$ is a sequence which is sampled from
$\boldsymbol{C}$ by the reservoir method.

###### Proof.

Generally speaking, the proof of this lemma goes along the same lines as Lemma
2, except that adopting the other martingale. Specifically, we define

$\displaystyle A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \ t\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t})=|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t}|,$
(118) $\displaystyle B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$
$\displaystyle=$ $\displaystyle\ \ t\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime}_{t})=\frac{t}{\varrho}|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}^{\prime}_{t}|,$
$\displaystyle Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \
B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})-A_{t}({\boldsymbol{\mathcal{C}^{\prime}}}),$

for $t\in(\varrho,T]$. When $t<\varrho$, we define

$A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})=B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})=|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t}|.$
(119)

The next step is similar to Lemma 2. We first show that
$(Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{T}({\boldsymbol{\mathcal{C}^{\prime}}}))$
is a martingale. Notice that
$(Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{T}({\boldsymbol{\mathcal{C}^{\prime}}}))$
is obviously a martingale for $t\leq\varrho$. When $t>\varrho$, the
$\boldsymbol{C}^{\prime}_{t-1}$ is fixed and thence the values of
$Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$
are fixed. Let $c_{t}$ be the next pairwise comparison for the reservoir
sampling method, which could be either from the original data source or the
adversarial data source controlled by the adversary. It is easy to check that

$A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})=\left\\{\begin{matrix}A_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),&c_{t}\notin{\boldsymbol{\mathcal{C}^{\prime}}},\\\
A_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+1.&c_{t}\in{\boldsymbol{\mathcal{C}^{\prime}}}.\end{matrix}\right.$
(120)

For $B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$, we consider the three
factors:

  * i)

is $c_{t}\in{\boldsymbol{\mathcal{C}^{\prime}}}$ or not?

  * ii)

is $c_{t}$ sampled or not?

  * iii)

conditioning on $c_{t}$ being sampled, does it replace an element $r_{t}$ from
${\boldsymbol{\mathcal{C}^{\prime}}}$ in the sample, or $r_{t}$ not in
${\boldsymbol{\mathcal{C}^{\prime}}}$?

  * Case 1.

When $c_{t}\notin{\boldsymbol{\mathcal{C}^{\prime}}}$ is either not sampled,
or sampled but with $r_{t}\notin{\boldsymbol{\mathcal{C}^{\prime}}}$, the
pairwise comparisons from $\boldsymbol{\mathcal{C}^{\prime}}$ are neither
added nor removed into the cache of the reservoir method. Consequently, we
have

$\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t}=\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t-1}.$
(121)

By the definition of $B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$

$\displaystyle B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \
\frac{t}{\varrho}\cdot|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t}|$
(122) $\displaystyle=$ $\displaystyle\ \
\frac{t-1}{\varrho}\cdot|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t-1}|+\frac{1}{\varrho}\cdot|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t-1}|$
$\displaystyle=$ $\displaystyle\ \
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1}),$

where the third equality stands since the sampled pairwise comparisons of
$\boldsymbol{C}_{t-1}$ is $|\boldsymbol{C}_{t-1}|=\varrho$ when $t>\varrho$.
Therefore conditioned on $c_{t}\notin{\boldsymbol{\mathcal{C}^{\prime}}}$, the
expectation of $B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ is

$\displaystyle\ \
\mathbb{E}[B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})|c_{t}\notin{\boldsymbol{\mathcal{C}^{\prime}}}]$
(123) $\displaystyle=$ $\displaystyle\ \
\left(1-\frac{\varrho}{t}d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\right)\cdot\Big{(}B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\Big{)}+\frac{\varrho}{t}d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\left(B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})-\frac{t}{\varrho}\right)$
$\displaystyle=$ $\displaystyle\ \
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}).$

Moreover,
$A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})=A_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$
when $c_{t}\notin{\boldsymbol{\mathcal{C}^{\prime}}}$ and we deduce that

$\mathbb{E}\big{[}\ Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\ \big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}}\
\big{]}=Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}).$ (124)

  * Case 2.

Now $c_{t}\in{\boldsymbol{\mathcal{C}^{\prime}}}$. When $c_{t}$ is neither
added nor removed into the cache of the reservoir method, we have
$|\boldsymbol{C}_{t}|=|\boldsymbol{C}_{t-1}|$ and
$B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})=B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$.
If $c_{t}$ into the cache and the replaced element
$r_{t}\notin{\boldsymbol{\mathcal{C}^{\prime}}}$, which has probability
$(\varrho/t)\cdot(1-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1}))$,
we have

$\displaystyle|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t}|$
$\displaystyle=$ $\displaystyle\ \
|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t-1}|+1$ (125)
$\displaystyle B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \
\frac{t}{\varrho}\cdot|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t}|$
$\displaystyle=$ $\displaystyle\ \
\frac{t}{\varrho}\cdot|\boldsymbol{\mathcal{C}^{\prime}}\cap\boldsymbol{C}_{t-1}|+\frac{t}{\varrho}$
$\displaystyle=$ $\displaystyle\ \
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})+\frac{t}{\varrho}.$

Then the expectation of $B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$
conditioned on $c_{t}\in{\boldsymbol{\mathcal{C}^{\prime}}}$ is

$\displaystyle\ \
\mathbb{E}[B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})|c_{t}\in{\boldsymbol{\mathcal{C}^{\prime}}}]$
(126) $\displaystyle=$ $\displaystyle\ \
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})+\left(\frac{\varrho}{t}\cdot(1-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\right)\cdot\frac{t}{\varrho}$
$\displaystyle=$ $\displaystyle\ \
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+1.$

Furthermore, with the definition of
$A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ when
$c_{t}\in{\boldsymbol{\mathcal{C}^{\prime}}}$, we know that

$\mathbb{E}\big{[}\ Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\ \big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}\
\big{]}=Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}).$ (127)

The analysis of the above two cases implies that
$(Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}}))$
is indeed a martingale.

The second part of proof is to obtain the bounds on the difference
$|Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})-Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})|$
and the variance of $Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ given
$Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$.
With the above analysis, we know that

$\displaystyle A_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ $\displaystyle=$
$\displaystyle\ \
\left\\{\begin{matrix}A_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),&c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}},\\\\[5.0pt]
A_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+1,&c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}.\end{matrix}\right.$
(128) $\displaystyle B_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$
$\displaystyle\in$ $\displaystyle\ \
\left\\{\begin{matrix}\displaystyle\left[B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+1\right],&c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}},\\\\[5.0pt]
\displaystyle\left[B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
B_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})+1+\frac{t}{\varrho}\right],&c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}.\end{matrix}\right.$

By the definition of $Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$, we conclude
that

$|Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})-Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})|\leq\frac{t}{\varrho}.$
(129)

We next bound the variance of $Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$
conditioned on
$Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}})$
and $d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$. When
$c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}}$, with probability
$(\varrho/t)\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$, it holds that

$\mathbb{E}[Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})]-Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})=\frac{t}{\varrho}-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1}).$
(130)

Otherwise, with probability $1-(\varrho/t)\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$, we have

$Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})-\mathbb{E}[Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})]=d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1}).$
(131)

Therefore,

$\displaystyle\ \ \textbf{{Var}}(\ Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\
\big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\notin\boldsymbol{\mathcal{C}^{\prime}},d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\
)$ (132) $\displaystyle=$ $\displaystyle\ \ \frac{\varrho}{t}\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\cdot\left(\frac{t}{\varrho}-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\right)^{2}+\left(1-\frac{\varrho}{t}\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\right)\cdot
d^{2}_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$
$\displaystyle=$ $\displaystyle\ \ \frac{t}{\varrho}\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})-d^{2}_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$
$\displaystyle\leq$ $\displaystyle\ \ \frac{t}{\varrho}.$

When $c_{t}\in\boldsymbol{\mathcal{C}^{\prime}}$, with probability
$(\varrho/t)\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$, it holds that

$Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})-\mathbb{E}[Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})]=\frac{t}{\varrho}+d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})-1.$
(133)

Otherwise, with probability $1-(\varrho/t)\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$, we have

$\mathbb{E}[Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})]-Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})=1-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1}).$
(134)

Thus,

$\displaystyle\ \ \textbf{{Var}}(\ Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})\
\big{|}\
Z_{0}({\boldsymbol{\mathcal{C}^{\prime}}}),\dots,Z_{t-1}({\boldsymbol{\mathcal{C}^{\prime}}}),\
c_{t}\in\boldsymbol{\mathcal{C}^{\prime}},d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\
)$ (135) $\displaystyle=$ $\displaystyle\ \ \frac{\varrho}{t}\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\cdot\left(\frac{t}{\varrho}-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\right)^{2}+\left(1-\frac{\varrho}{t}\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})\right)\cdot
d^{2}_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$
$\displaystyle=$ $\displaystyle\ \ \frac{t}{\varrho}\cdot
d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})-d^{2}_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$
$\displaystyle\leq$ $\displaystyle\ \ \frac{t}{\varrho}.$

(132) and (135) indicate that the conditional variance of
$Z_{t}({\boldsymbol{\mathcal{C}^{\prime}}})$ is bounded by $t/\varrho$.
Moreover, the bound remains intact when we remove the condition on
$d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}_{t-1})$.

Now we come to the conclusion of the whole lemma. Observe that

$\displaystyle\ \
\mathbb{P}(|d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C})-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime})|\geq\epsilon)$
(136) $\displaystyle=$ $\displaystyle\ \
\mathbb{P}(|B_{T}(\boldsymbol{\mathcal{C}^{\prime}})-A_{T}(\boldsymbol{\mathcal{C}^{\prime}})|\geq\epsilon\cdot
T)$ $\displaystyle=$ $\displaystyle\ \
\mathbb{P}(|Z_{T}(\boldsymbol{\mathcal{C}^{\prime}})-Z_{0}(\boldsymbol{\mathcal{C}^{\prime}})|\geq\epsilon\cdot
T).$

Then we apply Lemma 1 on the martingale
$Z(\boldsymbol{\mathcal{C}^{\prime}})=(Z_{0}(\boldsymbol{\mathcal{C}^{\prime}}),\dots,Z_{T}(\boldsymbol{\mathcal{C}^{\prime}}))$
with $\lambda=\epsilon T$, $\sigma^{2}_{t}=t/\varrho$ for $t\geq\varrho$ and
$\sigma^{2}_{t}=0$ for $t\geq\varrho$, and $M=T/\varrho$

$\displaystyle\ \
\mathbb{P}(|Z_{T}(\boldsymbol{\mathcal{C}^{\prime}})-Z_{0}(\boldsymbol{\mathcal{C}^{\prime}})|\geq\epsilon\cdot
T)$ (137) $\displaystyle\leq$ $\displaystyle\ \
2\textbf{{exp}}\left(-\frac{\displaystyle\lambda^{2}}{\displaystyle
2\sum_{t=1}^{T}\sigma^{2}_{t}+\frac{\lambda M}{3}}\right)$ $\displaystyle=$
$\displaystyle\ \ 2\textbf{{exp}}\left(-\frac{\epsilon^{2}T^{2}}{\displaystyle
2\sum_{t=1}^{T}\frac{t}{\varrho}+\frac{\epsilon T^{2}}{3\varrho}}\right)$
$\displaystyle=$ $\displaystyle\ \
2\textbf{{exp}}\left(-\frac{\epsilon^{2}T^{2}\varrho}{\displaystyle
T(T+1)+\frac{\epsilon T^{2}}{3}}\right)$ $\displaystyle\leq$ $\displaystyle\ \
2\textbf{{exp}}\left(-\frac{\epsilon^{2}T^{2}\varrho}{2T^{2}}\right)=2\textbf{{exp}}\left(-\frac{\epsilon^{2}\varrho}{2}\right).$

Therefore, it suffices to hold

$\varrho\geq\frac{2}{\epsilon^{2}}\textbf{{ln}}\
\left(\frac{2}{\delta}\right)$ (138)

and get the desired result. ∎

See 2

###### Proof.

For $i)$, the results of static case have been discussed by [47, 34, 48].
Notice that $\textbf{{log}}\ n(n-1)$ is the VC-dimension of
$\boldsymbol{\mathcal{C}^{\prime}}$. For $ii)$, we start with the Bernoulli
sampling method. For any dynamic stream $\boldsymbol{C}$ form
$\boldsymbol{\mathcal{C}^{\prime}}$, we apply the first part of Lemma 2 with
$\epsilon$ and $|\boldsymbol{\mathcal{C}^{\prime}}|$

$P\Big{(}\big{|}d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C})-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime})\big{|}\geq\epsilon\Big{)}\leq\frac{\delta}{|\boldsymbol{\mathcal{C}^{\prime}}|},$
(139)

where $\boldsymbol{C}^{\prime}$ is the sampled sequence by the Bernoulli
sampling method. In the event

$\big{|}d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C})-d_{\boldsymbol{\mathcal{C}^{\prime}}}(\boldsymbol{C}^{\prime})\big{|}\leq\epsilon,\
\ \forall\ \boldsymbol{C}\in\boldsymbol{\mathcal{C}^{\prime}},$ (140)

by definition we know that $\boldsymbol{C}^{\prime}$ is an
$\epsilon$-approximation of $\boldsymbol{C}$. Taking a union bound over all
$\boldsymbol{C^{\prime}}\in\boldsymbol{\mathcal{C}^{\prime}}$, we conclude
that the probability of this event not to hold is bounded by

$\frac{\delta}{|\boldsymbol{\mathcal{C}^{\prime}}|}\cdot|\boldsymbol{\mathcal{C}^{\prime}}|=\delta,$
(141)

meaning that Bernoulli method with $\varrho$ as above is
$(\epsilon,\delta)$-representative.

The proof for reservoir method is identical, except that we apple Lemma 3. ∎

## Asymptotic Optimality of the Proposed Policy with Complete Knowledge

We discuss the asymptotic optimality of the proposed stooping time and
generation rule with the complete knowledge. The assumption for the
theoretical analysis is described. First there exist some regularity
conditions on the prior distribution $\rho_{\boldsymbol{\theta}^{\prime}}$.
Without loss of generality, we could set $\theta^{\prime}_{1}=0$ and the
unknown model parameter satisfies
$\boldsymbol{\theta}=[\theta_{2},\dots,\theta_{n}]\in\mathbb{R}^{n-1}$. The
following assumptions have been applied in the sequential design for rank
aggregation [16]. It is noteworthy that the following assumptions are mainly
for the theoretical analysis. The proposed sequential manipulation method does
not depend on the condition of
$\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})$ or the probability mass
function $g$.

######  Assumption 1.

The support

$\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})=\overline{\left\\{\
\boldsymbol{\theta}\in\mathbb{R}^{n-1}\ \Bigg{|}\
\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})>0\ \right\\}}$ (142)

is a compact set, where $\overline{\\{\cdot\\}}$ denotes the closeure of
$\\{\cdot\\}$. Besides, for any full ranking list $\boldsymbol{\pi}_{0}$ which
does not include the candidates belong to $\theta^{\prime}_{1}$,

$\left\\{\left\\{\ \boldsymbol{\theta}\in\mathbb{R}^{n-1}\ \Bigg{|}\
\boldsymbol{\pi}(\boldsymbol{\theta})=\boldsymbol{\pi}_{0}\right\\}\bigcap\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})\right\\}^{\circ}\neq\varnothing,$
(143)

where $\\{\cdot\\}^{\circ}$ represents the interior of $\\{\cdot\\}$.

This assumption assigns the bounded support
$\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})$ to the prior
distribution $\rho_{\boldsymbol{\theta}^{\prime}}$. The second part tell us
that the support $\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})$
contains a non-empty interior for every full ranking list.

######  Assumption 2.

For all $s>0$, there exists a constant $\delta>0$ such that

$\mathcal{L}\left(\boldsymbol{B}(\boldsymbol{\theta},\epsilon)\cap\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})\right)\geq\textbf{{min}}\\{\delta\epsilon^{n-1},1\\},$
(144)

where $\boldsymbol{B}(\boldsymbol{\theta},\epsilon)$ denotes the open ball
centered at $\boldsymbol{\theta}$ with radius $\epsilon$, and
$\mathcal{L}(\cdot)$ denotes the Lebesgue measure.

This assumption keeps the support
$\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})$ be non-singular.

######  Assumption 3.

The log probability mass function $\textbf{{log}}\
g_{ij}(\boldsymbol{\theta})$ is uniform continuous differentiable w.r.t.
$\boldsymbol{\theta}$ for all pairwise comparisons $(i,j)$, that is

$\underset{\begin{matrix}\scriptstyle\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}}),\\\
\scriptstyle(i,j)\in\boldsymbol{\mathfrak{C}}\end{matrix}}{\textbf{{sup}}}\
\left\|\nabla_{\boldsymbol{\theta}}\ \textbf{{log}}\
g_{ij}(\boldsymbol{\theta})\right\|<\infty.$ (145)

This assumption needs the smoothness of the likelihood function. The BTl model
satisfies this assumption.

######  Assumption 4.

The probability mass function $g$ satisfies:

$\underset{\begin{matrix}\scriptstyle\boldsymbol{\theta},\boldsymbol{\tilde{\theta}}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}}),\\\
\scriptstyle\boldsymbol{\pi}(\boldsymbol{\theta})\neq\boldsymbol{\pi}(\boldsymbol{\tilde{\theta}})\end{matrix}}{\textbf{{min}}}\
\underset{(i,j)}{\textbf{{max}}}\ \
g_{i,j}(\boldsymbol{\theta})\cdot\textbf{{log}}\frac{g_{i,j}(\boldsymbol{\theta})}{g_{i,j}(\boldsymbol{\tilde{\theta}})}>0.$
(146)

This assumption requires the distinguishability between any pair of candidates
in $\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})$, e.g. there does not
exist tie between any pair of candidates. Assumption 4 is a standard
assumption in sequential hypothesis testing, which is known as the
“indifference zone” assumption. The “indifference zone” condition tell us that
the null and alternative hypotheses are separated in the sense that the
Kullback-Leibler divergence between the two hypotheses is positive. Here the
assumption excludes the case that the true preference score is in between the
two hypotheses ($i\succ j$ and $j\succ i$). Furthermore, it means that
selecting $i\succ j$ or $j\succ i$ (the null and alternative hypothesis) will
be different.

######  Assumption 5.

The prior distribution $\rho_{\boldsymbol{\theta}^{\prime}}$ satisfies

$\displaystyle\underset{\boldsymbol{\theta}\in\\{\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})\\}^{\circ}}{\textbf{{inf}}}\
\ \rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})>0,$ (147)
$\displaystyle\underset{\ \
\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})\ \
}{\textbf{{sup}}}\ \
\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})<0.$

This assumption requires that the density function of prior distribution
$\rho_{\boldsymbol{\theta}^{\prime}}$ is positive over
$\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})$.

Considering the Assumption 1-5, the following theorem establishes a lower
bound on the minimal Bayesian risk (45)

$\mathfrak{R}^{*}=\underset{\boldsymbol{\Lambda},S}{\textbf{{inf}}}\
\mathfrak{R}(\boldsymbol{\Lambda},S).$ (45)

######  Theorem 4.

If the Assumption 1-5 hold, we have

$\underset{\chi\rightarrow 0}{\textbf{{lim inf}}}\ \
\frac{\mathfrak{R}^{*}}{\chi\mathbb{E}\left[\tau_{\chi}(\Theta)\right]}\geq
1,$ (148)

where

$\tau_{\chi}(\boldsymbol{\theta})=|\textbf{{log}}\
\chi|\cdot\left(\underset{\boldsymbol{\lambda}\in\boldsymbol{\Delta}\phantom{\boldsymbol{\tilde{\theta}}}}{\textbf{{max\phantom{f}}}}\underset{\begin{matrix}\scriptstyle\boldsymbol{\tilde{\theta}}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}}),\\\
\scriptstyle\boldsymbol{\pi}(\boldsymbol{\theta})\neq\boldsymbol{\pi}(\boldsymbol{\tilde{\theta}})\end{matrix}}{\textbf{{min}}}\
\
\sum_{(i,j)}\lambda_{i,j}g_{i,j}(\boldsymbol{\theta})\cdot\textbf{{log}}\frac{g_{i,j}(\boldsymbol{\theta})}{g_{i,j}(\boldsymbol{\tilde{\theta}})}\right)^{-1},$
(149)

and

$\mathbb{E}\left[\tau_{\chi}(\Theta)\right]=\int_{\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}\tau_{\chi}(\boldsymbol{\theta})\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})d\boldsymbol{\theta}.$
(150)

To avoid confusion, we write $\Theta$ when $\boldsymbol{\theta}$ is viewed as
a random variable.

###### Proof.

For any manipulation policy $(\boldsymbol{\Lambda},S)$ and a prior probability
density function $\rho_{\boldsymbol{\theta}^{\prime}}$, there only exist two
cases:

  * •

$\boldsymbol{E}[\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S))]\geq\chi|\textbf{{log}}\
\chi|^{2}.$ (151)

  * •

$\boldsymbol{E}[\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S))]<\chi|\textbf{{log}}\
\chi|^{2}.$ (152)

For the first case, the Bayesian risk

$\mathfrak{R}(\boldsymbol{\Lambda},S)=\mathbb{E}[\mathfrak{R}(S)+\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S))]$
(44)

satisfies

$\mathfrak{R}(\boldsymbol{\Lambda},S)\geq\chi|\textbf{{log}}\
\chi|^{2}\geq(1+o(1))\chi\mathbb{E}\left[\tau_{\chi}(\Theta)\right].$ (153)

For the second case, it is easy to see

$\mathfrak{R}(\boldsymbol{\Lambda},S)\geq\mathbb{E}[\mathfrak{R}(S)]=\chi\mathbb{E}[S].$
(154)

Therefore, proving the results equals to show that

$\underset{\chi\rightarrow 0}{\textbf{{lim inf}}}\ \
\frac{\chi\mathbb{E}[S]}{\chi\mathbb{E}\left[\tau_{\chi}(\Theta)\right]}\geq
1.$ (155)

In other words, for any $\delta>0$, there exists a $\chi_{0}>0$ such taht when
$\chi<\chi_{0}$,

$\mathbb{E}[S]\geq(1-\delta)\mathbb{E}\left[\tau_{\chi}(\Theta)\right].$ (156)

For each $\delta>0$, we set

$\tau_{\chi,\delta}(\boldsymbol{\theta})=\left(1-\frac{2}{3}\delta\right)\tau_{\chi}(\boldsymbol{\theta}),$
(157)

then

$\displaystyle\mathbb{E}[S]$ $\displaystyle\geq$ $\displaystyle\ \ \
\mathbb{E}[S|S>\tau_{\chi,\delta}(\Theta)]$ (158) $\displaystyle\geq$
$\displaystyle\ \ \
\int_{\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})\tau_{\chi,\delta}(\boldsymbol{\theta})\mathbb{P}(S>\tau_{\chi,\delta}(\Theta)|\Theta=\boldsymbol{\theta})d\boldsymbol{\theta}$
$\displaystyle=$ $\displaystyle\ \
\mathbb{E}\left[\tau_{\chi,\delta}(\Theta)\right]-\int_{\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})\tau_{\chi,\delta}(\boldsymbol{\theta})\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta)|\Theta=\boldsymbol{\theta})d\boldsymbol{\theta}$
$\displaystyle\geq$ $\displaystyle\ \
\mathbb{E}\left[\tau_{\chi,\delta}({\Theta})\right]-\tau^{\textbf{{max}}}_{\chi,\delta}\cdot\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta)),$

where $\tau^{\textbf{{max}}}_{\chi,\delta}$ is defined as

$\tau^{\textbf{{max}}}_{\chi,\delta}=\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{max}}}\
\tau_{\chi,\delta}(\boldsymbol{\theta}).$ (159)

According to Assumption 4, we know that

$\tau^{\textbf{{max}}}_{\chi,\delta}=O(|\textbf{{log}}\
\chi|)=O(\mathbb{E}\left[\tau_{\chi}({\Theta})\right]).$ (160)

Furthermore, to prove (156), it is sufficient to show

$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta))=o(1).$ (161)

The next step is to establish an upper bound for
$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta))$. Given a full ranking list
$\boldsymbol{\pi}_{0}$, we write

$\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}=\\{\boldsymbol{\theta}|\boldsymbol{\pi}(\boldsymbol{\theta})=\boldsymbol{\pi}_{0}\\}$
(162)

as all preference score which will generate the full ranking
$\boldsymbol{\pi}_{0}$. Then

$\displaystyle\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta))$ $\displaystyle=$
$\displaystyle\ \ \sum_{\boldsymbol{\pi}_{0}}\
\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})$
(163) $\displaystyle=$ $\displaystyle\ \
O(1)\cdot\underset{\boldsymbol{\pi}_{0}}{\textbf{{max}}}\
\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}).$

Then we conduct an upper bound of
$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})$
for any $\boldsymbol{\pi}_{0}$. Define an event
$\boldsymbol{E}_{\boldsymbol{\pi}_{0}}$:

$\boldsymbol{E}_{\boldsymbol{\pi}_{0}}=\left\\{\frac{\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}|\mathcal{F}_{S})}{\underset{(i,j):\boldsymbol{\Theta}_{i,j}\cap\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}=\varnothing}{\textbf{{max}}}\
\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{i,j}|\mathcal{F}_{S})}>\frac{\chi^{\frac{\delta}{10}}}{\epsilon}\right\\},$
(164)

where $\mathcal{F}_{S}=\sigma(c_{1},\dots,c_{S})$ denotes the $\sigma$-algebra
generated by $c_{1},\dots,c_{S}$, $\epsilon>0$ is a constant and the
definition of $\boldsymbol{\Theta}_{i,j}$ is

$\boldsymbol{\Theta}_{i,j}=\big{\\{}\boldsymbol{\
\theta}\in\mathbb{R}^{n}_{+}\ |\ \theta_{i}\geq\theta_{j}\
\big{\\}}\cap\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}}).$ (52)

For each
$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})$,
we have

$\displaystyle\ \
\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})$
(165) $\displaystyle=$ $\displaystyle\ \
\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}_{\boldsymbol{\pi}_{0}})+\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}^{c}_{\boldsymbol{\pi}_{0}})$

where $\boldsymbol{E}^{c}_{\boldsymbol{\pi}_{0}}$ is the complement of
$\boldsymbol{E}_{\boldsymbol{\pi}_{0}}$. Then
$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})$
can be further bounded by

$\displaystyle\ \
\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})$
(166) $\displaystyle\leq$ $\displaystyle\ \
\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}_{\boldsymbol{\pi}_{0}})+\mathbb{P}(\boldsymbol{\theta}\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}^{c}_{\boldsymbol{\pi}_{0}}).$

The first term
$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}_{\boldsymbol{\pi}_{0}})$
equals to

$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}_{\boldsymbol{\pi}_{0}})=\int_{\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}}\mathbb{P}(S\leq\tau_{\chi,\delta}(\boldsymbol{\theta}),\boldsymbol{E}_{\boldsymbol{\pi}_{0}}|\Theta=\boldsymbol{\theta})\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})d\boldsymbol{\theta}.$
(167)

Notice that the intersection of
$\\{S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})\\}$ and
$\boldsymbol{E}_{\boldsymbol{\pi}_{0}}$ will be

$\\{S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})\\}\cap\boldsymbol{E}_{\boldsymbol{\pi}_{0}}\subset\left\\{\underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\frac{\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}|\mathcal{F}_{S})}{\underset{(i,j):\boldsymbol{\Theta}_{i,j}\cap\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}=\varnothing}{\textbf{{max}}}\
\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{i,j}|\mathcal{F}_{S})}>\frac{\chi^{\frac{\delta}{10}}}{\epsilon}\right\\}.$
(168)

Then

$\mathbb{P}(S\leq\tau_{\chi,\delta}(\boldsymbol{\theta}),\boldsymbol{E}_{\boldsymbol{\pi}_{0}}|\Theta=\boldsymbol{\theta})\leq\mathbb{P}\left(\underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\frac{\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}|\mathcal{F}_{S})}{\underset{(i,j):\boldsymbol{\Theta}_{i,j}\cap\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}=\varnothing}{\textbf{{max}}}\
\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{i,j}|\mathcal{F}_{S})}>\frac{\chi^{\frac{\delta}{10}}}{\epsilon}\Bigg{|}\Theta=\boldsymbol{\theta}\right).$
(169)

The next step is to transform the right-side of the inequality to a
probability by a martingale parameterized by $\boldsymbol{\theta}$. The
corresponding results are represented by the Lemma 3 in [16].

######  Lemma 4.

Suppose that $\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})$ is a
martingale w.r.t the filtration $\\{\mathcal{F}_{S}:S\geq 1\\}$ and
probability measure $\mathbb{P}(\cdot|\Theta=\boldsymbol{\theta})$ for any
$\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}$,

$\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})=\ell_{S}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S}(\boldsymbol{\theta}^{*}_{S})-\sum_{s=1}^{S}\sum_{(i,j)}\lambda_{i,j}^{(s)}g_{i,j}(\boldsymbol{\theta})\cdot\textbf{{log}}\frac{g_{i,j}(\boldsymbol{\theta})}{g_{i,j}(\boldsymbol{\theta}^{*}_{S})}+\sum_{s=1}^{S}\sum_{(i,j)}\lambda_{i,j}^{(s)}g_{i,j}(\boldsymbol{\theta})\cdot\textbf{{log}}\frac{g_{i,j}(\boldsymbol{\theta})}{g_{i,j}(\boldsymbol{\theta}^{\prime\prime})},$
(170)

where

$\ell_{S}(\boldsymbol{\theta})=\textbf{{log}}\
\prod_{s=1}^{S}g_{ij}(\boldsymbol{\theta}),$ (171)

and

$\boldsymbol{\theta}^{*}_{S}\in\underset{\begin{matrix}\scriptstyle\boldsymbol{\tilde{\theta}}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}}),\\\
\scriptstyle\boldsymbol{\pi}(\boldsymbol{\theta})\neq\boldsymbol{\pi}(\boldsymbol{\tilde{\theta}})\end{matrix}}{\textbf{{arg\
min}}}\
\sum_{s=1}^{S}\sum_{(i,j)}\lambda^{(s)}_{i,j}g_{i,j}(\boldsymbol{\theta})\textbf{{log}}\frac{g_{i,j}(\boldsymbol{\theta})}{g_{i,j}(\tilde{\boldsymbol{\theta}})}.$
(172)

There exists a $\chi_{0}>0$ such that when $\chi$ satisfies $0<\chi<\chi_{0}$,
it holds that

$\displaystyle\ \ \mathbb{P}\left(\underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\frac{\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}|\mathcal{F}_{S})}{\underset{(i,j):\boldsymbol{\Theta}_{i,j}\cap\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}=\varnothing}{\textbf{{max}}}\
\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{i,j}|\mathcal{F}_{S})}>\frac{\chi^{\frac{\delta}{10}}}{\epsilon}\
\Bigg{|}\ \Theta=\boldsymbol{\theta}\right)$ (173) $\displaystyle\leq$
$\displaystyle\ \ \mathbb{P}\left(\underset{\begin{matrix}\scriptstyle 1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta}),\\\
\scriptstyle\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}\end{matrix}}{\textbf{{max}}}\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})\geq\frac{\delta}{2}|\textbf{{log}}\
\chi|\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right).$

With Lemma 4, we know that establishing the upper bound of (169) equals to
find an upper bound of the right hand side of (173). It is noteworthy that the
right hand side of (173) is a stochastic process, indexed by
$\boldsymbol{\theta}^{\prime\prime}$ and $S$, going beyond a certain level
($\delta|\textbf{{log}}\ \chi|/2$).

To handle the level-crossing probabilities, we introduce the Azuma-Hoeffding
inequality [3, 28] and derive the level-crossing probability by aggregating
marginal tail bounds of a random field by Lemma 5 and 6.

######  Lemma 5 (Azuma-Hoeffding Inequality).

Let $\mathcal{M}_{S}$ be a martingale w.r.t. the filtration
$\\{\mathcal{F}_{S}:S\geq 1\\}$ and
$\Delta\mathcal{M}_{S}=\mathcal{M}_{S}-\mathcal{M}_{S-1}$. Suppose that
$\Delta\mathcal{M}_{S}\in[a_{S},b_{S}]$ where $a_{S}$ and $b_{S}$ are
deterministic constants, for each $S>0$, we have

$\mathbb{P}\left(\underset{1\leq s\leq S}{\textbf{{max}}}\ \mathcal{M}_{s}\geq
S_{0}\right)\leq\textbf{{exp}}\left(-\frac{2S_{0}^{2}}{\sum_{s=1}^{S}(b_{s}-a_{s})^{2}}\right).$
(174)

######  Lemma 6.

Let
$\\{\zeta(\boldsymbol{\theta}):\boldsymbol{\theta}\in\boldsymbol{\Theta}\\}$
be a random filed over a compact set
$\boldsymbol{\Theta}\subset\mathbb{R}^{n}$ that satisfies Assumption 2, where
$\zeta(\cdot)$ has a continuous sample path almost surely under a probability
measure $\mathbb{P}$. Moreover, $\zeta(\cdot)$ has a Lipschitz-continuous
sample path in the sense that there exists a constant $\kappa$ such that for
all $\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}\in\boldsymbol{\Theta}$,

$\big{|}\zeta(\boldsymbol{\theta})-\zeta(\boldsymbol{\theta}^{\prime})\big{|}\leq\kappa\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|$
(175)

almost surely under $\mathbb{P}$. We define

$\beta(\boldsymbol{\theta},b)=\mathbb{P}\big{(}\zeta(\boldsymbol{\theta})\geq
b\big{)},$ (176)

and for all $\gamma>0$, it holds that

$\mathbb{P}\left(\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}}{\textbf{{max}}}\
\zeta(\boldsymbol{\theta})\geq
b\right)\leq\frac{\kappa^{n-1}_{L}}{\gamma^{n-1}\delta_{b}}\times\int_{\boldsymbol{\Theta}}\beta(\boldsymbol{\theta},b-\gamma)d\boldsymbol{\theta},$
(177)

where $\delta_{b}$ is the constant in Assumption 2.

With Lemma 5, we set

$\displaystyle\mathbb{P}$ $\displaystyle=$ $\displaystyle\ \
\mathbb{P}(\cdot|\Theta=\boldsymbol{\theta}),$ (178) $\displaystyle S$
$\displaystyle=$ $\displaystyle\ \ \tau_{\chi,\delta}(\boldsymbol{\theta}),$
$\displaystyle S_{0}$ $\displaystyle=$ $\displaystyle\ \
\frac{\delta}{2}|\textbf{{log}}\ \chi|-1,$ $\displaystyle\mathcal{M}_{S}$
$\displaystyle=$ $\displaystyle\ \
\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime}),$ $\displaystyle a_{S}\ \
=\ \ b_{S}$ $\displaystyle=$ $\displaystyle\ \ 2\
\underset{\begin{matrix}\scriptstyle\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}}),\\\
\scriptstyle(i,j)\in\mathfrak{C}\end{matrix}}{\textbf{{max}}}|\textbf{{log}}\
g_{i,j}(\boldsymbol{\theta})|,$

and for each $\boldsymbol{\theta}^{\prime\prime}$, we have

$\mathbb{P}\left(\underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\
\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})\geq\frac{\delta}{2}|\textbf{{log}}\
\chi|-1\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right)\leq\textbf{{exp}}\left(-\frac{2\left(\frac{\delta}{2}|\textbf{{log}}\
\chi|-1\right)^{2}}{\tau_{\chi,\delta}(\boldsymbol{\theta})\cdot
a_{1}^{2}}\right).$ (179)

According to Assumption 1 and 3, $a_{1}<\infty$ stands and

$\mathbb{P}\left(\underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\
\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})\geq\frac{\delta}{2}|\textbf{{log}}\
\chi|-1\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right)\leq\textbf{{exp}}\left(-\Omega(\delta^{2}|\textbf{{log}}\
\chi|)\right),$ (180)

where $O(\cdot)$ is the infinitesimal of the same order. Notice that

$\displaystyle\ \ \underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\
\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})-\underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\
\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime\prime})$ (181)
$\displaystyle\leq$ $\displaystyle\ \ \underset{1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta})}{\textbf{{max}}}\
|\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})-\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime\prime})|$
$\displaystyle\leq$ $\displaystyle\ \
\tau_{\chi,\delta}(\boldsymbol{\theta})\cdot\kappa_{0}\cdot\|\boldsymbol{\theta}^{\prime\prime}-\boldsymbol{\theta}^{\prime\prime\prime}\|,\
\ \ \forall\ \
\boldsymbol{\theta}^{\prime\prime},\boldsymbol{\theta}^{\prime\prime\prime}\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},$

where

$\kappa_{0}=4\
\underset{\begin{matrix}\scriptstyle\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}}),\\\
\scriptstyle(i,j)\in\mathfrak{C}\end{matrix}}{\textbf{{max}}}\
|\nabla\textbf{{log}}\ g_{ij}(\boldsymbol{\theta})|<\infty$ (182)

is the Lipschitz constant of
$\mathcal{M}_{1}(\boldsymbol{\theta}^{\prime\prime})$. Consequently,
$\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime})$ is a Lipschitz-continuous
random field w.r.t.
$\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}$.
Then adding the constraint
$\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}$
into (180) and adopting Lemma 6 give

$\displaystyle\ \ \mathbb{P}\left(\underset{\begin{matrix}\scriptstyle 1\leq
S\leq\tau_{\chi,\delta}(\boldsymbol{\theta}),\\\
\scriptstyle\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}}\end{matrix}}{\textbf{{max}}}\
\mathcal{M}_{S}(\boldsymbol{\theta}^{\prime\prime})\geq\frac{\delta}{2}|\textbf{{log}}\
\chi|-1\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right)$ (183)
$\displaystyle\leq$ $\displaystyle\ \
\textbf{{exp}}\left(-\Omega(\delta^{2}|\textbf{{log}}\
\chi|)\right)\cdot\mathcal{L}(\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})\cdot\frac{\tau_{\chi,\delta}(\boldsymbol{\theta})^{n-1}\kappa^{n-1}_{0}}{\delta_{b}}$
$\displaystyle=$ $\displaystyle\ \
\textbf{{exp}}\left(-\Omega(\delta^{2}|\textbf{{log}}\ \chi|)\right)\cdot
O(|\textbf{{log}}\ \chi|^{n-1}).$

Combine (167), (169), (173) and (183), we have

$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}_{\boldsymbol{\pi}_{0}})\leq\textbf{{exp}}\left(-\Omega(\delta^{2}|\textbf{{log}}\
\chi|)\right)\cdot O(|\textbf{{log}}\ \chi|^{n-1}).$ (184)

we have established a upper bound for first term in the right-hand side of
(166). To bound the second term, we adopt the following lemma [16].

######  Lemma 7.

For every full ranking involving $n$ candidates $\boldsymbol{\pi}_{0}$
generated by $(\boldsymbol{\Lambda},S)$, the corresponding risk is

$\mathfrak{R}_{\Theta}(\boldsymbol{R}(\boldsymbol{\Lambda},S))=\underset{(i,j)\in\boldsymbol{\mathfrak{C}}}{\sum}\mathbbm{I}[\theta^{\prime}_{i}<\theta^{\prime}_{j}]r_{i,j}+\mathbbm{I}[\theta^{\prime}_{i}>\theta^{\prime}_{j}](1-r_{i,j}).$
(43)

If

$\mathbb{E}[\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S))]\leq\epsilon,$
(185)

we have

$\mathbb{P}(\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}},\boldsymbol{E}^{c}_{\boldsymbol{\pi}_{0}})\leq\left(1+\frac{\chi^{\frac{\delta}{10}}}{\epsilon}\right)\epsilon.$
(186)

Consequently, (166) will be bounded by

$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta),\Theta\in\boldsymbol{\Theta}_{\boldsymbol{\pi}_{0}})\leq\textbf{{exp}}\left(-\Omega(\delta^{2}|\textbf{{log}}\
\chi|)\right)\cdot O(|\textbf{{log}}\
\chi|^{n-1})+\left(1+\frac{\chi^{\frac{\delta}{10}}}{\epsilon}\right)\epsilon.$
(187)

Back to (163), it holds that

$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta)\leq
O(1)\times\left\\{\textbf{{exp}}\left(-\Omega(\delta^{2}|\textbf{{log}}\
\chi|)\right)\cdot O(|\textbf{{log}}\
\chi|^{n-1})+\left(1+\frac{\chi^{\frac{\delta}{10}}}{\epsilon}\right)\epsilon\right\\}.$
(188)

Therefore, when $\chi\rightarrow 0$

$\mathbb{P}(S\leq\tau_{\chi,\delta}(\Theta)=o(1).$ (189)

We finish the proof. ∎

By the definition of asymptotic optimality of manipulation policy
$(\boldsymbol{\Lambda},S)$:

$\underset{\chi\rightarrow 0}{\textbf{{inf}}}\
\frac{\mathfrak{R}(\boldsymbol{\Lambda},S)}{\mathfrak{R}^{*}}=1,$ (46)

we know that $(\boldsymbol{\Lambda},S)$ is asymptotic optimal when
$\chi\rightarrow 0$ if

$\mathfrak{R}(\boldsymbol{\Lambda},S)=(1+o(1))\cdot\mathfrak{R}^{*}.$ (190)

Theorem 4 tells us that

$\mathfrak{R}(\boldsymbol{\Lambda},S)=(1+o(1))\cdot\mathfrak{R}^{*}=(1+o(1))\chi\mathbb{E}_{\boldsymbol{\theta}\sim\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}\left[\tau_{\chi}(\boldsymbol{\theta})\right]$
(191)

as $\chi\rightarrow 0$ is sufficient to show the asymptotic optimality of
$(\boldsymbol{\Lambda},S)$. To prove the asymptotic optimality with complete
knowledge of the proposed stopping time (49) and the generation rule solved by
(54), we require the identifiability of model to adopt the MLE and obtain the
preference score. It is worth noting that the BTL model could satisfy this
requirement.

The following theorem provides the asymptotic upper bounds for the expected
Kendall tau of the proposed manipulation policy with complete information.

######  Theorem 5.

Consider the proposed stopping time (49) and the generation rule solved by
(54) with complete knowledge, when the exploration probability $p\in(0,1)$
will be

$p\propto|\textbf{{log}}\chi|^{-\frac{1}{2}+\delta_{0}}$ (192)

for some $\delta_{0}\in\big{(}0,\frac{1}{2}\big{)}$. Then we have

$\mathbb{E}[\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S))]=O(\chi).$
(193)

###### Proof.

We first discuss the second stopping time $S_{2}$. By the generation rule
solved through (54), the expected Kendall tau at $S_{2}$ is

$\displaystyle\mathbb{E}[\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S_{2}))]$
$\displaystyle=$ $\displaystyle\ \
\mathbb{E}\underset{(i,j)\in\boldsymbol{\mathfrak{C}}}{\sum}\mathbbm{I}[\theta^{\prime}_{i}<\theta^{\prime}_{j}]r_{i,j}$
(194) $\displaystyle=$ $\displaystyle\ \
\int_{\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}\underset{(i,j):\boldsymbol{\theta}\in\boldsymbol{\Theta}_{i,j}}{\sum}\mathbb{P}\left\\{\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}_{1})>\underset{\boldsymbol{\theta}_{2}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}_{2})\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})d\boldsymbol{\theta}$
$\displaystyle=$ $\displaystyle\ \
\int_{\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}_{i,j}}{\sum}\mathbb{P}\left\\{\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}_{2})>z_{\alpha}(\chi)\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})d\boldsymbol{\theta}$

where $\boldsymbol{R}(\boldsymbol{\Lambda},S)$, $r_{i,j}$,
$\boldsymbol{\Theta}_{i,j}$, $z_{\alpha}(\chi)$,
$\ell_{S}(\boldsymbol{\theta})$ are defined as (41), (42), (52), (50) and
(171) correspondingly. The above equation can be further bounded by

$\displaystyle\ \
\mathbb{E}[\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S_{2}))]$ (195)
$\displaystyle\leq$ $\displaystyle\ \
\frac{n(n-1)}{2}\cdot\mathcal{L}\big{(}\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})\big{)}\times\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})$ $\displaystyle\ \
\times\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\underset{(i,j):\boldsymbol{\theta}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{max\phantom{p}}}}\
\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}}(\boldsymbol{\theta})>z_{\alpha}(\chi)\
\Bigg{|}\ \Theta=\boldsymbol{\theta}\right\\}.$

Here the inequality holds as

$\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\ell_{S_{2}}(\boldsymbol{\theta}_{1})\geq\ell_{S_{2}}(\boldsymbol{\theta}_{2}),\
\ \text{if}\ \ \boldsymbol{\theta}_{2}\notin\boldsymbol{\Theta}_{i,j}$ (196)

and

$\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})<\infty$ (197)

by Assumption (5). The last part of (195) can be decomposed as

$\displaystyle\ \
\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}}(\boldsymbol{\theta})>z_{\alpha}(\chi)\
\Bigg{|}\ \Theta=\boldsymbol{\theta}\right\\}$ (198) $\displaystyle\leq$
$\displaystyle\ \
\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}}(\boldsymbol{\theta})>z_{\alpha}(\chi)\
\text{and}\ S_{2}\leq\tau\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}+\mathbb{P}\left\\{S_{2}\geq\tau\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}.$

For the first term of the above right-hand side, we introduce
$S_{2}\wedge\tau=\textbf{{min}}(S_{2},\tau)$ and write

$\displaystyle\ \
\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}}(\boldsymbol{\theta})>z_{\alpha}(\chi)\
\text{and}\ S_{2}\leq\tau\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right\\}$
(199) $\displaystyle\leq$ $\displaystyle\ \
\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}\wedge\tau}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}\wedge\tau}(\boldsymbol{\theta})>z_{\alpha}(\chi)\
\Bigg{|}\ \Theta=\boldsymbol{\theta}\right\\}$

Let $\eta(\boldsymbol{\theta}^{\prime\prime})$ be a random field

$\eta(\boldsymbol{\theta}^{\prime\prime})=\ell_{S_{2}\wedge\tau}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}\wedge\tau}(\boldsymbol{\theta}),\
\ \forall\ \ \boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}.$
(200)

The marginal tail probability of $\eta(\boldsymbol{\theta}^{\prime\prime})$
can be obtained by the following lemma [16].

######  Lemma 8.

For all $\boldsymbol{\theta}^{\prime\prime}\neq\boldsymbol{\theta}$ and
constant $L>0$, we have

$\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S\wedge\tau}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S\wedge\tau}(\boldsymbol{\theta})>L\
\Bigg{|}\ \Theta=\boldsymbol{\theta}\right\\}\leq\textbf{{exp}}(-L).$ (201)

We can take $L=z_{\alpha}(\chi)-1$ and obtain

$\mathbb{P}\left\\{\eta(\boldsymbol{\theta}^{\prime\prime})>z_{\alpha}(\chi)\
\Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}\leq\textbf{{exp}}(-z_{\alpha}(\chi)+1).$
(202)

Moreover, $\eta(\boldsymbol{\theta}^{\prime\prime})$ is a Lipschitz-continuous
function as

$\eta(\boldsymbol{\theta}^{\prime\prime})-\eta(\boldsymbol{\theta}^{\prime\prime\prime})\leq|\ell_{S_{2}\wedge\tau}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}\wedge\tau}(\boldsymbol{\theta}^{\prime\prime\prime})|\leq\tau\cdot\kappa_{0}\|\boldsymbol{\theta}^{\prime\prime}-\boldsymbol{\theta}^{\prime\prime\prime}\|.$
(203)

Combining Lemma 6 and 7, we arrive at

$\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\eta(\boldsymbol{\theta}^{\prime\prime})>z_{\alpha}(\chi)\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}\leq
O\Big{(}\tau^{n-1}\textbf{{exp}}\big{(}-z_{\alpha}(\chi)\big{)}\Big{)}.$ (204)

To bound $\mathbb{P}\left\\{S_{2}\geq\tau\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}$, we need the following lemma.

######  Lemma 9.

When $\tau$ satisfies

$\tau=\Omega(|\textbf{{log}}\ \chi|^{3}),$ (205)

we have

$\mathbb{P}\left\\{S_{2}\geq\tau\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}\leq\chi^{2}.$ (206)

For the stopping time $S_{1}$, we have the similar result:

$\mathbb{P}\left\\{S_{2}\geq\tau\ \Bigg{|}\
\Theta=\boldsymbol{\theta}\right\\}\leq\chi^{2},\ \ \text{if}\
\tau=\Omega(|\textbf{{log}}\ \chi|^{3}).$ (207)

Combining (198) with (204) and Lemma 8, we have

$\displaystyle\ \
\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{2}}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{2}}(\boldsymbol{\theta})>z_{\alpha}(\chi)\
\Bigg{|}\ \Theta=\boldsymbol{\theta}\right\\}$ (208) $\displaystyle\leq$
$\displaystyle\ \
O(\chi^{2})+O\Big{(}\tau^{n-1}\textbf{{exp}}\big{(}-z_{\alpha}(\chi)\big{)}\Big{)}$
$\displaystyle=$ $\displaystyle\ \
O(\chi^{2})+O\Big{(}\textbf{{exp}}(-|\textbf{{log}}\ \chi|-|\textbf{{log}}\
\chi|^{1-\alpha}+(n-1)\textbf{{log}}\ \tau)\Big{)}$ $\displaystyle=$
$\displaystyle\ \ O(\chi^{2})+O\Big{(}\chi\textbf{{exp}}(-|\textbf{{log}}\
\chi|^{1-\alpha}+3(n-1)\textbf{{log}}\ |\textbf{{log}}\ \chi|)\Big{)}$
$\displaystyle=$ $\displaystyle\ \ o(\chi)$

and finish the analysis of $S_{2}$.

For $S_{1}$, we have

$\displaystyle\ \ \underset{(i,j):1\leq i<j\leq n}{\textbf{{max}}}\
\textbf{{exp}}\left\\{\underset{}{\textbf{{min}}}\left(\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{2}),\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{2})\right)\right\\}$ (209)
$\displaystyle\leq$ $\displaystyle\ \ \underset{(i,j):1\leq i<j\leq
n}{\sum}\textbf{{exp}}\left\\{\underset{}{\textbf{{min}}}\left(\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{2}),\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{2})\right)\right\\}$ $\displaystyle\leq$
$\displaystyle\ \ \textbf{{exp}}(-z_{\alpha}(\chi)).$

We take logarithm for the both sides of the inequality

$\underset{}{\textbf{{min}}}\left(\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{2})-\underset{}{\textbf{{min}}}\left(\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{1}),\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}_{1})\right)\right)\geq z_{\alpha}(\chi).$
(210)

Then the expected Kendall tau at $S_{1}$ will be bounded by

$\displaystyle\ \
\mathbb{E}[\mathfrak{R}(\boldsymbol{R}(\boldsymbol{\Lambda},S_{1}))]$ (211)
$\displaystyle\leq$ $\displaystyle\ \
\frac{n(n-1)}{2}\cdot\mathcal{L}\big{(}\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})\big{)}\times\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\rho_{\boldsymbol{\theta}^{\prime}}(\boldsymbol{\theta})$ $\displaystyle\ \
\times\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{sup}}}\
\underset{(i,j):\boldsymbol{\theta}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{max\phantom{p}}}}\
\mathbb{P}\left\\{\underset{\boldsymbol{\theta}^{\prime\prime}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S_{1}}(\boldsymbol{\theta}^{\prime\prime})-\ell_{S_{1}}(\boldsymbol{\theta})>z_{\alpha}(\chi)\
\Bigg{|}\ \Theta=\boldsymbol{\theta}\right\\}.$

The rest of the proof is similar to that for $S_{2}$. ∎

Now we arrive at the asymptotic optimality of the expected stopping time of
the proposed manipulation policy.

######  Theorem 6.

Consider the proposed stopping time (49) and the generation rule solved by
(54) with complete knowledge, when the exploration probability $p\in(0,1)$
will be

$p\propto|\textbf{{log}}\chi|^{-\frac{1}{2}+\delta_{0}}$ (212)

for some $\delta_{0}\in\big{(}0,\frac{1}{2}\big{)}$. Then we have

$\underset{\chi\rightarrow 0}{\textbf{{lim sup}}}\
\frac{\mathbb{E}[S]}{\mathbb{E}\left[\tau_{\chi}(\Theta)\right]}\leq 1.$ (213)

###### Proof.

First we establish a upper bound for the expectation of a stopping time $S$,
the numerator $\mathbb{E}[S]$.

$\displaystyle\mathbb{E}[S]$ $\displaystyle=$ $\displaystyle\ \
\sum_{m=0}^{\infty}\mathbb{E}\left[S\ \big{|}\
m(1+\delta)\tau_{\chi}(\Theta)\leq
S<(m+1)(1+\delta)\tau_{\chi}(\Theta)\right]$ (214) $\displaystyle\leq$
$\displaystyle\ \
(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]+\sum_{m=1}^{\infty}\mathbb{E}\left[S\
\big{|}\ m(1+\delta)\tau_{\chi}(\Theta)\leq
S<(m+1)(1+\delta)\tau_{\chi}(\Theta)\right]$ $\displaystyle\leq$
$\displaystyle\ \
(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]+(1+\delta)\cdot\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{max}}}\
\tau_{\chi}(\boldsymbol{\theta})\cdot$ $\displaystyle\ \
\phantom{(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]}\sum_{m=1}^{\infty}(m+1)\mathbb{P}(m(1+\delta)\tau_{\chi}(\Theta)\leq
S<(m+1)(1+\delta)\tau_{\chi}(\Theta))$ $\displaystyle\leq$ $\displaystyle\ \
(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]+(1+\delta)\cdot\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{max}}}\
\tau_{\chi}(\boldsymbol{\theta})\cdot$ $\displaystyle\ \
\phantom{(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]}\sum_{m=1}^{\infty}(m+1)\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{max}}}\mathbb{P}\left(m(1+\delta)\tau_{\chi}(\Theta)\leq
S<(m+1)(1+\delta)\tau_{\chi}(\Theta)\ \Big{|}\
\Theta=\boldsymbol{\theta}\right).$

We start with stopping time $S_{2}$. For $m\geq 1$,

$\displaystyle\ \ \mathbb{P}\left(m(1+\delta)\tau_{\chi}(\Theta)\leq
S_{2}<(m+1)(1+\delta)\tau_{\chi}(\Theta)\ \Big{|}\
\Theta=\boldsymbol{\theta}\right)$ (215) $\displaystyle\leq$ $\displaystyle\ \
\mathbb{P}\left(m(1+\delta)\tau_{\chi}(\Theta)\leq
S_{2}<(m+1)(1+\delta)\tau_{\chi}(\Theta),\underset{\begin{matrix}\scriptstyle
S/(1+\delta)\tau_{\chi}(\Theta)\\\
\scriptstyle\in[\delta_{2}m,m+1]\end{matrix}}{\textbf{{max}}}\
\|\boldsymbol{\hat{\theta}}_{S}-\boldsymbol{\theta}\|\leq\ |\textbf{{log}}\
\chi|^{-\delta_{1}}\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right)$
$\displaystyle\ \ +\mathbb{P}\left(\underset{\begin{matrix}\scriptstyle
S/(1+\delta)\tau_{\chi}(\Theta)\\\
\scriptstyle\in[\delta_{2}m,m+1]\end{matrix}}{\textbf{{max}}}\
\|\boldsymbol{\hat{\theta}}_{S}-\boldsymbol{\theta}\|\geq\ |\textbf{{log}}\
\chi|^{-\delta_{1}}\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right),$

where $\boldsymbol{\hat{\theta}}_{S}$ is the MLE

$\boldsymbol{\hat{\theta}}_{S}=\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{arg
sup}}}\
L\bigg{(}\boldsymbol{\theta},\boldsymbol{w}^{(S)}_{\mathcal{A}}\bigg{)},$ (48)

and the $\delta_{1}$ and $\delta_{2}$ is two constants related to exploration
probability $p\propto|\textbf{{log}}\chi|^{-\frac{1}{2}+\delta_{0}}$:

$\delta_{1}=\frac{\delta_{0}}{8},\ \ \delta_{2}=|\textbf{{log}}\
\chi|^{-\frac{\delta_{0}}{2}}.$ (216)

The following lemma show a upper bound of the second term in the preceding
display.

######  Lemma 10.

Suppose $\boldsymbol{\lambda}^{(S)}=\\{\lambda^{(S)}_{i,j}\\}$ is a generation
rule at $S$ step and $\\{\epsilon_{\boldsymbol{\lambda},T_{1},T_{2}}\\}$,
$\\{\delta_{T_{1},T_{2}}\\}$ is two sequences of real numbers such that

$\displaystyle\underset{\begin{matrix}\scriptstyle T_{1}\leq S\leq T_{2},\\\
\scriptstyle(i,j)\in\mathfrak{C}\end{matrix}}{\textbf{{min}}}\
\lambda^{(S)}_{i,j}\geq\epsilon_{\boldsymbol{\lambda},T_{1},T_{2}},$ (217)
$\displaystyle\underset{T_{1}\rightarrow\infty}{\textbf{{lim}}}\
T_{1}\cdot\epsilon_{\boldsymbol{\lambda},T_{1},T_{2}}\cdot\delta^{2}_{T_{1},T_{2}}=\infty.$

Then, it holds that

$\mathbb{P}\left(\underset{T_{1}\leq S\leq T_{2}}{\textbf{{max}}}\
\|\boldsymbol{\hat{\theta}}_{S}-\boldsymbol{\theta}\|\geq\delta_{T_{1},T_{2}}\
\Bigg{|}\
\Theta=\boldsymbol{\theta}\right)\leq\textbf{{exp}}\Big{(}-\Omega\big{(}T_{1}\epsilon^{2}_{\boldsymbol{\lambda},T_{1},T_{2}}\delta^{4}_{T_{1},T_{2}}\big{)}\Big{)}\times
O\big{(}T_{2}^{n}\big{)}.$ (218)

When

$T_{1}=m(1+\delta)\delta_{2}\tau_{\chi}(\boldsymbol{\theta}),\ \
T_{2}=m(1+\delta)\tau_{\chi}(\boldsymbol{\theta}),\ \
\epsilon_{\boldsymbol{\lambda},T_{1},T_{2}}=\Omega\Big{(}|\textbf{{log}}\chi|^{-\frac{1}{2}+\delta_{0}}\Big{)},\
\ \delta^{2}_{T_{1},T_{2}}=|\textbf{{log}}\chi|^{-\delta_{1}},$ (219)

we have

$\displaystyle\ \ \mathbb{P}\left(\underset{\begin{matrix}\scriptstyle
S/(1+\delta)\tau_{\chi}(\Theta)\\\
\scriptstyle\in[\delta_{2}m,m+1)\end{matrix}}{\textbf{{max}}}\
\|\boldsymbol{\hat{\theta}}_{S}-\boldsymbol{\theta}\|\geq\ |\textbf{{log}}\
\chi|^{-\delta_{1}}\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right)$ (220)
$\displaystyle\leq$ $\displaystyle\ \
\textbf{{exp}}\left(-\Omega\Big{(}m(1+\delta)\delta_{2}\tau_{\chi}(\boldsymbol{\theta})|\textbf{{log}}\chi|^{-4\delta_{1}}|\textbf{{log}}\chi|^{-1+2\delta_{0}}\Big{)}\right)\times
O\Big{(}m^{n-1}|\textbf{{log}}\chi|^{n-1}\Big{)}$ $\displaystyle=$
$\displaystyle\ \
\textbf{{exp}}\left(-\Omega\Big{(}m|\textbf{{log}}\chi|^{2\delta_{0}-4\delta_{1}}\delta_{2}\Big{)}\right)\times
O\Big{(}m^{n-1}|\textbf{{log}}\chi|^{n-1}\Big{)}$ $\displaystyle=$
$\displaystyle\ \
\textbf{{exp}}\left(-\Omega\Big{(}m|\textbf{{log}}\chi|^{\delta_{0}}\Big{)}\right)\times
O\Big{(}m^{n-1}|\textbf{{log}}\chi|^{n-1}\Big{)}.$

Now we analyze the first term on the right-hand side of (215). For $m\geq 1$,
$S_{2}>m(1+\delta)\tau_{\chi}(\boldsymbol{\theta})$ implies that there exists
a pairwise comparison $(i,j)$ such that

$\left|\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2})\right|\leq z_{\alpha}(\chi),$ (221)

where $S=m(1+\delta)\tau_{\chi}(\boldsymbol{\theta})$. Without loss of
generality, let $\boldsymbol{\theta}\in\boldsymbol{\Theta}_{i,j}$ and
$S_{2}>m(1+\delta)\tau_{\chi}(\boldsymbol{\theta})$ further shows that

$\ell_{S}(\boldsymbol{\theta})-\underset{\boldsymbol{\theta}_{2}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2})\leq z_{\alpha}(\chi).$ (222)

Consequently, the first term on the right-hand side of (215) will be bounded

$\displaystyle\ \ \mathbb{P}\left(m(1+\delta)\tau_{\chi}(\Theta)\leq
S_{2}<(m+1)(1+\delta)\tau_{\chi}(\Theta),\underset{\begin{matrix}\scriptstyle
S/(1+\delta)\tau_{\chi}(\Theta)\\\
\scriptstyle\in[\delta_{2}m,m+1)\end{matrix}}{\textbf{{max}}}\
\|\boldsymbol{\hat{\theta}}_{S}-\boldsymbol{\theta}\|\leq\ |\textbf{{log}}\
\chi|^{-\delta_{1}}\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right)$ (223)
$\displaystyle\leq$ $\displaystyle\ \
\mathbb{P}\left(\ell_{S}(\boldsymbol{\theta})-\underset{\boldsymbol{\theta}_{2}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2})\leq
z_{\alpha}(\chi),\underset{\begin{matrix}\scriptstyle
S/(1+\delta)\tau_{\chi}(\Theta)\\\
\scriptstyle\in[\delta_{2}m,m+1)\end{matrix}}{\textbf{{max}}}\
\|\boldsymbol{\hat{\theta}}_{S}-\boldsymbol{\theta}\|\leq\ |\textbf{{log}}\
\chi|^{-\delta_{1}}\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right).$

The preceding display can be bounded by the following lemma.

######  Lemma 11.

Suppose that the generation rule
$\boldsymbol{\lambda}^{*}(\boldsymbol{\hat{\theta}}_{S})$ is solved by (54):

$\boldsymbol{\lambda}^{*}(\boldsymbol{\hat{\theta}}_{S})\in\underset{\
\boldsymbol{\lambda}\in\boldsymbol{\Delta}\phantom{\tilde{1}}}{\textbf{{arg\
max}}}\
\underset{\begin{matrix}\scriptstyle\boldsymbol{\tilde{\theta}}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})\\\
\scriptstyle\boldsymbol{\pi}(\boldsymbol{\hat{\theta}}_{S})\neq\boldsymbol{\pi}(\boldsymbol{\tilde{\theta}})\end{matrix}}{\textbf{{min\phantom{g}}}}\
\sum_{(i,j)}\lambda_{i,j}\cdot
g_{i,j}(\boldsymbol{\hat{\theta}}_{S})\cdot\textbf{{log}}\frac{g_{i,j}(\boldsymbol{\hat{\theta}}_{S})}{g_{i,j}(\boldsymbol{\tilde{\theta}})}.$
(54)

If $\boldsymbol{\lambda}^{*}(\boldsymbol{\hat{\theta}}_{S})$ is adopted with
probability $1-o(1)$ uniformly for
$S\in[m(1+\delta)\delta_{2}\tau_{\chi}(\boldsymbol{\theta}),m(1+\delta)\tau_{\chi}(\boldsymbol{\theta})]$,
we have

$\displaystyle\ \
\mathbb{P}\left(\ell_{S}(\boldsymbol{\theta})-\underset{\boldsymbol{\theta}_{2}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2})\leq
z_{\alpha}(\chi),\underset{\begin{matrix}\scriptstyle
S/(1+\delta)\tau_{\chi}(\Theta)\\\
\scriptstyle\in[\delta_{2}m,m+1)\end{matrix}}{\textbf{{max}}}\
\|\boldsymbol{\hat{\theta}}_{S}-\boldsymbol{\theta}\|\leq\ |\textbf{{log}}\
\chi|^{-\delta_{1}}\ \Bigg{|}\ \Theta=\boldsymbol{\theta}\right)$ (224)
$\displaystyle\leq$ $\displaystyle\ \
\textbf{{exp}}\Big{(}-\Omega(m|\textbf{{log}}\ \chi|)\Big{)}\times
O\Big{(}|\textbf{{log}}\ \chi|^{n-1}m^{n-1}\Big{)},$

where $S=m(1+\delta)\tau_{\chi}(\boldsymbol{\theta})$.

Combining the results of Lemma 9 and Lemma 10, (215) will be bounded as

$\displaystyle\ \ \mathbb{P}\left(m(1+\delta)\tau_{\chi}(\Theta)\leq
S_{2}<(m+1)(1+\delta)\tau_{\chi}(\Theta)\ \Big{|}\
\Theta=\boldsymbol{\theta}\right)$ (225) $\displaystyle\leq$ $\displaystyle\ \
\left(\textbf{{exp}}\Big{(}-\Omega(m|\textbf{{log}}\
\chi|)\Big{)}+\textbf{{exp}}\Big{(}-\Omega(m|\textbf{{log}}\
\chi|^{\delta_{0}})\Big{)}\right)\times O\Big{(}|\textbf{{log}}\
\chi|^{n-1}m^{n-1}\Big{)}.$

Aggregating the preceding display with (214), the expectation of the stopping
time $S_{2}$ will be bounded

$\displaystyle\mathbb{E}[S_{2}]$ $\displaystyle\leq$ $\displaystyle\ \
(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]+(1+\delta)\cdot\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{max}}}\
\tau_{\chi}(\boldsymbol{\theta})\cdot$ (226) $\displaystyle\ \
\phantom{(1+\delta)}\sum_{m=1}^{\infty}(m+1)\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{max}}}\mathbb{P}\left(m(1+\delta)\tau_{\chi}(\Theta)\leq
S<(m+1)(1+\delta)\tau_{\chi}(\Theta)\ \Big{|}\
\Theta=\boldsymbol{\theta}\right)$ $\displaystyle\leq$ $\displaystyle\ \
(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]+O(|\textbf{{log}}\ \chi|)\times$
$\displaystyle\ \
\phantom{(1+\delta)}\sum_{m=1}^{\infty}(m+1)\left(\textbf{{exp}}\Big{(}-\Omega(m|\textbf{{log}}\
\chi|)\Big{)}+\textbf{{exp}}\Big{(}-\Omega(m|\textbf{{log}}\
\chi|^{\delta_{0}})\Big{)}\right)\times O\Big{(}|\textbf{{log}}\
\chi|^{n-1}m^{n-1}\Big{)}$ $\displaystyle\leq$ $\displaystyle\ \
(1+\delta)\mathbb{E}[\tau_{\chi}(\Theta)]+o(|\textbf{{log}}\ \chi|).$

The preceding display is the desired conclusion for the asymptotic optimality
of $S_{2}$.

Next we proceed to the case of $S_{1}$. Notice that the event $S_{1}>S$
implies that

$\sum_{(i,j)}\textbf{{exp}}\left(\textbf{{min}}\left(\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\boldsymbol{\theta}^{\prime})}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2}),\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\boldsymbol{\theta}^{\prime})}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2})\right)\right)>\textbf{{exp}}(-z_{\alpha}(\chi))$
(227)

which further conducts

$\displaystyle\ \ n(n-1)\cdot\underset{(i,j)}{\textbf{{max}}}\
\textbf{{exp}}\left(\textbf{{min}}\left(\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\boldsymbol{\theta}^{\prime})}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2}),\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\textbf{{Supp}}(\boldsymbol{\theta}^{\prime})}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2})\right)\right)$ (228) $\displaystyle>$
$\displaystyle\ \ \textbf{{exp}}(-z_{\alpha}(\chi)).$

It means that there exist a pairwise comparison $(i,j)$ such that

$\left|\underset{\boldsymbol{\theta}_{1}\in\boldsymbol{\Theta}_{i,j}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{1})-\underset{\boldsymbol{\theta}_{2}\in\in\boldsymbol{\Theta}_{j,i}}{\textbf{{sup}}}\
\ell_{S}(\boldsymbol{\theta}_{2})\right|\leq z_{\alpha}(\chi)+\textbf{{log}}\
n(n-1).$ (229)

Then the analysis process of $S_{1}$ is similar to $S_{2}$ by replacing
$z_{\alpha}(\chi)$ with $z_{\alpha}(\chi)+\textbf{{log}}\ n(n-1)$. ∎

## Proof of Theorem 3

The following proposition [10] shows the strong duality for the Wasserstein
DRO problem that we investigate in this paper:

$\underset{\
\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\
\textbf{{max\phantom{p}}}}\
\underset{\mathbb{Q}\in\boldsymbol{\mathfrak{U}}^{\gamma}(\mathbb{P})}{\textbf{{sup}}}\
\mathbb{E}_{\boldsymbol{q}\sim\mathbb{Q}}\left[L(\boldsymbol{\theta},\boldsymbol{q})\right],$
(59)

This strong duality result ensures that the inner supremum admits a
reformulation which is a simple, univariate optimization problem. Note that
there exists the other strong duality result of Wasserstein DRO [25].

######  Proposition 2.

Let $d:\mathbb{R}\times\mathbb{R}\rightarrow[0,\infty]$ be a lower semi-
continuous cost function satisfying $d(p,\ q)=0$ whenever $p=q$. For
$\lambda\geq 0$ and loss function $\ell$

$\ell(\boldsymbol{\theta},p_{i,j})=p_{i,j}\cdot\textbf{{log}}~{}g_{i,j}(\boldsymbol{\theta}),$
(230)

where $f_{(i,j)}(\boldsymbol{\theta})$ is the probabilistic mass function of
pairwise comparison $(i,j)$, we define

$\psi_{\lambda,\ell}(\boldsymbol{\theta},q_{i,j}):=\underset{q_{i,j}\in\mathbb{R}_{+}}{\textbf{{sup}}}\
\Big{\\{}\ \ell(\boldsymbol{\theta},q_{i,j})-\lambda\cdot d(p_{i,j},q_{i,j})\
\Big{\\}}.$ (231)

Then it holds that

$\underset{\mathbb{Q}\in\boldsymbol{\mathfrak{U}}^{\gamma}(\mathbb{P})}{\textbf{{sup}}}\
\
\mathbb{E}_{\boldsymbol{q}\sim\mathbb{Q}}\big{[}L\big{(}\boldsymbol{\theta},\boldsymbol{q}\big{)}\big{]}=\underset{\lambda\geq
0}{\ \textbf{{min\phantom{p}}}}\left\\{\
\lambda\gamma+\sum_{(i,j)}\psi_{\lambda,\ell}(\boldsymbol{\theta},q_{i,j})\
\right\\}$ (232)

With the strong duality, we have the following result.

See 3

###### Proof.

Let $\Delta_{ij}=q_{ij}-p_{ij}$ where
$\boldsymbol{q}=(q_{1,2},\dots,q_{n,n-1})\in\mathbb{R}^{N}_{+}$. We define
$\psi_{\lambda,\ell}(\boldsymbol{\theta})$ as

$\displaystyle\psi_{\lambda,\ell}(\boldsymbol{\theta})$ $\displaystyle=$
$\displaystyle\ \ \underset{\boldsymbol{q}}{\textbf{{sup}}}\
\underset{(i,j)}{\sum}\ \Big{\\{}\ell(\boldsymbol{\theta},\
q_{ij})-\lambda\big{[}d(p_{i,j},\ q_{i,j})\big{]}^{2}\Big{\\}}$ (233)
$\displaystyle=$ $\displaystyle\ \ \underset{\boldsymbol{q}}{\textbf{{sup}}}\
\underset{(i,j)}{\sum}\
\left\\{q_{ij}\cdot\textbf{{log}}~{}g_{(i,j)}(\boldsymbol{\theta})-\lambda\big{|}p_{ij}-q_{ij}\big{|}^{2}\right\\}$
$\displaystyle=$ $\displaystyle\ \ \underset{(i,j)}{\sum}\
\underset{\Delta_{ij}\in\mathbb{R}}{\textbf{{sup}}}\
\Big{(}\Delta_{ij}b_{ij}-\lambda\Delta_{ij}^{2}+p_{ij}b_{ij}\Big{)},$

where

$b_{i,j}=\textbf{{log}}~{}g_{i,j}(\boldsymbol{\theta}),$ (234)

and the third equality holds due to $\psi_{\lambda,\ell}(\boldsymbol{\theta})$
is a decomposable function. Expanding (233), we can simplify
$\psi_{\lambda,\ell}(\boldsymbol{\theta})$ as below:

$\displaystyle\psi_{\lambda,\ell}(\boldsymbol{\theta})$ $\displaystyle=$
$\displaystyle\ \
\big{\langle}\boldsymbol{p},\boldsymbol{b}\big{\rangle}+\underset{(i,j)}{\sum}\
\underset{\Delta_{ij}\in\mathbb{R}}{\textbf{{sup}}}\
\big{(}\Delta_{ij}b_{ij}-\lambda\Delta_{ij}^{2}\big{)}$ (235) $\displaystyle=$
$\displaystyle\ \
\left\\{\begin{array}[]{lc}\displaystyle\langle\boldsymbol{p},\
\boldsymbol{b}\rangle+\frac{1}{4\lambda}\|\boldsymbol{b}\|^{2}_{2},&\ \text{if
}\ \lambda>0,\\\\[10.0pt] \infty,&\ \text{if }\ \lambda=0.\end{array}\right.$

Next, we investigate the duality of (59) with Proposition 2. As
$\psi_{\lambda,\ell}(\boldsymbol{\theta},\ q_{i,j})=\infty$ when $\lambda=0$,
the dual formulation of the supremum in (59) would be

$\displaystyle\ \ \ \
\underset{\mathbb{Q}\in\boldsymbol{\mathfrak{U}}^{\gamma}(\mathbb{P})}{\textbf{{sup}}}\
\mathbb{E}_{\boldsymbol{q}\sim\mathbb{Q}}\left[L(\boldsymbol{\theta},\boldsymbol{q})\right]$
(236) $\displaystyle=\ \ \underset{\lambda\geq 0}{\textbf{{min}}}\ \
\Bigg{\\{}\lambda\gamma+\psi_{\lambda,\ell}(\boldsymbol{\theta})\Bigg{\\}}$
$\displaystyle=\ \ \underset{\lambda>0}{\textbf{{min}}}\ \
\Bigg{\\{}\lambda\gamma+\langle\boldsymbol{p},\
\boldsymbol{b}\rangle+\frac{1}{4\lambda}\|\boldsymbol{b}\|^{2}_{2}\Bigg{\\}}.$

By the definition of $\boldsymbol{b}$, we know that

$L(\boldsymbol{\theta},\ \boldsymbol{p})=\big{\langle}\boldsymbol{p},\
\boldsymbol{b}\big{\rangle}$ (237)

Moreover, notice that the right hand side of (236) is a convex function which
approaches infinity when $\lambda\rightarrow\infty$, the global optimal of it
can be obtained uniquely via the first order optimality condition as

$\frac{\partial}{\partial\lambda}\Bigg{\\{}\
\lambda\gamma+\langle\boldsymbol{p},\
\boldsymbol{b}\rangle+\frac{1}{4\lambda}\|\boldsymbol{b}\|^{2}_{2}\
\Bigg{\\}}=0,$ (238)

and the optimal dual variable is

$\lambda^{*}_{\gamma}=\frac{\|\boldsymbol{b}\|_{2}}{2\sqrt{\gamma}}.$ (239)

Substituting $\lambda^{*}_{\gamma}$ and $\boldsymbol{b}$ into (236), we have

$\displaystyle\ \
\underset{\mathbb{Q}\in\boldsymbol{\mathfrak{U}}^{\gamma}(\mathbb{P})}{\textbf{{sup}}}\
\mathbb{E}_{\boldsymbol{q}\sim\mathbb{Q}}\left[L(\boldsymbol{\theta},\boldsymbol{q})\right]$
(240) $\displaystyle=$ $\displaystyle\ \
\sqrt{\gamma}\cdot\|\boldsymbol{b}\|_{2}+\langle\boldsymbol{p},\
\boldsymbol{b}\rangle$ $\displaystyle=$ $\displaystyle\ \ \sqrt{\
\gamma\underset{(i,j)}{\sum}[\textbf{{log}}~{}g_{i,j}(\boldsymbol{\theta})]^{2}}+\underset{(i,j)}{\sum}p_{i,j}\textbf{{log}}~{}g_{i,j}(\boldsymbol{\theta}).$

When we sepicify the probability mass function of $(i,j)$ as

$g_{i,j}(\boldsymbol{\theta})=\frac{e^{\theta_{i}}}{e^{\theta_{i}}+e^{\theta_{j}}},$

we can obtain the formulation of $h$ for the BTL model. ∎

## Details of Algorithm 3 and 4

Input : the probability mass function $g$, the support set
$\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})$, the incomplete
knowledge $\boldsymbol{S}$ and the solution accuracy $\epsilon$.

1 Initialization:  $\displaystyle\mu_{\text{min}}=0,$
$\displaystyle\mu_{\text{max}}=\mu_{\infty}=\textbf{{max}}\left\\{m\cdot\|\boldsymbol{z}\|_{\infty},\sqrt{\frac{m}{2\beta}}\cdot\|\boldsymbol{z}\|_{2}\right\\},$
where $\boldsymbol{z}=[z_{1,2},\dots,z_{n,n-1}]$
$z_{ij}=\underset{\boldsymbol{\theta}\in\textbf{{Supp}}(\rho_{\boldsymbol{\theta}^{\prime}})}{\textbf{{max}}}\
-\textbf{{log}}~{}g_{i,j}(\boldsymbol{\theta}).$

2while  _$|\mu_{\text{max}}-\mu_{\text{min}}| >\epsilon\cdot\mu_{\infty}$_ do

3 $\displaystyle\mu$ $\displaystyle=$ $\displaystyle\ \ \ \
\frac{1}{2}(\mu_{\text{min}}+\mu_{\text{max}}),$
$\displaystyle\boldsymbol{\theta}(\mu)$ $\displaystyle=$ $\displaystyle\ \ \ \
\textbf{{SimplexProjection}}(\boldsymbol{\theta}^{(0)},\mu),$
$\displaystyle\nabla\mathcal{H}(\mu)$ $\displaystyle=$ $\displaystyle\ \ \ \
\frac{1}{2}\|\boldsymbol{\theta}(\mu)-\boldsymbol{\theta}_{\mathcal{A}}\|^{2}_{2}-\beta.$

4 if  _$\nabla\mathcal{H}(\mu) >0$_ then

5 $\mu_{\text{min}}=\mu,$

6 else

7 $\mu_{\text{max}}=\mu.$

8 end if

9

10 end while

11

12Update  $\mu=\frac{1}{2}\big{(}\mu_{\text{min}}+\mu_{\text{max}}\big{)}.$

13Solve the distributionally robust estimation
$\boldsymbol{\hat{\theta}}=\textbf{{SimplexProjection}}(\boldsymbol{\theta}^{(0)},\mu)$

Output : the distributionally robust estimation $\boldsymbol{\hat{\theta}}$.

Algorithm 3 Robust Estimation

Input : the partial dual problem (241)

1 Initialization: the initial step size $\eta_{0}$, the maximum iteration
number $T_{1}$, $\boldsymbol{U}=[n]$, $s=0$, $v=0$.

2for  _$t=0$ to $T_{1}-1$_ do

3
$\boldsymbol{\theta}^{(t+1)}=\boldsymbol{\theta}^{(t)}-\eta_{t}\nabla\mathcal{L}(\boldsymbol{\theta}^{(t)},\mu).$

4 end for

5

6while  _$\boldsymbol{U}\neq\varnothing$_ do

7 Pick $k\in\boldsymbol{U}$ at random and separate $\boldsymbol{U}$ as
$\displaystyle\boldsymbol{G}=\\{\ j\in\boldsymbol{U}\ |\
\theta^{(T_{1})}_{j}\geq\theta^{(T_{1})}_{k}\ \\},$
$\displaystyle\boldsymbol{L}=\\{\ j\in\boldsymbol{U}\ |\
\theta^{(T_{1})}_{j}<\theta^{(T_{1})}_{k}\ \\}.$

8 Set  $\Delta v=|\boldsymbol{G}|,\ \Delta
s=\sum_{j\in\boldsymbol{G}}\hat{\theta}^{(T_{1})}_{j}.$

9 if  _$(s+\Delta s)-(v+\Delta v) <1$_ then

10 $s\leftarrow s+\Delta s,\ v\leftarrow v+\Delta v,\
\boldsymbol{U}\leftarrow\boldsymbol{L}$

11 else

12 $\boldsymbol{U}\leftarrow\boldsymbol{G}/\\{k\\}.$

13 end if

14

15 end while

16

17
$\boldsymbol{\hat{\theta}}^{(T_{1})}=\big{[}\boldsymbol{\theta}^{(T_{1})}-\gamma\cdot\boldsymbol{1}\big{]}_{+},$
where  $\gamma=\frac{s-1}{v}.$

Output : $\boldsymbol{\hat{\theta}}^{(T_{1})}$.

Algorithm 4 $\textbf{{SimplexProjection}}(\boldsymbol{\theta}^{(0)},\mu)$

######  Definition 8 ($p$-Wasserstein distance).

Let $p\in[1,\infty]$. The $p$-Wasserstein distance between distributions
$\mathbb{P},\ \mathbb{Q}\in\mathcal{P}(\boldsymbol{\Omega})$ is defined as

$\displaystyle\mathcal{W}_{p}\ (\mathbb{P},\
\mathbb{Q})=\left\\{\begin{array}[]{ll}\Bigg{(}\underset{\gamma\in\Gamma(\mathbb{P},\
\mathbb{Q})}{\textbf{{min}}}{\int}_{\boldsymbol{\Omega}\times\boldsymbol{\Omega}}\big{[}d(\boldsymbol{p},\
\boldsymbol{q})\big{]}^{p}\gamma\big{(}\mathrm{d}\boldsymbol{p},\
\mathrm{d}\boldsymbol{q}\big{)}\Bigg{)}^{\frac{1}{p}},&p<\infty\\\\[20.0pt]
\underset{\gamma\in\Gamma(\mathbb{P},\ \mathbb{Q})}{\textbf{{inf}}}\
\underset{\vphantom{\gamma\in\Gamma(\mathbb{P},\
\mathbb{Q})}\boldsymbol{\Omega}\times\boldsymbol{\Omega}}{\gamma\textnormal{-}\textbf{{ess
sup}}}\ d\big{(}\boldsymbol{p},\
\boldsymbol{q}\big{)},&p=\infty,\end{array}\right.$

where $\Gamma(\mathbb{P},\ \mathbb{Q})$ denotes the set of all Borel
probability distributions on $\boldsymbol{\Omega}\times\boldsymbol{\Omega}$
with marginal distributions $\mathbb{P}$ and $\mathbb{Q}$,
$d:\boldsymbol{\Omega}\times\boldsymbol{\Omega}\rightarrow\mathbb{R}_{+}$ is a
nonnegative function, and $\gamma\textnormal{-}\textbf{{ess sup}}$ expresses
the essential supremum of $d(\cdot,\ \cdot)$ with respect to the measure
$\gamma$.

The Wasserstein distance arises in the problem of optimal transport [40, 49]:
for any coupling $\gamma\in\Gamma(\mathbb{P},\ \mathbb{Q})$, the conditional
distribution $\gamma_{\boldsymbol{w}|\boldsymbol{w}^{\prime}}$ can be viewed
as a randomized overhead for ‘transporting’ a unit quantity of some material
from a random location $\boldsymbol{w}\sim\mathbb{P}$ to another location
$\boldsymbol{w}^{\prime}\sim\mathbb{Q}$. If the cost of transportation from
$\boldsymbol{w}\in\boldsymbol{\Omega}$ to
$\boldsymbol{w}^{\prime}\in\boldsymbol{\Omega}$ is given by
$[d(\boldsymbol{w},\boldsymbol{w}^{\prime})]^{p}$, $\mathcal{W}_{p}\
(\mathbb{P},\ \mathbb{Q})$ will be the minimum expected transport cost [42].

Introducing a dual variable $\mu$ for the constraint
$1/2\|\boldsymbol{\theta}-\boldsymbol{\theta}_{\mathcal{A}}\|_{2}^{2}\leq\beta$,
we solve the original optimization problem (62) by maximizing its dual
problem. Furthermore, the strong duality stands for (62) as the Slater
condition is satisfied by $\boldsymbol{\theta}_{\mathcal{A}}$. Then the
standard min-max swap will be performed as

$\displaystyle\underset{\mu\geq 0}{\ \
\textbf{{max}}\phantom{f}}\mathcal{H}(\mu)$ $\displaystyle:=$ $\displaystyle\
\ \underset{\boldsymbol{\theta}\in\mathbb{R}^{n}}{\textbf{{inf}}}\ \Big{\\{}\
\mathcal{L}_{1}(\boldsymbol{\theta},\mu)\ \Big{|}\ \boldsymbol{\theta}\succeq
0,\ \boldsymbol{1}^{\top}\boldsymbol{\theta}=1\ \Big{\\}}$ (241)
$\displaystyle=$ $\displaystyle\ \
\underset{\boldsymbol{\theta}\in\mathbb{R}^{n}}{\textbf{{inf}}}\Big{\\{}\frac{\mu}{2}\big{\|}\boldsymbol{\theta}-\boldsymbol{\theta}_{\mathcal{A}}\big{\|}^{2}_{2}-\mu\beta+h(\boldsymbol{\theta})\
\Big{|}\ \boldsymbol{\theta}\succeq
0,\boldsymbol{1}^{\top}\boldsymbol{\theta}=1\Big{\\}}.$

By Corollary 4.4.5 of Chapter VI in [27], we know that

$\displaystyle\nabla\mathcal{H}(\mu)$ $\displaystyle=$ $\displaystyle\ \
\nabla_{\mu}\ \mathcal{L}_{1}(\boldsymbol{\theta}(\mu),\mu)$ (242)
$\displaystyle=$ $\displaystyle\ \ \nabla_{\mu}\
\Bigg{\\{}\frac{\mu}{2}\big{\|}\boldsymbol{\theta}(\mu)-\boldsymbol{\theta}_{\mathcal{A}}\big{\|}^{2}_{2}-\mu\beta+h(\boldsymbol{\theta}(\mu))\Bigg{\\}}$
$\displaystyle=$ $\displaystyle\ \
\frac{1}{2}\big{\|}\boldsymbol{\theta}(\mu)-\boldsymbol{\theta}_{\mathcal{A}}\big{\|}^{2}_{2}-\beta.$

If $\nabla\mathcal{H}(\mu)$ can be solved efficiently, it is possible to
binary search with $\log(1/\varepsilon)$ iterations and the accuracy
$\varepsilon$ for the $\mu^{*}$ as
$\|\nabla\mathcal{H}(\mu^{*})\|\leq\varepsilon$.

Given $\mu^{*}$ and denote the probabilistic simplex as

$\Delta=\\{\ \boldsymbol{\theta}\in\mathbb{R}^{n}\ |\
\boldsymbol{\theta}\succeq 0,\ \boldsymbol{1}^{\top}\boldsymbol{\theta}=1\
\\},$ (243)

the corresponding $\boldsymbol{\theta}(\lambda^{*})$ can be obtained by the
projected sub-gradient descent which minimizes the objective $\mathcal{L}$
with the following sequence $\\{\boldsymbol{\theta}^{(t)}\\}_{t=1}^{T}$,

$\boldsymbol{\theta}^{(t+1)}=\textbf{Proj}_{\Delta}\big{(}\boldsymbol{\theta}^{(t)}-\eta_{t}\nabla\mathcal{L}(\boldsymbol{\theta}^{(t)},\mu^{*})\big{)},$
(244)

where $\nabla\mathcal{L}(\boldsymbol{\theta}^{(t)},\mu^{*})$ is the
(sub)gradient of $\mathcal{L}(\boldsymbol{\theta},\mu^{*})$ at
$\boldsymbol{\theta}^{(t)}$, $\eta_{t}$ is the positive step size and
$\textbf{Proj}_{\Delta}(\boldsymbol{\varphi})$ is the Euclidean projection of
$\boldsymbol{\varphi}$ onto $\Delta$, i.e. the solution of

$\underset{\boldsymbol{\theta}\in\mathbb{R}^{n}}{\textbf{{min}}}\
\frac{1}{2}\|\boldsymbol{\varphi}-\boldsymbol{\theta}\|^{2}_{2},\
\textit{s.t.}\ \boldsymbol{\theta}\succeq 0,\
\boldsymbol{1}^{\top}\boldsymbol{\theta}=1.$ (245)

The projection $\boldsymbol{\theta}^{(t+1)}$ has the form

$\displaystyle\boldsymbol{\theta}^{(t+1)}$ $\displaystyle=$ $\displaystyle\ \
[\boldsymbol{\varphi}^{(t+1)}-\gamma\boldsymbol{1}]_{+}$ (246)

where $[\cdot]_{+}=\textbf{{max}}\\{\cdot,0\\}$ and $\gamma$ holds

$\gamma=\frac{1}{\rho}\left(\sum_{i=1}^{\rho}\varphi^{(t+1)}_{i}-1\right),$
(247) $\rho=\textbf{{max}}\left\\{j\in[n]\ \left|\
\psi_{j}-\frac{1}{j}\left(\sum_{r=1}^{j}\psi_{r}-1\right)>0\right.\right\\},$
(248)

where $\boldsymbol{\psi}$ is the sorted version of
$\boldsymbol{\varphi}^{(t+1)}$ with descent order.

## Details of Algorithm 5

Input : The MLE estimator $\boldsymbol{\hat{\theta}}$ and the total number of
iterations $L$.

1

2Initialization: A starting point $\boldsymbol{\lambda}^{0}$ and a constant
$c_{0}>0$.

3for  _$l=1$ to $L$_ do

4 Solve the maximizing sub-problem
$\boldsymbol{\theta}(\boldsymbol{\lambda}^{l-1})\in\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}:r(\boldsymbol{\theta})\neq
r(\boldsymbol{\hat{\theta}})}{\textbf{{arg max}}}\
-g(\boldsymbol{\theta};\boldsymbol{\lambda}^{l-1},\boldsymbol{\hat{\theta}}),$
where
$g(\boldsymbol{\theta};\boldsymbol{\lambda}^{l-1},\boldsymbol{\hat{\theta}})=\underset{(i,j)\in\mathcal{A}}{\sum}\
\lambda^{l-1}_{i,j}D^{i,j}(\boldsymbol{\hat{\theta}}\|\boldsymbol{\theta}).$

5 Calculate the sub-gradient $d(\boldsymbol{\lambda}^{l-1})$
$d(\boldsymbol{\lambda}^{l-1})=\big{(}d(\boldsymbol{\lambda}^{l-1})_{1,2},\dots,d(\boldsymbol{\lambda}^{l-1})_{n,n-1}\big{)},$
where
$d(\boldsymbol{\lambda}^{l-1})_{i,j}=-D^{i,j}(\boldsymbol{\hat{\theta}}\|\boldsymbol{\theta}(\boldsymbol{\lambda}^{l-1})).$

6 Solve the minimizing sub-problem
$\boldsymbol{\lambda}^{l}\in\underset{\boldsymbol{\lambda}\in\Delta}{\textbf{{arg
min}}}\ \eta_{l}\langle
d(\boldsymbol{\lambda}^{l-1}),\boldsymbol{\lambda}\rangle+D(\boldsymbol{\lambda}\|\boldsymbol{\lambda}^{l-1}),$
where $\eta_{l}=c_{0}/\sqrt{~{}l~{}}$ and
$D(\boldsymbol{\lambda}\|\boldsymbol{\lambda}^{l-1})=\underset{(i,j)\in\mathcal{A}}{\sum}\lambda_{i,j}\log\frac{\lambda_{i,j}}{\lambda^{l-1}_{i,j}}$

7 end for

8The categorical distribution is obtained through averaging the sequence
$\\{\boldsymbol{\lambda}^{1},\dots,\boldsymbol{\lambda}^{L}\\}$ like
$\boldsymbol{\hat{\lambda}}=\frac{1}{L}\sum_{l=1}^{L}\boldsymbol{\lambda}^{l}.$

Output : The categorical distribution $\boldsymbol{\hat{\lambda}}$.

Algorithm 5
$\textbf{{MirrorDescent}}(\boldsymbol{S},f,\boldsymbol{\Theta}^{\beta}_{\mathcal{A}},\boldsymbol{\theta}^{(m)})$

$\boldsymbol{\hat{\lambda}}^{(m)}=\underset{\phantom{\boldsymbol{\hat{\theta}}^{(m)}}\boldsymbol{\lambda}\in\Delta\phantom{\boldsymbol{\hat{\theta}}^{(m)}}}{\textbf{{arg
max}}}\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}:\boldsymbol{\pi}(\boldsymbol{\theta})\neq\boldsymbol{\pi}(\boldsymbol{\hat{\theta}}^{(m)})}{\
\textbf{{min}\phantom{g}}}\
g(\boldsymbol{\theta},\boldsymbol{\lambda};\boldsymbol{\hat{\theta}}^{(m)}),$

where $\boldsymbol{\lambda}=(\lambda_{1,2},\dots,\lambda_{n,n-1})$,

$g(\boldsymbol{\theta},\boldsymbol{\lambda};\boldsymbol{\hat{\theta}}^{(m)})=\underset{(i,j)\in\mathcal{A}}{\sum}\
\lambda_{i,j}D^{i,j}(\boldsymbol{\hat{\theta}}^{(m)}\|\boldsymbol{\theta}),$

and $D^{i,j}(\boldsymbol{\hat{\theta}}\|\boldsymbol{\theta})$ is the Kullback-
Leibler (KL) divergence from $f(\boldsymbol{\theta};(i,j),y)$ to
$f(\boldsymbol{\hat{\theta}};(i,j),y)$ as

$D^{i,j}(\boldsymbol{\hat{\theta}}\|\boldsymbol{\theta})=\underset{y\in\\{-1,1\\}}{\sum}f(\boldsymbol{\hat{\theta}};(i,j),y)\log\frac{f(\boldsymbol{\hat{\theta}};(i,j),y)}{f(\boldsymbol{\theta};(i,j),y)}.$
$\boldsymbol{\theta}(\boldsymbol{\lambda}^{(l-1)})\in\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}:r(\boldsymbol{\theta})\neq
r(\boldsymbol{\hat{\theta}})}{\textbf{{arg max}}}\
-g(\boldsymbol{\theta};\boldsymbol{\lambda}^{(l-1)},\boldsymbol{\hat{\theta}}),$

$\boldsymbol{\theta}(\boldsymbol{\lambda}^{(l-1)})\in\underset{\boldsymbol{\theta}\in\boldsymbol{\Theta}^{\beta}_{\mathcal{A}}:\boldsymbol{\pi}(\boldsymbol{\theta})\neq\boldsymbol{\pi}(\boldsymbol{\hat{\theta}})}{\textbf{{arg
min}}}\
g(\boldsymbol{\theta};\boldsymbol{\lambda}^{(l-1)},\boldsymbol{\hat{\theta}}),$
$\displaystyle\ \ \underset{\delta\geq 0}{\textbf{{max}}}\ \
\mathcal{G}(\delta)$ $\displaystyle:=$ $\displaystyle\ \
\underset{\boldsymbol{\theta}\in\mathbb{R}^{n}}{\textbf{{inf}}}\ \Big{\\{}\
\mathcal{L}_{2}(\boldsymbol{\theta},\delta)\ \Big{|}\
\boldsymbol{\theta}\succeq 0,\
\boldsymbol{1}^{\top}\boldsymbol{\theta}=1,\boldsymbol{\pi}(\boldsymbol{\theta})\neq\boldsymbol{\pi}(\boldsymbol{\hat{\theta}})\
\Big{\\}}$ $\displaystyle=$ $\displaystyle\
\underset{\boldsymbol{\theta}\in\mathbb{R}^{n}}{\textbf{{inf}}}\ \left\\{\
\begin{matrix}\displaystyle\frac{\delta}{2}\big{\|}\boldsymbol{\theta}-\boldsymbol{\theta}_{\mathcal{A}}\big{\|}^{2}_{2}-\delta\beta\\\\[5.0pt]
+\
g(\boldsymbol{\theta};\boldsymbol{\lambda}^{(l-1)},\boldsymbol{\hat{\theta}})\end{matrix}\
\left|\ \begin{matrix}\boldsymbol{\theta}\succeq
0,\boldsymbol{1}^{\top}\boldsymbol{\theta}=1,\\\\[10.0pt]
\boldsymbol{\pi}(\boldsymbol{\theta})\neq\boldsymbol{\pi}(\boldsymbol{\hat{\theta}})\end{matrix}\right.\right\\}$

Balance the choice probability of the selection rule

$\lambda^{(m)}_{i,j}=p\cdot\frac{2}{n(n-1)}+(1-p)\hat{\lambda}^{(m)}_{i,j},\
i,j\in[n],\ i\neq j.$

is chosen such that $\sum_{i}\theta^{(t+1)}_{i}=1$. With Lemma 2 of [21], we
know that $\gamma$ plays the same role as the unique index $i$ which

$\displaystyle\sum_{j=1}^{i}\Big{(}\varphi^{(t+1)}_{j}-\varphi^{(t+1)}_{i}\Big{)}<1$
(249)
$\displaystyle\sum_{j=1}^{i+1}\Big{(}\varphi^{(t+1)}_{j}-\varphi^{(t+1)}_{i+1}\Big{)}\geq
1,$

or $i=n$ if there does not exist any index satisfies (249).

The projection
$\boldsymbol{\theta}(\lambda)=[\theta_{i}(\lambda),\dots,\theta_{n}(\lambda)]$
has the form

$\theta_{i}(\lambda)=\left[\tilde{\theta}_{i}-\frac{1}{\lambda}\frac{\partial
F(\boldsymbol{\theta})}{\partial\theta_{i}}\right]$ (250)

finding the the Euclidean projection of vector
$\boldsymbol{v}(\lambda)=[v_{1},\dots,v_{n}]\in\mathbb{R}^{n}$

$v_{i}=$ (251)

onto the probabilistic simplex. Then the projection
$\boldsymbol{\theta}(\lambda)$ has the form
$\theta_{i}(\lambda)=(v_{i}-\eta)_{+}$ for some $\eta\in\mathbb{R}$ where
$\eta$ is chosen such that $\boldsymbol{\theta}(\lambda)$ will satisfy the
probabilistic unit sphere constraint. It is equivalent to find the unique
index $i$ such that

$\sum_{j=1}^{i}(v_{j}-v_{i})<1,\ \text{and}\
\sum_{j=1}^{i+1}(v_{j}-v_{i+1})\geq 1,$ (252)

and $i=n$ if there does not exist such an index. By (252), we know that

$v_{j}-\eta\left\\{\begin{array}[]{ll}\geq 0,&j\leq i,\\\ \leq 0,&j\geq
i\end{array}\right.$ (253)