Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation
Authors: Thomas Kleine Buening
Aadirupa Saha
Christos Dimitrakakis
Haifeng Xu
Venue: ICLR 2024 spotlight (2024)
Keywords: bandits
mechanism design
incentive-aware learning
nash equilibrium
Primary area: learning theory
TL;DR: We introduce the strategic click-bandit problem and design an incentive-aware learning algorithm that induces desirable arm strategies while simultaneously minimizing regret.

Abstract: We study a strategic variant of the multi-armed bandit problem, which we coin the strategic click-bandit. This model is motivated by applications in online recommendation where the choice of recommended items depends on both the click-through rates and the post-click rewards. Like in classical bandits, rewards follow a fixed unknown distribution. However, we assume that the click-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., strategically chosen 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) incentivizing desirable arm behavior under uncertainty; (b) minimizing regret by learning unknown parameters.  We approximately characterize all Nash equilibria of the arms under UCB-S and show a $\tilde{\mathcal{O}} (\sqrt{KT})$ regret bound uniformly in every equilibrium. We also show that incentive-unaware algorithms generally fail to achieve low regret in the strategic click-bandit. Finally, we support our theoretical results by simulations of strategic arm behavior which confirm the effectiveness and robustness of our proposed incentive design.

Published as a conference paper at ICLR 2024
BANDITS MEET MECHANISM DESIGN TO COMBAT CLICKBAIT IN ONLINE RECOMMENDATION
Thomas Kleine Buening', Aadirupa Saha" Christos Dimitrakakis", Haifeng Xu² The Alan Turing Institute, 2TTIC, Uniivesityy of Neuchatel, UUniversity of Chicago
ABSTRACT
We study strategic variant of the multi-arme' bandit problem, which coin the strategic click-bandir. This model is motivated by applications in online rec- ommendation where the choice of recommended items depends on both the click- through rates and the post-click rewards. Like in classical bandits, rewards follow fixed unknown distribution. However, we assume that the click-rate of each arm is chosen strategically by the arm (e.g.. host on Airbnb) in order to maximize the number of times gets clicked. The algorithm designer does not know the post-click rewards nor the arms' actions (i.e., strategically chosen click-rates) in advance, and must learn both values over time. To solve this problem, we design incentive-aware learning algorithm, UCB-S, which achieves two goals simul- taneously: (a) incentivizing desirable arm behavior under uncertainty; (b) mini- mizing regret by learning unknown parameters. We approximately characterize all Nash equilibria of the arms under UCB-S and show a ((VKT) regret bound uniformly in every equilibrium. We also show that incentive-unaware algorithms generally fail to achieve low regret in the strategic click-bandin Finally, we sup- port our thcoretical results by simulations of strategic arm behavior which confirm the effectiveness and robustness of our proposed incentive design.
INTRODUCTION
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 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 click on at least one of them.
However, vendor-chosen item descriptions are an essential aspect of the problem that is often ig- nored. These invite vendors exaggerate their true value in the descriptions in order increase their Brock-Trrough-aa Rates (CTRs). As consequence, even though online learning algorithms can generally identify relevant items. the existence of unrepresentative or exaggerated item descriptions remains a challenge Yue et al. 2010; Hofmann et al. 2012). These include thumbnails or headlines that do not truly reflect the underlying item (see Figure [ - well-known internet phenomenon called the clickbait (Wang et al. [022]. While moderately increasing user click-rates through attrac- tive descriptions is often encouraged since it helps to increase the overall user activity, clickbait can be harmful platform as it leads to bad recommendation outcomes and damage the platform's 's reputation which may exceed the value of any additional clicks. A key reason for such dishonest or exaggerated item deceptions is the strategic behavior of vendors driven by their incentive to increase their item's 's exposure and click probability. Thus naturally, vendors are better off carefully choosing descriptions as to increase click-rates, which leads to phenomena such clickbait [
To address this issue, we take an approach that marries mechanism design without payments with on- line 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 design of on- line learning policies that can carefully align vendor incentives with the platform' overall objective may help to resolve this issue from its root.
Author currently with Apple MI. Research.
'This is possible because most platforms rely on vendors to provide descriptions about their items. For instance, the images of restaurants Yelp, rentals Airbnb, hotels on Expedia, title and thumbnails of Youtube videos, and descriptions of products on Amazon all provided by the vendors.

---

Published as a conference paper at ICLR 2024
ANVIL
2013
THIS LOWN TRAICH
Tha
Figure 1: Examples of unrepresentative or clickbait headlines and thumbnails on Bing News, Airbnb, Youtube, and Facebook Marketplace (identifying information partly redacted).
To incorporate vendor-chosen item descriptions in this setting, propose and study natural strate- gic variant of the classical aumti Bandit (MAB) problem, which we call the strategic click- bandit in order to emphasize the strategic role that clicks and CTRs play in setup Concretely, in strategic Blickbbandin
each arm is characterized by (a) a reward distribution with mean 144 inherent to the arm; and (b) a click probability E [o, 1]. chosen freely by the arm at the beginning. Since the learner (i.e., the recommendation system) knows neither of these values in advance, it must learn them through interaction. The learner's objective is represented through a general utility function u(s;
s (4) that depends on both click-rate and post-click rewards.
We highlight two fundamental differences between strategic click-bandits and standard MABs. First, each arm in the strategic click-bandit is self-interested agent whose objective is to maximize the number of times gets clicked. This captures the strategic behavior of many vendors in online recommendations, especially those who are rewarded based on user clicks (e.g., Youtube (2023). Second, s; freely chosen action by arm i, rather than fixed parameter of arm We believe these modeling adjustments more realistically capture vendor behaviors in real applications. They also lead to intriguing mechanism design questions since the bandit algorithm not only needs to learn the unknown parameters, but also has to carefully align incentives avoid undesired arm behavior. In summary, our contributions are:
1. We introduce the strategic click-bandit problem, which involves strategic arms manipulating click-rates so as to maximize their own utility, and show that pncentive-unawand algorithms generally fail to achieve low regret in the strategic
(Section 3
Proposition 4.1)
2. We design incentive-aware learning algorithm, UCB-S, that combines mechanism design and online learning techniques and effectively incentivizes desirable arm strategies while min- imizing regret by making credible and justified threats
under uncertainty (Section (5)
3. We characterize the set of Nash equilibria for the arms under the UCB-S mechanism and show that every arm i's strategy is Ó max (A, / /K/T)) close to the desired strategy in cquilibrium (Theorem [.2). We then show that UCB-S achieves (VVKT) strong strategic regret (Theorem 5.3) and complement this with an almost matching lower bound of 52 /KT) for weak strategic regret (Theorem (.5).
We simulate strategic arm behavior through repeated interaction and gradient ascent and em- pirically demonstrate the effectiveness of the proposed UCB-S mechanism (Section 6).
RELATED WORK
The MAB problem is a well-studied online learning framework. which can be used model decision-making under uncertainty (Lai et al.] 1985 Auer 2002). Since it inherently involves se- quential actions and the xxplration-eexlooiaaion trade-off, the MAB framework has been applied to online recommendations (Li et al.] 2010) Zong et al. 2016 Wang et al., 2017) well as myriad of other domains (Bouneffouf et al. (020). While there is much work studying strategic machine learning (e.g.. Hardt et al.) 2016 Freeman et al. 2020 Zhang and Conitzer, 2021), we here wish to highlight related work that connects online learning (and specifically the MAB formalism) to mechanism design (Nisan and Ronen 1999). Additional related work is discussed in Appendix H
To the best of our knowledge, Braverman et al. (2019) are the first to study a strategic variant of is pulled, it receives privately observed reward
the MAB problem. In their model, when v and chooses to pass on portion x of it to the principal, keeping v - x for itself. The goal of
We use the terms click-throug--rate, click-rate, and click probability interchangeably.
2

---

Published as a conference paper at ICLR 2024
Model 1: The Strategic Click-Bandi Problem
Learner commits to algorithm M, which is shared with all arms Arms choose strategies (81,...,8kk) 8k) E [0, 1] (unknown to M) for t = I...., do
Algorithm M selects arm in [K] Arm is clicked with probability 8i, i.e., Cr., Bern(s;,)
if é was clicked (Ct,i, = 1) then
7
Arm is receives utility 1 from the click
M observes post-click reward Tr, drawn from distribution with mean pi,
the principal then to incentivize arms to share as much reward with the principal as possible. In contrast to our work, the principal must not learn the underlying reward distribution 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 limited manipulation budget. [Shin et al. (022) study MABs with strategic replication in which agents can submit several arms with replicas to the platform. They design an algorithm, which sep- arately explores the arms submitted by each agent and in doing so discourages agents from creating additional arms and replicas. Another line of work studies auction-design in MAB formalisms, often motivated by applications in ad auctions (Babaioff al.) 2009; Devanur and Kakade 2009; Babaioff et al. 2015). In these models, in every round the auctioneer selects one ad vertiser''s item, which is subsequently clicked not, and the goal of the auctioneer is to incentivize advertisers to truthfully bid their value-per-click by constructing selection and payment rules.
To the best of our knowledge, our work the first to study the situation where the arms' strate- gies (as well as other parameters) are initially unobserved, and must be learned from interaction while simultaneously incentivizing arms under uncertainty without payments. As a result, while other work is usually able to precisely incentivize certain arm strategies, our mechanism design and characterization of the Nash equilibria are approximate.
THE STRATEGIC CLICK-BANDIA PROBLEM
We consider 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 self-interested arms.
Let [K] := (1...., K} denote the set of arms, each being viewed as strategic agent. The strategic blick-bandit proceeds two phases. In the first phase, the learner commits to an online learning policy M, upon which each arm i chooses a description, which results in corresponding click- rate 8, E [0, 1]. The second phase proceeds rounds. pulls/recommends
each round t: (I) the algorithm M arm & based observed past data; (2) arm i, is clicked with probability s4i (3) if is clicked, arm i, receives utility (whereas all other arms receive utility 0) and the learner observes post-click reward rr,ú, [0, drawn from i, 's reward distribution with mean f4i [0, 1). If 4 is not clicked, all arms receive 0 utility and the learner does not observe any post-click rewards. The post-click mean μı fixed for each arm and captures the true value of the arm. From the learner's perspective, both s; and μ4; of each arm are unknown but can be learned from online bandit feedback, that is, whether the recommended arm is clicked and, if so, what its realized reward is. In the following, we will also refer to the online learning policy M as a mechanism to emphasize its dual role in learning and incentive design. We summarize the interaction in Model T
3.1 LEARNER'S UTILITY
The learner's utility of selecting an arm i with CTR and post-click value μ4 is denoted u(s;, 14).. One example of this utility function u(s, (4) = sj. In this case, the learner monotonically prefers large and does not about how much the click-rate differs from the post-click value μ. How- ever, 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 penalty term
3

---

Published as a conference paper at ICLR 2024
for how much 8; differs from p4; for instance, natural choice is u(s, su X(s 24) weight À > O. Such non-monotonicity of the learner's ' utility u(s,, (4:) in s; versus arm i's monotonic preference of larger click-rates forms the fundamental tension in the strategic click-bandit model and is also the reason that mechanism design is needed. We keep the above utility functions in mind as running examples, but derive our results for much more general class of functions satisfying the following mild regularity assumptions:
2 for some
(AI) u: [0, 1] x [0, 1] + R is L-Lipschitz w.r.t. the nnorr.
(A2) u² (1) == (0.1) u( p4) is monotonically increasing.
(A3) s" s*(4) == arj.a u(s, μ1) is H H-Lipschitz and is bounded away from zero.
Assumption J bounds the loss of selecting a suboptimal arm. [A2) states that, in the (idealized)
situation when the arms choose click-rates as to maximize the learner's utility u, then arms with larger post-click rewards le are always preferred. [A3) then ensures that from the perspective of the learner most desired strategy s" s*()) does not change abruptly w.r.t. je and the learner wishes
to incentivize non-zero click-rates. In what follows, the function s s*(x) will play a central role as it describes the arm strategy that maximizes the learner's utility. For instance, in the case of u(s, μ1) = sp A(s - u)² it is given by s" (n) = (1+ 22 22),. As such, the learner will typically try to incentivize an arm with post-click reward fu; to choose strategy 8" (1s)..
3.2 ARMS' UTILITY AND NASH EQUILIBRIA AMONG ARMS
The mean post-click reward μ4 of each arm i fixed, whereas arm can freely choose the CTR s;- In the strategic click-bandit, the objective of each arm i is to maximize the number of times it gets clicked - 1 (s,=1) Ct.s, which captures the objectives of vendors on internet platforms for whom user traffic typically proportionally converts to revenue F We now introduce the solution concept for the game among arms defined by a mechanism M and post-click rewards ........K. often referred to
equilibrium. Let s-s denote the K 1 strategies of all arms except Each arm i chooses 8t to maximize their expected number of clicks v; (M, 8;, 8-;), which is a function of the mechanism M, their own action 8; well as all other arms' actions s-s- Concretely,
0e (M, 81, 8-1) = EMM Σ (G=))) Ctai
where the expectation is taken over the mechanism's 's decisions and the environment's randomness.
to summarize a strategy profile of the arms. Let Σ denote the set of probability measures over [0. 1]. Given a mixed strategy profile a
We generally write == (81, (81,..., .8k)
r-;) E Σ" i.e., distribution over [o, _j arm i's utility is then defined as (;M o,, o-1) = Eg [v. (M, $4, s)].
Definition 3.1 (Nash Equilibrium). We say that a = (aI...., σk) E ΣK is a Nash equilibrium (NE) under mechanism M if (,MM oi, oi:) 2 veMMo o-s) for all i E [K] and strategies of Σ.
In other words, or is in NE if no arm can increase its utility by unilaterally deviating to some other strategy. If some NE a E Σ has weight one on a pure strategy profile s E [0, 1| this equilibrium said to be pure-strategies. Let (E(M) == {a E ' a a NE under M) denote the set of all (possibly mixed) NE under mechanism M. Following conventions in standard economic analysis, we assume that the arms will form a NE in NE(M) in response to an algorithm M 0
Remark 3.1 (Existence of Nash Equilibrium). In general, the arms' utility functions (M, 8;, s-)) may be discontinuous in the arms' strategies due to their intricate dependence on the learning algorithm M. It is well-known that in games with discontinuous utilities, a NE may not exist (Reny 1999.. However, for all subsequently considered algorithms we will prove the existence of a NE by either explicitly describing the equilibrium or implicitly proving its existence.
"More generally, difffernnt arms i may have different value-per clicc is that could well depend μs so that (M,, (1; 8-)) = Rys |>> 1 (se=s) Ct.s 2/1. This can easily he accommodated for by our model and results readily extend to this case since each arm's 's goal still boils down to maximizing the number of clicks. "For instance, sufficient condition for the arms to find a NE is their knowledge about how far away they from the best arm, i.c., their optimality gap in post-click rewards A, == max P4 p4-
4

---

Published as a conference paper at ICLR 2024
3.3 STRATEGIC REGRET
The learner's goal is to maximize Et=l M(, which naturally depends on the arm strategies $1...., S.. For given post-click values P1.... PI..... PK, the maximal utility u(s" f²)) ) then achieved for μ²= == max4e[K] [4; and 8" := s" (n²) ), that is, u(s" ,²) max4e[K] max.e|o,1) u(8,)t). With u(s", as a benchmark, we can define the strategic regret of a mechanism M under a pure-strategy equilibrium s E NE(M) as
T Rr 8) = E Σ u(s" 11""","") ul u(88
For some mixed-strategy equilibrium a NE(M), we then accordingly define strategic regret as (r(M, o) == Bero ( (M, s)]. In general, there may exist several Nash equilibria for the arms under given mechanism M. We can then consider the strong strategic regret of M given by the regret under the worst-case equilibrium:
(M,, (M) CENE(M)
or the weak strategic regret given by the regret under the most favorable equilibrium:
(M)
min GENE(M)
RT(M,
where (M) S (M). The regret upper bound of our proposed algorithm, UCB-S, holds under any equilibrium in NE(UCB-S), thereby bounding strong strategic regret (Theorem [5.3). On the other hand, the proven lower bounds (Proposition and Theorem 5.5) hold for weak strategic regret and thus also apply to its strong counterpart.
LIMITATIONS OF INCENTIVE-UNAWARE ALGORITHMS
We start our analysis of the strategic click-bandit problem by showing that simply finding the arm with the largest post-click reward, argmax; μ4 largest utility, argmax, u(s,, (4), is insufficient to achieve (T) weak strategic regret. In fact, we find that even with oracle knowledge of ,.,,..., MK and $1;---; SK. algorithm may suffer linear weak strategic regret if it fails to account for the arms' strategic nature. For such incentive-unaveen oracle algorithms, we show a (?T) lower bound for weak strategic regret on any non-trivial problem instance.
Recall that μ² = max;e[K] and s* = s* (x(²) and suppose that the arm i = argmax, K] Pi with maximal post-elick rewards is unique. Our negative results rely on the following problem- dependent gaps in terms of utility:
8 uss" ,1" u(1, and n u(s" ,('
max u" (p:)).
(E(K]((s')
Here, 3 denotes the cost of the optimal arm i' deviating from the desired strategy s* = *n²) by playing s,, The quantity 77 denotes the gap between the maximally achievable utility u(s", p²) and the utility of the second best arm.
Proposition 4.1. Let p-Oracle be the algorithm with oracle knowledge of ,i...., UK that plays = argmax μl in every round I, whereas (s, -r)-rlcle is the algorithm with oracle knowledge of pr...., ........... PbK and $1,...,88, that always plays i [K p4) with fies broken in favor of the larger We then have
(i) Under every equilibrium o E NE(p-Oracle), the p-Oracle suffers regret Q(3T), i.e.
(1((--racle) = =((td)
(i) Under every or ())(Oll))) the (s, pr-Oracle suffers regret Di min( B,n)T), i.e. (,,((, (1)ss,))-naa (r)-cccle) 52( minn8Bn)T))

---

Published as a conference paper at ICLR 2024
Mechanism 1: UCB with Screening (UCB-S)
initialize: Ag [K]
for t 1,.... do
A + then
Select i, ae 14-1
else
Select i uniformly at random from [K]
Arm in is clicked with probability 8 i..., Ce.b Bern(st.) if it was clicked (c,,i. 1) then
Observe post-click reward re,ic
if % < min wi,1 (²) or st. max s (1) then
Ignore arm in future rounds: A + A \ (ie)
Proof Sketch. (i): We show that 1 is strictly dominant strategy for arm i" under the --Oraele. This implies that arm i* plays = with probability one in every NE under the μ-Oracle. The claimed lower bound then follows from bounding the instantaneous regret per round from below by B. (ii): Let j E argmax;41 p4-- It can be seen that in any NE, arm i" will play the largest E [0, 1] such that u(s, p4=)) 2 u(sy", ((-)) We then show that either = 1 or u(s;,, p.-) = u(s" (ug-) p. Once again this allows us lower bound the regret per round by min m) O
As concrete example of the failure of the μr- j--Olell and the (s, Oracle,,,,,,, let consider the running example of u(s, μ)) 8p A(s - -1)2. In this case, letting X = 5 and μo- = 0.8 and < 0.7 for i it, we get 0.1 and v 0.1 that both oracles suffer (2())) regret in every equilibrium.
5 NO-REGRET INCENTIVE-AWAN LEARNING: UCB-S
The results of Proposition 4.1 suggest that any incentive-unaware learning algorithm that is oblivious the strategic nature of the arms will generally fail achieve low regret. particular, "uncon- ditional" selection of any arm will likely result in undesirable equilibria among arms. For these reasons, we deploy conceptually simple screening idea, which threatens arms with elimination when deviating from the desired strategies.
Let denote (i) the number of times up to (and including) round that arm was selected by the learner, and let m²(i) denote the number of times post-click rewards were observed for arm i up to (and including) round Let 3 be the average observed click-rate and ø the average observed post-click reward for arm i. We then define the pessimistic and optimistic estimates of and μ4 as
8 3 (2log(T)/nn()
$ = + (2log(T)//n(())
c 14 / log(()) (T))
a = P + 2 log(T) ())m
where of = -o and 5 to for ne 0 as well as , = &o and / +oo for mi) 0.
In every round, UCB-S (Mechanism 1 selects arms optimistically according to their post-click rewards and subsequently observes the arm clicked, i.e., Ct.i, and, so, a post-click reward Tri However, if an arm's click-rate is detected to be different from the learner's desired arm strategy (u,), the arm is eliminated forever, expressed by the screening rule line 10
min (E(
8 (1)) Or m..)
max 8" (p).
ne(ei, M
The 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 credible and justified with high probability, we leverage confidence bounds on s; and μą. More precisely, an arm is truthful and chooses 8; (J4z), then with probability 1 1/7a it will not be eliminated by the screening rule.

---

Published as a conference paper at ICLR 2024
As prelude the analysis of the UCB-S mechanism, we begin by showing that there always exists a NE among the arms under UCB-S. As mentioned briefly in Section the existence a NE among the arms is not guaranteed under arbitrary mechanism due to the arms' continuous strategy space and possibly discontinuous utility function.
Lemma 5.1. For any post-click rewards (,,,..., p.k, there always exists a (possibly mixed) Nash equilibrium for the arms under the UCB-S mechanism.
5.1 CHARACTERIZING THE NASH EQUILIBRIA UNDER UCB-S
We now approximately characterize all NE for the arms under the UCB-S mechanism. In order prove a regret upper bound for UCB-S, it will be key ensure that each 8, which is sufficiently close to the desired strategy s" s*(4) (i.c., the strategy that maximizes the learner's utility). This is particularly important for arms i" with maximal post-click rewards μ4. maxie[K] 14: If such arms i" were to deviate substantially from s (1:=) ). e.g., by a constant amount, the learner would be forced suffer constant regret even when selecting arms with maximal post- click rewards, making it impossible to achieve sublinear regret.
plays strategy
In the following, we show that under the UCB-$ mechanism every NE such that the strategies of arms with maximal post-click rewards deviate from the desired strategies by at most O(v K/T).. We then also show that for suboptimal arms the difference between each arm i's strategy 8 and the desired strategy s* (p,) is governed by their optimality gap in post-click rewards, given by A, μ² pt. Recall that H denotes the Lipschitz constant of s* (u).
Theorem 5.2. For all E supp(a) with a E NE((UBBS) and all i [K]:
8; s'(( H max {
))
K log(T)
A..
T
In parficular, for all arms 1" E [K] with A,- 0, i.e,, maximal post-click rewards:
K Klog(T)
8,, = ((x +
H
T
The derivation of Theorem 5.2 can be best understood by noting that the estimates of each arm's strategy roughly concentrate at a rate 1/ Vt. Then, depending on how often an arm expects be selected by U,B-S, it can exploit our uncertainty about its strategy and safely increase its click-rates to match our confidence. Generally, optimal arms expect least T/K allocations while preventing elimination, which can be seen to imply NE strategies that deviate by at most / ///T. On the other hand, suboptimal arms can expect roughly log(T)) A allocations as long as they can prevent elimination and all other arms act rationally, which results in the linear dependence on A, Hence, interestingly UCB-S' selection policy directly impacts the truthfulness selected more frequently between incentivizing all arms to truthful and recommending only the best arms. The proof of Theorem 5.2 5.2 of the best response property of the Nash equilibrium.
the arms, as arms that are forced to choose strategies closer s* "(4).. We thus observe trade-off
(Appendix Cp then relies the above observation and careful and repeated application
5.2 UPPER BOUND OF THE STRONG STRATEGIC REGRET OF UCB-S
With the approximate NE characterization from Theorem 5.2 at our disposal, we are ready to prove regret upper bound for UCB-S. We show that the strong strategic regrei of the UCB-S mechanism upper bounded by ((KTT), that is, for any a E NE((UBBSS) the regret guarantee holds.
Theorem 5.3. Let A == μ* μ4 and let L and H denote the Lipschitz constants of u(s, p.) and s* (4), respectively. The strong strategic regret of UCB-S is bounded as
(VKKTOTTTTTTT +
log(T))
(UCB-S) = -
(3)
A
FA.50
In other words, the above regret bound is achieved under any equilibrium NE(UUB-S).
7

---

Published as a conference paper at ICLR 2024
Proof Sketch. As suggested by the regret bound there 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., A, 0) deviating from the ceility-maximiziing strategy s" (p*). For such arms Theorem 5.2 bounded the deviation by a term of order v /K/T, thereby leading to at most order v T regret. The second term in (3) corresponds to the regret suffered from playing arms
with suboptimal post-click rewards, i.e., A >> 0. Using a typical UCB argument, the Lipschitzness
of u(s, u) and 5" s1(),, and again Theorem 5.2 applied Is" (µ*) 8il I |s (p") =s* (w:) +
O(HA)) & HA, + O(HA;) we obtain the claimed upper bound.
Similarly to classical MABS we can state a regret bound independent of the instance-dependent quantities A and translate Theorem 5.3 into minimax-type guarantee. Corollary 5.4. The strong strategic regret of UCB-S is bounded as
(UCB-S) = (L. KT (og))g(T))
In other words, the above regret bound achieved under any equilibrium o NE(UCC-S).
Theorem 5.3 nicely shows that the additional cost of the incentive design and the strategic behavior of the arms of order v KT which primarily stems from arms with maximal post-click rewards deviating by roughly v /K/T from the desired strategy (see Theorem 5.2). The dishonesty of subop- timal arms does not notably contribute the regret and is contained in the ITg( A; expressions as we can bound the number of times suboptimal arms are played sufficiently well. As a result, the total cost of incentive design and strategic behavior matches the minimax learning complexity of MABs so that we obtain an overall O D(VK) KT) strategic regret bound under every equilibrium.
5.3 LOWER BOUND FOR WEAK STRATEGIC REGRET
Complementing our regret analysis, we prove lower bound on weak strategic regret in the strategic click-bandit. By definition, weak strategic regret lower bounds its strong counterpart, i.e., RT (M) S (M). that the shown lower bound directly applies to strong strategic regret well, which implies that UCB-S is near-optimal.
Theorem 5.5. Let M be any mechanism with NE(M) + 0. There exists utility function satisfy- ing (Al) A3) and post-click rewards (1,...., , PK such that for all Nash equilibria a E NE(MM):
R3 σ) = (VVK)).
In other words, (M) (((KT))
Proof Sketch. Consider the utility function u(s, u4) = sp. Intuitively, for any low regret mecha- nism M the NE for the arms will be in (s1,..., 8K) ) (1, .... 1) as these strategies maximize the learner's utility u and are to the advantage of the arms. In this case, the learning problem reduces a classical MAB and we inherit the well-known minimax VKT lower bound. However, it is
not directly clear that there exists no better mechanism that would, e.g., incentivize arm strategies ($1...., 85*, ...,,...,,.... 5k) (0, .., ,,, 0) under which i' argmax, 14 becomes easier to distin- guish from i * '" For this reason, we argue via the arms' utilities and lower bound the minimal utility a suboptimal arm must receive in any NE. This directly implies lower bound on the number of times we must play any suboptimal arm in equilibrium, which yields the claimed result.
SIMULATING STRATEGIC ARM BEHAVIOR VIA REPEATED INTERACTION
Goal of the experiments is to analyze the effect of the proposed incentive- learning algorithm UCB-S on strategically responding arms. Strategic arm behavior is here modeled through decen- tralized gradient ascent and repeated interaction with the mechanism. Contrary to the assumption of arms playing in NE, arms follow a simple gradient ascent strategy to adapt to the mechanism, which serves realistic and natural model of strategic behavior. This requires prior knowledge from the point of view of the arms and all learning is performed through sequential interaction with the mechanism. For this reason, the final strategies in our experiments may necessarily be in NE. Despite this, we want to see whether the mechanism is still able to incentivize arms to behave in the desired manner which will also provide insight into the robustness of the proposed incentive design.
8

---

Published as a conference paper at ICLR 2024
08
03
0.1
07-
oumeen strateyy
CUIFENT strategy
CUFTERT, Strnegy
Ourrent Stategy OESPCS Statogo 5"100
desied 5intogy (11)
desired srotagy UTU
055 dratigy
01
(a) Optimal arm with
(b) Suboptimal arm with
(c) Suboptimal with (d) Suboptimal arm with mean Jaa = 0.7.
mean μu1 0.75.
mean jaz = 0.725.
mean μ4 0.675.
Figure 2: The strategic behavior of K 4 arms when each arm uses gradient ascent maximize their utility e; in response to the UCB-S mechanism. In red, the desired strategy s (w,)) for each arm respectively. As suggested by Theorem 5.2] the truthfulness, i.e., distance s* (u:), of suboptimal arm i is governed by the arm's 's optimality gap A, We see this confirmed as the distance 8, s* (1,, increases as A increases. In accordance with our theoretical results, the optimal arm has the largest incentive to play close to the desired strategy (as it loses the most when eliminated).
Experimental Setup. We consider the earlier introduced utility function defined as u(8. 14) = sp - A(s 12² such that the desired (learner's utility muliit--aaimiziig! strategy given μ is s" (n)
16
19K5
Strutige: Regret UCB-S Stratagr: Regret UCB
1900
1300
(1 (1+ 2x mr. We let = 5. To model the strate- gic behavior of arms in response UCB-S, we let the strategic arms interact with the mecha- nism over the course of 20 epochs (x-axis) and model each arm's 's strategic behavior via gradi- ent ascent w.r.t. its utility v, More precisely, af- ter every epoch (i.e.. interaction over T = 50k rounds), each arm performs an gradient step with respect to its utility vs We initialized the arm strategies to approximated 1, however, our experiments show that other initialization, such as 5; = 0 or s; = 0.5, yield similar results. All results are averaged over 10 complete runs and the standard deviation shown in shaded color.
011
Current strategy
CUPTenT: dtrategy
ent 2r3ttey
ent strotogy
3005
05
Figure 3: Strategic arm behavior when inter-
Figure 4: Strategic re- gret of UCB-S and stan- dard UCB as arms adapt their strategies.
acting with incentive- unaware standard UCB.
Results. The conducted simulations show that under natural greedy behavior as modeled by gradi- ent ascent, the incentive design of UCB-S is still effective and desirable arm strategies incentivized (Figure ( Most notably, the optimal arm (having the largest incentive to be truthful) converges to a strategy close to the desired strategy s" (w1). The suboptimal arms do not converge to a strategy close to the desired strategy and we observe that the distance to s *J(x) depends on the optimality gap A,, which mirrors our theoretical results (Theorem 5.2). In addition, Figure 4 shows that as the arms interact with UCB-S and adapt their strategies, the regret of UCB-S improves substan- tially. In contrast, incentive-unaware algorithms like UCB fail to incentivize desirable strategies (all arm strategies remain close to 1, see Figure 3 and UCB accordingly suffers large regret (Figure 4 throughout all epochs. The observation that UCB-S initially suffer larger regret than UCB can be explained by the elimination rule causing UCB-S select arms uniformly at random when arms are notably untruthful. This threat of elimination, however, incentivizes the arms to adapt their strategies in the next epoch and eventually leads smaller regret for UCB-S.
DISCUSSION
We study the strategic click-bandit problem in which each arm is associated with click-rate, chosen strategically by the arms, and an immutable post-click reward. We show the necessity of incentive design in this model and design an incentive- sirable arm strategies under uncertainty. As the learner has no prior knowledge of the arm strategies and the post-click rewards, the mechanism design approximate and leaves room for arms to ex- ploit 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. In our simulations we then observe that our incentive design is robust and still effective under natural greedy arm behavior and that the design of incentive-awar learning algorithms is necessary to achieve low regret under strategic arm behavior. Some interesting open questions which we leave for future work include whether the proposed incentive design remains effective under adaptive arm strategies and whether can construct mechanism under which there exists desirable NE in dominant strategies.
online learning algorithm that incentivizes de-

---

Published as a conference paper at ICLR 2024
Acknowledgments. We thank the anonymous reviewers for their insightful and constructive com- ments. We also want to thank Boi Faltings for helpful discussions in the early stages of this work. Thomas Kleine Buening was partly supported by the Norwegian Research Council (Grant 302203). Haifeng Xu is supported by the A12050 program at Schmidt Sciences (Grant G-24-66104) an NSF Award CCF-2303372, an Army Research Office Award W91 INF-23-1-0030 and Office of Naval Research Award N00014-23-1-2802.
REFERENCES
Peter Auer. Using confidence bounds for exploitation-exploration 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.
Moshe Babaioff, Robert D Kleinberg. and Aleksandrs Slivkins. Truthful mechanisms with implicit payment computation. Journal of the ACM (JACM), 62(2):1-37, 2015.
Dirk Bergemann and Juuso Välimäki. Dynamic mechanism design: An introduction. Journal of Economic Literature, 57(2):235-274, 2019.
Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey 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, and S Matthew Weinberg. Multi-armed bandit problems with strategic arms. In Conference 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 the 10th ACM conference on Electronic commerce, pages 99-106, 2009.
Jing Dong, Ke Li, Shuai Li, and Baoxiang Wang. Combinatorial bandits under strategic manipula- tions. 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 strate- gic manipulation. In International Conference Machine Learning, pages 3092-3101. PMLR, 2020.
Rupert Freeman, David M Pennock, Chara Podimata, and Jennifer Wortman Vaughan. No-regret and incentive-compatible prediction with expert advice. arXiv preprint arXiv:2002.088837 2020.
Guoju Gao, He Huang, Mingjun Xiao, Jie Wu, Yu-E Sun, and Sheng Zhang. Auction-based com- binatorial multi-armed bandit mechanisms with strategic arms. In JEEE INFOCOM 2021-IEEE Conference on Computer Communications, pages 1-10. IEEE, 2021.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-39) 2019.
Nicola Gatti, Alessandro Lazaric, and Francesco Trovò. A truthful learning mechanism for con- textual multi-slot sponsored search auctions with externalities. Proceedings of the 1 13th ACM Conference Electronic Commerce, pages 605-622, 2012.
Arpita Ghosh and Patrick Hummel. Learning and incentives in user-generated content: Multi-armed bandits with endogenous arms. In Proceedings of the 4th conference Innovations in Theoretical Computer Science, pages 233-246 2013.
Irving L Glicksberg. A further generalization of the kakutani fixed point theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society, 3(1):170-174, 1952.
10

---

Published as a conference paper at ICLR 2024
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifica- tion. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111-122, 2016.
Katja Hofmann, Fritz Behr, and Filip Radlinski. On caption bias in interleaving experiments. In Pro- ceedings of the 2 st ACM international conference on Information and knowledge management, pages 115-124, 2012.
Jiri Hron, Karl Krauth, Michael Jordan, Niki Kilbertus, and Sarah Dean. Modeling content creator incentives on algorithm-curated platforms. arXiv preprint arXiv:2206. 13102, 2022.
Xinyan Hu, Meena Jagadeesan, Michael Jordan, and Jacob Steinhard. Incentivizing high-quality content in online recommender systems. arXiv preprint arXivv2306.074799 2023.
Kirthevasan Kandasamy, Joseph Gonzalez. Michael I Jordan, and Ion Stoica. Veg mechanism design with unknown agent values under stochastic bandit feedback. Journal of Machine Learning Research, 1153):1-455 2023.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. Proceedings of the 19th international conference World wide web, pages 661-670, 2010.
Yang Liu and Chien-Ju Ho. Incentivizing high quality user contributions: New arm generation in bandit learning. In Proceedings of the AAAI Conference on Artificial Intellignce, volume 32, 2018.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623 648, 2004.
Hamid Nazerzadeh, Renato Paes Leme, Afshin Rostamizadeh, and Umar Syed. Where to sell: Simulating auctions from learning algorithms. In Proceedings of the 2016 ACM Conference Economics and Computation, pages 597-598, 2016.
Noam Nisan and Amir Ronen. Algorithmic mechanism design. Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129-140, 1999.
David C Parkes. Online mechanisms. 2007.
Alessandro Pavan, Ilya Segal, and Juuso Toikka. Dynamic mechanism design: A myersonian ap- proach. Econometrica, 82(2):601-66) 1-63,, 2014.
Philip Reny. On the existence of pure and mixed strategy nash equilibria in discontinuous games. Econometrica, 67(5):1029-10566 1999.
Suho Shin, Seungjoon Lee, and Jungseul Ok. Multi-armes bandit algorithm against strategic replica- tion. In International Conference on Artificial Intelligence and Statistics, pages 403-431, PMLR, 2022.
Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Ma- chine Learning, 12(1-2):1-286 2019.
Huazheng Wang, Qingyun Wu, and Hongning Wang. Factorization bandits for interactive recom- mendation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Wenjie Wang, Fuli Feng, Xiangnan He, Hanwang Zhang, and Tat-Seng Chua. Clicks can be cheat- ing: Counterfactual recommendation for mitigating clickbait issue. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1288-1297, 2021.
Youtube. How money on YouTube, 2023.

---

Published as a conference paper at ICLR 2024
Yisong Yue. Rajan Patel, and Hein Roehrig. Beyond position bias: Examining result attractiveness as a source of presentation bias clickthrough data. In Proceedings of the 19th international conference on World wide web, pages 1011-1018, 2010.
Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. 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 for large- recommendation problems. arXiv preprint
2016.
12

---

Published as a conference paper at ICLR 2024
APPENDIX
The appendix is arranged as follows:
Section A
contains the proof of Proposition 4.1
Section
B
proves the existence of a Nash equilibrium under UCB-S (Lemma 5.1
Section contains the proof of the Nash equilibrium characterization (Theorem 5.2
Section
contains the proof the regret upper bound of UCB-S (Theorem 5.3
Section B
contains the proof of Corollary 5.4
Section F
contains the proof of the lower bound (Theorem 5.5).
Section G
contains basic technical lemmas that are used in the proofs.
Section discusses additional related work.
A PROOF OF PROPOSITION 4.1
Proof of Proposition| 4.1. (i): Under any strategy profile 8 = (811..., ,K), arm o i has utility Ve(n-Oracle, 8,, 8-5) while arm i" has utility
Uy (J-OOracee 8 8-1)) Tsp
Hence, the pure strategy = 1 is strictly dominant strategy for arm i", which implies that i" plays 8t- with probability one in every Nash equilibrium. Now,
u(s" 1..)) u(s , (..5,)5))) ) u(s" (p-) - u(1, (4-
and the j--raale thus suffers regret every round, which implies the claimed (2(TT) lower bound in every equilibrium.
(ii): Let j argmaxzz b4 be the arm with second largest post-click value and define uz. u(s" (1z=))))); (1z-). P.)). Let s' be the largest s [0, 1] such that u(s', pa-) 2 uz.. We distinguish between two cases:
Case Suppose that u4=' > uT.. From the continuity of u then follows that s' = 1. To see this, suppose the contrary true. Then, for all s" s' with 8" E [0, 1] must hold that u(s", (4-) < ut- by definition of s' as the largest this contradicts the continuity of u(s, p) in s, since we have just shown that u(s", pe)) ug. u(s', ) for all s" > s'. We have thus shown by contradiction that s' =1
[0, such that uss, pe) 2 ujr However,
Then, if arm 1" chooses strategy s,- = 1, arm i is pulled every round by (s. Or-rcll for all 8-4- [0, = that 1i- ((s. (1)-raele, 1, s_++) T. This immediately implies that sy a strictly dominant strategy for i*, since vi- ((s, (1) -4r-cle,,,, 8, 8-;+) & Ts < T for all s E [o, 1). Thus, arm 1" plays 8;- in every Nash equilibrium of the arms. Analogous to the proof of (i), this yields |u(s", u(")" u(s;", u(s;=,,:=)) ) = B, which implies that the (s, Or-Orae suffers 2(8T) under any Nash equilibrium the arms.
Case 2. Suppose that u(=', ny... In first step, we show that arm i" plays s' with probability one every Nash equilibrium. We begin by noting that if arm 1 plays s,- s'. then for any opponent strategies 8-j- [0, 1] arm i" is played all T' rounds so that Uy ((s, p))Oracle, s', s_xx)==+++) = Ts'. Naturally, s' "hus strictly dominates any other strategy s" < since (;((s, (1)ss,))-ona Oracll, s S Ts".
Next, suppose that arm i* plays some strategy s" > s' with probability one Then, by definition of s', we have u(s", ) uG- uls (My-), As result, arm j' best response sy- to s"
Foor simplicity, assume that arm i* plays the strategy with probability one. The case where 1" plays s' with some positive probability he treated analogously.
13

---

Published as a conference paper at ICLR 2024
will be such that u..) ((($5",,5" thereby obtaining utility vy- ((s, (1).pu))rrakle s,,, 8-j-) 2 Ts" (Hy-). As a result, jf plays a best response, arm 1 receives utility when playing s", whereas arm 1" receives utility T'' when playing s'. Hence, any s" s' cannot be part of an equilibrium for arm i" and we have shown that arm i* plays with probability one in every equilibrium. Finally, by definition of s', we have
u(s" (=) H4+) 2 (4) u(s (p) (p)-). u(s" ,1" u (1g-) =
which implies that (s, -ra-le suffers R(TT") regret under any Nash equilibrium of the arms. Hence, we obtain the claimed lower bound of S2( min
Remark A.1. Interestingly when the (s,pv)-Oaace from Proposition 4.1 (ä) does not break fies favor of the larger ys but instead uniformly at random, can be shown that in all but a few problem instances no Nash equilibrium for the arms exists. However, for any we explicitly construct an e-Nash equilibrium for the arms under which the algorithm suffers Mminn T) strategic regret.
Before proving the statement of Remark A.1 formally introduce the concept of e-Nash equi- librium among the arms here.
Definition A.1 (s-Nash Equilibrium). For > 0, we say that strategies = (aI.... σk) form an E-Nash equilibrium under M if (M os o-1) 2 (M, a-.) for all e [K] and of E.
we will show that there exists an e-Nash equilibrium in pure-strategies s E [0, 1] such that the oracle algorithm that breaks ties uniformly suffers linear strategic regret.
For Remark A.1
Proof of Remark A.1
As in the proof of Proposition 4.1 (ii), let j E argmax bi be the arm with second largest post-click value and define uj- == u( (pzr), Now, let s' be the largest E [0, 1] such that
u(8', p 2 uj- and uls' - 8', px) > ujj for all E' 0.
Note that such s' exists since is continuous and u(s* ((()) 11-)) > uf... We again distinguish between two cases, similarly to the proof Proposition 4.1
Case 1. If u((ss, (4+) ) > ui.. it follows that s' = 1. This means that = (st,, s_5. with s;- and arbitrary s-i- E [0, 1 form pure strategy Nash equilibrium for the arms. As in the proof of (i), we then obtain
uls" n²) u(su. p4.)
which implies order ((3T) regret under 8-1.).
Case 2. Now, suppose that u(s', p2)) un. Let s -' and 8, s for all i 8.. We that ( is (Te') equilibrium under the oracle algorithm. Hence, for any 0, the strategy profile &e' == (8' ,',8-r) ) is e-Nash equilibrium for all f. Using that u is I.-Lipschitz, we have
|u(s' - (p-) - u(s)), = Ju(s' - -'..p))) u(s'.pr)) s LE',
and it follows that
|u(s" ((==,,"") uls' s pr. >> Ju(s", -
- -0(3 Le' Le'
We can choose < sufficiently small so that Le' < 1/T. Hence, over T rounds the oracle algorithm suffers ((nT) regret under the E-Nash equilibrium given by sy, This yields the claimed lower bound.
14

---

Published as a conference paper at ICLR 2024
B PROOF OF LEMMA 5.1
Proof of Lemma 5.1 We use Glicksberg's theorem Glicksberg (9952). which guarantees the istence of a Nash equilibrium
continuous games with compact strategy space and continuous utility functions U, The strategy space [0, 1] is compact and we are left with proving the continu- ity of ey (UCCB-S s) in & E [o, 1] Since v; (UCB-S, s) = E [t]]ss the question is whether E. [+)( is continuous in under UCB-S. The choice of influences the actions of UCB-S when through the screening rule in line 10 but also the UCB-type selection in line since post-click rewards are only observed when the arm is clicked.
Let Hr denote the history of the mechanism's selections and observations up to round t, consisting of tuples (ie, Ct, )., Even though rt, is sometimes observed, we include it here and note that it will not matter as the realizations of Tt, are independent of 8. We let Hi up round denote the set of all possible histories.
While we are interested in (t)) for technical reasons, it will be more convenient to prove the continuity of (H, E -) as a function of s. We will do so by induction over t E [T]. Naturally, P. (H1 E is continuous in since Ps Ps( of For the proof by induction, let us now assume that P. P,(Hz E is continuous in s. Then, for
1) Si, and we break ties in line 4 indeepedennt
++1 we find that again Pa (Ct-1.hr1 = 1) 1 (C 0) Siga1 is continuous in The interesting part is then whether Ps (ft+1 = i) is continuous 8.
Lemma B.1. For any event A, if He) and Ip, (H4) are continuous in 8 for all H4 E Hi then (A(A) is also continuous in s.
Proof. This follows from the law of total probability.
We begin by analyzing the dependence of the screening rule in line on First of all, note that for all i E A,- \ {i we always have E Ar, i.e., no other arm than &, will ever be eliminated at the end of round 1. Moreover, since (ct, = 1) 8t, is continuous in 8, it follows that P& > a) and (g,,
He) are also continuous in s for all a E IR. Consequently, the probability that arm is eliminated in line 10 at the end of round t, i.e., P. (& & At), must be continuous in
Let us assume that A, * 0. since P. (1 = i) is always continuous have Pa ((e41 = i) = Note that for all of ig we have pe = pt-1 We will now first consider any i F 4. i E Ac, we then have
A, = If & A,, we
P. Pa(111 = H.))
P. PT(
TH is $ Ar, H.) (i As H4))
(
max
T
4 E A,, A,, (.) Paa A He)
(4)
jEAr(1t
=P(p
pp-1 1 Φ A., H.) P..i. & A, 14))
max (e.))
max JEA((iA)) + 11(11t
11)- i441 # 4, H.) (P441 # i is E Ar, H4) -P E A, H.).
The leading factors are independent of and have already shown that Pa & A(+1) is continu- ous in s. We are thus left with proving the continuity of P. (1++1 # it is E AA41, He).
It holds that Po (pt, E 74)) s, P7Z, E cr,6, 1, H4) + (1 s, PF E cr,, 0, H4), where we used that P= E ct.., Ha) P(ut, E Ct.i, H.) is independent of (conditional on the click-event C. Hence, sum and product of continuous functions Pa E H.) is continuous in and we get that
Pa it Ho) Pa > max
1-1 H.) Pa E Aet1 Hz)
1F1.
Note that Tt+1d44 independent of
15

---

Published as a conference paper at ICLR 2024
is continuous in where used that p.j pi-- ! for all j + ds independent of Then, since
Ps Pa ft & ø A.) = 0, we have
P. (4 it M(.) = (ic41 it A,, H.)
A, 14).
which shows the continuity of (ic+1 it A,, H4). Hence, in view of equation (4)
obtain that (4 = H4) is continuous in s. Finally, Lemma tel us that, since (H() is assumed be continuous, IP, (8r+1 i) is continuous well. Hence, Pa (H++1) is continuous and
by induction we get that IP, (Hr) is continuous, which implies the continuity of Eg [ir( in 8 for all i.
C PROOF OF THBOREM 5.2
Proof of Theorem 5.2 In the following let (d1..... NE(UCB-S) and supp(or). We start with some preliminaries. Recall that the arm i's utility function given algorithm UCB- S and strategies (st, s-1) be expressed as
e: (UCBBS 8,, 8-1) E(UCB.S.a.....)) (n))
and (UCCBBS, s,, --)) = _, (UCB-S st, s_1) = Eis,. |n (i)] For convenience, omit the argument UCB-S in the following, as every probability and expectation will be w.rt. UCB-S. The following variables will prove useful. Let T; be the first round that arm is not in the active set A, anymore,
7. = min [T]: i & A.):
and let be the first rounds in which A, is empty,
min (t [T]: A, 0}.
Here, we introduce the convention that = if E A7 and T Ar +
To characterize the strategy profiles in the support of any Nash equilibrium under UCB-S, we are going to rely the best response property of the Nash equilibrium. More precisely, for any supp(ar with a E NE(UCB-S) arm i's strategy, 8i must be a best response to a-i, iee, for all of E [0, 1]:
0,(si, v..8,,
In a first step, show that UCB-S incentivizes arms choose strategies at least large as the desired strategy 8" (Ju.) While this seems obvious at first since each arm i's utility includes linear factor of 8t, we notice that in the click-bandit model arms can prevent the principal from learning about their true post-click value by choosing low click-rates s. This could in theory be viable strategy for suboptimal arms, i.c., #4 μ², since it would delay the principal from detecting that the arm is suboptimal. However, we quickly notice that delaying UCB-S from learning about (11 ... fk is each arm's disadvantage as any delay simply delays the round which it receives utility. Moreover, while an arm may delay the learning of μı UCB-S still improves its estimate of 8; and the threat elimination becomes more imminent.
Lemma C.1. For all s E supp(or) with a E (E((UCBS)) and all e [K]:
s; 3.25 s²,5))
Proof. Let E NE(UCB-S). We begin by making some fundamental observations about UCB-S the click-bandit model. Let < If ef and i, A,, then 4,41 i To see this, note that
Note that p4 1 is H.-measurable for all $W.Lo.g. we assume that there are no ties (ignoring the rounds where no post-click rewards have yet been observed). In fact, when there is possibility of a tie, it can be seen that the arms have even larger incentive choose 8; x" (14), since they are guaranteed be pulled again in the ensuing round when not clicked.
16

---

Published as a conference paper at ICLR 2024
the estimates of ji...... ................................ Mr and their confidence bounds do not change from t to t + 1 if Cr =0, since no post-click reward was observed for any of the arms. Hence, given that it E Ac, we have
argmax T. = arginax p = in. SeAr
iEA: 1
Thus, given that is not eliminated in the mean time, UCB-S plays arm i, until arm in is clicked, i.e, until the arm receives utility 1, or we' ve reached round T. Hence, whenever Cr = 0, it simply delays the UCB selection rule by one round the estimates and confidences of p.,,... Pk do not change. At the same time, arm with i = i still only receives utility for this sequence of selections by UCB-S, since the UCB selection rule "progresses" once Cr, = 1.
More formally, we can define the phases of the UCB selection rule recursively by The == min > M C,s, = 1} with no == and 7 oc if round T' is exceeded without click. We define the number of such rounds as N == max(k: 7) оo} and remark that N S T always.
We first note that conditional on An the identity of in. independent of s; (and --:,, but only de- pends on Pi...., . fx and their realization at rounds ,....... T7k- 1, i.e., P P(s.o (. = i A 1)
P( A ). Moreover, we also see that IP (s..o-)) Then, since
Aq ) is independent of st
P(s,,-.) = i i Amn-1
Σ ((eeo- (bbr = Am (U - AliE An
this implies that IP ( (Brz = E Am is independent of st, Using the shown independence, let us then write
() =) = P(ims = =i iE A (ioria-.) E Am--)
(5)
+ + =i =ili i P (l(sso-)) & Am--).
Now, it holds that (m = i i E Amn-1) 2 P(aio_. = iili & Aqu-1) always. Naturally, for 8; < s" (pz) we have P ()) E Ama-1) < (())) E Am--) so that from equation (5) it follows that
(1 = (m))) =
(6)
We also see that as s; decreases the number of utility- dillit--yelliig rounds decreases in expectation, i.c., for < s" (p:):
E (s [N] < ((s)(1).m-.))1))
since 77 7 Geom St., Finally, it follows from equations (6) and and technical lemma
about the comparison of expectation under two measures (Lemma G. in Appendix G that
E - (mr (i)] E(sno
Une =
N
< ((i))o))
fing =1)
= B (m))))))))))
Since a post-click reward is observed with probability s; every time an arm is pulled by the learner, we have (ee...))(mm())) = E (m)())) so that (s(,, o-.) = ()),.)) Now, from the above we see that for any s; < s" (Hi), the strategy s* (1.) is strictly better response to a than s;, i.e., (14)) a-;) > 01 -)). This shows that 2 s* (11s) for any E supp(a;) with E NE(UCB-S).
Hooweeer, note that the value of At for general i is not independent of s; conditional on i Ac, since, e.g., for small s, other arms will be played fewer times before round f, thereby reducing the probability of them being climinated by round
17

---

Published as a conference paper at ICLR 2024
We continue the proof of Theorem 5.2 by decomposing the number of times each arm is selected by UCB-S. Given (s,, 0-.) we can split (s,,a ([nr(t) into the time steps before ти and after т, since arm i is never played in the rounds between 7i and т. Recall that UCB-S plays arms uniformly at random after round T so that
TK Σ
E (s..o_ (nT())) (o)
(1=0)
Σ (=++1
1 (4=1)
(e (1)) + (o,
(8)
The proof of Theorem 5.2 proceeds by upper and lower bounding the quantities in 8 which will eventually lead to an approximate characterization of the best response 8;. More precisely, establish following bounds a NE(UUBBS) and 8; E supp(a:):
Lemma (( 1)) [17 (i)] < 50
H² log(T)
(((5=-5((4))
Lemma
T
E (e, [ ((1).
Lemma
E, (e [nr = 22 min|
(oR(T) a 8* (m/ (m)) 1)
C.I BOUNDS ON (i), nr. (i), T.. AND UNDER UCB-S
We begin by bounding the number of allocations arm receives before elimination. As one expects, UCB-S S is able detect that * s" (p:) with high probability after most O(1/(s; s" (1)))) selections.
Lemma C.2. Let NE(UCB-S) and s, supp(o,) with s, + s* (pa). Then, the number of times that is being selected before elimination, n..) (i), satisfies the following. For some constant G1 0, holds that
22 log(T)
3
P (( no, (i) S C1
2
51(8; - s" (1:))²
T
and an immediate consequence for some C2
22 log(T)
Eisho aln (1),()]] S C2 s,(s; - s" (H,))2
Proof. For simplicity, consider w.l.o.g. the one-sided elimination rule checking whether the arm i's strategy 8; exceeds the desired strategy s" s(())::
max 8" (n). aElu ml
Let az(1)
2oo (.)))
and Br(i)
v
2 log(T) ma(t)
Recall that s² (μ) is H/-Lipschitz Then,
max PE
(H() + H3((1.
As consequence, we see that sufficient condition for the elimination rule 9 to trigger is given by
( s" (p)) H3)(1),
(10)
where by definition of 3 3 - as (1). The following statements are always w.r.t (8,, a-1), i.e., w.r.. the probability measure P( From Hoeffding's inequality, we know that with probability at least 1 - 1/72:
| sil S (i).
18

---

Published as a conference paper at ICLR 2024
Similarly, using the Lipschitzness of s² (p)), Hoeftding's inequality implies that with probability least 1/T2:
(x*) ((i) S 170 pal S H.)(())
then follows that with probability at least -2/72
(1)) 2 (+: 8 ((+)) - (ix(1) + ++(xi)) 2 (s: s ((ss)) - (H + 1)3x(1,
where we used that (i) 2 (T)(T)
llg((T)
(t), since (1 > m (1) by definition.
(i(
m.
Therefore, the sufficient condition in equation TO satisfied with probability 1 2/T² for
log(T)
* s (14) > 2 + 1) = 2(H 1/
mi(i)
In other words, arm has been eliminated by round t with probability at least - 2/T if
(i(1) 16H2 log(T)
(11)
(s; (1,)))
Lastly, we translate this to statement about (i).). Recall that conditional on (i),), we have (i) ne(i)] = (i)s), since arm is clicked with probability 8;. From Hoeffding 's inequality, then again have with probability 1 1/T"
(i) - ne (1)ss)) S 2ne log(T)
and thus m²(1) 2 me(1)s: 2m)(( log(T)) (T). Then, in view of equation 111 if
H log(T)
(1) > ci (5 - s* (p:))²
for some sufficiently large 0 > 0, then with probability at least 1 1 3//7² arm has been eliminated before round t. Since 7; denotes the round which is eliminated from As, this means that with probability 1 - 3/T²:
2 log(
Re, (i) S
s:(5; (u:))²²
Since by definition Ti S T, this implies that for some 02 > 0:
2 log(T)
Eiso alm,, (i) S si 5* (14))²
We briefly recall a standard result often used the context of MABs, which states that any prob- ably correct decision rule needs ((+) samples to distinguish between two hypotheses for which the Bernoulli means lie E apart. We only give short outline of the proof and refer to the many expositions of such bounds for more detail (see, e.g., Theorem in (Mannor and Tsitsiklis 2004
Section in (Slivkins et al. 2019), Section 14 in [Lattimore and Szepesvári 2020)).
Lemma C.3. In order for to reuse current notation, suppose that K 1. In this case, n,, (1) simply denotes the number of samples from arm before it gets eliminated, i.e., UCB-S asserts that 81 # 8" (11). For 81 # 8* ([1), it holds that
log(T) (51 3t (21))2
E,, [n,, (1))
Proof. W.l.o.g. assume that Tt.1 μr for all t that only concerned with the estimation of the Bernoulli mean 8 (this clearly only reduces the number of samples the elimination rule would need). Note that the elimination rule is correct with probability 1 1/72 by construction
19

---

Published as a conference paper at ICLR 2024
of the confidence sets around $1, i.e., only eliminates arm if it in fact deviated from s (u1). We can then consider the hypotheses
Ho 81 s" (p1) and H1 81 5" (p1)+
Then, since the climination rule is correct with probability 1- 1/T2, the standard hypothesis testing
argument (see, e.g., Theorem in (Mannor and Tsitsiklis 2004)) yields for some constant
that E, (n., (1) cl' < cog(2]
(01 (x1))"(x)))
The next lemma states that o is close to The intuition of this quickly explained. If the set A, becomes empty, UCB-S plays arms uniformly at random. However, if one arm would happen to remain A, this arm would always be played (as it has no competition). To do so, an arm simply has to ensure that it does not get eliminated too early. Now, in view of Lemma C.3 arm can be sampled order æ more times without getting eliminated for moving its strategy order v closer to s" (ps). Writing the arms' utility as ( --4) E (x.. (t)]; ((s,,--)) (+)]))))))()(((( (14))) +
(s. s" (p:)) we see that quadratic increase in (s,...)) (i)( will dominate linear decrease 8; (m:).
Lemma C.4. Let a E NE(UCB-S) and 8; E supp(o;;) Then,
E 1 T-
Proof. Let (J44 I N 8; Due to delays for smaller click-rates (see proof of Lemma C.I and the fact that under sy the probability of arm being eliminated at any given round is smaller than under 8,, it holds for all j j that
Beego- (1) E (i))
By definition of r, we have (a ) [7] [ EjE(K] F Mn,, (j) so that the above implies
() (T) S B(ano-llaT (i) o .) E (n., (i))-
In other words, under any strategy s" (p:) S s < 8;. all arms j 4 will be eliminated after a total of E E -,) f (i)) rounds that there least E (ss,o__)) (i) + T -- (E,
many "uncontested" rounds.
For convenience, let (s,,,_))) empty and arms are being selected uniformly at random. Now, in view of Lemma C,3 there exists sf with
E |) i... the expected number of rounds that A, is
log(T) (V E In (i) + N(si,o
2/ - ((A) 2 (
such that (s)),--) [n,, (1) 2 E (1) N(s..
The proof proceeds by contradiction. To this end, suppose the contrary is true, namely, that N(s,, o_;) is not constant, but in fact increasing in T, ie., N(s,, σ-v) = w(1). We then show
that (1 -i)) > aii, which is contradiction 8; being best response a- From Lemma we know that
log(T')
8; (44) 50
(v
s* (Bt) 1117,
20

---

Published as a conference paper at ICLR 2024
where we used that s; 2 s² (14) by Lemma C.1 we then obtain
Using that B() (m) 2 (s) (i)}
(5 a-))
(s M. (i) (5 (14) + (5: -64-5((44)) (14)))
log(T) ( 17 (1) M 0-1) (*((ss) + (v R | + N(8 a-1)
(B (n. (1) (s;, (14) + a (Ioo(T) (n,,
(
(i)] (i) + NNoNN( N( ((8,,
2N 2N( 8² s'((s) + +0 (0 (V (i)]
((s,o (p:)
K
N(s,,
(B(s (i)]
(s. + (s: - s s((i))
K
E (nT
Us 0-))
Hence, & is better response to a-e than 8,, which a contradiction 8, E supp(a.).
The next lemma lower bounds (es, :) [ir(1)) for which we distinguish between optimal and sub- optimal arms in terms of post-click rewards μr.
Lemma C.5. Let a E NE(UCB-S).
(i) For all i [K] with A, 0 and s,, supp(o,-):
T
(1rr....)177(7()) 5 (u+=)
K
(ii) For all i [K] with A, > 0 and E supp(a;;):
E E( [nT(1)] 2 Ω min log(T)
r1
8 (11)
A
K
Proof. (i): Let a E NE(UCB-S) and let 8 E [K] such that A,- = 0. Recall that when playing strategy s" (pa+) arm i* is eliminated with low probability so that
P P(r(())) E Ar) 2 1-11
Now, given that i" is not going to be eliminated, the UCB-type selection rule of UCB-S se- lects any arm it with maximal post-click reward p4- μ² least Q(T/K) times that (( (nT(()))) 2 Q(T/K). Then, since St. has to be best response to a we obtain ((er (TT 2 8, (e, a - (MT (i*)] (s11,
T K
U.. (s* o,) 2 (p B (he (or s (444))))
(ii): Once again, we use the desired strategy s* ((4) to infer properties of 8,. Let us be reminded that under 8" (m4) arm is eliminated with low probability, i.e.,
P ((e Ar) 21 1/72
so that when studying (s" (p4), ai) the potential elimination of arm i is negligible.
21

---

Published as a conference paper at ICLR 2024
We will argue about (())())) [t)] via - [t]] To isolate the rounds in which arms are clicked, i.e., post click-rewards are observed, we will re-use the rounds Th, 72...... which determine the phases of the UCB selection rule (introduced in Lemma C.I.p On the rounds 7, "2,..... the UCB-selection rule of line 4 is analogous to standard UCB a MAB. We can then use well-known results from the instance-dependent lower bound analysis of the MAB prob- lem. From Lemma 16.3 in (Lattimore and Szepesvári 2020) it then follows that for some constant C1
2 log(T) + log A VK
24
We see that this lower bound is only meaningful for sufficiently large A, as the numerator may become negative for A; = O (VK/T)) For now let us assume that A; sufficiently large. Recall that (M)))a_) (w))a_-///rll) (m)(())))))))))))) = (p))((r))) [ir(()]s* (n,) as arm clicked with probability s"()).. Since 8, must be best response a-ss it must then hold that
(((())))--))m(())))))))) o=(
log(T) A
2 Ui (1ss); 0-1) = (as (l))((i) 2 02
for some C2 > 0. Solving for [s (v4).a.))) |nT (i) then yields
log(T)
(a))) [iT(1)] 2 02 s, A
Next, for A, S K(T) it is well-known that the number of times UCB plays arm order at least S2T/KK). We then have Eg (m. = ((x). so that
Bie, 1) ())] 2 (eno ) uz- (s;.
T
2 (1)) s' (o (wo.)) s (w:)
K
C.2 CONNECTING THE BOUNDS
Finally, using the lower and upper bound on B(,,,r :) [i)] obtain the following approximate characterization of the strategies in the Nash equilibrium NE(UCB-S).
For i" E [K] with A,- = 0, it follows from equation g and Lemma that
C.2 Lemma
C.4
Lemma
C.5
T
H2 log(T)
8" (14- )52
< E ((r(()=)))
50
+ +
K
8i0 (8:- 8² (1
K
Solving for s;, S* (pi-), we obtain
H22 (og(T) T s* (H:+)
8;- (si. - 5" (1x+ < O
Finally, using that s* (u.)) & by Lemma C.I bounded away from zero by assumption (A3)
yields the claimed bound (note that s² s(()) is
K log(T)
8;- - s" (px+) < O H
T ( )2
We here used that the standard minimax bandit regret of UCB in MABs bounded ō(vKT)
22

---

Published as a conference paper at ICLR 2024
For [K] with A
suppose that l) a. S 5" (1z)) k. Then, we have
(Tg s
2 log(T) 8,(8; s* (Hi))) + t0( K
Ω
so
which after solving for s; s* (11) yields
8, S² (
For [K] with log(T) s,
s" (u:) k
follows, analogously the case of A, 0, from Lemma C.2
Lemma C.4 and Lemma C.5 that
K Klog(T)
8; (1i) 50
(H (H6)
D PROOF OF THEOREM 5.3
Proof of Theorem 5.3 Let E NE(UCB-S) and let E [K] be any arm with A,- 0. We begin with a standard regret decomposition into the number of times each arm played and the rounds before i is climinated. It holds that
(UCCBB-), Eg
u()" uusi Mie)
Eg Egno
u(s* p²) u(si, M+s)))
+ Eeno
Σ u(s" ,4") ) u(st. Hie)
< Eg
Σ KE(K]
E. [, (i){(u(s",p)) ,²) - u(sn.Hl))
+ (T -Bl(T)))
(12)
From Lemma D.I below we know that T - Eo [T-]] S VKT. We continue to split the arms into
two cases. To this end, let A == v Klog(T) (m, and let A, / K (og(T) between (a) A, S A and (b) A, > A.
(=") For i [K], we distinguish
We begin with (a). Recall that s* (n²). For the proof we will need last technicality, namely, that A < 2A,, We here assume that 8* (u²) > AH Then, since (s(())) s" s(4)) s HA, HA,, get
K Klog(T) T
K Klog (T)
2
K Klog(? 22.
A
< s*
s* s'()
HA!
T
s" (1²)
T
11 Otherwise there is nothing prove since the regret bound of Theorem
5.3 is of order T.
23

---

Published as a conference paper at ICLR 2024
We can now apply Theorem 5.2 obtain for any E supp(or) that
Σ
Eg (i)((((s" ,1") ((8).14))
:A,
S L
Eg (2)](1s sil + 111 mull
SAiSA;
K log(T) Ts (1:)2 (1;)
S
Σ
EM (i) 1s (s*(x²) (0()] + O H
:AISA;
K (Tg(T) nt (1=)²
1 Σ
Eg(RTo (i)
(H+1)A;+0 +0 H
+ Ai
RA;SA;
S LLHH+ +2)
Σ
Ea( (i)
(13)
RA,SA;
22 2)A!
Σ
En (i)
BAISAY
Klog(T)
S SL H
Σ
Eg ( (i)
(u²)
:A:SA:
LH O (1())) ( (VKTlog(T))
where we used that E.A.sa Eoln, (i)) S T in the last line.
For taking care of the sum over arms satisfying (b), define the "good event" & jut S μ S Vie [K] vt E [T]}. We know that & occurs with probability at least 1 - 1/T" for any s E [0. 1| by merit of Hoeffding's 's inequality. Under E, we obtain from the standard UCB argument for all S Tr that
2 (T)
Mi 2
Dr. pe:
me(ee)
[T) Hence, E [K] with A > 0 we get that My (1) < clog(2) This implies that A, S 2 mzy- (3)
A
Now, post-click rewards are observed for arm i with probability 8; every time i is played by UCB-S, which tells us that Eg [m,,- (i)] = E, [n,,- (t)]sq, It follows from Theorem 5.2 that
Eg [n., (i) u(s" 14) u(ss. 14)
Eg [m (i)s( ,1*) u(8..M4) S
Σ
8i
CA
18* ss/ 111"" -mil
<
Σ
Eg [T, (i)
8t
iA,
Eg In (i)] |s 15*
s*()l] + O(HA)) +A.
L
Σ
8;
HA: + ((HA)) +A
L Σ
clog(T)
8,
AADA
log(T)
< LH Σ
s
EA
log(())
< LH Σ
(1())
AA
24

---

Published as a conference paper at ICLR 2024
where the last line used that 2 s" (ps) for all 8, supp(o,) shown in Lemma C.1 the proof of Theorem 5.3
This completes
Lemma D.I. Let 8 E [K] with A. = O. For all ó > 0:
VKT
Po TT > T
> 1 -.
1 1-
Proof. Suppose the contrary is true, i.e. Po Tr. T
VKT 1-6
S 8. Since Ti S T by definition,
this implies that
E [T-] S 56.7 6) VKT
1 1-8) 8 = VTT.
(14)
Now, let 83- E supp(o;-)) with (s... [T3-]] $ T VKT. Note that such 8,- must exist for (4) hold. We now show that there exists strategy 8/-- which is a better response to a- than 8;. To
this end, similarly to the proof of Lemma C.4 Lemma C.3
tells us that there exists s/.- E [0, 1] with
log(T) E ((..._.)[mT, (4) + KT
8/4- 5" (((x)) Ω
such that Fs. a.... [Tx.] = 7 (1(1). Moreover, recall from Lemma C.4 that B ((er_o-.))17) <
x (()) Then, using Vzty
2 Vx
/ズ4ツ" equation 8 and Lemma C.2
we obtain
De- (st+, --.-) s E o. [, (i") || OL1/K)
E (ss0,,0 My, [] (m:-) + (s+- s + OL/KK
E(so,o (i') s' (m+
+0 )00
(v ( M (
log(T)
(i*)
< Essor e)) M7, (i" [s" (p:)))))))) + 0 (1 (oog(T) ia xt) IMT (i*)]
< B(sc, Ma. (i ]s" (1x-)
(i*] + KT)
s' + 12 (1/ Eieroo (r. (i) + VTT
B(orr.0..)) (i") + K
VKT
(
log(7)
Blepoo (i*)] + VKT
(s* + (6/ (1x))))
K
Es (,) vi- (5.),
Hence, Up (8tr, er (=))))) a contradiction.
E PROOF OF COROLLARY 5.4
The argument roughly follows the standard way to translate an instance- dependent regret bound in multi-armed bandits minimax bound (see, e.g., (Lattimore and Szepesvári vari 2020 However, the difference lies in that we split the arms not according to some
Proof of Corollary 5.4
fixed gap A but according to the arm-specific gap
K log(T)
A
T s* (Hr)²*
25

---

Published as a conference paper at ICLR 2024
which already used in the proof of Theorem 5.3 This is necessary due to the guarantees of Theorem 5.2 being gap-dependent.
We begin by recalling from equation 13 in the proof of Theorem 5.3 that
Σ :A SA
Egln,, (0)((u(s, ,10 u( (1))
< L(H +2)
Σ
Baln,, (i)
(15)
iAiSA;
LH
O
(VTTlog(T))
KT
('()))
EAISA
where we coarsely upper bounded [, (i) T. For all arms with A, > A/, we also get similarly the proof of Theorem 5.3
Eg|n,, (i)((((s, ,1"" u(si, m4))
PAPAA
log(T)
SH Σ
(H:)
:A.DA!
log(T)
SH Σ
(16)
K
S Σ
LH
(v KT (oTTlog(T)
PASA ('1)))
where we used very coarse upper bound in the last line by simply adding a factor of (ps) Note that the bound in the second last line is much stronger bound than the one claimed in Corol- lary 5.4 Combining these two bounds yields the first statement of the corollary.
Recall the definition of 8min mi] (1s) and note that
K log(T)
max A'
(17)
22
KE[K]
To get the more refined bound in Corollary 5.4 we can continue from equation 15 and bound the right hand side via maximum using [7 get
LH o (VKTlog(T)
L(H 2)
Σ
E. (1)As Smin
RA,SA,
Lastly, note that in view equation 16 we have
LH o (VKTlogg(T)
Ea (u)s" w²)) u().. < LHO (VKTlog(T)
Smin
The corollary then follows from the regret decomposition equation
12
F PROOF OF THEOREM 5.5
Proof of Theorem 5.5 We work under the utility function u(s, = sj. In the strategic click- bandit model there are two distributions associated with each arm, the click distribution P., = Bern(s;) and the reward distribution Pa, with mean μ4. We here assume that arm i's reward dis- tribution Bernoulli with mean 14, E [0, 1]. For convenience, w.l.og. we assume that the learner observes both, the click-event and the post-click reward every round. This clearly makes the learning
26

---

Published as a conference paper at ICLR 2024
problem easier for the learner. To summarise the distributions of arm i we let Psi,u Pas P denote the product distribution.
We consider problem instances
1 11 2
1
)
1r
22
2
4 2''
with μı-- 3 +. A. For convenience, assume that M is index-independent, i.e., if arm and arm have identical distributions P P...... = s,, then (ir(t), mi) and (mr(j), ny (1)) have the same distribution. If M is index-indepee indeendndee, we can consider different indices 1" for the maximal element μ.. Let us choose A eVKKTT for some constant later.
be chosen sufficiently small
Let us suppose that M better than the claimed lower bound so that (M, p1) I <(VKT) for some s NE(M, s1) 12 By choice of A in μ., it then directly follows that Es [nr (i) S o (
for all i + 1*, otherwise Ri (M, 8, 2 ((vKT). Since ΣiE(K] (an(ar(i)] = T, this entails Es (i*) 2 ((k)
We now show that E. (nr( = of kt) cannot hold when s is a Nash equilibrium. To this end, consider an alternative strategy s/. Now, let of = 5, with
argmax B aler (k)). kE[K]
Generally, would expect j = 1", however, j could be any other index in [K] (except for now). Since Σte[K] E3 (A)] T for any 8, get that (s c) [nr K If this would be contradiction to the statement that (( = of R
If j * i", we find that KI.(Pa.. sy. Poj Psl.uc) = 0, since i and j have identical click and reward distribution. More generally, we obtain from the chain rule that
(L(Pas.pg: Pel. = KL(P,,, Pa:) + KL P PA.) = KL(P my Pa.) SAA where we used that e.g., Theorem 2.4 in Slivkins et al. (2019). Recall that A c/ K/TT. For sufficiently small
S KL P...) ) = KL (B)r(()
{), Bern( + +)) < 8A (see,
constant e > 0, Theorem 3 in (Garivier et al. 20199) then yields that either
T K
(i) "r(i)
Beg [nr (i)
or (e
(18)
2
Assuming nr( 2 1, using some algebra (Lemma G.2 the latter can be seen to imply that
T
E(g,s-)) [nr (i))
2K'
where the last inequality holds due to the choice of j. Hence, from equation
18 we obtain that
T
E (s 1) [nr((i]] 2 2K
This leads to contradiction, as 8y is better response to 8-; than We have thus shown that Rr s, (1) Ω (V(KT) for any NE(M,
G TECHNICAL LEMMAS
Lemma G.1. Let IP and P be two probability measure (and let and E. denote the respective expectations). Suppose that for integer-valued random variables N. X1, X2...., it holds for all k E N and some i N:
E[N < [[ and 0 < PX |
IN = NN a.s.
(19)
We consider pure strategy NE here, though, mixed strategies he handled analogously.
27

---

Published as a conference paper at ICLR 2024
Then,
N
N
E
1
[x+=
<
E
Σ
(X==1)
(20)
Proof.
Note that if N and X1, X2,...... were independent and X1, X2,... iid this would immedi- ately follow from Wald's lemma.
We prove the lemma via factorization. holds that
N
E
(xx |N=
= n P(N = n)
n=1
00
P(X; N P n)
P(Xx i =) n)
N
E
P(Xx = ii
N P(X, N) = É
E
(x
where in the last line we used that PXx,
N) > almost surely.
Lemma G.2. Let X and Y be two random variables (which are not necessarily independent) and
Y 2 1. Suppose that
X
1
N
Y 2
Then,
Y
E
Proof. Basic algebra yields that
2.X
2X
Y
2X Y
E
1
E
E
<B2X-Y1
Y
Y
Y
Hence, if E 2X
2 1, it follows that B E
H MORE RELATED WORK
In other related work, Ghosh and Hummel 2013 : Liu and Ho (2018): Hron et al. 2002); Hu et al. (2023) study incentive design in online recommendation and are interested in incentivizing agents to contribute high-quality content. They differ to our work primarily in that either the strategies are directly observable, or no bandit learning together with incentive design performed simul- taneously. There is also a multitude of additional work on auction-based mechanism design with unknown agent values and bandit feedback (Gatti et al. 2012 Nazerzadeh et al. 2016 Kandasamy et al. 2023 e.g.). Similar to the previously discussed auction design in MABs (Babaioff al. 2009 Devanur and Kakade 2009: Babaioff et al.) 2015). Gao et al. (2021) study an auction- based combi- natorial multi-ane armed bandit with payments, where each arm misreport the cost for its selection.
Other related areas of research are dynamic mechanism design (Pavan et al. 2014 Bergemann and
Välimäki 2019) well online mechanism design (Parkes 2007).
28

---

Published as a conference paper at ICLR 2024
I
FUTURE WORK
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 consider multi-slot recommendations in which the learner selects a subset of arms every round and the selected arms compete for the click (and our observations are therefore relative). In fact, the case where the learner selects set of arms and each arm i clicked with probability s; independently of the other arms can be handled with exactly the same methods as presented in this paper. More generally, we believe that the idea of introducing a screening rule based on confidences of each arm't 's strategy can be extended various settings and many of our techniques reused.
29


Reviews:
[{"review_id": "GV8PVuQtEP", "reviewer": "Reviewer_cU9Z", "summary": "The paper defines the strategic click-bandit problem, modeling strategic agents represented by arms in classic MAB setting, who are able to choose a click-rate strategically to maximize the utility of themselves under learner's learning policy. It is proved that classic incentive-unaware learning algorithms will fail in this new setting, and an incentive-aware learning algorithm, UCB-S, which elimates arms based on UCB according to the estimations for optimal click-rates and utilities, is proposed. UCB-S is shown to achieve sublinear regret bound uniformaly in every Nash equilibrium among arms.", "questions": "Please comment on Weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The model of strategic click-bandit quite novel and interesting. \n2. The theoretical analysis, including ones for incentive-unaware algorithm, new proposed UCB-S, is concrete.\n3. The experiments show the robustness of the new proposed algorithm, given each arm running greedy gradient descent.", "weaknesses": "1. The motivation of the propose strategic click-bandit setting, modeling recommandation systems, is not quite convincing. Basically, vendors are willing to choose proper item descritions to improve its click-rate, but they are not able to controll the click rate. Especially in the motivated example of clickbait, such a behavior is definitely harm the click-rate in long time. However, in proposed the bandit setting, each arm chooses the click-rate arbitrarily and such a probability will be fixed forever.\n2. The theoretical analysis is based on the assumption that Nash equilibrium can be achieved by arms, which may be not realistic. On the other hand, the setting in the experiments that each arm optimize itself by gradient descend would be more realistic one, but maybe much harder to obtain theoretical result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ED3TR7SaUE", "reviewer": "Reviewer_Se7C", "summary": "The authors study a strategic MAB problem named strategic click-bait. The application scenario of this problem is the online recommendation systems where the content creators or item providers can strategically manipulate the click rate of the items to any arbitrary value between 0 and 1, where the platform aims to achieve high click through rate as well as the consistency between an item's click through rate and the expected reward (normalized) of the item. The authors show that there exist multiple equilibria in the system and propose the UCB-S (UCB with screening) algorithm to penalize the agents for choosing click rates higher than the estimated reward, and proved that the algorithm has \\Tilde{O}(\\sqrt{ KT }) regret bound in every equilibrium, which outperforms incentive unaware MAB algorithms.", "questions": "Besides questions in the weaknesses, I have the following questions:\n\n1. Will adding a fixed-length cold-start process keep the same regret bound and reduce the false elimination rate of truthful agents?\n2. In a more realistic setting, the agents will need to compete for high click rates, how would you model the problem in this case?\n3. What application scenarios other than online recommendations are suitable for implementing UCB-S?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Despite some discussion on certain details being missing, the overall presentation is good. The problem settings, algorithm, and main results are clearly presented. I haven't checked all the proof details but the theorems follow the intuition.", "weaknesses": "1. The problem setting where the arms can arbitrarily manipulate their click rates from 0 to 1 is an unrealistic assumption. In most real-world online recommendation systems, it is impossible for the item to get arbitrarily close to 1 click rate. There will be limits on the number of items that can appear on the webpage and there will be competition among the item providers, either through sponsors or genuinely improving the item's quality. Due to the limit, only some items will get high click rates but not all. I think the strategic MAB problem is more like an information elicitation problem than a strategic recommendation problem.\n2. The UCB-S algorithm is also unrealistic since the punishment is too harsh for any commercial platform. Specifically, the agents are permanently eliminated the first time their report doesn't fall into the estimated expected reward range, and such elimination can be false positives, especially in the early stages of the system. Such false positive eliminations can cause severe regression in brand reputation. I suggest the authors propose alternative solutions that may involve some fixed-length cold-start process to reduce the false positive occurrences or penalize the agents in different ways (like eliminating for a certain period of time instead of permanent elimination), and present the regret bound for the alternatives.\n3. It is not easy to understand how the strategic setting in this work is different from previous works in strategic MAB, the authors should consider adding a table with each work's setting, assumptions, solution existence/uniqueness, convergence, and regret bounds to help the readers better understand the novelty.\n4. Some details should be elaborated\n(1). What is the characterization of NE under the incentive unaware platform? Is it the largest expected reward agent always plays 1 and other agents are indifferent about their strategies? If so, how does this correspond to the result in Figure 3?\n(2). Why is UCB-S having higher regret in the early stages than UCB in Figure 4? How is the y-axis value computed?\n(3). Under what conditions the NE under UCB-S are pure strategy NE/mixed strategy NE?\n5. Minor typo: page 4, \"(A3) then ensures that the from the perspective\" -> \"(A3) then ensures that from the perspective\"\n\nI'm on the fence and I think my rating is 5.5, exactly on the borderline since the limitations in the problem setting is really making the UCB-S unrealistic in actual production. I think the theoretical results are interesting, but this is conditioned on my limited experience with the MAB literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wzDdcJjQoR", "reviewer": "Reviewer_byQz", "summary": "The authors study the problem of combating clickbait via incentive design in a multi-arm bandit framework. The vendors in the system (e.g., content providers in a recommender system) are modeled as strategic arms. Each vendor/arm has a bernoulli reward distribution with fixed mean, and can choose their clickthrough rate. There is a tradeoff in the utility between higher CTRs (which yields higher engagement) and truthfully reporting a ctr that reflects the true reward (disincentivizing clickbait which is modeled as inflating the CTR for low quality content).\n\nThe authors show that ignoring vendor incentives can lead to high regret and design an incentive-aware modification of UCB based on thresholding the reported CTRs to derive low-regret guarantees. They characterize the equilibrium strategies of the agents. Finally, they validate the model and techniques via experiments.", "questions": "I would mainly like to hear the authors thoughts on the first two points in the \"weaknesses\" section. Namely, (1) How would one go about relaxing the assumption that CTR is a chosen quantity? (2) Can the model be extended to a setting with learning agents who have some degree of flexibility in changing the arm's mean reward?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The model, while certainly quite stylized, is a neat first step in formulating the incentive issues that arise due to clickbait in the language of bandits. The model is motivated well and explained clearly. The writing is crisp and clear and the paper is overall a pleasure to read. Ultimately I think the paper makes a clear contribution to a growing area of interest; the model, while stylized, is important and will pave the way for future work on aligning vendor incentives with the overall health of the ecosystem.", "weaknesses": "Why does the strategic agent behind an arm get to choose the CTR? Is that a realistic assumption? For example, how could a video creator on Youtube choose their CTR? They could direct effort into improving their content which could contribute to increasing CTR, but allowing the agent to choose the CTR as a fixed value seems like a fairly unrealistic assumption. \n\nThe strategic aspect is interesting, but one limitation of the model is that the agents are in a sense “stuck” at their particular reward mean $\\mu_i$. So an agent’s incentive is solely based on strategically choosing a CTR based on the mechanics of the utility function and learning algorithm. But you would expect that realistically an agent might also put in effort into improving $\\mu_i$ (e.g., by improving or changing the quality/genre/tone of content they are producing in a recommender system setting). I feel like that’s an important component that would make this model more compelling, and studying the interplay between clickbait actions (strategically choosing $\\mu_i$) and quality-improving actions would be very interesting.\n\nI also think some more work and thought needs to be given on the formulation of agent utilities. The present results hold under some assumptions on utilities like Lipschitnzess and monotonicity of maximizers, and the utility is also based on a single-shot report of the strategically-chosen CTR which seems like a limiting assumption since the agents would probably change their behavior across time steps. But these aspects can be a good direction for future work and doesn’t diminish my opinion of the paper too much.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "otXMvbALpm", "reviewer": "Reviewer_KcYc", "summary": "This paper proposes a stochastic bandit problem that models a practical situation where vendors in recommendation platforms exaggerates the true values of their products (arms) to increase CTR, which is inconsistent with the objective of recommendation platforms to find an arm $i$ that maximizes a learner's utility $u(s_i, \\mu_i)$, where $s_i$ stands for CTR and $\\mu_i$ stands for the true mean reward.\n\nThe paper aims to design an algorithm that minimizes strong and weak strategic regrets in the face of strategic vendor behavior (i.e., vendors are aware of the algorithm and strategically select the arm CTR before running the algorithm).\nThe paper presents an algorithm UCB-S, which maintains a set of arms that are estimated not ``clickbaiting'' with high confidence, and runs UCB among arms in the set.\nProblem-dependent and problem-independent strong strategic regret upper bounds of UCB-S are both proved to be sublinear over time.\nA weak strategic minimax regret lower bound is also provided.", "questions": "Modeling:\n* The proposed model assumes that arms are aware of the algorithm that the learner is going to run in advance. Is this realistic in practice? Further, it is assumed that arms will pick CTRs that form a NE in $NE(M)$, according to Theorem 5.2, does it imply that arms have to know $K$ and $T$ in advance? I recommend presenting how to pick CTRs to form a NE in $NE(M)$. If $K$, $T$, and algorithm $M$ are required to form a NE before running $M$, it appears that the assumption is too strong.\n* According to the description of Model 1, strategies $\\bf{\\it{s}}$ are picked in advance and stay fixed when running $M$, then, the goal of $M$ becomes maximizing learner's utility by estimating $\\bf{\\it{s}}$ and $\\bf{\\mu}$. In this case, why are we interested in strong and weak strategic regret, as they take into account the distribution of strategy selection while strategies are just unknown constants throughout the execution of $M$?\n\nAlgorithm design:\n* I did not see the explicit definition of $\\hat{\\mu}^t_i$. Is it an estimate of $\\mu_i$? If yes, then it is non-trivial to explicitly state how to get $\\hat{\\mu}^t_i$ by observing $c_{t, i_t}$ and $r_{t, i_t}$ at each round, and I wonder if Step 4 in UCB-S maximizing $\\bar{\\mu}^t_i$ aligns with the goal of maximizing $u(\\cdot)$.\n* The algorithm UCB-S only estimates strategies and eliminates bad arms that seem like clickbait, while arms are responsible to pick proper strategies that are less likely to get eliminated. Although it might be tricky for arms to pick strategies, it seems to me that the design of UCB-S is straightforward UCB.\n\nRegret analysis:\n* In Section 4, it is not surprising that $(s, \\mu)-$Oracle has linear weak strategic regret, since weak strategic regret considers the strategy distribution $\\bf{\\sigma}$ while the oracle considers only a realization of $\\bf{\\sigma}$ (In fact, UCB-S also considers a realization of $\\bf{\\sigma}$ instead of $\\bf{\\sigma}$, so I doubt whether UCB-S achieves sublinear strong strategic regret as stated in Theorem 5.3).\n* I cannot go through all the proofs, but I can hardly follow the proof of Proposition 4.1. In the first glance, it seems to me that the proof is self-contradictory: in Case 1, it is stated that $u(s'+\\varepsilon, \\mu_{i^*})<u^*_{j^*}$ with $\\varepsilon>0, s'+\\varepsilon\\leq 1$ contradicts the continuity of $u(s, \\mu)$ in $s$, while the proof of Case 2 is based on the statement $u(s'', \\mu_{i^*})<u^*_{j^*}$ with $s''>s'$. Please double check the proof.\n* Theorem 5.3 and Corollary 5.4 provide a problem-dependent and a problem-independent regret upper bound respectively. It is counterintuitive that the problem-dependent bound is larger than the problem-independent bound, as it is often the case that problem-dependent bound is smaller since it additionally takes into account distributional information.\n* As previously mentioned, UCB-S considers a realization of $\\bf{\\sigma}$ as a fixed unknown parameter, and performs straightforward UCB, so I feel like the problem-dependent regret upper bound in Theorem 5.3 can be tightened to order $\\log T$. It is of interest to provide a problem-dependent lower bound to show the tightness of the upper bound.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The considered problem of clickbait is common and of interest in both industry and academic. The formulation carefully models the learner's utility $u\\$ and arm utility $v$, that generalizes a large class of learner's objective.\n* It is novel to combine Nash equilibrium and arm strategy selection in bandit literature. I believe that it well captures the real-world situations where clickbaits are under detection.", "weaknesses": "* I feel like it would be more proper and much more interesting if the problem could be modeled by adversarial bandit. Current setting assumes that arms decide their own strategies with knowledge of algorithm in advance (which seems strong to me), and the algorithm is a plain UCB estimating fixed $s$ and $\\mu$. However, this problem has the intrinsic of an adversarial strategy selection, that can be well captured by adversarial bandit, in which case, arms dynamically select strategies based on history and thus omit the requirement of knowing algorithm in advance. More importantly, adversarial bandit constructs the interaction between arm strategy selection and learner recommendation/elimination, thus captures real trade-off between incentivizing all arms to be truthful and recommending only the best arms, while current model does not.\n* There is confusion in algorithm design and many counterintuitive regret analysis (which I have listed in Questions), that make me doubt the soundness of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)