# Can Probabilistic Feedback Drive User Impacts in Online Platforms?111
Authors listed in alphabetical order.

Jessica Dai  University of California, Berkeley  Bailey Flanigan  Carnegie
Mellon University Nika Haghtalab  University of California, Berkeley  Meena
Jagadeesan  University of California, Berkeley  Chara Podimata  MIT &
Archimedes / Athena RC

###### Abstract

A common explanation for negative user impacts of content recommender systems
is misalignment between the platform’s objective and user welfare. In this
work, we show that misalignment in the platform’s objective is not the only
potential cause of unintended impacts on users: even when the platform’s
objective is fully aligned with user welfare, the platform’s learning
algorithm can induce negative downstream impacts on users. The source of these
user impacts is that different pieces of content may generate observable user
reactions (feedback information) at different rates; these feedback rates may
correlate with content properties, such as controversiality or demographic
similarity of the creator, that affect the user experience. Since differences
in feedback rates can impact how often the learning algorithm engages with
different content, the learning algorithm may inadvertently promote content
with certain such properties. Using the multi-armed bandit framework with
probabilistic feedback, we examine the relationship between feedback rates and
a learning algorithm’s engagement with individual arms for different no-regret
algorithms. We prove that no-regret algorithms can exhibit a wide range of
dependencies: if the feedback rate of an arm increases, some no-regret
algorithms engage with the arm more, some no-regret algorithms engage with the
arm less, and other no-regret algorithms engage with the arm approximately the
same number of times. From a platform design perspective, our results
highlight the importance of looking beyond regret when measuring an
algorithm’s performance, and assessing the nature of a learning algorithm’s
engagement with different types of content as well as their resulting
downstream impacts.

##  1 Introduction

Recommendation platforms—which facilitate our consumption of news, music,
social media, and many other forms of digital content—can harm users in
unintended ways, as documented by researchers (Allcott et al., 2020),
journalists (Wells et al., 2021), and regulators (Commission, 2022). One
prevailing explanation for these impacts has been misalignment between the
platform’s objective (e.g., platform profit or user engagement) and user
welfare (Stray et al., 2021). This raises the question: Is aligning the
platform’s objective with user utility sufficient to avoid negative impacts on
users?

In this work, we show that even if the platform’s objective _perfectly
optimizes user utility_ , the process by which the platform continually
_learns_ user preferences can induce unintended impacts on users. In this
learning process, the platform’s learning algorithm relies on observing users’
reactions to content, such as whether a user clicked on a piece of content,
pressed the like button, or retweeted it. Whether users react to content in
observable ways can depend on the specifics of the content—e.g., the content
could be controversial, provoking users to comment, or broadly relatable,
prompting users to share it—in ways which are not captured by user
utilities.222We expect that user feedback rates are not intrinsically captured
by user utility: for example, high-utility content may either induce a high
feedback rate (e.g., if a user retweets controversial content that they agree
with) or induce a low feedback rate (e.g., if the content is educational and
does not provoke a response). Similarly, low-utility content may either incite
response (e.g., if the user disagrees with controversial content) or be
ignored (leading to low feedback rates). As a result, the approach by which
the learning algorithm accounts for these differential rates of information
gain can affect how often content with such properties (e.g.,
controversiality) is recommended. Unfortunately, the resulting impact on
recommendations may inadvertently affect the overall user experience on the
platform, as we describe in Examples 1 and 2.

We study the impact of the platform’s learning algorithm within the _multi-
armed bandits_ framework with _probabilistic feedback_. In this model, each
piece of content corresponds to an arm with a loss, which quantifies a fixed
user’s utility for the corresponding content and can vary over time. The
platform’s objective is regret minimization, and is aligned with maximizing
user utility. To capture the fact that content may generate observable user
data at different rates, each arm $i$ has a fixed feedback rate $f_{i}$
representing the probability of the algorithm observing a sample from that
arm’s loss distribution in a given round. The platform must then determine how
to account for these differential rates of information gain in its learning
algorithm—a choice which can significantly impact what content users see.

Rather than only focusing on regret, we study how often a bandit algorithm
engages with individual arms, and how this depends upon the arm’s feedback
rate $f_{i}$. To quantify engagement with an arm, we introduce two measures:
the arm pull count $\mathtt{APC}_{i}$ (how often an algorithm pulls arm $i$ in
$T$ rounds), and the feedback observation count $\mathtt{FOC}_{i}$ (how often
it sees feedback from arm $i$ in $T$ rounds).333While these measures are
linked through $f_{i}$, they can lead to different user impacts, so we
consider both. To formalize how these measures vary with $f_{i}$ for a given
algorithm, we introduce the notions of feedback monotonicity and balance. At a
high level, an algorithm is positive (negative) feedback monotonic with
respect to $\mathtt{APC}$ ($\mathtt{FOC}$) if, when an arm’s $f_{i}$
increases, the algorithm weakly increases (decreases) $\mathtt{APC}_{i}$
($\mathtt{FOC}_{i}$). An algorithm satisfies balance when such a change in
$i$’s feedback rate is guaranteed to have no effect on $\mathtt{APC}_{i}$
($\mathtt{FOC}_{i}$).

The following examples illustrate how these types of feedback monotonicity
properties can in turn affect downstream user experience on the platform. Note
that these effects transcend what is typically captured in individual
utilities (how much a given user likes a given piece of content), instead
constituting community-level, platform-level, and society-level impacts.

######  Example 1 (Own-group content and $\mathtt{APC}$).

For a given user, $f_{i}$ may be higher for content that appears to be
produced by own-group creators, e.g. creators who are demographically or
ideologically similar to the user (Agan et al., 2023).444The empirical study
of Agan et al. (2023) is explicitly motivated by $\mathtt{APC}$ in the context
of recommendations. $\mathtt{APC}$ captures how often content is shown to
users. If an algorithm induced positive monotonicity in $\mathtt{APC}$, users
may see own-group content disproportionately often, contributing to problems
such as polarization and echo chambers.

######  Example 2 (Incendiary content and $\mathtt{FOC}$.).

Observable feedback often occurs in the form of “retweets,” and high $f_{i}$
can be associated with highly controversial or incendiary content.
$\mathtt{FOC}$ captures observable engagement metrics. If an algorithm induced
positive monotonicity in $\mathtt{FOC}$, creators may be incentivized to
optimize for $\mathtt{FOC}$ by creating more incendiary content; this would
increase the incendiariness of the overall landscape of content available on
the platform. Moreover, since retweets by users about incendiary content are
visible to other users, positive monotonicity in $\mathtt{FOC}$ may also
create a toxic environment on the platform and impact the overall user
experience.

We defer a discussion of further examples to Appendix A.

###  1.1 Our contributions

We initiate the study of how a bandit algorithm’s choice of arms to pull
correlates with the probability of observing feedback for those arms. We
introduce the measures $\mathtt{APC}$ (Def. 2) and $\mathtt{FOC}$ (Def. 3),
which capture two aspects of how a bandit algorithm treats arms that can
result in downstream impacts on users; feedback monotonicity and balance are
the algorithmic properties we aim to analyze. We summarize our results in
Table 1.

Our main technical finding is that no-regret algorithms for the probabilistic
feedback setting can exhibit a range of behavior with respect to
$\mathtt{APC}$ and $\mathtt{FOC}$ (Table 1). We illustrate this by
constructing different families of no-regret algorithms with strikingly
different monotonicity properties for both $\mathtt{APC}$ and $\mathtt{FOC}$,
where these differences are driven by how the algorithms respond to
probabilistic feedback.

  1. 1.

We present three black-box transformations
$(\text{BB}_{\text{Divide}},\text{BB}_{\text{Pull}},\text{BB}_{\text{DA}})$
which convert a generic no-regret bandit algorithm for the deterministic
feedback setting into a bandit algorithm for the probabilistic feedback
setting (Section 3); each of these transformations has different consequences
for $\mathtt{APC}$ and $\mathtt{FOC}$.

  2. 2.

We analyze these black-box transformations applied to concrete algorithms (UCB
and AAE), and achieve both improved regret bounds and stricter monotonicity
guarantees (Sections 4.1 and 4.2).

  3. 3.

We give an algorithm which improves known regret bounds for adversarial
losses, removing the dependence on the minimum feedback probability in
Esposito et al. (2022) (Section 4.3).

Compared to regret, $\mathtt{APC}$ and $\mathtt{FOC}$ are finer-grained
measures for the behavior of a bandit algorithm, so tightly analyzing how
these properties change with $f_{i}$ also requires finer-grained control than
in typical regret analyses. To isolate the impact of modifying feedback
probabilities, we use a coupling argument to explicitly compare the
algorithm’s behavior on two instances that are identical except for one
$f_{i}$.

Algorithm $\mathtt{APC}$ mono. $\mathtt{FOC}$ mono. Regret upper bound
$\text{BB}_{\text{Divide}}(\textsc{Alg},f^{\star})$ Alg. 1 $\approx$ Thm. 3.2
$+$ Thm. 3.2
$R_{\textsc{Alg}}\left(Tf^{\star}/\ln(T)\right)\cdot\ln(T)/f^{\star}$ Thm. 3.1
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ Alg. 2 $\approx/-$ Thm. 3.4
$\approx/+$ Thm. 3.4 $R_{\textsc{Alg}}(T)\cdot 1/\min_{i}f_{i}$ Thm. 3.3
$\text{BB}_{\text{DA}}(\textsc{Alg})$ Alg. 3 $\approx/+$ Thm. 3.6 $\approx/+$
Thm. 3.6 $R_{\textsc{Alg}}(T)\cdot 4\ln(T)/\min_{j}f_{j}$ Thm. 3.5
$\text{BB}_{\text{Pull}}$(AAE) Alg. 4 $-^{\diamond}$ Thm. 4.2
$\approx^{\diamond}$ Thm. 4.2
$O\left(\ln(T)\cdot\sum_{i}1/(\Delta_{i}f_{i})\right)$ Thm. 4.1
$\text{BB}_{\text{DA}}$(AAE) Alg. 6 $+^{\diamond}$ Thm. 4.3 $+$ Thm. 4.3
$O\left(\ln^{2}(T)\cdot\sum_{i}1/(\Delta_{i}\min_{j}f_{j})\right)$ Thm. 3.5
3-Phase EXP3 Alg. 7 $O\left(\sqrt{T\ln(K)\sum_{i\in[K]}1/f_{i}}\right)$ Thm.
4.4

Table 1: Alg is any no-regret bandit algorithm with regret $R_{\textsc{Alg}}$
in the deterministic feedback setting. $f^{\star}$ is a tunable parameter. AAE
is active-arm elimination; UCB is the upper confidence bounds algorithm. In
columns $\mathtt{APC}$ and $\mathtt{FOC}$, $+$, $-$ indicate strict positive,
negative feedback monotonicity. $\approx$ indicates approximate balance,
differing across arms by up to a factor of $O(1/T)$. $\approx/+$ (resp.
$\approx/-$) means that either approximate balance or positive (resp.
negative) monotonicity may be achieved, depending on the underlying algorithm
and problem instance. The superscript $\diamond$ indicates that the stated
property holds only for suboptimal arms.

###  1.2 Related work

Our work relates to research on multi-armed bandits, empirical evidence for
probabilistic feedback, real-world interpretation of $\mathtt{FOC}$ and
$\mathtt{APC}$, and the societal impacts of recommender systems.

Multi-armed bandits. Our technical results build on the vast literature on
multi-armed bandits (see Hazan et al. (2016) for a textbook treatment). Most
relevant to our work is multi-armed bandits with probabilistic feedback graphs
(e.g. Esposito et al. (2022)). This extends the framework of multi-armed
bandits with feedback graphs (Alon et al., 2015), where at each round, when an
arm is pulled, the loss of all of the neighbors of that arm is observed. In
the probabilistic feedback setting, the graphs are drawn from a distribution
at each time step. Recent work has studied regret guarantees for the
probabilistic feedback graph setting for adversarial (e.g. Esposito et al.
(2022); Ghari and Shen (2022)) and stochastic losses (e.g. Li et al. (2020);
Cortes et al. (2020)). We study a special case of this framework where the
graph is always (a union of) self-loops and achieve an improved regret bound
for adversarial losses (Theorem 4.4).

A handful of recent works have examined how the feedback observed by the
bandit learner impacts the arm pull count $\mathtt{APC}$. For example, Haupt
and Narayanan (2022) study how the variance of the noise in the observations
of arm rewards impacts $\mathtt{APC}$ for $\epsilon$-Greedy in a 2-arm
setting; in contrast, we vary the feedback probability that the reward is
observed and study the behavior of more general algorithms and instances.
Moreover, motivated by clickbait, Buening et al. (2023) also study how
feedback probabilities impact $\mathtt{APC}$, focusing on the $K$ arms
(content creators) strategically selecting feedback probabilities to optimize
for $\mathtt{APC}$. However, Buening et al. (2023) focuses on designing
incentive-aware platform algorithms that optimize a utility function (that can
take into account both clickthrough rates and arm rewards); in contrast, we
consider no-regret platform algorithms that optimize only for arm reward, and
analyze their impact in terms of monotonicity properties.

Separately, the measure $\mathtt{APC}$ has been studied in recent work that
aims to achieve fairness across arms, with a focus on ensuring that higher
mean reward arms are pulled more often than lower mean reward arms (Joseph et
al., 2016). Another notion of stronger constraints on arm pulls is
replicability (esfandiari2022replicable), which seeks to ensure that an
algorithm will pull arms in the same order across identical instances with
high probability. Though related, this is distinct from our definition of
$\mathtt{APC}$ and our goals of controlling monotonicity. Their algorithms
employ a similar “block” approach as ours, though they give explicit
algorithms rather than black-box transformations for generic algorithms.

Empirical evidence for probabilistic feedback. The idea that recommendation
platforms may not observe all user “utilities” at all times is well-studied.
While the intuition that expressed preferences may not be a full picture of
their true preferences underpins an entire subfield of behavioral economics,
we note several works here that study the problem applied to recommendation
systems through a more algorithmic lens. In particular, probabilistic feedback
often occurs for reasons that cannot be fully explained by quality of the
content itself, which motivates our idea that $f_{i}$ should be studied
separately from utilities. For example, Schnabel et al. (2019) show that
probabilistic feedback can arise from interface design choices; Joachims et
al. (2005) uses eye-tracking to show that clickthrough (i.e. feedback) rates
depend on factors like ranking position and the set of other content that is
shown, while Joachims et al. (2017) applies this intuition to develop
recommendation algorithms that are sensitive to the impact of ranking position
on feedback rates; Li and Xie (2020) show that advertisements with images
induce more user engagement than advertisements with text only, and that
various attributes of images (e.g. colorfulness, professional versus amateur
photography, human face, image-text fit) can also affect feedback rates; and
Cao et al. (2021) find similar results in the context of fashion social media
marketing, with both media richness and trustworthiness of marketing content
as factors that affect feedback rates.

Real-world interpretations of $\mathtt{FOC}$ and $\mathtt{APC}$. Many (though
of course not all) of the commonly-discussed harms of recommendation systems
and online platforms can be formalized in terms of $\mathtt{FOC}$ and
$\mathtt{APC}$. For example, the setting described in Wells et al. (2021)—harm
to teen girls on Instagram—harm arises due to repeated exposure
($\mathtt{APC}$) to particular types of content; in the setting described in
Roose (2019)—radicalization on Youtube—the harm is due to “rabbit holes” that
arise due to a combination of $\mathtt{APC}$ and $\mathtt{FOC}$. In fact,
though Roose (2019) is a general-audience reported case study, the more
rigorous evaluation of Ribeiro et al. (2020) also examines both $\mathtt{APC}$
and $\mathtt{FOC}$ in the context of evaluating the role of algorithms in
radicalization. Similarly, emotional contagion experiments (e.g. Ferrara and
Yang (2015) on Twitter, Kramer et al. (2014) on Facebook) often find that
exposure to ($\mathtt{APC}$) content with emotional valence (either positive
or negative) also affects the emotional valence of users’ downstream posts.

Of particular note is Agan et al. (2023), which is the most closely-related
empirical work to our knowledge. This recent work is an empirical study
explicitly motivated by the harms of $\mathtt{APC}$ in recommendation systems,
and correlations that may arise due to a learning algorithm’s treatment of
information; this work motivates our Example 1. In particular, they model
$f_{i}$ as related to “own-group” content, e.g. demographic similarity of the
creator, and are concerned about algorithmic bias in the sense of over-
representing content from “own-group” creators. They show that under this
model, standard learning algorithms do in fact induce correlations between
“own-group” content (i.e. $f_{i}$) and how often it is shown (i.e.
$\mathtt{APC}$). This work can be seen as an empirical validation that our
theoretical framework may be concretely applicable.

Societal impacts of recommender systems. This research thread has broadly
investigated misalignment between recommendations and user utility. One
proposed source of misalignment is potential discrepancies between metrics
derived from observed behavior (e.g. engagement) and user utility (e.g.
Ekstrand and Willemsen (2016); Milli et al. (2021); Kleinberg et al. (2022)).
Another source of misalignment that has recently been studied is how
recommendations can shape user preferences over time (Adomavicius et al.,
2013; Carroll et al., 2022; Dean and Morgenstern, 2022). Furthermore,
approaches for bringing human values in recommender system design have been
investigated (Stray et al., 2021, 2022). Several other societal impacts of
recommender systems have been studied including the emergence of filter
bubbles (Flaxman et al., 2016), stereotyping (Guo et al., 2021), the ability
of users to reach different content (Dean et al., 2020), and content creator
incentives induced by the recommendation algorithm (Ben-Porat and Tennenholtz,
2018; Ben-Porat et al., 2020; Jagadeesan et al., 2022; Hron et al., 2022).

##  2 Model & Preliminaries

We model the interaction between the platform/ learner and the user as a
multi-armed bandit (MAB) that happens over $T$ rounds. Each arm corresponds to
a piece of content; “pulling” an arm corresponds to recommending that piece of
content to the user. We say that an arm _“returns feedback”_ if we observe its
loss upon pulling it.

An instance of our problem is specified by
$\mathcal{I}=\\{\mathcal{A},\mathcal{F},\mathcal{L}\\}$, where $\mathcal{A}$,
$\mathcal{F}$, and $\mathcal{L}$ are defined as follows. Let
$\mathcal{A}:=[K]$ denote the set of $K$ arms. Let
$\mathcal{F}:=[f_{1},\ldots,f_{K}]$ be the feedback probabilities for each
arm, i.e., the value $f_{i}\in[0,1]$ denotes the probability with which arm
$i$ returns feedback when pulled. The probabilities $\mathcal{F}$ can be
chosen arbitrarily by an adversary and are unknown to the learner, but remain
fixed throughout the $T$ rounds. In the deterministic feedback setting,
$f_{i}=1$ for all $i$; in the probabilistic feedback setting, $f_{i}$ can be
less than $1$. Let $\mathcal{L}$ denote the process by which the losses
$\ell_{i,t}$ are generated. Losses can be _adversarial_ or _stochastic_. For
adversarial losses, the sequence $\\{\ell_{i,t}\\}_{i\in[K],t\in[T]}$ can be
chosen arbitrarily, but obliviously, i.e. before the start of the algorithm.
For stochastic losses, each arm $i\in[K]$ has a loss distribution with mean
$\bar{\ell}_{i}$ and variance $1$ from which the per-round loss $\ell_{i,t}$
is sampled. For each arm $i$, we define
$\Delta_{i}:=\bar{\ell}_{i}-\min_{j}\bar{\ell}_{j}$ to be the difference
between the mean loss of arm $i$ and the mean loss of the optimal arm
$\min_{j}\bar{\ell}_{j}$.

For an arm $i\in[K]$, the random variable $X_{i,t}$ corresponds to whether
feedback will be observed if arm $i$ is pulled at round $t$, i.e.,
$X_{i,t}\sim\texttt{Bern}(f_{i})$. With some abuse of notation, we let
$\ell_{i_{\tau},\tau}\cdot X_{i_{\tau},\tau}$ represent the observed loss at
time $\tau$, where $\ell_{i_{\tau},\tau}\cdot X_{i_{\tau},\tau}=\perp$ denotes
lack of observation when $X_{i_{\tau},\tau}=0$ and $\ell_{i_{\tau},\tau}\cdot
X_{i_{\tau},\tau}=\ell_{i_{\tau},\tau}$ denotes the observed loss when
$X_{i_{\tau},\tau}=1.$ Let $H_{t}=\\{(i_{\tau},\ell_{i_{\tau},\tau}\cdot
X_{i_{\tau},\tau},X_{i_{\tau},\tau}\\})\\}_{\tau\in[t-1]}$ for some round $t$
denote the _history_ of play until round $t$, and $\mathcal{H}_{t}$ denote the
family of all possible history trajectories until round $t$. An algorithm
$\textsc{Alg}:\bigcup_{t=0}^{T}\mathcal{H}_{t}\to[K]$ produces a (possibly
randomized) mapping from histories of play to arms to be chosen. We sometimes
overload notation and write $\textsc{Alg}(t)$ to denote the mapping from
$H_{t}$ to $i_{t}$.

###  2.1 Measuring the behavior of an algorithm on an instance

We capture the behavior of an algorithm by the following three quantities. The
first is the standard objective function in multi-armed bandits, an
algorithm’s _(pseudo-)regret_ :555Throughout, we omit “pseudo” from the
definition below for succinctness.

######  Definition 1 (Regret).

The (pseudo-)regret of an algorithm Alg playing arm $i_{t}\in[K]$ at round $t$
is defined as:

$R_{\textsc{Alg}}(T)=\mathbb{E}[\sum_{t\in[T]}\ell_{i_{t},t}]-\min_{j\in[K]}\mathbb{E}[\sum_{t\in[T]}\ell_{j,t}].$

We are also interested in how much an algorithm engages with individual arms.
To capture this, we define the quantities $\mathtt{FOC}_{i}$ and
$\mathtt{APC}_{i}$ for arms $i\in[K]$.

######  Definition 2 (Arm Pull Count ($\mathtt{APC}$)).

Given a problem instance $\mathcal{I}$, the arm pull count ($\mathtt{APC}$) of
an arm $i$ over a run of an algorithm Alg is equal to

$\mathtt{APC}_{i}(\mathcal{I};\textsc{Alg})=\mathbb{E}\big{[}\sum_{t\in[T]}\mathds{1}[i_{t}=i]\big{]}.$

######  Definition 3 (Feedback Observation Count ($\mathtt{FOC}$)).

Given a problem instance $\mathcal{I}$, the feedback observation count
($\mathtt{FOC}$) of arm $i$ over a run of an algorithm Alg is equal to

$\mathtt{FOC}_{i}(\mathcal{I};\textsc{Alg})=\mathbb{E}\big{[}\sum_{t\in[T]}\mathds{1}[i_{t}=i]\cdot
X_{i_{t},t}\big{]}.$

In all three definitions, the expectation is taken with respect to randomness
in both the algorithm and the instance (i.e., loss distributions and feedback
observations). When the instance $\mathcal{I}$ and algorithm Alg are clear
from context, we write $\mathtt{FOC}_{i}$ and $\mathtt{APC}_{i}$. A simple
consequence of the definitions is that $\mathtt{FOC}_{i}$ and
$\mathtt{APC}_{i}$ are related by a multiplicative factor of $f_{i}$.

######  Lemma 2.1.

For any arm $i$, instance $\mathcal{I}$, and algorithm Alg, it holds that
$\mathtt{FOC}_{i}(\mathcal{I})=f_{i}\cdot\mathtt{APC}_{i}(\mathcal{I}).$

We prove Lemma 2.1 in Appendix B; the result follows from noting that, at any
time $t$, the realization of $X_{i_{t},t}$ is independent of all history up to
time $t$.

###  2.2 Feedback monotonicity and balance

Using $\mathtt{FOC}$ and $\mathtt{APC}$, we formalize how an algorithm
responds to feedback probabilities through feedback monotonicity and balance.
We let $\widetilde{\mathcal{F}}(i)$ denote a set of feedback probabilities in
which we have modified arm $i$’s feedback rate, holding all else constant:
that is, $\smash[t]{f_{i}\neq\tilde{f}_{i}}$, and $\forall j\neq
i,\smash[t]{f_{j}=\tilde{f}_{j}}$. For an instance
$\mathcal{I}=\\{\mathcal{A},\mathcal{F},\mathcal{L}\\}$, we use
${\widetilde{\mathcal{I}}}$ to notate the instance identical to $\mathcal{I}$
except for $\smash{\tilde{f}_{i}}$, that is
$\smash{\widetilde{\mathcal{I}}=\\{\mathcal{A},\widetilde{\mathcal{F}}(i),\mathcal{L}\\}}$.
In our analysis, we let $i$ be arbitrary, and only modify feedback for one arm
$i\in[K]$ at a time, and analyze how $\mathtt{APC}_{i}$ and $\mathtt{FOC}_{i}$
would change if the feedback probabilities were
$\smash{\widetilde{\mathcal{F}}(i)}$ instead of $\mathcal{F}$. We formally
define monotonicity and balance below.

######  Definition 4 (Feedback monotonicity.).

An algorithm exhibits positive (resp. negative) feedback monotonicity wrt
measure $Q\in\\{\mathtt{APC},\mathtt{FOC}\\}$ if and only if for all
$\mathcal{I}=\\{\mathcal{A},\mathcal{F},\mathcal{L}\\}$, for all
$i\in\mathcal{A}$, and for all pairs $\tilde{f}_{i},f_{i}\in[0,1]$ such that
$\tilde{f}_{i}>f_{i}$, we have that $Q_{i}(\widetilde{\mathcal{I}})\geq
Q_{i}(\mathcal{I})$ (resp. $Q_{i}(\widetilde{\mathcal{I}})\leq
Q_{i}(\mathcal{I})$).

######  Definition 5 (Balance).

An algorithm is _balanced_ with respect to a measure $Q$ if for all pairs of
$\smash{\widetilde{\mathcal{I}},\mathcal{I}}$, we have that
$\smash{Q_{i}(\mathcal{I})=Q_{i}(\widetilde{\mathcal{I}})}$.

The goal of our work is to examine the landscape of potential feedback
monotonicity properties (positive, negative, balance) for each measure
($\mathtt{APC}$ and $\mathtt{FOC}$). We note that not all combinations are
achievable: in particular, the measure $\mathtt{FOC}$ cannot satisfy balance
or negative feedback monotonicity across all instances and all arms.

######  Proposition 2.2.

Suppose that Alg has sublinear regret for stochastic losses in the
probabilistic feedback setting. For any pair of feedback probabilities
$\tilde{f}_{i}>f_{i}$, for sufficiently large $T$, there exists an instance
$\mathcal{I}$ such that
$\mathtt{FOC}_{i}(\tilde{\mathcal{I}})>\mathtt{FOC}_{i}(\mathcal{I})$. In
fact,
$\mathtt{FOC}_{i}(\tilde{\mathcal{I}})-\mathtt{FOC}_{i}(\mathcal{I})>\frac{9}{10}\cdot
T(\tilde{f}_{i}-f_{i})$.

We prove Proposition 2.2 in Appendix B; the high-level idea is to note that if
$i$ were to be the optimal arm, it must be pulled $T-o(T)$ times on each
instance.

In the remaining sections, as we analyze what feedback monotonicities are
achievable, we sometimes consider relaxed versions of the precise definitions
(e.g., restricting to suboptimal arms), as we will make explicit in the
theorem statements.

##  3 Algorithmic Transformations and Implications for $\mathtt{APC}$ and
$\mathtt{FOC}$

In order to understand how an algorithm behaves with respect to $\mathtt{APC}$
and $\mathtt{FOC}$, we need to disentangle how it reacts to probabilistic
feedback and how it incorporates feedback observations to make future
decisions. To do this, we study _black-box ( BB) transformations_ of a generic
no-regret algorithm Alg for the deterministic feedback setting into a no-
regret algorithm $\text{BB}(\textsc{Alg})$ that accounts for probabilistic
feedback. We call these transformations “black-box” as they require only query
access to Alg.

We analyze three different black-box transformations, which exhibit distinct
behavior with respect to regret, $\mathtt{APC}$, and $\mathtt{FOC}$ (see Table
1). The first, $\text{BB}_{\text{Divide}}$, divides the time horizon $T$ into
equally-sized intervals and repeatedly pulls the same arm within each interval
(Section 3.1). The second, $\text{BB}_{\text{Pull}}$, repeatedly pulls the
same arm until feedback is observed (Section 3.2). The third,
$\text{BB}_{\text{DA}}$, pulls each arm a pre-specified number of times,
depending on the feedback probability $f_{i}$ of that arm (Section 3.3).

High-level approach. All three transformations use the high-level idea of
dividing $T$ into blocks, where the transformed algorithm
$\text{BB}(\textsc{Alg})$ pulls the same arm for all rounds in the same block.
Rounds of $\text{BB}(\textsc{Alg})$ are indexed $t\in[T]$. We index blocks, or
rounds of Alg, with $\phi$, and let $\Phi$ be the total number of blocks, or
calls to Alg, in the evaluation of $\text{BB}(\textsc{Alg})$ up to $T$.
Finally, $S_{\phi}$ denotes the set of all $t$ indices that are within block
$\phi$. Then each transformation proceeds as follows. For each $\phi$, we
notate $\smash{i_{\phi}^{\textsc{Alg}}}:=\textsc{Alg}(\phi)$, i.e. the arm
selected by Alg in its $\phi$th round. Then, $\text{BB}(\textsc{Alg})$ pulls
$\smash{i_{\phi}^{\textsc{Alg}}}$ for $t\in S_{\phi}$ and returns an
observation $\smash{\ell_{i_{\phi}^{\textsc{Alg}},\phi}}$ to Alg. Each
transformation implements two steps differently: first, defining $S_{\phi}$,
and second, returning $\smash{\ell_{i_{\phi}^{\textsc{Alg}},\phi}}$ to Alg.

###  3.1 $\text{BB}_{\text{Divide}}$: Transformation for balanced
$\mathtt{APC}$ and positive $\mathtt{FOC}$

The first black-box transformation that we construct,
$\text{BB}_{\text{Divide}}$, generates algorithms that approximately balance
$\mathtt{APC}$. $\text{BB}_{\text{Divide}}$, formalized in Alg.1, separates
$T$ into equally sized blocks of size $B=\lceil 3\ln T/f^{\star}\rceil$, where
$f^{\star}\in(0,\min_{i}f_{i}]$ is a tunable parameter for trading-off regret
and monotonicity.

In the context of the high-level approach described above, the set $S_{\phi}$
is taken to be the next $B$ timesteps on $\text{BB}(\textsc{Alg})$’s time
horizon, i.e. $S_{\phi}=\left\\{(\phi-1)\cdot B+1,\ldots,\phi\cdot
B\right\\}$, and $\ell_{i_{\phi}^{\textsc{Alg}},\phi}$ is taken to be a
uniform-at-random draw from the set of observations
$\left\\{\ell_{i_{t},t}:X_{i_{t},t}=1,t\in S_{\phi}\right\\}$.

1 Set the block size to $B=\lceil 3\ln T/f^{\star}\rceil$ and initialize round
count $t=1$.

2 for  _blocks $\phi\in\\{1,\dots,\Phi=\lfloor T/B\rfloor\\}$_ do

3 Let $i_{\phi}^{\textsc{Alg}}=\textsc{Alg}(\phi)$ be the arm chosen by Alg on
its $\phi$th timestep.

4 Let $S_{\phi}=\left\\{(\phi-1)\cdot B+1,\ldots,\phi\cdot B\right\\}.$

5 Pull $i_{\phi}^{\textsc{Alg}}$ for rounds $t\in S_{\phi}$, i.e.
$i_{t}=i_{\phi}^{\textsc{Alg}},\forall t\in S_{\phi}$ and let $t\leftarrow
t+1$.

6 if  _$\exists t\in S_{\phi}$ s.t. $X_{i_{t},t}=1$ (i.e. there are
observations)_ then

7 Return a random observation to Alg, i.e.
$\ell_{i_{\phi}^{\textsc{Alg}},\phi}\sim\text{Unif}\\{\ell_{i_{t},t}:X_{i_{t},t}=1,t\in
S_{\phi}\\}$.

8

9 else Return a loss of $1$ to Alg, i.e.
$\smash{\ell_{i_{\phi}^{\textsc{Alg}},\phi}}=1$

10

11For remaining rounds, pull a random arm.

Algorithm 1 BBDivide($\textsc{Alg},f^{\star}$)

First, we show the following regret bound which holds for adversarial losses
as well as stochastic losses.

######  Theorem 3.1 (Regret $\text{BB}_{\text{Divide}}$).

Let Alg be any algorithm for the deterministic feedback setting that achieves
regret at most $R_{\textsc{Alg}}(T)$ when losses are adversarial (resp.
stochastic). Then, for $f^{\star}\in(0,\min_{i}f_{i}]$ and adversarial (resp.
stochastic) losses,

$R_{\text{BB}_{\text{Divide}}(\textsc{Alg},f^{\star})}(T)\leq\frac{3\ln
T}{f^{\star}}R_{\textsc{Alg}}\left(\frac{Tf^{\star}}{3\ln T}\right).$

Theorem 3.1 indicates that the regret of
$\text{BB}_{\text{Divide}}(\textsc{Alg})$ exceeds that of Alg by at most a
factor of $3\ln T/f^{\star}$. When Alg is specified, direct applications of
Theorem 3.1 can improve the $f^{\star}$ dependence (Appendix C.1.1).

$\text{BB}_{\text{Divide}}$ approximately balances $\mathtt{APC}$ and is
positive feedback monotonic with respect to $\mathtt{FOC}$.

######  Theorem 3.2.

[Impact of $\text{BB}_{\text{Divide}}$ on $\mathtt{APC}$ and $\mathtt{FOC}$ ]
Fix an instance
$\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{L}\right\\}$. Let
$\smash{\widetilde{f}_{i}\geq f_{i}}$, and let
$\smash{\widetilde{\mathcal{I}}=\\{\mathcal{A},\widetilde{\mathcal{F}}(i),\mathcal{L}\\}}$.
For any algorithm Alg for the deterministic feedback setting and for any
$f^{\star}\leq\min_{i}f_{i}$, if $T$ is sufficiently large, then the algorithm
$\text{BB}_{\text{Divide}}(\textsc{Alg},f^{\star})$ satisfies

$|\mathtt{APC}_{i}(\mathcal{I})-\mathtt{APC}_{i}(\widetilde{\mathcal{I}})|\leq
1/T\hskip 4.0pt\text{and}\hskip
4.0pt\mathtt{FOC}_{i}(\widetilde{\mathcal{I}})>\mathtt{FOC}_{i}(\mathcal{I}).$

These monotonicity results, together with our regret bound, suggest that
$f^{\star}$ may have opposite effects on regret and monotonicity. By Theorem
3.1, a higher value of $f^{\star}$ decreases the regret bound, and setting
$f^{\star}$ to be close to $\min_{i}f_{i}$ is optimal.666Via an estimation
phase, we can estimate $\min_{i}f_{i}$ without asymptotically affecting the
regret guarantees. Conversely, for monotonicity, while Theorem 3.2 set
$\tilde{f}_{i}>f_{i}$, the reverse statements would also hold (i.e., we could
have instead set $f_{i}>\tilde{f}_{i}\geq f^{\star}$).777The lower bound on
$\tilde{f}_{i}$ ensures that there is still an observation in each block with
high probability, despite the lower feedback probability. As such, a higher
value of $f^{\star}$ restricts the set of feedback probabilities under which
the monotonicity results apply. We give full proofs in Section C.1.

###  3.2 $\text{BB}_{\text{Pull}}$: Transformation for negative $\mathtt{APC}$
and positive $\mathtt{FOC}$

Our second transformation $\text{BB}_{\text{Pull}}$, formalized in Alg. 2,
generates algorithms with negative monotonicity in $\mathtt{APC}$.
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ will pull $i_{\phi}^{\textsc{Alg}}$
until feedback is observed for that arm, return the observation to Alg. In
terms of the structure described at the beginning of the section, if block
$\phi$ starts at time step $t$, $S_{\phi}$ is implicitly defined as the set of
time steps until there is an observation: i.e.,
$S_{\phi}=\left\\{t^{\prime}\geq t\mid
X_{i_{\phi}^{\textsc{Alg}},t^{\prime\prime}}=0\text{ }\forall
t^{\prime\prime}<t^{\prime}\right\\}$. The loss passed to Alg is the
observation made at the end of $S_{\phi}$, i.e.
$\ell_{i_{\phi}^{\textsc{Alg}},\phi}:=\ell_{i_{\phi}^{\textsc{Alg}},\max\left\\{t\mid
t\in S_{\phi}\right\\}}$.

1 Begin with $\phi=1$ and $t=1$.

2 while  _$t\leq T$_ do

3 Let $i_{\phi}^{\textsc{Alg}}=\textsc{Alg}(\phi)$ be the arm chosen by Alg on
its $\phi$th timestep.

4 while  _$X_{i_{\phi}^{\textsc{Alg}},t}=0$ and $t\leq T$_ do

5 Pull $i_{\phi}^{\textsc{Alg}}$, i.e. $i_{t}=i_{\phi}^{\textsc{Alg}}$ , and
let $t\leftarrow t+1$.

6 Return $\ell_{i_{t},t}$ to Alg, i.e.
$\ell_{i_{\phi}^{\textsc{Alg}},\phi}=\ell_{i_{t},t}$ and let
$\phi\leftarrow\phi+1$.

Algorithm 2 BBpull(Alg)

First, we bound regret for stochastic losses.888Theorem 3.3 requires
stochastic losses, because regret analysis in Theorem 3.1 relies on the block
size being fixed (and arm-independent).

######  Theorem 3.3 (Regret $\text{BB}_{\text{Pull}}$).

Let Alg be any algorithm for the deterministic feedback setting that achieves
regret at most $R_{\textsc{Alg}}(T)$ for stochastic losses. Then, for
stochastic losses, $\text{BB}_{\text{Pull}}(\textsc{Alg})$ achieves regret at
most

$R_{\text{BB}_{\text{Pull}}(\textsc{Alg})}(T)\leq
R_{\textsc{Alg}}(T)\cdot\frac{1}{\min_{i}f_{i}}.$

Theorem 3.3 shows that applying $\text{BB}_{\text{Pull}}$ increases regret by
up to a $\nicefrac{{1}}{{\min_{i}f_{i}}}$ factor, improving upon the regret
for $\text{BB}_{\text{Divide}}$ (Theorem 3.1) by a $\ln T$ factor. We next
formalize the monotonicity of $\text{BB}_{\text{Pull}}$. We show that although
$\mathtt{APC}$ is negative monotonic, $\mathtt{FOC}$ maintains positive
monotonicity, like in $\text{BB}_{\text{Divide}}$.

######  Theorem 3.4.

[Impact of $\text{BB}_{\text{Pull}}$ on $\mathtt{APC}$ and $\mathtt{FOC}$ ]
Fix an instance
$\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{L}\right\\}$ with
stochastic losses. Let $\smash{\widetilde{f}_{i}\geq f_{i}}$, and let
$\widetilde{\mathcal{I}}=\\{\mathcal{A},\widetilde{\mathcal{F}}(i),\mathcal{L}\\}$.
For any algorithm Alg for the deterministic feedback setting, the algorithm
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ satisfies

$\mathtt{APC}_{i}(\mathcal{I})\geq\mathtt{APC}_{i}(\widetilde{\mathcal{I}})\hskip
4.0pt\text{and}\hskip
4.0pt\mathtt{FOC}_{i}(\mathcal{I})\leq\mathtt{FOC}_{i}(\widetilde{\mathcal{I}}).$

###### Proof sketch.

The observations provided to Alg by $\text{BB}_{\text{Pull}}(\textsc{Alg})$
are identically distributed on $\mathcal{I}$ and
$\smash{\widetilde{\mathcal{I}}}$. A coupling argument illustrates that the
only source of difference is in the number of times that Alg is called by
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ on $\mathcal{I}$ and
$\widetilde{\mathcal{I}}$. A higher $f_{i}$ means that Alg can be called more
times before $T$ runs out on $\smash{\widetilde{\mathcal{I}}}$, giving
positive monotonicity in $\mathtt{FOC}$. For $\mathtt{APC}$, higher
$\smash{f_{i}}$ means fewer pulls per observation. Full proofs are deferred to
Appendix C.2. ∎

###  3.3 $\text{BB}_{\text{DA}}$: Transformation for positive $\mathtt{APC}$
and positive $\mathtt{FOC}$

The third-black box transformation generates algorithms that are positive
monotonic in $\mathtt{APC}$. Given an algorithm Alg for the deterministic
feedback setting, $\text{BB}_{\text{DA}}$, formalized in Alg. 3, combines
conceptual ingredients from $\text{BB}_{\text{Divide}}$ and
$\text{BB}_{\text{Pull}}$ (DA is short for DivideAdjusted). As in
$\text{BB}_{\text{Divide}}$, block sizes are pre-specified, but are also arm-
dependent, as in $\text{BB}_{\text{Pull}}$. To set block sizes $B_{i}$ for
each arm, we make the additional assumption that the algorithm designer knows
the feedback probabilities apriori, and set $\smash{B_{i}=\lceil\frac{3\ln
T}{f^{\star}}(1+f_{i})\rceil}$ for $f^{\star}\in(0,\min_{j}f_{j}]$. In terms
of the high-level approach described at the beginning of the section, the set
$S_{\phi}$ is taken to be $\left\\{(\phi-1)\cdot
B_{i_{\phi}}^{\textsc{Alg}}+1,\ldots,\phi\cdot
B_{i_{\phi}}^{\textsc{Alg}}\right\\}$, and
$\ell_{i_{\phi}^{\textsc{Alg}},\phi}$ is taken to be a uniform-at-random draw
from the set of observations $\left\\{\ell_{i_{t},t}:X_{i_{t},t}=1,t\in
S_{\phi}\right\\}$.

1 Begin with $\phi=1$ and $t=1$.

2 while  _$t\leq T$_ do

3 Let $i_{\phi}^{\textsc{Alg}}=\textsc{Alg}(\phi)$, $B_{\phi}=\lceil\frac{3\ln
T}{f^{\star}}(1+f_{i_{\phi}^{\textsc{Alg}}})\rceil$, and
$S_{\phi}=\\{t,t+1,\dots,\min(t+B_{\phi},T)\\}$.

4 for  _$t\in S_{\phi}$_ do

5 Pull $i_{\phi}^{\textsc{Alg}}$, i.e. $i_{t}=i_{\phi}^{\textsc{Alg}}$, and
let $t\leftarrow t+1$.

6 if  _$\exists t\in S_{\phi}$ s.t. $X_{i_{t},t}=1$ (i.e. there are
observations)_ then

7 Return a random observation to Alg, i.e.
$\ell_{i_{\phi}^{\textsc{Alg}},\phi}\sim\text{Unif}\\{\ell_{i_{t},t}:X_{i_{t},t}=1,t\in
S_{\phi}\\}$.

8

9 else Return a loss of $1$ to Alg, i.e.
$\smash{\ell_{i_{\phi}^{\textsc{Alg}},\phi}}=1$.

10

Update $\phi\leftarrow\phi+1$.

Algorithm 3 BBda($\textsc{Alg},f^{\star}$)

First, we show the following regret bound; Theorem 3.5 requires stochastic
losses because $B_{i}$ is arm-dependent.

######  Theorem 3.5.

[Regret $\text{BB}_{\text{DA}}$] Let Alg be any algorithm for the
deterministic feedback setting that achieves regret at most
$R_{\textsc{Alg}}(T)$ when the losses are stochastic. Then, for stochastic
losses, for any $f^{\star}\leq\min_{i}f_{i}$, the algorithm
$\text{BB}_{\text{DA}}(\textsc{Alg},f^{\star})$ achieves regret at most

$R_{\text{BB}_{\text{DA}}(\textsc{Alg})}(T)\leq\frac{6\ln
T}{f^{\star}}R_{\textsc{Alg}}\left(\frac{Tf^{\star}}{3\ln T}\right).$

Since the block size explicitly increases with $f_{i}$,
$\text{BB}_{\text{DA}}(\textsc{Alg})$ pulls an arm more frequently when its
feedback probability increases. More formally, increasing the feedback
probability of an arm (approximately) increases the number of times it is
pulled within any block where Alg selects it. We show $\text{BB}_{\text{DA}}$
exhibits positive monotonicity for both $\mathtt{APC}$ and $\mathtt{FOC}$.

######  Theorem 3.6.

[Impact of $\text{BB}_{\text{DA}}$ on $\mathtt{APC}$ and $\mathtt{FOC}$ ] Fix
an instance $\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{L}\right\\}$
with stochastic losses. Let $\smash{\tilde{f}_{i}\geq f_{i}}$, and let
$\smash{\widetilde{\mathcal{I}}=\\{\mathcal{A},\widetilde{\mathcal{F}}(i),\mathcal{L}\\}}$.
For any algorithm Alg for the deterministic feedback setting and for any
$f^{\star}\leq\min_{i}f_{i}$, the algorithm
$\text{BB}_{\text{DA}}(\textsc{Alg},f^{\star})$ satisfies

$\mathtt{APC}_{i}(\widetilde{\mathcal{I}})\geq\mathtt{APC}_{i}(\mathcal{I})-1/T\hskip
4.0pt\text{and}\hskip
4.0pt\mathtt{FOC}_{i}(\widetilde{\mathcal{I}})\geq\frac{\tilde{f}_{i}}{f_{i}}\mathtt{FOC}_{i}(\mathcal{I})-\frac{\tilde{f}_{i}}{T}>\mathtt{FOC}_{i}(\mathcal{I}).$

Theorem 3.6 also follows from a coupling argument; we defer proofs to Appendix
C.3.

##  4 Finer-Grained Analyses of Monotonicity and Regret

While the black-box transformations in Section 3 provided a clean way to
analyze the behavior of $\mathtt{FOC}$ and $\mathtt{APC}$, the regret bounds
obtained for those transformations unfortunately scaled with the minimum
feedback probability $1/\min_{i\in[K]}f_{i}$ of any arm, and the monotonicity
analysis did not differentiate between strict monotonicity and balance. In
this section, we introduce four concrete algorithms—which are variants of EXP3
(Auer et al., 2002b), UCB (Auer et al., 2002a), and AAE (Active Arm
Elimination (Even-Dar et al., 2002))—that have improved monotonicity and/or
regret guarantees.

In Section 4.1, we show that applications of $\text{BB}_{\text{Pull}}$ to AAE
and UCB can also achieve improved regret bounds that scale with the average
feedback probability $\smash{\sum_{i\in[K]}\nicefrac{{1}}{{f_{i}}}}$ across
arms rather than the minimum feedback probability
$\smash{\nicefrac{{K}}{{(\min_{i\in[K]}f_{i})}}}$. Section 4.2 shows that more
explicit analyses of $\text{BB}_{\text{Pull}}$ and $\text{BB}_{\text{DA}}$
applied to AAE enjoy stronger monotonicity guarantees than what is implied by
naive applications of Theorems 3.4 and 3.6. Finally, in Section 4.3, we move
beyond black-box transformations and present a variant of EXP3, which also
achieves regret that scales with
$\smash{\sum_{i\in[K]}\nicefrac{{1}}{{f_{i}}}}$ in the adversarial case, but
which lacks clean monotonicity properties.

###  4.1 Improved regret guarantees

Consider $\text{BB}_{\text{Pull}}$ applied to AAE and UCB, formalized in
Algorithms 4 and 5 below. First, we show that these algorithms achieve
improved regret bounds compared to a naive application of Theorem 3.1.

1 Maintain active set $A$; start with $A:=[K]$.

2 Initialize phase $s=1$ and $t=1$.

3 while  _$t\leq T$_ do

4 for  _arm $i\in A$_ do

5 Let $R_{i,s}=\emptyset$.

6 while  _$|R_{i,s}|\leq 8\ln T\cdot 2^{2s}$ and $t\leq T$_ do

7 if  _$X_{i,t}=1$_ then

8 Append $R_{i,s}\leftarrow R_{i,s}\cup\left\\{t\right\\}$.

9 Pull $i_{t}=i$, and increment $t\leftarrow t+1$.

10

11 Calculate the mean $\mu_{s}(i):=-\frac{1}{|R_{i,s}|}\sum_{t^{\prime}\in
R_{i,s}}\ell_{i,t^{\prime}}$ of the negative of all observations.999The
negative is introduced to convert losses into utilities.

12 Set $\text{LCB}_{s}(i)=\mu_{s}(i)-2^{-s}$ and
$\text{UCB}_{s}(i)=\mu_{s}(i)+2^{-s}$.

13 For any arm $i\in A$ where $\exists j\in A$ such that
$\text{LCB}_{s}(j)>\text{UCB}_{s}(i)$, remove $i$ from $A$.

14 Increment $s\leftarrow s+1$.

Algorithm 4 $\text{BB}_{\text{Pull}}(\text{AAE})$

1 Initialize number of pulls $n_{i}=0$ for all $i\in[K]$.

2 Initialize empirical mean $\mu(i)=0$ for all $i\in[K]$.

3 Initialize $t=1$.

4 while  _$t\leq T$_ do

5 if  _$n_{i}=0$ for any arm $i\in[K]$_ then

6 Let $i_{t}$ be the arm with the smallest index such that $n_{i_{t}}=0$.

7 else

8 For every arm $i\in[K]$, compute $\text{UCB}(i)=\mu(i)+\sqrt{\frac{6\ln
T}{n_{i}}}$.

9 Let $i_{t}=\text{argmax}_{j\in[K]}\text{UCB}(j)$.

10 Pull arm $i_{t}$.

11 if  _$X_{i,t}=1$_ then

12 Update the empirical mean
$\mu(i)\leftarrow\frac{n_{i_{t}}\cdot\mu(i)}{n_{i_{t}}+1}-\frac{\ell_{i_{t},t}}{n_{i_{t}}+1}$.

13 Increment $n_{i_{t}}\leftarrow n_{i_{t}}+1$.

14 Increment $t\leftarrow t+1$.

Algorithm 5 $\text{BB}_{\text{Pull}}(\text{UCB})$

######  Theorem 4.1.

On any stochastic instance
$\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{I}\right\\}$,
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ (presented in Algorithm 4) and
$\text{BB}_{\text{Pull}}(\textsc{UCB})$ (presented in Algorithm 5) have regret
bound of $O\left(\sqrt{T\ln(T)\sum_{i\in[K]}{1}/{f_{i}}}\right)$ and an
instance-dependent regret bound of
$O\left(\sum_{i\in[K]\mid\Delta_{i}>0}\frac{\ln T}{\Delta_{i}f_{i}}\right)$.

###### Proof sketch.

As in the standard analysis of AAE and UCB, we upper bound the number of times
that an arm $i$ can be pulled in terms of its reward gap $\Delta_{i}$. To do
so, we first bound the maximum number of phases an arm $i$ is active, and then
show a high probability bound on the maximum number of times $i$ can be pulled
in a given phase in terms of $f_{i}$. We defer a full proof to Section D.1 for
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ and to Section D.2 for
$\text{BB}_{\text{Pull}}(\textsc{UCB})$. ∎

Theorem 4.1 converts the dependence on the minimum feedback probability
$\min_{j}f_{j}$ from Theorem 3.3 into a finer-grained dependence on the per-
arm feedback probabilities $f_{j}$. In particular, in the instance-dependent
regret bounds of Theorem 4.1, the _“effective”_ gap $\Delta_{i}f_{i}$ can be
small either if the arm is close to optimal or if the feedback probability is
small. In contrast, the regret bound of $O(\sum_{i\in[K]}\frac{\ln
T}{\Delta_{i}\min_{j}f_{j}})$ given by applying Theorem 3.3 directly has an
effective gap $\Delta_{i}\min_{j}f_{j}$ that can be small even if
$\smash{\min_{j}f_{j}}$ is small. Similarly, the instance-independent regret
bounds in Theorem 4.1, in comparison to the instant-independent regret bound
of $\smash[b]{O(\sqrt{T(\ln T)\frac{K}{\min_{i}f_{i}}})}$, also replace the
dependence on $K/\min_{i}f_{i}$ with $\sum_{j\in[K]}1/f_{j}$.

Interestingly, the improvement in regret bounds relies on the specifics of
$\text{BB}_{\text{Pull}}$: we do not expect it to be possible to obtain a
similar improvement in regret bounds for $\text{BB}_{\text{Divide}}$ or
$\text{BB}_{\text{DA}}$ applied to AAE or UCB. Intuitively, this is because
$\text{BB}_{\text{Pull}}$ does not pull any arm more than is necessary to
observe feedback, while $\text{BB}_{\text{Divide}}$ and
$\text{BB}_{\text{DA}}$ must pull all arms (including sub-optimal ones) a
prespecified number of times, by definition.

###  4.2 Stricter monotonicity guarantees

When the black-box transformations $\text{BB}_{\text{Pull}}$ and
$\text{BB}_{\text{DA}}$ are applied to AAE, we show stronger monotonicity
properties for suboptimal arms, i.e. any arm $i$ where
$\bar{\ell}_{i}>\min_{j\in[K]}\bar{\ell}_{j}$. Specifically,
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ achieves strict negative monotonicity
in $\mathtt{APC}$ and approximate balance in $\mathtt{FOC}$ (Theorem 4.2),
while $\text{BB}_{\text{DA}}(\textsc{AAE})$ achieves strict positive
monotonicity in $\mathtt{APC}$ (Theorem 4.3). For both of these results, we
focus on suboptimal arms for technical reasons (for large $T$, AAE eventually
only pulls the optimal arm, which would equalize $\mathtt{APC}$). Despite this
restriction, we expect that the qualitative impacts of monotonicity still
arise even if monotonicity holds for all arms but the optimal arm.

We start by analyzing $\text{BB}_{\text{Pull}}(\textsc{AAE})$ (formalized in
Algorithm 4). We show that for suboptimal arms,
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ is approximately balanced for
$\mathtt{FOC}$ as long as $T$ is sufficiently large, implying (with Lemma 2.1)
that $\mathtt{APC}$ strictly decreases in $f_{i}$.

######  Theorem 4.2.

Fix a stochastic instance
$\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{L}\right\\}$. Let $i$ be
such that $\bar{\ell}_{i}>\min_{j\in[K]}\bar{\ell}_{j}$. Let
$\smash{\widetilde{f}_{i}>f_{i}}$, and let
$\smash{\widetilde{\mathcal{I}}=\\{\mathcal{A},\widetilde{\mathcal{F}}(i),\mathcal{L}\\}}$.
For sufficiently large $T$, $\text{BB}_{\text{Pull}}(\textsc{AAE})$ satisfies

$|\mathtt{FOC}_{i}(\mathcal{I})-\mathtt{FOC}_{i}(\widetilde{\mathcal{I}})|\leq\nicefrac{{1}}{{T}}\hskip
4.0pt\text{and}\hskip
4.0pt\mathtt{APC}_{i}(\widetilde{\mathcal{I}})<\mathtt{APC}_{i}(\mathcal{I}).$

Theorem 4.2 strengthens the monotonicity properties of
$\text{BB}_{\text{Pull}}$: $\text{BB}_{\text{Pull}}(\textsc{AAE})$ satisfies
strict (rather than weak) negative monotonicity in $\mathtt{APC}$, and
approximate balance (rather than weak positive monotonicity) in
$\mathtt{FOC}$.101010At first glance, it would appear that this result
contradicts Proposition 2.2, because we show balance is possible for
$\mathtt{FOC}$ (for suboptimal arms). However, Proposition 2.2 only shows that
balance is not possible across all arms (in particular, the optimal arm
necessarily exhibits positive feedback monotonicity). The proof of Theorem 4.2
leverages a modified version of the coupling argument from the proof of
Theorem 3.4 which incorporates that any suboptimal arm must be eliminated in
AAE after sufficiently many rounds. We defer a full proof to Section D.1.

To achieve strictly positive feedback monotonicity in $\mathtt{APC}$, we turn
to $\text{BB}_{\text{DA}}(\textsc{AAE})$ (formalized in Algorithm 6). The
monotonicity properties of $\text{BB}_{\text{DA}}(\textsc{AAE})$ are given in
Theorem 4.2.

1 Maintain active set of $A$; start with $A:=[K]$.

2 For arm $i\in[K]$, set $B_{i}=\lceil(1+f_{i})\cdot\frac{3\ln
T}{f^{\star}}\rceil$.

3 Initialize phase $s=1$ and $t=1$.

4 while  _$t\leq T$_ do

5 for  _arm $i\in A$_ do

6 Let $R_{i,s}=\emptyset$.

7 for  _$\min(B_{i},T-t)$ iterations_ do

8 if  _$X_{i,t}=1$ and $|R_{i,s}|<8\ln T\cdot 2^{2s}$_ then

9 Append $R_{i,s}\leftarrow R_{i,s}\cup\left\\{t\right\\}$.

10 Pull $i_{t}=i$, and increment $t\leftarrow t+1$.

11 Calculate the mean $\mu_{s}(i):=-\frac{1}{\min(|R_{i,s}|,2\ln T\cdot
2^{2s})}\sum_{t^{\prime}\in R_{i,s}}\ell_{i,t^{\prime}}$ of the negative of
the first $8\ln T\cdot 2^{2s}$ observations (if more than $8\ln T\cdot 2^{2s}$
observations are made).

12 Set $\text{LCB}_{s}(i)=\mu_{s}(i)-2^{-s}$ and
$\text{UCB}_{s}(i)=\mu_{s}(i)+2^{-s}$.

13 For any arm $i\in A$ where $\exists j\in A$ such that
$\text{LCB}_{s}(j)>\text{UCB}_{s}(i)$, remove $i$ from $A$.

14 Increment $s\leftarrow s+1$.

Algorithm 6 $\text{BB}_{\text{DA}}(\text{AAE},f^{\star})$

######  Theorem 4.3.

Fix a stochastic instance
$\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{L}\right\\}$. Let $i$ be
such that $\bar{\ell}_{i}>\min_{j\in[K]}\bar{\ell}_{j}$. Let
$\widetilde{f}_{i}>f_{i}$, and let
$\widetilde{\mathcal{I}}=\left\\{\mathcal{A},\mathcal{F}(i),\mathcal{L}\right\\}$.
For any $f^{\star}\leq\min_{i}f_{i}$ and sufficiently large $T$,
$\text{BB}_{\text{DA}}(\textsc{AAE},f^{\star})$ satisfies

$\mathtt{APC}_{i}(\widetilde{\mathcal{I}})>\mathtt{APC}_{i}(\mathcal{I})\hskip
4.0pt\text{and}\hskip
4.0pt\mathtt{FOC}_{i}(\widetilde{\mathcal{I}})>\mathtt{FOC}_{i}(\mathcal{I}).$

Theorem 4.3 follows from a similar argument as in the proof of Theorem 4.2: if
$i$ is sub-optimal, there it must be removed at the same phase on both
$\mathcal{I}$ and $\widetilde{\mathcal{I}}$. 111111As for why we begin with
analyzing $\mathtt{APC}$ instead of $\mathtt{FOC}$, note that in
$\text{BB}_{\text{Pull}}(\textsc{AAE})$, the number of observations per arm
per phase was predetermined; for $\text{BB}_{\text{DA}}(\textsc{AAE})$, the
number of pulls per arms per phase is predetermined. We defer a full proof to
Section D.3.

###  4.3 Improving regret for adversarial losses

Next, we consider the adversarial setting and aim for regret that scales with
$\sum_{i\in[K]}\nicefrac{{1}}{{f_{i}}}$, to match the stochastic result of
Theorem 4.1. Like in the stochastic setting, our black-box transforms fail to
achieve this improved regret dependence: the regret analysis from Theorem 3.1
for $\text{BB}_{\text{Divide}}(\text{EXP3})$ results in regret that
unavoidably scales with $\sqrt{\nicefrac{{K}}{{\min_{i}f_{i}}}}$,121212See
Cor. C.1. Note this is still better than scaling with
$\nicefrac{{K}}{{\min_{i}f_{i}}}$, the naive implication of Theorem 3.1.
because $\min_{i}f_{i}$ is explicitly used for determining the block size in
$\text{BB}_{\text{Divide}}$, and our regret guarantees in Section 3 for the
other two black-box transformations are restricted to stochastic losses.
Moreover, directly using standard EXP3 incurs linear regret (Proposition E.1).

We move beyond the black-box framework and construct 3-Phase EXP3 (Algorithm
7), an algorithm that achieves improved regret bounds that scale with
$\sum_{i\in[K]}\nicefrac{{1}}{{f_{i}}}$. These regret bounds for the
adversarial setting match the instance-independent regret bounds that
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ and
$\text{BB}_{\text{Pull}}(\textsc{UCB})$ achieve for the stochastic setting.
3-Phase EXP3 directly modifies EXP3 to account for probabilistic feedback: in
particular, 3-Phase EXP3 obtains both unbiased and high-probability estimates
of $\nicefrac{{1}}{{f_{i}}}$, then runs a version of standard EXP3 with a
reward estimator and learning rate that uses those estimates. However, despite
this simple structure, we empirically show that Algorithm 7 does not seem to
permit clean monotonicity properties.

1 Phase 1: Set $N=\lceil 8\log(TK)\rceil$.

2 for  _arms $i\in[K]$_ do

3 Pull arm $i$ until a reward is observed $N$ times.

4 Set $P^{LR}_{i}$ to be the total number of rounds taken by the previous step
divided by $N$.

5 Phase 2: for  _arms $i\in[K]$_ do

6 Pull arm $i$ until a reward is observed.

7 Set $P^{E}_{i}$ to be the number of rounds taken by the previous step.

8 Let $t_{0}$ indicate the current round (after the completion of phase 1 and
2).

9 Let $\pi_{i,t_{0}}=1/K$ for all $i\in[K]$.

10 Phase 3: Set $\eta=\sqrt{\frac{\log K}{T\sum_{i\in[K]}P^{LR}_{i}}}$.

11 for  _rounds $t=t_{0},\dots,T$_ do

12 Pull an arm $i_{t}$ with probability $\pi_{i_{t},t}$.

13 Update estimator: $\widehat{\ell}_{i,t}=\frac{\ell_{i,t}\cdot
X_{i,t}}{\pi_{i,t}}P^{E}_{i},\forall i\in[K]$.

14 Update weights:
$w_{i,t+1}=w_{i,t}\cdot\exp(-\eta\widehat{\ell}_{i,t}),\forall i\in[K]$.

15 Update probability distribution:
$\pi_{i,t+1}=\frac{w_{i,t+1}}{\sum_{j\in[K]}w_{j,t+1}}$, $\forall i\in[K]$.

Algorithm 7 3-Phase EXP3

Regret of 3-phase EXP3. We prove the following regret bound for 3-Phase EXP3.

######  Theorem 4.4.

Let $\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{I}\right\\}$ be an
adversarial instance such that $\ell_{i,t}\in[0,1]$ for all arms $i$ and all
time steps $1\leq t\leq T$. For an oblivious adversary and unknown $f_{i}$
values, Algorithm 7 incurs regret

$R(T)\leq O\left(\sqrt{T\ln(K)\sum_{i\in[K]}\nicefrac{{1}}{{f_{i}}}}\right).$

The intuition for Theorem 4.4 follows. If $f_{i}$’s were known, a natural way
to create an unbiased loss estimator would have been
$\hat{\ell}_{i,t}=(\nicefrac{{\ell_{i,t}}}{{\pi_{i,t}}})\cdot(\nicefrac{{X_{i,t}}}{{f_{i}}})$.
The first two phases of the algorithm adjust the algorithm to account for
unknown $f_{i}$. In particular, $P_{i}^{E}$ is a low-variance unbiased
estimator of $1/f_{i}$ and $P_{i}^{LR}=\Theta(1/f_{i})$ with high probability.
With these estimates, we adjust the second moment analysis of EXP3 while
incurring only a constant overhead in the regret. We defer the full proof to
Section E.2.

The regret bound in Theorem 4.4 outperforms the $O(\sqrt{TK\log
K/\min_{i}f_{i}})$ bound achieved by $\text{BB}_{\text{Divide}}$ applied to
EXP3 (Corollary C.1). In particular, when $\min_{i}f_{i}$ is much smaller than
other values of $f_{i}$, the regret bound in Theorem 4.4 can be up to a factor
of $K$ better than the regret bound in Corollary C.1. Theorem 4.4 also matches
(up to $\log K$) the instance-independent regret bound achieved for stochastic
losses by Algorithm 4 (Theorem 4.1).

The regret from Theorem 4.4 also outperforms regret bounds from existing work
on multi-armed bandits with probabilistic feedback (e.g. Esposito et al.
(2022)). In particular, the feedback structure in our setting corresponds to a
simple feedback graph consisting of a union of $K$ self-loops (one for each
arm) with probability $f_{i}$ associated with the self-loop for arm $i$.
Esposito et al. (2022) show a regret bound of
$\tilde{O}(\sqrt{TK/\min_{i}f_{i}})$ (with some additional optimizations when
$\min_{i}f_{i}$ is very small). Their algorithm is very similar to
$\text{BB}_{\text{Divide}}$ applied to EXP3 and uses a similar approach of
splitting the time horizon into blocks. Esposito et al. (2022) provide an
algorithm that achieves a regret bound of
$\widetilde{O}(\sqrt{T\cdot\sum_{i\in[K]}1/f_{i}})$, but only under the
additional assumption that the full feedback graph is observed at every round.
This assumption is not satisfied in our setting. In comparison, our bound
achieves a much more fine-grained dependence on the feedback probabilities
$f_{i}$.

Monotonicity of 3-Phase EXP3. However, it seems that the improved regret for
Algorithm 7 comes at the cost of clean monotonicity properties in
$\mathtt{FOC}$ and $\mathtt{APC}$. In fact, we can construct two simple
instances that exhibit significantly different feedback monotonicities with
respect to $\mathtt{APC}$, even for a simplified version of 3-Phase EXP3 where
the algorithm is given the $f_{i}$’s as inputs rather than estimating them in
the first two phases. Figure 1 shows that the algorithm exhibits strictly
positive monotonicity in one instance and strictly negative monotonicity in
the other instance.

Figure 1: Analysis of $\mathtt{APC}$ for a simplified version of 3-Phase EXP3
(Algorithm 7) in two instances where $K=2$ and $T=1000$. In Instance 1 (left),
Arm 1 has constant loss $0.9$ and Arm 2 has constant loss $0.1$; In Instance 2
(right), Arm 1 has constant loss $0.1$ and Arm 2 has constant loss $0.9$.
$\mathtt{APC}$ is strictly negative monotonic in Instance 1 and strictly
positive in Instance 2. These differing directions of monotonicity suggest
that Algorithm 7 does not exhibit clean monotonicity guarantees.

Further, the instances in Figure 1 differ only in their loss functions,
suggesting that the monotonicity properties of 3-phase EXP3 may depend on the
instance through the loss functions. Examining 3-Phase EXP3 further, we can
see that such a dependency could arise due to its loss estimator directly
incorporating estimates for $f_{i}$. In particular, unlike algorithms
generated with the black-box reductions in Section 3, 3-phase EXP3 does not
permit a clean separation between how it reacts to probabilistic feedback and
how it incorporates loss observations to make future decisions. The
entanglement of these decisions may make monotonicity unavoidably instance-
dependent.

##  5 Beyond Monotonicity: An Empirical Study of Correlations

To better understand and control the downstream impacts of the relationship
between feedback and $\mathtt{APC}$/$\mathtt{FOC}$, our theoretical analysis
focuses on the monotonicity properties of these relationships, not just
correlation. Monotonic dependence shifts the state of the entire system,
rather than only in certain pockets of the content landscape, and so it is a
stronger property to study. However, the weaker notion of correlations may
also be of concern; here, we initiate a numerical exploration of correlation
induced by bandit algorithms between $f_{i}$ and
$\mathtt{APC}$/$\mathtt{FOC}$.

Fig. 2 shows the correlation between either measure and the $f_{i}$’s in a
single instance. In this example, by inspection appears that
$\mathtt{APC}_{i}$ is weakly negatively correlated with $f_{i}$ across
algorithms, and $\mathtt{FOC}_{i}$ is somewhat more strongly positively
correlated with $f_{i}$ across algorithms. Furthermore, these trends hold
consistently across randomly generated instances. We give experimental details
below.

Figure 2: Correlations induced between $f_{i}$ and $\mathtt{APC}_{i}$ (top
row) as well as $\mathtt{FOC}_{i}$ (bottom row) by
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ (left column),
$\text{BB}_{\text{Pull}}(\textsc{UCB})$ (middle), and 3-Phase EXP3 (right).
There are $K=100$ arms and $T=1000$ rounds. The darkness of a point indicates
the corresponding arm’s average utility; darker is higher.

Algorithms. On each instance, we run three of the algorithms from Section 4:
$\text{BB}_{\text{Pull}}(\textsc{UCB})$ (Algorithm 5),
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ (Algorithm 4), and 3-Phase EXP3
(Algorithm 7) with the simplification that the algorithm is given the
$f_{i}$’s as inputs (rather than estimating them in the first two phases).

Instance generation methods. All of our instances have $K=100$ arms and
$T=1000$ rounds. We first uniformly randomly generate the means of arms’
utility / loss distributions (utilities for
$\text{BB}_{\text{Pull}}(\textsc{UCB})$ and
$\text{BB}_{\text{Pull}}(\textsc{AAE})$, losses for 3-Phase EXP3). These means
range from 0 to 1 for $\text{BB}_{\text{Pull}}(\textsc{UCB})$, 0 to 5 for
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ 131313The larger magnitude for AAE
ensures that arms are actually eliminated in the time horizon $T$ we have
chosen to be standard across algorithms., and -1 to 0 for 3-Phase EXP3. Then,
for each arm, we sample realized rewards for each time step in $[T]$ from a
Gaussian distribution centered at that arm’s mean with standard deviation 0.1
for $\text{BB}_{\text{Pull}}(\textsc{UCB})$ and 3-Phase EXP3 and 0.5 for
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ (commensurate with the scaled up
mean). Negative utilities / positive losses are truncated to 0. Finally, we
uniformly draw each arm’s $f_{i}$ from the interval $[0,1]$.

Results. For illustrative purposes, the scatter plots below show the
correlation between either measure and the $f_{i}$’s over arms in a single
random instance. In this single example, by inspection it looks as if
$\mathtt{APC}_{i}$ is weakly negatively correlated with $f_{i}$ across
algorithms, and $\mathtt{FOC}_{i}$ is somewhat more strongly positively
correlated with $f_{i}$ across algorithms.

We show these trends to hold consistently across randomly generated instances:
we randomly generate $100$ instances by the same procedure as above, and
evaluate the Pearson correlation coefficient141414The Pearson correlation
coefficient is the ratio of two variables’ covariance and the product of their
standard deviations. It ranges from $-1$ to $1$, where positive (resp.
negative) values indicate positive (resp. negative) correlation, and magnitude
indicates the strength of correlation. between $\mathtt{APC}_{i}$ and $f_{i}$,
$\mathtt{FOC}_{i}$ and $f_{i}$ for each of the three algorithms on every
instance. In Table 2 below, we report the average Pearson correlation
coefficients across these instances, which are consistent with the inspected
trends in our scatter plots.

| APCi and $f_{i}$ | FOCi and $f_{i}$
---|---|---
| mean | min | max | mean | min | max
$\text{BB}_{\text{Pull}}(\textsc{UCB})$ | $-0.33$ | $-0.51$ | $-0.16$ | $0.43$ | $0.22$ | $0.59$
3-Phase EXP3 | $-0.23$ | $-0.41$ | $0.03$ | $0.72$ | $0.49$ | $0.86$
$\text{BB}_{\text{Pull}}(\textsc{AAE})$ | $-0.33$ | $-0.53$ | $-0.11$ | $0.74$ | $0.54$ | $0.88$
Table 2: Correlations between $f_{i}$ and $\mathtt{APC}$/$\mathtt{FOC}$
observed in 100 randomly generated instances.

##  6 Discussion

In this work, we illustrate how the learning algorithm can inadvertently lead
to downstream impacts on users even when the objective is perfectly aligned
with user welfare. In particular, we show that the ways in which the algorithm
handles heterogeneous rates of user reaction across different types of content
can inadvertently impact the user experience. To study this, we provide a
framework to investigate how the learning algorithm’s engagement with
individual arms depends on the feedback rates of the arms. We analyze the
monotonicity of the arm pull count $\mathtt{APC}$ and the feedback observation
count $\mathtt{FOC}$ in the feedback rates across the space of no-regret
algorithms. From a platform design perspective, our results highlight the
importance of measuring the feedback monotonicity of a learning algorithm as
well as the resulting downstream impacts on users.

To achieve some of these monotonicities, many of our algorithms require
discarding information. This creates an interesting parallel to the literature
on robust bandits: While it is common to discard bandit observations that are
produced by adversarial or non-myopic agents (e.g. Lykouris et al. (2018);
Haghtalab et al. (2022); Gupta et al. (2019)), our work discards information
not because the information is untrustworthy but because we aim to avoid
undesirable downstream impact. On the other hand, in the probabilistic
feedback setting, information is already hard to come by; intuitively, we may
want to do better with the information we do have access to. An interesting
open question, therefore, is about whether it might be possible to interpolate
between monotonicity properties and how efficiently information is used, and
whether such an approach can also improve regret.

Ultimately, which feedback monotonicities the platform may hope to induce will
inherently depend on which downstream effects are desirable or concerning.
This may differ across areas of the content space: for example, among content
that tends to generate constructive discussion, we may want positive feedback
monotonicity in $\mathtt{FOC}$, as this would elicit more beneficial user
interaction. Meanwhile, among the kinds of content described in Examples 1 and
2, negative monotonicity or balance may be preferred. As the algorithms we
give in this work affect monotonicity over all content, more practical future
directions may explore finer-grained control over monotonicity in different
subsets of the content space.

Finally, though our theoretical analysis focuses on monotonicity, in real-
world settings, more general correlations between feedback and $\mathtt{APC}$
or $\mathtt{FOC}$ may also be of concern to the platform. In Section 5, we
give a simulation study of correlations induced by common bandit algorithms.
Combined with our rigorous monotonicity results, these simulations provide a
bridge towards better understanding how probabilistic feedback can shape the
impacts of a learning algorithm on users.

## References

  * Adomavicius et al. [2013] Gediminas Adomavicius, Jesse C. Bockstedt, Shawn P. Curley, and Jingjing Zhang.  Do recommender systems manipulate consumer preferences? A study of anchoring effects.  _Information Systems Research_ , 24(4):956–975, 2013.
  * Agan et al. [2023] Amanda Y Agan, Diag Davenport, Jens Ludwig, and Sendhil Mullainathan.  Automating automaticity: How the context of human choice affects the extent of algorithmic bias.  Technical report, National Bureau of Economic Research, 2023.
  * Allcott et al. [2020] Hunt Allcott, Luca Braghieri, Sarah Eichmeyer, and Matthew Gentzkow.  The welfare effects of social media.  _American Economic Review_ , 110(3):629–676, 2020\.
  * Alon et al. [2015] Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, and Tomer Koren.  Online learning with feedback graphs: Beyond bandits.  In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, _Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015_ , volume 40 of _JMLR Workshop and Conference Proceedings_ , pages 23–35. JMLR.org, 2015.
  * Auer et al. [2002a] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47:235–256, 2002a.
  * Auer et al. [2002b] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002b.
  * Ben-Porat and Tennenholtz [2018] Omer Ben-Porat and Moshe Tennenholtz.  A game-theoretic approach to recommendation systems with strategic content providers.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 1118–1128, 2018.
  * Ben-Porat et al. [2020] Omer Ben-Porat, Itay Rosenberg, and Moshe Tennenholtz.  Content provider dynamics and coordination in recommendation ecosystems.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Buening et al. [2023] Thomas Kleine Buening, Aadirupa Saha, Christos Dimitrakakis, and Haifeng Xu.  Bandits meet mechanism design to combat clickbait in online recommendation.  _arXiv preprint arXiv:2311.15647_ , 2023.
  * Cao et al. [2021] Dongmei Cao, Maureen Meadows, Donna Wong, and Senmao Xia.  Understanding consumers’ social media engagement behaviour: An examination of the moderation effect of social media context.  _Journal of Business Research_ , 122:835–846, 2021.
  * Carroll et al. [2022] Micah D. Carroll, Anca D. Dragan, Stuart Russell, and Dylan Hadfield-Menell.  Estimating and penalizing induced preference shifts in recommender systems.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, _International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 2686–2708. PMLR, 2022.
  * Commission [2022] The European Commission.  Digital services act: EU’s landmark rules for online platforms enter into force.  2022\.
  * Cortes et al. [2020] Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang.  Online learning with dependent stochastic feedback graphs.  In _International Conference on Machine Learning_ , pages 2154–2163. PMLR, 2020.
  * Dean and Morgenstern [2022] Sarah Dean and Jamie Morgenstern.  Preference dynamics under personalized recommendations.  In David M. Pennock, Ilya Segal, and Sven Seuken, editors, _EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022_ , pages 795–816. ACM, 2022.
  * Dean et al. [2020] Sarah Dean, Sarah Rich, and Benjamin Recht.  Recommendations and user agency: the reachability of collaboratively-filtered information.  In _Conference on Fairness, Accountability, and Transparency (FAT* ’20)_ , pages 436–445. ACM, 2020.
  * Ekstrand and Willemsen [2016] Michael D. Ekstrand and Martijn C. Willemsen.  Behaviorism is not enough: Better recommendations through listening to users.  In Shilad Sen, Werner Geyer, Jill Freyne, and Pablo Castells, editors, _Proceedings of the 10th ACM Conference on Recommender Systems, Boston, MA, USA, September 15-19, 2016_ , pages 221–224. ACM, 2016\.
  * Esposito et al. [2022] Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven, and Nicolò Cesa-Bianchi.  Learning on the edge: Online learning with stochastic feedback graphs.  _Advances in Neural Information Processing Systems_ , 35:34776–34788, 2022.
  * Even-Dar et al. [2002] Eyal Even-Dar, Shie Mannor, and Yishay Mansour.  PAC bounds for multi-armed bandit and Markov decision processes.  In _International Conference on Computational Learning Theory_ , pages 255–270, 2002.
  * Ferrara and Yang [2015] Emilio Ferrara and Zeyao Yang.  Measuring emotional contagion in social media.  _PloS one_ , 10(11):e0142390, 2015.
  * Flaxman et al. [2016] Seth Flaxman, Sharad Goel, and Justin M. Rao.  Filter Bubbles, Echo Chambers, and Online News Consumption.  _Public Opinion Quarterly_ , 80:298–320, 2016.
  * Ghari and Shen [2022] Pouya M Ghari and Yanning Shen.  Online learning with probabilistic feedback.  In _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 4183–4187. IEEE, 2022.
  * Guo et al. [2021] Wenshuo Guo, Karl Krauth, Michael I. Jordan, and Nikhil Garg.  The stereotyping problem in collaboratively filtered recommender systems.  In _ACM Conference on Equity and Access in Algorithms (EAAMO)_ , pages 6:1–6:10, 2021.
  * Gupta et al. [2019] Anupam Gupta, Tomer Koren, and Kunal Talwar.  Better algorithms for stochastic bandits with adversarial corruptions.  In _Conference on Learning Theory_ , pages 1562–1578. PMLR, 2019\.
  * Haghtalab et al. [2022] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei.  Learning in stackelberg games with non-myopic agents.  In _Proceedings of the 23rd ACM Conference on Economics and Computation_ , pages 917–918, 2022.
  * Haupt and Narayanan [2022] Andreas Haupt and Aroon Narayanan.  Risk aversion in learning algorithms and an application to recommendation systems.  _arXiv preprint arXiv:2205.04619_ , 2022.
  * Hazan et al. [2016] Elad Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Henderson et al. [2022] Peter Henderson, Ben Chugg, Brandon Anderson, and Daniel E Ho.  Beyond ads: Sequential decision-making algorithms in law and public policy.  In _Proceedings of the 2022 Symposium on Computer Science and Law_ , pages 87–100, 2022.
  * Hron et al. [2022] Jiri Hron, Karl Krauth, Michael I. Jordan, Niki Kilbertus, and Sarah Dean.  Modeling content creator incentives on algorithm-curated platforms.  _CoRR_ , abs/2206.13102, 2022.
  * Jagadeesan et al. [2022] Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt.  Supply-side equilibria in recommender systems.  _CoRR_ , abs/2206.13489, 2022.
  * Joachims et al. [2005] Thorsten Joachims, Laura Granka, Bing Pan, Helene Hembrooke, and Geri Gay.  Accurately interpreting clickthrough data as implicit feedback.  2005\.
  * Joachims et al. [2017] Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel.  Unbiased learning-to-rank with biased feedback.  In _Proceedings of the tenth ACM international conference on web search and data mining_ , pages 781–789, 2017.
  * Joseph et al. [2016] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth.  Fairness in learning: Classic and contextual bandits.  _Advances in neural information processing systems_ , 29, 2016.
  * Kleinberg et al. [2022] Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan.  The challenge of understanding what users want: Inconsistent preferences and engagement optimization.  In David M. Pennock, Ilya Segal, and Sven Seuken, editors, _EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022_ , page 29. ACM, 2022.
  * Kramer et al. [2014] Adam DI Kramer, Jamie E Guillory, and Jeffrey T Hancock.  Experimental evidence of massive-scale emotional contagion through social networks.  _Proceedings of the National academy of Sciences of the United States of America_ , 111(24):8788, 2014.
  * Li et al. [2020] Shuai Li, Wei Chen, Zheng Wen, and Kwong-Sak Leung.  Stochastic online learning with probabilistic graph feedback.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 4675–4682, 2020.
  * Li and Xie [2020] Yiyi Li and Ying Xie.  Is a picture worth a thousand words? an empirical study of image content and social media engagement.  _Journal of Marketing Research_ , 57(1):1–19, 2020.
  * Lykouris et al. [2018] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme.  Stochastic bandits robust to adversarial corruptions.  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 114–122, 2018.
  * Milli et al. [2021] Smitha Milli, Luca Belli, and Moritz Hardt.  From optimizing engagement to measuring value.  In Madeleine Clare Elish, William Isaac, and Richard S. Zemel, editors, _FAccT ’21: 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual Event / Toronto, Canada, March 3-10, 2021_ , pages 714–722. ACM, 2021.
  * Ribeiro et al. [2020] Manoel Horta Ribeiro, Raphael Ottoni, Robert West, Virgílio AF Almeida, and Wagner Meira Jr.  Auditing radicalization pathways on youtube.  In _Proceedings of the 2020 conference on fairness, accountability, and transparency_ , pages 131–141, 2020.
  * Roose [2019] Kevin Roose.  The making of a youtube radical.  _The New York Times_ , 2019.
  * Schnabel et al. [2019] Tobias Schnabel, Paul N Bennett, and Thorsten Joachims.  Shaping feedback data in recommender systems with interventions based on information foraging theory.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , pages 546–554, 2019.
  * Stray et al. [2021] Jonathan Stray, Ivan Vendrov, Jeremy Nixon, Steven Adler, and Dylan Hadfield-Menell.  What are you optimizing for? aligning recommender systems with human values.  _CoRR_ , abs/2107.10939, 2021.
  * Stray et al. [2022] Jonathan Stray, Alon Y. Halevy, Parisa Assar, Dylan Hadfield-Menell, Craig Boutilier, Amar Ashar, Lex Beattie, Michael D. Ekstrand, Claire Leibowicz, Connie Moon Sehat, Sara Johansen, Lianne Kerlin, David Vickrey, Spandana Singh, Sanne Vrijenhoek, Amy X. Zhang, McKane Andrus, Natali Helberger, Polina Proutskova, Tanushree Mitra, and Nina Vasan.  Building human values into recommender systems: An interdisciplinary synthesis.  _CoRR_ , abs/2207.10192, 2022.
  * Wells et al. [2021] Georgia Wells, Jeff Horwitz, and Deepa Seetharaman.  Facebook knows instagram is toxic for teen girls, company documents show.  _The Wall Street Journal_ , 2021.

##  Appendix A Additional Motivating Examples

Here, we provide additional elaboration for why varied feedback rates may
cause downstream impacts on users, motivating our study of $\mathtt{APC}$ and
$\mathtt{FOC}$.

######  Example 3 (Clickbait and $\mathtt{APC}$).

Observable feedback often occurs in the form of “clicks” or “likes/dislikes;”
a high feedback rate is correlated with how “clickbaity” the content is.
Creators may be incentivized to optimize for $\mathtt{APC}$, which captures
objectives like view count. A creator can easily increase clickbaitiness (e.g.
by changing content title or video thumbnail) without affecting the content’s
true utility. Thus, if the algorithm induces positive correlations between
$\mathtt{APC}$ and feedback rate, creators may seek to make cosmetic changes
without necessarily improving content quality. In the absence of positive
correlation between $\mathtt{APC}$ and feedback rates, creators would be
unable to rely on cheap strategies to generate engagement; instead, they would
need to actually improve the quality of their content in order to increase the
likelihood that it is shown to users.

More generally, even absent creator incentives, we can see that different
relationships between feedback rate and $\mathtt{APC}$/$\mathtt{FOC}$ can
result in qualitative differences in user experience.

######  Example 4 (Recommended topics).

Certain content topics, such as political commentary or news, may naturally
correspond to higher feedback rates than other topics, such as scientific or
educational material. If the algorithm induces positive correlations between
APC and feedback rate, then this would result in more political content shown
to users; if it induces negative correlations, more educational content would
be shown to users. Both have significant consequences for the overall
qualitative user experience on the platform. (Of course it is possible for the
platform to manually up- or down-weight content of various topics to control
the content balance shown to users; however, we are interested in
understanding possibly-unexpected changes that arise as a consequence of the
learning algorithm itself.) Adding the possibility of creator incentives in
this setting only amplifies these effects.

Finally, we would like to highlight that understanding how algorithms behave
with respect to APC and FOC under probabilistic feedback settings is of
general interest in many applications where bandits are used to model
sequential decisionmaking settings, even beyond content recommendation in
online platforms.

######  Example 5 (Advertising).

In online advertising, retailers trying to place ads via a centralized
platform (such as Google) can decide whether to pay the platform per-click, or
per-conversion. We can think of the number of times an ad is shown as
$\mathtt{APC}$, and the number of times an ad is clicked as $\mathtt{FOC}$. If
the retailers choose pay-per-conversion, the resulting data provided to the
platform can be viewed as having a lower feedback probability than the data
that would have been provided for pay-per-click: this is because a conversion
only happens a subset of the time that a click happens. Retailers may want to
maximize the number of times that their ad is shown, which is captured by
$\mathtt{APC}$. Whether an algorithm induces positive or negative correlations
with $\mathtt{APC}$ and feedback rate could affect which of these payment
models advertisers decide to select.

######  Example 6 (Audits and public policy).

Because it is costly to ensure that every single person or organization
complies exactly with established standards or laws, governments often instead
prefer to conduct audits, where some people or organizations are selected for
an audit.151515See Henderson et al. [2022] for a more extensive discussion of
bandits applied in similar contexts. In this model, we can think of an arm as
the person or organization to be audited; the pull of an arm as an audit; and
feedback observation as whether the government will be able to get the ground
truth “yes/no” for whether the law was violated. Why might some arms have
lower or higher feedback probabilities? There may be some other
reasons/features of the arm that affect feedback probability: for example, it
may be harder to observe feedback for small businesses (vs bigger ones that
have structured accounting departments), or non-English-speaking businesses.
This reasoning also gives intuition for why it may be undesirable to pull low
or high feedback arms more often (i.e. why monotonicity in $\mathtt{APC}$ may
be problematic) — for example, perhaps this means that in the long run,
minority-owned businesses or smaller companies are audited disproportionately
more than larger ones.

##  Appendix B Supplemental Materials for Section 2

We prove Lemma 2.1, restated below for convenience. See 2.1

###### Proof of Lemma 2.1.

For an arm $i\in[K]$, recall that we have defined $X_{i,t}$ to be the random
variable corresponding to whether feedback is returned at round $t$, if arm
$i$ were to be pulled, i.e., $X_{i,t}\sim\texttt{Bern}(f_{i})$, and $H_{t}$ to
be the history of algorithm Alg until round $t$:
$H_{t}=\\{(i_{\tau},\ell_{i_{\tau},\tau}\cdot\mathbbm{1}\\{X_{i_{\tau},\tau}\\},X_{i_{\tau},\tau})\\}_{\tau\in[t-1]}$.
Then, for any arm $i\in[K]$, by the definition of $\mathtt{FOC}_{i}$ we have
that:

$\displaystyle\mathtt{FOC}_{i}(\mathcal{I})$
$\displaystyle=\mathbb{E}_{H_{t},\ell_{i_{t},t},X_{i_{t},t}}\left[\sum_{t\in[T]}\mathbbm{1}\left[i_{t}=i\right]\cdot
X_{i_{t},t}\right]$ (Definition 3)
$\displaystyle=\mathbb{E}_{H_{t}}\left[\mathbb{E}_{\ell_{i_{t},t},X_{i_{t},t}}\left[\sum_{t\in[T]}\mathbbm{1}\left[i_{t}=i\right]\cdot
X_{i_{t},t}\Big{|}H_{t}\right]\right]$ (law of total expectation)
$\displaystyle=f_{i}\cdot\mathbb{E}_{\ell_{i_{t},t},X_{i_{t},t}}\left[\sum_{t\in[T]}\mathbbm{1}\left[i_{t}=i\right]\right]$
(note that $\mathbb{E}[X_{i,t}\mid H_{t}]=\mathbb{E}[X_{i_{t},t}]=f_{i}$)
$\displaystyle=f_{i}\cdot\mathtt{APC}_{i}(\mathcal{I})$

where the third equality is due to the fact that conditioning on $H_{t}$, the
arm drawn by Alg $i_{t}$ is independent of whether $X_{i_{t},t}$ is $0$ or
$1$. ∎

We prove Proposition 2.2, restated below for convenience. See 2.2

###### Proof of Proposition 2.2.

By Lemma 2.1, we have that
$\mathtt{FOC}_{i}(\widetilde{\mathcal{I}})-\mathtt{FOC}_{i}({\mathcal{I}})=\tilde{f}_{i}*\mathtt{APC}_{i}(\widetilde{\mathcal{I}})-f_{i}*\mathtt{APC}_{i}(\mathcal{I})$,
and since $f_{i}<\widetilde{f}_{i}$, we can write
$f_{i}=c\cdot\widetilde{f}_{i}$ for some $c<1$.

Let $i$ be the optimal arm. A no-regret algorithm will pull $i$ $T-o(T)$ times
on both $\mathcal{I}$ and $\widetilde{\mathcal{I}}$, so that for a fixed $T$,
there exists some $\alpha>0$ where
$\mathtt{APC}_{i}(\widetilde{\mathcal{I}})>T\cdot c^{\alpha}$.

Now, we have

$\displaystyle\tilde{f}_{i}*\mathtt{APC}_{i}(\widetilde{\mathcal{I}})-f_{i}*\mathtt{APC}_{i}(\mathcal{I})$
$\displaystyle>\tilde{f}_{i}\cdot c^{\alpha}\cdot
T-f_{i}\cdot\mathtt{APC}_{i}(\mathcal{I})$
$\displaystyle\geq\tilde{f}_{i}\cdot c^{\alpha}\cdot T-f_{i}\cdot T$
$\displaystyle=T\cdot\widetilde{f}_{i}\cdot(c^{\alpha}-c).$

It remains to show that

$\displaystyle T\cdot\widetilde{f}_{i}\cdot(c^{\alpha}-c)>\frac{9}{10}\cdot
T(\widetilde{f}_{i}-f_{i})$ $\displaystyle=\frac{9}{10}\cdot
T\cdot\widetilde{f}_{i}\cdot(1-c)$ $\displaystyle\iff c^{\alpha}-c$
$\displaystyle>\frac{9}{10}-\frac{9}{10}c$ $\displaystyle\iff
c^{\alpha}-\frac{c}{10}$ $\displaystyle>9/10.$

Taking $T$ to be sufficiently large guarantees that $\alpha$ is sufficiently
small for the above inequality to hold.

∎

##  Appendix C Supplemental Materials for Section 3

In this section, we provide proofs of regret and montonicity guarantees for
our black-box transformations.

###  C.1 Proofs for Section 3.1: $\text{BB}_{\text{Divide}}$

Recall that $\text{BB}_{\text{Divide}}$, formalized in Algorithm 1, divides
time horizon into equally-sized blocks of size $B=\nicefrac{{3\ln
T}}{{f^{\star}}}$. We analyze its regret and monotonicity properties below.

####  C.1.1 Corollaries of Theorem 3.5

Finally, we present several corollaries which give the regret of
$\text{BB}_{\text{Divide}}$ applied to standard bandit algorithms.

######  Corollary C.1.

For fixed $f^{\star}\in(0,\min_{i}f_{i}]$, transformation
$\text{BB}_{\text{Divide}}$ applied to standard EXP3 incurs the following
regret:

$R_{\text{BB}_{\text{Divide}}(\text{EXP3},f^{\star}))}(T)\leq
O\left(\sqrt{\frac{1}{f^{\star}}\cdot TK\ln(T)\ln(K)}\right).$

This follows from Theorem 3.1, along with the known result of Auer et al.
[2002b] that the regret for standard EXP3 is $R_{\text{EXP3}}(T)\leq
O(\sqrt{TK\ln K})$.

######  Corollary C.2.

For fixed $f^{\star}\in(0,\min_{i}f_{i}]$, transformation
$\text{BB}_{\text{Divide}}$ applied to standard UCB incurs the following
regret:

$R_{\text{BB}_{\text{Divide}}(\text{UCB},f^{\star}))}(T)\leq
O\left(\sum_{i\in[K]}\frac{\ln^{2}(T)}{\Delta_{i}\cdot f^{\star}}\right).$

This follows from Theorem 3.1, along the known result of Auer et al. [2002a]
that the instance-dependent regret for standard UCB is $R_{UCB}(T)\leq
O\left(\ln T\cdot\left(\sum_{i\in[K]}\frac{1}{\Delta_{i}}\right)\right)$,
where $\Delta_{i}=\bar{\ell}_{i}-\min_{j}\bar{\ell}_{j}$.

######  Corollary C.3.

For fixed $f^{\star}\in(0,\min_{i}f_{i}]$, transformation
$\text{BB}_{\text{Divide}}$ applied to standard AAE incurs the following
regret:

$R_{\text{BB}_{\text{Divide}}(\text{AAE},f^{\star}))}(T)\leq
O\left(\sum_{i\in[K]}\frac{\ln^{2}(T)}{\Delta_{i}\cdot f^{\star}}\right).$

This follows from Theorem 3.1, along the known result by Even-Dar et al.
[2002] that the instance-dependent regret for standard AAE is $R_{AAE}(T)\leq
O\left(\ln T\cdot\left(\sum_{i\in[K]}\frac{1}{\Delta_{i}}\right)\right)$,
where $\Delta_{i}=\bar{\ell}_{i}-\min_{j}\bar{\ell}_{j}$.

####  C.1.2 Regret of $\text{BB}_{\text{Divide}}$: Proof of Theorem 3.1

We prove Theorem 3.1 and give some applications to concrete algorithms. For
convenience, we restate the regret bound of $\text{BB}_{\text{Divide}}$ below.
See 3.1

To analyze the regret of $\text{BB}_{\text{Divide}}$ applied to a generic
algorithm Alg, we will use the following lemma, which lower bounds the
likelihood of seeing a sample from the true loss distribution in every block.

######  Lemma C.4.

Fix an $f^{\star}\in(0,\min_{i}f_{i}]$, and divide the time horizon $T$ into
blocks of size $B=\frac{3\ln T}{f^{\star}}$ and let $\Phi=\lfloor T/B\rfloor$,
as in Algorithm 1. Suppose then that for each block
$\phi\in\\{1,2,\dots,\Phi$}, we play the same arm $i_{\phi}$ for every round
in block $\phi$. Let $E$ be the “ _clean event_ ” that at least one feedback
observation occurs in _each_ block $\phi$, i.e., that for all blocks $\phi$,
$\exists t\in S_{\phi}:X_{i_{t},t}=1$. Then, $\Pr[E]\geq 1-1/T^{2}$.

###### Proof.

Let $E_{\phi}$ be the event that at least one feedback observation occurred in
block $\phi$, i.e., $\exists t\in S_{\phi}:X_{i_{t},t}=1$. Since for any arm
$i$, $\Pr[X_{i,t}=1]=f_{i}$, then for arm $i_{\phi}$, we have that

$\Pr[\neg
E_{\phi}]=(1-f_{i_{\phi}})^{B}\leq(1-f^{\star})^{B}\leq\exp(-f^{\star}B)=1/T^{3}.$

Union bounding over all $\lfloor T/B\rfloor$ blocks, we conclude that

$\Pr[\neg E]\leq\sum_{\phi\in[\Phi]}\Pr[\neg E_{\phi}]\leq 1/T^{2}.\qed$

We are now ready to prove Theorem 3.1.

###### Proof of Theorem 3.1: Regret $\text{BB}_{\text{Divide}}$.

Throughout the proof we will use $f^{\star}\in(0,\min_{i}f_{i}]$.

First, observe that Line 9 of Algorithm 1 (i.e., the last $T-B\Phi$ steps of
the time horizon) contributes $O(\ln T)$ regret, because
$T-B\Phi<T-B\frac{T}{B}+B\leq B=\frac{3\ln T}{f^{\star}}$. The rest of the
proof thus analyzes the regret incurred in the first $B\Phi$ time steps. Now,
we divide up these rounds into $\Phi$ blocks of size $B$, and let $E$ be the
“clean event” that at least one feedback observation occurs in each block
$\phi\in\\{1,\dots,\Phi\\}$. By Lemma C.4, we have that $\Pr[E]\geq
1-\frac{1}{T^{2}}$. The event that $E$ does not occur contributes at most
$O(1)$ to the expected regret, so we can condition on $E$ for the remainder of
the analysis.

Next, fix an instance with stochastic feedback
$\mathcal{I}=\\{\mathcal{A},\mathcal{F},\mathcal{L}\\}$ over $T$ rounds. Now,
we define corresponding instance with deterministic feedback
$\mathcal{I^{\prime}}=\\{\mathcal{A},(1,\dots,1),\mathcal{L}^{\prime}\\}$ over
$\Phi=\lfloor T/B\rfloor$ time steps, where $\mathcal{L}^{\prime}$ denotes the
process generating the following sequence of $\Phi$ losses
$\ell_{i,1}^{\prime},\dots,\ell_{i,\Phi}^{\prime}$ for all $i\in\mathcal{A}$:
For all $i\in\mathcal{A}$ and $\phi\in\\{1,\dots,\Phi\\}$,
$\ell^{\prime}_{i,\phi}\sim\mathrm{Unif}\left\\{\ell_{i,s}:s\in
S_{\phi}\right\\}$, i.e., the loss is sampled uniformly from the loss
functions of the original instance within block $\phi$. Now, we show that the
(pseudo)regret of Alg on instance $\mathcal{I}^{\prime}$ over $\Phi$ rounds is
the same as that of $\text{BB}_{\text{Divide}}(\textsc{Alg},f^{\star})$ on
instance $\mathcal{I}$ over $T$ rounds. By the definition of the regret, the
regret of Alg on the instance $\mathcal{I}^{\prime}$ is equal to

$\mathbb{E}\left[\sum_{\phi=1}^{\Phi}\ell^{\prime}_{i_{\phi},\phi}\right]-\min_{i}\mathbb{E}\left[\sum_{\phi=1}^{\Phi}\ell^{\prime}_{i,\phi}\right],$
(1)

where the randomness of the first expectation is due to the randomness of the
algorithm Alg and $\mathcal{L}^{\prime}$. The regret of
$\text{BB}_{\text{Divide}}(\textsc{Alg})$ on $\mathcal{I}$ is equal to:

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\ell_{i_{t},t}\right]-\min_{i}\mathbb{E}\left[\sum_{t=1}^{T}\ell_{i,t}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{\phi=1}^{\Phi}\sum_{t\in
S_{\phi}}\ell_{i_{\phi},t}\right]-\min_{i}\sum_{\phi=1}^{\Phi}\sum_{t\in
S_{\phi}}\mathbb{E}[\ell_{i,t}]$
$\displaystyle=B\cdot\left(\mathbb{E}\left[\sum_{\phi=1}^{\Phi}\underbrace{\frac{1}{B}\sum_{t\in
S_{\phi}}\ell_{i_{\phi},t}}_{(A)}\right]-\min_{i}\sum_{\phi=1}^{\Phi}\underbrace{\frac{1}{B}\sum_{t\in
S_{\phi}}\mathbb{E}[\ell_{i,t}]}_{(B)}\right)$

where randomness in the expectation is due to the randomness of
$\text{BB}_{\text{Divide}}(\textsc{Alg})$, the randomness of feedback
observations, and the randomness of the loss functions. Notice that (A) is
equal to the $\mathbb{E}[\ell^{\prime}_{i_{\phi},\phi}]$ and (B) is equal to
$\mathbb{E}[\ell^{\prime}_{i,\phi}]$. Moreover, the observation at the end of
the $\phi$th block, which is passed as the loss to Alg for its $\phi$th
timestep, is also distributed according to
$\text{Unif}\left\\{\ell_{i_{\phi},t}:t\in S_{\phi}\right\\}$.

We thus see that:

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\ell_{i_{t},t}\right]-\min_{i}\mathbb{E}\left[\sum_{t=1}^{T}\ell_{i,t}\right]$
$\displaystyle=B\cdot\left(\mathbb{E}\left[\sum_{\phi=1}^{\Phi}\mathbb{E}[\ell^{\prime}_{i_{\phi},\phi}]\right]-\min_{i}\sum_{\phi=1}^{\Phi}\mathbb{E}[\ell^{\prime}_{i,\phi}]\right)$
$\displaystyle=B\cdot\left(\mathbb{E}_{\mathcal{L}^{\prime}}\left[\sum_{\phi=1}^{\Phi}\ell^{\prime}_{i_{\phi},\phi}\right]-\min_{i}\mathbb{E}_{\mathcal{L}^{\prime}}\left[\sum_{\phi=1}^{\Phi}\ell^{\prime}_{i,\phi}\right]\right).$

This expression corresponds exactly to $B$ times the regret of Alg on
$\mathcal{I}^{\prime}$ (see (1)), and thus can be upper bounded by

$\displaystyle
B\cdot\left(\mathbb{E}_{\mathcal{L}^{\prime}}\left[\sum_{\phi=1}^{\Phi}\ell^{\prime}_{i_{\phi},\phi}\right]-\min_{i}\mathbb{E}_{\mathcal{L}^{\prime}}\left[\sum_{\phi=1}^{\Phi}\ell^{\prime}_{i,\phi}\right]\right)$
$\displaystyle\leq B\cdot R_{\textsc{Alg}}(\Phi)$ $\displaystyle\leq B\cdot
R_{\textsc{Alg}}(T/B)$ $\displaystyle\leq\frac{3\ln T}{f^{\star}}\cdot
R_{\textsc{Alg}}\left(\frac{Tf^{\star}}{3\ln T}\right).$

The $\frac{3\ln T}{f^{\star}}$ error term from the last $T-B\Phi$ steps can be
absorbed into this regret term, since
$R_{\textsc{Alg}}\left(\frac{Tf^{\star}}{3\ln T}\right)\geq 1$.

∎

####  C.1.3 Monotonicity of $\text{BB}_{\text{Divide}}$: Proof of Theorem 3.2

Next, we analyze the monotonicity properties of $\text{BB}_{\text{Divide}}$.
For convenience, we restate Theorem 3.2 below.

See 3.2

The intuition for the $\mathtt{APC}$ statement is that since
$\text{BB}_{\text{Divide}}$ effectively treats each block as one round of Alg,
equalizing the block sizes will naturally balance $\mathtt{APC}$. Once Alg
decides to pull an arm $i$, $\text{BB}_{\text{Divide}}(\textsc{Alg})$ will
pull it $B$ times regardless of its feedback probability. This result relies
on $f^{\star}$ being sufficiently small to ensure that there is an observation
in every block. The $\mathtt{FOC}$ statement follows from an application of
Lemma 2.1. We formalize this below.

###### Proof of Theorem 3.2.

We first analyze $\mathtt{APC}$. Let $E$ be the “clean event” that at least
one feedback observation occurs in each block $1\leq\phi\leq\Phi$. By Lemma
C.4, we know that $\mathbb{P}[E]\geq 1-\frac{1}{T^{2}}$. Conditioning on the
clean event $E$, we see that
$\mathtt{APC}_{i}(\mathcal{I})=\mathtt{APC}_{i}(\tilde{\mathcal{I}})$ by the
construction of the algorithm, since in every block where Alg selects $i$,
$\text{BB}_{\text{Divide}}(\textsc{Alg})$ will pull $i$ exactly $B$ times. The
event that $E$ does not occur contributes at most $1/T$ to $\mathtt{APC}$.

We next analyze $\mathtt{FOC}$. From the proof of the $\mathtt{APC}$
statement, we have that
$\mathtt{APC}_{i}(\tilde{\mathcal{I}})\geq\mathtt{APC}_{i}(\mathcal{I})-1/T.$
Applying Lemma 2.1, which states that
$\mathtt{FOC}_{i}=f_{i}\cdot\mathtt{APC}_{i}$, we have

$\mathtt{FOC}_{i}(\tilde{\mathcal{I}})=\tilde{f}_{i}\cdot\mathtt{APC}_{i}(\tilde{\mathcal{I}})\geq\tilde{f}_{i}\cdot\mathtt{APC}_{i}(\mathcal{I})-\tilde{f}_{i}/T=\frac{\tilde{f}_{i}}{f_{i}}\cdot\mathtt{FOC}_{i}(\mathcal{I})-\tilde{f}_{i}/T\geq\mathtt{FOC}_{i}(\mathcal{I})-\tilde{f}_{i}/T,$

where the last inequality is because $\tilde{f}_{i}\geq f_{i}$.

For strict inequality, notice that it suffices to show that
$\frac{\tilde{f}_{i}}{f_{i}}\cdot\mathtt{FOC}_{i}(\mathcal{I})-\frac{\tilde{f}_{i}}{T}>\mathtt{FOC}_{i}(\mathcal{I})$.
As long as Alg pulls $i$ at least once, this will hold for sufficiently large
values of $T$. ∎

###  C.2 Proofs for Section 3.2: $\text{BB}_{\text{Pull}}$

In this section, we provide proofs for the regret and monotonicity of
algorithms transformed by $\text{BB}_{\text{Pull}}$. Before doing so
explicitly, we first introduce a simulated version of
$\text{BB}_{\text{Pull}}$, as well as Lemmas C.5 and C.6, which will help us
compare transformed algorithms on similar instances.

####  C.2.1 Construction of a simulated version of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$

We first introduce Algorithm 8, a simulated version of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$, which will be easier to analyze but
behaves the same way as $\text{BB}_{\text{Pull}}(\textsc{Alg})$. First, let us
define the following random variables. (Recall that $\phi$ indexes losses for
the time horizon of Alg, $\Phi$ is the total number of times Alg is called by
$\text{BB}_{\text{Pull}}(\textsc{Alg})$, and $\Phi\leq T$ because Alg can be
called at most $T$ times.)

  * •

Losses: For each round $\phi\in[\Phi]$ of Alg and each arm $j\in[K]$,
$\ell^{\prime}_{j,\phi}$ is the placeholder for the loss passed to Alg if Alg
were to observed the loss of arm $j$ at time $\Phi.$ More formally,
$\ell^{\prime}_{j,\phi}:=\ell_{j,t}$ the loss for arm $j$ at a time step $t$
that corresponds to the last time step in block $\phi$ of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$. Since we are in the stochastic loss
setting, $\ell^{\prime}_{j,\phi}$ is a random variable drawn from the
distribution of arm $j$ (with mean $\bar{\ell}_{j}$) independently across
$\phi$ and $j$. We note that these losses are only observed up to timestep
$\Phi$ (which is a random variable less than $T$) and only for the specific
arms pulled by the algorithm.

  * •

Feedback realizations: For all $j\in[K]$ and $\phi\in[T]$, let
$Q_{j,\phi}\sim\textrm{Geom}(f_{j})$ for $\phi\in[T]$ be a random variable
distributed according to the geometric distribution with parameter equal to
the feedback probability of arm $j$. This will represent the number of
Bernoulli trials needed to observe a success. (These random variables are also
fully independent across values of $j$ and $\phi$.)

  * •

Algorithm randomness: Let $b$ be randomness of Alg that will be used across
time steps $1\leq\phi\leq T$. Let $\textsc{Alg}_{b}$ denote Alg initialized
with randomness $b$.

We are now ready to present the simulated version of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$, described in Algorithm 8.

Input: A sequence of positive integers $Q_{j,\phi}$ for $\phi\in[T]$ and
$j\in[K]$.

1 Initialize $t=1$ and $\phi=1$.

2 while  _$t\leq T$_ do

3 Let $i^{\textsc{Alg}}_{\phi}=\textsc{Alg}(\phi)$ be the output of Alg at
timestep $\phi$.

4 for  _$\min(T-t,Q_{i^{\textsc{Alg}}_{\phi},\phi})$ iterations_ do

5 Pull $i_{t}\coloneqq i^{\textsc{Alg}}_{\phi}$ and let $t\leftarrow t+1$.

6 if  _$t <T$_ then

7 Observe $\ell_{i_{t},t}$ and return
$\ell^{\prime}_{i^{\textsc{Alg}}_{\phi},\phi}\coloneqq\ell_{i_{t},t}$ to Alg.

8 Let $\phi\leftarrow\phi+1$.

Algorithm 8 Simulated version of $\text{BB}_{\text{Pull}}(\textsc{Alg})$

Note that the random variables $Q_{j_{\phi},\phi}$ actually now capture the
block size of the transformed algorithm $B_{\phi}$ (which, for
$\text{BB}_{\text{Pull}}$, is a random variable). For clarity, we will use $Q$
rather than $B$ in the remaining analyses.

We first argue that, given two instances $\mathcal{I},\tilde{\mathcal{I}}$
which are identical except for $\tilde{f}_{i}\geq f_{i}$, the sequences of
arms that Algorithm 8 pulls are distributed identically across the instances.
We formalize this in the following lemma.

######  Lemma C.5.

Let $Q_{j,\phi}$ and $\widetilde{Q}_{j,\phi}$ for $j\in[K]$ and
$\phi=1,\dots,$ be an infinitely-long sequence of arbitrary positive integers.
Let $\Phi^{*}$ be any positive integer and
$T=\max\\{\sum_{\phi\in[\Phi^{*}]}\sum_{j\in[K]}Q_{j,\phi},\allowbreak\sum_{\phi\in[\Phi^{*}]}\sum_{j\in[K]}\widetilde{Q}_{j,\phi}\\}$
be the time horizon. Let
$\mathcal{I}=\\{\mathcal{A},\mathcal{F},\mathcal{L}\\}$ be a stochastic
instance with time horizon $T$; let $\tilde{f}_{i}\geq f_{i}$ and
$\widetilde{\mathcal{I}}=\\{\mathcal{A},\tilde{\mathcal{F}}(i),\mathcal{L}\\}$.
Run Algorithm 8 with parameters
$\left\\{Q_{j,\phi}\right\\}_{j\in[K],\phi\in[T]}$ on $\mathcal{I}$ and run
Algorithm 8 with parameters
$\left\\{\widetilde{Q}_{j,\phi}\right\\}_{j\in[K],\phi\in[T]}$ on
$\widetilde{\mathcal{I}}$. Let $i^{\textsc{Alg}}_{\phi}$ and
$\tilde{i}^{\textsc{Alg}}_{\phi}$ denote the arms pulled in the description of
Algorithm 8 for the two instances, respectively. Then, the following two
vector valued random variables are identically distributed:
$(i^{\textsc{Alg}}_{1},\dots,i^{\textsc{Alg}}_{\Phi^{*}})$ and
$(\tilde{i}^{\textsc{Alg}}_{1},\dots,\tilde{i}^{\textsc{Alg}}_{\Phi^{*}})$.

The intuitive interpretation of Lemma C.5 is very natural: if we have two set
of arms with identical loss distributions and run
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ on them, we expect to see that the
sequence of arms recommended by Alg is distributed identically across the two
instances, even if we can’t guarantee that the exact same arm is picked at
every timestep on each instance. We provide a formal proof below.

###### Proof of Lemma C.5.

Let $\\{\ell^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$ denote possible
loss sequences observed on $\mathcal{I}$ up to some $\psi\leq\Phi^{*}$ and
$\\{\tilde{\ell}^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$ denote possible
loss sequences observed on $\widetilde{\mathcal{I}}$ up to the same $\psi$.
Let us fix the bit of randomness $b$ used for Alg on $\mathcal{I}$ to be the
same as the bit of randomness used for Alg on $\widetilde{\mathcal{I}}$.
Because of the way we have set
$T=\max\\{\sum_{\phi\in[\Phi^{*}]}\sum_{j\in[K]}Q_{j,\phi},\allowbreak\sum_{\phi\in[\Phi^{*}]}\sum_{j\in[K]}\widetilde{Q}_{j,\phi}\\}$,
we are guaranteed that blocks $\phi=1,\dots,\psi$ will have been reached on
both $\widetilde{\mathcal{I}}$ and $\mathcal{I}$. Conditioned on $b$, let
$F_{b}:[0,1]^{K\times\psi}\to[K]^{\psi}$ be the mapping from all
$\ell^{\prime}_{j,\phi}$ for $\phi\leq\psi$, to the sequence of arms it would
have pulled correspondingly, that is,

$\displaystyle
F_{b}\left(\\{\ell^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}\right)=(i_{1}^{\textsc{Alg}},i_{2}^{\textsc{Alg}},\dots,i_{\psi}^{\textsc{Alg}}).$

Note that $F_{b}$ does not depend on the feedback probabilities $f_{i}$ or the
random variables $Q_{i,\phi}$, because Alg is fully oblivious to these
quantities. For any $b$, $F_{b}$ is fully deterministic. Therefore, the
distribution of
$(i_{1}^{\textsc{Alg}},i_{2}^{\textsc{Alg}},\dots,i_{\psi}^{\textsc{Alg}})$ is
fully specified by the distributions of
$\\{\ell^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$, and the distribution
of
$(\tilde{i}_{1}^{\textsc{Alg}},\tilde{i}_{2}^{\textsc{Alg}},\dots,\tilde{i}_{\psi}^{\textsc{Alg}})$
is fully specified by the distributions of
$\\{\tilde{\ell}^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$.

Since the loss sequences are distributed identically across instances, we have
that

$\displaystyle\\{\ell^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\\{\tilde{\ell}^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$
$\displaystyle\implies
F_{b}\left(\\{\ell^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}\right)$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}F_{b}\left(\\{\tilde{\ell}^{\prime}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}\right)$
$\displaystyle\implies(i_{1}^{\textsc{Alg}},i_{2}^{\textsc{Alg}},\dots,i_{\psi}^{\textsc{Alg}})$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}(\tilde{i}_{1}^{\textsc{Alg}},\tilde{i}_{2}^{\textsc{Alg}},\dots,\tilde{i}_{\psi}^{\textsc{Alg}}),$

where $\stackrel{{\scriptstyle d}}{{=}}$ denotes identically distributed
relationship. Finally, because this holds conditionally over any arbitrary
$b$, we can integrate over all possible random bits $b$ to establish the
claim. ∎

To use Algorithm 8 in our proofs, we need to argue that it makes decisions
that are distributed identically to those of Algorithm 2. We formalize this
below:

######  Lemma C.6 (Distribution of arms pulled by simulated algorithm).

Fix an instance $\mathcal{I}$. Let $\\{i_{t}^{\text{orig}}\\}_{t\in[T]}$ be a
sequence of random variables that represents the arms selected by Algorithm 2
on $\mathcal{I}$ over the time horizon $T$, and
$\\{i_{t}^{\text{sim}}\\}_{t\in[T]}$ be a sequence of random variables that
represents the arms selected by Algorithm 8 on an identical instance
$\mathcal{I}$. Then the sequence $\\{i^{\text{orig}}_{t}\\}_{t\in[T]}$ is
distributed identically to $\\{i^{\text{sim}}_{t}\\}_{t\in[T]}$.

The key difference between Algorithm 8 and Algorithm 2 is that the number of
times Algorithm 8 pulls $i_{\phi}^{\textsc{Alg}}$ is determined by the random
variable $Q_{i_{\phi},\phi}$, rather than by the first time feedback is
observed in Algorithm 2. However, $Q_{i_{\phi},\phi}$ is distributed
identically to the number of times feedback will be observed, so the simulated
version should overall produce the same distribution of outputs. We formalize
this intuition below.

###### Proof of Lemma C.6.

This proof will proceed in three main steps. First, we argue that the sequence
of arms selected by Alg for either Algorithm 8 or Algorithm 2 are identically
distributed. Second, we relate the $X_{j,t}$ used by Algorithm 2 to the $\phi$
timescale. Third, we show by induction that feedback observations are
identically distributed on Algorithm 8 and Algorithm 2. Finally, we argue that
the sequences of arms selected by Algorithm 8 and Algorithm 2 are identically
distributed.

##### Step 1: Coupling arm pulls

$i_{\phi}^{\textsc{Alg},\text{orig}}=i_{\phi}^{\textsc{Alg},\text{sim}}$.

Fix a sequence of random variables $Q_{j,\phi}\sim\text{Geom}(f_{j})$ for
$\phi\in[T]$ and $j\in[K]$ used to run Algorithm 8. Let
$T^{*}=\sum_{\phi\in[T]}\max_{j\in[K]}Q_{j,\phi}$; then fix a sequence of
random variables $X_{j,t}\sim\text{Bern}(f_{j})$ for $t\in[T^{*}]$ and
$j\in[K]$ that determine feedback observations in Algorithm 2.

We run Algorithm 2 and Algorithm 8 on identical copies of $\mathcal{I}$ for
$T^{*}$ rounds; we distinguish each copy by $\mathcal{I}^{\text{orig}}$ for
Algorithm 2 and $\mathcal{I}^{\text{sim}}$ for Algorithm 8. We set $T^{*}$ in
this way to guarantee that timestep $\phi$ will be reached on both
$\mathcal{I}^{\text{orig}}$ and $\mathcal{I}^{\text{sim}}$; we will handle
truncation in the final step.

Recall that Algorithm 2 and Algorithm 8 both make calls to the same underlying
Alg. Let $b$ be the bit of randomness used for Alg in Algorithm 2 and
Algorithm 8. Now, conditioning on $b$, let
$F_{b}:[0,1]^{K\times\psi}\to[K]^{\psi}$ be, as defined before, the mapping
from the sequence of possible losses that Alg may have observed for any arm at
any time $\phi\leq\psi$, to the sequence of arms it would have pulled
corresponding to those losses, that is,

$\displaystyle
F_{b}\left(\\{\ell_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}\right)=(i_{1}^{\textsc{Alg}},i_{2}^{\textsc{Alg}},\dots,i_{\psi}^{\textsc{Alg}}).$

Note that $F_{b}$ does not depend on the feedback probabilities $f_{i}$ or the
feedback observations $Q_{i,\phi}$ or $X_{i,t}$, because Alg is fully
oblivious to these quantities. For any $b$, $F_{b}$ is fully deterministic.
Furthermore, the simulated and real algorithms use Alg with the same bit of
randomness, so $F_{b}^{\text{orig}}=F_{b}^{\text{sim}}$, and the arms selected
by Alg for either Algorithm 2 or Algorithm 8 are fully specified by the
distributions of the losses for each arm. Then, for any $\psi\leq T$, we have
that

$\displaystyle\\{\ell^{\text{orig}}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\\{\ell^{\text{sim}}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}$
$\displaystyle\textit{because
}\mathcal{I}^{\text{orig}}=\mathcal{I}^{\text{sim}}$ $\displaystyle\implies
F_{b}\left(\\{\ell^{\text{orig}}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}\right)$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}F_{b}\left(\\{\ell^{\text{sim}}_{j,\phi}\\}_{j\in[K],\phi\in[\psi]}\right)$
$\displaystyle\textit{because }F_{b}^{\text{orig}}=F_{b}^{\text{sim}}$
$\displaystyle\implies\\{i_{\phi}^{\textsc{Alg},\text{orig}}\\}_{\phi\in[\psi]}$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\\{i_{\phi}^{\textsc{Alg},\text{sim}}\\}_{\phi\in[\psi]}$ by
definition of $F_{b}$.

We end this step by creating a coupling between arms selected by Alg so that
$i_{\phi}^{\textsc{Alg},\text{orig}}=i_{\phi}^{\textsc{Alg},\text{sim}}$ for
all $\phi\in[T]$. For the rest of the analysis, we condition on this
particular sequence.

##### Step 2: Coupling the block lengths.

Define $Q^{\prime}_{\phi}:[K]^{\phi}\times\\{0,1\\}^{K\times
T^{*}}\to\mathbb{N}$ to be the function that maps
$\\{i_{\phi^{\prime}}^{\textsc{Alg},\text{orig}}\\}_{\phi^{\prime}\leq\phi}$,
the sequence of arms selected by Alg up to $\phi$, and the sequence of
Bernoullis $X_{j,t}$ used to run Algorithm 2, to the number of times
$i_{\phi}^{\textsc{Alg},\text{orig}}$ needs to be pulled (on $t$ timescale)
before feedback is observed.161616We note that while Algorithm 2 only takes
$X_{j,t}$ variables into account for arm $j$ that was pulled at time $t$,
these random variables can be defined for all arms at all time steps without
changing the behavior of Algorithm 2. In some abuse of notation, we let
$Q^{\prime}_{\phi}:=Q^{\prime}_{\phi}\left(\\{i_{\phi^{\prime}}^{\textsc{Alg},\text{orig}}\\}_{\phi^{\prime}\leq\phi},\\{X_{j,t}\\}_{j\in[K],t\geq
1}\right)$ be shorthand for the number of times
$i_{\phi}^{\textsc{Alg},\text{orig}}$ must be pulled until a feedback
observation. Now, $Q^{\prime}_{\phi}$ is fully determined by the history of
Alg arm pulls and the sequence of $X_{j,t}$. (Note that $Q^{\prime}_{\phi}$
needs to depend on the $X_{j,t}$’s as well as the history of Alg’s selections.
This is because even if we know $i_{\phi}^{\textsc{Alg}}$, we do not know
which $t$ indices of the $X_{i_{\phi}^{\textsc{Alg}},t}$ sequence determine
whether we make an observation or not. We can only relate $t$ to $\phi$
correctly if we know exactly which arms were pulled in previous
$\phi^{\prime}<\phi$, and their corresponding feedback observations.)

Next, we will show that for all $\phi\in[T]$, conditioned on fixing
$Q^{\prime}_{\psi}$ and $Q_{i_{\psi},\psi}$ such that
$Q_{i_{\psi},\psi}=Q^{\prime}_{\psi}$ for all $\psi<\phi$, it holds that
$Q_{i_{\phi},\phi}\stackrel{{\scriptstyle d}}{{=}}Q^{\prime}_{\phi}$.

Recall that we have fixed a coupling between arms selected by Alg so that
$i_{\phi}^{\textsc{Alg},\text{orig}}=i_{\phi}^{\textsc{Alg},\text{sim}}$ for
all $\phi\in[T]$. For ease of presentation, we refer to these arms as
$i_{\phi}$ simply.

First note that for any $\phi$,
$Q_{i_{\phi},\phi}\sim\text{Geom}(f_{i_{\phi}})$ by definition; furthermore,
these are independent across all $\phi$. To complete our claim, it suffices to
show that $Q^{\prime}_{\phi}\sim\text{Geom}(f_{i_{\phi}})$ conditioned on
fixing $Q^{\prime}_{\psi}$ and $Q_{i_{\psi},\psi}$ such that
$Q_{i_{\psi},\psi}=Q^{\prime}_{\psi}$ for all $\psi<\phi$.

Recall that
$Q^{\prime}_{\phi}:=Q^{\prime}_{\phi}\left(\\{i_{\phi^{\prime}}\\}_{\phi^{\prime}\leq\phi},\\{X_{j,t}\\}_{j\in[K],t\geq
1}\right)$ is the shorthand for the number of times $i_{\phi}$ must be pulled
until a feedback observation. Let $t_{\phi}$ be the first time steps $t$ that
belongs to block $\phi$. Note that $t_{\phi}$ is a deterministic function of
the fixed variables
$\\{Q^{\prime}_{\psi}\\}_{\psi<\phi}=\\{Q_{i_{\psi},\psi}\\}_{\psi<\phi}$.
Furthermore, $X_{i_{\phi},t}$s for $t\geq t_{\phi}$ are independent of
$\\{Q^{\prime}_{\psi}\\}_{\psi<\phi}$ and $Q^{\prime}_{\phi}$ is a function of
$i_{\phi}$ that only depends on $X_{i_{\phi},t}$ for $t\geq t_{\phi}$.
Moreover, $X_{i_{\phi},t}$ for $t\geq t_{\phi}$ are Bernoulli random variables
that are independent of $t_{\phi}$. Therefore,
$Q^{\prime}_{\phi}\sim\text{Geom}(f_{i_{\phi}})$ conditioned on the past. That
is, for all $\phi\in[T]$, it holds that
$Q_{i_{\phi},\phi}\stackrel{{\scriptstyle d}}{{=}}Q^{\prime}_{\phi}$
conditioned on fixing $Q^{\prime}_{\psi}$ and $Q_{i_{\psi},\psi}$ such that
$Q_{i_{\psi},\psi}=Q^{\prime}_{\psi}$ for all $\psi<\phi$.

We end this step by taking an adaptive coupling over the realizations of
$Q^{\prime}_{\psi}$ and $Q_{j},\psi$, such that for all $\phi\in[T]$,
$Q_{i_{\phi},\phi}=Q^{\prime}_{\phi}$.

##### Step 3: Arms selected by Algorithm 2 and Algorithm 8 are identically
distributed.

Finally, we are ready to prove the main claim. Let us condition on the coupled
sequence of arms pulled by Alg from Step 1,
$\\{i_{\phi}^{\textsc{Alg}}\\}_{\phi\in[T]}$, and the coupled feedback
observations
$\left(\\{Q_{i_{\phi},\phi}\\}_{\phi\in[T]},\\{Q^{\prime}_{\phi}\\}_{\phi\in[T]}\right)$
from Step 2.

For Algorithm 2, the random variables $X_{j,t}$ and the sequence
$\\{i_{\phi}^{\textsc{Alg},\text{orig}}\\}_{\phi\in[T]}$ fully specifies the
arms pulled by 2, i.e. the sequence $\\{i_{t}^{\text{orig}}\\}_{t\in[T]}$. For
Algorithm 8, the random variables $X_{j,\phi}$ and the sequence
$\\{i_{\phi}^{\textsc{Alg},\text{sim}}\\}_{\phi\in[T]}$ fully specifies the
arms pulled by 8, i.e. the sequence $\\{i_{t}^{\text{sim}}\\}_{t\in[T]}$.
Conditioned on this coupling
$\left(\\{Q_{j,\phi}\\}_{\phi\in[T]},\\{X_{j,t}\\}_{t\geq 1}\right)$,
therefore, we have that

$\displaystyle\\{i_{\phi}^{\textsc{Alg},\text{orig}}\\}_{\phi\in[\psi]}$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\\{i_{\phi}^{\textsc{Alg},\text{sim}}\\}_{\phi\in[\psi]}$
$\displaystyle\implies\\{i_{t}^{\text{orig}}\\}_{t\in[T]}$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\\{i_{t}^{\text{sim}}\\}_{t\in[T]}$ from conditioning on coupling,

i.e. that the distribution of arms pulled by Algorithm 2 and Algorithm 8 are
identically distributed, conditioned on the coupling. Truncating $\psi$ to $T$
for both algorithms also preserves the identical distribution. The main claim
of the lemma follows by another application of the law of total probability.

∎

####  C.2.2 Regret of $\text{BB}_{\text{Pull}}$: Proof of Theorem 3.3

We prove Theorem 3.3, restated below. See 3.3 The intuition is that in
expectation, the number of times that an arm is pulled in
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ before feedback is observed is at most
$1/\min_{i}f_{i}$. This means that we can upper bound the regret of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ as $1/\min_{i}f_{i}$ times the regret
of Alg.

###### Proof of Theorem 3.3 (Regret of $\text{BB}_{\text{Pull}}$).

Recall that the regret guarantees for $\text{BB}_{\text{Pull}}$ apply only to
stochastic losses. To relate the regret of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ to the regret of Alg, we consider the
outputs of Alg while $\text{BB}_{\text{Pull}}(\textsc{Alg})$ is evaluated.
Recall that $\Phi$ is the number of times that Alg is called. Note that the
simulated version of $\text{BB}_{\text{Pull}}(\textsc{Alg})$, Algorithm 8, is
run with the set of random variables $Q_{j,\phi}$ for $j\in[K]$ and
$\phi\in[T]$, such that $Q_{j,\phi}\sim\mathrm{Geom}(f_{j})$, independently.
Here, $Q_{i_{\phi}^{\textsc{Alg}},\phi}$ denotes the number of times of arm
$i^{\textsc{Alg}}_{\phi}$ is pulled until feedback is observed. Recall that
$\bar{\ell}_{i}$ denotes the mean loss of arm $i$ and let
$i^{*}=\arg\min_{i}\bar{\ell}_{i}$ be the arm with optimal expected loss. The
(pseudo-)regret of $\text{BB}_{\text{Pull}}(\textsc{Alg})$ can be expressed as
follows:

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\bar{\ell}_{i_{t}}\right]-\min_{i}\sum_{t=1}^{T}\bar{\ell}_{i}$
$\displaystyle=\mathbb{E}\left[\sum_{\phi=1}^{\Phi}\sum_{i\in\mathcal{A}}\mathds{1}[i^{\textsc{Alg}}_{\phi}=i]\cdot
Q_{i,\phi}\cdot\left(\bar{\ell}_{i}-\bar{\ell}_{i^{*}}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{\phi=1}^{T}\sum_{i\in\mathcal{A}}\mathds{1}[i^{\textsc{Alg}}_{\phi}=i]\cdot
Q_{i,\phi}\cdot\left(\bar{\ell}_{i}-\bar{\ell}_{i^{*}}\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{\phi=1}^{T}\sum_{i\in\mathcal{A}}\mathds{1}[i^{\textsc{Alg}}_{\phi}=i]\cdot\mathbb{E}[Q_{i,\phi}]\cdot\left(\bar{\ell}_{i}-\bar{\ell}_{i^{*}}\right)\right]$
$\displaystyle\leq\frac{1}{\min_{i}f_{i}}\underbrace{\mathbb{E}\left[\sum_{\phi=1}^{T}\sum_{i\in\mathcal{A}}\mathds{1}[i^{\textsc{Alg}}_{\phi}=i]\cdot\left(\bar{\ell}_{i}-\bar{\ell}_{i^{*}}\right)\right]}_{(1)},$

where the second transition follows by noting that, as described above,
Algorithm 8 is run with well-defined variables $Q_{i,\phi}\geq 0$ for all
$\phi\leq T$ and $\bar{\ell}_{i}-\bar{\ell}_{i^{*}}\geq 0$ for all
$i\in\mathcal{A}$, so that we can extend the summation to $\phi\in(\Phi,T]$.
In the third transition, the outer expectation is over Alg and the inner
expectation is over the feedback observations. And the last transition uses
$\mathbb{E}[Q_{i,\phi}]=\frac{1}{f_{i}}\leq\frac{1}{\min_{i}f_{i}}$.

To relate (1) to the regret of Alg, we observe that in
$\text{BB}_{\text{Pull}}(\textsc{Alg})$, the algorithm Alg also receives
stochastic losses with mean $\bar{\ell}_{i}$ when it pulls
$i_{\phi}^{\textsc{Alg}}=i$ that are identically distributed as in the
original instance $\mathcal{I}$. This means that (1) is exactly equal to the
regret of Alg in an instance with stochastic losses over $T$ time steps. This
completes the proof. ∎

####  C.2.3 Monotonicity of $\text{BB}_{\text{Pull}}$: Proof of Theorem 3.4

Here, we formalize the coupling argument which will allow us to show positive
feedback monotonicity in $\mathtt{FOC}$ and negative feedback monotonicity in
$\mathtt{APC}$ for $\text{BB}_{\text{Pull}}$ applied to an underlying
algorithm Alg. A very similar approach will be used to prove Theorems 3.6,
4.2, and 4.3 in the following sections, though those arguments will require a
slightly more complex conditioning step.

For reference, we restate the result below. See 3.4

We are now ready to proceed with the main coupling argument.

###### Proof of Theorem 3.4 (Monotonicity of $\text{BB}_{\text{Pull}}$)..

Fix an instance
$\mathcal{I}=\left\\{\mathcal{A},\mathcal{F},\mathcal{L}\right\\}$ with
stochastic losses. Let $\tilde{f_{i}}\geq f_{i}$, and let
$\widetilde{\mathcal{I}}=\left\\{\mathcal{A},\mathcal{F}(i),\mathcal{L}\right\\}$.
We will denote the time horizon of the transformed algorithm on $\mathcal{I}$
as $\Phi$, as before, and the time horizon of the transformed algorithm on
$\widetilde{\mathcal{I}}$ as $\widetilde{\Phi}$. We will analyze
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ by comparing the behavior of Algorithm
8 on $\mathcal{I}$ and on $\widetilde{\mathcal{I}}$ in three steps as follows:

  1. 1.

We construct a probability coupling between the sequence of random variables
$Q_{j,\phi}$ and $\widetilde{Q}_{j,\phi}$ for $j\in[K]$ and
$\phi=1,\dots,\infty$. This coupling ensures that
$Q_{i,\phi}\geq\widetilde{Q}_{i,\phi}$ for arm $i$ and
$Q_{j,\phi}=\widetilde{Q}_{j,\phi}$ for all other arms $j\neq i$, for all
$\phi$.171717Constructing an infinitely long sequence is only for convenience
in using Lemma C.5; we only consume at most $T$ of these random variables in
any algorithm for analysis.

  2. 2.

We call Algorithm 8 on $\mathcal{I}$ and $\widetilde{\mathcal{I}}$ with
$Q_{j,\phi}$ and $\widetilde{Q}_{j,\phi}$ for $j\in[K]$ and
$\phi=1,\dots,\infty$, respectively. Using Lemma C.5, we argue that for any
$\Phi^{*}$,
$(i^{\textsc{Alg}}_{1},\dots,i^{\textsc{Alg}}_{\Phi^{*}})\stackrel{{\scriptstyle
d}}{{=}}(\tilde{i}^{\textsc{Alg}}_{1},\dots,\tilde{i}^{\textsc{Alg}}_{\Phi^{*}})$;
then, we couple the arm pulls on each instance so
$(i^{\textsc{Alg}}_{1},\dots,i^{\textsc{Alg}}_{\Phi^{*}})=(\tilde{i}^{\textsc{Alg}}_{1},\dots,\tilde{i}^{\textsc{Alg}}_{\Phi^{*}})$.

  3. 3.

By this step, random variables $Q_{j,\phi}$, $\widetilde{Q}_{j,\phi}$,
$i^{\textsc{Alg}}_{\phi}$, and $\tilde{i}^{\textsc{Alg}}_{\phi}$ are fixed
according to the above coupling. As a final step, we modify step 2 so that
Algorithm 8 terminates after $T$ rounds. In this case, Alg may be called a
different number of times, $\Phi\leq\widetilde{\Phi}$, on instance
$\mathcal{I}$ and $\widetilde{\mathcal{I}}$. We handle this by showing that
this impacts the monotonicity in the claimed direction.

##### Step 1: Coupling realizations of feedback observations.

Note that for $\tilde{f}_{i}>f_{i}$, the distribution of
$\widetilde{Q}_{i,\phi}$ is stochastically dominated by $Q_{i,\phi}$. That is,
as the feedback probability increases, we need fewer pulls to observe feedback
when that arm is pulled. Therefore, there is a joint probability distribution
over $(Q_{j,\phi},\widetilde{Q}_{j,\phi})$ such that for all $\phi$, with
probability $1$ the following hold: $Q_{i,\phi}\geq\widetilde{Q}_{i,\phi}$ and
for all $j\neq i$, $Q_{j,\phi}=\widetilde{Q}_{j,\phi}$. This also gives us a
coupling, that is a joint distribution, over
$\left(\\{Q_{j,\phi}\\}_{j\in[K],\phi\in\\{1,\dots,\infty\\}},\\{\widetilde{Q}_{j,\phi}\\}_{j\in[K],\phi\in\\{1,\dots,\infty\\}}\right)$
that meets the aforementioned property. (See Footnote 17 about dealing with
infinitely long sequences.)

##### Step 2: Coupling arms pulled by Alg across instances $\mathcal{I}$ and
$\widetilde{\mathcal{I}}$.

We next consider Algorithm 8 on two instances $\mathcal{I}$ and
$\widetilde{\mathcal{I}}$ using the coupled sequence of random variables
$Q_{j,\phi}$ and $\widetilde{Q}_{j,\phi}$ for $j\in[K]$ and
$\phi=1,\dots,\infty$, respectively, as coupled in in Step 1. Conditioned on
these sequences, we now apply Lemma C.5. Note that the preconditions of this
lemma are met for any $\Phi^{*}$, so we have that
$(i^{\textsc{Alg}}_{1},\dots,i^{\textsc{Alg}}_{\Phi^{*}})$ and
$(\tilde{i}^{\textsc{Alg}}_{1},\dots,\tilde{i}^{\textsc{Alg}}_{\Phi^{*}})$ are
identically distributed. This allows us to consider a joint probability
distribution over
$(i^{\textsc{Alg}}_{1},\dots,i^{\textsc{Alg}}_{\Phi^{*}},\tilde{i}^{\textsc{Alg}}_{1},\dots,\tilde{i}^{\textsc{Alg}}_{\Phi^{*}})$
such that $i^{\textsc{Alg}}_{\phi}=\tilde{i}^{\textsc{Alg}}_{\phi}$ for all
$\phi\in[\Phi^{*}]$.

Figure 3: Timelines of $\text{BB}_{\text{Pull}}(\textsc{Alg})$ on instances
$\cal I$ (top row) and $\widetilde{\mathcal{I}}$ (bottom row) are
demonstrated. Each time step $t\in[T]$ maps to a block number in $\mathcal{I}$
that is no more than its block number in $\widetilde{\mathcal{I}}$. The total
number of times Alg is called in instance $\mathcal{I}$, $\Phi$, and the
number of times it is called in $\widetilde{\mathcal{I}}$, $\widetilde{\Phi}$,
satisfy $\Phi\leq\widetilde{\Phi}$.

##### Step 3: Handling different stopping times.

We now have random variables $Q_{j,\phi}$, $\widetilde{Q}_{j,\phi}$,
$i^{\textsc{Alg}}_{\phi}$, $\tilde{i}^{\textsc{Alg}}_{\phi}$ are all fixed and
for all $\phi=1,\cdots,\infty$ satisfy
$i^{\textsc{Alg}}_{\phi}=\tilde{i}^{\textsc{Alg}}_{\phi}$,
$Q_{i,\phi}\geq\widetilde{Q}_{i,\phi}$, and
$Q_{j,\phi}=\widetilde{Q}_{j,\phi}$ for $j\neq i$.

We next consider the actual performance of Algorithm 8 on instances
$\mathcal{I}$ and $\widetilde{\mathcal{I}}$ over $T$ timesteps. Note that this
is exactly the same as history of arms played by Algorithm 8 on $\mathcal{I}$
and $\widetilde{\mathcal{I}}$, respectively, in Step 2 of the analysis, except
that the algorithm now terminates at time $T$. Therefore, the number of rounds
Alg is called in each of these two instances may be different. Notice that
$\Phi$ and $\widetilde{\Phi}$ are deterministic variables, since the arms
pulled and the number of rounds until an observation is made are all fixed. It
is not hard to see that $\Phi\leq\widetilde{\Phi}$. This is perhaps best seen
by considering Figure 3. We note that the time horizon of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ for the two instances can be thought
of as two sequence of blocks $[\Phi]$ and $[\widetilde{\Phi}]$. For each
$\phi\leq\min\\{\Phi,\widetilde{\Phi}\\}$,
$i^{\textsc{Alg}}_{\phi}=\tilde{i}^{\textsc{Alg}}_{\phi}$. Therefore, the only
case where
$Q_{i^{\textsc{Alg}}_{\phi},\phi}\neq\widetilde{Q}_{i^{\textsc{Alg}}_{\phi},\phi}$
is when $i^{\textsc{Alg}}_{\phi}=i$; these are shown by gray blocks in Figure
3. In this case
$Q_{i^{\textsc{Alg}}_{\phi},\phi}\geq\widetilde{Q}_{i^{\textsc{Alg}}_{\phi},\phi}$
by the coupling we designed above. In all other blocks, where
$i^{\textsc{Alg}}_{\phi}\neq i$, we have that
$Q_{i^{\textsc{Alg}}_{\phi},\phi}=\widetilde{Q}_{i^{\textsc{Alg}}_{\phi},\phi}$.
Let $\phi(t)$ (resp. $\widetilde{\phi}(t)$) be the function that maps
timesteps on the timescale indexed by $t$ to timesteps on Alg’s timescale on
$\mathcal{I}$ (resp. $\widetilde{\mathcal{I}}$). We can now see that every
time step $t\in[T]$ maps to blocks $\phi(t)$ and $\widetilde{\phi}(t)$ in
instances $\mathcal{I}$ and $\widetilde{\mathcal{I}}$, respectively, such that
$\widetilde{\phi}(t)\geq\phi(t)$. This implies that
$\Phi\leq\widetilde{\Phi}$, because $\phi(T)\leq\widetilde{\phi}(T)$.

##### Notation for Analyzing $\mathtt{FOC}$ and $\mathtt{APC}$.

The remainder of the proof boils down to analyzing $\mathtt{FOC}$ and
$\mathtt{APC}$ on $\mathcal{I}$ and $\tilde{\mathcal{I}}$. We use the coupling
thus far with the property that $Q_{j,\phi}$, $\widetilde{Q}_{j,\phi}$,
$i^{\textsc{Alg}}_{\phi}$, $\tilde{i}^{\textsc{Alg}}_{\phi}$ are all fixed and
for all $\phi=1,\cdots,\infty$ satisfy
$i^{\textsc{Alg}}_{\phi}=\tilde{i}^{\textsc{Alg}}_{\phi}$,
$Q_{i,\phi}\geq\widetilde{Q}_{i,\phi}$, and
$Q_{j,\phi}=\widetilde{Q}_{j,\phi}$ for $j\neq i$. Figure 3 provides an
intuitive proof of the desired claims.

To formalize these claims, we introduce the following additional notation.
Given a range $R\subseteq[T]$, let $\mathtt{FOC}_{i}^{R}(\mathcal{I})$ be the
number of times feedback is observed on arm $i$ in timesteps in $R$ on
$\widetilde{\mathcal{I}}$, and let
$\mathtt{FOC}_{i}^{R}(\widetilde{\mathcal{I}})$ be the number of times
feedback is observed on arm $i$ in timesteps in $R$ on $\tilde{\mathcal{I}}$.
Similarly, let $\mathtt{APC}_{i}^{R}(\mathcal{I})$ be the number of times arm
$i$ is pulled in timesteps in $R$ on $\mathcal{I}$, and let
$\mathtt{APC}_{i}^{R}(\widetilde{\mathcal{I}})$ be the number of times arm $i$
is pulled in timesteps in $R$ on $\widetilde{\mathcal{I}}$. Since we have
conditioned on $Q_{j,\phi}$, $\widetilde{Q}_{j,\phi}$,
$i^{\textsc{Alg}}_{\phi}$, $\tilde{i}^{\textsc{Alg}}_{\phi}$, we see that at
this point $\mathtt{FOC}_{i}^{R}(\mathcal{I})$,
$\mathtt{FOC}_{i}^{R}(\widetilde{\mathcal{I}})$,
$\mathtt{APC}_{i}^{R}(\mathcal{I})$, and
$\mathtt{APC}_{i}^{R}(\widetilde{\mathcal{I}})$ are all deterministic.

Since we will analyze the last time block separately, we let
$T_{1}=\sum_{\phi\in[\Phi-1]}Q_{i^{\textsc{Alg}}_{\phi},\phi}\leq T$ be the
time step referring to the penultimate block of
$\text{BB}_{\text{Pull}}(\textsc{Alg})$ on $\mathcal{I}$. We let $T_{0}$ be
the corresponding time step on instance $\widetilde{\mathcal{I}}$ defined by
$T_{0}=\sum_{\phi\in[\Phi-1]}\widetilde{Q}_{i^{\textsc{Alg}}_{\phi},\phi}$
(note that the expression sums over $\phi\in[\Phi-1]$, and not over
$\phi\in[\tilde{\Phi}-1]$). By definition, it holds that $T_{0}\leq T_{1}$.

##### Analyzing $\mathtt{FOC}$.

We first prove that
$\mathtt{FOC}_{i}^{[T]}(\tilde{\mathcal{I}})-\mathtt{FOC}_{i}^{[T]}(\mathcal{I})\geq
0$. First, we observe that: