# Simultaneously Learning Stochastic and Adversarial Bandits under the
Position-Based Model

Cheng Chen1, Canzhe Zhao2, Shuai Li 2 Corresponding author

###### Abstract

Online learning to rank (OLTR) interactively learns to choose lists of items
from a large collection based on certain click models that describe users’
click behaviors. Most recent works for this problem focus on the stochastic
environment where the item attractiveness is assumed to be invariant during
the learning process. In many real-world scenarios, however, the environment
could be dynamic or even arbitrarily changing. This work studies the OLTR
problem in both stochastic and adversarial environments under the position-
based model (PBM). We propose a method based on the follow-the-regularized-
leader (FTRL) framework with Tsallis entropy and develop a new self-bounding
constraint especially designed for PBM. We prove the proposed algorithm
simultaneously achieves $O(\log{T})$ regret in the stochastic environment and
$O(m\sqrt{nT})$ regret in the adversarial environment, where $T$ is the number
of rounds, $n$ is the number of items and $m$ is the number of positions. We
also provide a lower bound of order $\Omega(m\sqrt{nT})$ for adversarial PBM,
which matches our upper bound and improves over the state-of-the-art lower
bound. The experiments show that our algorithm could simultaneously learn in
both stochastic and adversarial environments and is competitive compared to
existing methods that are designed for a single environment.

## Introduction

Learning to rank is widely used in online web search and recommender systems
which selects a small group of items to present in a limited number of
positions after a user starts a search session (Liu et al. 2009). Online
learning to rank (OLTR) is to learn the best ranking policy through user
interactions and aims to maximize user satisfaction, _e.g._ the number of user
clicks, during the learning period. To understand the click signals received
from users on given ranked lists of items, many click models are introduced
and studied (Chuklin, Markov, and Rijke 2015). One of the most popular click
models adopted in the industry is the position-based model (PBM) (Richardson,
Dominowska, and Ragno 2007) due to its simplicity and effectiveness to
characterize the click rate as a product of item attractiveness and position
bias. PBM is studied in OLTR setting with theoretical analysis on regret
(Lagrée, Vernade, and Cappé 2016; Komiyama, Honda, and Takeda 2017), which is
in expectation the difference of the received clicks from the clicks of the
best policy. Some other works in OLTR study the cascade model (Kveton et al.
2015a; Li et al. 2016; Zong et al. 2016) and general click model (Zoghi et al.
2017; Lattimore et al. 2018; Li, Lattimore, and Szepesvári 2019).

Most existing works in OLTR focus on the stochastic environment where the item
attractiveness and position examination probabilities, if any, are assumed to
be fixed through the learning process. However, this usually is a strong
assumption in real applications where the item attractiveness could change
dynamically, like the clothes interest of users might periodically change
across seasons. The algorithms designed in the stochastic environment might
fail to converge if the stochastic assumptions do not hold. This motivates the
study of adversarial environment where the involved samples are arbitrary on a
bounded domain. Usually the regret guarantee of algorithms designed under
adversarial environment can only be $O(\sqrt{T})$, even in the stochastic
environment whose best algorithm can achieve a much better regret of
$O(\log(T))$. It is an interesting topic in online learning if there is an
algorithm that can achieve $O(\sqrt{T})$ regret if run in the adversarial
environment and $O(\log(T))$ regret if run in the stochastic environment. This
problem is also called best-of-both-worlds (BOBW). Some works study this
problem in classical multi-armed bandit problem (MAB) (Bubeck and Slivkins
2012; Seldin and Slivkins 2014; Auer and Chiang 2016; Seldin and Lugosi 2017;
Wei and Luo 2018; Zimmert and Seldin 2019) and combinatorial MAB (CMAB) with
semi-bandit feedback (Zimmert, Luo, and Wei 2019). It is an open question if
we can design BOBW algorithms in OLTR whose adversarial formulation needs to
be well deliberated first. In this work we hope to answer this question under
the commonly adopted PBM.

We propose an algorithm for OLTR under PBM based on the follow-the-
regularized-leader (FTRL) framework to simultaneously learn in stochastic and
adversarial environments. Though OLTR under PBM can be formulated as a special
case of CMAB by regarding the pair of an item and a position as a base arm,
the direct application of existing studies does not hold. One of the main
challenges is that the commonly defined suboptimality gap could be negative in
the PBM setting, making it impossible to follow the existing self-bounding
technique in (Zimmert, Luo, and Wei 2019; Zimmert and Seldin 2019; Wei and Luo
2018). For this, we deliberately design a suboptimality gap, which is non-
trival and quite different from the commonly defined suboptimality gap. We
also build a new form of self-bounding constraint for PBM based on the
property of the proposed suboptimality gap. Also, the structure of PBM could
have Tsallis entropy as the potential function and the corresponding
regularized leader can be computed efficiently, compared with the hybrid
regularizer in the previous work (Zimmert, Luo, and Wei 2019). We prove our
algorithm could achieve $O(\log T)$ regret in the stochastic environment and
$O(\sqrt{T})$ regret in the adversarial environment, verifying its
simultaneous learning ability in both environments.

Furthermore, we provide a regret lower bound $\Omega(m\sqrt{nT})$ for OLTR
under PBM. This improves the state-of-the-art lower bound $\Omega(\sqrt{mnT})$
(Lattimore et al. 2018) which is analyzed under document-based model, a
special case of PBM. Our lower bound matches our upper bound, showing the
optimality of both. Table 1 shows a full comparison of our work with most
related works.

The experiments show that our algorithm outperforms the baselines in
adversarial environments while is competitive with TopRank (Lattimore et al.
2018) and PMED (Komiyama, Honda, and Takeda 2017) in stochastic environments.
The results show the simultaneous learning ability of our algorithm in both
environments.

|  Regret Bound
(Stochastic) |  Regret Bound
(Adversarial) |  Original Model
---|---|---|---
Kale, Reyzin, and Schapire (2010) |  - |  $\displaystyle O\left(m\sqrt{nT\log(n)}\right)$ |  Bandits for Ordered Slates
Bubeck and Cesa-Bianchi (2012) |  - |  $\displaystyle O\left(m\sqrt{nT}\right)$ |  CMAB with semi-bandit feedback
Lagrée, Vernade, and Cappé (2016) |  $\displaystyle O\left(\frac{n}{\beta_{m}\Delta}\log(T)\right)$ |  - |  PBM with known position bias
Zoghi et al. (2017) |  $\displaystyle O\left(\frac{m^{3}n}{\Delta}\log(T)\right)$ |  - |  General Click Model
Lattimore et al. (2018) |  $\displaystyle O\left(\frac{mn}{\Delta}\log(T)\right)$
$\displaystyle O\left(\sqrt{m^{3}nT\log(T)}\right)$
$\displaystyle\Omega\left(\sqrt{mnT}\right)$ |  $\displaystyle\Omega\left(\sqrt{mnT}\right)$ |  General Click Model
Li, Lattimore, and Szepesvári (2019) |  $\displaystyle O\left(m\sqrt{nT\log(nT)}\right)$ |  - |  General Click Model with Linear Features
Zimmert, Luo, and Wei (2019) |  $\displaystyle O\left(\frac{m^{2}n}{\Delta_{\beta}\Delta}\log(T)\right)$ |  $\displaystyle O\left(m\sqrt{nT}\right)$ |  CMAB with semi-bandit feedback
Ours |  $\displaystyle O\left(\frac{mn}{\Delta_{\beta}\Delta}\log(T)\right)$ |  $\displaystyle O\left(m\sqrt{nT}\right)$
$\Omega\left(m\sqrt{nT}\right)$ |
Table 1: This table compares regret bounds of related works when their results
are applied to OLTR under PBM for both stochastic and adversarial
environments. $T$ is the number of total rounds, $m$ is the number of
positions and $n$ is the number of items. $\Delta$ is the minimal gap between
the attractiveness of the best $m$ items. $\Delta_{\beta}$ is the minimal gap
between position examination probabilities.

#### Related Work

The study of OLTR under PBM has received many interests. For the stochastic
environment, Lagrée, Vernade, and Cappé (2016) studies PBM but assumes the
position examination probabilities are known or could be pre-computed from
historical data. This assumption is a bit unrealistic and does not account for
possible drift of position bias. Komiyama, Honda, and Takeda (2017) remove
this requirement but only provides an asymptotic regret bound. With rank-1
structure, PBM with unknown position bias can also be solved using methods in
rank-1 bandits (Katariya et al. 2017) though their setting is originally
designed to select one item each round. Some works study a general class of
click models with PBM as a special case (Zoghi et al. 2017; Lattimore et al.
2018; Li, Lattimore, and Szepesvári 2019). They distill a set of assumptions
that are satisfied by common click models including the cascade model and PBM.
The algorithms designed on this general click model are more robust than that
on PBM. All the above algorithms study only the stochastic environment and
might be brittle when the stochastic assumption is violated.

For the adversarial environment, PBM is first studied by Kale, Reyzin, and
Schapire (2010) as an ordered slate model. They solve it by a variant of
multiplicative-weights algorithm and prove a regret upper bound
$O(m\sqrt{n\log(n)T})$, $O(\sqrt{\log(n)})$ worse than ours. Bubeck and Cesa-
Bianchi (2012) show that OSMD with a $0$-potential function can achieve
$O(m\sqrt{nT})$ regret, but their method need to know the time horizon.
Radlinski, Kleinberg, and Joachims (2008) study a ranked bandit problem using
the greedy idea to select items one-by-one, which can only give approximation
guarantees. It is extended to metric space by considering item contexts
(Slivkins, Radlinski, and Gollapudi 2013). Other studies include online
optimization over the permutahedron (Ailon 2014; Ailon, Hatano, and Takimoto
2016), which corresponds to PBM with $m=n$ and PBM with full-information
feedback (Cohen and Hazan 2015).

The model of OLTR under PBM can be regarded as a special case of combinatorial
semi-bandits (Gai, Krishnamachari, and Jain 2012; Chen, Wang, and Yuan 2013;
Kveton et al. 2015b; Combes et al. 2015; Combes, Magureanu, and Proutiere
2017; Zimmert, Luo, and Wei 2019; Neu and Bartók 2013; Neu 2015; Audibert,
Bubeck, and Lugosi 2014) with specific combinatorial constraints. Most
existing works study either stochastic or adversarial environment.

For the BOBW algorithms, many study this topic for MAB (Bubeck and Slivkins
2012; Seldin and Slivkins 2014; Auer and Chiang 2016; Seldin and Lugosi 2017;
Wei and Luo 2018) where Zimmert and Seldin (2019) show that FTRL with
$\frac{1}{2}$-Tsallis entropy can achieve optimal regret bounds for both
stochastic and adversarial environments. Zimmert, Luo, and Wei (2019) study
combinatorial semi-bandits by a novel hybrid regularizer but only show the
optimality in two special cases for the stochastic environment, full
combinatorial set and $m$-set. Other BOBW works include prediction with expert
advice (Koolen, Grünwald, and van Erven 2016; Mourtada and Gaïffas 2019),
linear bandits (Lee et al. 2021), online convex optimization (Cutkosky and
Boahen 2017) and Markov decision process (Jin and Luo 2020). Our work focuses
on the BOBW under PBM.

## Setting

This section introduces both stochastic and adversarial environments of OLTR
under PBM.

Suppose there are $n$ items with item set $[n]=\\{1,2,\dots,n\\}$ and $m$
positions ($m\leq n$). In each round $t$, the learner selects an ordered list
$I_{t}=(i_{t,1},i_{t,2},\dots,i_{t,m})$ consisting of $m$ distinct items,
where $i_{t,j}$ denotes the item placed at position $j$ in round $t$. Note
that this problem can be formulated as a special case of combinatorial semi-
bandits and the action list $I_{t}$ can be written as a subpermutation matrix
$X_{t}\in{\mathcal{X}}$ where

$\displaystyle{\mathcal{X}}=\left\\{X\in\\{0,1\\}^{n\times
m}~{}\Bigg{|}~{}\sum_{i=1}^{n}X_{i,j}=1,\forall j\in[m];\right.$
$\displaystyle\left.~{}\sum_{j=1}^{m}X_{i,j}\leq 1,\forall i\in[n]\right\\}$

is the action set and $X_{i,j}$ denotes whether to put item $i$ on position
$j$.

Lattimore and Szepesvári (2020) introduce the adversarial setting of PBM as
follows. For each round $t$ and position $k\in[m]$, the environment secretly
chooses $S_{t,k}$ as subset of $[n]$. The reward of round $t$ is defined as
$r_{t}=\sum_{k=1}^{m}\mathds{1}\left\\{i_{t,k}\in S_{t,k}\right\\}$ where
$I_{t}$ is the selected action list at time $t$. The feedback is the positions
of the clicked items. Notice that this model can be reformulated as a
combinatorial semi-bandit problem. At round $t$, the environment secretly
chooses all loss matrices $\ell_{t}\in\\{0,1\\}^{n\times m}$ for any $t$
before the game where $\ell_{t,i,j}=0$ means there is no loss (or there is a
click) if placing item $i$ at position $j$ in round $t$. After selecting
$I_{t}$, the algorithm receives a loss of $\langle X_{t},\ell_{t}\rangle$ and
observes semi-bandit feedback $\ell_{t,i,j}$ for those $(i,j)$ such that
$X_{t,i,j}=1$. The goal of the algorithm is to minimize the expected
cumulative pseudo-regret

$\displaystyle R(T)=\mathbb{E}\left[\sum_{t=1}^{T}\langle
X_{t}-x^{\ast},\ell_{t}\rangle\right]\,,$ (1)

where
$x^{*}\in\operatorname*{arg\,min}_{x\in\mathcal{X}}\mathbb{E}\left[\sum^{T}_{t=1}\langle
x,\ell_{t}\rangle\right]$ is the best action and the expectation is taken over
the randomness of both the algorithm and the environment.

For the stochastic environment, each item $i\in[n]$ is associated with an
(unknown) attractiveness $\alpha_{i}\in[0,1]$ and each position $j\in[m]$ is
associated with an (unknown) examination probability $\beta_{j}\in(0,1]$.
Without loss of generality, we assume
$\alpha_{1}>\alpha_{2}>\cdots>\alpha_{m}>\alpha_{m+1}\geq\alpha_{m+2}\geq\cdots\geq\alpha_{n}$
and $\beta_{1}>\beta_{2}>\cdots>\beta_{m}>\beta_{m+1}=0$. Let
${\mathcal{H}}_{t}$ be the $\sigma$-algebra containing all the history
$(\ell_{1},X_{1},\ldots,\ell_{t},X_{t})$ by the end of round $t$. In the
stochastic environment, all elements in the loss matrix $\ell_{t}$ are
${\mathcal{H}}_{t-1}$-conditionally independent whose $(i,j)$-entry is drawn
from Bernoulli distribution $\mathrm{Ber}(1-\alpha_{i}\beta_{j})$ like
previous works (Komiyama, Honda, and Takeda 2017; Lagrée, Vernade, and Cappé
2016; Chuklin, Markov, and Rijke 2015). In this case, $x_{i,j}^{\ast}$ is
actually $\delta_{i,j}$ which is $1$ if and only if $i=j$. The goal of the
algorithm is also to minimize the expected cumulative pseudo-regret Eq. (1).

#### Notations

Throughout this paper, we use $I_{j}^{*}$ to denote the item selected by the
best action $x^{\ast}$ at position $j$, or $x^{\ast}_{I_{j}^{\ast},j}=1$. For
a given set $\mathcal{X}$, let $\mathds{1}\\{\mathcal{X}\\}$ be the indicator
function and $\mathcal{I}_{\mathcal{X}}(x)$ be the characteristic function
which is $\infty$ if $x\notin\mathcal{X}$ and $0$ otherwise. Let
$\mathrm{Conv}({\mathcal{X}})$ be the convex hull of ${\mathcal{X}}$. We use
${\bf{1}}_{n}$ to denote the $n$-dimensional vector whose entries are all
$1$s. The conditional expectation
$\mathbb{E}\left[\cdot\mid{\mathcal{H}}_{t-1}\right]$ is abbreviated as
$\mathbb{E}_{t}\left[\cdot\right]$. For the stochastic environment, let
$\Delta=\min_{i\in[m]}\\{\alpha_{i}-\alpha_{i+1}\\}$ be the minimal gap
between the attractiveness of top $m$ items and
$\Delta_{\beta}=\min_{j\in[m]}\\{\beta_{j}-\beta_{j+1}\\}$ be the minimal gap
between any two position examination probabilities.

## Algorithm

Algorithm 1 FTRL-PBM

Input: ${\mathcal{X}}$.

1: ${\hat{L}}_{0}=\mathbf{0}_{n\times m}$, $\eta_{t}=1/(2\sqrt{t})$.

2: for $t=1,\dots,T$ do

3: Compute  $\displaystyle
x_{t}=\operatorname*{arg\,min}_{x\in\mathrm{Conv}({\mathcal{X}})}\langle
x,{\hat{L}}_{t-1}\rangle+\frac{1}{\eta_{t}}\Psi(x)\,;$

4: Sample $X_{t}\sim P(x_{t})$;

5: Observe $\ell_{t,i,j}$ for those $(i,j)$-th entries satisfying
$X_{t,i,j}=1$;

6: Compute the loss estimator
$\hat{\ell}_{t,i,j}=\frac{\ell_{t,i,j}\cdot\mathds{1}\left\\{X_{t,i,j}=1\right\\}}{x_{t,i,j}}$;

7: Compute $\hat{L}_{t}=\hat{L}_{t-1}+{\hat{\ell}}_{t}$.

8: end for

This section presents our main algorithm, ${\tt FTRL\mathchar 45\relax PBM}$,
in Algorithm 1 for both stochastic and adversarial environments under PBM. Our
${\tt FTRL\mathchar 45\relax PBM}$ algorithm follows the general follow-the-
regularized leader (FTRL) framework, whose main idea is to follow the action
which minimizes the regularized cumulative loss of the past rounds. Since the
complete loss vectors cannot be observed in the bandit setting, usually an
unbiased estimator $\hat{\ell}_{t}$ satisfying
$\mathbb{E}_{t}\left[\hat{\ell}_{t}\right]=\ell_{t}$ would serve as a
surrogate.

Specifically, our algorithm ${\tt FTRL\mathchar 45\relax PBM}$ keeps track of
the cumulative estimated loss
${\hat{L}}_{t}=\sum^{t}_{s=1}\hat{\ell}_{s}\in\mathbb{R}_{+}^{n\times m}$ and
initializes it as a zero vector (line 1). At each round $t$, ${\tt
FTRL\mathchar 45\relax PBM}$ first computes a regularized leader $x_{t}$ in
the convex hull of the action set $\mathrm{Conv}({\mathcal{X}})$ by

$\displaystyle
x_{t}=\operatorname*{arg\,min}_{x\in\mathrm{Conv}({\mathcal{X}})}\langle
x,{\hat{L}}_{t-1}\rangle+\frac{1}{\eta_{t}}\Psi(x)$ (2)

where $\Psi(x)$ is the regularizer (line 3). Here we take the $1/2$-Tsallis
entropy

$\displaystyle\Psi(x)=\sum_{i}-\sqrt{x_{i}}$

as our regularizer, which is shown optimal for BOBW MAB (Zimmert and Seldin
2019). For BOBW semi-bandits, the optimal algorithm adopts a hybrid
regularizer (Zimmert, Luo, and Wei 2019), which is complicated and may be not
efficient for PBM.

Then ${\tt FTRL\mathchar 45\relax PBM}$ samples an action $X_{t}\sim P(x_{t})$
from ${\mathcal{X}}$ (line 4) where $P(x_{t})$ satisfies $\mathbb{E}_{X\sim
P(x_{t})}\left[X\right]=x_{t}$. We follow previous works (Kale, Reyzin, and
Schapire 2010; Helmbold and K Warmuth 2009) to construct $P(x)$. The method is
to first complete matrix $x_{t}$ into a doubly stochastic matrix $M_{t}$,
which is a convex combination of permutation matrices by Birkhoff’s theorem,
and then decompose matrix $M_{t}$ into its convex combination of at most
$n^{2}$ permutation matrices by Algorithm 1 of (Helmbold and K Warmuth 2009).
The time complexity of whole sampling procedure is of order $O(n^{4.5})$ and
the details can be found in Appendix D.

After observing the semi-bandit feedback for the selected action $X_{t}$, we
can construct the unbiased estimator for the loss vector as

$\displaystyle\hat{\ell}_{t,i,j}=\frac{\ell_{t,i,j}\cdot\mathds{1}\left\\{X_{t,i,j}=1\right\\}}{x_{t,i,j}}$

for the $(i,j)$-th entry (line 6). Then the cumulative estimated loss
${\hat{L}}$ is updated (line 7).

### Optimization

It remains to solve the constrained convex optimization problem (2). To avoid
computing the expensive projection onto the feasible set, we consider the
Frank-Wolfe (FW) (Frank, Wolfe et al. 1956) algorithm (a.k.a., conditional
gradient method) due to its projection-free property. Specifically, the Frank-
Wolfe algorithm only needs to compute the solution of a linear optimization
over the feasible set in each iteration. We present the optimization algorithm
for Problem (2) in Algorithm 2.

Notice that Algorithm 2 requires to solve a linear optimization over
$\mathrm{Conv}({\mathcal{X}})$. This could be viewed as finding a maximal
matching in a bipartite graph where edge $e_{i,j}$ has weight $r^{(k)}_{i,j}$
since $\mathrm{Conv}({\mathcal{X}})$ is the convex hull of truncated
permutation matrices and it could be solved by the Hopcroft–Karp algorithm
(Hopcroft and Karp 1973) in $O(n^{2.5})$ time. Thus the total computational
cost of Algorithm 2 is $O(n^{2.5}K)$ time where $K$ is the maximal iteration
number of Frank-Wolfe algorithm.

Algorithm 2 Frank-Wolfe Algorithm for Problem (2)

Input: $x_{t-1}$, $\mathrm{Conv}({\mathcal{X}})$, $\eta_{t}$, $\Psi(\cdot)$,
${\hat{L}}_{t-1}$, $K$.

1: Let $x^{(1)}=x_{t-1}$,
$f(\cdot)=\langle\cdot,{\hat{L}}_{t-1}\rangle+\eta_{t}^{-1}\Psi(\cdot)$

2: for $k=1,\dots,K$ do

3: Compute $r^{(k)}:=\nabla f(x^{(k)})$.

4: Compute
$s^{(k)}:=\operatorname*{arg\,min}_{s\in\mathrm{Conv}({\mathcal{X}})}\langle
s,r^{(k)}\rangle$.

5: Let $\gamma:=\frac{2}{1+k}$.

6: Update $x^{(k+1)}:=(1-\gamma)x^{(k)}+\gamma s^{(k)}$.

7: end for

8: return $x^{(K)}$.

## Regret Analysis

This section provides regret upper bounds of our algorithm ${\tt FTRL\mathchar
45\relax PBM}$ for both stochastic and adversarial environments, together with
an improved lower bound for PBM, which also matches our upper bound. We also
discuss the relationship between our results and previous works.

### Upper Bounds

We give the regret upper bounds of ${\tt FTRL\mathchar 45\relax PBM}$ for each
of the adversarial and stochastic environments and provide proof sketches.

######  Theorem 1.

For the adversarial environment, the regret of our ${\tt FTRL\mathchar
45\relax PBM}$ algorithm satisfies

$\displaystyle R(T)$ $\displaystyle\leq 3m+2m\log
T+\sum_{t=1}^{T}\left(\frac{3}{\sqrt{t}}\sum_{j=1}^{m}\sum_{i\neq
I^{*}_{j}}\sqrt{{\mathbb{E}}[x_{t,i,j}]}\right)$
$\displaystyle=O(m\sqrt{nT})\,.$

Though this regret bound matches that of OSMD with $0$-potential (Bubeck and
Cesa-Bianchi 2012) and BOBW semi-bandits (Zimmert, Luo, and Wei 2019), these
two methods have some shortcomings compared to ours. OSMD with $0$-potential
needs to know the time horizon. Existing doubling trick methods lead to
additional logarithmic factors in either stochastic or adversarial setting
(Besson and Kaufmann 2018). BOBW semi-bandits could be inefficient under PBM
since they use a hybrid regularizer.

###### Proof sketch.

Denote $\Psi_{t}(\cdot)=\frac{1}{\eta_{t}}\Psi(\cdot)$. Let
$\Phi_{t}(\cdot)=\max_{x\in\mathrm{Conv}({\mathcal{X}})}\ \langle
x,\cdot\rangle-\Psi_{t}(x)$ be the Fenchel conjugate of
$\Psi_{t}+{\mathcal{I}}_{\mathrm{Conv}({\mathcal{X}})}$. Like the standard
FTRL analysis (Chapter 28 of (Lattimore and Szepesvári 2020)), the regret can
be decomposed as a sum of the stability term and the regularization penalty
term

$\displaystyle R(T)=$
$\displaystyle\underbrace{{\mathbb{E}}\left[\sum_{t=1}^{T}\langle
X_{t},\ell_{t}\rangle+\Phi_{t}(-{\hat{L}}_{t})-\Phi_{t}(-{\hat{L}}_{t-1})\right]}_{R_{stab}}$
$\displaystyle+\underbrace{{\mathbb{E}}\left[\sum_{t=1}^{T}-\Phi_{t}(-{\hat{L}}_{t})+\Phi_{t}(-{\hat{L}}_{t-1})-\langle
x^{*},\ell_{t}\rangle\right]}_{R_{pen}}\,.$

Then we bound these two terms separately (Lemma 5 and Lemma 4 in the Appendix
B)

$\displaystyle R_{stab}\leq$ $\displaystyle 3m+2m\log T$
$\displaystyle+\sum_{t=4}^{T}\left[\frac{1}{\sqrt{t}}\sum_{j=1}^{m}\sum_{i\neq
I^{*}_{j}}\left(\sqrt{{\mathbb{E}}[x_{t,i,j}]}+{\mathbb{E}}[x_{t,i,j}]\right)\right]\,,$
(3) $\displaystyle R_{pen}\leq$
$\displaystyle\sum_{t=1}^{T}\sum_{j=1}^{m}\sum_{i\neq
I^{*}_{j}}\frac{1}{\sqrt{t}}\left(2\sqrt{{\mathbb{E}}[x_{t,i,j}]}-{\mathbb{E}}[x_{t,i,j}]\right)\,.$
(4)

Summing these two inequalities leads to the resulting regret upper bound. The
second bound comes since
$\sum_{i=1}^{n}\sqrt{{\mathbb{E}}[x_{t,i,j}]}\leq\sqrt{n}$. ∎

For the stochastic environment, it is key to prove a self-bounding constraint
like previous works (Zimmert, Luo, and Wei 2019; Zimmert and Seldin 2019; Wei
and Luo 2018). The common suboptimality gap of putting item $i$ at position
$j$ is defined as $\Delta_{i,j}=\beta_{j}(\alpha_{j}-\alpha_{i})$, the reward
difference from the right item (Komiyama, Honda, and Takeda 2017). This could
be negative for $i<j$. When this happens, a better item is put at position
$j$. Then there must be some bad item placed before position $j$. We account
for this situation and introduce a new suboptimality gap definition that is
more suitable to PBM.

######  Definition 1.

For any $i\in[n]$ and $j\in[m]$, define

$\displaystyle\Delta_{i,j}=\begin{cases}(\beta_{j}-\beta_{j+1})(\alpha_{j}-\alpha_{i})\quad&j<i\,,\\\
0&j=i\,,\\\
(\beta_{j-1}-\beta_{j})(\alpha_{i}-\alpha_{j})\quad&j>i\,.\end{cases}$

The key idea for this definition comes from the incurred minimal regret of
misplacing items. For the case that item $i$ is put at position $j$ with
$i<j$. The item $i$ is misplaced but is better than the right item at position
$j$, which should be item $j$. This means there must be some bad items
misplaced at earlier positions. The optimistic case is that item $j$ is just
put at one position ahead $j-1$. Switching item $i$ and item $j$ would give
the minimal regret gap, i.e. $\Delta_{i,j}$ is defined as the difference
between the reward of $(\cdots,i,j,\cdots)$ and $(\cdots,j,i,\cdots)$ where
the only effectively involved positions are $j-1,j$. The case of $i>j$ is
similar.

Now we can present the self-bounding constraint for PBM based on this
introduced suboptimality gap.

######  Lemma 1.

For the stochastic environment, the regret satisfies

$\displaystyle
R(T)\geq\frac{1}{2}\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{j=1}^{m}\Delta_{i,j}{\mathbb{E}}[x_{t,i,j}]\,.$

We first present Lemma 2 which reveals the property of the introduced
suboptimality gap. The proof of Lemma 2 is postponed to Appendix A.

######  Lemma 2.

Let $i_{1},i_{2},\dots,i_{m}$ be any sequence chosen from $[n]$ without
repetition. Then

$\displaystyle\sum_{j=1}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}}\beta_{j})\geq\frac{1}{2}\sum_{j=1}^{m}\Delta_{i_{j},j}\,.$

Then Lemma 1 follows immediately from Lemma 2 by summing over the time
horizon.

###### Proof of Lemma 1.

Lemma 2 implies that

$\displaystyle R(T)$
$\displaystyle=\sum_{t=1}^{T}\sum_{j=1}^{m}{\mathbb{E}}[\beta_{j}\alpha_{j}-\beta_{j}\alpha_{I_{t,j}}]\geq\sum_{t=1}^{T}\sum_{j=1}^{m}{\mathbb{E}}[\frac{1}{2}\Delta_{I_{t,j},j}]$
$\displaystyle=\frac{1}{2}\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{j=1}^{m}\Delta_{i,j}{\mathbb{E}}[x_{t,i,j}]\,,$

which completes the proof. ∎

With the self-bounding constraint in Lemma 1, we can obtain the following
regret bound for the stochastic setting.

######  Theorem 2.

For the stochastic environment, the regret of ${\tt FTRL\mathchar 45\relax
PBM}$ algorithm is upper bounded by

$\displaystyle R(T)$
$\displaystyle\leq\Bigg{(}18\sum_{j=1}^{m}\sum_{\begin{subarray}{c}i=1\\\
i\neq j\end{subarray}}^{n}\frac{1}{\Delta_{i,j}}+4m\Bigg{)}\log T+6m$
$\displaystyle=O\Big{(}\frac{mn}{\Delta_{\beta}\Delta}\log(T)\Big{)}\,.$

This regret bound improves a factor of $O(m)$ over that of BOBW semi-bandits
(Zimmert, Luo, and Wei 2019) which is designed for general combinatorial
cases. Our regret upper bound is $O(\frac{1}{\Delta_{\beta}})$ worse than
(Lattimore et al. 2018) which studies only the stochastic environments.

###### Proof.

$\displaystyle R(T)\leq$ $\displaystyle
2R(T)-\frac{1}{2}\sum_{t=1}^{T}\sum_{j=1}^{m}\sum_{\begin{subarray}{c}i=1\\\
i\neq j\end{subarray}}^{n}{\mathbb{E}}[x_{t,i,j}]\Delta_{i,j}$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\sum_{j=1}^{m}\sum_{\begin{subarray}{c}i=1\\\
i\neq
j\end{subarray}}^{n}\left(6\sqrt{\frac{{\mathbb{E}}[x_{t,i,j}]}{t}}-\frac{1}{2}{\mathbb{E}}[x_{t,i,j}]\Delta_{i,j}\right)$
$\displaystyle+6m+4m\log T$ $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\sum_{j=1}^{m}\sum_{\begin{subarray}{c}i=1\\\
i\neq j\end{subarray}}^{n}\frac{18}{\Delta_{i,j}t}+4m\log T+6m$
$\displaystyle\leq$
$\displaystyle\Bigg{(}18\sum_{j=1}^{m}\sum_{\begin{subarray}{c}i=1\\\ i\neq
j\end{subarray}}^{n}\frac{1}{\Delta_{i,j}}+4m\Bigg{)}\log T+6m\,,$

where the first inequality is by Lemma 1, the second inequality is by Eq.(3)
and Eq.(4), and the third inequality is due to the AM–GM inequality. ∎

### Lower Bound

We provide an improved lower bound for PBM and defer its proof to Appendix C.

######  Theorem 3.

Suppose that $n\geq\max\\{m+3,2m\\}$ and $T\geq n$. For any algorithm there
exists an instance of OLTR under PBM such that

$\displaystyle R(T)\geq\frac{1}{16}m\sqrt{(n-m+1)T}\,.$

Our lower bound improves $O(\sqrt{m})$ over the state-of-the-art lower bound
(Lattimore et al. 2018) and matches our upper regret bound.

## Experiments

This section compares the empirical performances of our ${\tt FTRL\mathchar
45\relax PBM}$ with related baselines where TopRank (Lattimore et al. 2018),
PBM-PIE (Lagrée, Vernade, and Cappé 2016), PMED (Komiyama, Honda, and Takeda
2017) are designed for the stochastic environment and RankedExp3 (Radlinski,
Kleinberg, and Joachims 2008), MW (Kale, Reyzin, and Schapire 2010) are
designed for the adversarial environment. We do not include (Zimmert, Luo, and
Wei 2019) since we could not find an efficient method for PBM with their
hybrid regularizer. Since the vanilla PBM-PIE in (Lagrée, Vernade, and Cappé
2016) needs the knowledge of the position examination probabilities, we use a
bi-convex optimization to estimate the examination probabilities for PBM-PIE
like (Komiyama, Honda, and Takeda 2017) rather than directly supplying. All
parameters are kept the same as in their original papers. For all experiments,
we use $n=10$ items and $m=5$ positions.

We only present the results of experiments on synthetic data in this section,
The results of experiments on real-world data are deferred to Appendix E. For
the synthetic data, we set the position examination probabilities to
$\beta=(1,\frac{1}{2},\cdots,\frac{1}{5})$ which are commonly adopted in
previous works (Wang et al. 2018; Li, Lattimore, and Szepesvári 2019). The
attractiveness of items are set as
$\alpha=(0.95,0.95-\Delta,0.95-2\Delta,\cdots,0.95-9\Delta)$. We consider two
cases of $\Delta=0.03$ and $\Delta=0.01$.

Figure 1: This figure shows empirical comparisons between our ${\tt
FTRL\mathchar 45\relax PBM}$ and TopRank, PBM-PIE, PMED, RankedExp3 and MW in
stochastic and periodic environments constructed by synthetic data. We adopt
the metric of averaged rewards, which are the cumulative rewards divided by
time $t$. All results are averaged over $10$ random runs and the error bars
are standard errors which are standard deviations divided by $\sqrt{10}$.

We first construct stochastic environments (Lagrée, Vernade, and Cappé 2016;
Komiyama, Honda, and Takeda 2017) from the item attractiveness and position
examination probabilities set above. The results are shown in Fig.1(a)(d).

Next we construct adversarial environments. Since it is a bit hard to design a
real adversarial environment, we construct two periodical stochastic
environments like (Zimmert and Seldin 2019; Zimmert, Luo, and Wei 2019)111They
assume the relative order of items is fixed and the phase length is
increasing.. We divide the whole time horizon into phases with $100$k rounds
in each phase. For the first periodic environment, the position examination
probabilities are fixed and the attractiveness of the first five items and
last five items are exchanged periodically. Specifically, the odd phase uses
the same environment as in the stochastic case and the even phase uses item
attractiveness $(0.95-5\Delta,\cdots,0.95-9\Delta,0.95,\cdots,0.95-4\Delta)$.
For the second periodic environment, the position examination probabilities
are also changed periodically. We reverse the order of $\alpha,\beta$
simultaneously. Specifically, the odd phase uses the same environment as in
the stochastic case and the even phase uses item attractiveness
$(0.95-9\Delta,0.95-8\Delta,\cdots,0.95-\Delta,0.95)$ and position examination
probabilities $(\frac{1}{5},\frac{1}{4},\cdots,1)$. The results are shown in
Fig.1(b)(c)(e)(f).

TopRank performs best in (a)(d) since it is specially designed for the
stochastic environment. PMED is also designed for the stochastic environment
and has almost the same performance as TopRank in (a). Since it needs to solve
a bi-convex optimization problem, fixed iterations would not give good
convergence. Thus its performance has a large variance and deteriorates a lot
for small gap (d). The design of PBM-PIE needs the knowledge of position bias.
Though we can estimate them by bi-convex optimization, the estimation error
would be amplified in the results when the estimated values are adopted
directly. Then the performance of PBM-PIE is not very good and has a large
variance in (a)(d). All of TopRank, PMED and PBM-PIE are strongly affected by
the periodic changes (b)(c)(e)(f).

Our algorithm ${\tt FTRL\mathchar 45\relax PBM}$ is competitive in stochastic
environments and is best in adversarial environments, showing the robustness
and simultaneous learning ability of our algorithm. The greedy idea in
RankedExp3 is not very suitable for PBM but since it is designed for the
adversarial environment, its performances are relatively stable. MW can be
regarded as FTRL with negative Shannon entropy. It has good performances in
some scenarios but is not the best due to the suboptimality of the
regularizer.

## Conclusions

To characterize the dynamic changes of online learning to rank (OLTR)
environments, we study how to simultaneously learn in both stochastic and
adversarial environments for OLTR under the position-based model (PBM). We
design an algorithm based on the follow-the-regularized-leader framework and
prove its efficiency in both environments. We also provide a lower bound for
adversarial PBM which matches our upper bound. Experiments also validate the
robustness of our algorithm.

Our results only focus on PBM. It would be a practical and promising topic to
design efficient algorithms for both environments under general click models
subsuming multiple click models. Further, the adversarial setting for general
click models is open and suggested to be solved in the future.

## Acknowledgments

The corresponding author Shuai Li is supported by National Natural Science
Foundation of China (62006151, 62076161). This work is sponsored by Shanghai
Sailing Program. Cheng Chen is supported by Singapore Ministry of Education
(AcRF) Tier 2 grant MOE2018-T2-1-013.

## References

  * Ailon (2014) Ailon, N. 2014.  Improved bounds for online learning over the permutahedron and other ranking polytopes.  In _Artificial Intelligence and Statistics_ , 29–37. PMLR.
  * Ailon, Hatano, and Takimoto (2016) Ailon, N.; Hatano, K.; and Takimoto, E. 2016.  Bandit online optimization over the permutahedron.  _Theoretical Computer Science_ , 650: 92–108.
  * Audibert, Bubeck, and Lugosi (2014) Audibert, J.-Y.; Bubeck, S.; and Lugosi, G. 2014.  Regret in online combinatorial optimization.  _Mathematics of Operations Research_ , 39(1): 31–45.
  * Auer and Chiang (2016) Auer, P.; and Chiang, C.-K. 2016.  An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits.  In _Conference on Learning Theory_ , 116–120. PMLR.
  * Besson and Kaufmann (2018) Besson, L.; and Kaufmann, E. 2018.  What doubling tricks can and can’t do for multi-armed bandits.  _arXiv preprint arXiv:1803.06971_.
  * Bubeck and Cesa-Bianchi (2012) Bubeck, S.; and Cesa-Bianchi, N. 2012.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Foundations & Trends in Machine Learning_.
  * Bubeck and Slivkins (2012) Bubeck, S.; and Slivkins, A. 2012.  The best of both worlds: Stochastic and adversarial bandits.  In _Conference on Learning Theory_ , 42–1. JMLR Workshop and Conference Proceedings.
  * Chen, Wang, and Yuan (2013) Chen, W.; Wang, Y.; and Yuan, Y. 2013.  Combinatorial multi-armed bandit: General framework and applications.  In _International Conference on Machine Learning_ , 151–159. PMLR.
  * Chuklin, Markov, and Rijke (2015) Chuklin, A.; Markov, I.; and Rijke, M. d. 2015.  Click models for web search.  _Synthesis lectures on information concepts, retrieval, and services_ , 7(3): 1–115.
  * Cohen and Hazan (2015) Cohen, A.; and Hazan, T. 2015.  Following the perturbed leader for online structured learning.  In _International Conference on Machine Learning_ , 1034–1042. PMLR.
  * Combes, Magureanu, and Proutiere (2017) Combes, R.; Magureanu, S.; and Proutiere, A. 2017.  Minimal exploration in structured stochastic bandits.  In _Conference on Neural Information Processing Systems_ , 1761–1769.
  * Combes et al. (2015) Combes, R.; Talebi, S.; Proutière, A.; and Lelarge, M. 2015.  Combinatorial Bandits Revisited.  In _Conference on Neural Information Processing Systems_.
  * Cutkosky and Boahen (2017) Cutkosky, A.; and Boahen, K. A. 2017.  Stochastic and Adversarial Online Learning without Hyperparameters.  In _NIPS_ , 5059–5067.
  * Dempster, Laird, and Rubin (1977) Dempster, A. P.; Laird, N. M.; and Rubin, D. B. 1977.  Maximum likelihood from incomplete data via the EM algorithm.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 39(1): 1–22.
  * Frank, Wolfe et al. (1956) Frank, M.; Wolfe, P.; et al. 1956.  An algorithm for quadratic programming.  _Naval research logistics quarterly_ , 3(1-2): 95–110.
  * Gai, Krishnamachari, and Jain (2012) Gai, Y.; Krishnamachari, B.; and Jain, R. 2012.  Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations.  _IEEE/ACM Transactions on Networking_ , 20(5): 1466–1478.
  * Helmbold and K Warmuth (2009) Helmbold, D. P.; and K Warmuth, M. 2009.  Learning Permutations with Exponential Weights.  _Journal of Machine Learning Research_ , 10(7).
  * Hopcroft and Karp (1973) Hopcroft, J. E.; and Karp, R. M. 1973.  An n^5/2 algorithm for maximum matchings in bipartite graphs.  _SIAM Journal on computing_ , 2(4): 225–231.
  * Jin and Luo (2020) Jin, T.; and Luo, H. 2020.  Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition.  _Advances in Neural Information Processing Systems_ , 33.
  * Kale, Reyzin, and Schapire (2010) Kale, S.; Reyzin, L.; and Schapire, R. E. 2010.  Non-stochastic bandit slate problems.  In _Advances in Neural Information Processing Systems_ , 1054–1062.
  * Katariya et al. (2017) Katariya, S.; Kveton, B.; Szepesvari, C.; Vernade, C.; and Wen, Z. 2017.  Stochastic rank-1 bandits.  In _Artificial Intelligence and Statistics_ , 392–401. PMLR.
  * Komiyama, Honda, and Takeda (2017) Komiyama, J.; Honda, J.; and Takeda, A. 2017.  Position-based multiple-play bandit problem with unknown position bias.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , 5005–5015.
  * Koolen, Grünwald, and van Erven (2016) Koolen, W. M.; Grünwald, P.; and van Erven, T. 2016.  Combining adversarial guarantees and stochastic fast rates in online learning.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , 4464–4472.
  * Kveton et al. (2015a) Kveton, B.; Szepesvari, C.; Wen, Z.; and Ashkan, A. 2015a.  Cascading bandits: Learning to rank in the cascade model.  In _International Conference on Machine Learning_ , 767–776. PMLR.
  * Kveton et al. (2015b) Kveton, B.; Wen, Z.; Ashkan, A.; and Szepesvari, C. 2015b.  Tight regret bounds for stochastic combinatorial semi-bandits.  In _Artificial Intelligence and Statistics_ , 535–543. PMLR.
  * Lagrée, Vernade, and Cappé (2016) Lagrée, P.; Vernade, C.; and Cappé, O. 2016.  Multiple-play bandits in the position-based model.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , 1605–1613.
  * Lattimore et al. (2018) Lattimore, T.; Kveton, B.; Li, S.; and Szepesvári, C. 2018.  TopRank: a practical algorithm for online stochastic ranking.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , 3949–3958.
  * Lattimore and Szepesvári (2020) Lattimore, T.; and Szepesvári, C. 2020.  _Bandit algorithms_.  Cambridge University Press.
  * Lee et al. (2021) Lee, C.-W.; Luo, H.; Wei, C.-Y.; Zhang, M.; and Zhang, X. 2021.  Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously.  _arXiv preprint arXiv:2102.05858_.
  * Li, Lattimore, and Szepesvári (2019) Li, S.; Lattimore, T.; and Szepesvári, C. 2019.  Online learning to rank with features.  In _International Conference on Machine Learning_ , 3856–3865. PMLR.
  * Li et al. (2016) Li, S.; Wang, B.; Zhang, S.; and Chen, W. 2016.  Contextual combinatorial cascading bandits.  In _International conference on machine learning_ , 1245–1253. PMLR.
  * Liu et al. (2009) Liu, T.-Y.; et al. 2009.  Learning to rank for information retrieval.  _Foundations and Trends® in Information Retrieval_ , 3(3): 225–331.
  * Mourtada and Gaïffas (2019) Mourtada, J.; and Gaïffas, S. 2019.  On the optimality of the Hedge algorithm in the stochastic regime.  _Journal of Machine Learning Research_ , 20: 1–28.
  * Neu (2015) Neu, G. 2015.  First-order regret bounds for combinatorial semi-bandits.  In _Conference on Learning Theory_ , 1360–1375. PMLR.
  * Neu and Bartók (2013) Neu, G.; and Bartók, G. 2013.  An efficient algorithm for learning with semi-bandit feedback.  In _International Conference on Algorithmic Learning Theory_ , 234–248. Springer.
  * Radlinski, Kleinberg, and Joachims (2008) Radlinski, F.; Kleinberg, R.; and Joachims, T. 2008.  Learning diverse rankings with multi-armed bandits.  In _Proceedings of the 25th international conference on Machine learning_ , 784–791.
  * Richardson, Dominowska, and Ragno (2007) Richardson, M.; Dominowska, E.; and Ragno, R. 2007.  Predicting clicks: estimating the click-through rate for new ads.  In _Proceedings of the 16th international conference on World Wide Web_ , 521–530.
  * Rockafellar (2015) Rockafellar, R. T. 2015.  _Convex analysis_.  Princeton university press.
  * Seldin and Lugosi (2017) Seldin, Y.; and Lugosi, G. 2017.  An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits.  In _Conference on Learning Theory_ , 1743–1759. PMLR.
  * Seldin and Slivkins (2014) Seldin, Y.; and Slivkins, A. 2014.  One practical algorithm for both stochastic and adversarial bandits.  In _International Conference on Machine Learning_ , 1287–1295. PMLR.
  * Slivkins, Radlinski, and Gollapudi (2013) Slivkins, A.; Radlinski, F.; and Gollapudi, S. 2013.  Ranked bandits in metric spaces: learning diverse rankings over large document collections.  _Journal of Machine Learning Research_ , 14(Feb): 399–436.
  * Wang et al. (2018) Wang, X.; Golbandi, N.; Bendersky, M.; Metzler, D.; and Najork, M. 2018.  Position bias estimation for unbiased learning to rank in personal search.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_ , 610–618.
  * Wei and Luo (2018) Wei, C.-Y.; and Luo, H. 2018.  More adaptive algorithms for adversarial bandits.  In _Conference On Learning Theory_ , 1263–1291. PMLR.
  * Yandex (2013) Yandex. 2013.  Yandex personalized web search challenge.
  * Zimmert, Luo, and Wei (2019) Zimmert, J.; Luo, H.; and Wei, C.-Y. 2019.  Beating stochastic and adversarial semi-bandits optimally and simultaneously.  In _International Conference on Machine Learning_ , 7683–7692. PMLR.
  * Zimmert and Seldin (2019) Zimmert, J.; and Seldin, Y. 2019.  An optimal algorithm for stochastic and adversarial bandits.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , 467–475. PMLR.
  * Zoghi et al. (2017) Zoghi, M.; Tunys, T.; Ghavamzadeh, M.; Kveton, B.; Szepesvari, C.; and Wen, Z. 2017\.  Online learning to rank in stochastic click models.  In _International Conference on Machine Learning_ , 4199–4208. PMLR.
  * Zong et al. (2016) Zong, S.; Ni, H.; Sung, K.; Ke, N. R.; Wen, Z.; and Kveton, B. 2016.  Cascading bandits for large-scale recommendation problems.  _arXiv preprint arXiv:1603.05359_.

##  Appendix A Proof of Lemma 2

This section presents the proof of Lemma 2, which lower bounds the
instantaneous regret in each round of the stochastic setting.

###### Proof of Lemma 2.

We prove it by induction on $m$. For $m=1$,

$\displaystyle\alpha_{1}\beta_{1}-\alpha_{i_{1}}\beta_{1}=\beta_{1}(\alpha_{1}-\alpha_{i_{1}})\geq(\beta_{1}-\beta_{2})(\alpha_{1}-\alpha_{i_{1}})=\Delta_{i_{1},1}\geq\frac{1}{2}\Delta_{i_{1},1}\,.$

Suppose the conclusion holds for $m-1$. Now we consider the situation of $m$.

If $i_{1}=1$, by the induction hypothesis, there is

$\displaystyle\sum_{j=1}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}}\beta_{j})=\sum_{j=2}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}}\beta_{j})\geq\frac{1}{2}\sum_{j=2}^{m}\Delta_{i_{j},j}=\frac{1}{2}\sum_{j=1}^{m}\Delta_{i_{j},j}\,.$

If $i_{1}\neq 1$, it suffices to consider the following two cases.

Case (a). If $i_{j}\neq 1$ for all $j\in[m]$, we define a sequence
$(i_{j}^{\prime})_{j=1}^{m}$ by $i_{1}^{\prime}=1$ and $i_{j}^{\prime}=i_{j}$
for $j\geq 2$. By induction, one can see that

$\sum_{j=1}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}^{\prime}}\beta_{j})=\sum_{j=2}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}^{\prime}}\beta_{j})\geq\frac{1}{2}\sum_{j=2}^{m}\Delta_{i_{j},j}\,.$
(5)

Since $\alpha_{1}\geq\alpha_{i_{1}}$, it is clear that

$\alpha_{i_{1}^{\prime}}\beta_{1}-\alpha_{i_{1}}\beta_{1}=\beta_{1}(\alpha_{1}-\alpha_{i_{1}})\geq(\beta_{1}-\beta_{2})(\alpha_{1}-\alpha_{i_{1}})=\Delta_{i_{1},1}\,.$
(6)

Adding Eq.(5) and Eq.(6) shows that

$\displaystyle\sum_{j=1}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}}\beta_{j})\geq\Delta_{i_{1},1}+\frac{1}{2}\sum_{j=2}^{m}\Delta_{i_{j},j}\geq\frac{1}{2}\sum_{j=1}^{m}\Delta_{i_{j},j}\,.$

Case (b). If there exists $k\in\\{2,3,\dots,m\\}$ such that $i_{k}=1$, we
define a sequence $(i_{j}^{\prime})_{j=1}^{m}$ by $i_{1}^{\prime}=1$,
$i_{k}^{\prime}=i_{1}$ and $i_{j}^{\prime}=i_{j}$ for $j\neq 1,k$. By
induction, one can see that

$\begin{split}\sum_{j=1}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}^{\prime}}\beta_{j})=&\sum_{j=2}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}^{\prime}}\beta_{j})\\\
\geq&\frac{1}{2}\sum_{j=2}^{m}\Delta_{i_{j}^{\prime},j}=\frac{1}{2}\sum_{j=1}^{m}\Delta_{i_{j},j}-\frac{1}{2}(\Delta_{i_{1},1}+\Delta_{1,k}-\Delta_{i_{1},k})\,.\end{split}$
(7)

Also, it holds that

$\sum_{j=1}^{m}(\alpha_{i_{j}^{\prime}}\beta_{j}-\alpha_{i_{j}}\beta_{j})=\beta_{1}(\alpha_{1}-\alpha_{i_{1}})+\beta_{k}(\alpha_{i_{1}}-\alpha_{1})=(\beta_{1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}})\,.$
(8)

Adding Eq.(7) and Eq.(8) shows that

$\displaystyle\sum_{j=1}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}}\beta_{j})\geq\frac{1}{2}\sum_{j=1}^{m}\Delta_{i_{j},j}+(\beta_{1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}})-\frac{1}{2}(\Delta_{i_{1},1}+\Delta_{1,k}-\Delta_{i_{1},k})\,,$

which remains to show
$(\beta_{1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}})\geq\frac{1}{2}(\Delta_{i_{1},1}+\Delta_{1,k}-\Delta_{i_{1},k})$.
We consider the following three cases.

  1. 1.

If $k=i_{1}$, then $\Delta_{i_{1},k}=0$ and

$\displaystyle\frac{1}{2}(\Delta_{i_{1},1}+\Delta_{1,k}-\Delta_{i_{1},k})=$
$\displaystyle\frac{1}{2}(\beta_{1}-\beta_{2}+\beta_{k-1}-\beta_{k})(\alpha_{1}-\alpha_{k})$
$\displaystyle\leq$
$\displaystyle(\beta_{1}-\beta_{k})(\alpha_{1}-\alpha_{k})=(\beta_{1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}})\,.$

  2. 2.

If $k<i_{1}$, then $\alpha_{k}\geq\alpha_{i_{1}}$ and

$\displaystyle\frac{1}{2}(\Delta_{i_{1},1}+\Delta_{1,k}-\Delta_{i_{1},k})\leq$
$\displaystyle\frac{1}{2}(\Delta_{i_{1},1}+\Delta_{1,k})$ $\displaystyle=$
$\displaystyle\frac{1}{2}((\beta_{1}-\beta_{2})(\alpha_{1}-\alpha_{i_{1}})+(\beta_{k-1}-\beta_{k})(\alpha_{1}-\alpha_{k}))$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}((\beta_{1}-\beta_{2})(\alpha_{1}-\alpha_{i_{1}})+(\beta_{k-1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}}))$
$\displaystyle\leq$
$\displaystyle(\beta_{1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}})\,.$

  3. 3.

If $k>i_{1}$, then $\alpha_{k}\leq\alpha_{i_{1}}$ and

$\displaystyle\frac{1}{2}(\Delta_{i_{1},1}+\Delta_{1,k}-\Delta_{i_{1},k})$
$\displaystyle=$
$\displaystyle\frac{1}{2}((\beta_{1}-\beta_{2})(\alpha_{1}-\alpha_{i_{1}})+(\beta_{k-1}-\beta_{k})(\alpha_{1}-\alpha_{k})-(\beta_{k-1}-\beta_{k})(\alpha_{i_{1}}-\alpha_{k}))$
$\displaystyle=$
$\displaystyle\frac{1}{2}((\beta_{1}-\beta_{2})(\alpha_{1}-\alpha_{i_{1}})+(\beta_{k-1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}}))\leq(\beta_{1}-\beta_{k})(\alpha_{1}-\alpha_{i_{1}})\,.$

To sum up, we can achieve

$\displaystyle\sum_{j=1}^{m}(\alpha_{j}\beta_{j}-\alpha_{i_{j}}\beta_{j})\geq\frac{1}{2}\sum_{j=1}^{m}\Delta_{i_{j},j}\,.$

∎

##  Appendix B Proof of Theorem 1

In this section, we provide the details for the proof of Theorem 1. Before
presenting the proof, we introduce some definitions and tools from the convex
analysis in section B.1. Then we analyze the regularization penalty term and
the stability term in section B.2 and section B.3, respectively.

###  B.1 Preliminaries

Define ${\tilde{\Psi}}(\cdot)=\Psi(\cdot)+\langle\cdot,{\bf{1}}\rangle$ and
${\tilde{\Psi}}_{t}(\cdot)=\eta_{t}^{-1}{\tilde{\Psi}}(\cdot)$. Let
$\bar{{\mathbb{R}}}={\mathbb{R}}\bigcup\\{-\infty,+\infty\\}$ be the extended
real number system. We can extend the range of ${\tilde{\Psi}}$ to
$\bar{{\mathbb{R}}}$ by setting ${\tilde{\Psi}}(x)=\infty$ for any
$x\in{\mathbb{R}}^{n\times m}\setminus{\mathcal{D}}$, where
${\mathcal{D}}=[0,+\infty)^{n\times m}$ is the domain of ${\tilde{\Psi}}$.
Then ${\tilde{\Psi}}$ is a Legendre function (Rockafellar 2015).

The Fenchel conjugate of a convex function $f$ is defined as

$\displaystyle f^{*}(\cdot)=\max_{x\in{\mathbb{R}}^{d}}\langle
x,\cdot\rangle-f(x)\,.$

Then for any $y\leq 0$, the Fenchel conjugate of ${\tilde{\Psi}}_{t}(\cdot)$
is

$\displaystyle{\tilde{\Psi}}_{t}^{*}(y)=\max_{x\in{\mathcal{D}}}\langle
x,y\rangle-{\tilde{\Psi}}_{t}(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{1}{4\eta_{t}(1-\eta_{t}y_{i,j})}\,.$

Let ${\tilde{\Phi}}_{t}(\cdot)=\max_{x\in\mathrm{Conv}({\mathcal{X}})}\
\langle x,\cdot\rangle-{\tilde{\Psi}}_{t}(x)$. It is clear that
${\tilde{\Phi}}_{t}(\cdot)$ is the Fenchel conjugate of
${\tilde{\Psi}}_{t}+{\mathcal{I}}_{\mathrm{Conv}({\mathcal{X}})}$. According
to Section 26 of (Rockafellar 2015), the following properties hold

$\displaystyle\nabla{\tilde{\Psi}}_{t}$
$\displaystyle=(\nabla{\tilde{\Psi}}^{*}_{t})^{-1}\,,$ (9)
$\displaystyle\nabla{\tilde{\Phi}}_{t}(\cdot)$
$\displaystyle=\operatorname*{arg\,max}_{x\in\mathrm{Conv}({\mathcal{X}})}\langle
x,\cdot\rangle-{\tilde{\Psi}}_{t}(x)\,,$
$\displaystyle\nabla{\tilde{\Psi}}^{*}_{t}(\cdot)$
$\displaystyle=\operatorname*{arg\,max}_{x\in{\mathcal{D}}}\langle
x,\cdot\rangle-{\tilde{\Psi}}_{t}(x)\,,$ $\displaystyle\nabla\Phi_{t}(\cdot)$
$\displaystyle=\operatorname*{arg\,max}_{x\in\mathrm{Conv}({\mathcal{X}})}\langle
x,\cdot\rangle-\Psi_{t}(x)\,.$

Since $\langle x,{\bf{1}}\rangle=m$ for any
$x\in\mathrm{Conv}({\mathcal{X}})$, we know that

$\displaystyle\nabla{\tilde{\Phi}}_{t}(-\hat{L}_{t-1})=\nabla\Phi_{t}(-\hat{L}_{t-1})=x_{t},$
(10)

which is the regularized leader of FTRL.

The Bregman divergence associated with a Legendre function $f$ is defined as

$\displaystyle D_{f}(x,y)=f(x)-f(y)-\langle\nabla f(y),x-y\rangle\,.$

######  Lemma 3 (Lemma 4 of (Zimmert, Luo, and Wei 2019)).

For any $L\in(-\infty,0]^{n\times m}$, let
${\tilde{L}}=\nabla{\tilde{\Psi}}_{t}(\nabla{\tilde{\Phi}}_{t}(L))$. Then for
any $\ell\in(-\infty,0]^{n\times m}$, it holds that

$\displaystyle D_{{\tilde{\Phi}}_{t}}(L+\ell,L)\leq
D_{{\tilde{\Psi}}_{t}^{*}}({\tilde{L}}+\ell,{\tilde{L}})\,.$

###  B.2 Regularization penalty term

######  Lemma 4.

The regularization penalty term can be bounded as

$\displaystyle R_{pen}\leq\sum_{t=1}^{T}\sum_{j=1}^{m}\sum_{i\neq
I^{*}_{j}}\frac{1}{\sqrt{t}}\left(2\sqrt{{\mathbb{E}}[x_{t,i,j}]}-{\mathbb{E}}[x_{t,i,j}]\right)\,.$

###### Proof.

Recall $\Phi_{t}(\cdot)$ is defined as
$\Phi_{t}(\cdot)=\max_{x\in\mathrm{Conv}({\mathcal{X}})}\ \langle
x,\cdot\rangle-\Psi_{t}(x)$. One can see that

$\displaystyle\sum_{t=1}^{T}\left(-\Phi_{t}(-{\hat{L}}_{t})+\Phi_{t}(-{\hat{L}}_{t-1})-\langle
x^{*},{\hat{\ell}}_{t}\rangle\right)$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\left(\min_{x\in\mathrm{Conv}({\mathcal{X}})}\left\\{\langle
x,{\hat{L}}_{t}\rangle+\eta_{t}^{-1}\Psi(x)\right\\}-\min_{x\in\mathrm{Conv}({\mathcal{X}})}\left\\{\langle
x,{\hat{L}}_{t-1}\rangle+\eta_{t}^{-1}\Psi(x)\right\\}-\langle
x^{*},{\hat{\ell}}_{t}\rangle\right)$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\left(\min_{x\in\mathrm{Conv}({\mathcal{X}})}\left\\{\langle
x,{\hat{L}}_{t}\rangle+\eta_{t}^{-1}\Psi(x)\right\\}-\left(\langle
x_{t},{\hat{L}}_{t-1}\rangle+\eta_{t}^{-1}\Psi(x_{t})\right)-\langle
x^{*},{\hat{\ell}}_{t}\rangle\right)$ $\displaystyle\leq$
$\displaystyle\langle
x^{*},{\hat{L}}_{T}\rangle+\eta_{T}^{-1}\Psi(x^{*})+\sum_{t=1}^{T-1}\left(\langle
x_{t+1},{\hat{L}}_{t}\rangle+\eta_{t}^{-1}\Psi(x_{t+1})\right)-\sum_{t=1}^{T}\left(\langle
x_{t},{\hat{L}}_{t-1}\rangle+\eta_{t}^{-1}\Psi(x_{t})\right)-\langle
x^{*},{\hat{L}}_{T}\rangle$ $\displaystyle=$
$\displaystyle\eta_{T}^{-1}\Psi(x^{*})+\sum_{t=1}^{T-1}\eta_{t}^{-1}\Psi(x_{t+1})-\sum_{t=1}^{T}\eta_{t}^{-1}\Psi(x_{t})$
$\displaystyle=$
$\displaystyle\eta_{1}^{-1}(\Psi(x^{*})-\Psi(x_{1}))+\sum_{t=2}^{T}(\eta_{t}^{-1}-\eta_{t-1}^{-1})(\Psi(x^{*})-\Psi(x_{t}))$
$\displaystyle=$ $\displaystyle
2(\Psi(x^{*})-\Psi(x_{1}))+2\sum_{t=2}^{T}(\sqrt{t}-\sqrt{t-1})(\Psi(x^{*})-\Psi(x_{t}))\,.$
(11)

where the third equation comes from the fact ${\hat{L}}_{0}=0$.
Using ${\mathbb{E}}[\ell_{t}]={\mathbb{E}}[\hat{\ell}_{t}]$ and taking
expectations of both sides of Eq.(11) lead to

$\displaystyle
R_{pen}\leq\mathbb{E}\left[2(\Psi(x^{*})-\Psi(x_{1}))+2\sum_{t=2}^{T}(\sqrt{t}-\sqrt{t-1})(\Psi(x^{*})-\Psi(x_{t}))\right]\,.$
(12)

Since $\Psi(x)=\sum_{i}-\sqrt{x_{i}}$, it holds that

$\displaystyle\Psi(x^{*})-\Psi(x_{t})$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{m}\sqrt{x_{t,i,j}}-\sum_{j=1}^{m}\sum_{i:i=I^{*}_{j}}\sqrt{1}$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{m}(\sqrt{x_{t,i,j}}-\frac{1}{2}x_{t,i,j})-\sum_{j=1}^{m}\sum_{i:i=I^{*}_{j}}(\sqrt{1}-\frac{1}{2})$
$\displaystyle\leq\sum_{j=1}^{m}\sum_{i:i\neq
I^{*}_{j}}(\sqrt{x_{t,i,j}}-\frac{1}{2}x_{t,i,j})\,,$ (13)

where the last inequality is due to
$\sqrt{x_{t,i,j}}-\frac{x_{t,i,j}}{2}\leq\frac{1}{2}$ for any $0\leq
x_{t,i,j}\leq 1$.

Substituting Eq.(13) into Eq.(12) shows that

$\displaystyle R_{pen}$
$\displaystyle\leq{\mathbb{E}}\left[2(\Psi(x^{*})-\Psi(x_{1}))+2\sum_{t=2}^{T}(\sqrt{t}-\sqrt{t-1})(\Psi(x^{*})-\Psi(x_{t}))\right]$
$\displaystyle\leq{\mathbb{E}}\left[\sum_{t=1}^{T}\frac{2}{\sqrt{t}}(\Psi(x^{*})-\Psi(x_{t}))\right]$
$\displaystyle\leq{\mathbb{E}}\left[\sum_{t=1}^{T}\sum_{j=1}^{m}\sum_{i:i\neq
I^{*}_{j}}\frac{2}{\sqrt{t}}(\sqrt{x_{t,i,j}}-\frac{1}{2}x_{t,i,j})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{j=1}^{m}\sum_{i:i\neq
I^{*}_{j}}\frac{1}{\sqrt{t}}(2\sqrt{{\mathbb{E}}[x_{t,i,j}]}-{\mathbb{E}}[x_{t,i,j}])\,,$

where the second inequality is due to
$\sqrt{t}-\sqrt{t-1}\leq\frac{1}{\sqrt{t}}$ for any $t\geq 1$ and the last
step comes from Jensen’s inequality. ∎

###  B.3 Stability term

######  Lemma 5.

The stability term can be bounded as

$\displaystyle R_{stab}\leq 3m+2m\log
T+\sum_{t=4}^{T}\left[\frac{1}{\sqrt{t}}\sum_{j=1}^{m}\sum_{i\neq
I^{*}_{j}}\left(\sqrt{{\mathbb{E}}[x_{t,i,j}]}+{\mathbb{E}}[x_{t,i,j}]\right)\right]\,.$

######  Lemma 6.

For any $w_{i}\in{\mathbb{R}}$, if
$\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}}\geq-\frac{1}{4}$,
then

$\displaystyle\langle
x_{t},{\hat{\ell}}_{t}\rangle+\Phi_{t}(-{\hat{L}}_{t})-\Phi_{t}(-{\hat{L}}_{t-1})\leq\sum_{i=1}^{n}\sum_{j=1}^{m}\left[2\eta_{t}x_{t,i,j}^{\frac{3}{2}}({\hat{\ell}}_{t,i,j}-w_{i})^{2}+8\eta_{t}^{2}x_{t,i,j}^{2}|w_{i}-{\hat{\ell}}_{t,i,j}|_{+}^{3}\right]\,,$

where $|z|_{+}=\max\\{z,0\\}$.

###### Proof.

For any
$w=\begin{bmatrix}w_{1}{\bf{1}}_{n},w_{2}{\bf{1}}_{n},\cdots,w_{m}{\bf{1}}_{n}\end{bmatrix}\in{\mathbb{R}}^{n\times
m}$, we have

$\displaystyle\langle
x_{t},{\hat{\ell}}_{t}\rangle+\Phi_{t}(-{\hat{L}}_{t})-\Phi_{t}(-{\hat{L}}_{t-1})$
$\displaystyle=$ $\displaystyle\langle
x_{t},{\hat{\ell}}_{t}\rangle+{\tilde{\Phi}}_{t}(-{\hat{L}}_{t})-{\tilde{\Phi}}_{t}(-{\hat{L}}_{t-1})$
$\displaystyle=$ $\displaystyle\langle
x_{t},{\hat{\ell}}_{t}-w\rangle+{\tilde{\Phi}}_{t}(-{\hat{L}}_{t}+w)-{\tilde{\Phi}}_{t}(-{\hat{L}}_{t-1})$
$\displaystyle=$ $\displaystyle\langle
x_{t},{\hat{\ell}}_{t}-w\rangle+{\tilde{\Phi}}_{t}(-{\hat{L}}_{t-1}-{\hat{\ell}}_{t}+w)-{\tilde{\Phi}}_{t}(-{\hat{L}}_{t-1})$
$\displaystyle\overset{\text{(a)}}{=}$ $\displaystyle
D_{{\tilde{\Phi}}_{t}}(-{\hat{L}}_{t-1}-{\hat{\ell}}_{t}+w,-{\hat{L}}_{t-1})$
$\displaystyle\leq$ $\displaystyle
D_{{\tilde{\Psi}}_{t}}(\nabla{\tilde{\Psi}}_{t}(x_{t})-{\hat{\ell}}_{t}+w,\nabla{\tilde{\Psi}}_{t}(x_{t}))$
$\displaystyle\overset{\text{(b)}}{=}$ $\displaystyle\langle
x_{t},{\hat{\ell}}_{t}-w\rangle+{\tilde{\Psi}}_{t}^{*}(\nabla{\tilde{\Psi}}_{t}(x_{t})-{\hat{\ell}}_{t}+w)-{\tilde{\Psi}}_{t}^{*}(\nabla{\tilde{\Psi}}_{t}(x_{t}))$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{m}\left[x_{t,i,j}({\hat{\ell}}_{t,i,j}-w_{i})+\frac{1}{2\eta_{t}}(x_{t,i,j}^{-\frac{1}{2}}+2\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i}))^{-1}-\frac{1}{2\eta_{t}}x_{t,i,j}^{\frac{1}{2}}\right]$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{m}\left[\frac{1}{2\eta_{t}}x_{t,i,j}^{\frac{1}{2}}\left(2\eta_{t}x_{t,i,j}^{\frac{1}{2}}({\hat{\ell}}_{t,i,j}-w_{i})+(1+2\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}})^{-1}-1\right)\right]$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{m}\left[2\eta_{t}x_{t,i,j}^{\frac{3}{2}}({\hat{\ell}}_{t,i,j}-w_{i})^{2}(1+2\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}})^{-1}\right]\,,$
(14)

where the first two equality comes from $\sum^{n}_{i=1}x_{t,i,j}=1$, equality
(a) and (b) is by Eq.(10) and the inequality is due to Lemma 3.

Since we have
$\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}}\geq-\frac{1}{4}$
for any $i\in[n]$ and $j\in[m]$, it can be obtained that
$(1+2\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}})^{-1}\leq 2$.
Thus,

$\displaystyle(1+2\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}})^{-1}=$
$\displaystyle
1-2\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}}(1+2\eta_{t}({\hat{\ell}}_{t,i,j}-w_{i})x_{t,i,j}^{\frac{1}{2}})^{-1}$
$\displaystyle\leq$ $\displaystyle
1+4\eta_{t}|w_{i}-{\hat{\ell}}_{t,i,j}|_{+}x_{t,i,j}^{\frac{1}{2}}\,.$ (15)

Substituting Eq.(B.3) into Eq.(B.3) concludes the proof.

∎

We are now ready to prove Lemma 5.

###### Proof of Lemma 5.

By the unbiasedness of ${\hat{\ell}}_{t}$ and the tower rule, one can see that

$\displaystyle{\mathbb{E}}[\langle
X_{t},\ell_{t}\rangle]={\mathbb{E}}[{\mathbb{E}}_{t}[\langle
X_{t},\ell_{t}\rangle]]={\mathbb{E}}[{\mathbb{E}}_{t}[\langle
x_{t},\ell_{t}\rangle]]={\mathbb{E}}[{\mathbb{E}}_{t}[\langle
x_{t},{\hat{\ell}}_{t}\rangle]]\,.$ (16)

Let $w_{j}=\ell_{t,I_{t,j},j}$. Lemma 6 and Eq.(16) show that

$\displaystyle{\mathbb{E}}\left[\langle
X_{t},\ell_{t}\rangle+\Phi(-{\hat{L}}_{t})-\Phi(-{\hat{L}}_{t-1})\right]$
$\displaystyle\leq$
$\displaystyle{\mathbb{E}}\left[\sum_{i=1}^{n}\sum_{j=1}^{m}2\eta_{t}x_{t,i,j}^{\frac{3}{2}}({\hat{\ell}}_{t,i,j}-\ell_{t,i,I_{t,i}})^{2}+8\eta_{t}^{2}x_{t,i,j}^{2}|w_{i}-{\hat{\ell}}_{t,i,j}|_{+}^{3}\right]$
$\displaystyle\leq$ $\displaystyle
2\eta_{t}\sum_{j=1}^{m}{\mathbb{E}}\left[x_{t,I_{t,j},j}^{\frac{3}{2}}({\hat{\ell}}_{t,I_{t,j},j}-\ell_{t,I_{t,j},j})^{2}+\sum_{i:i\neq
I_{t,j}}x_{t,i,j}^{\frac{3}{2}}({\hat{\ell}}_{t,i,j}-\ell_{t,I_{t,j},j})^{2}\right]+8\eta_{t}^{2}m$
$\displaystyle\leq$ $\displaystyle
2\eta_{t}\sum_{j=1}^{m}{\mathbb{E}}\left[x_{t,I_{t,j},j}^{-\frac{1}{2}}(1-x_{t,I_{t,j},j})^{2}+\sum_{i:i\neq
I_{t,j}}x_{t,i,j}^{\frac{3}{2}}\right]+8\eta_{t}^{2}m$ $\displaystyle=$
$\displaystyle
2\eta_{t}\sum_{i=1}^{n}\sum_{j=1}^{m}{\mathbb{E}}\left[x_{t,i,j}^{\frac{1}{2}}(1-x_{t,i,j})^{2}+(1-x_{t,i,j})x_{t,i,j}^{\frac{3}{2}}\right]+8\eta_{t}^{2}m$
$\displaystyle=$ $\displaystyle
2\eta_{t}\sum_{i=1}^{n}\sum_{j=1}^{m}{\mathbb{E}}\left[x_{t,i,j}^{\frac{1}{2}}(1-x_{t,i,j})\right]+8\eta_{t}^{2}m$
$\displaystyle\leq$ $\displaystyle
2\eta_{t}\sum_{i=1}^{n}\sum_{j=1}^{m}{\mathbb{E}}[x_{t,i,j}]^{\frac{1}{2}}(1-{\mathbb{E}}[x_{t,i,j}])+8\eta_{t}^{2}m\,,$

where the second inequality is due to
$\sum^{n}_{i=1}\sum^{m}_{j=1}x_{t,i,j}^{2}|w_{i}-{\hat{\ell}}_{t,i,j}|_{+}^{3}\leq
m$. The third inequality comes from ${\hat{\ell}}_{t,i,j}=0$ for $i\neq
I_{t,j}$ and

$\displaystyle\left({\hat{\ell}}_{t,I_{t,j},j}-\ell_{t,I_{t,j},j}\right)^{2}$
$\displaystyle=\left(\frac{\ell_{t,I_{t,j},j}\mathds{1}{\\{X_{t,I_{t,j},j}=1\\}}}{{\bf
x}_{t,I_{t,j},j}}-\ell_{t,I_{t,j},j}\right)^{2}$
$\displaystyle=\ell_{t,I_{t,j},j}^{2}\left(\frac{1}{{\bf
x}_{t,I_{t,j},j}}-1\right)^{2}$ $\displaystyle\leq\left(\frac{1}{{\bf
x}_{t,I_{t,j},j}}-1\right)^{2}\,.$

And the last inequality follows from Jensen’s inequality.

Thus,

$\displaystyle{\mathbb{E}}\left[\sum_{t=1}^{T}\langle
X_{t},\ell_{t}\rangle+\Phi_{t}(-{\hat{L}}_{t})-\Phi_{t}(-{\hat{L}}_{t-1})\right]$
$\displaystyle\leq$ $\displaystyle 3m+{\mathbb{E}}\left[\sum_{t=4}^{T}\langle
X_{t},\ell_{t}\rangle+\Phi_{t}(-{\hat{L}}_{t})-\Phi_{t}(-{\hat{L}}_{t-1})\right]$
$\displaystyle\leq$ $\displaystyle 3m+2m\log
T+\sum_{t=4}^{T}\left[2\eta_{t}\sum_{i=1}^{n}\sum_{j=1}^{m}{\mathbb{E}}[x_{t,i,j}]^{\frac{1}{2}}(1-{\mathbb{E}}[x_{t,i,j}])\right]\,.$
(17)

If $i\neq I^{*}_{j}$,

$\displaystyle\sqrt{{\mathbb{E}}[x_{t,i,j}]}(1-{\mathbb{E}}[x_{t,i,j}])\leq\sqrt{{\mathbb{E}}[x_{t,i,j}]}\,.$
(18)

If $i=I^{*}_{j}$ ,

$\displaystyle\sqrt{{\mathbb{E}}[x_{t,i,j}]}(1-{\mathbb{E}}[x_{t,i,j}])\leq
1-{\mathbb{E}}[x_{t,i,j}]=\sum_{i:i\neq I^{*}_{j}}{\mathbb{E}}[x_{t,i,j}]\,.$
(19)

Substituting Eq.(18) and Eq.(19) into Eq.(17) shows that

$\displaystyle R_{stab}\leq 3m+2m\log
T+\sum_{t=4}^{T}\left[2\eta_{t}\sum_{j=1}^{m}\sum_{i\neq
I^{*}_{j}}(\sqrt{{\mathbb{E}}[x_{t,i,j}]}+{\mathbb{E}}[x_{t,i,j}])\right]\,,$

which concludes the proof. ∎

###  B.4 Proof of Theorem 1

Now we turn to the proof of Theorem 1.

###### Proof of Theorem 1.

Like the standard FTRL analysis (see Chapter 28 of (Lattimore and Szepesvári
2020)), the regret can be decomposed as

$\displaystyle R(T)=$
$\displaystyle\underbrace{{\mathbb{E}}\left[\sum_{t=1}^{T}\langle
X_{t},\ell_{t}\rangle+\Phi_{t}(-{\hat{L}}_{t})-\Phi_{t}(-{\hat{L}}_{t-1})\right]}_{R_{stab}}+\underbrace{{\mathbb{E}}\left[\sum_{t=1}^{T}-\Phi_{t}(-{\hat{L}}_{t})+\Phi_{t}(-{\hat{L}}_{t-1})-\langle
x^{*},\ell_{t}\rangle\right]}_{R_{pen}}\,.$ $\displaystyle\leq$ $\displaystyle
3m+2m\log T+\sum_{t=1}^{T}\left(\frac{3}{\sqrt{t}}\sum_{j=1}^{m}\sum_{i\neq
I^{*}_{j}}\sqrt{{\mathbb{E}}[x_{t,i,j}]}\right)$

where the first inequality comes from Lemma 4 and Lemma 6. According to
Cauchy-Schwartz inequality, we have
$\sum_{i=1}^{n}\sqrt{{\mathbb{E}}[x_{t,i,j}]}\leq\sqrt{n}$. Thus,

$\displaystyle R(T)\leq 3m+2m\log
T+3m\sqrt{n}\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 6m\sqrt{nT}$

where the last inequality comes from the fact
$\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 2\sqrt{T}$.

∎

##  Appendix C Lower Bound

###### Proof of Theorem 3.

We assume the learner is deterministic in this section. Let
${\mathcal{S}}_{n}(m)$ be the set of all $m$-permutations of $[n]$. For each
$u\in{\mathcal{S}}_{n}(m)$, we define a loss vector $\ell_{u}$ as

$\displaystyle\ell_{u}(i,j)=\begin{cases}\frac{1}{2}-\Delta&\quad\text{if
}u_{j}=i\\\ \frac{1}{2}&\quad\text{otherwise}\,,\end{cases}$

where $0<\Delta<1/2$ is some value to be tuned subsequently.

Let $N_{i,j}(t)=\sum_{s=1}^{t}\mathds{1}\left\\{X_{s,i,j}=1\right\\}$ be the
total number of times that item $i$ is placed at position $j$ by the end of
round $t$. We will use subscript $u$ to denote the expectation, probability,
regret, etc., under the ranking problem whose loss is determined by
$\ell_{u}$. Note that
$R_{u}(T)=\Delta\sum_{j=1}^{m}(T-\mathbb{E}_{u}\left[N_{u_{j},j}(T)\right])$.
Then

$\displaystyle\sum_{u\in{\mathcal{S}}_{n}(m)}R_{u}(T)=$
$\displaystyle\Delta\sum_{u\in{\mathcal{S}}_{n}(m)}\sum_{j=1}^{m}(T-\mathbb{E}_{u}\left[N_{u_{j},j}(T)\right])$
$\displaystyle=$
$\displaystyle\Delta\sum_{j=1}^{m}\sum_{u_{-j}\in{\mathcal{S}}_{n}(m-1)}\sum_{u_{j}\in[n]\setminus
u_{-j}}(T-\mathbb{E}_{u}\left[N_{u_{j},j}(T)\right])\,,$

where $u_{-j}=(u_{1},\cdots,u_{j-1},u_{j+1},\cdots,u_{m})$ denotes a
$(m-1)$-permutation of $[n]$.

Now fix $j\in[m]$, $u_{-j}\in{\mathcal{S}}_{n}(m-1)$ and $T$. Let $J_{j,T}$ be
drawn according to the probability
$\left(\frac{N_{1,j}(T)}{T},\frac{N_{2,j}(T)}{T},\dots,\frac{N_{n,j}(T)}{T}\right)$.
Let ${\mathbb{P}}_{j,u}$ be the law of $J_{j,T}$ under the ranking problem
whose loss is determined by $\ell_{u}$. Then we have
${\mathbb{P}}_{j,u}(J_{j,T}=i)=\mathbb{E}_{u}\left[\frac{N_{i,j}(T)}{T}\right]$.

We define a ranking problem with respect to $u_{-j}$ whose loss is determined
by $\ell_{u_{-j}}$ where

$\displaystyle\ell_{u_{-j}}(i,j^{\prime})=\begin{cases}\ell_{u}(i,j^{\prime})&\quad\text{if
}j^{\prime}\neq j\\\ \frac{1}{2}&\quad\text{otherwise}\,.\end{cases}$

Similarly, we use subscript $u_{-j}$ to denote the expectation, probability,
regret, etc., under the ranking problem whose loss is determined by
$\ell_{u_{-j}}$. We also denote by ${\mathbb{P}}_{j,u_{-j}}$ the law of
$J_{j,T}$ when the learner is interacting with the ranking problem determined
by $\ell_{u_{-j}}$.

By Pinsker’s inequality (Chapter 14 of (Lattimore and Szepesvári 2020)) , we
have

$\displaystyle{\mathbb{P}}_{j,u}(J_{j,T}=u_{j})\leq{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=u_{j})+\sqrt{\frac{1}{2}\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})}\,,$

which means

$\displaystyle{\mathbb{E}}_{u}[N_{u_{j},j}(T)]\leq{\mathbb{E}}_{u_{-j}}[N_{u_{j},j}(T)]+T\sqrt{\frac{1}{2}\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})}\,.$

Thus,

$\displaystyle\sum_{u_{j}\in[n]\setminus
u_{-j}}{\mathbb{E}}_{u}[N_{u_{j},j}(T)]\leq$
$\displaystyle\sum_{u_{j}\in[n]\setminus
u_{-j}}{\mathbb{E}}_{u_{-j}}[N_{u_{j},j}(T)]+T\sum_{u_{j}\in[n]\setminus
u_{-j}}\sqrt{\frac{1}{2}\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})}$
$\displaystyle\leq$
$\displaystyle\sum_{u_{j}\in[n]}{\mathbb{E}}_{u_{-j}}[N_{u_{j},j}(T)]+T\sum_{u_{j}\in[n]\setminus
u_{-j}}\sqrt{\frac{1}{2}\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})}$
$\displaystyle\leq$ $\displaystyle T+T\sum_{u_{j}\in[n]\setminus
u_{-j}}\sqrt{\frac{1}{2}\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})}\,.$
(20)

Let $Y^{t}=(Y_{1},Y_{2},\dots,Y_{t})\in\\{0,1\\}^{m\times t}$ be the sequence
of feedback received by the learner up to round $t$ and
$y^{t}=(y_{1},y_{2},\dots,y_{t})\in\\{0,1\\}^{m\times t}$ be a specific value
taken by $Y^{t}$. Since the learner is deterministic, $Y^{t}$ uniquely
determines $N_{i,j}(t)$ for $j\in[m]$ and $i\in[n]$. Specifically, we have
${\mathbb{P}}_{j,u}(\cdot\big{|}y^{T})={\mathbb{P}}_{j,u_{-j}}(\cdot\big{|}y^{T})$.
Let ${\mathbb{P}}_{u}^{t}$ be the law of $Y^{t}$ when the learner is
interacting with the ranking problem determined by $\ell_{u}$. Then we have

$\displaystyle{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=i)=\sum_{y^{T}}{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=i\big{|}y^{T}){\mathbb{P}}_{u_{-j}}^{T}(y^{T})\,.$

Thus,

$\displaystyle\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})=$
$\displaystyle\sum_{i\in[n]}\left[\sum_{y^{T}}{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=i\big{|}y^{T}){\mathbb{P}}_{u_{-j}}^{T}(y^{T})\right]\log\frac{\sum_{y^{T}}{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=i\big{|}y^{T}){\mathbb{P}}_{u_{-j}}^{T}(y^{T})}{\sum_{y^{T}}{\mathbb{P}}_{j,u}(J_{j,T}=i\big{|}y^{T}){\mathbb{P}}_{u}^{T}(y^{T})}$
$\displaystyle\leq$
$\displaystyle\sum_{i\in[n]}\sum_{y^{T}}{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=i\big{|}y^{T}){\mathbb{P}}_{u_{-j}}^{T}(y^{T})\log\frac{{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=i\big{|}y^{T}){\mathbb{P}}_{u_{-j}}^{T}(y^{T})}{{\mathbb{P}}_{j,u}(J_{j,T}=i\big{|}y^{T}){\mathbb{P}}_{u}^{T}(y^{T})}$
$\displaystyle=$
$\displaystyle\sum_{y^{T}}\left[\sum_{i\in[n]}{\mathbb{P}}_{j,u_{-j}}(J_{j,T}=i\big{|}y^{T})\right]{\mathbb{P}}_{u_{-j}}^{T}(y^{T})\log\frac{{\mathbb{P}}_{u_{-j}}^{T}(y^{T})}{{\mathbb{P}}_{u}^{T}(y^{T})}$
$\displaystyle=$
$\displaystyle\operatorname{KL}({\mathbb{P}}_{u_{-j}}^{T},{\mathbb{P}}_{u}^{T})\,,$

where the inequality uses Jensen’s inequality and the fact that
$f(x_{1},x_{2})=x_{1}\log\frac{x_{1}}{x_{2}}$ is a convex function whose
Hessian matrix $\begin{bmatrix}\frac{1}{x_{1}}&-\frac{1}{{\bf x}_{2}}\\\
-\frac{1}{{\bf x}_{2}}&\frac{x_{1}}{x_{2}^{2}}\end{bmatrix}$ is positive semi-
definite. The second equality comes from
${\mathbb{P}}_{j,u}(\cdot\big{|}y^{T})={\mathbb{P}}_{j,u_{-j}}(\cdot\big{|}y^{T})$.

According to the chain rule for KL divergence, we have

$\displaystyle\operatorname{KL}({\mathbb{P}}_{u_{-j}}^{T},{\mathbb{P}}_{u}^{T})$
$\displaystyle=$
$\displaystyle\operatorname{KL}({\mathbb{P}}_{u_{-j}}^{1},{\mathbb{P}}_{u}^{1})+\sum_{t=2}^{T}\sum_{y^{t-1}}{\mathbb{P}}_{u_{-j}}^{t-1}(y^{t-1})\operatorname{KL}({\mathbb{P}}_{u_{-j}}^{t}(\cdot|y^{t-1}),{\mathbb{P}}_{u}^{t}(\cdot|y^{t-1}))$
$\displaystyle=$
$\displaystyle\operatorname{KL}({\mathbb{P}}_{u_{-j}}^{1},{\mathbb{P}}_{u}^{1})+\sum_{t=2}^{T}\left(\sum_{y_{t-1}:i_{t,j}=u_{j}}{\mathbb{P}}_{u_{-j}}^{t-1}(y^{t-1})\operatorname{KL}\left(\frac{1}{2},\frac{1}{2}-\Delta\right)\right.$
$\displaystyle\left.+\sum_{y^{t-1}:i_{t,j}\neq
u_{j}}{\mathbb{P}}_{u_{-j}}^{t-1}(y^{t-1})\operatorname{KL}\left(\frac{1}{2},\frac{1}{2}\right)\right)$
$\displaystyle=$
$\displaystyle\operatorname{KL}\left(\frac{1}{2},\frac{1}{2}-\Delta\right){\mathbb{E}}_{u_{-j}}[N_{u_{j},j}(T)]$
$\displaystyle\leq$ $\displaystyle
8\Delta^{2}{\mathbb{E}}_{u_{-j}}[N_{u_{j},j}(T)]\,.$

Then,

$\displaystyle\sum_{u_{j}\in[n]\setminus
u_{-j}}\sqrt{\frac{1}{2}\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})}\leq$
$\displaystyle\sqrt{\frac{n-m+1}{2}\sum_{u_{j}\in[n]\setminus
u_{-j}}\operatorname{KL}({\mathbb{P}}_{j,u_{-j}},{\mathbb{P}}_{j,u})}$
$\displaystyle\leq$ $\displaystyle\sqrt{(n-m+1)\sum_{u_{j}\in[n]\setminus
u_{-j}}4\Delta^{2}{\mathbb{E}}_{u_{-j}}[N_{u_{j},j}(T)]}$ $\displaystyle=$
$\displaystyle 2\Delta\sqrt{(n-m+1)T}\,.$

Recall that we have assumed $n\geq\max\\{m+3,2m\\}$. Choosing
$\Delta=\frac{1}{8}\sqrt{\frac{n-m+1}{T}}$ and substituting the above into
Eq.(20) shows that

$\displaystyle\sum_{u_{j}\in[n]\setminus
u_{-j}}{\mathbb{E}}_{u}[N_{u_{j},j}(T)]\leq\frac{(n-m+1)T}{2}\,.$

Thus,

$\displaystyle\sum_{u\in{\mathcal{S}}_{n}(m)}R_{u}(T)=$
$\displaystyle\Delta\sum_{j=1}^{m}\sum_{u_{-j}\in{\mathcal{S}}_{n}(m-1)}\sum_{u_{j}\in[n]\setminus
u_{-j}}(T-{\mathbb{E}}_{u}[N_{u_{j},j}(T)])$ $\displaystyle\geq$
$\displaystyle\frac{n!}{2(n-m+1)!}\Delta m(n-m+1)T$ $\displaystyle=$
$\displaystyle\frac{n!}{16(n-m)!}m\sqrt{(n-m+1)T}\,.$ (21)

Since $|{\mathcal{S}}_{n}(m)|=\frac{n!}{(n-m)!}$ holds, there exists an
$u\in{\mathcal{S}}_{n}(m)$ such that

$\displaystyle R_{u}(T)\geq\frac{1}{16}m\sqrt{(n-m+1)T}\,.$

∎

##  Appendix D Omitted Details for Algorithm 1

This section discusses the remaining issue in the implementation of Algorithm
1: the sampling rule for choosing actions.

###  D.1 Decomposition of Subpermutation Matrices

The sampling of $X_{t}$ (line 4 of Algorithm 1) requires finding a
distribution over the action set ${\mathcal{X}}$ with mean $x_{t}$.
Specifically, we wish to express $x_{t}$ as a convex combination of a group of
$n\times m$ subpermutation matrices. Our method is presented in Algorithm 3.
Following Kale, Reyzin, and Schapire (2010), we first complete $x_{t}$ into a
doubly stochastic matrix $W\in{\mathbb{R}}^{n\times n}$ satisfying each
element $W_{i,j}\geq 0$ and $\sum^{n}_{j=1}W_{i,j}=\sum^{n}_{j=1}W_{j,i}=1$
for any $i\in[n]$ in $O(n^{2})$ time (Line 1 in Algorithm 3). Then we apply
the Algorithm 1 in (Helmbold and K Warmuth 2009) (Line 2-8 in Algorithm 3) to
decompose the doubly stochastic matrix $W$ into its convex combination. At
each iteration, Algorithm 3 finds a permutation matrix $\Pi^{k}$ such that
$W_{i,\Pi^{k}(i)}>0$ for any $i\in[n]$. This could be viewed as the problem of
maximal matching in a bipartite graph where edge $e_{i,j}$ has weight
$W_{i,j}$ and could be solved by the Hopcroft–Karp algorithm at the cost of
$O(n^{2.5})$ time. Helmbold and K Warmuth (2009) further show that the doubly
stochastic matrix $W$ can be decomposed into the convex combination of at most
$n^{2}-2n+2$ permutation matrices. Consequently, there are at most $O(n^{2})$
iterations on Line 2 of Algorithm 3 and Algorithm 3 will end in $O(n^{4.5})$
time.

Algorithm 3 Permutation Matrix Decomposition (on Line 4 of Algorithm 1)

Input: $x_{t}$

1: Let $W\in{\mathbb{R}}^{n\times n}$ where $\forall i\in[n]$,
$W_{i,j}=x_{t,i,j}$ if $1\leq j\leq m$ and
$W_{i,j}=\frac{1}{n-m}\left(1-\sum^{m}_{j=1}x_{t,i,j}\right)$ if $m<j\leq n$.
Let $k=0$.

2: while $\|W\|_{1}\neq 0$ do

3: $k:=k+1$.

4: Find a permutation $\Pi^{k}$ such that $W_{i,\Pi^{k}(i)}$ is positive for
any $i\in[n]$.

5: $\gamma_{k}:=\min_{i\in[n]}W_{i,\Pi^{k}(i)}$.

6: $W:=W-\gamma_{k}\Pi^{k}$.

7: end while

8: Randomly sample and return a permutation
$\Pi\in\\{\Pi^{1},\cdots,\Pi^{k}\\}$ with probabilities
$\\{\gamma_{1},\cdots,\gamma_{k}\\}$.

##  Appendix E Experiments on Real-world Data

Figure 2: This figure shows empirical comparisons between our ${\tt
FTRL\mathchar 45\relax PBM}$ and TopRank, PBM-PIE, PMED, RankedExp3 and MW in
stochastic and periodic environments constructed by real-world data. The
metric is the averaged rewards and the error bars are computed in the same way
as in Fig.1.

This section presents the experimental results on real-world data. The real-
world experiment is conducted on the _Yandex_ dataset (Yandex 2013). There are
total $167$m search queries where each query is associated with $10$ items,
_i.e._ URL links, on $10$ positions. We first take $10$ most frequent items
and then take the queries which only consist of these $10$ items. As a result,
we get $557,574$ queries. Then we use the EM algorithm (Dempster, Laird, and
Rubin 1977) to extract the item attractiveness and position examination
probabilities like (Lagrée, Vernade, and Cappé 2016; Komiyama, Honda, and
Takeda 2017). The resulting item attractiveness are
$\alpha=(0.894,0.231,0.139,0.0745,0.0585,0.0424,0.0237,0.0234,0.0231,0.0178)$
and the position examination probabilities are
$\beta=(0.891,0.227,0.0778,0.0412,0.0378)$. Like synthetic data, we also
construct stochastic and periodic environments. The results are shown in
Fig.2(a)(b)(c). The performances of PBM-PIE are roughly $0.2$, far below
others, and fall out of the shown ranges in (a)(b). The results are similar to
those in synthetic settings, showing the simultaneous learning abilities of
our algorithm ${\tt FTRL\mathchar 45\relax PBM}$.