# Disincentivizing Polarization in Social Networks

Christian Borgs
UC Berkeley
<EMAIL_ADDRESS>Jennifer Chayes
UC Berkeley
<EMAIL_ADDRESS>Christian Ikeokwu
UC Berkeley
<EMAIL_ADDRESS>Ellen Vitercik
Stanford University
<EMAIL_ADDRESS>
###### Abstract

On social networks, algorithmic personalization drives users into filter
bubbles where they rarely see content that deviates from their interests. We
present a model for content curation and personalization that avoids filter
bubbles, along with algorithmic guarantees and nearly matching lower bounds.
In our model, the platform interacts with $n$ users over $T$ timesteps,
choosing content for each user from $k$ categories. The platform receives
stochastic rewards as in a multi-arm bandit. To avoid filter bubbles, we draw
on the intuition that if some users are shown some category of content, then
all users should see at least a small amount of that content. We first analyze
a naive formalization of this intuition and show it has unintended
consequences: it leads to “tyranny of the majority” with the burden of
diversification borne disproportionately by those with minority interests.
This leads us to our model which distributes this burden more equitably. We
require that the probability any user is shown a particular type of content is
at least $\gamma$ times the average probability all users are shown that type
of content. Full personalization corresponds to $\gamma=0$ and complete
homogenization corresponds to $\gamma=1$; hence, $\gamma$ encodes a hard cap
on the level of personalization. We also analyze additional formulations where
the platform can exceed its cap but pays a penalty proportional to its
constraint violation. We provide algorithmic guarantees for optimizing
recommendations subject to these constraints. These include nearly matching
upper and lower bounds for the entire range of $\gamma\in[0,1]$ showing that
the cumulative reward of a multi-agent variant of the Upper-Confidence-Bound
algorithm is nearly optimal. Using real-world preference data, we empirically
verify that under our model, users share the burden of diversification and
experience only minor utility loss when recommended more diversified content.

##  1 Introduction

Over the past decade, large internet platforms have amassed an unprecedented
level of social and political power. Research has shown that the feedback
loops generated by algorithmic recommendations increase polarization [21, 23,
30]. Echo chambers created by algorithmic recommendations on these platforms
can have a wide range of adverse effects, such as amplifying and creating
glass ceilings for minorities [31], as well as limiting exposure and job
recommendations [14]. They also lead to disinformation and propaganda being
disproportionately spread to minoritized groups [15].

In this paper, we propose an approach to content recommendation that
simultaneously preserves the positive aspects of personalization while
avoiding the pitfalls of filter bubbles.

We do so by introducing a model that ensures that if some users are served a
particular category of content, then all users will see at least a small
amount of that content. For example, if a network includes individuals across
a political spectrum, then every user will be exposed to at least a small
amount of news from opposing perspectives. This allows a platform to present
diverse content without forcing content on its users that no one is interested
in. This approach builds upon seminal work by Celis et al. [10] who initiated
the study of algorithmic approaches to reducing polarization. However, our
approach to avoiding filter bubbles is different and our analysis techniques
diverge significantly, as detailed in Section 1.2.

We model a platform recommending content to users with a standard multi-armed
bandit formulation. There are $k$ categories of content—such as fashion,
sports, left-learning political content, right-leaning political content, and
so on—and $n$ users. For each user and content category, the platform receives
a stochastic reward from an unknown distribution for showing the user content
from that category, measured, for example, in terms of engagement or ad
revenue. The platform interacts with the $n$ users over $T$ timesteps, at each
timestep choosing a distribution over content categories for each user. The
platform’s goal is to maximize its cumulative reward. Standard bandit
algorithms would eventually learn for each user the category with maximal
expected reward and only show them content from that category, at which point
the user’s content recommendations would be caught in a filter bubble.

###  1.1 Our contributions

We propose a flexible approach to disincentivizing filter bubbles that adapts
to the interests of the individuals on the network. We summarize our
contributions along the following two axes.

####  1.1.1 Modeling contributions

We first analyze an approach that requires that the distribution of content
shown to any one user is not far from the distribution shown to the
population, so users cannot be siloed into disjoint filter bubbles. However,
we show that the optimal recommendations exacerbate _tyranny of the majority_
: the burden of diversification is borne by groups with minority interests (as
often happens with naive approaches to diversification). A majority group will
exclusively see content that they most enjoy while recommendations for
minority users become far less relevant.

##### An equitable approach to preventing filter bubbles.

The intuition behind our revised approach is that in order to avoid filter
bubbles _and_ tyranny of the majority, (1) users should primarily see content
that they are most interested in (thus avoiding tyranny of the majority), and
(2) if some users are shown a particular type of content, then all users
should see at least a small amount of that content (thus avoiding filter
bubbles). When both requirements are satisfied, users with majority interests
will be exposed to content that interests minority groups and vice versa.

Formally, for each user, we impose the following constraint: we require that
the probability she is shown content from a particular category must be at
least $\gamma$ times the average probability the entire population is shown
content from that category, where $\gamma\in[0,1]$ is a tunable parameter. We
refer to this model as Formulation 1. Setting $\gamma=0$ corresponds to
complete personalization and setting $\gamma=1$ requires that everyone see the
same distribution of content. Moreover, if no one on the network is interested
in some type of content, there is no requirement that users be shown that
content. When $\gamma\leq\frac{1}{2}$, we show that conditions (1) and (2) are
met and thus the burden of diversification is borne more equally among all
users. We also provide a second formulation, called Formulation 2, where
instead of imposing hard constraints, the platform is penalized based on the
the extent to which it violates the $\gamma$ constraint.

##### Taxation without knowledge of the true content distribution.

The penalization described above depends on the true, underlying probabilities
that the platform assigns to different types of content at each timestep. To
augment the flexibility of our approach, we also analyze a model where an
auditor only has access to a dataset describing the types of content that
users were actually shown, as opposed to a description of the true
distributions. In this model, the platform is penalized at the end of the $T$
timesteps based on the extent to which the _empirical_ distribution over
content shown to each user violates the $\gamma$ constraint described above.
We refer to this model as Formulation 3.

####  1.1.2 Technical contributions

Since the platform does not know the reward distributions (corresponding to
the users’ preferences for the different types of content), it must learn a
high-reward policy over the course of the $T$ rounds. We analyze the _regret_
of the Upper-Confidence-Bound (UCB) algorithm. The key challenges we face are
providing nearly-matching lower bounds—which depend on structure exhibited by
the specific constraints that we impose—and bounding the regret under
Formulation 3, under which the optimal policy may be _history-dependent._

##### Regret upper bounds.

Under Formulation 1, we measure regret as the difference between (1) the
cumulative reward of the optimal distribution over content that satisfies our
$\gamma$ constraint and (2) the cumulative reward of the platform’s learning
algorithm. Crucially, the optimal distribution (1) is defined by the users’
reward distributions, but these are unknown to the learning algorithm. When
$\gamma=1$, a variant of the UCB algorithm achieves a regret of
$\tilde{O}(\sqrt{nkT})$ and for $\gamma<1$, another variant achieves a regret
of $\tilde{O}(n\sqrt{kT}).$ Under Formulations 2 and 3, we measure regret with
respect to the optimal policy that maximizes the cumulative reward minus the
penalty. Our regret bounds are $\tilde{O}(n\sqrt{kT})$.

Key challenge. Under Formulation 3, the optimal policy may be _history-
dependent_ : it may dynamically adjust its recommendations based on the
empirical distribution over content thus far, and thus the magnitude of the
final penalty. This is in contrast to Formulations 1 and 2, where the optimal
policy is a fixed distribution over content.

##### Regret lower bounds.

We provide a nearly-matching lower bound on regret under Formulation 1. As in
the upper bound, our lower bound transitions from an $\Omega(n)$ dependence
for small $\gamma$ to an $\Omega(\sqrt{n})$ dependence for large $\gamma$. For
$k=2$ arms, we prove a lower bound of $\Omega(n\sqrt{T})$ for
$\gamma<\frac{1}{2}$. Meanwhile, for all $k\geq 2$ and all $\gamma\in[0,1]$,
we prove a lower bound of $\Omega(\sqrt{nkT})$. This means that no algorithm
has regret better than $\Omega(n\sqrt{T})$ for $\gamma<\frac{1}{2}$ or
$\Omega(\sqrt{nkT})$ for any $\gamma\in[0,1]$.

This transition from a $\Theta(n)$ to $\Theta(\sqrt{n})$ dependence elucidates
a tension between the reward of the optimal policy and the ability of the
learning algorithm to compete with the optimal policy. As $\gamma$ grows, the
set of distributions that the platform can show the user while still
satisfying the $\gamma$ constraint shrinks. Thus, the optimal policy comes
from an increasingly restricted set so the regret benchmark is smaller.
Likewise, as $\gamma$ grows, the learner has to use an increasingly restricted
set of policies to compete with the optimal policy. Since regret shrinks as
$\gamma$ grows, we show that the optimal policy’s reward diminishes at a
faster rate than the learner’s handicap in competing with the optimal policy.

Key challenge. Lower bounds for bandit problems typically follow by
identifying two worst-case problem instances that are similar enough that any
algorithm would not be able to statistically distinguish between them, but are
distinct enough to ensure that even if an algorithm has low regret on one
instance, it will have high regret on the other. Simply creating $n$ copies
(one for each user) of the worst-case problem instances used in standard
bandit lower bounds would lead to a large statistical difference between
problem instances, thus precluding an $\Omega(n)$ dependence. Our lower bound
construction therefore takes advantage of structure specific to our model.

##### Experiments.

We analyze the optimal policies under the formulations from Section 1.1.1
using real user preference data [18]. We empirically verify that when users’
preferences are heterogeneous, subgroups share the burden of diversification.
We also show that users experience only a minor loss in utility when
recommended diversified content.

###  1.2 Related work

There has been significant interest in understanding the mechanics of how
recommender systems affect large-scale opinion dynamics, and if and when they
lead to polarization [e.g., 16, 6, 28]. Most of the analysis has focused on
how recommender systems impact network structure [32] and how this affects the
spread of information and the opinions of members on the network. Recently
there have been growing calls to algorithmically increase “exposure diversity”
and combat filter bubbles [7, 13, 19]. Castells et al. [9] discuss
methodologies and metrics to assess recommendation diversity, and Halpern et
al. [17] analyze the trade-off between diversity and engagement in
recommendation algorithms.

The most related research to ours is seminal work by Celis et al. [10], who
initiated the study of algorithmic approaches to reducing polarization. There
are a variety of differences between our work and theirs, highlighted below.

  * •

_Modeling approach._ Celis et al. [10] suggest that a regulator should place
pre-determined, fixed upper and lower bounds on the probability that each arm
is played so that no user can exclusively see one type of content. Choosing
bounds for each type of content, however, may be challenging. (For example,
how should bounds on fashion content and major world events compare?)
Moreover, if no user is interested in a type of content, it may not make sense
to force all users to see it. The regulator would have to make these
differential decisions, which would be a divisive and controversial task.
These concerns are largely ameliorated under our model.

  * •

_Stronger assumption on the regulator’s knowledge._ Celis et al. [10] assume
the regulator can control the exact probabilities that the platform shows
different types of content to users. In contrast, in our Formulation 3, we
propose a tax based on the content that the platform actually showed the user.
As we describe in Section 1.1.2, this introduces technical challenges in
providing a no-regret algorithm for the platform.

  * •

_Lower bounds._ Our nearly-matching lower bounds help develop a complete
understanding of this problem.

Since the multi-armed bandit problem was proposed [33], many variants have
been studied, such as bandits with budgets [5, 29, 1], bandits with
constraints [27, 3, 26, 12], and bandits with floors on content [34, 11]. Only
a few variants [e.g., 20] study multi-agent settings. However, they usually
still involve a common reward like in the classical multi-armed bandit
problem. There has also been recent work on fairness in multi-armed bandits
[e.g., 20, 22] but none of these focus on the issues of filter bubbles and
polarization in social networks.

##  2 Notation and model

We use
$\pazocal{P}^{d-1}=\\{\bm{x}\in[0,1]^{d}:\left\lVert\bm{x}\right\rVert_{1}=1\\}$
to denote the probability simplex and $[k]$ to denote the set
$[k]=\\{1,2,\dots,k\\}.$

##### Problem definition.

There are $n$ users and $k$ categories of content—for example, fashion,
sports, right-leaning news, left-leaning news, and so on—each modeled as an
_arm_ of a _$k$ -armed bandit_. An instance of our problem, denoted
$\nu=\left\\{\mathscr{D}_{i,j}:i\in[n],j\in[k]\right\\}$, is defined by reward
distributions $\mathscr{D}_{i,j}$ over $[0,1]$ with density function
$f_{i,j}:[0,1]\to\mathbb{R}_{\geq 0}$. This distribution models the platform’s
reward for showing user $i$ content from category $j$, measured in terms of
engagement or ad revenue, for example. The set of all instances $\nu$ is
denoted $\mathscr{E}^{n,k}$. The mean of user $i$’s reward distribution for
arm $j$ is denoted $\mu_{i,j}\in[0,1]$, with
$\bm{\mu}_{i}=\left(\mu_{i,1},\dots,\mu_{i,k}\right)$. The instance $\nu$ is
unknown to the platform.

##### Interaction between platform and users.

This interaction takes place over $T$ timesteps. At each timestep $t\in[T]$:

  1. 1.

The platform selects an _action_ , which is a distribution over arms for each
user. This distribution corresponds to a random variable
$\bm{A}_{t}\in[k]^{n}$ over arm choices for each of the $n$ users. We use the
notation $\bm{a}_{t}\in[k]^{n}$ to denote the specific set of arms the
platform plays on round $t$, so it is a realization of the random variable
$\bm{A}_{t}.$

  2. 2.

Given the set of arms
$\bm{a}_{t}=\left(a_{t,1},\dots,a_{t,n}\right)\in[k]^{n}$, the platform
receives a reward for each user. The reward for user $i$ is drawn from the
distribution $\mathscr{D}_{i,a_{t,i}}$. We use the random variable
$\bm{X}_{t}=\left(X_{t,1},\dots,X_{t,n}\right)\in[0,1]^{n}$ to denote the
platform’s reward on round $t$. We also use $\bm{x}_{t}\in[0,1]^{n}$ to denote
a realization of this random variable.

##### Platform’s learning algorithm.

The platform uses a learning algorithm, or _policy_ , $\pi$ to decide the
distribution over arms at each timestep. On timestep $t\in[T]$, the
(randomized) policy $\pi$ takes as input the history
$\bm{h}_{t-1}=\left(\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1}\right)\in([k]^{n}\times[0,1]^{n})^{t-1}$
and returns the set of arms $\bm{a}_{t}\in[k]^{n}$ that will be played on
round $t$. The conditional probability that $\bm{A}_{t}=\bm{a}_{t}$ given the
history
$\bm{A}_{1}=\bm{a}_{1},\bm{X}_{1}=\bm{x}_{1},\dots,\bm{A}_{t-1}=\bm{a}_{t-1},\bm{X}_{t-1}=\bm{x}_{t-1}$
is denoted
$\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})$, or
more compactly as $\pi(\bm{a}_{t}\mid\bm{h}_{t-1})$. The notation $\Pi^{n,k}$
denotes the set of all policies $\pi$.

##### Distribution over outcomes.

Since the reward distributions are independent, the conditional distribution
of the reward $\bm{X}_{t}\in[0,1]^{n}$ given
$\bm{A}_{t}=\bm{a}_{t}=\left(a_{t,1},\dots,a_{t,n}\right)\in[k]^{n}$ has
density function

$f_{\bm{a}_{t}}\left(\bm{x}_{t}\right)=\prod_{i=1}^{n}f_{i,a_{t,i}}\left(x_{t,i}\right).$

The interaction between the policy $\pi$ and the instance $\nu$ induces a
distribution $\mathbb{P}_{\pi\nu}$ over outcomes with density function

$f_{\pi\nu}\left(\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{T},\bm{x}_{T}\right)=\prod_{t=1}^{T}\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f_{\bm{a}_{t}}(\bm{x}_{t}).$
(1)

##### Platform’s goal.

The platform’s overall goal is to choose a policy $\pi$ that optimizes its
total reward

$\mathop{\mathbb{E}}_{\pi\nu}\left[\sum_{i=1}^{n}\sum_{t=1}^{T}X_{i,t}\right].$
(2)

For each user $i\in[n]$, the optimal policy would choose the arm $j_{i}$ that
maximizes expected reward:
$j_{i}=\textnormal{argmax}_{j\in[k]}\left\\{\mu_{i,j}\right\\}$. Classic
bandit algorithms will eventually converge to this policy. However, repeatedly
showing user $i$ content from category $j_{i}$ traps the user in a filter
bubble. In the next sections, we limit the platform’s ability to form filter
bubbles.

##  3 A first attempt to disincentivize filter bubbles

We begin with a naive first attempt at disincentivizing filter bubbles and
show that it has the harsh unintended consequence of exacerbating “tyranny of
the majority”: the burden of diversification is borne by those with minority
interests. Interestingly, this issue mirrors real-world attempts at
diversification where the labor associated with diversification is put
disproportionately on members of the underrepresented groups.

To motivate this first attempt, we observe that in a network with severe
filter bubbles, members are partitioned into groups which are exposed to
disparate types of content. Thus, our first attempt at avoiding filter bubbles
ensures that the content recommendations are not too “spread out.” We
formalize this intuition by requiring that each user’s distribution over
content is not too far from the average distribution over content shown to the
entire population.

More formally, building on the notation from Section 2, let
$\pi_{i}(j\mid\bm{h}_{t-1})$ denote the marginal probability that the platform
shows user $i$ arm $j$ on timestep $t$ given the history $\bm{h}_{t-1}$, with
$\bm{\pi}_{i}(\bm{h}_{t-1})=\left(\pi_{i}(1\mid\bm{h}_{t-1}),\dots,\pi_{i}(k\mid\bm{h}_{t-1})\right)$.
Next, let
$\bar{\bm{\pi}}(\bm{h}_{t-1})=\frac{1}{n}\sum_{i=1}^{n}\bm{\pi}_{i}(\bm{h}_{t-1})$
denote the average of these marginal distributions. The $j^{th}$ component of
$\bar{\bm{\pi}}(\bm{h}_{t-1})$, denoted $\bar{\pi}(j\mid\bm{h}_{t-1})$,
measures the average probability that arm $j$ is shown to any user. Under our
naive first approach, we require that the distance between the vectors
$\bm{\pi}_{i}(\bm{h}_{t-1})$ and $\bar{\bm{\pi}}(\bm{h}_{t-1})$ is small under
the $\ell_{\infty}$-norm:

$\left\lVert\bm{\pi}_{i}(\bm{h}_{t-1})-\bar{\bm{\pi}}(\bm{h}_{t-1})\right\rVert_{\infty}=\max_{j\in[k]}\left|\pi_{i}(j\mid\bm{h}_{t-1})-\bar{\pi}(j\mid\bm{h}_{t-1})\right|\leq\Delta$
(3)

for some $\Delta>0$. (The $\ell_{\infty}$-norm could be replaced by any norm,
but we use the $\ell_{\infty}$-norm for this exposition.)

We now show that the optimal policy
$\bm{p}_{1}^{*},\dots,\bm{p}_{n}^{*}\in\pazocal{P}^{k-1}$ leads to tyranny of
the majority, where

$\bm{p}_{1}^{*},\dots,\bm{p}_{n}^{*}=\textnormal{argmax}_{\bm{p}_{1},\dots,\bm{p}_{n}}\left\\{\sum_{i=1}^{n}\bm{\mu}_{i}\cdot\bm{p}_{i}:\left\lVert\bm{p}_{i}-\frac{1}{n}\sum_{i^{\prime}=1}^{n}\bm{p}_{i^{\prime}}\right\rVert_{\infty}\leq\Delta,\forall
i\in[n]\right\\}.$

To illustrate the pitfalls of this approach, we analyze a setting where there
are two types of content (e.g., left- and right-leaning political content) and
the users can be partitioned into disjoint sets where one set only likes
content from the first category (i.e., $\bm{\mu}_{i}=(1,0)$). Meanwhile, the
other set only likes content from the second category (i.e.,
$\bm{\mu}_{i}=(0,1)$). Without loss of generality, we assume that the former
set—which we denote as $N$—is the majority.

When $\Delta\geq\frac{|N|}{n}$, the constraints are meaningless and allow for
full personalization: $\bm{p}_{i}^{*}=(1,0)$ if $i\in[N]$ and
$\bm{p}_{i}^{*}=(0,1)$ if $i\not\in[N]$. Therefore, we analyze the case where
$\Delta<\frac{|N|}{n}$. We show that under the optimal policy, the majority
group will be able to exclusively see the content that they enjoy:
$\bm{p}_{i}^{*}=(1,0)$ if $i\in N$. Meanwhile, the minority group’s
recommendations take a hit in order to ensure that the constraints are
satisfied. In particular, for all $i\not\in N$,
$\bm{p}_{i}^{*}=\left(1-\frac{n\Delta}{|N|},\frac{n\Delta}{|N|}\right)$. The
proof of the following lemma is in Appendix A.

######  Lemma 3.1.

Suppose that there are $k=2$ arms and for some set $N\subseteq[n]$ with
$|N|\geq\frac{n}{2}$, $\bm{\mu}_{i}=(1,0)$ for all $i\in N$ and
$\bm{\mu}_{i}=(0,1)$ for all $i\not\in N$. If $\Delta<\frac{|N|}{n}$, then
$\bm{p}_{i}^{*}=(1,0)$ if $i\in N$ and
$\bm{p}_{i}^{*}=\left(1-\frac{n\Delta}{|N|},\frac{n\Delta}{|N|}\right)$
otherwise.

Lemma 3.1 illustrates that under this approach, tyranny of the majority
prevails at the expense of minority interests.

##  4 Equitable approaches to disincentivizing filter bubbles

Motivated by Section 3, we propose three different formulations for
disincentivizing filter bubbles that avoid tyranny of the majority. The
intuition behind these approaches is built upon the following two pillars:

  1. 1.

To avoid tyranny of the majority, users should primarily be recommended
content they are most interested in,

  2. 2.

But to avoid filter bubbles, that content must contain a flavor of the content
shown to the entire population.

We show that it is possible to achieve both of these ends. If both conditions
are satisfied, then a policy like that of Lemma 3.1 where the majority group
sees no minority content is not possible. By the first requirement, groups
with minority interests will be recommended content that they are interested
in, which means that by the second requirement, the majority group’s content
recommendations will contain a small amount of that minority content, and vice
versa.

###  4.1 Formulation 1: Personalization constraint

In our first formulation, we require that for each user $i\in[n]$,
$\bm{\pi}_{i}(\bm{h}_{t-1})$ is at least $\gamma\bar{\bm{\pi}}(\bm{h}_{t-1})$
for some $\gamma\in[0,1]$:

$\bm{\pi}_{i}(\bm{h}_{t-1})\geq\gamma\bar{\bm{\pi}}(\bm{h}_{t-1}).$ (4)

Each user’s recommendations become less personalized as $\gamma$ grows.

To illustrate the benefit of this approach over that of Section 3, we analyze
the same polarized example where there is a majority group $N$ with
$\bm{\mu}_{i}=(1,0)$ for all $i\in N$. For the minority group,
$\bm{\mu}_{i}=(0,1)$ for all $i\not\in N.$ For all $\gamma\leq\frac{1}{2}$, we
show that under the optimal policy, the majority of each group’s content
recommendations match their interests, but both groups see some content that
appeals to the opposing group. In this case the optimal policy is defined as

$\bm{p}_{1}^{*},\dots,\bm{p}_{n}^{*}=\textnormal{argmax}_{\bm{p}_{1},\dots,\bm{p}_{n}}\left\\{\sum_{i=1}^{n}\bm{\mu}_{i}\cdot\bm{p}_{i}:\bm{p}_{i}\geq\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\bm{p}_{i^{\prime}},\forall
i\in[n]\right\\}.$ (5)

The proof of the following lemma is in Appendix B.

######  Lemma 4.1.

Suppose that there are $k=2$ arms and for some set $N\subseteq[n]$,
$\bm{\mu}_{i}=(1,0)$ for all $i\in N$ and $\bm{\mu}_{i}=(0,1)$ for all
$i\not\in N$. For $\gamma\leq\frac{1}{2}$, the optimal policy has the
following form:

$\bm{p}_{i}^{*}=\begin{cases}\left(1-\frac{\gamma(n-|N|)}{n},\frac{\gamma(n-|N|)}{n}\right)&\text{if
}i\in N\\\ \left(\frac{\gamma|N|}{n},1-\frac{\gamma|N|}{n}\right)&\text{if
}i\not\in N.\end{cases}$

Since $\gamma\leq\frac{1}{2}$, this policy ensures that users are mostly
recommended content that they are interested in:
$\bm{\mu}_{i}\cdot\bm{p}_{i}^{*}\geq 1-\gamma\geq\frac{1}{2}$ for all
$i\in[n].$ However, they are still shown a small fraction of content that the
other set of the population is interested in. We note that when $N$ is the
majority group $\left(|N|\geq\frac{n}{2}\right)$, the minority group
$[n]\setminus N$ still sees more content that they are not interested in than
the majority group because $\frac{\gamma|N|}{n}\geq\frac{\gamma(n-|N|)}{n}$.
However, the burden of diversification is split far more equally among the two
groups than in Lemma 3.1. The policy mirrors a typical mode of community forum
discussions where members split time between listening to the opinions of each
person in the entire group (for a $\gamma$-fraction of the time) and breaking
into focus groups about specific topics (for a $(1-\gamma)$-fraction of the
time).

In Section 5, we provide upper and lower bounds on the platform’s _regret_
with respect to the optimal policies $\bm{p}_{1}^{*},\dots,\bm{p}_{n}^{*}$
defined in Equation (5). Regret measures the difference between the total
reward of the optimal policy and that of the platform’s policy $\pi$. In other
words, for any instance $\nu$ and policy $\pi$, the expected regret is defined
as

$R_{T,1}(\pi,\nu)=T\sum_{i=1}^{n}\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\mathop{\mathbb{E}}_{\pi\nu}\left[\sum_{i=1}^{n}\sum_{t=1}^{T}X_{i,t}\right].$
(6)

###  4.2 Formulation 2: Personalization penalty

We analyze a second formulation where there are no constraints on the
platform’s policy, but the platform is penalized based on the extent to which
Equation (4) is violated. Given a parameter $\eta\geq 0$, this penalty is
defined as

$\eta\sum_{i=1}^{n}\sum_{j=1}^{k}\max\left\\{\gamma\bar{\bm{\pi}}(j\mid\bm{h}_{t-1})-\pi_{i}(j\mid\bm{h}_{t-1}),0\right\\}.$

In other words, the platform’s goal is to maximize its cumulative reward

$\displaystyle\text{reward}_{2}(\pi,\nu;\eta,\gamma)$ $\displaystyle=\,$
$\displaystyle\mathop{\mathbb{E}}_{\pi\nu}\left[\sum_{i=1}^{n}\left(\sum_{t=1}^{T}X_{i,t}-\eta\sum_{j=1}^{k}\max\left\\{\gamma\bar{\bm{\pi}}(j\mid\bm{h}_{t-1})-\pi_{i}(j\mid\bm{h}_{t-1}),0\right\\}\right)\right]$
$\displaystyle=\,$
$\displaystyle\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi\nu}\left[\sum_{i=1}^{n}\left(\bm{\mu}_{i}\cdot\bm{\pi}_{i}(\bm{h}_{t-1})-\eta\sum_{j=1}^{k}\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\pi_{i^{\prime}}(j\mid\bm{h}_{t-1})-\pi_{i}(j\mid\bm{h}_{t-1}),0\right\\}\right)\right].$
(7)

The policy that maximizes Equation (7) is history independent and can be
written as $\bm{p}^{*}=\left(\bm{p}_{1}^{*},\dots,\bm{p}_{n}^{*}\right)$ with
$\bm{p}_{i}^{*}\in\pazocal{P}^{k-1}.$ The expected regret of a policy $\pi$
under this formulation is
$R_{T,2}(\pi,\nu)=\text{reward}_{2}(\bm{p}^{*},\nu;\eta,\gamma)-\text{reward}_{2}(\pi,\nu;\eta,\gamma)$.

###  4.3 Formulation 3: Personalization penalty on the empirical distribution

Sections 4.1 and 4.2 describe models in which the platform is subject to
constraints or penalties based on the _true_ distribution over content that it
shows users. However, an auditor may only have access to the _realizations_ of
those distributions—that is, the set of arms $a_{t,i}\in[k]$ shown to each
user $i$ at timestep $t$. Formulation 3 covers a setting in which a regulator
penalizes the platform at the end of the $T$ timesteps based on the empirical
distribution over content. Specifically, let
$\hat{p}_{i,j}=\frac{1}{T}\sum_{t=1}^{T}\textbf{1}_{\\{A_{t,i}=j\\}}$ be the
average number of times that the platform pulls arm $j$ for user $i$. At the
end of the $T$ timesteps, the platform is penalized based on how small
$\hat{p}_{i,j}$ is compared to
$\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}$. In
particular, given a normalizing factor $\eta$, we define a penalty that is the
analogue of Equation (7):

$\eta\sum_{i=1}^{n}\sum_{j=1}^{k}\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}.$

The platform’s goal is therefore to maximize their expected total payoff minus
this penalty, which is equal to

$\displaystyle\text{reward}_{3}(\pi,\nu;\eta,\gamma)$
$\displaystyle=\mathop{\mathbb{E}}_{\pi\nu}\left[\sum_{i=1}^{n}\left(\sum_{t=1}^{T}X_{i,t}-\eta\sum_{j=1}^{k}\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}\right)\right]$
$\displaystyle=\sum_{i=1}^{n}\left(\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi\nu}\left[\bm{\mu}_{i}\cdot\bm{\pi}_{i}(\bm{h}_{t-1})\right]-\eta\sum_{j=1}^{k}\mathop{\mathbb{E}}_{\pi\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}\right]\right).$
(8)

Let $\pi^{*}$ be the policy that maximizes Equation (8). The regret of $\pi$
is

$R_{T,3}(\pi,\nu)=\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)-\text{reward}_{3}(\pi,\nu;\eta,\gamma).$

A key difference between Equation (7) and Equation (8) is that in Equation
(7), the platform is penalized at every timestep whereas in Equation (8), the
platform is penalized at the end of the $T$ timesteps. We make this
distinction because the empirical distribution over content at a single
timestep would be extremely noisy.

##  5 Regret analysis

In this section, we discuss algorithms that the platform can use to minimize
regret in the three formulations from Section 4. We also provide a nearly-
matching lower bound on regret for Formulation 1 in Section 5.1.3.

###  5.1 Regret analysis for Formulation 1

We begin with lower bounds on regret under Formulation 1. In Section 5.1.1, we
show that a variant of the UCB algorithm has regret $O(n\sqrt{Tk})$ for
$\gamma<1$ and in Section 5.1.2, we show that a different variant of UCB has
regret $O(\sqrt{nkT})$ for $\gamma=1$. We then prove in Section 5.1.3 that
these bounds are nearly optimal: for $\gamma\leq\frac{1}{2}$ and $k=2$, no
algorithm can achieve regret better than $\Omega(n\sqrt{T})$, and for all
$k\geq 2$ and $\gamma\in[0,1]$ (including $\gamma>\frac{1}{2}$) our bound is
$\Omega(\sqrt{nkT})$.

The transition from a $\Theta(n)$ to a $\Theta(\sqrt{n})$ dependence
illustrates that as $\gamma$ grows, the platform is better able to compete
with the optimal policy subject to the $\gamma$ constraints. As $\gamma$
grows, the platform has a smaller set of distributions that it can use to
compete with the optimal policy while obeying the $\gamma$ constraints.
However, for the same reason, the cumulative reward of the optimal policy
shrinks as $\gamma$ grows. Intuitively, the transition from a $\Theta(n)$ to a
$\Theta(\sqrt{n})$ dependence as $\gamma$ grows illustrates that the optimal
policy’s reward degrades faster than the platform’s ability to compete with
that policy.

####  5.1.1 Regret upper bound when $\gamma<1$

We analyze a multi-agent variant of the UCB algorithm, which we call $n$-UCB,
and show that it has regret $O(n\sqrt{Tk})$ when $\gamma<1$.

The $n$-UCB algorithm essentially runs a copy of classic UCB for each user,
but coordinates amongst these $n$ UCB copies to ensure that they satisfy the
global constraints. This requires $n$-UCB to play distributions over arms from
the set of distributions $\left(\bm{p}_{1},\dots,\bm{p}_{n}\right)$ that
satisfy the constraints:
$\bm{p}_{i}\geq\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\bm{p}_{i^{\prime}}$ for
all $i\in[n]$. This is in contrast to the classic case where UCB plays a
single arm at each timestep. For completeness, we include a full description
of $n$-UCB (Algorithm 1) and the proof of the following theorem in Appendix C.

######  Theorem 5.1.

Let $\pi$ be the policy of $n$-UCB. Then
$R_{T,1}(\pi,\nu)=\tilde{O}(n\sqrt{kT})$.

####  5.1.2 Regret upper bound when $\gamma=1$

When $\gamma=1$, all users must be shown the same distribution of content. We
can therefore reduce our problem to a single-agent bandit problem with the
reward distributions $\mathscr{D}_{j}=\sum_{i=1}^{n}\mathscr{D}_{i,j}$ for all
arms $j\in[k]$. We adapt the robust-UCB framework by Bubeck et al. [8] with
the median-of-means estimator [2], as summarized by Algorithm 2 in Appendix D.
The full proof of the following theorem is in Appendix D.

######  Theorem 5.2.

Let $\pi$ be the policy of Robust-UCB. Then
$R_{T,1}(\pi,\nu)=\tilde{O}(\sqrt{nkT}).$

####  5.1.3 Regret lower bound

In this section, we provide nearly-matching regret lower bounds. Our first
bound holds when there are $k=2$ arms, $\gamma\leq\frac{1}{2}$, and $n$ is
sufficiently large ($n>100$). In this case, we prove a regret lower bound of
$\Omega(n\sqrt{T})$. Meanwhile, for all $k\geq 2$ and $\gamma\in[0,1]$
(including $\gamma>\frac{1}{2}$), we provide a bound of $\Omega(\sqrt{nkT})$.

We begin with our main result (Theorem 5.3) and show in Corollary 5.4

######  Theorem 5.3.

For all $T\geq 4$, the regret is lower bounded as follows:

$\inf_{\pi\in\Pi^{n,2}}\sup_{\nu\in\mathscr{E}^{n,2}}R_{T,1}(\pi,\nu)\geq\max\left\\{\sqrt{\frac{T}{8}}\left(\frac{n}{8e}-\gamma\left(\frac{n}{8e}+\sqrt{\frac{n}{2\pi}}\right)\right),\frac{\sqrt{nT}}{16e}\right\\}.$

###### Proof.

This theorem follows directly from Lemmas 5.5 and 5.6. ∎

######  Corollary 5.4.

For all $n>100$, $\gamma\leq\frac{1}{2}$, and $T\geq 4$, the regret is lower
bounded as

$\inf_{\pi\in\Pi^{n,2}}\sup_{\nu\in\mathscr{E}^{n,2}}R_{T,1}(\pi,\nu)\geq\frac{n\sqrt{T}}{900}.$

We now provide a proof sketch of the first part of Theorem 5.3. The full proof
is in Appendix E.

######  Lemma 5.5.

For all $T\geq 1$, the regret is lower bounded as follows:

$\inf_{\pi\in\Pi^{n,2}}\sup_{\nu\in\mathscr{E}^{n,2}}R_{T,1}(\pi,\nu)\geq\sqrt{\frac{T}{8}}\left(\frac{n}{8e}-\gamma\left(\frac{n}{8e}+\sqrt{\frac{n}{2\pi}}\right)\right).$
(9)

###### Proof sketch.

Our proof is based on worst-case instances $\nu_{\bm{b}}$ defined for any
vector $\bm{b}\in\\{0,1\\}^{n}$. For each agent $i\in[n]$, their reward
distributions for the two arms are Bernoulli with means
$\bm{\mu}_{i}=\left(\mu_{i,0},\mu_{i,1}\right)$ where
$\bm{\mu}_{i}=\left(\frac{1}{2}+\epsilon,\frac{1}{2}\right)$ if $b_{i}=0$,
$\bm{\mu}_{i}=\left(\frac{1}{2},\frac{1}{2}+\epsilon\right)$ if $b_{i}=1$, and
$\epsilon=\sqrt{\frac{1}{8T}}.$ We lower bound the expected regret
$\mathop{\mathbb{E}}\left[R_{T,1}\left(\pi,\nu_{\bm{b}}\right)\right]$ by the
right-hand-side of Equation (9), where the expectation is over both the draw
of the vector $\bm{b}\sim\text{Unif}\left(\\{0,1\\}^{n}\right)$ and the
distribution over outcomes $\mathbb{P}_{\pi\nu_{\bm{b}}}$. This implies that
there exists an instance $\nu_{\bm{b}}$ such that
$R_{T,1}\left(\pi,\nu_{\bm{b}}\right)\geq\sqrt{\frac{T}{8}}\left(\frac{n}{8e}-\gamma\left(\frac{n}{8e}+\sqrt{\frac{n}{2\pi}}\right)\right)$.

Without constraints, the optimal policy would exclusively show arm $0$ to each
user $i\in[n]$ with $b_{i}=0$ since it has higher reward for these users, and
similarly it would exclusively show arm $1$ to each user $i\in[n]$ with
$b_{i}=1$. Due to the constraints, both the optimal policy and the policy
$\pi$ must show some users the “wrong” arm on a non-negligible fraction of
rounds. In total, the policy $\pi$ will lose the following reward from showing
users the wrong arms:

$\epsilon\mathop{\mathbb{E}}_{\bm{b}}\left[\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i}\left(1\mid\bm{h}_{t-1}\right)\right]+\sum_{i:b_{i}=1}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i}\left(0\mid\bm{h}_{t-1}\right)\right]\right)\right].$

We begin by proving that that optimal policy loses at most

$\sqrt{\frac{T}{8}}\cdot\frac{\gamma(n-1)}{2}$ (10)

total reward from showing users the wrong arms. Meanwhile, we prove that any
policy $\pi$ will lose at least

$\sqrt{\frac{T}{8}}\left(\frac{\gamma
n}{2}+\frac{n}{8e}-\gamma\left(\frac{n}{8e}+\sqrt{\frac{n}{2\pi}}\right)\right)$
(11)

total reward. We prove this by showing that for any user $i\in[n]$, the
distribution over outcomes conditioned on $b_{i}=0$ is close to the
distribution over outcomes conditioned on $b_{i}=1$. Intuitively, this means
that any policy $\pi$ will struggle to distinguish whether $b_{i}=0$ or
$b_{i}=1$. Taking the difference of (11) and (10) implies the lemma. ∎

We conclude by proving that for all $\gamma\in[0,1]$ and $k\geq 2$, regret is
lower bounded by

$\frac{1}{16e}\sqrt{nT(k-1)}.$

The proof is similar to that of existing bandit lower bounds [e.g., 24,
Theorem 15.2], so we include it for completeness in Appendix E.

######  Lemma 5.6.

For all $T\geq\frac{7(k-1)}{n}$, the regret is lower bounded as follows:

$\inf_{\pi\in\Pi^{n,k}}\sup_{\nu\in\mathscr{E}^{n,k}}R_{T,1}(\pi,\nu)\geq\frac{\sqrt{nT(k-1)}}{16e}.$

###  5.2 Regret analysis for Formulation 2

Under Formulation 2, a variation on UCB we call Penalty-UCB (Algorithm 3)
achieves regret $\tilde{O}(n\sqrt{kT})$. Penalty-UCB maintains estimates
$\bm{\hat{\mu}}_{i}^{(t)}$ of each $\bm{\mu}_{i}$ and selects the distribution
maximizing the estimated reward minus the penalty:

$\left(\bm{p}_{i}^{(t)}\right)_{i\in[n]}=\operatorname*{argmax}\left\\{\sum\limits_{i=1}^{n}\bm{p}_{i}\cdot\bm{\hat{\mu}}_{i}^{(t)}-\eta\sum_{j=1}^{k}\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},j}-p_{i,j},0\right\\}\right\\}.$

For completeness, we include the proof of the following theorem in Appendix F.

######  Theorem 5.7.

Let $\pi$ be the policy of Penalty-UCB. Then
$R_{T,2}(\pi,\nu)=\tilde{O}(n\sqrt{kT}).$

###  5.3 Regret analysis for Formulation 3

A key challenge under Formulation 3 is that the platform’s optimal strategy,
given perfect information about the reward distributions $\mathscr{D}_{i,j}$,
may be _history dependent_. For example, the platform may choose to increase
or decrease personalization dynamically based on the empirical distribution of
content chosen thus far.

Nonetheless, we show that Penalty-UCB (Algorithm 3) competes with the optimal
history-dependent policy by reducing our analysis to that of Section 5.2. We
use the notation $\pi^{*}$ to denote the optimal policy that maximizes
Equation (8).

First, we show that under Formulation 2, the optimal policy obtains a larger
reward (measured in terms of $\text{reward}_{2}$) than $\pi^{*}$ under
Formulation 3 (measured in terms of $\text{reward}_{3}$). The full proof is in
Appendix G.

######  Lemma 5.8.

Let $\bm{p}^{*}=\left(\bm{p}_{1}^{*},\dots,\bm{p}_{n}^{*}\right)$ with
$\bm{p}_{i}^{*}\in\pazocal{P}^{k-1}$ be the policy that maximizes
$\text{reward}_{2}\left(\bm{p},\nu;\frac{\eta}{T},\gamma\right)$. Then

$\text{reward}_{2}\left(\bm{p}^{*},\nu;\frac{\eta}{T},\gamma\right)\geq\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma).$

###### Proof sketch.

For any arm $j\in[k]$, we can exchange the expectation and the maximum in
Equation (8) as follows:

$\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}\right]\geq\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\hat{p}_{i^{\prime},j}\right]-\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\hat{p}_{i,j}\right],0\right\\}.$

By definition of $\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\hat{p}_{i,j}\right]$,
this allows us to show that $\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)$ is
upper-bounded by

$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{k}$
$\displaystyle\left(\sum_{t=1}^{T}\mu_{i,j}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right]\right.$
$\displaystyle\left.-\eta\max\left\\{\frac{1}{T}\sum_{t=1}^{T}\left(\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i^{\prime}}(j\mid\bm{h}_{t-1})\right]-\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right]\right),0\right\\}\right).$
(12)

We next define the history-independent policy
$\bm{p}=\left(\bm{p}_{1},\dots,\bm{p}_{n}\right)$ such that

$p_{i,j}=\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi_{i}^{*}(j\mid\bm{h}_{t-1})\right].$

We rearrange Equation (12) and use the definition of $\bm{p}^{*}$ to get that

$\displaystyle\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{j=1}^{k}\left(T\mu_{i,j}p_{i,j}-\eta\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},j}-p_{i,j},0\right\\}\right)$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{j=1}^{k}\left(T\mu_{i,j}p^{*}_{i,j}-\eta\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p^{*}_{i^{\prime},j}-p^{*}_{i,j},0\right\\}\right)=\text{reward}_{2}\left(\bm{p}^{*},\nu;\frac{\eta}{T},\gamma\right).$

∎

Next, we show that for any policy $\pi$ that deterministically plays each of
the $k$ arms once in the first $k$ rounds, the difference between its rewards
under Formulations 2 and 3 is bounded. This condition holds for Penalty-UCB
(Algorithm 3) and could be removed with a slightly more involved analysis. The
full proof is in Appendix G.

######  Lemma 5.9.

Let $\pi$ be any policy such that $\pi_{i}(t\mid\bm{h}_{t-1})=1$ for all
$t\leq k$ and $i\in[n]$. For any instance $\nu$,

$\text{reward}_{2}\left(\pi,\nu;\frac{\eta}{T},\gamma\right)\leq\text{reward}_{3}(\pi,\nu;\eta,\gamma)+\eta
nk(\gamma+1)\sqrt{\frac{10\log T}{T}}.$

###### Proof sketch.

For any arm $j\in[k]$, we can exchange the expectation and the maximum in
Equation (7) as follows:

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\pi_{i^{\prime}}(j\mid\bm{h}_{t-1})-\pi_{i}(j\mid\bm{h}_{t-1}),0\right\\}\right]$
$\displaystyle\geq\,$
$\displaystyle\max\left\\{\mathop{\mathbb{E}}_{\pi\nu}\left[\frac{1}{T}\sum_{t=1}^{T}\left(\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\textbf{1}_{\\{A_{t,i^{\prime}}=j\\}}-\textbf{1}_{\\{A_{t,i}=j\\}}\right)\right],0\right\\}.$
(13)

Next, we use a result by Aven [4] to show that the right-hand-side of Equation
(13) is lower-bounded by

$\mathop{\mathbb{E}}_{\pi\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}\right]-\sqrt{\frac{1}{2T^{2}}\cdot\text{Var}\left(\sum_{t=1}^{T}\left(\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\textbf{1}_{\\{A_{t,i^{\prime}}=j\\}}-\textbf{1}_{\\{A_{t,i}=j\\}}\right)\right)}.$
(14)

We upper-bound the variance term in Equation (14) by $20T(\gamma+1)^{2}\log
T$, which implies the lemma statement. ∎

Our regret bound follows from Lemmas 5.8 and 5.9 as well as Theorem 5.7. The
proof is in Appendix G.

######  Theorem 5.10.

Let $\pi$ be the policy played by Algorithm 3. Then the regret is bounded as

$\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)-\text{reward}_{3}(\pi,\nu;\eta,\gamma)=\tilde{O}\left(n\sqrt{kT}+\frac{\eta
nk(1+\gamma)}{\sqrt{T}}\right).$

Even if $\eta$ grows linearly in $T$, the regret bound in Theorem 5.10 will
only grow with $\sqrt{T}$.

##  6 Empirical Results

To explore how our framework impacts exposure diversity in practice, we test
it out on real world data: the MovieLens dataset [18] which describes people’s
expressed preferences for movies111We use this dataset in order to analyze our
methods on real-world user preferences, recognizing that movie recommendation
filter bubbles would likely not be as pernicious as political news filter
bubbles, for example.. These preferences take the form of ¡user, item, rating,
timestamp¿ tuples, each the result of a user giving a 0–5 star rating for a
movie at a particular time.

###  6.1 Experimental setup

There are $n=58$ users, randomly selected from the database, and a set
$\mathscr{K}$ of $k=18$ movie genres: $\mathscr{K}=\\{$Action, Adventure,
Animation, Children, Comedy, Crime, Documentary, Drama, Fantasy, Film-Noir,
Horror, Musical, Mystery, Romance, Sci-Fi, Thriller, War, Western$\\}$. Each
genre is paired with an associated index in $[k]$ determined by alphabetically
ordering $\mathscr{K}$.

For each movie $m\in\pazocal{M}$ , where $\pazocal{M}$ is the set of all
movies, there is an associated genre set $m_{K}\subseteq[k]$ with $|m_{K}|\geq
1$ (a movie could belong to multiple genres). We use the ratings data to
generate preferences for the users. For each movie $m\in\pazocal{M}_{i}$,
where $\pazocal{M}_{i}$ is the set of movies watched by user $i\in[n]$, the
user gives a numeric rating $r_{i,m}$ on a 5-star scale with half-star
increments: $r_{i,m}\in\\{0.5,1,1.5,\ldots,5.0\\}.$ We sum these ratings by
genre and divide by the number of movies that user $i$ watched from that
genre. This results in an average rating $\mu_{i,j}\in[0,5]$ per genre
$j\in[k]$. Finally, we divide $\mu_{i,j}$ by 5 so that $\mu_{i,j}\in[0,1]$. In
the end,

$\mu_{i,j}=\frac{\sum_{m\in\pazocal{M}_{i}}r_{i,m}\cdot\mathbbm{1}\left\\{j\in
m_{K}\right\\}}{\sum_{m\in\pazocal{M}_{i}}\mathbbm{1}\left\\{j\in
m_{K}\right\\}}\cdot\frac{1}{5}.$

Using the $\bm{\mu}_{i}$s as the mean reward vectors, we use linear programs
(LPs) to solve for the optimal policy under no constraints and under both our
polarization cap and polarization tax frameworks.

###  6.2 Effect of the polarization cap and tax on content recommendations

We begin by investigating the effects that our constraints from Formulation 1
(Section 4.1) have on the optimal content distribution.

These experiments provide a parallel to Lemma 4.1, which shows that in a
polarized population, users share the burden of diversification. To model a
polarized society, we restrict our attention to two dissimilar genres:
thriller and romance. In this restricted space, $\bm{\mu}_{i}\in[0,1]^{2}$. We
call the users who prefer the thriller genre _thriller-lovers_ and those who
prefer the romance genre _romance-lovers_.

(a) Average probability placed on romance for romance- and thriller-lovers.

(b) Average probability placed on thriller for horror- and thriller-lovers.

Figure 1: Polarization cap: Content changes as a function of $\gamma$ for 2
user groups. We compute the optimal policy for 50 values of $\gamma$ equally
spaced between $[0,1]$.

In Figure 1(a), we plot the probability placed on romance by the optimal
policy (which maximizes $\sum_{i=1}^{n}\bm{\mu}_{i}\cdot\bm{p}_{i}$ such that
$\bm{p}_{i}\geq\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\bm{p}_{i^{\prime}}$) as
a function of $\gamma$. For comparison, we run the same experiments for two
similar genres: thriller and horror. In Figure 1(b), we plot the probability
placed on thriller.

In both Figures 1(a) and 1(b), as $\gamma$ increases, the content
recommendations become more homogeneous. However, the rates at which the
recommendations become homogeneous are significantly different. In Figure 1(a)
where the users are polarized, the content recommendations converge slowly. It
is not until $\gamma=0.9$ that the content is completely homogeneous.

Meanwhile, in Figure 1(b) where the groups of users are similar, the
recommendations become homogeneous at a faster rate. In this example, they
converge at approximately $\gamma=0.6$.

(a) Probability placed on romance for romance-lovers.

(b) Probability placed on romance for thriller-lovers.

Figure 2: Polarization tax: Content changes as function of $\gamma$ and $\eta$
for romance- and thriller-lovers. We compute the optimal policy for 6 values
of $\gamma$ equally spaced between $[0,1]$ and 50 values of $\eta$ equally
spaced between $[0,1]$.

Under Formulation 2—where the platform is subject to a penalty (Equation
(7))—we perform the same experiments for romance- versus thriller-lovers.
These experiments are illustrated in Figure 2 where we vary both $\eta$ and
$\gamma$. As before, the content distributions converge as $\gamma$ increases.
However, $\eta$ serves to modulate the impact of $\gamma$ on content
recommendations.

When $\eta$ is small, the platform prefers to pay some tax to show more
personalized content than they would under the hard constraint from
Formulation 1. In fact, in Figure 2(a), we see that even when $\gamma=1$ (so
the platform is penalized for any level of personalization), the platform
prefers to pay some tax and personalize its recommendations, but for
sufficiently large $\eta$ (approximately $\eta\gtrsim 0.2$), the platform
switches to obeying the $\gamma$ constraint and paying no tax. For the other
values of $\gamma$, the content recommendations change more gradually as
$\eta$ grows. However, after a certain point ($\eta\gtrsim 0.4$), only the
value of $\gamma$ leads to differences in the optimal policy.

###  6.3 Effect of the polarization tax on user utility

We next investigate the impact of the polarization penalty (Formulation 2) on
the users’ utility. We analyze the same setting from Section 6.2 where there
is a polarized society consisting of romance- and thriller-lovers.

(a) Romance- and thriller-lovers

(b) Horror- and thriller-lovers

(c) All user types

Figure 3: Multiplicative utility loss as a function of $\gamma$ and $\eta$.

Letting $(\bm{p}_{i}^{\gamma;\eta})_{i\in[n]}$ be the optimal policy under
Equation (7) and $(\bm{p}_{i}^{*})_{i\in[n]}$ policy with no penalty
($\eta=0$), Figure 3(a) plots the ratio of the users’ cumulative utilities
under these two policies:
$\sum\bm{\mu}_{i}\cdot\bm{p}_{i}^{\gamma;\eta}\left/\sum\bm{\mu}_{i}\cdot\bm{p}_{i}^{*}\right..$
Figure 3(b) plots the same quantity under the homogenous society from Section
6.2 with only horror- and thriller-lovers.

In Figures 3(a) and 3(b), utility decreases as $\gamma$ and $\eta$ grow, but
there is a larger utility loss for the polarized group (Figure 3(a)) compared
to the homogeneous group (Figure 3(b)). Interestingly, in the homogenous group
(Figure 3(b)), utility continuously decreases as $\eta$ increases, while in
the polarized group (Figure 3(a)), the utility loss eventually flattens out.
This is because when the population is homogeneous, as $\eta$ increases the
platform only recommends one genre rather than pay the tax, even when $\gamma$
is small. However, when users are polarized (Figure 2), the platform
recommends both genres and pays some tax for most values of $\gamma$. It is
only when $\gamma=1$ that the platform recommends only one genre.

Figure 3(c) plots the same quantity but without restricting the genres
($\bm{\mu}_{i}\in[0,1]^{18}$). Since the users’ preferences are more diverse,
the users’ cumulative utility suffers a larger but still minimal loss. This is
because each user now sees a larger share of content they might not prefer
since there are more groups on the platform. Finally, in Appendix H, we
provide plots illustrating the additive utility loss (rather than
multiplicative).

##  7 Conclusions and discussion

Our work proposes a flexible approach to disincentivizing filter bubbles that
adapts to the interests of the individuals on the network. Under our model, if
some users are shown a particular type of content, then all users see at least
a small amount of that content. We show that our model incentivizes diversity
in a way that is equitable to users on the platform and discuss algorithms for
recommending content under our framework.

There remain many open questions around disincentivizing polarization in
social networks. One might want to distinguish between the content of
protected minority groups and that of hate-focused or troll groups. Our
current formulation does not distinguish between these situations. One could
consider a model where the penalties or cap might scale non-linearly with the
size of the group, allowing for more effective moderation. In addition, there
is more work to be done to understand the precise impacts of our constraints
on the utility of the users and platform. Rewards could represent the profit
of the platform or the utility of its users, and our current analysis does not
address this distinction.

However, the difference could be important when there is a wealth disparity
between groups and differences in utility of the users might not easily map to
differences in the platform’s revenue. A related direction could be to extend
our model to maximize popular and well-studied notions of fairness like Nash
social welfare.

##### Acknowledgements.

We thank Rediet Abebe for inspirational early discussions about this research
direction.

## References

  * Agrawal and Devanur [2014] Shipra Agrawal and Nikhil R Devanur.  Bandits with concave rewards and convex knapsacks.  In _ACM Conference on Economics and Computation (EC)_ , pages 989–1006, 2014.
  * Alon et al. [1996] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  In _Proceedings of the Annual Symposium on Theory of Computing (STOC)_ , pages 20–29, 1996.
  * Amani et al. [2019] Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis.  Linear stochastic bandits under safety constraints.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Aven [1985] Terje Aven.  Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables.  _Journal of applied probability_ , 22(3):723–728, 1985.
  * Badanidiyuru et al. [2013] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins.  Bandits with knapsacks.  In _Symposium on Foundations of Computer Science (FOCS)_ , 2013.
  * Bail et al. [2018] Christopher A Bail, Lisa P Argyle, Taylor W Brown, John P Bumpus, Haohan Chen, MB Fallin Hunzaker, Jaemin Lee, Marcus Mann, Friedolin Merhout, and Alexander Volfovsky.  Exposure to opposing views on social media can increase political polarization.  _Proceedings of the National Academy of Sciences_ , 115(37):9216–9221, 2018.
  * Bozdag and Van Den Hoven [2015] Engin Bozdag and Jeroen Van Den Hoven.  Breaking the filter bubble: democracy and design.  _Ethics and information technology_ , 17:249–265, 2015\.
  * Bubeck et al. [2013] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi.  Bandits with heavy tail.  _IEEE Transactions on Information Theory_ , 59(11):7711–7717, 2013.
  * Castells et al. [2021] Pablo Castells, Neil Hurley, and Saul Vargas.  Novelty and diversity in recommender systems.  In _Recommender systems handbook_ , pages 603–646. Springer, 2021\.
  * Celis et al. [2019] L Elisa Celis, Sayash Kapoor, Farnood Salehi, and Nisheeth Vishnoi.  Controlling polarization in personalization: An algorithmic framework.  In _Proceedings of the conference on fairness, accountability, and transparency (FAT*)_ , pages 160–169, 2019.
  * Claure et al. [2020] Houston Claure, Yifang Chen, Jignesh Modi, Malte Jung, and Stefanos Nikolaidis.  Multi-armed bandits with fairness constraints for distributing resources to human teammates.  In _Proceedings of the 2020 ACM/IEEE International Conference on Human-Robot Interaction_ , pages 299–308, 2020.
  * Dani et al. [2008] Varsha Dani, Thomas P Hayes, and Sham M Kakade.  Stochastic linear optimization under bandit feedback.  2008\.
  * Elahi et al. [2022] Mehdi Elahi, Dietmar Jannach, Lars Skjærven, Erik Knudsen, Helle Sjøvaag, Kristian Tolonen, Øyvind Holmstad, Igor Pipkin, Eivind Throndsen, Agnes Stenbom, et al.  Towards responsible media recommendation.  _AI and Ethics_ , pages 1–12, 2022.
  * Fabbri et al. [2022] Francesco Fabbri, Maria Luisa Croci, Francesco Bonchi, and Carlos Castillo.  Exposure inequality in people recommender systems: The long-term effects.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 16, pages 194–204, 2022.
  * Freelon et al. [2022] Deen Freelon, Michael Bossetta, Chris Wells, Josephine Lukito, Yiping Xia, and Kirsten Adams.  Black trolls matter: Racial and ideological asymmetries in social media disinformation.  _Social Science Computer Review_ , 40(3):560–578, 2022.
  * Haghtalab et al. [2021] Nika Haghtalab, Matthew O Jackson, and Ariel D Procaccia.  Belief polarization in a complex world: A learning theory perspective.  _Proceedings of the National Academy of Sciences_ , 118(19):e2010144118, 2021.
  * Halpern et al. [2023] Daniel Halpern, Ariel D Procaccia, Iyan Rahwan, Itai Shapira, and Manuel Wüthrich.  Optimal engagement-diversity tradeoffs in social media.  2023\.
  * Harper and Konstan [2015] F Maxwell Harper and Joseph A Konstan.  The movielens datasets: History and context.  _ACM Transactions on Interactive Intelligent Systems (TIIS)_ , 5(4):1–19, 2015.
  * Helberger et al. [2018] Natali Helberger, Kari Karppinen, and Lucia D’acunto.  Exposure diversity as a design principle for recommender systems.  _Information, Communication & Society_, 21(2):191–207, 2018.
  * Hossain et al. [2021] Safwan Hossain, Evi Micha, and Nisarg Shah.  Fair algorithms for multi-agent multi-armed bandits.  pages 24005–24017, 2021.
  * Jiang et al. [2019] Ray Jiang, Silvia Chiappa, Tor Lattimore, András György, and Pushmeet Kohli.  Degenerate feedback loops in recommender systems.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 383–390, 2019.
  * Joseph et al. [2016] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth.  Fairness in learning: Classic and contextual bandits.  2016\.
  * Krueger et al. [2020] David Krueger, Tegan Maharaj, and Jan Leike.  Hidden incentives for auto-induced distributional shift.  _arXiv preprint arXiv:2009.09153_ , 2020.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * mcd [https://math.stackexchange.com/users/1059789/mcd] mcd (https://math.stackexchange.com/users/1059789/mcd).  $\mathbb{E}[x\mid x\geq n/2]$ when $x\sim\text{Bin}(n,0.5)$.  Mathematics Stack Exchange.  URL https://math.stackexchange.com/q/4616304.  URL:https://math.stackexchange.com/q/4616304 (version: 2023-01-11).
  * Moradipari et al. [2021] Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis.  Safe linear thompson sampling with side information.  _IEEE Transactions on Signal Processing_ , 69:3755–3767, 2021.
  * Pacchiano et al. [2021] Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, and Heinrich Jiang.  Stochastic bandits with linear constraints.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 2827–2835. PMLR, 2021.
  * Rychwalska and Roszczyńska-Kurasińska [2018] Agnieszka Rychwalska and Magdalena Roszczyńska-Kurasińska.  Polarization on social media: when group dynamics leads to societal divides.  2018\.
  * Slivkins [2019] Aleksandrs Slivkins.  Introduction to multi-armed bandits.  _arXiv preprint arXiv:1904.07272_ , 2019.
  * Stoica and Chaintreau [2019] Ana-Andreea Stoica and Augustin Chaintreau.  Hegemony in social media and the effect of recommendations.  In _Companion Proceedings of The 2019 World Wide Web Conference_ , pages 575–580, 2019.
  * Stoica et al. [2018] Ana-Andreea Stoica, Christopher Riederer, and Augustin Chaintreau.  Algorithmic glass ceiling in social networks: The effects of social recommendations on network diversity.  In _Proceedings of the International World Wide Web Conference (WWW)_ , pages 923–932, 2018.
  * Su et al. [2016] Jessica Su, Aneesh Sharma, and Sharad Goel.  The effect of recommendations on network structure.  In _Proceedings of the International World Wide Web Conference (WWW)_ , 2016.
  * Thompson [1933] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3-4):285–294, 1933.
  * Wu et al. [2016] Yifan Wu, Roshan Shariff, Tor Lattimore, and Csaba Szepesvári.  Conservative bandits.  In _International Conference on Machine Learning (ICML)_ , 2016.

##  Appendix A Proofs about first attempt (Section 3)

See 3.1

###### Proof.

First, we write the expected reward as

$\sum_{i=1}^{n}\bm{p}_{i}\cdot\bm{\mu}_{i}=\sum_{i\in N}p_{i,1}+\sum_{i\not\in
N}p_{i,2}=n-|N|+\sum_{i\in N}p_{i,1}-\sum_{i\not\in N}p_{i,1},$

so we can write our optimization problem as

$\begin{array}[]{ll}\text{maximize}&\sum_{i\in N}p_{i,1}-\sum_{i\not\in
N}p_{i,1},\\\ \text{subject
to}&\left|p_{i,1}-\frac{1}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},0}\right|\leq\Delta.\end{array}$
(15)

Next, we show that there exists an optimal solution such that $p_{i,1}=q_{1}$
for all $i\in N$ and $p_{i,1}=q_{2}$ for all $i\not\in N$, for some
$q_{1},q_{2}\in[0,1].$

######  Claim A.1.

An optimal solution to Equation (15) has $p_{i,1}=q_{1}$ for all $i\in N$ and
$p_{i,1}=q_{2}$ for all $i\not\in N$, for some $q_{1},q_{2}\in[0,1].$

###### Proof of Claim A.1.

First, if $N=\emptyset$, then the optimal solution is to set $p_{i,1}=0$ for
all $i\in[n]$, and if $N=[n]$, then the optimal solution is to set $p_{i,1}=1$
for all $i\in[n]$. In both of these cases, the claim holds.

Next, suppose $N\not=\emptyset$ and $N\not=[n]$. Let $p_{1,0},\dots,p_{n,0}$
be an optimal solution to Equation (15) and let $q_{1}=\frac{1}{|N|}\sum_{i\in
N}p_{i,1}$ and $q_{2}=\frac{1}{n-|N|}\sum_{i\not\in N}p_{i,1}$. This is a
feasible solution to Equation (15) because

$\frac{1}{n}\left(|N|q_{1}+(n-|N|)q_{2}\right)=\frac{1}{n}\sum_{i=1}^{n}p_{i,1},$

so for all $i\in N$, we have that

$-\Delta\leq\min_{j\in
N}p_{j,0}-\frac{1}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},0}\leq
q_{1}-\frac{1}{n}\left(|N|q_{1}+(n-|N|)q_{2}\right)\leq\max_{j\in
N}p_{j,0}-\frac{1}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},0}\leq\Delta.$

Similarly, for all $i\not\in N$,

$-\Delta\leq\min_{j\not\in
N}p_{j,0}-\frac{1}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},0}\leq
q_{2}-\frac{1}{n}\left(|N|q_{1}+(n-|N|)q_{2}\right)\leq\max_{j\not\in
N}p_{j,0}-\frac{1}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},0}\leq\Delta.$

Moreover, this solution has the same objective function value as
$p_{1,0},\dots,p_{n,0}$, so it is an optimal solution. ∎

Using this notation, we simplify the constraints by writing

$q_{1}-\frac{1}{n}\sum_{i=1}^{n}p_{i,1}=q_{1}-\frac{1}{n}\left(|N|q_{1}+(n-|N|)q_{2}\right)=\frac{(n-|N|)(q_{1}-q_{2})}{n}.$

Therefore, the constraint (Equation (15)) for any $i\in N$ becomes

$|q_{1}-q_{2}|\leq\frac{n\Delta}{n-|N|}.$ (16)

Similarly, we may write

$q_{2}-\frac{1}{n}\sum_{i=1}^{n}p_{i,1}=q_{2}-\frac{1}{n}\left(|N|q_{1}+(n-|N|)q_{2}\right)=\frac{|N|(q_{2}-q_{1})}{n}.$

Therefore, the constraint (Equation (15)) for any $i\not\in N$ becomes

$|q_{1}-q_{2}|\leq\frac{n\Delta}{|N|}.$ (17)

Since $|N|\geq\frac{n}{2}$, Equation (17) is tighter than Equation (16).
Therefore, our optimization problem can be written as the LP

maximize $\displaystyle g(q_{1},q_{2})=|N|q_{1}-(n-|N|)q_{2}$ subject to
$\displaystyle q_{2}\geq q_{1}-\frac{n\Delta}{|N|}$ (18) $\displaystyle
q_{2}\leq q_{1}+\frac{n\Delta}{|N|}$ (19) $\displaystyle 0\leq q_{2},q_{1}\leq
1$

The vertices $(q_{1},q_{2})$ of this LP polytope and their objective values
$g(q_{1},q_{2})$ are

Intersection of Equations (18) and (19): Infeasible
$\displaystyle\text{Intersection of Equation~{}\eqref{eq:po_big} and
}q_{2}=0\text{: }$
$\displaystyle\left(q_{1}^{(1)},q_{2}^{(1)}\right)=\left(\frac{n\Delta}{|N|},0\right)$
$\displaystyle g\left(q_{1}^{(1)},q_{2}^{(1)}\right)=n\Delta$
$\displaystyle\text{Intersection of Equation~{}\eqref{eq:po_big} and
}q_{2}=1\text{: }$ Infeasible $\displaystyle\text{Intersection of
Equation~{}\eqref{eq:po_big} and }q_{1}=0\text{: }$ Infeasible
$\displaystyle\text{Intersection of Equation~{}\eqref{eq:po_big} and
}q_{1}=1\text{: }$
$\displaystyle\left(q_{1}^{(2)},q_{2}^{(2)}\right)=\left(1,1-\frac{n\Delta}{|N|}\right)$
$\displaystyle
g\left(q_{1}^{(2)},q_{2}^{(2)}\right)=2|N|-n+n\Delta\left(\frac{n}{|N|}-1\right)$
$\displaystyle\text{Intersection of Equation~{}\eqref{eq:po_small} and
}q_{2}=0\text{: }$ Infeasible $\displaystyle\text{Intersection of
Equation~{}\eqref{eq:po_small} and }q_{2}=1\text{: }$
$\displaystyle\left(q_{1}^{(3)},q_{2}^{(3)}\right)=\left(1-\frac{n\Delta}{|N|},1\right)$
$\displaystyle g\left(q_{1}^{(3)},q_{2}^{(3)}\right)=2|N|-n+n\Delta$
$\displaystyle\text{Intersection of Equation~{}\eqref{eq:po_small} and
}q_{1}=0\text{: }$
$\displaystyle\left(q_{1}^{(4)},q_{2}^{(4)}\right)=\left(0,\frac{n\Delta}{|N|}\right)$
$\displaystyle
g\left(q_{1}^{(4)},q_{2}^{(4)}\right)=-\frac{n\Delta(n-|N|)}{|N|}$
$\displaystyle\text{Intersection of Equation~{}\eqref{eq:po_small} and
}q_{1}=1\text{: }$ Infeasible.

Finally, we have vertices $\left(q_{1}^{(5)},q_{2}^{(5)}\right)=(0,0)$ with
$g\left(q_{1}^{(5)},q_{2}^{(5)}\right)=0$ and
$\left(q_{1}^{(6)},q_{2}^{(6)}\right)=(1,1)$ with
$g\left(q_{1}^{(6)},q_{2}^{(6)}\right)=2|N|-n$. Since $\Delta<\frac{|N|}{n}$,
$(q_{1},q_{2})=(0,1)$ and $(q_{1},q_{2})=(1,0)$ are infeasible. Since
$|N|\geq\frac{n}{2}$,
$\left(q_{1}^{(3)},q_{2}^{(3)}\right)=\left(1-\frac{n\Delta}{|N|},1\right)$
maximizes the objective value, which implies the lemma statement. ∎

##  Appendix B Proofs about our more equitable approach (Section 4)

See 4.1

###### Proof.

Our goal is to find distributions
$\bm{p}_{1},\dots,\bm{p}_{n}\in\pazocal{P}^{1}$ to the optimization problem

$\begin{array}[]{ll}\text{maximize}&\sum_{i=1}^{n}\bm{p}_{i}\cdot\bm{\mu}_{i}=\sum_{i\in
N}p_{i,1}+\sum_{i\not\in N}p_{i,2}\\\ \text{such
that}&p_{i,1}\geq\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},1},\forall
i\in[n]\\\
&p_{i,2}\geq\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},2},\forall
i\in[n]\end{array}$ (20)

We claim that without loss of generality, we may set $p_{i,1}=q_{1}$ for all
$i\in N$ and $p_{i,2}=q_{2}$ for all $i\not\in N$, for some
$q_{1},q_{2}\in[0,1].$

######  Claim B.1.

An optimal solution to Equation (20) has $p_{i,1}=q_{1}$ for all $i\in N$ and
$p_{i,2}=q_{2}$ for all $i\not\in N$, for some $q_{1},q_{2}\in[0,1].$

###### Proof of Claim B.1.

First, if $N=\emptyset$, then the optimal solution is to set $p_{i,2}=1$ for
all $i\in[n]$, and if $N=[n]$, then the optimal solution is to set $p_{i,1}=1$
for all $i\in[n]$. In both of these cases, the claim holds.

Next, suppose $N\subset[n]$ and $N\not=\emptyset$. Let
$\bm{p}_{1},\dots,\bm{p}_{n}\in\pazocal{P}^{1}$ be an optimal solution to
Equation (20) and let $q_{1}=\frac{1}{|N|}\sum_{i\in N}p_{i,1}$ and
$q_{2}=\frac{1}{n-|N|}\sum_{i\not\in N}p_{i,2}$. This is a feasible solution
to the constraints in Equation (20) because

$\displaystyle q_{1}$ $\displaystyle=\frac{1}{|N|}\sum_{i\in
N}p_{i,1}\geq\frac{1}{|N|}\sum_{i\in
N}\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},1}=\frac{\gamma}{n}\sum_{i=1}^{n}p_{i,1}=\frac{\gamma}{n}\left(\sum_{i\in
N}p_{i,1}+\sum_{i\not\in N}\left(1-p_{i,1}\right)\right)$
$\displaystyle=\frac{\gamma}{n}\left(|N|q_{1}+(n-|N|)\left(1-q_{2}\right)\right).$

Similarly,

$\displaystyle q_{2}$ $\displaystyle=\frac{1}{|N|}\sum_{i\in
N}p_{i,2}\geq\frac{1}{|N|}\sum_{i\in
N}\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},2}=\frac{\gamma}{n}\sum_{i=1}^{n}p_{i,2}=\frac{\gamma}{n}\left(\sum_{i\in
N}\left(1-p_{i,1}\right)+\sum_{i\not\in N}p_{i,1}\right)$
$\displaystyle=\frac{\gamma}{n}\left(|N|\left(1-q_{1}\right)+(n-|N|)q_{2}\right).$

Moreover, the objective functions are the same because

$|N|q_{1}+(n-|N|)q_{2}=\sum_{i\in N}p_{i,1}+\sum_{i\not\in N}p_{i,2}.$

Therefore, the claim holds. ∎

Based on Claim B.1, we may write our optimization problem as

maximize $\displaystyle|N|q_{1}+(n-|N|)q_{2}$ such that $\displaystyle
q_{1}\geq\frac{\gamma}{n}\left(|N|q_{1}+(n-|N|)\left(1-q_{2}\right)\right)$
$\displaystyle
1-q_{1}\geq\frac{\gamma}{n}\left(|N|\left(1-q_{1}\right)+(n-|N|)q_{2}\right)$
$\displaystyle
q_{2}\geq\frac{\gamma}{n}\left(|N|\left(1-q_{1}\right)+(n-|N|)q_{2}\right)$
$\displaystyle
1-q_{2}\geq\frac{\gamma}{n}\left(|N|q_{1}+(n-|N|)\left(1-q_{2}\right)\right)$
$\displaystyle q_{1},q_{2}\in[0,1].$

Rearranging terms, our optimization problem is

maximize $\displaystyle g(q_{1},q_{2})=|N|q_{1}+(n-|N|)q_{2}$ such that
$\displaystyle q_{1}\geq\frac{\gamma(n-|N|)}{n-\gamma|N|}(1-q_{2})$ (21)
$\displaystyle q_{1}\leq 1-\frac{\gamma(n-|N|)}{n-\gamma|N|}\cdot q_{2}$ (22)
$\displaystyle q_{1}\geq 1-\frac{n-\gamma(n-|N|)}{n-\gamma|N|}\cdot q_{2}$
(23) $\displaystyle q_{1}\leq\frac{n-\gamma(n-|N|)}{\gamma|N|}(1-q_{2})$ (24)
$\displaystyle q_{1},q_{2}\geq 0\text{ and }q_{1},q_{2}\leq 1.$ (25)

To analyze the corners of this LP polytope, we identify where the eight
hyperplanes in Equations (21)-(25) intersect. Note that Equations (21) and
(22) are parallel, so they don’t intersect. The same is true of Equations (23)
and (24). Moreover, $q_{1}=0$ if and only if $q_{2}=1$ by Equations (21) and
(24), so we ignore the intersections with $q_{1}=0$ and $q_{2}=1$. This leads
to the following corners $(q_{1},q_{2})$ with objective values
$g(q_{1},q_{2})$:

Intersection of (21) and (23):
$\displaystyle\left(q_{1}^{(1)},q_{2}^{(1)}\right)=\left(\frac{\gamma(n-|N|)}{n},\frac{\gamma|N|}{n}\right)$
$\displaystyle
g\left(q_{1}^{(1)},q_{2}^{(1)}\right)=\frac{2\gamma|N|(n-|N|)}{n}$
Intersection of (21) and (24):
$\displaystyle\left(q_{1}^{(2)},q_{2}^{(2)}\right)=\left(0,1\right)$
$\displaystyle g\left(q_{1}^{(2)},q_{2}^{(2)}\right)=n-|N|$
$\displaystyle\text{Intersection of \eqref{eq:h1} and }q_{2}=0\text{: }$
$\displaystyle\left(q_{1}^{(3)},q_{2}^{(3)}\right)=\left(\frac{\gamma(n-|N|)}{n-\gamma|N|},0\right)$
$\displaystyle
g\left(q_{1}^{(3)},q_{2}^{(3)}\right)=\frac{\gamma(n-|N|)|N|}{n-\gamma|N|}$
$\displaystyle\text{Intersection of \eqref{eq:h1} and }q_{1}=1\text{: }$ Not
feasible Intersection of (22) and (23):
$\displaystyle\left(q_{1}^{(4)},q_{2}^{(4)}\right)=(1,0)$ (26) $\displaystyle
g\left(q_{1}^{(4)},q_{2}^{(4)}\right)=|N|$ Intersection of (22) and (24):
$\displaystyle\left(q_{1}^{(5)},q_{2}^{(5)}\right)=\left(1-\gamma\left(1-\frac{|N|}{n}\right),1-\frac{\gamma|N|}{n}\right)$
$\displaystyle
g\left(q_{1}^{(5)},q_{2}^{(5)}\right)=n-\frac{2\gamma|N|(n-|N|)}{n}$
$\displaystyle\text{Intersection of \eqref{eq:h2} and }q_{2}=0\text{: }$
$\displaystyle(q_{1},q_{2})=(1,0)\text{ as in Equation~{}\eqref{eq:2and3}}$
$\displaystyle\text{Intersection of \eqref{eq:h2} and }q_{1}=1\text{: }$
$\displaystyle(q_{1},q_{2})=(1,0)\text{ as in Equation~{}\eqref{eq:2and3}}$
$\displaystyle\text{Intersection of \eqref{eq:h3} and }q_{2}=0\text{: }$
$\displaystyle(q_{1},q_{2})=(1,0)\text{ as in Equation~{}\eqref{eq:2and3}}$
$\displaystyle\text{Intersection of \eqref{eq:h3} and }q_{1}=1\text{: }$
$\displaystyle(q_{1},q_{2})=(1,0)\text{ as in Equation~{}\eqref{eq:2and3}}$
$\displaystyle\text{Intersection of \eqref{eq:h4} and }q_{2}=0\text{: }$ Not
feasible. $\displaystyle\text{Intersection of \eqref{eq:h4} and
}q_{1}=1\text{: }$ Not feasible.

For $\gamma\leq\frac{1}{2}$, the optimum is achieved at
$\left(q_{1}^{(5)},q_{2}^{(5)}\right)=\left(1-\gamma\left(1-\frac{|N|}{n}\right),1-\frac{\gamma|N|}{n}\right)$,
so the lemma holds. ∎

##  Appendix C Proofs about the Formulation 1 regret upper bound when
$\gamma<1$ (Section 5.1.1)

Algorithm 1 Multi-agent UCB (defined by parameter $\delta$)

1:Failure probability $\delta\in(0,1)$

2:Set $N_{i,j}(0)=0,~{}\forall i\in[n],j\in[k]$;
$\bm{\hat{\mu}}_{i}^{(0)}=\bm{0},~{}~{}\forall i\in[n]$

3:for $t\in\\{1,\dots,T\\}$ do

4: if $t\in\\{1,\ldots,k\\}$ then

5: Set $\bm{p}_{i}^{(t)}=\bm{e}_{t}$

6: else

7: Set
$\left(\bm{p}_{i}^{(t)}\right)_{i\in[n]}=\operatorname*{argmax}\limits_{(\bm{p}_{i})_{i\in[n]}\in
S}\sum\limits_{i=1}^{n}\bm{p}_{i}\cdot\bm{\hat{\mu}}_{i}^{(t-1)}$

8: Draw an arm $j_{i}^{(t)}\sim\bm{p}_{i}^{(t)}~{}~{}\forall i\in[n]$

9: Receive reward $r_{i}^{(t)}\sim\mathscr{D}_{i,j_{i}^{(t)}}$

10: For all $i\in[n]$, set
$N_{i,j_{i}^{(t)}}(t)=N_{i,j_{i}^{(t)}}(t-1)+1$$\triangleright$ Increment the
counter for arm $j_{i}^{(t)}$

11: Set $N_{i,j}(t)=N_{i,j}(t-1),~{}~{}\forall i\in[n]$ and $j\neq
j_{i}^{(t)}$ $\triangleright$ Do not increment the other counters

12: Set
$\beta_{i,j}^{(t)}=\sqrt{\frac{1}{N_{i,j}(t)}\log\frac{2Tnk}{\delta}},~{}~{}\forall
i\in[n],j\in[k]$ $\triangleright$ Define confidence intervals

13:
$\hat{\mu}_{i,j}^{(t)}=\frac{1}{N_{i,j}(t)}\sum\limits_{\tau=1}^{t}r_{i}^{(\tau)}\mathbbm{1}\left\\{j_{i}^{(\tau)}=j\right\\}+\beta_{i,j}^{(t)}$,
$~{}~{}\forall i\in[n],j\in[k]$ $\triangleright$ Estimate mean rewards

######  Claim C.1.

With probability $1-\delta$, for all $i\in[n],t\in[T]$ and $j\in[k]$,

$\bm{\hat{\mu}}_{i,j}^{(t)}\geq\bm{\mu}_{i,j}\geq\bm{\hat{\mu}}_{i,j}^{(t)}-2\bm{\beta}_{u,i}^{(t)}$

###### Proof.

Consider a fixed iteration $t$. For $i\in[n]$ and $j\in[k]$ and $\ell\in[t]$,
let $\tau=\inf_{s}\\{N_{i,j}(s)\geq\ell\\}$ and
$\hat{v}^{\ell}_{i,j}=\frac{1}{\ell}\sum\limits_{s=1}^{\tau}r_{i,j}^{(s)}\mathbbm{1}\left\\{j_{i}^{(s)}=j\right\\}$.
Since the $\hat{v}^{\ell}_{i,j}$ are independent in $\ell,i,$ and $j$ applying
Hoeffding’s inequality with parameter $\delta^{\prime}=\delta/(tnk)$, with
probability greater than $1-\delta^{\prime}$,

$|\hat{v}^{\ell}_{i,j}-\mu_{i,j}|\leq\sqrt{\frac{\log(2/\delta^{\prime})}{\ell}}$

Applying the union bound for all $\forall\ell\in[t],\forall i\in[n],\forall
j\in[k]$ we have that:

$\displaystyle\mathbb{P}\left(\exists\ell\in[t],\exists i\in[n],\exists
j\in[k]:|\hat{v}^{\ell}_{i,j}-\mu_{i,j}|\geq\sqrt{\frac{\log(2/\delta^{\prime})}{\ell}}\right)$
$\displaystyle\leq\,$
$\displaystyle\sum_{\ell=1}^{t}\sum_{i=1}^{n}\sum_{j=1}^{k}\mathbb{P}\left(|\hat{v}^{\ell}_{i,j}-\mu_{i,j}|\geq\sqrt{\frac{\log(2/\delta^{\prime})}{N_{i,j}(t)}}\right)$
$\displaystyle\leq\,$ $\displaystyle tnk\delta^{\prime}=\delta$

Thus with probability at least $1-\delta$, $\forall\ell\in[t],\forall
i\in[n],\forall j\in[k]$,

$|\hat{v}_{i,j}^{\ell}-\mu_{i,j}|\leq\sqrt{\frac{\log(2tnk/\delta)}{\ell}}.$

Since $\hat{\mu}_{i,j}^{t}=\hat{v}_{i,j}^{N_{i,j}(t)}+\beta_{i,j}^{(t)}$ and
$N_{i,j}(t)\in[t]~{}\forall i,j$ with probability at least $1-\delta$

$\hat{\mu}_{i,j}^{t}-2\beta_{i,j}^{(t)}\leq\mu_{i,j}\leq\hat{\mu}_{i,j}^{t}.$

∎

See 5.1

###### Proof.

Fix a timestep $t\in[T]$

$\displaystyle\sum_{i\in[n]}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i})$
$\displaystyle=\sum_{i\in[n]}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)}+\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)}-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i})$
$\displaystyle\leq\sum_{i\in[n]}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\bm{p}_{i}^{*}\cdot\bm{\hat{\mu}}_{i}^{(t)}+\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)}-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i})$

By Claim C.1, $\bm{p}\cdot\bm{\mu}_{i}\leq\bm{p}\cdot\bm{\hat{\mu}}_{i}^{(t)}$
$\forall i\in[n]$ and all $\bm{p}\in\mathbb{R}_{\geq 0}^{k}$

$\displaystyle\sum_{i\in[n]}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i})$
$\displaystyle\leq\sum_{i\in[n]}(\bm{p}_{i}^{*}\cdot\bm{\hat{\mu}}_{i}^{(t)}-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i})$
$\displaystyle\leq\sum_{i\in[n]}\bm{p}_{i}^{(t)}\cdot\bm{\beta}_{i}^{(t)}$

Thus

$R_{T}\leq\sum_{t=1}^{T}\sum_{i\in[n]}\bm{p}_{i}^{(t)}\cdot\bm{\beta}_{i}^{(t)}$

Let $\mathscr{F}_{i,t-1}$ denote the canonical filtration
$\sigma((X_{i,s},\bm{p}_{i}^{(s)}):0\leq s<t)$ on the choice of
$\bm{p}_{i}^{(t)}$ and let $j_{i}^{(t)^{\prime}}$ be a random variable
distributed as $\bm{p}_{i}^{(t)}\mid\mathscr{F}_{i,t-1}$ and conditionally
independent from $j_{i,t}^{(t)}$, i.e.$~{}j_{i}^{(t)^{\prime}}\perp
j_{i}^{(t)}\mid\mathscr{F}_{i,t-1}$. Note that by definition the following
equality holds:

$\mathop{\mathbb{E}}_{j_{i}^{(t)}\sim\bm{p}_{i}^{(t)}}[\beta_{i,j_{i}^{(t)}}^{(t)}]=\mathop{\mathbb{E}}_{j_{i}^{(t)^{\prime}}\sim\bm{p}_{i}^{(t)}}[\beta_{i,j_{i}^{(t)^{\prime}}}^{(t)^{\prime}}\mid\mathscr{F}_{i,t-1}].$

Consider the following random variables
$A_{i,t}=\mathop{\mathbb{E}}_{j_{i}^{(t)^{\prime}}\sim\bm{p}_{i}^{(t)}}[\beta_{i,j_{i}^{(t)^{\prime}}}\mid\mathscr{F}_{i,t-1}]-\beta_{i,j_{i}^{(t)}}(t)$.
Note that $M_{i,t}=\sum_{s=1}^{t}A_{i,s}$ is a martingale. Since $|A_{t}|\leq
2\sqrt{2\log(Tnk/\delta)}$, using this as the bound in Azuma-Hoeffding and
taking a union bound over $i\in[n]$ and $t\in T$ implies that with probability
at least $1-\delta$,

$R_{T}=\sum_{t=1}^{T}\sum_{i=1}^{n}\bm{p}_{i}^{(t)}\cdot\bm{\beta}_{i}^{(t)}\leq\sum_{t=1}^{T}\sum_{i=1}^{n}\bm{\beta}_{i,j_{i}^{(t)}}^{(t)}+nT\sqrt{\frac{1}{T}\log\left(\frac{Tnk}{\delta}\right)\log\left(\frac{1}{\delta}\right)}$

$=\sum_{t=1}^{T}\sum_{i=1}^{n}\bm{\beta}_{i,j_{i}^{(t)}}^{(t)}+n\sqrt{T\log\left(\frac{Tnk}{\delta}\right)\log\left(\frac{1}{\delta}\right)}$

Now we bound
$\sum\limits_{i=1}^{n}\sum\limits_{t=1}^{T}\bm{\beta}_{i,j_{i}^{(t)}}^{(t)}$,

$\sum_{t=1}^{T}\sum_{i=1}^{n}\bm{\beta}_{i,j_{i}^{(t)}}^{(t)}=\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{j=1}^{k}\beta_{i,j}^{(t)}\mathbbm{1}\left\\{j_{i}^{(t)}=j\right\\}$

For fixed $i,j$

$\sum_{t=1}^{T}\beta_{i,j}^{(t)}\mathbbm{1}\left\\{j_{i}^{(t)}=j\right\\}=\sqrt{\log(Tnk/\delta)}\sum_{t=1}^{N_{i,j}(T)}1/\sqrt{t}\leq
2\sqrt{N_{i,j}(T)\log(Tnk/\delta)}$

Therefore

$\displaystyle\sum_{i\in[n]}\sum_{t=1}^{T}\bm{\beta}_{i}^{(t)}$
$\displaystyle\leq
2\sum_{i=1}^{n}\sum_{j=1}^{k}\sqrt{N_{i,j}(T)\log(Tnk/\delta)}$
$\displaystyle\leq
2\sum_{i=1}^{n}\sqrt{k\sum_{j=1}^{k}N_{i,j}(T)\log(Tnk/\delta)}$
$\displaystyle=2\sum_{i=1}^{n}\sqrt{kT\log(Tnk/\delta)}$
$\displaystyle=2n\sqrt{kT\log(Tnk/\delta)}$

Where the second line follows from the concavity of $\sqrt{\cdot}$ and the
penultimate line follows from the fact that
$\sum\limits_{j=1}^{k}N_{i,j}(T)=T$.

The result then follows by setting $\delta=\frac{1}{nT}.$ ∎

##  Appendix D Proofs about the Formulation 1 regret upper bound when
$\gamma=1$ (Section 5.1.2)

In this section, the distribution
$\mathscr{D}_{j}=\sum_{i=1}^{n}\mathscr{D}_{i,j}$ is supported on $[0,n]$
instead of $[0,1]$ and we denote the average reward for arm $j\in[k]$ as
$\mu_{j}=\sum_{i=1}^{n}\mu_{i,j}$.

######  Definition D.1 (median-of-means estimator [2]).

Let $\delta\in(0,1)$ and $X_{1},\ldots,X_{T}$ be i.i.d random variables with
mean $\mathop{\mathbb{E}}[X]=\mu$ and variance
$\mathop{\mathbb{E}}|X-\mu|^{2}=\sigma^{2}$. Let
$m=\lfloor{8\log(1/\delta)\wedge T/2}\rfloor$ and $t=\lfloor T/m\rfloor$. Let
$\bar{\mu}^{1},\dots,\bar{\mu}^{m}$ be $m$ empirical mean estimates, each one
calculated on $t$ data points as follows:

$\bar{\mu}^{1}=\frac{1}{t}\sum_{s=1}^{t}X_{s}~{},~{}\bar{\mu}^{2}=\frac{1}{t}\sum_{s=t+1}^{2t}X_{s}~{},\ldots,~{}\bar{\mu}^{m}=\frac{1}{t}\sum_{s=(m-1)t+1}^{mt}X_{s}.$

The _median-of-means estimator_ $\bar{\bm{\mu}}(T,\delta)$ is the median of
these $m$ empirical means.

Algorithm 2 Robust-UCB (defined by parameter $\delta$)

1:Failure probability $\delta\in(0,1)$, median-of-means estimator
$\bm{\bar{\mu}}(t,\delta)$

2:Set $N_{j}(0)=0,$ $\hat{\mu}_{j}^{(0)}=0$ $~{}\forall j\in[k]$

3:for $t\in\\{1,\dots,T\\}$ do

4: if $t\in\\{1,\ldots,k\\}$ then

5: Set $\bm{p}^{(t)}=\bm{e}_{t}$

6: else

7: Set
$\bm{p}^{(t)}=\operatorname*{argmax}\limits_{\bm{p}\in\pazocal{P}^{k-1}}\bm{p}\cdot\bm{\hat{\mu}}^{(t-1)}$

8: Draw an arm $j^{(t)}\sim\bm{p}^{(t)}$

9: Receive reward $r^{(t)}\sim\mathscr{D}_{j^{(t)}}$

10: Set $N_{j^{(t)}}(t)=N_{j^{(t)}}(t-1)+1$$\triangleright$ Increment the
counter for arm $j^{(t)}$

11: Set $N_{j}(t)=N_{j}(t-1),~{}~{}\forall j\neq j^{(t)}$ $\triangleright$ Do
not increment the other counters

12: Set
$\beta_{j}^{(t)}=\sqrt{\frac{24n}{N_{j}(t)}\log\frac{Tk}{\delta}},~{}~{}\forall
j\in[k]$ $\triangleright$ Define confidence intervals

13: $\hat{\mu}_{j}^{(t)}=\bm{\bar{\mu}}_{j}(N_{j}(t),\delta)+\beta_{j}^{(t)}$,
$~{}~{}\forall j\in[k]$ $\triangleright$ Get mean rewards estimates

See 5.2

###### Proof.

For all $t\in[T]$, $j\in[k]$ the median-of-mean estimate at time $t$,
$\hat{\mu}_{j}^{(t)}$ with probability at least $1-\delta$ we have

$|\hat{\mu}_{j}^{(t)}-\mu_{j}|\leq\sqrt{\frac{24n\log(kT/\delta)}{T}}$

By applying Lemma D.2 with $\sigma^{2}_{j}=n/4$ which is justified by ClaimD.3
and then taking a union bound over all arms $j\in[k]$.

This event and Proposition 1 in Bubeck et al. [8] imply the desired regret
upper bounds for the Robust-UCB with median-of-means estimator. The result
then follows by setting $\delta=\frac{1}{nT}.$ ∎

######  Lemma D.2.

Let $\delta\in(0,1)$. Let $X_{j,1},\ldots,X_{j,T}$ be i.i.d random variables
with mean $\mathop{\mathbb{E}}[X_{j}]=\mu_{j}$ and
$\mathop{\mathbb{E}}|X_{j}-\mu_{j}|^{2}=\sigma^{2}_{j}$. Let
$m=\lfloor{8\log(1/\delta)\wedge T/2}\rfloor$ and $t=\lfloor T/m\rfloor$. Let

$\bar{\mu}^{1}_{j}=\frac{1}{t}\sum_{s=1}^{t}X_{j,s}~{},~{}\bar{\mu}^{2}_{j}=\frac{1}{t}\sum_{s=t+1}^{2t}X_{j,s}~{},\ldots,~{}\bar{\mu}^{m}_{j}=\frac{1}{t}\sum_{s=(m-1)t+1}^{kt}X_{j,s},$

be $m$ empirical mean estimates, each one computed on $t$ data points. Let
$\hat{\mu}_{j}$ be the median of these $m$ empirical means. Then with
probability at least $1-\delta$

$|\hat{\mu}_{j}-\mu|\leq\sigma\sqrt{\frac{96\log(1/\delta)}{T}}.$

###### Proof.

By Chebyshev’s inequality $\forall\ell\in[m]$

$\mathbb{P}[|\bar{\mu}^{\ell}_{j}-\mu_{j}|\leq\sigma\sqrt{12/t}]\geq 3/4$

Let $\epsilon>0$ and
$Y_{\ell}=\mathbbm{1}\left\\{|\hat{\mu}^{\ell}_{j}-\mu_{j}|>\epsilon\right\\}$
for $\ell\in[k]$, For $\epsilon=\sigma\sqrt{12/t}$, $Y_{\ell}$ is
stochastically dominated by a Bernoulli distribution with parameter $p=1/4$.
Thus using Hoeffding’s inequality for the tail of a binomial distribution we
get

$\displaystyle\mathbb{P}(|\hat{\mu}_{j}-\mu_{j}|>\epsilon)$
$\displaystyle=\mathbb{P}\left(\sum_{\ell=1}^{m}Y_{\ell}\geq
m/2\right)\leq\mathbb{P}(Bin(m,1/4)\geq
m/2)\leq\exp(-2m(p-1/2)^{2})=\exp(-m/8)$ $\displaystyle=\delta.$

∎

######  Claim D.3.

$\sigma^{2}_{j}=\mathop{\mathbb{E}}[|X_{j}-\mu_{j}|^{2}]\leq n/4~{}~{}\forall
j\in[k]$

###### Proof.

$\displaystyle\mathop{\mathbb{E}}[|X_{j}-\mu_{j}|^{2}]$
$\displaystyle=\mathop{\mathbb{E}}\left[\left|\sum_{i=1}^{n}X_{i,j}-\mu_{i,j}\right|^{2}\right]$
$\displaystyle\leq\sum_{i=1}^{n}\mathop{\mathbb{E}}[|X_{i,j}-\mu_{i,j}|^{2}]$
$\displaystyle\leq\sum_{i=1}^{n}1/4=n/4$

where the second line follows from the independence across users $i$ and
triangle inequality. While the last line follows from Popoviciu’s variance
inequality. ∎

##  Appendix E Proofs about the Formulation 1 regret lower bounds (Section
5.1.3)

See 5.5

###### Proof.

Our proof is based on worst-case instances $\nu_{\bm{b}}$ defined for any
vector $\bm{b}\in\\{0,1\\}^{n}$. For each user $i\in[n]$, their reward
distributions for the two arms are Bernoulli with means
$\bm{\mu}_{i}=\left(\mu_{i,0},\mu_{i,1}\right)$ where

$\bm{\mu}_{i}=\begin{cases}\left(\frac{1}{2}+\epsilon,\frac{1}{2}\right)&\text{if
}b_{i}=0\\\ \left(\frac{1}{2},\frac{1}{2}+\epsilon\right)&\text{if
}b_{i}=1\end{cases}$ (27)

where $\epsilon=\sqrt{\frac{1}{8T}}.$ We will lower bound the expected regret
$\mathop{\mathbb{E}}_{\bm{b}}\left[R_{T}\left(\pi,\nu_{\bm{b}}\right)\right]$
over both the randomness of the draw of the vector
$\bm{b}\sim\text{Unif}\left(\\{0,1\\}^{n}\right)$ and the distribution over
outcomes $\mathbb{P}_{\pi\nu_{\bm{b}}}$. This will imply that for any policy
$\pi$, there exists an instance $\nu_{\bm{b}}$ such that

$R_{T}\left(\pi,\nu_{\bm{b}}\right)\geq\sqrt{\frac{T}{8}}\left(\frac{n}{8e}-\gamma\left(\frac{n}{8e}+\sqrt{\frac{n}{2\pi}}\right)\right).$

Given an instance $\nu_{\bm{b}}$, the following distributions
$\bm{p}_{1},\dots,\bm{p}_{n}$ with

$\bm{p}_{i}=\begin{cases}\left(1-\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n},\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\right)&\text{if
}b_{i}=0\\\
\left(\frac{\gamma(n-\left\lVert\bm{b}\right\rVert_{1})}{n},1-\frac{\gamma(n-\left\lVert\bm{b}\right\rVert_{1})}{n}\right)&\text{if
}b_{i}=1.\end{cases}$

are feasible policies. This is because $n-\left\lVert\bm{b}\right\rVert_{1}$
is the number of 0’s in $\bm{b}$ and $\left\lVert\bm{b}\right\rVert_{1}$ is
the number of 1’s in $\bm{b}$, so for any $i$ such that $b_{i}=0$,

$1-\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\geq\frac{\gamma}{n}\left(\sum_{i:b_{i}=0}\left(1-\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\right)+\sum_{i:b_{i}=1}\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\right)=\gamma-\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}$

and

$\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}=\frac{\gamma}{n}\left(\sum_{i:b_{i}=0}\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}+\sum_{i:b_{i}=1}\left(1-\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\right)\right).$

Similarly, for any $i$ such that $b_{i}=1$,

$\frac{\gamma(n-\left\lVert\bm{b}\right\rVert_{1})}{n}=\frac{\gamma}{n}\left(\sum_{i:b_{i}=0}\left(1-\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\right)+\sum_{i:b_{i}=1}\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\right)$

and

$1-\frac{\gamma(n-\left\lVert\bm{b}\right\rVert_{1})}{n}=1-\gamma+\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\geq\frac{\gamma}{n}\left(\sum_{i:b_{i}=0}\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}+\sum_{i:b_{i}=1}\left(1-\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\right)\right)=\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}.$

After simplifying, this policy has an objective value of

$\displaystyle\sum_{i:b_{i}=0}\left(\frac{1}{2}+\left(1-\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\right)\epsilon\right)+\sum_{i:b_{i}=1}\left(\frac{1}{2}+\left(1-\frac{\gamma(n-\left\lVert\bm{b}\right\rVert_{1})}{n}\right)\epsilon\right)$
$\displaystyle=\,$
$\displaystyle\frac{n}{2}+\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\left(1-\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\right)\epsilon+\left\lVert\bm{b}\right\rVert_{1}\left(1-\frac{\gamma(n-\left\lVert\bm{b}\right\rVert_{1})}{n}\right)\epsilon$
$\displaystyle=\,$ $\displaystyle\frac{n}{2}+\epsilon\left(n-\frac{1}{n}\cdot
2\gamma\left\lVert\bm{b}\right\rVert_{1}\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\right).$

Thus, the optimal policy’s expected cumulative reward is at least

$\frac{nT}{2}+\epsilon\left(nT-\frac{1}{n}\cdot
2T\gamma\left\lVert\bm{b}\right\rVert_{1}\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\right).$
(28)

Meanwhile, for any policy $\pi$, let
$\pi_{i,0}^{(t)}=\pi_{i}\left(0\mid\bm{h}_{t-1}\right)$ denote the probability
that the policy chooses arm $0$ for user $i$ on round $t$ given the history
$\bm{h}_{t-1}$. The value $\pi_{i,0}^{(t)}$ is therefore a random variable
that depends on the history $\bm{h}_{t-1}$. Similarly, let
$\pi_{i,1}^{(t)}=\pi_{i}\left(1\mid\bm{h}_{t-1}\right)$. The expected
cumulative reward of policy $\pi$ is

$\displaystyle\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\left(\left(\frac{1}{2}+\epsilon\right)\pi_{i,0}^{(t)}+\frac{1}{2}\pi_{i,1}^{(t)}\right)+\sum_{i:b_{i}=1}\left(\frac{1}{2}\pi_{i,0}^{(t)}+\left(\frac{1}{2}+\epsilon\right)\pi_{i,1}^{(t)}\right)\right)\right]$
$\displaystyle=\,$
$\displaystyle\frac{nT}{2}+\epsilon\left(\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}\right]+\sum_{i:b_{i}=1}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}\right]\right)\right)$
$\displaystyle=\,$
$\displaystyle\frac{nT}{2}+\epsilon\left(nT-\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}\right]+\sum_{i:b_{i}=1}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}\right]\right)\right).$
(29)

Therefore, the expected regret of $\pi$ is at least Equation (28) minus
Equation (29), which is

$\epsilon\left(\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}\right]+\sum_{i:b_{i}=1}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}\right]\right)-\frac{1}{n}\cdot
2T\gamma\left\lVert\bm{b}\right\rVert_{1}\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\right).$
(30)

We will begin incorporating the constraints by rewriting the first part of
Equation (30) as

$\displaystyle\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}\right]+\sum_{i:b_{i}=1}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}\right]\right)$
$\displaystyle=\,$
$\displaystyle\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right]+\sum_{i:b_{i}=1}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,0}^{(t)}\right]\right)$
(31)
$\displaystyle+\sum_{t=1}^{T}\left(\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,1}^{(t)}\right]+\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,0}^{(t)}\right]\right).$

If $\left\lVert\bm{b}\right\rVert_{1}<\frac{n}{2}$, then
$\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}>\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}$,
so

$\displaystyle\sum_{t=1}^{T}\left(\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,1}^{(t)}\right]+\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,0}^{(t)}\right]\right)$
$\displaystyle\geq\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\sum_{t=1}^{T}\sum_{j=1}^{n}\left(\pi_{j,1}^{(t)}+\pi_{j,0}^{(t)}\right)\right]$
$\displaystyle=\gamma\left\lVert\bm{b}\right\rVert_{1}T.$

Similarly, if $\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}$,

$\displaystyle\sum_{t=1}^{T}\left(\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,1}^{(t)}\right]+\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,0}^{(t)}\right]\right)$
$\displaystyle\geq\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\sum_{t=1}^{T}\sum_{j=1}^{n}\left(\pi_{j,1}^{(t)}+\pi_{j,0}^{(t)}\right)\right]$
$\displaystyle=\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)T.$

Therefore,

$\displaystyle\mathop{\mathbb{E}}_{\bm{b}\sim\\{0,1\\}^{n}}\left[\sum_{t=1}^{T}\left(\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,1}^{(t)}\right]+\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,0}^{(t)}\right]\right)\right]$
(32) $\displaystyle\geq\,$ $\displaystyle\gamma
T\mathop{\mathbb{E}}_{\bm{b}}\left[\left\lVert\bm{b}\right\rVert_{1}\textbf{1}_{\left\\{\left\lVert\bm{b}\right\rVert_{1}<\frac{n}{2}\right\\}}+\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\textbf{1}_{\left\\{\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right\\}}\right]$
$\displaystyle=\,$ $\displaystyle\gamma
T\mathop{\mathbb{E}}_{\bm{b}}\left[\left\lVert\bm{b}\right\rVert_{1}\left(1-\textbf{1}_{\left\\{\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right\\}}\right)+\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\textbf{1}_{\left\\{\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right\\}}\right]$
$\displaystyle=\,$ $\displaystyle\gamma
T\left(\mathop{\mathbb{E}}_{\bm{b}}\left[\left\lVert\bm{b}\right\rVert_{1}\right]+n\mathop{\mathbb{E}}\left[\textbf{1}_{\left\\{\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right\\}}\right]-2\mathop{\mathbb{E}}\left[\left\lVert\bm{b}\right\rVert_{1}\textbf{1}_{\left\\{\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right\\}}\right]\right).$
(33)

When $\bm{b}\sim\text{Unif}\left(\\{0,1\\}^{n}\right)$,
$\left\lVert\bm{b}\right\rVert_{1}\sim\text{Bin}\left(n,\frac{1}{2}\right)$.
Therefore, Equation (33) is equal to

$\gamma
T\left(n-2\mathop{\mathbb{E}}\left[\left\lVert\bm{b}\right\rVert_{1}\,\left|\,\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right.\right]\Pr\left[\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right]\right)=\gamma
T\left(n-\mathop{\mathbb{E}}\left[\left\lVert\bm{b}\right\rVert_{1}\,\left|\,\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right.\right]\right).$

Since
$\left\lVert\bm{b}\right\rVert_{1}\sim\text{Bin}\left(n,\frac{1}{2}\right)$,

$\mathop{\mathbb{E}}\left[\left\lVert\bm{b}\right\rVert_{1}\,\left|\,\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right.\right]=\frac{n}{2^{n}}\left(2^{n-1}+{n-1\choose\frac{n-1}{2}}\right)$

[25] and by Stirling’s approximation,

$\mathop{\mathbb{E}}\left[\left\lVert\bm{b}\right\rVert_{1}\,\left|\,\left\lVert\bm{b}\right\rVert_{1}>\frac{n}{2}\right.\right]<\frac{n}{2}+\sqrt{\frac{n}{2\pi}}.$

We can use these facts to bound Equation (32) as follows:

$\mathop{\mathbb{E}}_{\bm{b}\sim\\{0,1\\}^{n}}\left[\sum_{t=1}^{T}\left(\frac{\gamma\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,1}^{(t)}\right]+\frac{\gamma\left\lVert\bm{b}\right\rVert_{1}}{n}\sum_{j=1}^{n}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{j,0}^{(t)}\right]\right)\right]\geq\gamma
T\left(\frac{n}{2}-\sqrt{\frac{n}{2\pi}}\right).$ (34)

Returning to Equation (31), we will next bound

$\displaystyle\mathop{\mathbb{E}}_{\bm{b}}\left[\sum_{t=1}^{T}\left(\sum_{i:b_{i}=0}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right]+\sum_{i:b_{i}=1}\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,0}^{(t)}\right]\right)\right]$
$\displaystyle=\,$
$\displaystyle\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\bm{b}}\left[\sum_{t=1}^{T}\left(\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right]\textbf{1}_{\\{b_{i}=0\\}}+\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,0}^{(t)}\right]\textbf{1}_{\\{b_{i}=1\\}}\right)\right].$

For each user $i\in[n]$, we will therefore lower bound

$\displaystyle\mathop{\mathbb{E}}_{\bm{b}}\left[\sum_{t=1}^{T}\left(\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right]\textbf{1}_{\\{b_{i}=0\\}}+\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\pi_{i,0}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,0}^{(t)}\right]\textbf{1}_{\\{b_{i}=1\\}}\right)\right]$
$\displaystyle=\,$
$\displaystyle\frac{1}{2}\left(\mathop{\mathbb{E}}_{\bm{b}}\left[\left.\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]\,\right|\,b_{i}=0\right]+\mathop{\mathbb{E}}_{\bm{b}}\left[\left.\mathop{\mathbb{E}}_{\pi\nu_{\bm{b}}}\left[\sum_{t=1}^{T}\left(\pi_{i,0}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,0}^{(t)}\right)\right]\,\right|\,b_{i}=1\right]\right).$
(35)

Let $\bm{b}_{-i}\in\\{0,1\\}^{n-1}$ denote the vector $\bm{b}$ with all
components except the $i^{th}$ component. Moreover, to simplify notation, let
$\mathbb{P}_{i,0}$ denote the distribution over outcomes
$(\bm{A}_{1},\bm{X}_{1},\dots,\bm{A}_{T},\bm{X}_{T})\in(\\{0,1\\}^{n}\times\\{0,1\\}^{n})^{T}$
defined by first drawing
$\bm{b}_{-i}\sim\text{Unif}\left(\\{0,1\\}^{n-1}\right)$ and then running the
policy $\pi$ on the instance $\nu_{(0,\bm{b}_{-i})}$. Similarly, let
$\mathbb{P}_{i,1}$ denote the distribution over outcomes
$(\bm{A}_{1},\bm{X}_{1},\dots,\bm{A}_{T},\bm{X}_{T})\in(\\{0,1\\}^{n}\times\\{0,1\\}^{n})^{T}$
defined by first drawing
$\bm{b}_{-i}\sim\text{Unif}\left(\\{0,1\\}^{n-1}\right)$ and then running the
policy $\pi$ on the instance $\nu_{(1,\bm{b}_{-i})}$. We can then rewrite
Equation (35) as

$\displaystyle\frac{1}{2}\left(\mathop{\mathbb{E}}_{i,0}\left[\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]+\mathop{\mathbb{E}}_{i,1}\left[\sum_{t=1}^{T}\left(\pi_{i,0}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,0}^{(t)}\right)\right]\right)$
$\displaystyle=\,$
$\displaystyle\frac{1}{2}\left(\mathop{\mathbb{E}}_{i,0}\left[\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]+\mathop{\mathbb{E}}_{i,1}\left[(1-\gamma)T-\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]\right).$
(36)

Based on the constraints, we know that
$\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\geq 0$ and
$\pi_{i,0}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,0}^{(t)}\geq 0$ with
probability 1. Therefore, by Markov’s inequality and the Bretagnolle–Huber
inequality,

$\displaystyle\frac{1}{2}\left(\mathop{\mathbb{E}}_{i,0}\left[\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]+\mathop{\mathbb{E}}_{i,1}\left[(1-\gamma)T-\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]\right)$
$\displaystyle\geq\,$
$\displaystyle\frac{T(1-\gamma)}{4}\left(\mathbb{P}_{i,0}\left[\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\geq\frac{T(1-\gamma)}{2}\right]\right.$
$\displaystyle+\left.\mathbb{P}_{i,1}\left[\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)<\frac{T(1-\gamma)}{2}\right]\right)$
$\displaystyle\geq\,$
$\displaystyle\frac{T(1-\gamma)}{8}\exp\left(-D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)\right).$

In the following claim, we bound
$D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right).$

######  Claim E.1.

$D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)\leq 8\epsilon^{2}T.$

###### Proof of Claim E.1.

In this proof, we will use the following notation to distinguish the reward
distributions for each instance $\nu_{\bm{b}}$. For any vector of rewards
$\bm{x}_{t}=\left(x_{t,1},\dots,x_{t,n}\right)\in\\{0,1\\}^{n}$ and any choice
of arms $\bm{a}_{t}=\left(a_{t,1},\dots,a_{t,n}\right)\in\\{0,1\\}^{n}$, we
will use the notation $f^{\bm{b}}_{\bm{a}_{t}}(\bm{x}_{t})$ to denote the
probability that the platform receives rewards $\bm{x}_{t}$ under instance
$\nu_{\bm{b}}$ after choosing arms $\bm{a}_{t}.$ We also use
$f_{i,0}^{(b_{i})}:\\{0,1\\}\to[0,1]$ to denote the PMF of arm $0$ for user
$i$ and $f_{i,1}^{(b_{i})}:\\{0,1\\}\to[0,1]$ to denote the PMF of arm $1$ for
user $i$. In other words, $f_{i,0}^{(0)}$ is the
Bern$\left(\frac{1}{2}+\epsilon\right)$ PMF, $f_{i,1}^{(0)}$ is the
Bern$\left(\frac{1}{2}\right)$ PMF, $f_{i,0}^{(1)}$ is the
Bern$\left(\frac{1}{2}\right)$ PMF, and $f_{i,1}^{(1)}$ is the
Bern$\left(\frac{1}{2}+\epsilon\right)$ PMF. With this notation,

$f^{\bm{b}}_{\bm{a}_{t}}(\bm{x}_{t})=\prod_{i=1}^{n}f^{(b_{i})}_{i,a_{t,i}}\left(x_{t,i}\right).$
(37)

Moving now to KL divergence between $\mathbb{P}_{i,0}$ and $\mathbb{P}_{i,1}$,
let $f_{i,0}:(\\{0,1\\}^{n}\times\\{0,1\\}^{n})^{T}\to[0,1]$ be the
probability mass function of the distribution $\mathbb{P}_{i,0}$, and define
$f_{i,1}$ similarly. By definition,

$D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)=\sum_{\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}}f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)\log\frac{f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}{f_{i,1}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}.$
(38)

We will begin by simplifying the logarithm in Equation (38). Beginning with
the numerator of the logarithm, we have that

$\displaystyle
f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)$
$\displaystyle=\mathbb{P}_{i,0}\left[\left(\bm{A}_{t},\bm{X}_{t}\right)_{t=1}^{T}=\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right]$
$\displaystyle=\frac{1}{2^{n-1}}\sum_{\bm{b}_{-i}\in\\{0,1\\}^{n-1}}\mathbb{P}_{\pi\nu_{\left(0,\bm{b}_{-i}\right)}}\left[\left(\bm{A}_{t},\bm{X}_{t}\right)_{t=1}^{T}=\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right].$

Using the notation defined in Section 2 (Equation (1)), we have that

$\displaystyle
f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)$
$\displaystyle=\frac{1}{{}^{n-1}}\sum_{\bm{b}_{-i}}f_{\pi\nu_{\left(0,\bm{b}_{-i}\right)}}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)$
$\displaystyle=\frac{1}{2^{n-1}}\sum_{\bm{b}_{-i}}\prod_{t=1}^{T}\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f^{\left(0,\bm{b}_{-i}\right)}_{\bm{a}_{t}}(\bm{x}_{t}).$

Applying Equation (37), we have that

$f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)=\frac{1}{2^{n-1}}\sum_{\bm{b}_{-i}}\prod_{t=1}^{T}\left(\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f^{(0)}_{i,a_{t,i}}\left(x_{t,i}\right)\prod_{j\not=i}f^{(b_{j})}_{j,a_{t,j}}(x_{t,j})\right)$

where $b_{j}$ indicates the $j^{th}$ component of the vector $\bm{b}_{-i}.$
Rearranging the product within the summation, we have that
$f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)$ is equal to

$\frac{1}{2^{n-1}}\sum_{\bm{b}_{-i}}\left(\prod_{t=1}^{T}\left(\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f^{(0)}_{i,a_{t,i}}\left(x_{t,i}\right)\right)\prod_{t=1}^{T}\left(\prod_{j\not=i}f^{(b_{j})}_{j,a_{t,j}}(x_{t,j})\right)\right).$

Since
$\prod_{t=1}^{T}\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f^{(0)}_{i,a_{t,i}}\left(x_{t,i}\right)$
does not depend on $\bm{b}_{-i}$, we rearrange the summation over
$\bm{b}_{-i}$ as

$f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)=\frac{1}{2^{n-1}}\prod_{t=1}^{T}\left(\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f^{(0)}_{i,a_{t,i}}\left(x_{t,i}\right)\right)\sum_{\bm{b}_{-i}}\prod_{t=1}^{T}\prod_{j\not=i}f^{(b_{j})}_{j,a_{t,j}}(x_{t,j}).$
(39)

Similarly,

$f_{i,1}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)=\frac{1}{2^{n-1}}\prod_{t=1}^{T}\left(\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f^{(1)}_{i,a_{t,i}}\left(x_{t,i}\right)\right)\sum_{\bm{b}_{-i}}\prod_{t=1}^{T}\prod_{j\not=i}f^{(b_{j})}_{j,a_{t,j}}(x_{t,j}).$
(40)

We now return to the logarithm in Equation (38). Based on Equations (39) and
(40), much of the numerator and denominator cancel out, leaving us with

$\log\frac{f_{i,0}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}{f_{i,1}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}=\log\prod_{t=1}^{T}\frac{f^{(0)}_{i,a_{t,i}}\left(x_{t,i}\right)}{f^{(1)}_{i,a_{t,i}}\left(x_{t,i}\right)}=\sum_{t=1}^{T}\log\frac{f^{(0)}_{i,a_{t,i}}\left(x_{t,i}\right)}{f^{(1)}_{i,a_{t,i}}\left(x_{t,i}\right)}.$

We can therefore can write the KL divergence as

$D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)=\sum_{t=1}^{T}\mathop{\mathbb{E}}_{i,0}\left[\log\frac{f^{(0)}_{i,A_{t,i}}\left(X_{t,i}\right)}{f^{(1)}_{i,A_{t,i}}\left(X_{t,i}\right)}\right].$

Moreover, by the law of total expectation,
$D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)$ is equal to

$\sum_{t=1}^{T}\left(\mathop{\mathbb{E}}_{i,0}\left[\left.\log\frac{f^{(0)}_{i,0}\left(X_{t,i}\right)}{f^{(1)}_{i,0}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=0\right]\mathbb{P}\left[A_{t,i}=0\right]+\mathop{\mathbb{E}}_{i,0}\left[\left.\log\frac{f^{(0)}_{i,1}\left(X_{t,i}\right)}{f^{(1)}_{i,1}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=1\right]\mathbb{P}\left[A_{t,i}=1\right]\right).$
(41)

Inspecting each conditional expectation in this sum, we have that

$\displaystyle\mathop{\mathbb{E}}_{i,0}\left[\left.\log\frac{f^{(0)}_{i,0}\left(X_{t,i}\right)}{f^{(1)}_{i,0}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=0\right]$
$\displaystyle=\,$ $\displaystyle\mathbb{P}_{i,0}\left[X_{t,i}=0\mid
A_{t,i}=0\right]\cdot\log\frac{f^{(0)}_{i,0}\left(0\right)}{f^{(1)}_{i,0}\left(0\right)}+\mathbb{P}_{i,0}\left[X_{t,i}=1\mid
A_{t,i}=0\right]\cdot\log\frac{f^{(0)}_{i,0}\left(1\right)}{f^{(1)}_{i,0}\left(1\right)}.$

By Equation (27), for any instance $\nu_{\bm{b}}$ such that $b_{i}=0$, the
probability that $X_{t,i}=0$ given that $A_{t,i}=0$ is
$\frac{1}{2}-\epsilon=f^{(0)}_{i,0}\left(0\right)$. Similarly, the probability
that $X_{t,i}=1$ given that $A_{t,i}=0$ is
$\frac{1}{2}+\epsilon=f^{(0)}_{i,0}\left(1\right)$. Therefore,

$\mathop{\mathbb{E}}_{i,0}\left[\left.\log\frac{f^{(0)}_{i,0}\left(X_{t,i}\right)}{f^{(1)}_{i,0}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=0\right]=f^{(0)}_{i,0}\left(0\right)\log\frac{f^{(0)}_{i,0}\left(0\right)}{f^{(1)}_{i,0}\left(0\right)}+f^{(0)}_{i,0}\left(1\right)\cdot\log\frac{f^{(0)}_{i,0}\left(1\right)}{f^{(1)}_{i,0}\left(1\right)}=D\left(f^{(0)}_{i,0},f^{(1)}_{i,0}\right).$
(42)

Similarly,

$\mathop{\mathbb{E}}_{i,0}\left[\left.\log\frac{f^{(0)}_{i,1}\left(X_{t,i}\right)}{f^{(1)}_{i,1}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=1\right]=D\left(f^{(0)}_{i,1},f^{(1)}_{i,1}\right).$
(43)

Let $N_{i,0}(T)$ be the number of rounds that user $i$ is shown arm $0$ and
let $N_{i,1}(T)$ be the number of rounds that user $i$ is shown arm $0$, so
$N_{i,0}(T)+N_{i,1}(T)=T$. Combining Equations (41), (42), and (43), we have
that

$\displaystyle D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)$
$\displaystyle=\sum_{t=1}^{T}\left(D\left(f^{(0)}_{i,0},f^{(1)}_{i,0}\right)\mathbb{P}_{i,0}\left[A_{t,i}=0\right]+D\left(f^{(0)}_{i,1},f^{(1)}_{i,1}\right)\mathbb{P}_{i,0}\left[A_{t,i}=1\right]\right)$
$\displaystyle=D\left(f^{(0)}_{i,0},f^{(1)}_{i,0}\right)\mathop{\mathbb{E}}_{i,0}\left[N_{i,0}(T)\right]+D\left(f^{(0)}_{i,1},f^{(1)}_{i,1}\right)\mathop{\mathbb{E}}_{i,0}\left[N_{i,1}(T)\right].$

Since $f_{i,0}^{(0)}$ is Bern$\left(\frac{1}{2}+\epsilon\right)$,
$f_{i,1}^{(0)}$ is Bern$\left(\frac{1}{2}\right)$, $f_{i,0}^{(1)}$ is
Bern$\left(\frac{1}{2}\right)$, and $f_{i,1}^{(1)}$ is
Bern$\left(\frac{1}{2}+\epsilon\right)$,

$D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)\leq
8\epsilon^{2}\left(\mathop{\mathbb{E}}_{i,0}\left[N_{i,0}(T)\right]+\mathop{\mathbb{E}}_{i,0}\left[N_{i,1}(T)\right]\right)=8\epsilon^{2}T.$

∎

By Claim E.1, $D\left(\mathbb{P}_{i,0},\mathbb{P}_{i,1}\right)\leq
8\epsilon^{2}T$, so if we set $\epsilon=\sqrt{\frac{1}{8T}}$, we have that

$\frac{1}{2}\left(\mathop{\mathbb{E}}_{i,0}\left[\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]+\mathop{\mathbb{E}}_{i,1}\left[(1-\gamma)T-\sum_{t=1}^{T}\left(\pi_{i,1}^{(t)}-\frac{\gamma}{n}\sum_{j=1}^{n}\pi_{j,1}^{(t)}\right)\right]\right)\geq\frac{T(1-\gamma)}{8e}.$
(44)

Combining Equations (30), (31), and (44), we have that the regret is lower
bounded by

$\sqrt{\frac{1}{8T}}\left(\frac{nT(1-\gamma)}{8e}+\gamma
T\left(\frac{n}{2}-\sqrt{\frac{n}{2\pi}}\right)-\frac{2T\gamma}{n}\mathop{\mathbb{E}}_{\bm{b}\sim\\{0,1\\}^{n}}\left[\left\lVert\bm{b}\right\rVert_{1}\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\right]\right).$

Since
$\mathop{\mathbb{E}}_{\bm{b}\sim\\{0,1\\}^{n}}\left[\left\lVert\bm{b}\right\rVert_{1}\left(n-\left\lVert\bm{b}\right\rVert_{1}\right)\right]=\frac{n}{4}(n-1)$,
we have that the expected regret is lower bounded by

$\sqrt{\frac{T}{8}}\left(\frac{n(1-\gamma)}{8e}+\gamma\left(\frac{n}{2}-\sqrt{\frac{n}{2\pi}}\right)-\frac{\gamma(n-1)}{2}\right)\geq\sqrt{\frac{T}{8}}\left(\frac{n}{8e}-\gamma\left(\frac{n}{8e}+\sqrt{\frac{n}{2\pi}}\right)\right).$

∎

See 5.6

###### Proof.

We begin by defining the worst-case instance $\nu$ where for each user
$i\in[n]$, their reward distributions for the $k$ arms are Bernoulli with
means

$\bm{\mu}_{1}=\cdots=\bm{\mu}_{n}=\left(\frac{1}{2}+\epsilon,\frac{1}{2},\frac{1}{2},\dots,\frac{1}{2}\right)$

where $\epsilon=\sqrt{\frac{k-1}{8nT}}$. We will use the notation $N_{i,j}(T)$
to denote the number of rounds that user $i$ is shown arm $j$ and
$N_{j}(T)=\sum_{i=1}^{n}N_{i,j}(T)$ to denote the total number of rounds that
all users are shown arm $j$. This means that $\sum_{j=1}^{k}N_{j}(T)=nT.$
Under instance $\nu$, the optimal policy obtains a reward of
$nT\left(\frac{1}{2}+\epsilon\right)$. Meanwhile, an arbitrary policy $\pi$
will obtain a reward of

$\left(\frac{1}{2}+\epsilon\right)\mathop{\mathbb{E}}_{\pi\nu}\left[N_{1}(T)\right]+\frac{1}{2}\sum_{j=2}^{n}\mathop{\mathbb{E}}_{\pi\nu}\left[N_{j}(T)\right]=\frac{nT}{2}+\epsilon\mathop{\mathbb{E}}_{\pi\nu}\left[N_{1}(T)\right].$

Therefore, the regret of policy $\pi$ on instance $\nu$ is

$R_{T}(\pi,\nu)=\epsilon\left(nT-\mathop{\mathbb{E}}_{\pi\nu}\left[N_{1}(T)\right]\right).$

Fix a policy $\pi$ and let
$j^{*}=\textnormal{argmin}_{j>2}\mathop{\mathbb{E}}_{\pi\nu}[N_{j}(T)].$ Since
$\sum_{j=2}^{k}N_{j}(T)\leq nT,$ we have that
$\mathop{\mathbb{E}}_{\pi\nu}\left[N_{j^{*}}(T)\right]\leq\frac{nT}{k-1}$. We
now use $j^{*}$ to construct a second worst-case instance $\nu^{\prime}$ where
for each user $i\in[n]$,

$\mu_{i,j}=\begin{cases}\frac{1}{2}+\epsilon&\text{if }j=1\\\
\frac{1}{2}+2\epsilon&\text{if }j=j^{*}\\\
\frac{1}{2}&\text{else.}\end{cases}$

Under instance $\nu^{\prime}$, the optimal policy obtains a reward of
$nT\left(\frac{1}{2}+2\epsilon\right)$. Meanwhile, policy $\pi$ will obtain a
reward of

$\left(\frac{1}{2}+\epsilon\right)\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{1}(T)\right]+\left(\frac{1}{2}+2\epsilon\right)\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{j^{*}}(T)\right]+\frac{1}{2}\sum_{j\not\in\\{1,j^{*}\\}}\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{j}(T)\right]=\frac{nT}{2}+\epsilon\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{1}(T)\right]+2\epsilon\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{j^{*}}(T)\right].$

Therefore,

$\displaystyle R_{T}(\pi,\nu^{\prime})$
$\displaystyle=\epsilon\left(2nT-\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{1}(T)\right]-2\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{j^{*}}(T)\right]\right)$
$\displaystyle=\epsilon\left(2\sum_{j=1}^{k}\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{j}(T)\right]-\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{1}(T)\right]-2\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{j^{*}}(T)\right]\right)$
$\displaystyle\geq\epsilon\mathop{\mathbb{E}}_{\pi\nu^{\prime}}\left[N_{1}(T)\right].$

By Markov’s inequality,

$R_{T}(\pi,\nu)+R_{T}(\pi,\nu^{\prime})\geq\frac{\epsilon
nT}{2}\left(\mathbb{P}_{\pi\nu}\left[N_{1}(T)\leq\frac{nT}{2}\right]+\mathbb{P}_{\pi\nu^{\prime}}\left[N_{1}(T)>\frac{nT}{2}\right]\right),$

so by the Bretagnolle–Huber inequality,

$R_{T}(\pi,\nu)+R_{T}(\pi,\nu)\geq\frac{\epsilon
nT}{4}\exp\left(-D\left(\mathbb{P}_{\pi\nu},\mathbb{P}_{\pi\nu^{\prime}}\right)\right).$
(45)

######  Claim E.2.

For $\epsilon<\frac{1}{5}$,
$D\left(\mathbb{P}_{\pi\nu},\mathbb{P}_{\pi\nu^{\prime}}\right)\leq\frac{4\epsilon^{2}nT}{k-1}.$

###### Proof of Claim E.2.

In this proof, we will use the following notation to distinguish the reward
distributions for the instances $\nu$ and $\nu^{\prime}$. For any vector of
rewards $\bm{x}_{t}=\left(x_{t,1},\dots,x_{t,n}\right)\in\\{0,1\\}^{n}$ and
any choice of arms $\bm{a}_{t}=\left(a_{t,1},\dots,a_{t,n}\right)\in[k]^{n}$,
we use the notation $f_{\bm{a}_{t}}(\bm{x}_{t})$ (respectively,
$f^{\prime}_{\bm{a}_{t}}(\bm{x}_{t})$) to denote the probability that the
platform receives rewards $\bm{x}_{t}$ after choosing arms $\bm{a}_{t}$ under
the instance $\nu$ (respectively, $\nu^{\prime}$). We also use
$f_{i,j}:\\{0,1\\}\to[0,1]$ (respectively,
$f^{\prime}_{i,j}:\\{0,1\\}\to[0,1]$) to denote the PMF of arm $j$ for user
$i$. With this notation,

$f_{\bm{a}_{t}}(\bm{x}_{t})=\prod_{i=1}^{n}f_{i,a_{t,i}}\left(x_{t,i}\right)$
(46)

and

$f^{\prime}_{\bm{a}_{t}}(\bm{x}_{t})=\prod_{i=1}^{n}f^{\prime}_{i,a_{t,i}}\left(x_{t,i}\right).$
(47)

By definition,

$D\left(\mathbb{P}_{\pi\nu},\mathbb{P}_{\pi\nu^{\prime}}\right)=\sum_{\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}}f_{\pi\nu}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)\log\frac{f_{\pi\nu}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}{f_{\pi\nu^{\prime}}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}.$
(48)

We will begin by simplifying the logarithm in Equation (48). Beginning with
the numerator of the logarithm and using the notation defined in Section 2
(Equation (1)), we have that

$f_{\pi\nu}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)=\mathbb{P}_{\pi\nu}\left[\left(\bm{A}_{t},\bm{X}_{t}\right)_{t=1}^{T}=\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right]=\prod_{t=1}^{T}\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})f_{\bm{a}_{t}}(\bm{x}_{t}).$

By Equation (46), we have that

$f_{\pi\nu}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)=\prod_{t=1}^{T}\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})\prod_{i=1}^{n}f_{i,a_{t,i}}\left(x_{t,i}\right).$
(49)

Similarly,

$f_{\pi\nu^{\prime}}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)=\prod_{t=1}^{T}\pi(\bm{a}_{t}\mid\bm{a}_{1},\bm{x}_{1},\dots,\bm{a}_{t-1},\bm{x}_{t-1})\prod_{i=1}^{n}f^{\prime}_{i,a_{t,i}}\left(x_{t,i}\right).$
(50)

We now return to the logarithm in Equation (48). Based on Equations (49) and
(50), much of the numerator and denominator cancel out, leaving us with

$\log\frac{f_{\pi\nu}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}{f_{\pi\nu^{\prime}}\left(\left(\bm{a}_{t},\bm{x}_{t}\right)_{t=1}^{T}\right)}=\log\prod_{t=1}^{T}\prod_{i=1}^{n}\frac{f_{i,a_{t,i}}\left(x_{t,i}\right)}{f^{\prime}_{i,a_{t,i}}\left(x_{t,i}\right)}=\sum_{t=1}^{T}\sum_{i=1}^{n}\log\frac{f_{i,a_{t,i}}\left(x_{t,i}\right)}{f^{\prime}_{i,a_{t,i}}\left(x_{t,i}\right)}.$

We can therefore can write the KL divergence as

$D\left(\mathbb{P}_{\pi\nu},\mathbb{P}_{\pi\nu^{\prime}}\right)=\sum_{i=1}^{n}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi\nu}\left[\log\frac{f_{i,A_{t,i}}\left(X_{t,i}\right)}{f^{\prime}_{i,A_{t,i}}\left(X_{t,i}\right)}\right].$

Moreover, by the law of total expectation,

$D\left(\mathbb{P}_{\pi\nu},\mathbb{P}_{\pi\nu^{\prime}}\right)=\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{j=1}^{k}\mathop{\mathbb{E}}_{\pi\nu}\left[\left.\log\frac{f_{i,j}\left(X_{t,i}\right)}{f^{\prime}_{i,j}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=j\right]\mathbb{P}_{\pi\nu}\left[A_{t,i}=j\right].$

We know that for all $j\not=j^{*}$, $f_{i,j}=f^{\prime}_{i,j}$, which means
that

$D\left(\mathbb{P}_{\pi\nu},\mathbb{P}_{\pi\nu^{\prime}}\right)=\sum_{i=1}^{n}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi\nu}\left[\left.\log\frac{f_{i,j^{*}}\left(X_{t,i}\right)}{f^{\prime}_{i,j^{*}}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=j^{*}\right]\mathbb{P}_{\pi\nu}\left[A_{t,i}=j^{*}\right].$
(51)

By further conditioning,

$\displaystyle\mathop{\mathbb{E}}_{\pi\nu}\left[\left.\log\frac{f_{i,j^{*}}\left(X_{t,i}\right)}{f^{\prime}_{i,j^{*}}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=j^{*}\right]$
$\displaystyle=\,$ $\displaystyle\mathbb{P}_{\pi\nu}\left[X_{t,i}=0\mid
A_{t,i}=j^{*}\right]\cdot\log\frac{f_{i,j^{*}}\left(0\right)}{f^{\prime}_{i,j^{*}}\left(0\right)}+\mathbb{P}_{\pi\nu}\left[X_{t,i}=1\mid
A_{t,i}=j^{*}\right]\cdot\log\frac{f_{i,j^{*}}\left(1\right)}{f^{\prime}_{i,j^{*}}\left(1\right)}.$

Under instance $\nu$, the probability that $X_{t,i}=0$ given that
$A_{t,i}=j^{*}$ is $f_{i,j^{*}}\left(0\right)$. Similarly, the probability
that $X_{t,i}=1$ given that $A_{t,i}=j^{*}$ is $f_{i,j^{*}}\left(1\right)$.
Therefore,

$\mathop{\mathbb{E}}_{\pi\nu_{\bm{0}}}\left[\left.\log\frac{f_{i,j^{*}}\left(X_{t,i}\right)}{f^{\prime}_{i,j^{*}}\left(X_{t,i}\right)}\,\right|\,A_{t,i}=j^{*}\right]=f_{i,j^{*}}\left(0\right)\log\frac{f_{i,j^{*}}\left(0\right)}{f^{\prime}_{i,j^{*}}\left(0\right)}+f_{i,j^{*}}\left(1\right)\cdot\log\frac{f_{i,j^{*}}\left(1\right)}{f^{\prime}_{i,j^{*}}\left(1\right)}=D\left(f_{i,j^{*}},f^{\prime}_{i,j^{*}}\right).$
(52)

Moreover, since $f_{i,j^{*}}$ is the Bin$\left(\frac{1}{2}+\epsilon\right)$
PMF and $f_{i,j^{*}}^{\prime}$ is the Bin$\left(\frac{1}{2}+2\epsilon\right)$
PMF, we have that $D\left(f_{i,j^{*}},f^{\prime}_{i,j^{*}}\right)\leq
4\epsilon^{2}$ for $\epsilon<\frac{1}{5}.$

Combining Equations (51) and (52), we have that

$\displaystyle D\left(\mathbb{P}_{\pi\nu},\mathbb{P}_{\pi\nu^{\prime}}\right)$
$\displaystyle=\sum_{i=1}^{n}\sum_{t=1}^{T}D\left(f_{i,j^{*}},f^{\prime}_{i,j^{*}}\right)\mathbb{P}_{\pi\nu}\left[A_{t,i}=j^{*}\right]$
$\displaystyle\leq
4\epsilon^{2}\sum_{i=1}^{n}\mathop{\mathbb{E}}_{\pi\nu}\left[N_{i,j^{*}}(T)\right]$
$\displaystyle=4\epsilon^{2}\mathop{\mathbb{E}}_{\pi\nu}\left[N_{j^{*}}(T)\right]$
$\displaystyle\leq\frac{4\epsilon^{2}nT}{k-1}.$

∎

Combining Equation (45) and Claim E.2, and setting
$\epsilon=\sqrt{\frac{k-1}{4nT}}$ (in which case $\epsilon<\frac{1}{5}$ for
$nT>7(k-1)$), we have that
$R_{T}(\pi,\nu_{\bm{0}})+R_{T}(\pi,\nu_{\bm{1}})\geq\frac{1}{8e}\sqrt{nT(k-1)}$,
so
$\max\left\\{R_{T}(\pi,\nu_{\bm{0}}),R_{T}(\pi,\nu_{\bm{1}})\right\\}\geq\frac{1}{16e}\sqrt{nT(k-1)}.$
∎

##  Appendix F Proofs about the Formulation 2 regret bounds

In this section, we will use the following notation. For any distributions
$\bm{p}_{1},\dots,\bm{p}_{n}\in\pazocal{P}^{k-1}$, denote the penalty
attributed to user $i$ as

$P_{i}((\bm{p}_{i})_{i\in[n]};\gamma,\eta)=\eta\sum_{j=1}^{k}\max\left\\{0,\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},j}-p_{i,j}\right\\}.$

The total penalty across all $n$ users is

$P((\bm{p}_{i})_{i\in[n]};\gamma,\eta)=\sum\limits_{i=1}^{n}P_{i}((\bm{p}_{i})_{i\in[n]};\gamma,\eta).$

Next, let $\bm{p}_{1}^{*},\dots,\bm{p}_{n}^{*}\in\pazocal{P}^{k-1}$ be
distributions that maximize the expected reward minus the penalties. Then the
expected regret of a policy $\pi$ under this formulation is

$T\sum_{i=1}^{n}\left(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-P_{i}((\bm{p}_{i}^{*})_{i\in[n]};\gamma,\eta)\right)-\mathop{\mathbb{E}}\left[\sum_{i=1}^{n}\sum_{t=1}^{T}\left(X_{i,t}-P_{i}((\bm{\pi}_{i}(\bm{h}_{t-1}))_{i\in[n]};\gamma,\eta)\right)\right].$

Algorithm 3 Penalty-UCB (defined by parameter $\delta$)

1:Failure probability $\delta>0$

2:Set $N_{i,j}(0)=0,~{}\forall i\in[n],j\in[k]$;
$\bm{\hat{\mu}}_{i}^{(0)}=\bm{0},~{}~{}\forall i\in[n]$

3:for $t\in\\{1,\dots,T\\}$ do

4: if $t\in\\{1,\ldots,k\\}$ then

5: Set $\bm{p}_{i}^{(t)}=\bm{e}_{t}$

6: else

7: Set
$\left(\bm{p}_{i}^{(t)}\right)_{i\in[n]}=\operatorname*{argmax}\left\\{\sum\limits_{i=1}^{n}\bm{p}_{i}\cdot\bm{\hat{\mu}}_{i}^{(t-1)}-\eta\sum_{j=1}^{k}\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},j}-p_{i,j},0\right\\}\right\\}$

8: Draw $j_{i}^{(t)}\sim\bm{p}_{i}^{(t)}~{}~{}\forall i\in[n]$

9: Receive reward $r_{i}^{(t)}\sim X_{i,j_{i}^{(t)}}$

10: $N_{i,j_{i}^{t}}(t)=N_{i,j_{i}^{t}}(t-1)+1,~{}~{}\forall i\in[n]$

11: $N_{i,j}(t)=N_{i,j}(t-1),~{}~{}\forall i\in[n]$ and $j\neq j_{i}^{t}$

12:
$\beta_{i,j}^{(t)}=\sqrt{\frac{\log(2Tnk/\delta)}{N_{i,j}(t)}},~{}~{}\forall
i\in[n],j\in[k]$

13:
$\bm{\hat{\mu}}_{i,j}^{t}=\frac{1}{N_{i,j}(t)}\sum\limits_{\tau=1}^{t}r_{i}^{(\tau)}\mathbbm{1}\left\\{j_{i}^{(\tau)}=j\right\\}+\beta_{i,j}^{(t)}$,
$~{}~{}\forall i\in[n],j\in[k]$

See 5.7

###### Proof.

Fix a timestep $t\in[T]$

$\sum\limits_{i=1}^{n}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\bm{p}^{(t)}_{i}\cdot\bm{\mu}_{i})-(P_{i}((\bm{p}_{i}^{*})_{i\in[n]};\gamma,\eta)-P_{i}((\bm{p}_{i}^{(t)})_{i\in[n]};\gamma,\eta))\\\
=\sum_{i=1}^{n}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-P_{i}((\bm{p}_{i}^{*})_{i\in[n]};\gamma,\eta))-(\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)}-P_{i}((\bm{p}_{i}^{(t)})_{i\in[n]};\gamma,\eta))-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i}+\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)}\\\
\leq\sum_{i=1}^{n}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-P_{i}((\bm{p}_{i}^{*})_{i\in[n]};\gamma,\eta))-(\bm{p}_{i}^{*}\cdot\bm{\hat{\mu}}_{i}^{(t)}-P_{i}((\bm{p}_{i}^{*})_{i\in[n]};\gamma,\eta))-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i}+\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)}\\\
=\sum_{i=1}^{n}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\bm{p}_{i}^{*}\cdot\bm{\hat{\mu}}_{i}^{(t)}-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i}+\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)})\\\
$

By Claim C.1, $\bm{p}\cdot\bm{\mu}_{i}\leq\bm{p}\cdot\bm{\hat{\mu}}_{i}^{(t)}$
$\forall i\in[n]$ and all $\bm{p}\in\mathbb{R}_{\geq 0}^{k}$

$\displaystyle\sum\limits_{i=1}^{n}(\bm{p}_{i}^{*}\cdot\bm{\mu}_{i}-\bm{p}^{(t)}_{i}\cdot\bm{\mu}_{i})-(P_{i}((\bm{p}_{i}^{*})_{i\in[n]};\gamma,\eta)-P_{i}((\bm{p}_{i}^{(t)})_{i\in[n]};\gamma,\eta))$
$\displaystyle\leq\sum_{i=1}^{n}(\bm{p}_{i}^{(t)}\cdot\bm{\hat{\mu}}_{i}^{(t)}-\bm{p}_{i}^{(t)}\cdot\bm{\mu}_{i})$
$\displaystyle\leq\sum_{i=1}^{n}\bm{p}_{i}^{(t)}\cdot\bm{\beta}_{i}^{(t)}$

Thus

$R_{T}\leq\sum_{t=1}^{T}\sum_{i\in[n]}\bm{p}_{i}^{(t)}\cdot\bm{\beta}_{i}^{(t)}$

Let $\mathscr{F}_{i,t-1}$ be the sigma algebra defined up to the choice of
$\bm{p}_{i}^{(t)}$ and $j_{i}^{(t)^{\prime}}$ be a random variable distributed
as $\bm{p}_{i}^{(t)}\mid\mathscr{F}_{i,t-1}$ and conditionally independent
from $j_{i,t}^{(t)}$, i.e.$~{}j_{i}^{(t)^{\prime}}\perp
j_{i}^{(t)}\mid\mathscr{F}_{i,t-1}$. Note that by definition the following
equality holds:

$\mathop{\mathbb{E}}_{j_{i}^{(t)}\sim\bm{p}_{i}^{(t)}}[\beta_{i,j_{i}^{(t)}}]=\mathop{\mathbb{E}}_{j_{i}^{(t)^{\prime}}\sim\bm{p}_{i}^{(t)}}[\beta_{i,j_{i}^{(t)^{\prime}}}\mid\mathscr{F}_{i,t-1}].$

Consider the following random variables
$A_{i,t}=\mathop{\mathbb{E}}_{j_{i}^{(t)^{\prime}}\sim\bm{p}_{i}^{(t)}}[\beta_{i,j_{i}^{(t)^{\prime}}}\mid\mathscr{F}_{i,t-1}]-\beta_{i,j_{i}^{(t)}}(t)$.
Note that $M_{i,t}=\sum_{s=1}^{t}A_{i,s}$ is a martingale. Since $|A_{t}|\leq
2\sqrt{2\log(nkT/\delta)}$, a simple application of Azuma-Hoeffding implies
that with probability at least $1-\delta$,

$R_{T}=\sum_{t=1}^{T}\sum_{i\in[n]}\bm{p}_{i}^{(t)}\cdot\bm{\beta}_{i}^{(t)}\leq\sum_{t=1}^{T}\sum_{i\in[n]}\bm{\beta}_{i,j_{i}^{(t)}}^{(t)}+n\sqrt{T\log\left(\frac{nkT}{\delta}\right)\log\left(\frac{1}{\delta}\right)}$

Now let us bound
$\sum\limits_{i\in[n]}\sum\limits_{t=i}^{T}\bm{\beta}_{i}^{(t)}$,

$\sum_{i\in[n]}\sum_{t=i}^{T}\bm{\beta}_{i}^{(t)}=\sum_{i\in[n]}\sum_{j\in[k]}\sum_{t=i}^{T}\beta_{i,j}^{(t)}\mathbbm{1}\left\\{j_{i}^{(t)}=j\right\\}$

For fixed $i,j$

$\sum_{t=i}^{T}\beta_{i,j}^{(t)}\mathbbm{1}\left\\{j_{i}^{(t)}=j\right\\}=\sqrt{\log(Tnk/\delta)}\sum_{t=1}^{N_{i,j}(T)}1/\sqrt{t}\leq
2\sqrt{N_{i,j}(T)\log(Tnk/\delta)}$

Therefore

$\displaystyle\sum_{i\in[n]}\sum_{t=i}^{T}\bm{\beta}_{i}^{(t)}$
$\displaystyle\leq
2\sum_{i\in[n]}\sum_{j\in[k]}\sqrt{N_{i,j}(T)\log(Tnk/\delta)}$
$\displaystyle\leq
2\sum_{i\in[n]}\sqrt{k\sum_{j\in[k]}N_{i,j}(T)\log(Tnk/\delta)}$
$\displaystyle=2\sum_{i\in[n]}\sqrt{kT\log(Tnk/\delta)}$
$\displaystyle=2n\sqrt{kT\log(Tnk/\delta)}$

Where the second line follows from the concavity of $\sqrt{\cdot}$ and the
penultimate line follows from the fact that
$\sum\limits_{j\in[k]}N_{i,j}(T)=T$. ∎

##  Appendix G Proofs about the Formulation 3 regret bounds

See 5.8

###### Proof.

First, for any arm $j\in[k]$, we can exchange the expectation and the maximum
in Equation (8) as follows:

$\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}\right]\geq\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\hat{p}_{i^{\prime},j}\right]-\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\hat{p}_{i,j}\right],0\right\\}.$
(53)

Moreover, we can rewrite the expected empirical distribution as follows:

$\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\hat{p}_{i,j}\right]=\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\textbf{1}_{\\{a_{t,i}=j\\}}\right]=\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right].$

Therefore, by Equation (53), we have that

$\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}\right]\geq\max\left\\{\frac{1}{T}\sum_{t=1}^{T}\left(\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i^{\prime}}(j\mid\bm{h}_{t-1})\right]-\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right]\right),0\right\\}.$

We can therefore bound $\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)$ as
follows:

$\displaystyle\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\left(\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\bm{\mu}_{i}\cdot\bm{\pi^{*}}_{i}(\bm{h}_{t-1})\right]-\eta\sum_{j=1}^{k}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\hat{p}_{i^{\prime},j}-\hat{p}_{i,j},0\right\\}\right]\right)$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{k}\left(\sum_{t=1}^{T}\mu_{i,j}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right]\right.$
(54)
$\displaystyle\left.-\eta\max\left\\{\frac{1}{T}\sum_{t=1}^{T}\left(\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i^{\prime}}(j\mid\bm{h}_{t-1})\right]-\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right]\right),0\right\\}\right).$
(55)

Define the history-independent policy
$\bm{p}=\left(\bm{p}_{1},\dots,\bm{p}_{n}\right)$ such that

$p_{i,j}=\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi_{i}^{*}(j\mid\bm{h}_{t-1})\right].$

This is a distribution because for any user $i\in[n]$,

$\sum_{j=1}^{k}p_{i,j}=\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\sum_{j=1}^{k}\pi_{i}^{*}(j\mid\bm{h}_{t-1})\right]=\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[1\right]=1.$

We rearrange Equation (55) to get that

$\displaystyle\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{k}\left(\mu_{i,j}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right]\right.$
$\displaystyle\left.-\eta\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i^{\prime}}(j\mid\bm{h}_{t-1})\right]-\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi^{*}\nu}\left[\pi^{*}_{i}(j\mid\bm{h}_{t-1})\right]\right),0\right\\}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{k}\left(T\mu_{i,j}p_{i,j}-\eta\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p_{i^{\prime},j}-p_{i,j},0\right\\}\right).$

By definition of $\bm{p}^{*}$, this means that

$\text{reward}_{3}(\pi^{*},\nu;\eta,\gamma)\leq\sum_{i=1}^{n}\sum_{j=1}^{k}\left(T\mu_{i,j}p^{*}_{i,j}-\eta\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}p^{*}_{i^{\prime},j}-p^{*}_{i,j},0\right\\}\right)=\text{reward}_{2}\left(\bm{p}^{*},\nu;\frac{\eta}{T},\gamma\right).$

∎

See 5.9

###### Proof.

First, for any arm $j\in[k]$, we can exchange the expectation and the maximum
in Equation (7) as follows:

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\pi\nu}\left[\max\left\\{\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\pi_{i^{\prime}}(j\mid\bm{h}_{t-1})-\pi_{i}(j\mid\bm{h}_{t-1}),0\right\\}\right]$
$\displaystyle\geq\,$
$\displaystyle\mathop{\mathbb{E}}_{\pi\nu}\left[\max\left\\{\frac{1}{T}\sum_{t=1}^{T}\left(\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\pi_{i^{\prime}}(j\mid\bm{h}_{t-1})-\pi_{i}(j\mid\bm{h}_{t-1})\right),0\right\\}\right]$
$\displaystyle\geq\,$
$\displaystyle\max\left\\{\mathop{\mathbb{E}}_{\pi\nu}\left[\frac{1}{T}\sum_{t=1}^{T}\left(\frac{\gamma}{n}\sum_{i^{\prime}=1}^{n}\pi_{i^{\prime}}(j\mid\bm{h}_{t-1})-\pi_{i}(j\mid\bm{h}_{t-1})\right)\right],0\right\\}.$

Using the fact that
$\mathop{\mathbb{E}}_{\pi\nu}[\pi_{i}(j\mid\bm{h}_{t-1})]=\mathop{\mathbb{E}}_{\pi\nu}[\textbf{1}_{\\{A_{t,i}=j\\}}]$,
we have that