Bandits Meet Mechanism Design
to Combat Clickbait in Online Recommendation
Thomas Kleine Buening 1 Aadirupa Saha 2 Christos Dimitrakakis 3 Haifeng Xu 4

Abstract

aspect of the problem that is often ignored. These invite
vendors to exaggerate their true value in the descriptions inorder to increase their Click-Through-Rates (CTRs). As aconsequence, though online learning algorithms can generally identify relevant items, the existence of unrepresentative
or exaggerated item descriptions remains a challenge (Yueet al., 2010; Hofmann et al., 2012). These include thumbnails or headlines that do not truly reflect the underlying item
(see Figure 1)—a well-known internet phenomenon called
the clickbait in the context of articles. While moderately
increasing user click-rates through attractive descriptions
is often encouraged since it helps to increase the overall
user activity, clickbait can be harmful to a platform as itleads to bad recommendation outcomes and damage to theplatform’s reputation which may exceed the value of any
additional clicks it brings. A key reason for such dishonest
or exaggerated item deceptions is the strategic behavior ofvendors driven by their incentive to increase their item’s
exposure and click probability. Thus naturally, vendors are
better off carefully choosing descriptions so as to increase
click-rates, which leads to phenomena such as clickbait.1

We study a strategic variant of the multi-armed
bandit problem, which we coin the strategic clickbandit. This model is motivated by applications
in online recommendation where the choice ofrecommended items depends on both the clickthrough rates and the post-click rewards. Like inclassical bandits, rewards follow a fixed unknown
distribution. However, we assume that the clickthrough rate of each arm is chosen strategically by
the arm (e.g., a host on Airbnb) in order to maximize the number of times it gets clicked. The
algorithm designer does not know the post-click
rewards nor the arms’ actions (i.e., strategicallychosen click-rates) in advance, and must learn
both values over time. To solve this problem,
we design an incentive-aware learning algorithm,
UCB-S, which achieves two goals simultaneously:(a) aligning incentives by incentivizing desirable
arm actions under uncertainty; (b) learning unknown parameters. We approximately characterize all Nash equilibria
among arms under UCB-S√e KT ) regret bound in every equiand show a O(
librium. We also show that incentive-unaware
algorithms generally fail to achieve low regret in
the strategic click-bandit setup.

1. Introduction

To address this issue, we take an approach that marries
mechanism design without payments to online learning,which are two celebrated research areas, however, mostly
studied as separate streams. Since clickbait is fundamentally
driven by vendor incentives, we believe that the novel designof online learning policies that can carefully align vendor
incentives with the platform’s overall objective may help toresolve this issue from its root.

Recommendation platforms act as intermediaries between
vendors and users so as to recommend items from the former to the latter. On Amazon, vendors sell physical items,
while on Youtube the recommended items are videos. The
recommendation problem is how to select one or more items
to present to each user so that they are most likely to clickon at least one of them.

To incorporate vendor-chosen item descriptions in this setting, we propose and study a natural strategic variant of
the classical Multi-Armed Bandit (MAB) problem, which
we call the strategic click-bandit in order to emphasize thestrategic role that clicks and CTRs play in our setup.2 Concretely, in strategic click-bandits, each arm i is characterizedby (a) a reward distribution with mean µi , inherent to the

However, vendor-chosen item descriptions are an essential

1
This is possible because most platforms rely on vendors toprovide descriptions about their items. For instance, the imagesof restaurants on Yelp, rentals on Airbnb, hotels on Expedia, title
and thumbnails of Youtube videos, and descriptions of productson Amazon are all provided by these items’ vendors.
2
We use the terms click-through-rate, click-rate, and click probability interchangeably.

1
University of Oslo 2 Apple ML Research 3 University of
Neuchatel 4 University of Chicago. Correspondence to: Thomas
Kleine Buening <thomkl@ifi.uio.no>.

Interactive Learning with Implicit Human Feedback Workshop at
ICML 2023. Honolulu, Hawaii, USA.

1

Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

Figure 1. Examples of unrepresentative or clickbait headlines and thumbnails on Bing News, Airbnb, Youtube, and Facebook Marketplace(identifying information partly redacted).

arm; and (b) a click probability si ∈ [0, 1], chosen freely by
the arm at the beginning. Since the learner (i.e., the recommendation system) knows neither of these values, it must
learn them through interaction. The learner’s objective isrepresented through a general utility function u(si , µi ) that
depends on both click-rate and post-click rewards.

that incentive-unaware algorithms generally fail toachieve low regret in the strategic click-bandit (Section 3, Proposition 4.2).
2. We design an incentive-aware learning algorithm,
UCB-S, that combines mechanism design and online learning techniques and effectively incentivizes
desirable arm strategies while minimizing regret bymaking credible and justified threats to arms under
uncertainty (Section 5).

The strategic click-bandit proceeds in two phases. In the firstphase, the learner commits to an online learning policy M ,upon which each arm i chooses a description, which results
in a corresponding CTR si ∈ [0, 1]. The second phaseproceeds in rounds. At each round t: (1) the algorithm M
pulls/recommends an arm it based on observed past data;(2) arm it is clicked with probability sit ; (3) if it is clicked,
ct,it = 1, the arm it receives utility 1 (whereas all otherarms i receive utility 0 and ct,i = 0) and the learner observes
a post-click reward drawn from it ’s reward distribution. If
it is not clicked, all arms receive 0 utility and the learnerdoes not observe any post-click rewards. From the learner’s
perspective, both si and µi of each arm are unknown but canbe learned from online bandit feedback — that is, whether
the recommended arm is clicked and, if so, what its realized
reward is.

3. We characterize the Nash equilibria among arms under the UCB-S mechanism
andp show that every arm
e max ∆i , K/T close to the dei’s strategy is O
sired strategy (Theorem 5.2).
√
e KT strong
4. We show that UCB-S achieves O
strategic regret (Theorem 5.3) and complement thiswith an almost matching lower bound on weak strategic regret (Theorem 5.5).

2. Related Work
The MAB problem is a well-studied online learning framework, which can be used to model decision-making under
uncertainty (Lai et al., 1985; Auer, 2002). Since it inherently
involves sequential actions and the exploration-exploitation
trade-off, the MAB framework has been applied to online
recommendations (Li et al., 2010; Zong et al., 2016; Wanget al., 2017) as well as a myriad other domains (Bouneffouf
et al., 2020). While there is a wide spectrum of work concerned with strategic machine learning (e.g., Hardt et al.,2016; Freeman et al., 2020; Zhang and Conitzer, 2021),
we focus on related work that connects online learning(and specifically the MAB formalism) to mechanism design (Nisan and Ronen, 1999).

We highlight two fundamental differences between strategic click-bandits and standard MABs. First, each arm inthe strategic click-bandit is a self-interested agent whose
objective
is to maximize the number of times it gets clickedPT
1
c with ct,i ∼ Bern(si ). This captures the{it =i} t,i
t=1
strategic behavior of many vendors in online recommendations, especially those who are rewarded based on user
clicks (e.g., Youtube (2023)). Second, si ∈ [0, 1] is a freely
chosen action by arm i, rather than a fixed parameter of arm
i. We believe these modeling adjustments more realistically
capture vendor behaviors in real applications. They also leadto intriguing mechanism design questions since the bandit
algorithm not only needs to learn the unknown parameters
si , µi , but also has to carefully align arms’ incentives toavoid undesired arm behavior.

To the best of our knowledge, Braverman et al. (2019) is thefirst to study a strategic variant of the multi-armed bandit
problem. In their model, when an arm is pulled, it receives a
privately observed reward ν and chooses to pass on a portion
x of it to the principal, keeping ν − x for itself. The goalof the principal is then to incentivize arms to share as muchreward with the principal as possible. In contrast to ourwork, the principal must not learn the underlying reward dis-In summary, our contributions are:1. We introduce the strategic click-bandit problem,
which involves strategic arms manipulating clickrates so as to maximize their own utility and show2Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

probability sit . If the arm is clicked, then ct,it = 1 and astochastic reward rt with mean µit , is generated. This mean
µi is fixed for each arm i captures the true value of thisarm. Because we only observe the reward when arm gets
clicked, we call the setting “click-bandits”. We summarize
the interaction in Model 1.

tribution or the arm strategies, but instead design an auction
among arms based on the shared rewards. Feng et al. (2020)and Dong et al. (2022) study the robustness of bandit algorithms to strategic reward manipulations. However, neither
work attempts to align incentives by designing mechanisms,
but instead assume a limited manipulation budget. Shin et al.
(2022) study multi-armed bandits with strategic replicationin which agents can submit several arms with replicas tothe platform. They design an algorithm, which separately
explores the arms submitted by each agent and in doing
so discourages agents from creating additional arms andreplicas.

Model 1 The Strategic Click-Bandit Problem
1: Learner commits to algorithm M (shared with all arms)
2: Arms choose strategies (s1 , . . . , sK ) ∈ [0, 1]K
3: for t = 1, . . . , T do
4:
Algorithm M selects arm it ∈ [K]5:
Arm it is clicked w.p. sit , i.e., ct,it ∼ Bern(sit )6:
if it was clicked (ct,it = 1) then7:
Arm it receives utility 1 from the click
8:
M observes post-click reward rt,it ∈ [0, 1] sampled from a distribution with mean µi

Another line of work studies auction-design in multi-armed
bandit formalisms, often motivated by applications in ad
auctions (Babaioff et al., 2009; Devanur and Kakade, 2009;
Babaioff et al., 2015). In these models, in every round theauctioneer selects one advertiser’s item, which is subsequently clicked or not. Each advertiser has a private valueper-click, which is unknown to the auctioneer, and instead
submits a bid, which may differ from their value-per-click.
The designer’s goal is to incentivize agents to truthfully bid
their value-per-click so as to maximize social welfare by
constructing selection and payment rules. Similarly, Gaoet al. (2021) study an auction-based combinatorial multiarmed bandit with payments, where each arm can misreporta cost for its selection.

The following two assumptions specify the information
available to the learner and the arms.
Assumption 3.1. The learner does not see the arm strategies
s1 , . . . , sK in advance, but only observes whether the arm
is clicked or not in round t. Similarly, the learner does notknow the mean post-click rewards µ1 , . . . , µK in advance,but only observes the realized reward rt,it if it is clicked.
Assumption 3.2. Every arm i ∈ [K] has private knowledgeof their mean post-click reward µi , but knows the maximal
value among all arms (not index) µ∗ := maxi∈[K] µi .

To the best of our knowledge, our work is the first to study
the situation where the arms’ strategies (as well as otherparameters) are initially unobserved, but must be learned
from interaction while simultaneously incentivizing arms
under uncertainty without payments. As a result, whileother work is usually able to precisely incentivize certain
arm strategies, our mechanism design and characterizationof the Nash equilibria are approximate.

3.1. Learner’s Utility
The learner’s utility of selecting an arm i with CTR si andpost-click value µi is denoted as u(si , µi ). One example ofthis utility function is u(s, µ) = sµ. In this case, the learnermonotonically prefers large s and does not care about how
much the click-rate s differs from the post-click value µ.
However, we believe that the learner (e.g., a platform like
Youtube or Airbnb) usually values consistency between the
click-rates and the post-click values of arms. This could be
captured by a penalty term for how much si differs from
µi ; for instance, another natural choice is u(s, µ) = sµ −λ(s − µ)2 for a weight λ > 0. Such non-monotonicity of
the learner’s utility u(si , µi ) in si versus arm i’s monotonic
preference of larger click-rates si forms the fundamental
tension in the strategic click-bandit model and is also thereason that mechanism design is needed. We keep the above
utility functions in mind as running examples, but derive
our results for a general class of functions u satisfying thefollowing regularity assumptions:3. The Strategic Click-Bandit Problem
We consider a natural strategic variant of the classical
MAB, motivated by applications in online recommendation. Unlike classical MABs, strategic click-bandits feature
decentralized interactions with the learner and multiple selfinterested arms. In the following, we will also refer to thisonline learning policy as a mechanism to emphasize its dualrole in learning and incentive design.
Let [K] := {1, . . . , K} denote the set of arms, each being
viewed as a strategic agent. At the beginning, the leaner
commits to a history-dependent arm selection policy M ,which is made public. Then, each arm chooses a strategy
si ∈ [0, 1], which determines the probability of the arm
being clicked (i.e., the CTR) after it is pulled (i.e., after itis recommended by the learner). Then, at each round t, thelearner selects an arm it . The selected arm is clicked with

(A1) u : [0, 1] × [0, 1] → R is L-Lipschitz.
(A2) u∗ (µ) := maxs∈[0,1] u(s, µ) is increasing.
(A3) s∗ (µ) := argmaxs∈[0,1] u(s, µ) is H-Lipschitz.
3Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

the arms. Let Σ denote the set of probability measures over[0, 1]. For a mixed strategy profile σ = (σi , σ−i ) ∈ ΣK ,i.e., a distribution over pure strategies, arm i’s utility under mechanism M is then defined as vi (M, σi , σ−i ) :=Es∼σ [vi (M, si , s−i )].
Definition 3.3 (Nash Equilibrium). We say that σ =(σ1 , . . . , σK ) ∈ ΣK is a Nash equilibrium (NE) undermechanism M if vi (M, σi , σ−i ) ≥ vi (M, σi′ , σ−i ) for alli ∈ [K] and strategies σi′ ∈ Σ.

(A1) bounds the loss of selecting a suboptimal arm. (A2)states that, in the (idealized) situation when the arms choose
CTR s so as to maximize the learner’s utility u, then an
arm with larger post-click rewards µ is preferred. (A3)then ensures that the ideal strategy under a utility functionu, as a function of µ, does not change abruptly w.r.t. µ.
From hereon-out, we work under a general learner’s utility
u satisfying (A1)-(A3).
In the following, the function s∗ (µ) will play a central roleas it describes the arm strategy that maximizes the learner’sutility. As such, the learner will typically try to incentivize
an arm with post-click reward µ to choose s∗ (µ). Finally,
we remark that our analysis straightforwardly generalizes
to the case in which different arms correspond to different
utility functions ui . However, for notational convenience,
we decide to use the same u among arms for the rest of thepaper. Moreover, while we assume that the utility functionu does not depend on the arms’ stochastic reward realization
rt,i , we can equivalently think of u depending on rt,i linearly so that the dependency boils down to the dependence
on µi after taking expectation. Assuming such quasi-linear
utilities is standard in most literature, and is widely known
as the von Neumann–Morgenstern utility assumption in economics.

In other words, σ is a Nash equilibrium if no arm i canincrease its utility by unilaterally deviating to any σi′ . If
a Nash equilibrium σ ∈ ΣK is a pure strategy profiles ∈ [0, 1]K (i.e., each σi is a point distribution supported
on a single action si ), this equilibrium is said to be apure-strategy Nash equilibrium. Let NE(M ) := {σ ∈ΣK : σ is a NE under M } denote the set of all (possibly
mixed) Nash equilibria for the arms under mechanism M .
Following conventions in standard economic analysis, we
assume that arms’ strategies will from a Nash equilibriumin NE(M ).
Remark 3.4 (Existence of Nash Equilibrium). In general,
the arm’s utility function vi (M, si , s−i ) may be discontinuous in the arms’ strategies due to its intricate dependence on
the learning algorithm M . It is well-known that in gameswith discontinuous utility functions, a Nash equilibrium may
not exist (Reny, 1999). Nevertheless, for all algorithms weconsider we will prove the existence of a Nash equilibriumby either explicitly describing the equilibrium or implicitly
proving its existence.

3.2. Arms’ Utility and Nash Equilibria Among Arms
The mean µi of each arm i’s true value is fixed, whereasarm i can freely choose the CTR value si . In the strategic
click-bandit, the objective of eachParm i is to maximize theTnumber of times it gets clicked t=1 1{it =i} ct,i , which
captures the incentives of many vendors on internet platforms, for whom user traffic typically proportionally converts to revenue.3 We now introduce the solution concept
for the game among arms defined by a mechanism M andpost-click rewards µ1 , . . . , µK , often referred to as an equilibrium. Let s−i denote the K − 1 strategies of all arms
except i. Each arm i chooses si to maximize their expected
number of clicks vi (M, si , s−i ), which is a function of theirown action si , the mechanism M as well as all other arms’
actions s−i . Concretely,vi (M, si , s−i ) := EM" TX

1{it =i} ct,i3.3. Strategic Regret
PT
The learner’s goal is to maximize t=1 u(sit , µit ), which
naturally depends on the strategies s1 , . . . , sK . For given
post-click values µ1 , . . . , µK , the maximal utility u(s∗ , µ∗ )is then achieved for µ∗ := maxi∈[K] µi and s∗ := s∗ (µ∗ ),that is, u(s∗ , µ∗ ) = maxi∈[K] maxs∈[0,1] u(s, µi ). Withu(s∗ , µ∗ ) as a benchmark, we then define the strategic regret of a mechanism M under a pure-strategy equilibriums ∈ NE(M ) as
" T
#
X
∗
∗
RT (M, s) := Eu(s , µ ) − u(sit , µit ) . (2)

#
(1)

t=1

t=1

For a mixed-strategy equilibrium σ ∈ NE(M ), we thenaccordingly define the strategic regret as

where the expectation is taken over the mechanism’s decisions and the environment’s randomness. We generally
write s := (s1 , . . . , sK ) to summarise a strategy profile of

RT (M, σ) := Es∼σ [RT (M, s)].
In general, there may exist several Nash equilibria for thearms under a given mechanism M . Then, we can consider
the strong strategic regret of M given by the regret under
the worst-case Nash equilibrium:

3

More generally, different arms i may have a different
value-per-click νi that P
could as well depend on µi so thatvi (M, si , s−i ) = EM [ t 1{it =i} ct,i νi ]. This can easily be
accommodated for by our model and our results readily extend to
this case since each arm’s goal still boils down to maximizing thenumber of clicks.

RT+ (M ) :=4max
σ∈NE(M )RT (M, σ),Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendationor the weak strategic regret given by the regret under themost favorable Nash equilibrium:
RT− (M ) :=min
σ∈NE(M )(ii) Let Oracles,µ be the algorithm with oracle knowledge of µ1 , . . . , µK and s1 , . . . , sK that plays it =argmaxi∈[K] u(si , µi ) in every round t with ties broken in favor of the larger µ.

RT (M, σ).

Naturally, RT+ (M ) ≥ RT− (M ). The regret upper bound of
our proposed algorithm, UCB-S, holds under any Nash equilibrium in NE(UCB-S), thereby bounding strong strategic
regret (Theorem 5.3). On the other hand, the lower bounds
we prove (Proposition 4.2 and Theorem 5.5) hold for weakstrategic regret (and therefore also apply to its strong counterpart).

For every equilibrium σ ∈ NE(Oracles,µ ) of thee , i.e., itsarms, the algorithm suffers regret Ω ∆LT
weak strategic regret is lower bounded ase .
RT− (Oracles,µ ) = Ω ∆LT

Proof Sketch. (i): We show that, under the described algorithm, s = 1 is a strictly dominant strategy for arm i∗ .
This implies that arm i∗ plays si∗ = 1 with probability
one in every Nash equilibrium under the oracle algorithm.
The claimed lower bound then follows from bounding the
instantaneous regret from below using s∗ (µi∗ ) ≤ c.

4. Necessity of Incentive Design: Limitationsof Incentive-Unaware Oracles
We start our analysis of the strategic click-bandit problem by showing that simply finding the arm with thelargest post-click reward, argmaxi µi , or largest utility,
argmaxi u(si , µi ), is insufficient to achieve o(T ) weakstrategic regret. In fact, we find that even with oracle knowledge of µ1 , . . . , µK and s1 , . . . , sK , an algorithm may suffer linear weak strategic regret if it fails to account for thearms’ strategic nature. For such incentive-unaware oracle
algorithms, we show a Ω(T ) lower bound on weak strategic regret for any utility function of the learner that is nottrivial to optimize, that is, when the loss of deviating fromthe maximal utility u(s∗ , µ∗ ) is locally lower bounded by a“reverse Lipschitz” constant formally defined below.

(ii): Let j ∗ ∈ argmaxi̸=i∗ µi . It can be seen that in any Nashequilibrium, arm i∗ will play the largest s ∈ [0, 1] such thatu(s, µi∗ ) ≥ u(sj ∗ , µj ∗ ). We then show that (at least) eithersi∗ = 1 or u(si∗ , µi∗ ) = u(s∗ (µj ∗ ), µj ∗ ). Once again thisallows us to bound the instantaneous regret for every roundfrom below, which yields the claimed lower bound.
Remark 4.3. Interestingly, when the algorithm, Oracles,µ ,from Proposition 4.2 (ii) does not break ties in favor of thelarger µ but instead uniformly at random, it can be shownthat in all but a few problem instances no Nash equilibrium
for the arms exists. However, for any ε > 0 we can explicitly
construct an ε-Nash equilibrium for the arms under whiche ) regret.
the algorithm suffers Ω(∆LT

Definition 4.1 (Locally Reverse Lipschitz). The utility funcetion u is locally reverse L-Lipschitzat (s∗ , µ∗ ) if for alls ∈ [0, 1] and µ ∈ [0, 1]:e |s∗ − s| + |µ∗ − µ| .
|u(s∗ , µ∗ ) − u(s, µ)| ≥ L

5. No-Regret Incentive-Aware Learning:
UCB-S

For the statement of the lower bound, recall the definition of the maximal post-click reward µ∗ := maxi µi and(learner’s) utility-maximizing arm strategy s∗ := s∗ (µ∗ ).
Moreover, let the optimality gaps in terms of post-click
rewards be given by ∆i := µ∗ − µi with minimal gap∆ := mini:∆i >0 ∆i .

The results of Proposition 4.2 suggest that an incentiveunaware learning algorithm that is oblivious to the strategic
nature of the arms will generally fail to achieve low regret. In particular, “unconditional” selection of any arm will
likely result in undesirable Nash equilibria among arms. For
these reasons, we deploy a conceptually simple screening
idea, which threatens arms with elimination when deviatingfrom the desired strategies. The challenge is that the arm
strategies s1 , . . . , sK are unknown to the mechanism aheadof time and must be learned through repeated interaction.

Proposition 4.2. Let µ1 , . . . , µK ∈ [0, 1] with unique i∗ ∈argmaxi∈[K] µi . For any utility function u that is locallyereverse L-Lipschitzat (s∗ , µ∗ ) with s∗ ≤ c for some c ∈[0, 1), the following holds:(i) Let Oracleµ be the algorithm with oracle knowledgeof µ1 , . . . , µK that plays it = argmaxi∈[K] µi in every round t.

Let denote nt (i) be the number of times up to (and including) round t that arm i was selected by the learner, whereas
we let mt (i) denote the number of times post-click rewards
were observed for arm i up to (and including) round t. Let
sbti be the average observed click-rate and µ
bti the averageobserved post-click reward for arm i. We then define theFor every equilibrium σ ∈ NE(Oracleµ ) amongthee , i.e., itsarms, the algorithm suffers regret Ω LT
weak strategic regret is lower bounded ase .
RT− (Oracleµ ) = Ω LT
5

Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

Algorithm 1 UCB with Screeing (UCB-S)
1: initialize: A0 = [K]2: for t = 1, . . . , T do
3:
if At−1 ̸= ∅ then4:
Select it ∈ argmaxi∈At−1 µt−1
i
5:
else
6:
Select it uniformly at random from [K]7:
Arm it is clicked with probability sit , i.e., ct,it ∼ Bern(sit )8:
if it was clicked (ct,it = 1) then9:
Observe post-click reward rt,it ∈ [0, 1]
10:
if stit < minµ∈[µti ,µti ] s∗ (µ) or stit > maxµ∈[µti ,µti ] s∗ (µ) then
t
t
t
t
11:
Ignore arm it in future rounds: At ← At−1 \ {it }optimistic and pessimistic estimates of si and µi as

5.1. Characterizing the Nash Equilibria under UCB-S
We now approximately characterize the Nash equilibria forthe arms under the UCB-S mechanism. In order to prove a
regret upper bound for UCB-S, it will be key to ensure thateach arm i plays a strategy si which is sufficiently close to
the desired strategy s∗ (µi ) (i.e., the strategy that maximizes
the learner’s utility). This is particularly important for armsi∗ with maximal post-click rewards µi∗ = µ∗ . If such armsi∗ deviate substantially from s∗ (µi∗ ), e.g., by a constantamount, the learner would be forced to suffer constant regret
even when selecting arms with maximal post-click rewards.

ss

2 log(T )sti = sbti −,nt (i)s
2 log(T )µti = µbti −,mt (i)

2 log(T )sti = sbti +,nt (i)s
2 log(T ).
µti = µbti +mt (i)

where sti = −∞ and sti = +∞ for nt (i) = 0 and µti =−∞ and µti = +∞ for mt (i) = 0.
In every round, UCB-S selects arms optimistically according
to their post-click rewards and subsequently observes if thearm is clicked, i.e., ct,it , and, if so, a post-click reward rt,it .
However, if an arm’s click-rate si is detected to be different
from the learner’s desired arm strategy s∗ (µi ), the arm iseliminated forever, expressed by the screening rule in line 1:
stit <minµ∈[µti ,µti ]tts∗ (µ)

orstit >

maxµ∈[µti ,µti ]t

In the following, we show that under the UCB-S mechanism
every Nash equilibrium consists of strategies such that thestrategies of arms with maximal post-click
p rewards deviate
e K/T ). We thenfrom the desired strategies by at most O(
also show that for suboptimal arms the difference between
each arm’s strategy si and the desired strategy s∗ (µi ) isgoverned by their optimality gap in terms of post-click rewards, given by ∆i := µ∗ − µi . Recall that H denotes the
Lipschitz constant of s∗ (µ).

s∗ (µ).

t

Theorem 5.2. For all s ∈ supp(σ) with σ ∈ NE(UCB-S)and all i ∈ [K]:s()!
K log(T )∗si = s (µi ) + O H · max ∆i ,.
T s∗ (µi )2The only exception is when all arms have been eliminated.
Then, UCB-S plays them all uniformly for the remaining
rounds. To ensure that the elimination of an arm is credibleand justified with high probability, we use high confidencebounds on si and µi . More precisely, if an arm chooses
si = s∗ (µi ) (as asked), then with probability 1 − 1/T 2 itwill not be eliminated by the screening rule.

In particular, for all arms i∗ ∈ [K] with ∆i∗ = 0:s!
K log(T )∗si∗ = s (µi∗ ) + O H.
T s∗ (µi∗ )2

As a prelude to the analysis of the UCB-S mechanism, we
begin by showing that there always exists a Nash equilibrium among the arms under UCB-S. As mentioned briefly
in Section 3, the existence of a Nash equilibrium among
the arms is not guaranteed under an arbitrary mechanism
due to the arms’ continuous strategy space and possibly
discontinuous utility function.

Proof Sketch. To characterize the strategy profiles in the
support NE(UCB-S), we are going to rely on the best response property of the Nash equilibrium. More precisely, forany s ∈ supp(σ) with σ ∈ NE(UCB-S), arm i’s strategy
si must be a best response to σ−i , i.e., for all s′i ∈ [0, 1]:

Lemma 5.1. For any post-click rewards µ1 , . . . , µK , there
always exists a (possibly mixed) Nash equilibrium for thearms under the UCB-S mechanism.

vi (UCB-S, si , σ−i ) ≥ vi (UCB-S, s′i , σ−i ).
6Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

Recall that arm i’s utility can be written asvi (UCB-S, si , σ−i ) = E(si ,σ−i ) [nT (i)]si . First, weshow that si ≥ s∗ (µi ) based on fundamental properties of
UCB-S and the click-bandit model. We then proceed byestablishing upper and lower bounds on E(si ,σ−i ) [nT (i)]under UCB-S. To this end, let τi be the first round that arm
i is not in the active set At anymore and τ be the first roundthat At is empty (and by convention τi = T and τ = T if
i ∈ AT and AT ̸= ∅, respectively):

In other words, the above regret bound is achieved under
any Nash equilibrium σ ∈ NE(UCB-S).
Proof Sketch. As suggested by the regret bound there are
two sources of regret. Broadly speaking, the first term on
the right hand side of (3) corresponds to the regret UCB-S
suffers due to arms with maximal post-click rewards (i.e.,∆i = 0) deviating from the utility-maximizing strategys∗ (µ∗ ). For such arms
p Theorem 5.2 bounded the deviation
by
a
term
of
order
K/T , thereby leading to the claimed√
KT bound. The second term in (3) corresponds to theregret suffered from playing arms with suboptimal post-click
rewards, i.e., ∆i > 0. Using a standard UCB argument, theLipschitzness of u(s, µ) and s∗ (µ), and again Theorem 5.2
applied to |s∗ (µ∗ ) − si | ≤ |s∗ (µ∗ ) − s∗ (µi )| + O(H∆i ) ≤H∆i + O(H∆i ) yields the claimed upper bound.

τi := min{t ∈ [T ] : i ̸∈ At }, τ := min{t ∈ [T ] : At = ∅}.
We then split E(si ,σ−i ) [nT (i)] into the rounds before τiand after τ . Note that arm i is never played in the rounds
between τi and τ , since it has been eliminated from At , butother arms are still active. However, after round τ arm i isplayed with probability 1/K by UCB-S.
T −τ
E(si ,σ−i ) [nT (i)] = E(si ,σ−i ) [nτi (i)] + E(si ,σ−i ).
K

Similarly, to classical multi-armed bandits we can state aregret bound independent of the instance-dependent quantities ∆i and translate Theorem 5.3 into a minimax-type
guarantee.
Corollary 5.4. The strong strategic regret of UCB-S isbounded as
X LH pRT+ (UCB-S) = O 
KT log(T ) .
s∗ (µi )From the screening rule, we obtain the upper boundE(si ,σ−i ) [nτi (i)] ≤ O

H 2 log(T ) .
si (si − s∗ (µi ))2Moreover, from the fact that si mustbe best response
to

 −τ
1
=O K
σ−i we then also find that E(si ,σ−i ) TK
. Conversely, the UCB-type selection rule implies a lower boundi∈[K]log(T ) ∗T E(si ,σ−i ) [nT (i)] ≥ Ω min{, s (µi ) } .
2
si ∆i
K

Letting smin := mini∈[K] s∗ (µi ), this bound can be further
refined to


LH p
+
RT (UCB-S) = O
KT log(T ) .
smin

As a result, when comparing the upper and lower bound on
E(si ,σ−i ) [nT (i)], any si ∈ supp(σi ) must satisfy





log(T ) ∗T
H 2 log(T )Ω min, s (µi )≤O.
si ∆2iKsi (si − s∗ (µi ))2In other words, the above regret bounds are achieved under
any Nash equilibrium σ ∈ NE(UCB-S).

Rearranging terms then yields the claimed result, where weuse that si ≥ s∗ (µi ) as established earlier.

In Corollary 5.4 we see that there remains a dependence
on the learner’s utility function u and post-click rewardsµi in the form of s∗ (µi ). The intuition for this can be
explained as follows: Suppose that s∗ (µ) is very small.
Now, UCB-S incentivizes arms to choose strategies close tos∗ (µi ), which in turn makes learning about the post-click
rewards more difficult. Hence, the incentivized strategies,
while maximizing u, make learning about the arms’ rewards
harder. However, we want to stress that the utility function
u is chosen at the discretion of the learner and a reasonablechoice of u would, for instance, ensure that the incentivizedclick-rate is always at least s∗ (µ) ≥ 0.1 for all µ.

5.2. Upper Bound on Strong Strategic Regret of UCB-S
With the Nash equilibrium characterization from Theorem 5.2 at our disposal, we are ready to prove a regret upperbound for UCB-S. We show that the strong strategic√regrete KT ,of the UCB-S mechanism is upper bounded by O
that is, for any σ ∈ NE(UCB-S) the bound holds.
Theorem 5.3. Let ∆i := µ∗ − µi and let L and H denotethe Lipschitz constants of u(s, µ) and s∗ (µ), respectively.
The strong strategic regret of UCB-S is bounded as

5.3. Lower Bound on Weak Strategic Regret

RT+ (UCB-S)=O

LH p
LH X log(T )
KT
log(T
)
+
s∗ (µ∗ )s∗ (µi )∆iComplementing our regret analysis, we now show a lower
bound for weak strategic regret in the strategic click-bandit.
By definition, weak strategic regret lower bounds its strong
counterpart so that the shown regret lower bound directly
applies to strong strategic regret as well.

!
.

i:∆i >0(3)
7

Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

References

Theorem 5.5. Let M be any mechanism with NE(M ) ̸= ∅.
There exists a utility function u satisfying (A1)-(A3) and postclick rewards µ1 , . . . , µK such that for all σ ∈ NE(M ):√RT (M, σ) = Ω KT .
√In other words, RT− (M ) = Ω KT .

Peter Auer. Using confidence bounds for exploitationexploration trade-offs. Journal of Machine Learning
Research, 3(Nov):397–422, 2002.
Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs
Slivkins. Characterizing truthful multi-armed bandit
mechanisms. In Proceedings of the 10th ACM conference
on Electronic commerce, pages 79–88, 2009.

Proof Sketch. Consider the utility function u(s, µ). Intuitively, for any low regret mechanism M the Nash equilibrium for the arms will be in (s1 , . . . , sK ) = (1, . . . , 1)
as these strategies maximize the learner’s utility u andare to the advantage of the arms. In this case, the learning problem reduces to a classical multi-armed
bandit and√
we inherit the well-known minimax KT lower bound.
However, it is not directly clear that there exists no bettermechanism that would, for instance, incentivize arm strategies (s1 , . . . , si∗ , . . . , sK ) = (0, . . . , 1, . . . , 0) under whichi∗ = argmaxi µi may become easier to distinguish fromi ̸= i∗ . For this reason, we argue via the arms’ utilities andlower bound the minimal utility a suboptimal arm must receive under any Nash equilibrium. Since this lower bounds
the number of times we play a suboptimal arm, we recover
the claimed lower bound.

Moshe Babaioff, Robert D Kleinberg, and Aleksandrs
Slivkins. Truthful mechanisms with implicit payment
computation. Journal of the ACM (JACM), 62(2):1–37,
2015.
Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey
on applications of multi-armed and contextual bandits.
In 2020 IEEE Congress on Evolutionary Computation(CEC), pages 1–8. IEEE, 2020.
Mark Braverman, Jieming Mao, Jon Schneider, andS Matthew Weinberg. Multi-armed bandit problems withstrategic arms. In Conference on Learning Theory, pages
383–416. PMLR, 2019.
Nikhil R Devanur and Sham M Kakade. The price of truthfulness for pay-per-click auctions. In Proceedings of the10th ACM conference on Electronic commerce, pages
99–106, 2009.

6. Discussion
We study the strategic click-bandit problem in which eacharm is associated with a click-rate, chosen strategically by
the arms, and a more sparsely observed and immutable postclick reward. We show the necessity of incentive design inthis model and design an incentive-aware online learningalgorithm that incentivizes desirable arm strategies under
uncertainty. As the learner has no prior knowledge of thearm strategies and the post-click rewards, the mechanism
design is approximate and leaves room for arms to exploit
the learner’s uncertainty. This leads to an interesting regret bound which makes the intuition precise that arms can
exploit the learner’s uncertainty about their strategies.

Jing Dong, Ke Li, Shuai Li, and Baoxiang Wang. Combinatorial bandits under strategic manipulations. In Proceedings of the Fifteenth ACM International Conference on
Web Search and Data Mining, pages 219–229, 2022.
Zhe Feng, David Parkes, and Haifeng Xu. The intrinsic
robustness of stochastic bandits to strategic manipulation.
In International Conference on Machine Learning, pages
3092–3101. PMLR, 2020.
Rupert Freeman, David M Pennock, Chara Podimata, andJennifer Wortman Vaughan. No-regret and incentivecompatible prediction with expert advice. arXiv preprint
arXiv:2002.08837, 2020.

A natural extension to the studied setting would be to assume that CTRs are user-dependent or more generally dependent on contextual information. Another direction would
be to consider multi-slot recommendations in which thelearner selects a subset of arms every round and the selectedarms compete for the click (and our observations are hence
preference-based). In fact, the case where the learner selects
a set of arms and each arm i is clicked with probability si
independently of the other arms can be handled with exactly
the same methods as presented in this paper. In the current
setup, it would also be appealing to construct online learning
mechanisms under which there exists a Nash equilibriumin dominant strategies with similarly benign properties asshown in this paper.

Guoju Gao, He Huang, Mingjun Xiao, Jie Wu, Yu-E Sun,and Sheng Zhang. Auction-based combinatorial multiarmed bandit mechanisms with strategic arms. In IEEE
INFOCOM 2021-IEEE Conference on Computer Communications, pages 1–10. IEEE, 2021.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou,
and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations intheoretical computer science, pages 111–122, 2016.
8

Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

Katja Hofmann, Fritz Behr, and Filip Radlinski. On caption
bias in interleaving experiments. In Proceedings of the
21st ACM international conference on Information andknowledge management, pages 115–124, 2012.
Tze Leung Lai, Herbert Robbins, et al. Asymptoticallyefficient adaptive allocation rules. Advances in appliedmathematics, 6(1):4–22, 1985.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire.
A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661–670,
2010.
Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129–140, 1999.
Philip J Reny. On the existence of pure and mixed strategy
nash equilibria in discontinuous games. Econometrica,
67(5):1029–1056, 1999.
Suho Shin, Seungjoon Lee, and Jungseul Ok. Multi-armed
bandit algorithm against strategic replication. In International Conference on Artificial Intelligence and Statistics,
pages 403–431. PMLR, 2022.
Huazheng Wang, Qingyun Wu, and Hongning Wang. Factorization bandits for interactive recommendation. In
Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Youtube. How to earn money on YouTube, 2023.
Yisong Yue, Rajan Patel, and Hein Roehrig. Beyond position bias: Examining result attractiveness as a source ofpresentation bias in clickthrough data. In Proceedingsof the 19th international conference on World wide web,pages 1011–1018, 2010.
Hanrui Zhang and Vincent Conitzer. Incentive-aware paclearning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5797–5804, 2021.
Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng
Wen, and Branislav Kveton. Cascading bandits forlarge-scale recommendation problems. arXiv preprint
arXiv:1603.05359, 2016.

9