Strategic Linear Contextual Bandits
Authors: Thomas Kleine Buening
Aadirupa Saha
Christos Dimitrakakis
Haifeng Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: bandits
mechanism design
online learning
incentive-aware learning
Primary area: bandits
TL;DR: We combine online learning with approximate mechanism design in a strategic variant of the linear contextual bandit problem, where the arms can strategically manipulate contexts.

Abstract: Motivated by the phenomenon of strategic agents gaming a recommender system to maximize the number of times they are recommended to users, we study a strategic variant of the linear contextual bandit problem, where the arms can strategically  misreport privately observed contexts to the learner. We treat the algorithm design problem as one of *mechanism design* under uncertainty and propose the Optimistic Grim Trigger Mechanism (OptGTM) that incentivizes the agents (i.e., arms) to report their contexts truthfully while simultaneously minimizing regret. We also show that failing to account for the strategic nature of the agents results in linear regret. However, a trade-off between mechanism design and regret minimization appears to be unavoidable. More broadly, this work aims to provide insight into the intersection of online learning and mechanism design.

Strategic Linear Contextual Bandits
Thomas Kleine Buening The Alan Turing Institute
Aadirupa Saha Apple ML Research
Christos Dimitrakakis University of Neuchatel
Haifeng Xu University of Chicago
Abstract
Motivated by the phenomenon of strategic agents gaming recommender system to maximize the number of times they are recommended to users, we study a strategic variant of the linear contextual bandit problem, where the arms can strategically misreport privately observed contexts to the learner. We treat the algorithm design problem one of mechanism design under uncertainty and propose the Optimistic Grim Trigger Mechanism (OpIGTM) that incentivizes the agents (i.e., arms) to report their contexts truthfully while simultaneously minimizing regret. We also show that failing to account for the strategic nature of the agents results in linear regret. However, trade-off between mechanism design and regret minimization appears to be unavoidable. More broadly, this work aims to provide insight into the intersection of online learning and mechanism design.
Introduction
Recommendation algorithms that select the most relevant item for sequentially arriving users or queries have become vital for navigating the internet and its many online platforms. However, recommender systems are susceptible to manipulation by strategic agents seeking to artificially increase their frequency of recommendation [31 33 38). These agents, ranging from sellers platforms like Amazon to websites aiming for higher visibility in search results, employ tactics such as altering product attributes engage in aggressive search engine optimization (29 32
By gaming the algorithms, agents attempt to appear more relevant than they actually are, often compromising the integrity and intended functionality of the recommender system. Here, the key issue lies in the agents' incentive to manipulate the learning algorithm to maximize their utility (i.e., profit). To address this challenge, we study and design algorithms in strategic variant of the linear contextual bandit, where the agents (i.e., arms) have the ability to misreport privately observed contexts to the learner. Our main contribution is connecting online learning with approximate mechanism design to minimize regret while, at the same time, discouraging the arms from gaming our learning algorithm.
The contextual bandit
is a generalization of the multi-armed bandit problem to the case where the learner observes relevant contextual information before pulling arm. It has found application in various domains including healthcare [37] and online recommendation 25 We here focus on the linearly realizable setting [1 (6), where each arm's 's reward is linear function of the arm's 's context in the given round. In the standard linear contextual bandit, at the beginning of round f, the learner observes the context क,, E Idd of every arm [K), selects
i, and receives reward drawn from a distribution with mean (0",",,, ) where f* E Rdd is an unknown parameter. In the strategic linear contextual bandit, we assume that each arm is seff-interested agent that wants maximize the number of times it gets pulled by manipulating its contexts.
More precisely, we consider the situation where each arm privately observes its true context xi,; every round, c.g., its relevance to the user arriving in round t, but reports a potentially gamed context vector 2t,4 to the learner. The learner does not observe the true contexts, but only the reported contexts
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

&,= (I..1...., Ft.KK } and chooses an action from this gamed action set X. When the learner pulls arm it, the learner then observes reward rt,s, drawn from a distribution with mean (0" ,,,,, In other words, the arms can manipulate the contexts the learner observes, but cannot influence the underlying reward. This often the case as superficially changing attributes or meta data has no effect on an item's 's true relevance to a user.
In summary, our contributions are:
We introduce a strategic variant of the linear contextual bandit problem, where each arm, in every round, can misreport its context to the learner to maximize its utility, defined as the total number of times the learner selects the arm over I rounds (Section B). We demonstrate that incentive-unawar algorithms, which do not explicitly consider the incentives they (implicitly) create for the arms, suffer linear regret in this strategic setting when the arms respond in Nash Equilibrium (NE) (Proposition 3.3). This highlights the necessity of integrating mechanism design with online learning techniques to minimize regret in the presence of strategic arms.
We begin with the case where 9 is known the learner in advance (Section 4. This simplifies the problem setup, allowing us to establish fundamental concepts while highlighting the challenges of designing a sequential mechanism without payments. For this scenario, we propose the Greedy Grim Trigger Mechanism (GGTM), which incentivizes the arms to be approximately truthful while minimizing regret. We show that (a) Truthful reporting is an (VT))-E for the arms (Theorem 4.1p and (b) GGTM has O(K2/K regret under every NE of the arms (Theorem 4.2)
Next, we consider the case where 0* is unknown to the learner in advance (Section 5). Without access to the true contexts, estimating accurately appears intractable, as the arms can manipulate the estimation process. Surprisingly, we show that learning 0* is not necessary for minimizing regret in the strategic linear contextual bandit. We construct confidence sets (which may not contain 0*) ) to derive pessimistic and optimistic estimates of our expected reward. These estimates are used to construct the Optimistic Grim Trigger Mechanism (OptGTM). Despite possibly incorrect estimates of f", OptGTM bounds the impact of misreported contexts both regret and the utility of all arms. We show that (a) Truthfulness is an O(dv -T) for which OptGTM has regret (d KT) (Theorem 5.1 and (b) OptGTM incurs at most Öddk² 2 (oddkv/TT) VKT) regret under every NE of the arms (Theorem 5.2
Finally, we support our theoretical findings with simulations of strategic gaming behavior in response to OptGTM and LinUCB (Section 6 We simulate how strategic arms adapt what contexts to report over time by equipping the arms with decentralized gradient ascent and letting the arms (e.g., vendors) and the learner (e.g., platform) repeatedly interact over several epochs. The experiments confirm the effectiveness of OptGTM and illustrate the shortcomings of incentive- unaware algorithms, such as LinUCB.
2 Related Work
Linear Contextual Bandits. In related work on linear contextual bandits with adversarial reward coruptiion (3 (5). an adversary corrupts the reward observation in round t by some amount co but not the observed contexts. In this problem, the optimal regret is given by O(dvT + dC), where C== Ee |cal is the adversary's budget. To the best of our knowledge, adversarial context corruptions have only been studied by (8), who achieve (dCVT) regret with C = Et, 1/,,;, xt,ill where o and F are the true and corrupted contexts, respectively. In contrast, we do not assume a bounded corruption budget so that these regret guarantees become vacuous (cf. Proposition 3.3 Moreover, instead of taking the worst-case perspective of purely adversarial manipulation, we assume that each arm is a self-interested agent maximizing their own utility.
Strategic Multi-Armer Bandits. Braverman et al. 4 were the first to study a strategic variant of the multi- nuldi-armed bandit problem and considered the case where the pulled arm privately receives the reward and shares only fraction of it with the learner. An extension of this setting has recently been studied in [1]. In other lines of work, 9 [3] study the robustness of bandit learning against strategic manipulation, however, simply assume a bounded manipulation budget instead of performing mechanism design. [II 355 consider multi-armed bandits with replicas where strategic agents can submit replicas of the same arm to increase the number of times one of their arms is pulled. Buening et al. [5] combine multi-armes bandits with mechanism design to discourage clickbait in online

---

Interaction Protocol 1: Strategic Linear Contextual Bandits
Learner publicly commits to algorithm M
for I. 1...., do
Every arm E [K] privately observes its context .t,e E IRd
Every amm E [K] reports a (potentially gamed) context Fa,s E R' to the learner
Learner observes the gamed contexts Xx ( selects arm is [K]. and receives reward
T1i == (0" -7.5,) +
where 1/t is zero-mean aab-Gaussian noise, Note that the reward is generated with respect to the unknown parameter 0* E R2 and the unobserved true context 27,6
recommendation. In their model, each arm maximizes its total number of clicks and is characterized by strategically chosen click-rate and a fixed post-click reward. However, all of these works substantially differ from work in problem setup and/or methodology.
Modeling Incentives in Recommender Systems. A complementary line of work studies content creator incentives recommender systems [16 21 22 23
42 and how algorithms shape the behavior of agents more generally (7]. These works primarily focus on modeling content creator behavior and studying content creator incentives under existing algorithms. Instead, our goal the design of incentive-aware learning algorithms which incentivize content creators (arms) to act in desirable fashion (truthfully) while maximizing the recommender system's 's performance.
27
40
41
Strategic Learning. We also want to mention extensive literature on strategic learning 14
18 19 26
17 34 36). Similarly to the model we study in this paper, the premise is that rational agents strategically respond to the learner's s algorithm (c.g.. classifier) to obtain desired outcome. However, the learner interacts with the agents only once and the agents are assumed to be myopic and to suffer a cost for, e.g., altering their features. Moreover, there is competition among the agents like in the strategic linear contextual bandit. In contrast to these works, we wish to design a sequential (online learning) mechanism to incentivize truthfulness, which is only possible because repeatedly interact with the same set of agents (i.e., arms).
43 [4] and strategic classification [10
Strategic Linear Contextual Bandits
We study a strategic-variant of the linear contextual bandit problem, where K strategic agents (i.e., arms) aim maximize their number of pulls by misreporting privately observed contexts to the learner. The learner follows the usual objective of minimizing regret, i.e., maximizing cumulative rewards, despite not observing the contexts. We here focus the where the strategic arms respond in Nash equilibrium to the learning algorithm. The interaction between the environment, the learning algorithm, and the arms is specified Interaction Protocol [
Notice that the arms can manipulate the contexts that the learner observes (and the learner only observes these gamed contexts and never the actual contexts), but the rewards are generated w.r.t. the true contexts. Moreover, if all arms are non-strategic and irrespective of the learning algorithm report their features truthfully every round, i.e., 24,5 x for all (t, i) E [T' x [K], the problem reduces to the standard non-strategic linear contextual bandit.
3.1 Strategic Arms and Nash Equilibrium
We assume that each arm reports possibly gamed context 2,,; the learner after observing its true context 27,, and potentially other information. For example, the arms may have prior knowledge of 6* and observe the identity of the selected arm the end of each round. However, we do not use any specific assumptions about the observational model of the arms. Our results can be viewed worst-case analysis over all such models. For concreteness, consider the case where the arms have prior knowledge of 8" and, at the end of every round, observe which arm was selected and the generated reward]
'ee naturally expect that the more information the arms observe each round, the more challenging the problem becomes for the learner, the arms' ability manipulate the learning algorithm increases.
3

---

Let o; be (mixed) strategy of arm i that is observed true contexts zi, to a distribution over reported contexts 2τ, R We define a-; as the strategies of all arms except i and define a strategy profile of the arms = (0)..... ,...).,,)))). We call arm truthful if truthfully reports privately context every round, i.e., de, = Fi, for all E [7]. This truthful strategy is denoted of and we let o²
and in every round maps from
We now formally define the objective of the arms. Let re)(1) Σi= 1( i} be the number of times arm pulled by the learner's algorithm M. The objective of every arm maximize the expected number of times it is pulled by the algorithm given by
Ue M, or) = EM [ (1) o))
where we condition on the arm strategies a as these will (typically) impact the algorithm's 's decisions. We assume that the arms respond the learning algorithm M in Nash Equilibrium (NE).
Definition 3.1 (Nash Equilibrium). We say that o = (o1....,ok .K) forms NE under the learner's algorithm M if for all i E [K] and any deviating strategy of:
Es [r( of, 0-1] 2 EM (nr(i) o..
Let NE(M) == (o: a is a NE under M) be the of NE under algorithm M. We also consider E-NE, which relax the requirement that no arm has an incentive to deviate.
Definition 3.2 (c-Nash Equilibrium). We say that (a1 (o forms e-NE under algorithm M if for all i E [K] and any deviating strategy a':
EM (mr( oo 00. 2 EM [nr(i) of 0-1
3.2 Strategic Regret
In the strategic linear contextual bandit, the performance of algorithm depends the strategies that it incentivizes. Naturally, minimizing regret when the arms always report their context truthfully easier than when contexts manipulated adversarially. We interested in the strategic regret of an algorithm M when the arms act according to Nash equilibrium under M. Formally, for E NE(M) the strategic regret of M defined as
T Σ
Rr =EM,o
10 m1,
(0" xT..)))
where i = argmax,e[K]] (0", = is the optimal arm in round (. The regret guarantees of our algorithms hold uniformly over all NE that they induce, i.c., for maXoeNE(M) (r (M,o).) σr).
Regularity Assumptions. We allow for the true context vectors oi,; to be chosen adversarially by nature, and make the following assumptions about the linear contextual bandit model. We assume that both the context vectors and the rewards are bounded, i.e., max (0", xr. =t,)) < and | ||2 1 for all & [T]. Moreover, assume constant optimality gap. That is, letting Ar,
2,37 ). we assume that ming,;A, Ar, is constant.
3.3 The Necessity of Mechanism Design
The first question that arises this strategic setup is whether mechanism design, i.e., actively aligning the arms' incentives, is necessary to minimize regret. As expected, find that this is the case. Standard algorithms, which are oblivious to the incentives they create, implicitly incentivize the arms to heavily misreport their contexts which makes minimizing regret virtually impossible.
We call a problem instance trivial if the algorithm that selects an arm uniformly at random every round achieves sublinear regret. Conversely, call problem instance non-trivial if the uniform selection suffers linear expected regret. show that being incentive-unaware generally leads to linear regret in non-trivial instances (even when the learner has prior knowledge of 6*).
Proposition 3.3. On any non-trivial problem instance, the incentive-unee weeawiiveunwwrre greedy algorithm that in round I plays it argmaxie[K] (0", x1.5) (with ties broken uniformly) suffers linear regret ()T) when the arms act according to any Nash equilibrium under the Note that the incentive scenttve-unaware unaware greedy algorithm has knowledge of 0".
greedy algorithm.

---

Mechanism 1: The Greedy Grim Trigger Mechanism (GGTM)
initialize: A [K]
for t ,,..., do
Observe reported contexts It, Kt,K
Play the (active) arm with largest reported reward: i, argmax,ea, 24,))
Observe reward Fr,i, from playing arm it-
6
if Eest: i (0" ,Te,..) > UCB,(f then
ie=i,
Eliminate arm i, from the active set: A A, Mie).
if A = then
Stop playing any and receive zero reward for all remaining rounds.
Similarly, algorithms for stochastic linear contextual bandits (LinUCB N ol) and algorithms for linear contextual bandits with adversarial context corruptions (RobustBandi (8)) suffer linear regret when the arms act according to any Nash equilibrium that the algorithms incentivize.
Proof Sketch. We demonstrate that the only NE for the arms lies in strategies that myopically maximize the probability of being selected in every round, which results in linear regret for the learner, because all arms always appear similarly good. The proof can be found in Appendix B
Another natural question to ask is whether exact incentive-compatiiiiy is possible in the strategic linear contextual bandit. A learning algorithm called incentive comppatiee if truthfulness a NE, i.e., reporting the true context i Ft every round is maximizing each arm's 's utility [14] 30) For the interested reader, in Appendix A we provide an eerentive-compatiin
algorithm with constant regret in the fully deterministic case, where 8" is known priori as well as the rewards of pulled arms directly observable. However, when is unknown and/or the reward observations are subject to noise, we conjecture that exact incentive-compatibity (i.e., truthfulness is an exact NE, not g-NE) is irreconcilable with regret minimization (ef. Appendix A).
4 Warm-Up: 0t is Known in Advance
There are a number of challenges in the strategic linear contextual bandit. The most significant one is the need to incentivize the arms to be (approximately) truthful while simultaneously minimizing regret by learning about 6" and selecting the best arms, even when observing (potentially) manipulated contexts. Notably, Proposition 3.3 showed that we fail to align the arms' incentives, minimizing regret becomes impossible. Therefore, in the strategic linear contextual bandit, we must combine mechanism design with online learning techniques.
The uncertainty about 0* poses serious difficulty when trying to design such incentive-aware learning algorithms. we only observe Tt,; and r., = (0", xx7,,) + T/, but do not observe the true context ui,;, accurate estimation of 0* is extremely challenging (and arguably intractable). We go into more depth in Section S when we introduce the Optimistic Grim Trigger Mechanism. For now, we consider the special case when 0" is known to the learner in advance. This lets us highlight some of the challenges when connecting mechanism design with online learning in a less complex setting and introduce high-level ideas and concepts. When 8* is known in advance, it can be instructive to consider what we refer to as the reported (expected) reward (8", .I..)) instead of the reported context vector ; itself. Taking this perspective, when arm i reports d-dimensional vector Ft,i, we simply think of arm i reporting a scalar reward (0", x4.;). In what follows, it will prove useful to keep this abstraction in mind
4.1 The Greedy Grim Trigger Mechanism
One idea for a mechanism to use a grim trigger. In repeated social dilemmas, the grim trigger strategy ensures cooperation among self-interested players by threatening with defection for all remaining rounds if the grim trigger condition is satisfied (28). Typically, the grim trigger condition defined so that it immediately satisfied if player defected least once.
WW use the expressions 'reported reward' and eexeetedd reward" interchangeably to mean the reward we would expect observe based on the context reported by the
5

---

In the strategic contextual bandit, from the perspective of the learner, an arm can be considered to 'cooperate" if it is reporting its context truthfully. In turn, an arm 'defects' when it is reporting a gamed context. However, when an arm is reporting some context Tt,; we do not know whether this arm truthfully reported its context or not, because we do not have access to the true context oi, For this reason, we instead compare the expected reward (0", ,Te,,) and the true reward (0", Fi,)) While we also cannot observe (0", xi,5) directly, we do observe Te, = (0" a + Tpp
Grim Trigger Condition. Intuitively, if for any arm i the total expected reward Eest: iz= (0", zg,s) is larger than the total observed reward fz,i == Eese: iema Te, then arm must have been misreporting its contexts. However, re, == (8", .Z,z)) + The is random so that we instead use the optimistic estimate of the observed reward given by
(f,)) = Σ
Te, + 2 n. (og
(1)
where (in lT) is the confidence width which can be derived from Hoeffding's inequality. To implement the grim trigger, we then eliminate arm i in round if the total expected reward is larger than the optimistic estimate of the total observed reward, i.e.,
Eigns ie= (0" xe,1) (f..)
Note that using the optimistic estimate of the total observed reward ensures that elimination justified with high probability. Conversely, we can guarantee with high probability that we do not erroneously eliminate a truthful arm.
Selection Rule.
To complete the Greedy Grim Trigger Mechanism (GGTM, Mechanism 1. then combine this with a greedy selection rule that pulls the arm with largest reported reward ,0,, .x.) in round from the set of arms that we believe have been truthful so far. Interestingly, even though we here assumed 0" to be known in advance, we see that GGTM still utilizes online learning techniques such the optimistic estimate ① align the arms' incentives.
is also worth noting that-similaa to its use in repeated social dilemmas -uur grim trigger mecha- nism is mutually destructive in the sense that eliminating an arm for all remaining rounds is inherently bad for the learner (and of course for the eliminated arm as well) Here lies the main challenge of the mechanism design and we must ensure that the arms are incentivized to "cooperate" (i.e., remain active) for a sufficiently long time.
4.2 Regret Analysis of GGTM
In what follows, we assume that each arm's 's strategy restricted to reporting their 'reward' x not strictly lower than their true (mean) reward (0","r" ".,,)) ) It seems intuitive that no rational arm would ever under-report its value to the learner and make itself seem worse than it actually is. However, there
are special cases, where under-reporting allows arm to arbitrarily manipulate without detection.
We discuss this later in Remark 4.3 and, more extensively, in Appendix C
Assumption 1. We assume that z0,) 2 (0",xI,) for all (t, i) E [T] x [K].
We now demonstrate that GGTM approximately incentivizes the arms to be truthful in the sense that the truthful strategy profile o* such that 24,, 2²,, for all (t, 2) E [T] X [K] is an Ö(VT)-NE under GGTM. When the arms always report truthfully and no arm is erroncously eliminated, the greedy selection rule naturally selects the best arm every round so that GGTM's 's regret is constant.
Theorem 4.1. Under the Greedy Grim Trigger Mechanism, being truthful is a D(VT)-NEfo for the arms. The strategic regret of GGTM when the arms act according to this equilibrium at most
RTGGGTM, σ²) < 1/T.
Proof Sketch. By design of the grim trigger, it is straightforward to show that the probability that a truthful arm gets eliminated at most 1/7².. Moreover, the grim trigger ensures that no arm can "poach' selections from a truthful arm more than order vT times by misreporting its contexts. This achieves two things: (a) it protects truthful arms and guarantees that truthfulness a good strategy, and (b) limits an arm's 's profit from being untruthful. The proof can be found in Appendix D.2
Note that in linear contextual bandits there is no single optimal arm, but the optimal arm changes per round.

---

The problem of estimating the unknown parameter 0" appears daunting given that the arms can strategically alter their contexts to manipulate our estimate of l to their advantage. In fact, imagine an arm manipulating its contexts orthogonal to 0" so that (0" Zz.i z 0 but Fy,i * x Observing only zt.; and Tt,; = (0", .x..)) + The our estimate of 6" becomes biased and could be arbitrarily far off the true parameter 8* even though the gamed context and true context have the same reward w.r.t. 8* This is also the case more generally. Since we observe neither 6" nor oi any incentivize the arms Theorem 4.1
tells us that truthfulness is an approximate NE. We now also provide more holistic strategic regret guarantee of O(K2VKI in every Nash equilibrium under GGTM. Proving this is more complicated as the arms can profit from exploiting our uncertainty about their truthfulness (i.e., the looseness of the grim trigger).
Theorem 4.2. The Greedy Grim Trigger Mechanism has strategic regret
(G =0 VKT (Tg()
K2 KT K log
(2)
cost of mmmiipplation
cost of mechonism design
for every a E NE(GGTM). Hence, maXGENE(GGTM Ry (GGG,, Ö(K-VKT)
Sketch. Sketch. must bound the regret due to the arms exploiting our uncertainty as well as the cost of committing to the grim trigger. Both of these quantities do play role when the arms always report truthfully (like in Theorem 4.1. A complete proof can be found in Appendix D
The regret analysis is notably more complicated than the one in Theorem 4.1
The regret bound suggests that there two sources of regret. The first term is due to our mechanism design being approximate (relying on estimates), which leaves room for the arms to exploit our uncertainty and misreport their contexts to obtain additional selections. The second part of (2) is the cost of the mechanism design, i.c., the cost of committing to the grim trigger. We suffer constant regret any round in which the round-optimal arm no longer in the active set. In the worst-case, this quantity is of order K2 KT.
Remark 4.3. We want to briefly comment on Assumption 7 appears intuitive that any rational arm would never under-report its value, i.e., make itself look worse than it actually is. However, in Appendix G we provide a simple example where occasionally under-reporting its value allows an arm to simulate an environment where it is always optimal, even though it is in fact only optimal half of the time. We will explain in the example that without additional strong assumptions on the noise distribution the two environments are indistinguishable so that such manipulation by the arms appears unavoidable when trying to maximize rewards.
5
The Optimistic Grim Trigger Mechanism
observed combination of rt,; and Ft, will "make sense" to us. But, how to report truthfully and minimize regret despite incorrect estimates of 0*?
Our key observation is that learning 0² is not necessary to incentivize the arms minimize regret; it appears to be hopeless endeavour after all. The idea of the Optimistic Grim Trigger Mechanism (OpIGTM, Mechanism 2 is to construct pessimistic estimates of the total reward we expected from pulling an arm. Importantly, we can construct such pessimistic estimates of the expected (i.c., "reported") reward even when the contexts are manipulated. OptGTM then threatens arms with elimination if our pessimistic estimate of the expected reward exceeds the optimistic estimate of the observed reward. Interestingly, this does not relate to the amount of corruption in the feature space vi,lll2 could become arbitrarily large. However, it does bound the effect of each arm's 's strategic manipulation on the decisions we make and thereby allows for effective incentive design and regret minimization.
and, in fact, Ee,llar..
To construct pessimistic (and optimistic) estimates of the expected reward, we use independent estimators Ōr,: and confidence sets Ct,; around 0r,,, which do not take into account that the contexts are potentially manipulated. That is, we have a separate estimator and confidence set for each arm i [K]. This will prevent one arm influencing the elimination of another. also stops collusive arm behavior, where majority group of the arms could dominate and steer estimation process.
7

---

Mechanism 2: The Optimistic Grim Trigger Mechanism (OptGTM)
initialize: A [K]
for t ,,..., T do
Observe reported contexts X; = I , Tt,
Play the active arm with largest reported optimistic reward
d argmax (CL.), SEA,
Receive reward Fr, from playing arm it if Eese:: iem LCBr,,, (Ir,i.) > (f,,( then
Eliminate arm i, from the active set: A-- A. (ic).
if A = 0 then
Stop playing any and receive reward for all remaining rounds.
Confidence Sets. For every arm E [K] we define the least-squares estimator di, w.r.t. its reported contexts and observed rewards before round as
Oz,
argmin DERd
(Eeer fe=i (10, re,s) + +211013)
where À O. We then define the confidence set Ct,i {0 E IRd: |0., O S Be,z) where Gr, = Odd (o)())(())) is the confidence size. Here, Ve,i is the covariance matrix of reported contexts of arm given by V1,i = A/ and Vr, = Al Eest: iz= We..
It is well-known that if the contexts were always reported truthfully, i..., Tz,; = x. then with high probability 8" E Ct.s. But, if the sequence of reported contexts 24,5 substantially differs from the true contexts zi,; there is no (high probability) guarantee that the true parameter 0* is element in Ct. In the literature on learning with adversarial corruptions (in linear contextual bandits), the standard approach deal with this widen the confidence set. However, for this to be effective we would need to assume a sufficiently small corruption budget for the arms and prior knowledge of the total amount of corruption, both of which we explicitly do not assume here.
Slightly overloading notation, we instead define the optimistic and pessimistic estimate of the expected reward of context vector w.r.t. arm i
(C),,,() = (ō.,,, x) + / /e, and LCB,,,()) = (0,, x))
Ve,ill=lly
We chose to state these estimates using additive bonuses. However, it can be convenient to think of them as (r) ~ maxøec,, (8, x) and (CB,,(z) minsec,, (f,
Grim Trigger Condition. In round E [T], we eliminate arm i from A, if the pessimistic estimate using the reports is larger than the optimistic estimate using the total observed reward, i.e.
Σ
(10E.) -aleeaaadBBBellllll Bellxe.lllvz)
Σ 8
Te. + 2 log()))
In other words,
L.B., > (F..)
Examining the left side of 44. the careful reader may wonder why we do not simply use our latest and arguably best estimate d,,s, but instead the whole sequence of "out-dated" estimators te, from previous rounds. In fact, this is crucial for the grim trigger. Using êr, renders the grim trigger condition ineffective, because, by definition, 0r, is the (least-squares) minimizer (3) of the difference between Ete: و (0.., Zi..)) and Σtst: i,= Tt,s. Hence, when using Or,; the grim trigger condition may not be satisfied even when the arms significantly and repeatedly misreport their contexts.
We complete the OptGTM algorithm by selecting arms optimistically with respect to each arm's own estimator and confidence set. That is, OptGTM selects the active arm with maximal optimistic (expected) reward UCB,, = (0r, It.i) + / //,, in round t. We see that
Selection Rule.
For more details on the design of least-squares estimators and the confidence sets, we refer to Abbasi- Yadkori al. M and Lattimore and Szepesvári [2]] (Chapter 20).

---

the grim trigger 44 incentivizes arms to ensure that over the course of all rounds & is not much smaller than rt.i (0" 2. + тΙ- Hence, (Z,,,, is also not substantially smaller than the true mean reward (0", x.,)) This suggests that playing optimistically is good strategy for the learner as long as the selected arm does not satisfy (4).
5.1 Regret Analysis of OptGTM
When 0* was known to the learner in advance, we assumed that the arms never report value smaller than their true value, i.e. (0", ,T,,) 2 (0", , for all (t, E [T] x [K] Now, when 0* is unknown to the learner, we similarly assume that the arms do not report their optimistic value less than their true value. Again, it seems intuitive that in any given round, no arm would under-report its worth.
Assumption 2. We assume that maxgec.,, (0, 2 (0", . for all (t, i) E [T] x [K].
We find that OptGTM approximately incentivizes the arms be truthful and, when the arms report truthfully, OptGTM suffers most (dv/KT regret.
Theorem 5.1. Under the Optimistic Grim Trigger Mechanism, being truthful is Öld KT K When the arms report truthfully, the strategic regret of OptGTM under this approximate NE is at most
(OpIOIT o²) ((v(dd)))
The optimal regret in standard non-strategic linear contextual bandits is (dv that OpIGTM is optimal up to factor of v K (and logarithmic factors) when the arms report truthfully. The additional factor of /K is caused by the fact that OptGTM maintains independent estimates for each arm. We now also provide a strategic regret bound for every NE of the arms under OpIGTM.
Theorem 5.2. The Optimistic Grim Trigger Mechanism has strategic regret
Rr(OpIGTM, o) = (a +ooo))))k"++
for every a E NE(OPIGTM), Hence, max (NE(QGGTM)) Rr = Ô [dK<VKT
The proof ideas of Theorem 5. and Theorem 5.2 are similar to their counterparts in Section The main difference lies in more technically challenging analysis of the grim trigger condition We also see that in contrast to non-strategic linear contextual bandits, where the regret typically does not depend the number of arms K, Thhorem [.1 and Theorem 5.2 include factor of K and K2vK, respectively. A dependence on K is expected due to the strategic nature of the arms which forces us explicitly incentivize each arm be truthful. However, we conjecture that the regret bound in Theorem 5.2 is not tight in K and expect the optimal dependence on the number of arms to be VK. The proofs of Theorem 5.1 and Theorem 5.2 can be found in Appendix
Experiments: Simulating Strategic Context Manipulation
We here experimentally analyze the efficacy of OptGTM when the arms strategically manipulate their contexts in response to our learning algorithm. We compare the performance of OptGTM with the traditional LinUCB algorithm O which-as shown in Proposition 3.3 implicitly incentivizes
the arms to manipulate their contexts and suffers large regret when the arms are strategic.
Contrary to the assumption of arms playing NE, we here model strategic arm behavior by letting the arms update their strategy (i.e., what contexts report) based on past interactions with the algorithms. More precisely, we assume that the strategic arms interact with the deployed algorithm (i.e., OptGTM or LinUCB) over the course of 20 epochs, with each epoch consisting of T 10k rounds. At the end of each epoch, every arm then updates its strategy using gradient ascent w.r.t. its utility. Importantly, this approach requires no prior knowledge from the arms, they learn entirely through sequential interaction. This does not necessarily lead to equilibrium strategies, but serves as natural model of strategic gaming behavior under which to study the algorithms.
Experimental Setup. We associate each arm with a true feature vector yf E Rd (e.g., product features) and randomly sample a sequence of user vectors e E Rdd (i.e., customer features). We assume that every arm can alter its feature vector y by reporting some other vector yr, but cannot alter the user contexts G. We use a feature mapping (h) = Tt.s to map yi E Rd and e E Rda to an arm-specific context Tt. E IRd that the algorithm observes. At the end of every epoch, each arm then performs an approximated gradient step on yi w.r.t. its utility, i.e., the number of times selected. We let K = 5 and d dj d2 5 and average the results over 10 runs.

---

Q2tGTM
OstGTM Uercca
Rospros
130
100
1788
3000
(a) Total strategic regret frr as the arms adapt their strategies the de- ployed algorithm over the of 20 epochs.
(b) Epoch 0 (Truthful Arms); Regret function of before the arms have interacted with the deployed algorithm.
(c) Epoch 20 (Strategic Arms): Re- gret function of after the have interacted with the deployed algorithm.
Figure 1: Comparison of the strategic regret of OptGTM and LinUCB. The strategic arms adapt their strategies gradually over the course of 20 epochs. OptGTM performs similarly across all epochs, whereas LinUCB performs increasingly worse the arms adapt the algorithm (Figure Tap. Figure [ [nd [C] provide closer look at the regret of the algorithms across the ' rounds in the initial epoch, where the arms are truthful, and the final epoch after the arms have adapted the algorithms.
Results. In Figure Ta we observe that OptGTM performs similarly well across all epochs, which suggests that OpIGTM successfully discourages the emergence of harmful gaming behavior. contrast, as the arms adapt their strategies (i.e., what features to report), LinUCB suffers increas- ingly more regret and almost performs badly as uniform sampling in the final epoch. In epoch O, when the all arms are truthful, i.e., are non-strategic, LinUCB performs better than OpGGT (Figure Tb). This is expected as OpIGTM suffers additional regret due to maintaining independent estimates of 6* for each arm (as mechanism to incentivize truthfulness). However, OptGTM significantly outperforms LinUCB the arms strategically adapt, which most evident in the final epoch (Figure Icp. Interestingly, as already suggested in Section 3 OptGTM cannot prevent manipulation in the feature space (see Figure 2p. However, OptGTM does manage bound the effect of the manipulation on the regret (Figure Tap and, most importantly, the effect on the utility of the arms as well (Figure 3). As result, the arms are discouraged from heavily gaming their contexts and the context manipulation has only minor effect on the actions taken by OptGTM.
the Nrss cider Linkia
Figure 2: Context manipu- Figure 3: Utility of the arms
lation Er,1læi, vlai
for each of the 10 runs.
7 Discussion
We study a strategic variant of the linear contextual bandit problem, where the arms strategically misreport privately observed contexts maximize their selection frequency. To address this, design two online learning mechanisms: the Greedy and the Optimistic Grim Trigger Mechanism, for the scenario where 8* is known and unknown, respectively. We demonstrate that our mechanisms incentivize the arms to be approximately truthful and, in doing so, effectively minimize regret. More generally, with this work, we aim to advance our understanding of problems the intersection of online learning and mechanism design. As the digital landscape, including online platforms and marketplaces, becomes increasingly agentic and dominated by self-interested agents, will be crucial to understand the incentives created by learning algorithms and to align these incentives while optimizing for performance.
Limitations. One limitation is the otherwise intuitive assumption that the arms do not under-report their value the learner (Assumption and Assumption 2). Secondly, we believe that the factor of K2 in the universal regret guarantees of Theorem 4.2 and Theorem 5.2 is suboptimal and we conjecture that the optimal worst-case strategic regret is given by O(d/KT) KT). We leave this investigation for future work.
10

---

Acknowledgements
Thomas Kleine Buening is supported by the UKRI Prosperity Partnership Scheme (Project FAIR). Haifeng Xu is supported in part by the Army Research Office Award 1911NF-23-1-0030, the ONR Award N00014-23-1-2802 and the NSF Award CCF-2303372.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Peter Auer. Using confidence bounds for exploitation-exxllrriion trade-offs. Journal of Machine Learning Research, 3(Nov):397 422, 2002.
[3] Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR, 2021.
[4] Mark Braverman, Jieming Mao, Jon Schneider, and S Matthew Weinberg. Multi-armed bandit problems with strategic arms. In Conference on Learning Theory, pages 383-416. PMLR, 2019.
[5] Thomas Kleine Buening, Aadirupa Saha, Christos Dimitrakakis, and Haifeng Xu. Bandits meet mechanism design to combat clickbait in online recommendation, In The Twelfth International Conference on Learning Representations, 2023.
[6] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourleenth International Conference on Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings, 2011.
[7] Sarah Dean, Evan Dong, Meena Jagadeesan, and Liu Leqi. Accounting for ai and users shaping one another: The role mathematical models. arXiv preprint arXiv:2404. 20w:2440.11666, 2024.
[8] Qin Ding, Cho-Jui Hsieh, and James Sharpnack. Robust stochastic linear contextual bandits under adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 7111-7123. PMLR, 2022.
[9] Jing Dong, Ke Li, Shuai Li, and Baoxiang Wang. Combinatorial bandits under strategic manipulations. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 219-229, 2022.
[10] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 55-70, 2018.
[11] Seyed Esmaeili, Mohammad Taghi Hajiaghayi, and Suho Shin. Replication-proof bandit mecha- nism design. arXiv preprint arXiv:2312. 16896, 2023.
[12] Seyed A Esmaeili, Suho Shin, and Aleksandrs Slivkins. Robust and performance incentivizing algorithms for multi-armed bandits with strategic agents. arXiv preprint arXiv:2312.07929, 2023.
[13] Zhe Feng, David Parkes, and Haifeng Xu. The intrinsic robustness of stochastic bandits to strategic manipulation. In International Conference on Machine Learning, pages 3092-3101. PMLR, 2020.
[14] Rupert Freeman, David Pennock, Chara Podimata, and Jennifer Wortman Vaughan. Ne-regret and weventive-compattiee online learning. In International Conference on Machine Learning. pages 2279. PMLR, 2020.
[15] Nicolas Gast, Stratis loannidis, Patrick Loiseau, and Benjamin Roussillon. Linear regression from strategic data sources. ACM Transactions on Economics and Computation (TEAC), 8(2):
1-24, 2020.

---

[16] Arpita Ghosh and Patrick Hummel. Learning and incentives in user generated content: Multi- armed bandits with endogenous arns. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 233-246, 2013.
[17] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111-122 2016.
[18] Keegan Harris, Dung Daniel Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu. Strategic instrumental variable regression: Recovering causal relationships from strategic responses. In International Conference on Machine Learning, pages 8502-8522 PMLR, 2022.
[19] Keegan Harris, Chara Podimata, and Steven Z Wu. Strategic apple tasting. Advances in Neural 2023.
Information Processing Systems,
[20] Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:2205.00m 0681 2022.
[21] Jiri Hron, Karl Krauth, Michael Jordan, Niki Kilbertus, and Sarah Dean. Modeling content creator incentives on algorithm-curated platforms. arXiv preprint arXiv:2206.13 2022.
[22] Xinyan Hu, Meena Jagadeesan, Michael Jordan, and Jacob Steinhard. Incentivizing high- quality content in online recommender systems. arXiv preprint 27X1v:2306.07779, 2023.
[23] Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt. Supply-side equilibria in recommender systems. Advances in Neural Information Processing Systems, 36, 2024.
[24] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020,
(25] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[26] Yang Liu and Yiling Chen. A bandit framework for strategic regression. Advances in Neural Information Processing Systems, 29, 2016.
[27] Yang Liu and Chien-Ju Ho. Incentivizing high quality user contributions: New generation in bandit learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[28] Michael W Macy and Andreas Flache. Learning dynamics in social dilemmas. Proceedings of the National Academy of Sciences, 99(suppl_3:77229722 -2336,, 2002.
[29] Ross A Malaga. Worst practices in search engine optimization. Communications of the ACM, 51(12):147-150, 2008
[30] Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatible bandit exploration. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pages 565-582, 2015.
[31] Nicolò Pagan, Joachim Baumann, Ezzat Elokda, Giulia De Pasquale. Saverio Bolognani, and Anikó Hannák. classification of feedback loops and their relation to biases automated decision-making systems. In Proceedings of the 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 1-14, 2023.
[32] Shankar Prawesh and Balaji Padmanabhan. The "most popular news" recommender: Count amplification and manipulation resistance. Information Systems Research, (5(3))569-589, 2014.
[33] Paul Resnick and Rahul Sami. The influence limiter: provably manipulation-resistan recom- mender systems. In Proceedings of the 2007 ACM conference on Recommender systems pages 25-32, 2007.
[34] Elan Rosenfeld and Nir Rosenfeld. One-shot strategic elassification under unknown costs. arXiv preprint arXiv:2311.02761, 2023,
12

---

[35] Suho Shin, Seungjoon Lee, and Jungseul Ok. Multi-armes bandit algorithm against strategic replication. In International Conference on Artificial Intelligence and Statistics, pages 403 431. PMLR, 2022.
[36] Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. Pac-learning for strategic classifica- tion. Journal of Machine Learning Research, 24(192): 2023.
[37] Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. Mobile health: sensors, analytic methods, and applications, pages 495-517 2017.
[38] Zongwei Wang, Min Gao, Junliang Yu, Hao Ma. Hongzhi Yin, and Shazia Sadiq, Poisoning attacks against recommender systems: A survey. arXiv preprint 2rXiv:2401.0133 2024.
[39] Chen- Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. International Conference on Algorithmic Learning Theory, pages 1043-1096. PMLR, 2022.
[40] Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. How bad is top-k recommendation under competing content creators? In International Conference on Machine Learning, pages 39674-39701. PMLR, 2023.
[41] Fan Yao, Chuanhao Li, Karthik Abinav Sankararaman, Yiming Liao, Yan Zhu, Qifan Wang, Hongning Wang, and Haifeng Xu. Rethinking incentives in recommender systems: Are monotone rewards always beneficial? Advances in Neural Information Processing Systems, 36, 2024.
[42] Fan Yao, Yiming Liao, Mingzhe Wu, Chuanhao Li, Yan Zhu, James Yang, Qifan Wang, Haifeng Xu, and Hongning Wang. User welfare optimization in recommender systems with competing content creators. arXiv preprint urXiv:2404. 18319, 2024.
[43] Mengxin Yu, Zhuoran Yang, and Jianqing Fan. Strategic decision-making in the presence of information asymmetry: Provably efficient with algorithmic instruments. arXiv preprint arXiv:2208. 2022.
[44] Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. In Proceedings the Conference on Artificial Intelligence, volume 35, pages 5797-5804, 2021.
the AAAI
[45] Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:2110.126133 2021.
13

---

A Remarks on IncentiveCompatible No-Regret Algorithms
In Section 3 we conjectured that there exists no incentive-compatible no-regret algorithm when the reward observations subject noise and l unknown. For the interested reader, here consider fully deterministic case where 0" is known priori and reward observations are directly observable, i.e., subject no noise that ve O. We can design the following provably incentive-compatible no-regret algorithm. In fact, we show that this mechanism is strategyproof, i.e., incentive-compatbble in weakly dominant strategies.
Mechanism Incentive Combttibbl No-Regret Algorithm in the Fully Deterministic Case
initialize: A [K] for 1 < T (K + 1) do
Play & E argmax;e,, (0", (0", x1,i) Observe reward ri., (6", :(,e)) (i.e., rewards of chosen arms directly observable)
5
if (t,,)) & rt.a, then Eliminate arm i; Act1 + A. {it).
for t 2 T (K + 1) do Play i, ~ (Ar) Observe reward ri.s == (0", x(.t.) (r,,)) # rt., then
10
11
Eliminate arm i;: A4t1+ + Ae (ie)
Lemma A.1. Mechanism 3 is strategyproof. i.e., being truthful weakly dominant strategy for every arm. Moreover, Mechanism 3 suffers at most K + strategic regret in every Nash equilibrium of the arms
Proof. Dicentive-Compatinne in Weakly Dominant Strategies. It is easy to that for the last K + rounds, reporting truthfully, i.e., reporting 27, .. is a weakly dominant strategy, since the the set of active arms is played uniformly and nothing be gained from misreporting (an can only miss out on being selected by misreporting in the last K + 1 steps). Hence, conditional on any history, reporting truthfully is the best continuation for any arm. In particular, when an arm plays truthfully in these rounds the obtained utility in the last K + steps is at least K+1 since |A, < K.
K
Now, for the time steps T (K + 1) note that any untruthful strategy can obtain most one more allocation than the truthful strategy, because 4 = i and (8", .,t,)) ) > , ,,",), then arm i is eliminated immediately. Hence, most utility can be gained from receiving an allocation by misreporting. However, in this case the arm gets eliminated and receives utility 0 in the last K + 1 rounds. As seen before the minimum utility the truthful strategy receives in the last K + receives is K+1 > 1. Consequently, irrespective of the other arms strategies, the truthful strategy is (weakly) K
optimal for arm
One may wonder why the truthful strategy is not strictly dominant. To see this note that reporting any Fe,i * æ²,, such that the difference Te, 2²,5 is orthogonal to 0*, i.e., (0" .y.. =f,;) 0, does not cause elimination and is equivalent under Mechanism 3. In other words, such untruthful strategies, which however have no effect on the selection, are equally good.
Regret. The regret in the last K + rounds is trivially bounded by K + 1. When showing that the algorithm is strategyproof
showed that any untruthful strategy such that there exists with (0* xI.+)) > (0","7,,) is worse than the truthful strategy independently from what the other arms are playing. Hence, any Nash equilibrium arm chooses strategies such that i, then (0", . = (0", ,x.)). In other words, since the selection is greedy, Mechanism 3 selected the best arm in the given round. Mechanism 3 therefore suffers zero regret in the first T - (K + 1) regret in any Nash equilibrium of the arms.
As discussed in Section conjecture that there exists incentive-compatin no-regret algorithm for the strategic linear contextual bandits when the reward observations are subject to noise. The
Note that since truthfulness is only weakly dominant there could be other Nash equilibria.
14

---

intuition for this conjecture is as follows. Suppose there exists a learning algorithm M that is incentive-compatible and no-regret, that is, the strategy profile where every arm is always truthful is a NE. Since M is also no-regret, the selection policy of M must depend on the reported contexts some way. In partieular, reported contexts to an action in there must exist context 3g that arm i could report that increases its probability of being selected.
some round in which M does not select arm i-but M maps from
Suppose arm changes its strategy from of (i.e., being truthful) to the strategy that always truthful except for round / where it reports 72 instead of o The algorithm M then observes reward drawn from a distribution with mean ,0*, zt,)) but might have expected a reward drawn from distribution with mean (Z)). We believe that the difference in observed and expected reward is statistically insignificant when arm only misreports a single or constant number of times. However, due to the intricate relationship between the learning algorithm and the induced NE strategies for the K arms,
providing a rigorous argument for this challenging.
B Proof of Proposition 3.3
Proof of Proposition 3.3 We begin with the incentive- unaware greedy algorithm that in round t pulls arm i, argmax x) (8", 21,)). Let ō argmax||= ig (0", z) and w.l.o.g. we assume that is unique. We show that the strategy profile, where every arm always reports is the only Nash cquilibrium under the incentive-unaware greedy algorithm. Let o be any strategy profile which is such that there exists a round and such that Tt, + z. We distinguish between two cases.
Case 1: There exists a round and arm such that xx,,) < ma (0", (tt.).
Note that this implies that arm i is not selected by the learner. However, by reporting T instead of Fr,s arm i is guaranteed be selected with probability least 1/K. Hence, reporting Ft,i is strictly worse than reporting i' so that a cannot be a NE.
Case 2: (0" .) ma (0", (..) for all rounds L and arms i.
Note that this implies that each arm is selected with probability 1/K every round Suppose that for any of these rounds t we have max (0", .z.5) (0", ,i). Then, by reporting ž instead of r arm i could ensure to be selected with probability one. Hence, the strategy where arm i in round t reports instead of æ4,5 a strictly better response. Therefore, a cannot NE. The other case is when max (0", -t.j) (0" F), but this cannot be because a is supposed to be different to always reporting T.
Consequently, the strategy profile where every arm always reports E is the only NE under the incentive- unaware greedy algorithm. Under this strategy profile, the incentive-unaware greedy algorithm will play uniformly and therefore suffer linear regret.
Insufficiency of Non-Strategic Linear Contextual Bandit Algorithms. It is not really surprising that algorithms for non-strategic linear contextual bandits fail in the strategic linear contextual bandit, since such algorithms implicitly incentivize the arms to "compete" in every round by misreporting their context as the best possible one. Nothing prevents the arms to not myopically optimize their probability of being selected every round. As example of a standard algorithm for non-strategic linear contextual bandits we consider LinUCB that in the non-strategic problem setup enjoys a regret guarantee of (dvTT).
The reasons for LinUCB's failure in this strategic problem are the same as for the incentive-unaware greedy algorithm from before. It will be the strictly dominant strategy for the arms to maximize their selection probability the given round by misreporting their context. Recall that LinUCB maintains a least-squares estimator given by
0, = argmin
> (10 - ) 1110
BERd
Pm1
'This already implies linear regret, but it will be instructive to still show that the only NE is in maximally gaming strategies.
15

---

and in round t selects arm (ties broken uniformly at random)
4 = argmax (0e F1,3) + Villoreillly
=E[K]
where B, Rs dT) and V = AI > Te, Let UCB.(c) = (0e,z) x) + /B b
The argument for LinUCB will be the same as for the incentive-unaware greedy algorithm. Let ãt = | (C) and w.l.o.g. assume that üg is unique.
Importantly, in what follows, keep in mind that it will not matter how the reports of arm influenced 0, or Vi in previous rounds. Once again, suppose is strategy profile such that there exists round t and arm such that conditioned on the history Ft, # Zt. Once again we distinguish between the following two cases:
Case 1: There exists a round and arm such that (CB,(#1,)) < max (CB((115))
This implies that arm was not selected by the learner in round f. However, by reporting 7n and in all future rounds report Ty for l i, arm can guarantee to selected with probability at least 1/K in round and at least many selections as under dg. Hence, cannot be best response o-
Case 2: UC)(( = maxje[K] (CB)( for all rounds t and arms i.
Note that this implies that arm i is selected with probability 1/K every round. Suppose that for any round ć it is the case that max (CB,(T).)) < (T), Then, by choosing strategy ã; in round t and žy adaptively for all future rounds > arm obtains more selections than when reporting Tt.i- Hence, a cannot be a NE.
As result, the strategy profile where all arms report ž, in round t is the only NE and LinUCB suffers linear regret, as it pulls arms uniformly at random. In exactly the same way, we can also show that the algorithms for linear contextual bandits with adversarial context corruptions in [ suffer linear regret.
C Assumption
| and Remark 4.3
Example We here give a simple example where a strategic arm can simulate a situation where is always optimal even though it is only optimal half of the time.
Let 0* and consider the following problem instance with two arms and where
0, is even
and 1
1, is odd
Now, suppose that arm 1 always reports It,1 = =1/2 and arm 2 reports truthfully (or approximately so). Then, arm 1 appears optimal every round I. In particular, average arm when we pull arm 1 has reward 1/2, which is consistent with its report of Iz.1 1/2.
Now, consider second problem instance, where
T 1/2 and x1,2 1/4.
Recall that assume that, like almost always in the literature, the noise is sub-Gaussian As an example, let's 's consider Bernoulli-note such that P(ri, = 27,, = 1 Prr,, = 0). Then, the first environment when amm manipulates suggested is identical to the second environment when the arms are truthful. In the second environment, to suffer sublinear regret we must select arm 1 order T many times. However, in the first environment, must select arm only order o(T) many times.
Discussion. Based on these observations, we expect that we would have to make additional (strong) assumptions about the distribution of the noise and the prior knowledge of the learner in order to drop Assumption [ As an example, let's 's assume standard normal noise (0, 1) and that the learner knows that the variance is always 1 priori. Then, one potentially effective approach would be to extend our current grim trigger to additionally threaten arms that misreport their variance. Of course, the variance is unknown, however, we could estimate the variance of each arm's reports separately and use confidence intervals around the estimated variance. We could then threaten an arm with elimination if the arm's 's estimated variance falls out of the confidence interval. However, we expect there to be several technical subtleties in analyzing such variance- aware aware mechanisms.
16

---

D Proof of Theorem 4.1 and Theorem 4.2
D.1 Preliminaries
We begin with some preliminaries that use in the proofs of both Theorem 4.1 and Theorem 4.2 Note that B[rr,s] (0", o7,)) and we denote the total true mean reward by
Σ
27,))
EST: fems
Let us also recall the definition of the total observed reward as fr,s == Eest: ود Te, and recall its upper confidence bound UCB,(fra) = fr. + n (Tg and define the lower confidence bound (CB,(ft,)) = îz.. (
We now analyze the basic properties of the grim trigger condition of GGTM, which eliminates arm in round t if
Σ
(0 F1,)) > (f.)(fe))
ESt: iz
or equivalently
Σ (0""),,)) re,) 2/ m//n(i) log(T).
ESt: u=
Define the good event as the event that
g = (LC.,(Fr.)) S f7 < UCB.(Ft.) V [T]. i E [K]]
By Hoeffding's inequality, we know that the good event occurs with probability at least P(g) 2 1- Next, let
T3 == min E [7]: : i g A,}
denote the first round in which is longer active and, by convention, let T; T if E Ar. By design of the grim trigger condition, note that T; = for all E [K] on the good event all arms always report truthfully.
We now provide general result bounding the maximal amount of manipulation any arm can exercise before being eliminated by GGTM.
Lemma D.1. On the good event G. any round t [T] and any arm i Ae it holds that
Σ
(10", ((0"))),) xi,)) S 4 (1)
From the definition of T; this entails that
Σ
(10), xZ.) S 4, nT, log(T).
EST 6==
Proof. On the good event G. it holds that
Σ
- re,s) E 2
+2/ mx(() log(T))
ESt: i=
which implies that
Σ
(0",x1.1) - -r,,)2
(0" "e, - x7,)) 2 (i) log)
ESt: f2=1
851: f==s
Hence, if Eese: v (8",, Ktn - xtta) > 4 n4 log(T), then
Σ (00 r(,)) - Te.)) 2 ne( log(T),
which means that arm is eliminated from A,. Finally, :; is defined as the first round such that of A so that
Σ ((0", - x2,)) < 4 n, (i) log(T")
EST: i
for all S and 1 (10), 21,1) x22.) 4, n., (i) (T),
17

---

For completeness, we also formally state the fact that on the good event 9 any truthful arm is not eliminated with high probability.
Lemma D.2. If arm i reports truthfully every round, i.e., plays strategy of with 2 2or for all round t E [T], then the good event arm i stays active for all rounds.
Proof. When arm i is truthful, then (0= f On the good event, f2 S (fra, for all & E [2]. Hence, the grim trigger condition is never satisfied and arm remains active throughout all T rounds.
D.2 Proof of Theorem
Proof of Theorem 4.7 We have show that the strategy profile a', where every arm always truth- fully reports their context, i.c., 2t, = zi, for all (t, E [T] [K], forms a (OVTT -Nash equilibrium for the arms under GGTM. We do this by showing that any deviating strategy o, for arm i cannot gain more than this vT clicks. Recall that 8o is the optimal arm in round t and i the arm the learner selects.
We begin by deriving the minimum utility of every arm when everyone is truthful. To this end, let (i) Et. 1 {iz i) be the number of times is the optimal arm. If every arm i is truthful, then on the good event G no arm gets eliminated (Lemma D.2p and (0" ,T,,) = (0", at,)) for all (t, i) E (7) x [K] As a result, GGTM pulls the optimal arm i in every round t. First, note that:
E- [nr(() 2 n7 T
because on the good event G (when everyone is truthful), we have (1) 2 ni. Since by construction P(g) 2 1 1/T", the lower bound follows.
Next, we bound the utility of a deviating strategy a, in response to GGTM and the other arms' truthful strategies '².g On the good event G, when the arms play strategies (o,, o",), we have
nT((1)
Σ
1i - -,0 = + Σ
1i #1
1=1
$
Σ 101 +1 Σ
1 1 - #1
T
= -1) + Σ 14
We will now bound the sum on the right hand side from above.
Every arm j * is truthful and therefore, on the good event, j E A. for all t. If the optimal arm is not i.e., i / i, it means that (0", ,,,,;; -x,i)) > 0. Next, since GGTM selects the arms greedily according to the reported reward, the event implies that
,r,) (0", -i.;))
where we used that any arm it # i is truthful that (0", xx,,)) (0",,,,,;) As result, we can apply Lemma D.I to obtain
T
T
Σ
1 10
f = , - x S
Σ
1 = i # i)(00" I1,i - s7.e
Σ 1f; 10,00
It, - x1,))
< 4 nr (o)
18

---

"i,; ( is positive and assumed to be constant, we get that E/=1 1 +i i} I Ol n,, (t) (T)) We coarsely upper bound n., (2) by T and using that the good event & has probability least 1/22, we obtain
Since for 87 * i the gap (0',2,,
B [NT(i)] S nz (1) + + (VTlog(T)
We have thus shown that
g nT (1)) 2 Bogot [ (i)] O +V(TTlog(T
for any deviating (dishonest) strategy dy. This means that o is ((VT) equilibrium for the arms.
Finally, the regret of GGTM when the arms are truthful is quickly bounded by 1/r by using the fact that on the good event no arm gets eliminated and, therefore, GGTM picks the round-optimal arm every round. The event that G does not hold has probability most 1/T" which implies expected regret I/T, i.e., Ry R (GGTM, S 1/T.
D.3 Proof of Theorem 4.2
The proof of Theorem 4.2 is notably more involved than that of Theorem 4.1 even though the general proof idea remains similar.
Proof of Theorem 4.2
We begin by decomposing of GGTM into the rounds where the optimal arm is active and the rounds which it is being ignored. To this end, recall the definition of the arm that is optimal in round as argmax,e [(K] (0* xT,))- We have
RT
E
16 E A t.t t....)
+
Σ
16t & A1) ot.
We now bound 11 and 12 separately follows.
Lemma D.3 (Bounding Ii).
E
Σ 1=1
1 E ArNo न.. - zinh) so <o(VKTlog(T
Proof. Let it denote the selection of GGTM round t. Recall that GGTM greedily selects the arm in A, with highest reported value in round t, that is, 21,,)) = maxieA, (0", zt,)). Consequently, on event (iz Ar), we have
(0", x2,;;) S (0", x1.;)) I max
x.,i) = (0", xz,,.))
SEA,
where the first inequality holds by the assumption the optimal arm iž reports their value at least as high as their true value. As consequence, it holds that (6* 2t.; =t,..) (0*, Ii,t 2(,;,) which implies:
T Σ
T
16 E A, - ai,h)
<
E
Σ
10 E A,10 st.s, ai,0.)
(5)
When ét Ar, necessary condition for arm i to be selected in round (i.e., i, i) is that t Te. Finally, we split the sum into each arm's contribution and apply Lemma D.I obtain
E
li = (0 Fus. a7,))
E
4 n., (i) log
<4v KT log())
where the last step follows from Jensen's inequality by bounding ne, (i) by nT (i) and using that ΣK ni( T by definition of (i).
19

---

While bounding 11 is fairly straightforward and we did not have to rely on the fact that the arms respond in Nash equilibrium, bounding I2 becomes more challenging as we must argue that it is in each arms' interest to maintain active for sufficiently long time.
Lemma D.4 (Bounding I2).
E
Σ 1 1iz & (PE - -Min)) 5R² SOR22K'' loglo
(6)
Proof. To bound // we argue via the best response property of the Nash equilibrium. This requires some intermediate steps. We begin with lower bound on the expected number of selections any arm must receive when the arms act according to a Nash equilibrium under GGTM.
Recall the definition nz = Ein 1(47 i} and that the indicator variables 1 1 = i are not random, since we work under an adversarially chosen sequence of true contexts. In contrast, the indicator 1 = }} is a random variable as it generally depends on the random reward observations and any randomization of the algorithm.
The following lemma provides a lower bound on the number of allocations any arm must receive in equilibrium. To prove the lemma, we show that more than order VKT allocations manipulating arms. This crucial would be impossible to incentivize approximately truthful arm behavior if an arm would lose too many allocations, e.g.. order 7' many, by doing so.
able protect any truthful arm from losing
key challenge here is that under two different strategics o; and of. the set of active arms can be quite different. This is the case since even though estimate each arm's 's expected reward independently. arm i can still slightly influence the elimination of some other arm j by poaching selections from them. As result, must content ourselves with conservative bound than one may originally expect.
Lemma D.5. Let a E NE(GGGTM). Then,
Eg (nr (i) 2 (i) O (VKTKloo
KT (og())
In particular, it holds that Eg [na 2 n1 00 KT log(T)) for any t E [T].
Proof. We use the fact that if o = (o (o1...., σk) ) is a NE under GGTM, then o, must be a best response a-1, i... Eo,,o_ [r)( 2 Boj (i)) for all strategies of. In particular, it must hold for the truthful strategy of that
Egg (1) 2 (er(
We focus on the good event G so that i E A, for all L given that arm i is truthful. We are interested in the number of rounds such that i and i, o i. Given strategies good event, we have
so that E Ar on the
T Σ 1 1=1
= -i
ΣΣ
16 = -, = =).
1=1
Note that i, j with i i E A, implies that (0", .z.g) 2 (0 x.,))- Moreover, because i is truthful
and i7 i, we have (0", .) (0 ,, ) so that (6", (.i)) > 10" ((,))) As a result,
(0", بं. a7.)) (0", Ft.j x;.))
then follows from Lemma D.I that
Σ 1 - i, = 10 ZL.; - -xi))= <
1 1 = i, -0>000,,
, - -17
(7)
tml
<
1 1(i = =11000,000 -
(8)
1=1
< 4 nr, (i) log()).
(9)
20

---

Since (6", - - 27,))
is constant for i? = i = j, we obtain
T Σ
S Σ "n S sO(VKTlog())
jtft [=1
where the last inequality follows from Jensen's inequality. Recalling that P(g) 2 - 1/72, this provides us with the following lower bound on the utility of the truthful strategy
Boj,.- _0_ (i) = Boy,o-
Σ 14
=1
1=1
2 _oz
Σ 11t i
-1it 1 -
2 (1) OVKKTolgT
Note that we, like before, we account for the event G by increasing the constant factor by one, since (1- (1-2/r=)nr(( 2 ni(i) - 1/r as ni(i)= - T.
Since o, has be best response to --i. i. must be least good of sot that
[x)r 2 ; [n) 2 (1) ((VKTllogTT)
To get the result for any t E [T], suppose that on the good event G it holds that (i(1) < n w(y V KT (KTllo(T)) log(T)). Now, recall from equation 7 that the number of rounds such that i i and it * is bounded by O(v (T)))) on event G. Hence, since we assumed that ny(i)
n, (i) w( / KT log))) and (0" .4,5 - 2,,,) 2 O, it must hold that T. < t. Consequently, on the good event 9, we obtain
nr. (i) ni (i) nt w( (v KT KT log())
This implies that E [n., (i)] (1- (n) w/ KT lTg + 1/r S (i) w/ KT KTollgoT)) (T) This stands in contradiction to the earlier lower bound of E, |nT(i)] E. |n,,, (i) 2 n (i)
Next, we provide an upper bound on the number of times an arm is pulled in any Nash equilibrium. In other words, we bound the profit any can make under GGTM from misreporting contexts.
Lemma D.6. Let a be any NE under GGTM. Then,
Eg [TTT(i)) < Eg [ (i) + O(K - (TVKllog)))
Proof. Note that Σ 1= (i) = E E 1 =
i} i)
for any T E [T]. Using Lemma D.5
we then obtain
E [nT (i)) = Eg [n (i))
= E.
Σ life = =}
= EE
(1 - Liee #1))
1=1
E. [m]]
Σ Es |n,, (7)
< E. [T]]
Σ
In (i) O - 1) - (olgg(T))
jti
= (n
O (K / KTlog(T)
21

---

Combining Lemma D.5 and Lemma D.6 we get for any Nash equilibrium NE(GGTM) that
Eg [n)] (vv KT (T)) EEg (n)( - Eo In,, (+) - OO(K 1) () (T)) which implies that
Eo (i) (0) - O KKKKKTlog
(10)
The expression - (t) is the number of rounds where arm was optimal but already eliminated by the grim trigger. As result, we can express the total number of rounds where the round-optimal arm ig was no longer active as follows.
Lemma D.7. For any o, we have
BØ
Σ 1 &
Ar}
B (1) n", (i)
Proof. Rewriting {1z E Ar} yields
Eg
Σ 16g & AD
Σ
EE
Σ
- A.
K
T
T
Σ
E
Σ
1(i =1 Σ - = i, A+}
1=1
K
Σ
Eg
(1)
- -n
Finally, note that (0", , =xt,)) S
so that from equation (T) it follows that
T
T
E
1 (ig & A0 ,,,, - -
S E
1 fi &
Ac)
K
E
[n+ -n (1)
O(K O(K /KT2//KKog(
Connecting the bound on 1, and 12, we then obtain the final regret bound of Theorem 4.2
RT σ) 0o
v /oTlo + K2 CVTTlog(T
< <ō K2 <O(K<VK7
Lemma D.3
Lemma D44
Remark D.8. We want brieffy comment on the existence of a Nash equilibrium. Since each arm't strategy space, given by (a E Rd: || < 1} in every round, is continuous, it is not obvious that Nash equilibrium for the arms exists under every algorithm. However, Glickberg's theorem shows that the continuity of the arms' utility in the arms' strategies is a sufficient condition for the existence of NE, since the strategy space is compact. We can then ensure the continuity by, e.g., choosing arms in OptGTM, and remarking
proportionally to exp(T' 22,i)) in GGTM and exp(TUCB,,T, that the probability of eliminating arm i in round is continuous in It,s conditional on any history. Due to the exponential scaling with T the effect of such slight randomization is negligible in the regret analysis.
22

---

E Proof of Theorem 5.1 and Theorem 5.2
The following preliminaries are fundamental the proofs of Theorem 5.1 and Theorem 5.2 so that we derive them jointly here.
E.1 Preliminaries
We begin by recalling the definition of the least-squares estimator w.r.t. arm i's reported contexts and the corresponding confidence ellipsoid Ct. Note that since the the least-squares estimator may not accurately estimate 0* and 0* may not be contained in C., w.h.p. As discussed in the main text, since accurate estimation of & appears hopeless, the main idea idea to incentivize arms to report contexts such that our expected reward does not differ substantially from the observed reward.
manipulating their contexts,
The least-squares estimator w.r.t. arm i is given by
0,, argmin
(Eech 12=1 (10, xe,) TE,,) 111013
AERd
where À > O. In the algorithm, we set the penalty factor to X = 1. The closed form solution is then given by
d Vo
Σ
with Ve, AI
Σ
B<:: femi
Ecr: femi
The confidence set Ct,6 is defined
Ct =2==00a 1= ER: 10 -11: 3 31.3
where we let Br, log
L+me 8
+ VSS with 100 < S and å = 1/12.
We now translate the standard result used to assert the validity of the confidence set to our situation. Clearly, when the sequence of Tt, differs significantly from the true contexts 2ř,;, the true parameter O" will not be contained in Cr. Instead, we will formulate the concentration result as follows.
Lemma E.1. Suppose there exists 0f E IR such that for all t with it = i.
(0 (,,,),,)) (1,))
(11)
In other words, the reported features Tτ, linearly realizable by some parameter 0 For any 8 (0, 1) let the confidence size be
1 mz(1
Br, 11 dlog
VĀS,
where 1 S. Note that the typical expression also includes some constant L such that |ær, < L. which we here simply set to 1. With probability least 1 - 8 it then holds that 03 E Cr.- In what follows, we choose 8 == 1/12.
As special case, when arm i is always truthful so that It,; x the true parameter 6* trivially satisfies (TT) and the result reduces to the standard confidence bound statement [ 24 restricted to observations from arm i.
Proof. Let 87 satisfy (II.. Then, note that Te.; (8", x7,)) 7/- I1,, 7t- Hence, the sequence of reported features Z,,; and observed reward rr.; yield a standard linear contextual bandit structure with unknown parameter 0f (instead of 0*). Then, to obtain the confidence bound follow the arguments from 1 [24), where we remark that we choose the confidence radius Sr, arm specific. However, we could also choose larger confidence radius such as Br d log(t) 3 zs d lo'"".. This will only have a negligible effect on the final regret.
constant
The grim trigger condition 44) of OptGTM stated that arm gets eliminated in round if
Σ
(Bee,) - /Blllze.lllyy))
Σ
Tt,s + 2 2//n((0 log(T).
(12)
ESt: TZ
ESt: 4=
23

---

Equivalently, Eest: ie= (CB,, > (f,))
As a sanity check, we show that when an arm always reports truthfully, i.c., 2i, = zi,; for all t, doesn't get eliminated with probability at least 1 1/1
Lemma E.2. When arm always reports truthfully it does not ger eliminated with high probability, that is, E Ap with probability at least 11/122
Proof. We consider the event that the true parameter 0 is contained in Ct.. i.c., G = {0 e Ct,i Vt E [T]]. The event 9 has probability least 1 1/T" according to Lemma E. when arm i truthful. Moreover, suppose that the reward observations concentrate as well, i.e., we assume the good event 9 (LCB,, (fr,s) f7, S (F,) Vt [T], [K]]- Recall that & has probability least 1 1/r² according Hoeffding's s inequality. A union bound then shows that the intersection of the two events has probability at least 2/T².
Now, since arm truthful, we have Tts; xū.s and (0, = (0, for all 0 E Rd Using Sauchy-Schwarr inequality and the fact that 6 E Ct,i, we get that
(dr. Te.s) (0" 2t,)) = (0r. 0" 2t,)) S |10e, 0 Ilv.,, lll..lllasslll S V Buallaaallly
Moreover, as we work on the good event G. we have
Σ (00
E
log()))
ESt: 4==
Combining these two statements yields
Σ (10,,, TEA)
Σ
Vesilleeally lell + +2/ mi) log(T))
ESE: Am
for all E [T]. other words, the grim trigger condition is never satisfied so that E Ar on event saw, occurs with probability at least 1 1- 1//22.
G E S, which,
We now analyze the grim trigger of the OpIGTM algorithm. As before, let T; min(t: & A.) with the convention that T; = T if E Ar. The following lemma upper bounds the total amount of manipulation that can exert before being eliminated by OptGTM's grim trigger elimination
rule.
Lemma E.3. On the good event G:
Σ (L)) 20,))
10"
Σ
V Vaullerallyyy + 44 nr. (i) lTg(T)).
ASTU: MEX
Or equivalently, since UC,L, = (0l,, + v Br, I1, 1 1, it holds that
(UCBL, [(UCLE (c.)) x0,, S
Σ
2 Br, 1.lllalllll + 4 -.vnn (i) log(T).
64
IST
Proof. Let l E [T]. On the good event G = (LCB,(A.)) S S UCB.(AL.) W [7], E [K]} and by definition of UCB,, (re, it follows that
Σ
(10,,) Te,) - ree))
ESt: ki=
Σ
(UCBra(IEN) - (0", x00"=
Σ
Veulleedllve, 22 log(T).
ESt:
ESt: iemi
R=
Hence, if Eese: ie=i (UCBL,(EL5)) (0", ((,))) > 2R, then
Σ ((0e,) re,))
Σ
Veaalleelllyzt + (1)
ESt: fezi
ESt: 1==1
24

---

which means that arm i must have been eliminated in a previous round or in round t, i.e., T; >> t. Hence, for any T,, the the left hand side must be smaller or equal to the right hand side.
Interestingly, notice that we worked on the good event & that only concerns the realization of the rewards and not the validity of the confidence set. This is important, since it is generally not true that the true parameter 0* is contained in the confidence set Ct
Lastly, before we begin with the proof Theorem 5.1 and Theorem 5.2 establish bound on the total exploration bonus, which after some additional work follows from the well-known elliptical potential lemma 24
Lemma E.4. It holds that
Σ ISTC
Villenalllyy S So (d (i)
The constant on the right hand side can be derived from the choice of B1,5-
Proof. Before apply the elliptical potential lemma[]] need to make sure that the explo- ration bonus does not blow up in early rounds. To this end, recall the definition of
Vl, = A
Σ DESTE
Ect: i==1
Let A = Eest: i= 2,5 Note that A is positive semi-definite so that Al + A is positive definite and its inverse (AT A)-1 well. The matrix inversion lemma let's us express this inverse
(AI + A) 1 = AI (AI + A) A1-1A.
Now, the eigenvalues of = (AI + A)-1 are given by \:/(1 + Ar), where A 2 0 are the eigenvalues of A, which means that positive semi-definite. Consequently,
| B (A + A)- ar, = =T, =T, Al|
We assumed that ||I., < (similarly we could assume upper bound L) so that || vÀ. For convenience, we set the penalty factor to = 1. We then apply Cauchy- Schharrz to get
VBulllealllae S
no. (i)
Σ
min (1, || 1
EST
The elliptical potential lemma II 124 bounds the sum on the right hand side
d Th., (2)
min(1, 11,, }} 2d
ASTE: G=
Finally, recall that we chose Be, = (dlog (n.()))), which then yields the claimed bound.
E.2 Proof of Theorem 5.1
Proof of Theorem 5.7 We begin by proving that being truthful is an approximate Nash equilibrium under OptGTM.
Truthfulness is Ö(dVKT)-NE In fist step, we show that if every amm is truthful, every arm is guaranteed least (1) O(dVT) utility, where (i) = Σ 1 (1g i). To this end, we write
T nr (i) = Σ
T
- i] + 3 1(1 i #
1=1
T
2 Σ 1e; = - - -
t=1
25

---

and our task will be bounding the sum on the right hand side. We focus on the event that 0" E Cz for all (t. i) E [T] x [K]. which according to Lemma E.1 occurs with probability least 1/2².
Since 0* E Ct.i, we have (C,., 2 (0", xt,zz) for every E [K]. Let &z = but it = j with j A i. Keeping in mind that æt,i ot, for all (L, E [T] [K], since all arms are truthful, this implies that
UCB 2 UCB (27,)) 2 (0", ,.i,))
As a result, holds that
UCB (0" m 10 Fitt =ig)) Next, since l E Ct, and 02,5 E Cr we find that
UCB (0", x11)) S (Or.s xt,z) 10 Fig) + Bes laoslll
s |10c] 0 1 llvz
$ / Be, | Ily
where the second line follows from Cauchy-Schwarz inequality. Using Lemma E.4 this implies
Σ
UCBL,(
(0", xt.)
E V (esilsesllvv IST:N=J
k=)
5o (dlog(T))/nn: (nr())))
Since ,t,,; - xi,)) is constant for i + j. this means that
E1s - i = i} O (d (dlog(())nn,.))
so that by Jensen's 's inequality
-
ΣΣ jfit
10 = 1,4 = 5o 5o (d
In second step, show that for any deviating strategy o; that is not truthful, the utility of arm i is upper bounded by (i) + (dvT). In what follows, work the event that j E A, and f E Ctj for all E (7) and j * and recall that this event has probability at least 1 11/re since the arms reporting truthfully (see Lemma E.2p. Since E Ar for all + have
T
(1) S 1 -
[=1
c=1
and we are tasked with bounding the sum on the right hand side appropriately. Now, similarly to before if i and i * (given it E Ad). then ( 2 UCB (F21;) 2 (0" xi,;;) where we used that 0* E Cr, since the arm i * i is truthful. Consequently, UCB,,; - (0", zi,)) 2 00,2.. a1.))
Combining Lemma E.3 and Lemma E.4 tells us that
(EL.) (0", x1,)) O ( (dlog(T)VT)
where we coarsely upper bounded n,, (i) by T. Since 10*,0t, x4,i) for it + i is positive and constant, follows that
Σ 1f4 1, * 0 (dlog(T)VT))
1=1
In summary, we have shown that
and Eo,oi, S (1) + Ô (dvT) for any deviating strategy o.. Hence, o² is Old KT) equilibrium under OpIGTM.
Eg (i) 2 ni (i) Ô dv KT
26

---

Regret analysis. Since we maintain estimates and confidence sets for each arm independently, it is natural decompose the regret as
K Σ
Σ
00 بं.5 - 27,1
10,2i,, - x2,5)
(13)
2=1
EST: i=
Note that w.h.p. truthful arm gets eliminated and 0r Ct, for all (t, [T] [K]. The regret analysis then proceeds similarly to that of LinUCB.
Since l* Cr we know that for any round such that i, = i that
(0" xT,;)) & U (xī,;) = UCB (FL,;) & (C,,,, = (CB,,
Then, again for any round with i, i, applying Cauchy-Schwaer inequality yields
( 27 . - (T (0" = s 22 Be
(14)
Next, first using Cauchy-Schii Schwarz inequality and the elliptical potential lemma (Lemma E.4 and then Jensen's 's inequality, follows that
2
Σ
Vallaallyy (ddlog(T)KK))
(15)
EST: 4==
Hence, connecting equations
13
15
we obtain Ry (OPIGTM,,")) S ((dvKT)) We see that
the additional K factor emerges due to OptGTTM maintaining independent estimates for each arm. the action set size can be prevented since observations from one arm can be used for another arm as well. However, to prevent collusion in the strategic linear contextual bandit important to limit the influence an has the selection (and elimination) of other arms.
Usually dependence
E.3
Proof of Theorem
Proof of Theorem 5.2 We begin the proof of Theorem 5.2 by decomposing the regret into two expression, which we then separately bound.
Decomposing strategic regret. We now decompose the regret of OpIGTM into the rounds t where the optimal arm in round still active and the rounds where not. Like before, let be the optimal arm in round t. For any E NE((OIGTMM,, have
[ (0*, .ItT;)
T
T
Rr( = E.
Σ
16 E A, मं. - 27,()
+ E.
Σ [==1
1 4 A.1 मं. - xi,..)
[=1
J2
(16)
With the help of Lemma
E.3 and Lemma E.4 we now bound J1.
Lemma E.5 (Bounding Ji).
Eg
Σ
1 A,300",
xi, <o(dVKTlog(T))
Proof. By design of OptGTM, we we hfv xt) S UCB1,,
S UCB (1e..) Then, on
the good event G. Lemma E.3 yields
Σ
00,"is --,,))) S
Σ
(UCBr,, (Fes)) - x((,))
BST 1=1
1ST:: i=i
< 2
2 (i) +
Σ
IST k=1
27

---

Then, on the good event, we have
Σ 1it E A0) 1i, t=1
Li , xi,e)
i= 1=1
Σ
2/ Be,
2/ n7, (2) log(T)
(ST;
K +
Σ O (dlog(T))
Σ
2 2 (i) log(T)
0 (dlog())VKT)
where we applied Jensen's 's inequality in the last inequality and used that E nr, (1) S T.
Lemma E.6 (Bounding J2).
T
H & A को. - stiie) S 0 LoKkk>/KToo/// Σ
Eg
Proof. The proof idea is the same as the one for Lemma D.4 which was used to show the regret upper bound of the Greedy Grim Trigger Mechanism (Theorem 4.2 Appendix DD. Recall that by
assumption (0", F 2, S 1. We reuse Lemma D.7 from the proof of Theorem 4.2 to get
T
T
E
Σ
10 & AO नं. - siehd)
S
E
Σ1
1
& Ad} = Σ E. (1 n (1)
where ni (1) = =1)= 1i; = i} is the number of rounds up to round é that i the optimal. To bound the right hand side, we first prove a lower bound on ES (nr(() (i)) for any NE o E NE(OPIGTM).
Lemma E.7. Let E NE((PIIGTM) It holds that
Eg [nr (i) 2 m1((1) O (dl)g(T)VKT)
In particular, it holds that Eor [nx(1) 2 (i) O (dlog(T) KT for I E (7).
Since G occurs with probability 1- 1/72 and (i) < T by definition, on event 9, have (1) 2 (i) O (dlog(T)VKTT
me(1) 2 (1) (ddlo((TVVK)))
Proof. Given that arm i always reports truthfully, i..., ,t, = z for all t, consider the event that 8" E Ct,; for all t. Recall that this event has probability at least - 1/r2 according to Lemma E. We use the best response property of the Nash equilibrium by comparing against the truthful strategy. To this end, consider the strategy profile (at.a o-)) and the event that 8* Cr for all as well as G. We then have that
T
T
nT (1) 2 Σ
1 1 =
10 Σ
-i)
ΣΣ
16
=
(17)
#+
where the sum on the right hand side is the number of rounds where is optimal but OpIGTM pulls another arm (because it has reported larger optimistic value).
28

---

Next, recall that 0 E Ct,s so that for ? = i it follows that
UCB = (Z 2 (0", (7,)) (0", x
Now, 4, = j implies UCB,, 2 ( 2 (6", (T,s)) since i E A, for all t and OptGTM selects the arm with maximal optimistic value. As result, when ij = i and in = J. we obtain that
UCBI,, - (6", , (6", Z..; -
Importantly, we have shown in Lemma E..3 that the total difference on the left hand side bounded before elimination, i.e., before round Tj. As consequence, we get
1 i 1110 12, [2d) S
1 =,, =}} (UCBL,(013) 10", xi.))
1=1
lit = j} (UCB),((FL)) -
1=1
2
fi; j} Br, Beolll + 4v n. (i) lTg
t=1
1 0 (dlog(T)) nr (i) + 44 en/nr,10 log(()
00 ( (f)
where we first used Lemma E.3 and then Lemma E.4 Recalling that (0", . - x > 0 is constant for j + it by assumption of a constant optimality gap, it then follows from Jensen's 's inequality that
ΣΣ = }} < Σ o [(d
(Ilog(T)/mr)) so o (dlog(T)<T))
J+1
where we used that Ej Rr, (1) 1 T. Hence, equation
17 yields
nr (1) 2 (1) O (dlog(())
Since og must be a best response to σ-i. we obtain
Eg [nT(1)] 2 Eo (nr((r) (i)) 2 (z) o
- (dlog(())VKT))
To obtain the result for E [T],, suppose that on the good event G the contrary is true so that (i) < (1) (0d)-)((llg)))))) (TT) However, similarly to before, Lemma E.3 us that the number of rounds that are "poached" from arm i.e., i7 = i and is * i, is upper bounded from above by log(o)))) KK). Hence, since (x1,), 2 x",,,) and ni(() S n (1) (dloog(T)//KT)) it must hold that т, < t. Then, on the good event G. it follows that ne, (i) S ni(1) < mz
w(d (og(()))) /KT). Since event G has probability at least - 1/1", this implies
R. (1)) = E, (n,,, (1) S nz (i) (d (dllog()VVKT))
This contradicts the lower bound of F., (i)( 2 (1) O(doog())/K)))
Lemma E.8. Let a E NE(OOIITM).. Then,
[Tr( < Eo (n=, -0 o
0 (dlog(T) (T) KT
where the expectation on the right hand side is taken w.r.t. T
29

---

Proof.
We have Ei= mz(1) = E/= 1==1 1 = = for any [T]. Using Lemma E.7 we
obtain
Eg [nr( Eo | (1)(
71
Egg
1(t =]
E.g
Σ (1 1f # +}}
[Ti]
E [ (i)
j
< [Ti]
Σ
E [m= (i) + (0 (dlog(T)KVKT)
jyi
Eno (0)] + 0 dllog( (dlog(T)KVKT)
Combing the lower and upper bounds each arm's utility of Lemma E.7 and Lemma
E.8 get
(1) O (dlog(T) < Ee (n)( E [nf, (f) o (dlog(T)
(18)
It then follows that
E (n) nł,, (i) s 20 (ddlo(()T() KTT
so that
K
Fg (17(1) - n7, (i) & O (dlog(T) K2 ( VKT).
This concludes the proof of Lemma
E.6
Finally, recalling the regret decomposition from the beginning of the proof and using Lemma E.5 and Lemma E.6 we obtain for any E NE(o) that
(log(T))KT++ (lgg) <O((3VVTT)
(GGGTT,,)) σ)
Lemman
Lemma
E.4 Linear Realizability of Reported Contexts
In the following, comment interesting observation in the strategic linear contextual bandit that may also provide some insight into the effectiveness of OptGTM. Suppose that each arm reports its contexts in linearly realizable fashion (without explicitly incentivizing them to do so). Formally, we can express this as the following assumption.
Assumption 3 (Linear Realizability of Reported Contexts). Every arm reports so that its reports follow some linear reward model. That is, for every arm E [K], there exists a vector 6 E Rd such that for all t [T]
10' xT.)) = (0) x.,)).
(19)
Perhaps surprisingly, the regret analysis OpIGTM becomes straightforward when the arms' strate- gies satisfy Assumption 3 Moreover, we can prove that OpIGTM suffers Ö(dy KT) strategic regret in every Nash equilibrium of the arms. That is, the regret guarantee better than that of Theorem 5.2
30

---

the total regret of A quick regret analysis. Let a be any NE under OptGTM. When we observe a reward after pulling arm in round t, we can interpret the reward as rr, ,0,, 7) ( + Th- Hence, isolating arm i, the learner is essentially playing linear contextual bandit with true unknown parameter 0% contexts Pt,i, and rewards rt,; (07, Ft.s) ?]-- As result, the independent estimators i, for every arm i, are in fact estimating 07 and, according to Lemma [_] with high probability 07 E Cr... It is then also easy to see that OpIGTM will never climinate any the arms with high probability, Now, since 0r E Cr
(0"
(2.)) S (E..),
As result, using Cauchy Schwarz incquality, we obtain
UCB), (0", F1.)) - (0e.; 01,) + v Vesllaasllyyy
S |0., lr 0. wlw.ll Vealllaallyy $ 22 Besllll resllyt
In every round t, OptGTM selects the arm with maximal optimistic reported value UCB(,((F..) so that UCB (Fr,4; - UCB,,, (2),,)) S O. We can then bound the instantaneous regret in round t as
50,;; vi,e)) S aC (1Z,5)) (0,, sh
I UCB (Ir,it) ) UCB,, (xt,i. + Berse 1 val
s 2 Be, Tt.s llv...
Using the elliptical potential lemma and Jensen's inequality (Lemma E.4 OptGTM is given by
24
(r(OPiGTM. oF S
Σ
2 Be, (e s 0 (dlog(T)VKT)
1ST
We have thus shown the following guarantee.
Corollary E.9. Suppose that Assumption 3 holds. Then,
(r(OOIGTM, a) δ (vKTT)
for every Nash equilibrium o E (E((OT)GTM).
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract, we list the main claims of this paper in a general fashion. Then, the introduction we state them in more detail. They accurately reflect the paper's contribution and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations and assumptions of our work throughout the paper. Additional limitations are highlighted the discussion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
32

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The assumptions can be found in Section 3 and in the paragraphs before the theorems. We provide proof sketches in the main text and complete proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
33

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/ /Cwee//ouidiiiiooooooooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https) hhaipp.ccc/pbll1/gguaddee////eos
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
34

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://ppp/.ppppp..ooo//////aaaa
35

---

Answer: [Yes]
Justification: We do not any potential negative social impact of this work. On the contrary, this work aims to improve the faimess and equity of online platforms by discouraging harmful gaming behavior in response to recommendation algorithms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This work addresses the problem of aligning agent incentives with that of learn- ing algorithms. While there are some potential positive societal impacts of this theoretical work, we do not believe that it is necessary to highlight them here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
36

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
37

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
38


Reviews:
[{"review_id": "qLh1OHFgrN", "reviewer": "Reviewer_XxQv", "summary": "The paper introduces a new strategic variant to the stochastic contextual bandit, where the contexts of the arms are not public but are made available to the arms only. The arms may choose to strategize by misreporting their context to sway the decisions of the learning algorithms. The model is analyzed in two settings: known and unknown \\theta^*. The primary results are algorithmic (truthful mechanism) contributions and corresponding regret bounds.", "questions": "Please refer to the above comments and reply accordingly.\n\nI am willing to engage in the rebuttal phase.", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is exceptionally well-written and easy to understand and follow. The proofs are laid out well.\n\nThe strategic variant of linear contextual bandit is very neat and interesting. I look forward to more results, hopefully with fewer assumptions or in more general settings.", "weaknesses": "1) Regarding model description, my biggest concern is the assumption that the arms respond to the learning algorithm M in Nash Equilibrium. Specifically, the definition of NE for arm $i$ depends on future stochasticity (randomness in M and sampling noise or rewards) via \\ eta_ T(i) . This is quite weird. What does it mean for a real-life setting? To calculate NE, each arm should not only know \\theta^* but also the true contexts of other arms (in addition to future stochasticity). Is my understanding correct? I urge the authors to better explain this assumption (maybe in the appendix) with a real-life example and highlight the necessary information model.\n\n\n2)In the result of theorem 4.2. Is it possible to give regret bound in terms of d, not K ? From my understanding of bandit literature, the cost of manipulation may be calculated in terms of d. Can you comment if it is possible to calculate the cost of the mechanism in terms of d instead of K?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer XxQv, thank you for taking the time to read and review our paper. We respond to your questions below. \n\n> 1. Regarding model description, my biggest concern is the assumption that the arms respond to the learning algorithm $M$ in Nash Equilibrium. Specifically, the definition of NE for arm  i  depends on future stochasticity (randomness in M and sampling noise or rewards) via $\\eta$. This is quite weird. What does it mean for a real-life setting? To calculate NE, each arm should not only know $\\theta^*$ but also the true contexts of other arms (in addition to future stochasticity). Is my understanding correct? I urge the authors to better explain this assumption (maybe in the appendix) with a real-life example and highlight the necessary information model. \n\nYes, you are correct in that the arms account for future stochasticity and contexts (in expectation). The reason for these assumptions is that we must ensure that the NE is well-defined. Without such knowledge, it is not clear what a best response for an arm is and we would instead need to, e.g., assume that the arms have a prior over the contexts etc. Even then, it can be unrealistic to assume that the arms reach an equilibrium (even in less complex models than ours). To this end, analyzing $\\varepsilon$-NE can be helpful. \n\nIn the added experiments (see rebuttal.pdf), we also study the case where the arms optimize their strategy over time using gradient ascent, which is a fairly natural model of strategic adaptation. Importantly, in this case, we do not need to assume that the arms have any prior knowledge (neither $\\theta^*$ nor anything else). Instead, the arms learn to adapt their strategies purely based on sequential interaction. In future work, it would be interesting to also theoretically analyze these types of situations (e.g., arms are no-regret learners). We additional explanations to the main text and added a thorough discussion of this to the appendix. Thank you for bringing this to our attention. In the appendix, we now also mention that the regret bounds of Theorem 4.2 and 5.2 directly extend to the case where the arms do not reach equilibrium but instead play any $O(\\sqrt{KT})$-NE and $O(d\\sqrt{KT})$-NE, respectively. \n\n\n> 2. In the result of Theorem 4.2. Is it possible to give regret bound in terms of $d$, not $K$? From my understanding of bandit literature, the cost of manipulation may be calculated in terms of $d$. Can you comment if it is possible to calculate the cost of the mechanism in terms of $d$ instead of $K$?\n\nIn the setting of Theorem 4.2, the latent parameter $\\theta^*$ is known to the learner in advance. As a result, the regret bound does not involve $d$. In general, any dependence on the dimension $d$ is only expected when we have to learn $\\theta^*$. Unfortunately, we also cannot artificially swap the dependence on $K$ for a dependence on $d$, as the reason for the $K$ dependence is the fact that we need to incentivize *all* strategic arms to be approximately truthful, which automatically yields a dependence on the number of arms. \n\nWe are not really sure in what part of the literature the cost of manipulation is calculated in terms of $d$. In the literature on linear contextual bandits with adversarial corruptions, the manipulation is typically captured by an additive or multiplicative term $C$. Sometimes $C$ is defined as the total amount of context manipulation so that it is somewhat related to $d$ (however, $C$ is not expressed as a function of $d$).  Please let us know if you have any other questions or if we misunderstood your question.", "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": "S3tqqKqHyW", "reviewer": "Reviewer_7kzE", "summary": "This paper studies the strategic linear contextual bandit problem, where the agents can strategically change (report) their covariate to the principal. The authors propose an Optimistic Grim Trigger Mechanism (OptGTM) to encourage agents be truthful and achieve sublinear regret.", "questions": "1. The authors assumed that the inequality in Assumptions 1 and 2 holds. Could the authors change it to inequality after taking expectations over X? What if these assumptions fail?\n\n2. Some related works are missing. Typically, when agents are strategic and incentivized to change their features, their private types can confound the observed covariates $x_{t,i}$ and the noise $eta_i$. Consequently, applying the loss in equation (3) would result in a biased estimator for $\\theta$. Relevant works include:\n\nHarris et al. Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses.\nYu et al.  Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments. \n\nCould the authors also comment on this point?\n\n3. Could the authors conduct some numerical studies to support their theoretical findings?", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors design a new framework and new theoretical guarantees to both achieve the Nash equilibrium and minimize regret.", "weaknesses": "see my questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 7kzE, thank you for reviewing our paper. Your time is highly appreciated. We respond to your questions below. \n\n> 1.  The authors assumed that the inequality in Assumptions 1 and 2 holds. Could the authors change it to inequality after taking expectations over X? What if these assumptions fail? \n\nWe assume a possibly adversarial sequence of *true* contexts $x_{t,i}^*$. However, if we were to assume stochastically sampled contexts (which is a stronger assumption), we could indeed take an expectation over this distribution and our results still hold. When the assumption is violated and the arms can under-report their value, the problem appears to be intractable in some special cases (without other arguably stronger assumptions). We provided an example and discussion of this observation in Appendix C. \n\n>  2. Some related works are missing. Typically, when agents are strategic and incentivized to change their features, their private types can confound the observed covariates  $x_{t,i}$  and the noise etai. Consequently, applying the loss in equation (3) would result in a biased estimator for $\\theta$. Relevant works include: Harris et al. Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses. Yu et al. Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments.\n\nThank you for pointing us to these papers. While this is a quite different perspective on strategic learning to ours, we agree that strategic regression and, in general, feature confounding based on types is quite relevant to our work. We added a brief discussion highlighting similarities and differences to Section 2 (Related Work) under 'Strategic Learning'.  \n\n> 3.  Could the authors conduct some numerical studies to support their theoretical findings?\n\nFollowing your and the other reviewers' suggestion, we have added experiments to the paper (see rebuttal.pdf). We believe thes experimental results are quite interesting and nicely illustrate the effectiveness of OptGTM and the necessity of a mechanism design approach in the strategic linear contextual bandit.", "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": "6iI2LGBBRJ", "reviewer": "Reviewer_QjK5", "summary": "This paper studies a variant of the linear contextual bandit problem, where each arm is an agent and can strategically misreport its feature vector to the learner. The authors propose the Optimistic Grim Trigger Mechanism (OptGTM) that incentivizes the agents to report their feature vectors truthfully while simultaneously minimizing the regret. The paper first shows that if an algorithm does not explicitly consider the incentives of the agents, it can incur a linear regret. Then, the authors propose GGTM for known $\\theta^*$ and OptGTM for unknown $\\theta^*$, which achieve sublinear regrets.", "questions": "See Weaknesses.", "limitations": "Limitations are adequately discussed in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper addresses an important and novel problem. The setting is innovative and has practical implications.\n2. The algorithm design is simple and intuitive, and the theoretical analysis is rigorous.\n3. The proposed OptGTM algorithm works for unknown $\\theta^*$, which is an impressive result for me.\n4. The readability is excellent (arguably the best among all the papers I reviewed). The problem setting is well-motivated, the model is clearly defined, the algorithm is easy to understand, and the flow of writing is logically coherent.", "weaknesses": "1. There is no experimental evaluation in the paper. While I understand that many theoretical papers do not include experiments, it would be beneficial to see some empirical results to validate the theoretical claims.\n2. The assumption of the constant optimality gap (Lines 150-151) is unusual for regret minimization. Is there any reason for this assumption? It would be better if the authors could provide some rationale behind this assumption.\n\nUpdate after rebuttal: The authors added some experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer QjK5, thank you for your time and your review. We respond to your comments below. \n\n> 1.  There is no experimental evaluation in the paper. While I understand that many theoretical papers do not include experiments, it would be beneficial to see some empirical results to validate the theoretical claims.\n\nThanks for the suggestion. We added experiments to the paper, which you can find in the rebuttal pdf.  In the experiments, we adopt the perspective of each strategic arm greedily updating its strategy to maximize its utility. The results support our theoretical results and the effectiveness and generality of the proposed mechanism design approach.  \n\n> 2.  The assumption of the constant optimality gap (Lines 150-151) is unusual for regret minimization. Is there any reason for this assumption? It would be better if the authors could provide some rationale behind this assumption. \n\nWithout this assumption, the equilibrium behavior of the arms becomes difficult to analyze. For instance, consider the case where every time arm 1 is optimal it is only better than arm 2 by an amount $1/T$ (in terms of rewards). Then, roughly speaking, arm 2 only has to manipulate its contexts by a total amount $\\leq 1 = T\\times  1/T$ to \"poach\" all selections from arm 1. This tiny amount of manipulation by arm 2 is statistically undetectable so that we *cannot* prevent arm 1 losing all its utility when being truthful. In other words, we cannot promise arm 1 that truthfulness is a viable strategy (not much worse than untruthful reporting). This does not consequently mean that arm 1 will heavily manipulate its contexts in NE, but it does mean that we cannot use the truthful strategy as a \"benchmark\" when analyzing the NE (in the proofs of Theorem 4.2 and 5.2, we use that each arm's NE strategy must be a better response than the truthful strategy). We added a foonote to the main text explaining this and discuss this in an additional paragraph in the appendix.", "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": "dNUBthqvtc", "reviewer": "Reviewer_8u5z", "summary": "The authors studied the problem of strategic agents who can modify their context in order to game the system under the linear contextual bandit framework. In this setting, each arm is a self-interested agent who wants to maximizes number of times it gets pulled by the learner. Prior work that did not explicitly consider the incentives of these arms suffers linear regret in the strategic setting. The authors proposed two mechanisms, first to deal with the case when the underlying parameter of the reward function is known to the learner in advance, and then when it is unknown to the learner. In either case, the proposed mechanism can incentivize the arms to be approximately truthful in reporting their true context to the learner. Furthermore, the authors provided strategic regret guarantee for each of the proposed mechanism that scales with $O(K^2 \\sqrt{KT})$ when the latent parameter is known and $O(dK^2 \\sqrt{KT})$ when the latent parameter is unknown.", "questions": "- Does manipulation budget for each arm matter in this setting? That is, does the current analysis change if the arms are only allowed to modify their true context by at most some (maybe unknown) values?", "limitations": "The authors have addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The studied problem of strategic linear contextual bandits is interesting, and the setup is novel.\n\n- The paper is well-written and easy to follow. \n\n- The theoretical bounds are clearly listed, and justifications for the differences in regret compared to non-strategic setting is provided.", "weaknesses": "- The paper did not provide matching lower bound analysis on the strategic regret in the two settings: when $\\theta^*$ is known in advance and when it is unknown in advance by the learner. \n\n- The notation in the Introduction is somewhat confusing. The authors refer to the strategic agents as arms, and use learner to denote the (what would typically be called) bandit agent. Furthermore, in the main contributions, the regret bound for the setting where $\\theta^*$ is unknown in advance uses $d$, which has not been introduced at this point (and only introduced in Section 3 later on). \n\n- The paper relied on a key assumption that the arms do not under-report their value. While this assumption seems intuitive, the authors did discussed in Appendix C that there might be cases where under-reporting may make sense for the arms. \n\n- The authors did not provide experiments to support their theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 8u5z, thank you for taking the time to review our paper and your helpful comments. We respond to your questions and comments below.  \n\n> - The paper did not provide matching lower bound analysis on the strategic regret in the two settings: when $\\theta^*$ is known in advance and when it is unknown in advance by the learner. \n\nThese are interesting questions for future work. In general, deriving lower bounds in strategic settings like ours is very challenging due to the intricate relationship between the learning algorithm and the equilibrium strategies that it induces. Note that we do inherit the $\\Omega(d \\sqrt{T})$ lower bound from the standard linear contextual bandit in the case where $\\theta^*$ is unknown. However, as we conjecture in the discussion (Section 6), we believe the lower bound for the strategic problem to be $\\Omega(d \\sqrt{KT})$. \n\n> - The notation in the Introduction is somewhat confusing. The authors refer to the strategic agents as arms, and use learner to denote the (what would typically be called) bandit agent. Furthermore, in the main contributions, the regret bound for the setting where  $\\theta^*$  is unknown in advance uses $d$, which has not been introduced at this point (and only introduced in Section 3 later on). \n\nThanks for pointing this out. We made according modifications to the text addressing these things. \n\n\n> - The authors did not provide experiments to support their theoretical findings. \n\nBased on your and the other reviewers' suggestion, we added experiments to the paper. You can find the experiments and the experimental details in the rebuttal pdf. \n\n> - Does manipulation budget for each arm matter in this setting? That is, does the current analysis change if the arms are only allowed to modify their true context by at most some (maybe unknown) values? \n\nThanks for the interesting question. Assuming a manipulation budget would not really change the setting. The main difference would be if we were to assume an extremely small manipulation budget of, e.g., constant size $C= O(1)$. For such small budgets, incentivizing the arms to be truthful is not necessary (after all, the amount of manipulation is almost insignificant). Instead, taking an adversarial (instead of strategic) approach would suffice, where we would slightly enlargen our confidence sets / increase exploration parameters to minimize regret. However, if the budget is large, then our approach, which does not rely on any assumption about the budget but instead bounds the effect of the arms' manipulation on our regret and the arms' utility, is necessary and much more effective. It is also worth mentioning that artificially assuming a manipulation budget can be unrealistic in practice and is one of the shortcomings of purely adversarial settings (see also reference [10] in the paper).", "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:
Thank you for taking the time to review our paper and for your helpful comments. 

Reviewer 7kzE, Reviewer QjK5 and Reviewer 8u5z suggested to include experiments in the paper. Following your suggestions, we conducted simulations of strategic context manipulation, which we added to the paper (see rebuttal.pdf). 

In the experiments, we study the situation where the strategic arms gradually adapt to the deployed learning algorithm to maximize their utility. Specifically, the arms repeatedly interact with the deployed bandit algorithm, updating their strategy (i.e., what contexts to report) at the end of each interaction using (approximate) gradient ascent w.r.t. their utility. In other words, the arms learn to maximize their utility in response to the deployed algorithm. This experimental setup should serve as a natural and simple model of real-world gaming behavior, which does *not* require any prior knowledge from the arms, and the experiments offer some additional insight into the effectiveness of OptGTM as well as the shortcomings of incentive-unaware algorithms such as LinUCB.

Meta-review: This work studies the problem of Strategic Linear Contextual Bandits, where each of the arms could misreport their contexts with the goal of maximizing the number of times they are selected. The authors design a novel algorithm in the setting where the linear bandit parameter $\theta^*$ is unknown and show that the algorithm enjoys nice regret guarantees. The proposed problem is interesting from a theory perspective and might have some practical implications.

Most reviewers agree that the paper is very well written and that the presentation is excellent. Further all reviewers agree that the new setting is interesting and that the contributions are good. Some concerns that reviews have expressed are about how realistic it is to assume that arms are able to compute (approximate) NE (this likely requires knowledge of the algorithm $M$ and how other arms play),  optimality of the regret bounds, and lack of empirical evaluation. Authors address these concerns to the satisfaction of the reviewers and include some empirical evaluation of their algorithm.

Overall I find this paper interesting and with good theoretical contributions. I recommend that the authors include the response to the above reviewers concern in some way to the final version of this paper. Further, the authors should include their empirical evaluation as a new section to the paper. I am happy to recommend the paper for acceptance to the venue.
Decision: Accept (poster)