Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting
Authors: Ahmed Ben Yahmed
Clément Calauzènes
Vianney Perchet
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-Armed Bandit Problems
Strategic Arms
Incentives
Primary area: bandits

Abstract: We examine multi-armed bandit problems featuring strategic arms under debt-free reporting. In this context, each arm is characterized by a bounded support reward distribution and strategically aims to maximize its own utility by retaining a portion of the observed reward, potentially disclosing only a fraction of it to the player. This scenario unfolds as a game over $T$ rounds, leading to a competition of objectives between the player, aiming to minimize regret, and the arms, motivated by the desire to maximize their individual utilities. To address these dynamics, we propose an algorithm that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible. Utilizing this algorithm, the player can attain the second-highest average (true) reward among arms, with a cumulative regret bounded by $O(\log(T)/\Delta)$ (problem-dependent) or $O(\sqrt{T\log(T)})$ (worst-case).

Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting
Ahmed Ben Yahmed CREST, ENSAE, Palaiseau, France Criteo AI Lab, Paris, France FairPlay joint team a benyahmed@criteo com
Clément Calauzènes Criteo Al Lab, Paris, France FairPlay joint team
c. callauzene@@rrtee.ccom
Vianney Perchet
CREST, ENSAE, Palaiseau, France Criteo Al Lab, Paris, France
FairPlay joint team vianney. rianney.percher porchhettnmooomalessu .rggg
Abstract
We consider the classical multi-armed bandit problem, but with strategic arms. In this context, each arm characterized by bounded support reward distribution and strategically aims to maximize its own utility by potentially retaining a portion of its reward, and disclosing only a fraction of it to the learning agent. This scenario unfolds as game over T rounds, leading to a competition of objectives between the learning agent, aiming to minimize their regret, and the arms, motivated by the desire to maximize their individual utilities. To address these dynamics, we introduce new mechanism that establishes an equilibrium wherein each arm behaves truthfully and discloses as much of its rewards as possible. With this mechanism, the agent can attain the second-highest average (true) reward among arms, with a cumulative regret bounded by Olog(T)/A) (problem-deeenddent) (ooo((TT)/naeeeeeeeeeeeeee (lg(T)) (worst-case).
Introduction
The multi-armed bandit (MAB) problem serves as a fundamental modeling framework for exploring the interplay between decision-maiee making agent (or player) and set of arms. Its primary aim is to enable the player to learn the most favorable sequence of decisions over time. In formal terms, we consider a scenario involving K arms, where, each time step the player selects one arm k2 from the set (1, 2..., K) and receives a reward, denoted as rk,,t- These rewards can either be generated stochastically or determined adversarially. The player's overarching objective is to strike balance between two key aspects: exploration and exploitation. Initially, he must explore all arms adequately gain confidence in identifying the best-performing focuses on exploiting this knowledge to maximize his cumulative reward over subsequent rounds. Established algorithms for this problem ensure that the player's performance is nearly as good as selecting the best individual arm, thus minimizing his regret ① 2 3 This modeling framework has broad real-world applications, including domains such clinical trials [4] 5 recommender
Once this is accomplished, he
systems (6), and resource allocation problems [7]. However, in many of these scenarios, arms are traditionally viewed as passive entities, faithfully reporting their generated rewards rk, the player.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This perspective leaves out an array of dynamic agency dilemmas, where the player selects one of the K agents (arms) each time step to execute a task on his behalf, with the associated cost remaining hidden from the player due to his limited domain or market knowledge. Essentially, the player is uncertain about the precise costs or returns until the task is completed, and the agent has substantial freedom to set these ex-post [8] In this context, it is reasonable to assume that arms are strategic and may act in their self-interest. Conceptually, arms can report a value, denoted as .t which may differ from the actual reward .t retaining in the process net utility of rh IRe 3. This strategic scenario introduces a game-like dynamic, creating a competition of objectives between the player, aiming to minimize his regret and the arms, wishing to maximize their own utilities.
Motivated by numerous real- real-world applications where, by design, strategic arms operate under restricted payment conditions, our study focuses on debt-free reporting. In this setting, arms cannot report values higher than the observed reward. An illustrative example pertains to scenarios with binary variables, where declaring a fake failure is possible but creating a fake success is impossible. This situation is evident in e-commerce, where advertisers receive rewards for successful ad campaigns that result in a sale after a click. Notably, an e-commerce platform may choose to conceal a sale, but it cannot fabricate one. This setting is also referred to budget-balance in the repeated trade literature [9] [0], requiring I S T,e for all t, or equivalently, (Z Tk,,e) belonging to the upper triangle T = ((a,b) b) E S² a S b). where S represents the variables' space.
2 Problem Statement
The concept of the strategic multi-armed bandit builds upon the foundation of the classic multi-armed bandit problem, introducing novel element wherein the arms possess the capability to retain portion of the reward for themselves. Within this framework, we contemplate a collection of K stochastic arms denoted by k E {I...., K). where each arm possesses bounded reward distribution Da supported on [0. 1]. Each arm is distinguished by its reward mean, denoted as (4k- To maintain generality without loss of clarity, we assume, for the presentation and the analysis,
ordering such that μ1 2 122 2 ... 2 PK (unknown to the player). In each round t, the player selects an arm denoted ky- This arm k, then observes reward Fk., [0, 1]. Subsequently, the arm reports a quantity I to the player and retains Tk,,t IR. as its own utility. In this scenario, it is important note that solely arm ky possesses knowledge of the actually observed reward r whereas the player is privy only to T and remains unaware of the withheld portion. Hence the decision of the player is based on the information gathered until time which can formally encoded in Fp, = {k,, T implying that h2 is a (Fpz) measurable. Conversely, the arm kg 's available information is succinctly represented by Fk,, [kzz Tkk.s: s: Ikk kr, 2 Je<tt:k =k, (ke Jecc and T is a (Fk,,)) measurable. Specifically, this indicates that the tacit model is being utilized, wherein the arms are informed about the pulled arms at each round and only observe the reward upon being chosen.
Furthermore, we operate under the debt-free reporting assumption: arms are prohibited from incurring negative balances when reporting x,,,, implying the following constraint S Ik,, S Tke Vt 2 1. In the context of strategic bandits, the player has the option to allocate a bonus V to each arm k {I..... }} at the end of the game. This bonus serves as an incentive to encourage arms to provide truthful information, for instance. It can take various forms, including additional rounds of pulling as in [8] or simply a bonus payment awarded the arms, similar to payments in the usual mechanism design for procurement auctions [II]. In this work, the latter option has been chosen for use, i.e. bonus payment- based algorithm. Therefore, the interaction between the player and the arms can be encapsulated in the Model
Model 1: The Strategic Multi-Armed Bandit Problem
Player commits to an algorithm A, which is public to the arms
2 for f = 1,..., do
T
Player selects arms he E (1....,K) K} according to the chosen algorithm A Arm it observes reward rk,, Dx:
Arm Kt reports IR, E [0, rk. to the player
end
Player assigns bonuses V to each arm k E {1...., K}
2

---

2.1 Arm Utility and Subgame Perfect Equilibrium Among Arms
Let us denote by P. the set of all possible arm strategies, by Th = (TT,, E P the strategy of arm & and by from the past history U {0, 1]2a x {0, } to [0, 1]. Here, [0, 1] denotes the accumulated observed and announced rewards, and {0, 1 indicates the rounds during which this arm has been selected thus far. Let a& R. (and F& R be the sequence of the reported values (and rewards, respectively) by arm l across T rounds where R, = R {+}. and the symbol 'x" is used for rounds when the arm is not observed. We also refer 3y the path of arm k under strategy π. Let x
(TI...... TT) the strategy profile of the arms. Explicitly, P is the set of mappings
denote the K 1 paths of all arms except k. As a result, the utility associated with arm is defined in ex- ex-post fashion follows:
Ux Tk, -T) = Σ (T - (t) [B + V Ve(ck x-
(1)
(I)
which is the cumulative savings over rounds plus the corresponding assigned bonus (we slightly abused notations here, as Vr only depends on the observations of the player, and not the full vector Tx). Given that each arm aims to maximize its own utility, we introduce the solution concept of subgame perfect Nash Equilibrium (SPE) among arms. A strategy profile π is SPE if ア is an optimal strategy for any arm k considering any history and given any strategy - k <pK1 adopted by other arms, at any time t.
2.2 Player's Strategic Regret
In the strategic scenario, the player. under the most unfavorable circumstances, cannot guarantee to achieve gains surpassing (lg. This limitation arises from the fact that the optimal arm merely requires a marginally higher reported value than the second- best arm to be chosen as the superior option by the player (see Section 2.3 for more details). In addition, the bonus allocated to the arms is deducted from the player's total revenue; hence, these bonuses are factored into the regret definition. Therefore, the regret, arising from the cumulative expected discrepancy between fl2 and the value reported by the selected arm k; over T rounds, along with the bonus values, is defined as follows:
T
K
R1 = E
Σ
(n2 Tk.
+
V MM
A=
2.3 Related Work
A simplified instance of the strategic bandit problem has been examined within the context of the principal-agent problem in contract theory [2] 13] In this analogy, a player engages an arm with greater expertise in a specific domain to perform work on his behalf. However, the arm may exploit the player's lack of knowledge the strategic bandit problem can be viewed as inspiration from the field of online advertising, several studies have delved into dynamic mechanisms
maximize its own utility and accumulate private savings. Consequently,
problem. Additionally, drawing
to address similar scenarios [4 15 16 17
18
19
20). For instance,
21 examined auctions with
reserve prices involving strategic myopic buyer.
In particular, [22 studied strategic arms but with a distinct utility function that depends solely on the number of pulls. this scenario, each strategic arm aims to maximize the total number rounds it selected rather than cumulative savings. The authors demonstrate that stochastic MAB algorithms are robust to strategic manipulation, allowing the player to achieve p with a sublinear regret. Under their utility definition, arm is content to report the entirety of its reward as long as it is selected, justifying their use of the best mean [4 as a comparator for regret.
A comparable study was conducted by 23 albeit with variation in the arm's 's utility function, which incorporates the number of pulls alongside savings. The primary difference lies in their incorporation of a non-empty set of truthful arms, among other considerations. In this context, where arms are informed about competition and with additional assumptions conducive to specific MAB algorithms, they establish the resilience of these algorithms to strategic manipulation. However, when arms lack
[1 if b otherwise
(1 g is the indicator function: 1 [m=b]
{
3

---

information about competition, they propose a mechanism reliant on the presence of truthful arms, ensuring a substantial revenue for the player.
The most related setting is considered by [8]. They addressed a multi-armed bandit problem with strategic arms, employing a similar utility function, dependent on cumulative savings as outlined in (T. Their work revealed that if the player aims for the highest mean μa i..., employs no-regret strategy - then the arms can form an undesirable equilibrium that leaves the player with a sub-linear cumulative revenue. Consequently, any incentive-unaware learning algorithm that is oblivious to the strategic nature of the arms is not resilient to such a utility definition and will generally fail to achieve low regret. Therefore, it becomes crucial to design algorithms that rely only on sequential crtisiinnmakinn but also on incorporating incentive mechanisms to enhance truthfulness. In this context, Lemma 14 of [8] establishes that no mechanism can guarantee more than pºl as revenue for the player in the worst case. This observation justifies the use of μ22 as a comparator in the regret definition. As solution, they propose mechanism referred to here as S-ETC (Strategic Explore Then Commit). When arms have the flexibility to report any value within the range of [0,1], potentially incurring negative utility, S-ETC ensures that the player achieves revenue of pz with sub-linear cumulative regret. However, under debt-free reporting, the player incurs an additional regret of O(T3) within given Nash equilibrium among the arms.
2.4 Objectives and Challenges
The central question we address whether there exist, under debt-free reporting, an algorithm for the player that establishes Nash equilibrium for the arms, guaranteeing lower regret, akin to classical non-strategic bandit settings [24 25 26), or not.
Dealing with strategic arms in the context of debt-free reporting poses significant challenges, espe- cially when striving to minimize regret. Our overarching goal is achieve a regret of O ((oo(()) This task proves to be far from straightforward, as it cannot be resolved by merely adapting prior research. In particular, when considering the fixed design (i.e., non adaptive exploration phase) solution proposed by [8) the minimum bonus required to ensure truthfulness is directly proportional to the length of the exploration phase. This cannot provide regret guarantee better than O
Furthermore, this observation underscores that achieving incentive-compatiiiiyy cannot be solely contingent on the bonus, it tends become prohibitively costly for the player. To address this, we shall rely on the adaptive elimination of arms, introducing secondary trade-off for the arms that enables reduction in the bonus requirement. The less faithful an arm behaves, the more swiftly is removed from consideration. However, this approach grants arms some control over the number of their pulls, necessitating meticulous design in other aspects of the mechanism.
2.5 Contributions
We operate within the framework of debt-free reporting, wherein each arm is constrained to report values no higher than its observed outcomes. In this context, our contributions are:
1. We introduce a novel incentive-aware learning algorithm, denoted as Algorithm ID S-SE, which integrates mechanism design and online learning techniques. This algorithm adeptly motivates favorable This introduces a strategic tradeoff for arms, balancing high savings through dishonesty with the risk of swift elimination.
strategies, minimizing regret by adjusting well-calibrated bonus.
2. We demonstrate that under Algorithm[I ! there is foomnnnttsstattee SPE in our game, where each arm simply reports truthfully, as proven Theorem 4.1 Under this equilibrium, the player provably obtain an expected revenue of Ji2T, up to a sub-linear regret that is bounded
by O
where gaps are defined as: Aij = 14i Mg. Vi,j E {I...., , K}. In the worst-case scenario with significantly small gaps, the regret bound is of
Ek k= Ags
log(T)
+ =k= Art
log(T)
O KT log(T) as outlined in Theorem 4.2 This result outperforms the regret bound of (T24/3) presented in the literature within the examined setting (see Table I
3. Under additional technical assumptions, we analyze the player's regret incurred when employing Algorithm I within any arms strategy profile. This analysis aims to provide a comprehensive characterization of a broad range of potential equilibria.

---

Table
Comparison summary between S-ETC
8 and S-SE: setting and results.
Tacit Model
Debt-free reporting
Bonus nature
Regret
S-ETC
8
V
Additional rounds
(TT4/3)
Problem-dependent
(Tog((T) A)
S-SE
/
Payment
Problem-independent
Ol O(yKT O(yKTlog(T)
3
The Player Algorithm
This section is dedicated to the description of the algorithm used by the player. We first introduce some notations.
Let (E....k be set of K real values evaluated at time f. We then denote by a the vector obtained by concatenating values {ag.a (t....... i.e., a. [a1,t: 02,t, ... dx,)). We also denote by a bijection from (1,...: K} itself that gives the index of the 1tth highest element in vector For example, if a [1, 10, 4. 6). then (1) represents the index of the highest value in which 2. Likewise, aa (2) = 4, aa (3) = 3, and (4) = 1. The inverse this mapping provides the rank associated with given index. When the context is clear,
simplify the notation and omit the
vector a, proceeding directly with a and its inverse o-1
Let S be set; then we denote the cardinality of S by |S]-
3.1 Algorithm Presentation
Algorithm [ closely integrates a strategy that combines successive elimination and bonus allocation, hence it referred to Strategic Successive Elimination (S-SE). It is structured into distinct phases:
composed of the first r rounds (a random stopping time defined in (8), where adaptive exploration technique is employed, based on round-robins on active arms leading series successive eliminations aimed identifying the best-performing arm. To achieve this, the player keeps track of the number of times (t) each arm & is pulled up to time t, defined as:
The Initial Phase.
Th (t)=
1 [k,=k]
(3)
1=1
Additionally, the empirical average of received rewards from arm & at time t computed as:
i Th
Zk,s 1l [[k.=A]
(4)
This is distinct from the empirical average of observed rewards:
1 (t)
Σ Tkis [
(5)
which is observable only by the concerned arm k. The relevant quantity to the player is f. = (pR,))e[[] and its ordering mapping Oz.- However, to alleviate cumbersome notations, we shall use from now o, instead of o..-
Leveraging Hoeffding confidence bound and denoting dxec
2 2log(T)
nx(e) the algorithm effectively
eliminates arms that are likely to perform worse than the best arm with high probability. Hence, an arm & is eliminated at time if the following event is happening:
E = (fo.(1), (o.(1), 2 jun, + a..r)
which leads to define the stopping time at which arm & is eliminated, with the convention that inf (1 +00,
= inf [T) Et)
5

---

Algorithm 1: Strategic Successive Elimination (S-SE)
Let A (.,.... K the set of all arms and t=1
while í < T and [A, > 1 do
Play & E {K E A argmin nu - 1)} hEAL
Update (1) and jugt if nxt() n (1), Vk, k' E E, then Ar+1 = As {k E A+ Pai0)) ao00) 2 Met + ax,))
Drop bad arms
else
Ar+1 Ar
end
10
t=t+1
end
is the length of the first phase Identify the arm with the highest average or (1), denoted k- for t + 1, do
12
Play and receive the reported value Tg+,t 14
15
Compute F
Σ
T
#=1+1
16
a < (in (e) (o,(1).
[og(T)
t-7
then
17
Set 2 =0
Incentive
18
Stop playing k* immediately and move to step end
Incentive
20 end
Allocate bonuses VkE(I....K]
Incentive
Consequently, the number of active arms in the As progressively reduces over time until, eventually, only the best-performing a random stopping time. It is not fixed from the outset but dynamically adapted to the statistical characteristics of the arms, and is defined as:
remains. Hence, the duration of this initial phase, represented as
it (t E [T] [Ad 1) inf { t T [ SS, C cI,, K) s.t [S K 11 and n
Ex
kES.
(8)
The Second Phase. It starts after stage т and thus may never happen, as classical MAB. such case, for / >> the best arm, i.e. h: = (1), is required to report average value that surpasses at least the hiigest average achieved at the conclusion of the initial phase, denoted as (2,(2),r If the player confidently detects the best arm is defecting and fails to report much, is no longer played. Additionally, its bonus is set to zero, and the game is halted (we assume that the player can choose to end the game when the best arm defects).
At the conclusion of the game, bonus denoted Vr assigned to each arm k, based on P[r] and its rank o- (A). The strategic distribution of bonuses serves as an incentive mechanism to encourage truthfulness. Drawing inspiration from real-world practices in financial exchanges within e-commerce, all bonus payments are deferred until the end of the game to ensure incentives.
Definition 3.1. Let represent the last time when arm k is active. Let 7 and r' respectively denote the duration of the first and second phases. Then the bonus function Vx defined as following:
V. Vx(2,, x=-) (Tu(T) - D -0.2-1 + ze.T) ((r-(1=6) (147/22
16 loggg(T)
+ DuiT
of
(9)
Hence, contingent their ranking at the conclusion of the first phase:

---

arm: if it refrains from defecting during the second phase, it will be rewarded with bonus that compensates for the discrepancy between its reported value and the second-best reported value. This process mirrors the dynamics observed in second-price auctions.
The
Suboptimal arms: they will receive a bonus inversely proportional to the difference between their means and the best arm mean. Consequently, the bonus increases as the reported values grow larger.
By implementing anytime tests to eliminate arms during the first phase (line 6 of Algorithm []) the algorithm introduces strategic tradeoff for arms, balancing the advantages of dishonesty with the risk of expedited elimination. This tradeoff' constrains potential gains from dishonest behavior, resulting in smaller bonuses required to ensure truthful reporting and, consequently, providing more robust guarantee. In contrast to the fixed design with predetermined exploration phase length introduced in [8) where arms know from the beginning exactly how long they will be played during the first phase independently of their performances, giving them more freedom and requiring larger bonuses (proportional the exploration phase) to ensure truthfulness, which more costly than the bonus given in Definition 3.1
4 Dominant-Strategs SPE
Algorithm D combines elements of bandit algorithm and incentive mechanism, creating beneficial tradeoff' that encourages truthful reporting as a dominant strategy for each arm in any subgame. Consequently, each arm reporting truthfully forms a dominant-strategy SPE. Specifically, we demonstrate that the utility of arm l under the truthful strategy T dominates its utility under any other strategy k. given any fixed history 22)
k = [kz Tk., Destkk U (ka)ase Formally, define the subgame utility of arm k under strategy profile (TK, π -k), at time t given any history ha.t-1 as:
U& (T he. " (rk, FKKo) [R. (
(10)
where the history hg is implicitly considered within V
Theorem 4.1 (Incentiee-ooppaibili
Under Algorithm 7 aand using the bonus function in Defini- tion 3.7 for any arm any strategy i. any strategy profile of other arms π -k any time I, and given any history hg,t-1 1-1,, the truthful reporting strategy n satisfies:
Uz π : Thh S 4x π -n](t Thaa--l
(11)
Proof. See Appendix
Therefore, truthful reporting is best response to any strategy profile π -k. Consequently, each arm playing truthfully forms a dominant-strategy SPE.
Regret Bound. Under the dominant truthful SPE established in Theorem we compute the player's 's regret over T rounds. As previously discussed, the regret is calculated in relation to ulz Notably, subtlety arises in the strategic scenario as compared the non-strategic one: we must factor in the bonuses paid when calculating the regret.
Theorem 4.2 (Regret Bound). Let T 2 The regret of Algorithm 7 upper- as:
K
log(T)
K
log(T)
R₂ S
(12)
Aik
Aek
k=3
The bestance-independeee regret upper-bound is given by:
Rr s O (VKTToog()
(13)
Proof. See Appendix D
By definition, the history combines the information available to the arm to make decision concerning the reporting, in addition to the reported value. ie he,,e Fk..t (wh..t).
7

---

Theorem 4.2
demonstrates that the regret bound under the considered setting is significantly lower than the regret attained in the Nash equilibrium presented [ under the same conditions. The bonus design compensates for any gains that may occur from being untruthful, establishing the truthful SPE. Under the latter, the algorithm the classical successive elimination algorithm designed for the non-strategic MAB, whose worst-case regret is known to match that of Theorem 4.2 At the same time, the successive climinations create a trade-off between high savings from dishonesty and swift elimination, which reduces the bonus values needed in a way that they do not incur an additional harmful cost for the regret.
A second observation is that the instance-dependent regret matches the one of regular MAB o (Σ log(T)
2- Ait up to a second additive term of the same order O E> log(2") This second term comes from the additional need to correctly estimate the value of the second-best arm make sure to "bill" accurately the best arm during the second phase. The less accurate the estimation of pg- the larger the deviation the best arm could have in the second phase without being detected. As the gain from potential deviation is incorporated in the bonus to ensure truthfulness, the accuracy of the estimation of μl2 impacts the regret.
It's worth noting that the truthful SPE highlighted in Theorem 4. might raise questions about the regret comparator (22- In other words, if truthfulness exists, why can't we expect to achieve rewards of 2ur? While it's true that arms are incentivized to be truthful, this motivation is realized through the allocation of bonuses at the conclusion. Bonuses are part of the arm's 's utility and contribute to making truthful reporting the best response that maximizes utility. Specifically, the best arm is incentivized with a bonus of O (1)) Since the bonus is integral to the regret calculation, we compute the regret relative to #22 in manner similar to the approach justified in Lemma 14 of (8)
Tightness of Regret. For simplicity, let's consider three arms with Ma 2 /22 2 43. The optimal arm only needs to report slightly higher value than the second-best arm to be chosen by the player as the superior option. Consequently, all efficient low-regret mechanisms must ensure truthfulness, at least for the two best arms. Under debt-free reporting, where no arm can falsely claim to be better than it actually is, distinguishing between the two best arms incurs regret of log(T) Additionally, Au2
distinguishing between the second and the third arm is required to estimate the second-bes best mean accurately, resulting in regret of log(?) However, the third arm does not need to be truthful; we only need to distinguish it from the second-best arm. Therefore, in general, the incurred regret will be of order log(2), where A23 is the difference between the true mean μ12 and an effective mean jáz, which can be different from μz3. Ideally, W3g = 0 to minimize the corresponding regret i.e incentivizing non-truthful strategies for arms k 2 3. allowing the player to identify the second-best arm more quickly. Nonetheless, in all cases, the regret will be of the same order as the one described (T2). In Appendix () we conducted an experimental analysis simulated data, highlighting the tightness of the regret bounds by evaluating several strategies.
Utilities Bounds. Considering the game-like dynamics between the player and the arms, alongside the regret bounds, it is natural to examine bounds on the utilities of the arms, as illustrated in the following corollary.
Corollary 4.1 (Utilities Upper Bound). Under the truthful SPE, the utility of any arm is upper bounded as follows:
(Tg(T) A
Wk E (2....,K] K} E S O
and ER4 ((T)2)
(14)
Proof. See Appendix D.I
5 Regret Analysis Across Arbitrary Strategy Profiles
In the previous section, we assessed the regret of Algorithm [when the arms adhere to the dominant strategy SPE. General profiles and equilibria in extensive games are known to be intractable [27] Specifically, for an arbitrary strategy profile that is not truthful, the values reported by the arms are not i.i.d., complicating the analysis as tools like Hoeffding's 's inequality cannot be directly applied. Consequently, determining the algorithm's 's output becomes non-trivial. To address this, we introduce an additional technical assumption regarding the boundedness of gains through dishonesty. With
8

---

this assumption, we can analyze the algorithm under a wide range of strategy profiles, not just the dominant one previously discussed.
Fix an arbitrary strategy profile æ. For each arm k. we define S = E (Tk,, as the cumulative savings of arm k up to round T. We assume the existence of some upper- -ouur-bound M on cumulative saving, i.e,, such that for all arms that S < M. We define the effective mean under strategy as Pi and let μr' (pg [k]] Therefore, we define A as the difference between the highest effective mean under strategy π and the effective mean of arm k. given by: AT 1
=k..s) 1 [p.=
[K] and for any strategy æ, must hold
M Similarly, AT represents the difference between the second-highest effective mean and the effective mean of arm & under strategy и,, defined as: A 1e (2) 1 We show that when arms use the strategy profile æ, even under non-i.i.d. reported variables, Algorithm Totpuuts by the following theorem.
ouutpts the second highest effective mean, and the regret is provided
Theorem 5.1. For any arbitrary strategy profile π with M -bounded savings, the regret of Algorithm is bounded by:
R7 = E
(o
x2s))) + Σ (a xx))
0
max
log (T)) M,
Σ
max
M, log(T))
(15)
Ag
ko (R)22
k:o Jan (k)23 (k)20
Proof. See Appendix
The upper bound of savings M determines the regret with regard to the second-highest effective mean of any strategy π, as shown by Theorem [5.]] In particular, it is demonstrated to be sublinear in T provided that M = oT)) The upper bound exhibits a similar form to the problem-dependent upper bound in Theorem 4.2 Specifically, under the truthful equilibrium π where M = O, M = pax A2t. we retrieve the result from 12 Additionally, in the debt-free
AT AIk. and A reporting setting, it is observed that for any strategy æ, = revenue drops when arms diverge from the honest SPE in way that affects the second-highes mean.
(2) I 1/2 This suggests that the player's
Sensitivity of Algorithm around truthful SPE. For a strategy profile where M = o(log (T)). the difference between the true second highest mean #2 and the effective second highest mean μoz is of the same order as the regret. In this scenario, the player's 's revenue is uzT, up to a sublinear regret R7 O (R Hence, even though the savings not zero, we retrieve results comparable to those with truthful reporting.
6 Limitations and Future Work
The algorithm S-SE, presented as an efficient solution to the strategic MAB, combines elements of successive climination with a well-tuned incentive. This raises the question: is it possible to adapt any no-regret MAB algorithm, such as UCB, with a suitable incentive to solve the same problem? A complete and detailed answer to such question is reserved for future work. However, is that this would be challenging because, a similar setting, (29 argue that a truthful mechanism under the strategic MAB problem needs to be exploration-separate.. In other words, any given time step, either it exploits (action depends on current knowledge) or it explores (action allows to gain knowledge but does not depend on current information), but not both simultaneously. This observation suggests that a tailored version of UCB (at least without additional assumptions) may not be suitable.
intuition
Despite the similarity between the algorithm of [8] and our algorithm S-SE, both being strategic versions of exploration-separatee algorithms, there is major difference in the nature of the games generated by both algorithms. In [8, all arms are played sequentially for predetermined number of explorations each before committing to the best arm, creating simultaneous-licc game. In contrast, Algorithm|
[ uses an adaptive design permitting lower regret. However, this adaptability involves an extensive game requiring more complicated analysis based on the concept of SPE.
It's also worth mentioning that the improvement in regret doesn't depend on the type of incentives, whether they are additional bonus rounds or bonus payments. This is because bonuses are subtracted

---

from player revenue and considered in the regret calculation, irrespective of their nature. Therefore, replacing the additional rounds in [ with payments will not lead to an improvement in regret. However, in this paper, actual payments are chosen to keep the intuition more direct and facilitate the presentation.
7 Conclusion
We addressed the challenge of strategic multi-armed bandit problems under debt-free reporting. Arms aim to maximize their own utilities by manipulating the reported values to the player, resulting in more complex problem compared to the standard setting due to the game-like dynamics involved. We proved that by employing strategic variant of successive elimination algorithm, it is possible to design a bonus-based incentive structure, resulting in dominant-strategy SPE for arms where they report truthfully. The dynamics of the successive elimination process, particularly the trade-off between high savings and swift elimination, allow for the implementation of cost-effective bonuses, leading to low regret.
References
[1] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. [
[2] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-255 256,65666660 05 2002.
[3] Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[4] William Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4):285-294 12 1933. T
[5] Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On multi-armed bandit designs for dose-finding trials. Journal of Machine Leurning Research, 1 2021. T
[6] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandi approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, WWW '10, page 661-670, New York, NY, USA, 2010. Association for Computing Machinery. I
[7] Jinhang Zuo and Carlee Joe-Wong. Combinatorial multi-armed bandits for resource allocation. 2021 55th Annual Conference Information Sciences and Systems (CISS), pages 1-4, 2021.
[8] Mark Braverman, Jieming Mao, Jon Schneider, and S. Matthew Weinberg. Multi-armed bandit problems with strategic arms. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Secon Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 383-416. PMLR. 25-28 Jun 2019. 5
10
[9] Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Repeated bilateral trade against smoothed adversary. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 1095-1130. PMLR, 12-15 55 Jul 2023.
[10] Martino Bernasconi, Mattco Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance, 2024, 2
[11] Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui, and Vianney Perchet. Learning in repeated auctions. Foundations and Trends@ in Machine Learning, 15(3):176-334, 2022.
[12] Sylvain Chassang. Calibrated incentive contracts. Econometrica, 81(5):1935-1971 September
2013. g
[13] Jean-Jacques Laffont and David Martimort. The theory incentives: The principal-agent
model. pages i-vi, 2002. B
10

---

[14] Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins. Characterizing truthful multi- armed bandit mechanisms: Extended abstract. EC '09, page 79-88, New York, NY, USA, 2009. Association for Computing Machinery.
[15] Nikhil R. Devanur and Sham M. Kakade. The price of truthfulness for pay-per-click auctions. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC '09, page 99-106, New York, NY, USA, 2009. Association for Computing Machinery.
[16] Moshe Babaioff, Robert D. Kleinberg, and Aleksandrs Slivkins. Truthful mechanisms with implicit payment computation. In Proceedings of the 11th ACM Conference on Electronic Commerce, BC 10, page 43-52, New York, NY, USA, 2010. Association for Computing Machinery.
[17] Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. In H. Wallach, Larochelle, A. Beygelzimer, F. d' Buc, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. 3
[18] Guoju Gao, He Huang, Mingjun Xiao, Jie Wu, Yu-E Sun, and Sheng Zhang. Auction-based combinatorial multi-armed bandit mechanisms with strategic arms. In IEEE INFOCOM 2021
IEEE Conference on Computer Communications, pages 1-10, 2021. 3
[19] Thomas Kleine Buening, Aadirupa Saha, Christos Dimitrakakis, and Haifeng Xu. Bandits meet mechanism design combat clickbait in online recommendation, 2023. 3
[20] Ahmed Ben Yahmed, Clément Calauzènes, and Vianney Perchet. Strategic arms with side com- munication prevail over low-regret mab algorithms. In /CASSP 2024 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7435-7439, 2024.
[21] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Learning prices for repeated auctions with strategic buyers. Advances in Neural Information Processing Systems, 11 2013. 3
[22] Zhe Feng, David Parkes, and Haifeng Xu. The intrinsic robustness of stochastic bandits to strategic manipulation. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3092-3101. PMLR, 13-18 Jul 2020.
[23] Seyed A. Esmaeili, Suho Shin, and Aleksandrs Slivkins. Robust and performance incentivizing algorithms for multi-armed bandits with strategic agents, 2023.
[24] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 1039) 1105, 2006. 4
[25] Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61:55-65, 09 2010.
[26] Rémy Degenne and Vianney Perchet. Anytime optimal algorithms in stochastic multi-armed bandits. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1587-1595, New York, New York, USA, 20-22 Jun 2016. PMLR. 4
[27] Elchanan Ben- cen-porath. The complexity of computing a best response automaton in repeated games with mixed strategies. Games and Economic Behavior, 2 1990. g
[28] Vincent Conitzer and Tuomas Sandholm. Complexity results about nash equilibria. cs/0205074, cs.GT70205074, 05 2002. 8
[29] Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins. Characterizing truthful multi- armed bandit mechanisms: extended abstract. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC '09, page 79 99- New York, NY, USA, 2009. Association for
Computing Machinery. 9
11

---

During the first phase, the Algorithm 2 plays arms and then eliminates those that are performing poorly, leveraging the corresponding confidence bound a.... Consequently, the number of active arms the set A, progressively reduces over time until only the gest-performing arm remains and is then A Useful Inequalities
Theorem A.1 (Hoeffding's Inequality). Let Xi...., Xn be a collection of i..d. sampled values from a distribution with expected value μ.. Define a - X₁. Then, for any > 0, we have:
IP ( pl 2 e) S 2exp (-2ne²)
(16)
Fact A.1. For sufficiently large T, the following inequality holds:
2 (T)
[ /
(17)
Fact A.2.
3M A
162 (T) (Ap)²
162 log (T) max 3.M,
V16log(T) max
(18)
A
B Background on Non-Strategic Successive Elimination Algorithm
In the non-strategic case, we assume directly that arms are truthful, i.c., Th,t = The for all & e {I...., }} and t [T'] and are independent and identically distributed (ii.d). The classic successive elimination algorithm as follows:
Algorithm 2: Successive Elimination
Let A₁ .l,..., K} the of all arms and t=1 2 while & < T and [Ad] > do
Play to (k E A+ argmin nu(t - 1)}
Hound-robing instance
kEAL
Update (t) and juke if (t) (t), Ak, K E A, then
Ar+1 A, \ {k E A, Po.(1). - -a,(1), 2 una + an,
Dr Drop bad arme
else
Ar+1 AA end
10
[=t+1
11 end
Continue to play the remaining best arm k*
played until the end of the game. Let n (T) be the number of rounds each arm l is played before being eliminated, and let r be the total length of the first phase.
Theorem B.I. Suppose that AIR 0, for k 2....,k K. Then under successive elimination algorithm (Algorithm P
with probability at least
7
332 log(T) (T)
(T( St
(19)
A
4K with probability least
72
32 log
32 log(T))
T 4 Σ
+
(20)
A
A
k=3
12

---

Proof of Theorem.B. For a given time instance and arm io E A,, leveraging the Hoeffding's inequality, we can assert the following inequality:
2 74
VI, P(LĀ, pal o
(21)
Employing the union bound, deduce that with probability of at least 1 - fio for any time t and arm k the following condition holds:
pkl S
(22)
Consequently, with a probability exceeding
2K
the elimination of the best arm is avoided. TT.
Consider any arm & such that μ S Ml, i.e., arms that are worse than the best arm. We focus on the last round when we did not deactivate & yet. This happens when the first time Tæ. the confidence intervals and the best arm do not overlap, i.e the first time when event F is valid. suboptimal arm k; is played at time t if its upper confidence bound exceeds the lower confidence bound of arm 1, indicating that:
PR.t + Obkt > Ai1 - a1.t
(23)
Using
we get:
11, 2 MI - 01 and Mnn S uc + Orl,
(24)
Hence with probability at least
72.
Pk + +2RR
2 11 201
(25)
200.1 + 201
2 l4 PR
(26)
W
4amr,t
2 μI PIR
(ne(1) ni (1)
(27)
32 log(T))
4
2 n& (T)
(28)
(M1 px)
Implying that with probability at least a/. m2 (T) S ty such that:
32 32log(T) (T)
32 log(T)
(29)
(N1 )1:)2
So in this case,with a probability of at least
4K 7
I t1 such that:
K
4
1x + 212
(30)
k=
C Proof of Theorem 4.1
Theorem 4.1 PicentiveCooppttbliiy
Under Algorithm [ Nand using the bonus function in Defini-
tion 3.7 for any arm k2 any strategy T. any strategy profile of other arms π -Kk at any time t, and given any history hg,t-1, i, the truthful reporting strategy Ti satisfies:
Uy R, [t]t Th U4 (TT π = Thapa-1]
(11)
Proof. Let's give h E [K], T E P and - E PK-1, The subgame utility of arm k when the player is using Algorithm and given any history hp.t-1 is
Uk (T, TT) x)]l hp.-1]
Σ (rk.s E(r..
2k.o) 1| + VA x-))
(31)
where the history / explicitly appears V ( x -b). ). For ease presentation, for 2 f, we detine the windowed savings average St:L (.) E. (Tk.s zk,z) [| which represents the contribution of the time window [t, l') to the complete average of savings by arm k.
The idea is to analyze both optimal and suboptimal arms.
13

---

Case 1 Et ST, s.t. Pu.s + 0 <
Po(()) (1)
Let 7h be the last node round of the extensive game where arm k is played.
In such case, 7k S 7 and
T
Ue (Ty क =x][: T
Σ
(rk,s xk.s) [R.==k]] (3
(32)
amt-1
7k
(rkis IR.o) [|k.=k] + (=(2
(33)
nu (Tx)5 + (x(
(def. of 5/-1
(34)
16log(T)
(Tx))))
+ 1h
(def. of v/a))
-10) P
(35)
2 (Tg gumh
16 lo)
5k
+ (1) P
Tk,
(def. of oxk7z) )
(36)
Considering that the final reported value at Tu is fully reimbursed to the arm as a bonus, it is dominant
to have Tk.Tk = Th,rg implying that 5% < 5t -1 The utility is upper-bounded as follows:
Us Me(TT n. x) T Tha S 2lgg(T) Str +
16 (ol))(T)
Sk
+ Tk,T
(37)
Pa (1)-e-1 jAK,TA-1
Then, by definition of Tk. the following inequalities holds.
Po,y 1(1),Tm-1
PR.TA-1
nu (T(TT)
S OkkTT--
O.k,Tu
(38)
2
nx 1)
(Tk)T)
(39)
[T(Tk) -1
S 0k.7
(40)
aftr 2lgg(T)
By rearranging terms, we obtain:
(Tx))) 2 2og((T) (T)
8log(T)
(41)
(1))-1(1),7011 1u
Hence:
8 8log(T)
16 16log(T)
Ue(T,, mx))(t Thh,,-ils
+ 1
St
stite-1 +
+ rk
(Po. 100)7a P
(on.-1(1),Tu--
P
(42)
16 log
16 (T)
24:Tk -1 k
Th.TK
(43)
(No.g 1(1),r=-1 1U
12
Mon 111.72-
PUR.T-11
16 lolog(T)
16log (T)
Sk
+ Tkink
(Por (())--1)))
Pukm +
Gl:TT
+ 5
gl:t
132
- - Pk + S
Gt:Te -1
+ 5
51:t-1
(44)
max {(c) ((0) eER,
(45)
Uz (T, π = T [
(46)
14

---

This concludes the first case.
Case 2 2- S T, s.t. Pk.r - ok,r > (2)( + (2) such a case, 7 = + T', where is the length of the first period, and r' is the length of the second one.
(TT. π 1
(rea TE,I) [[c= + Ve (2
(Step 17 of Algorithm
(47)
=n((T)Sk
(def. of Sk
(48)
=nu(T)sk (na(T((i Po,- 1(2)) Ik.s) ((-=-Tr)
(def. of wx
(49)
=m(()) (TT - -S,"" S1.T - + Ih.s) Pp---rr
(50)
(51)
If > т. meaning that is in the second phase: Us<TT, [ nx (T) (T) - -1T (00--((207-1)) + Ikr)) (
[(r'=T-r)
(52)
(T) + (nxx (T) - 31:-11 5t - (2) + Ik,y) [[-=-T-]]
(53)
(54)
Then, obtain three cases that depend on $
If ST = O:
Thh.,-1h : with (T) = (TT)
Uc(T: (x)
n& (T) - Sk 51:-1 Mo 1(9)7-1) + Ik,
(55)
If St * 0 but still not significant to be detected, i.e i' = - T:
Ux ( π x T = (T)sk + nu (T) - 5 51:1-1 5t. - 12)
+ TKKT
(56)
S (nx(() (T) - 5 31a-1 na. (2) + Ik.r
(57)
< U4 (T π -x T[huh,-)
(58)
If S%.T # in significant way such that the arm is detected as untruthful, stopped from being played, and prevented from receiving the bonus. In this case at most 7' 2
Un (TT, π 1)] he 1] = (T)
(59)
2 log( (T)
< Un U1 x)) : T(p
because in this case nu (T) = 0
o(
A
(60)
Hence, it is dominant to report truthfully:
24x (Tx, -x](( The & (t n -x)(t Thb
(61)
If S r. meaning that is in the first phase:
(4(T,, म +)]l: T (2)) + (na(T))(u,TT 21:T Ho, 12)) ok.) 1
(62)
= (T) + ST+1TT + (T)( - -
814-1- 5t0 - 51+1T io, (()))-1)))) + tk,77 1 [
(63)
Using results from the previous part:
Ua( π =n](t 2 S nu (T) SE- + nu (T) -5000-5--10 314-1 5t:r - noo 1(4))--1) 1) + &h.r
(64)
< nu (T) - St slit-1 Par ( 1(2),--1) + Th.
(65)
Us (TÍ [t] lt: T1h This concludes second case.
(66)
15

---

Case 3- vt < T. Pk,t + ax,t (1) (1),)) and ju.t ards S (2) + (2), In such case, т, which represents the length of the first phase, equal T. meaning that there is no exploitation phase. The utility is:
U -x)( Thxx1-11 Th (T)S + (x(
(67)
2 (x(STSk (TE(T) - Mor, (10,-11) + FR.T) (05
(68)
16log(T)
+ FkiTT 107 (17221)22
(69)
Mor 11)
PATT-1 + +nn Por 1(2),T-1) TT,T) 10 (x)=]
(T)(k) SU:T
(As in case 2)
(70)
16
+ (T(Ss) St.
+ TR,T (M)2]
(As in case 1)
(71)
Por- P1,T-1
Hence, we retrieve the two previous cases, and we can conclude that:
U4 (T π =x]+: hh, S Uu (T - : Tha
(72)
D Proof of Theorem 4.2
Theorem 4.2 (Regret Bound). Let T 2 The regret of Algorithm 7 upper-bounded as:
K
log(T)
K
log(T)
R S
(12)
Dik
A2x
k=3
The instance-independee regret upper-bound is given by:
Rr S O log())
(13)
Proof. Theorem 4.1 demonstrates the incentivized truthfulness of the arms. Consequently, calculate the regret while operating under the assumption that arms adhere to truthfulness, accurately reporting their real values. As previously discussed, the regret calculated in relation to /22. Notably, a subtlety arises in the strategic scenario as compared to the non-strategic one: we must factor in the bonuses paid when calculating the regret. We commence analysis by closely examining the Bonus function, denoted as MR:
V VK x- = (M (TT) - Porg (2) + IReTe) (1o-(1)=xi((p4
16log(T)
+ akat 110
(73)
( PRR.T-11
If o. = then (= S no (T) (ĀR.T - (2) Tkm and given that regret computed with respect to the second-highen mean then this bonus contributes to the regret only with rkm < 1.
If o. (k) 2 2, then:
(b)
16 logog(7)
WelIs.
+ Mk S 22m - (10)-=11 -10))
Puk. 1) +1
Bor 101) P
(74)
Interestingly, the term (b) of the upper-bound directly linked to the regret associated with selecting this arm during the initial phase. Equivalently, we can substitute (b) contribution by considering that this arm contributes with an additional regret, on average per round, 2A1k throughout the first phase.
16

---

Then the regret is as follows:
Exploration regrei denated as R.y
Exploitation regrel demoted as R.J.
regret denoted R.j-
(T)
RT S
Amp (T)
+B [(T (12 (o),))))) +
2014 E [nx (T) + K
(75)
Yet, we will evaluate each term of the regret separately: Exploration regret R7:
K
R7.-
(nx)
(76)
3=3
(2nteP(mx((T) S (b) + (2TP((m((T 2 (2)
(77)
K
32 (og(
22k
+ 112 T
(Theorem B.1
(78)
32 log (T)
o()
(79)
2k
3=3
The final inequality is a result of A2k I Aik- Exploitation regret R3:
Using Fact A.1
2 (T)
E
S v (/llg(())BlT)
(80)
S (T) [VTP((T + 2 4))
(81)
S (8log(T)itt +(1)
(82)
S Volog(T),
2
Σ
la o(1)
(83)
32 loloo((1 (T)²
S
16
+ o())
(84)
A R
V2 logg( (T)
$ 16
+ +0
(85)
A1k
On the other hand:
E (T (12 (2))))
< E μM2 (2),7
(86)
< E I22 No. T 5 (1] TT (11) + P2TP(T 2 41)
(87)
< [u2 - (2). S [1] T + o
(88)
However, we have:
112
E [2o.(2) S (1] P(r s 4) + E (2) 2 (1] P(r 2 4))
(89)
E [ 54]
#2
E No. (2), |T 2 t2 P(r 2 t2) P(r 2t)
(90)
2K
112
T2
991)
2K
+ TE U22 (T Stil
<
T o
(92)
17

---

Hence:
(T) o11)
R3 S 16 Σ
(93)
Bonus regret R7:
IB nn (T)) + K
(94)
K
241 tta) + 2TP(M)(T) 2 tk) K
(95)
k=
32 (og(
+ 27 4
2A1R
+ K
(Theorem B.1
(96)
A
T2)
k=
64 log (T)
K o(1)
(97)
Aik
By considering (79). 93 and (97) then with high probability exceeding 1 (#). the total regret is bounded by:
K log
(T)
log(T)
RT S 5
(98)
2k
A
Further analysis can be conducted to eliminate the gaps in the aforementioned regret. To address the variable Aij, let us select fixed e > and proceed as follows:
Arms k where Aij S contribute a maximum of per round, yielding a cumulative contribution of eT'.
Arms à where A;j 2 contribute at most O (l08(7)
By combining these points, the following be established:
log(T)
log(T)
K (ogg(T)
Klug(T)
0
+ t
Ol OLVKT KT (T)
(99)
Azk
AIk
c
2=2
Consequently:
Rr s O KT
(VKTTlogT
(100)
This analysis serves to bridge the gaps in the regret computation, leading to a more refined under- standing of the upper bound on the regret.
D.1 Proof of Corollary
Corollary 4.1 (Utilities Upper Bound). Under the truthful SPE, the utility of any arm is upper bounded as follows:
log(T)
Wk E (2....,K) K} E & 0
and ERG = OTTA12)
(14)
Aik
18

---

be threshold on Proof. For the suboptimal arms: & E f2..... ........K J. using 74 we have:
E [Va] - 24 14 (T) +
(101)
s PP (T)
1x) 2TP (x( (x) +1
(102)
32 (Tg
4
2
+ 2T
+1
(Theorem B.1
(103)
7
0 log(T)
(104)
A1k
For the optimal arm k = 1, the result directly follows from the definition of the corresponding bonus.
E Proof of Theorem 5.1
E.1 Number of Pulls under Strategies with Upper-Bounded Savings
Lemma E.1. For any strategy with bounded savings by M, the expected number of times that suboptimal arm is pulled to time T can be bounded as follow:
6M A
162 log (T)
2
B(mx S max
(105)
(A
72
Proof. For simplicity, we omit the dependency on the strategy profile π in our notation, since is clear that we focus on an arbitrary profile æ. Let (T) max the number of pulls of suboptimal arm k.
6M
162 log(T)
ag (Ag
T
(T)
<
(106)
T
< E
+
Σ
10==km
(107)
((T)
kr 1) Gx
(108)
Next, we bound the probability P n 1) 2 (T) using union bound. We denote by k* the best arm under policy π. We recall that the elimination test is conducted after arms have been played the same number of times. This means that if we assess whether arm & is played at time t,
19

---

then we have axt,1-1 = 0
hi k (n - (a(T)) =P 0
2 (a(T))
(109)
P P( + 2 na 2 (c(T))
(110)
P(ANA-1- - nelt -) + -1 2 1-- (t - 1)
5k
5/
0i 1) 21)
(111)
<
Σ
P P
$4 Sk
+ 20 2 P6 0 1) === =1)
(112)
nx(1 - 1)
(=()(())
Σ (x()(T
P P +
M
20 2 =1)
(113)
(t - 1)
A
P P
+
2
p 11=
(114)
(T(
A
A
6 f a | 1) =1)
(115)
6
(T)
Pl ( pa + par-
p + 1x(l - 1)
M
A4 2
-2A7
+ ak 1 1) 1)
6
(116)
P 1 pi lkk. x-1 Ag
3Ar
+ 0 (mx(t - 1) =1)
(117)
(T)
Σ (T)
P P ur 2
A 2
hu(t 16)
1) =1) +P |M p 2 aan--1/natt 1) = 1)] (118)
1
(119)
T"
'20
(T)
2
(120)
7
(TCx(T)
Where (a), (b), and (d) respectively depend on 1 2 (T) 2
3M 1 2 (x( 2
162 log T
and the
A
Hoeffding's ss inequality. (c) because that -kk- + pb: S - + ( Hence:
M
2 T
3M 162 log (T)) )
2
E [ma S (x( +
<
max
(AT) 0 J +
T
(121)
E.2 Proof of Theorem 5.1
Theorem 5.1. For any arbitrary strategy profile æ with M -bounded savings, the regret of Algorithm 7 is bounded by:
R7 = E
Mo (2) (2) The.s)
+
V (,( xx)
0
max
log (T) M,
Σ
max M,
log(T)) A r
(15)
Ag
kio Je (R)22
k:o Jan (K)23
Proof. Fix an arbitrary strategy profile म. For each arm k define S - - DT= (Tk,, - x))
[k), representing the cumulative savings of arm k up to round T. We assume that for all arms k E [K] and for any strategy π, the cumulative savings satisfy ST < M. We define the effective
20

---

mean under strategy as pi and let μz (1g [ee[K]- Therefore, we define AT as the difference between the highest effective mean under strategy л and the effective mean of arm k. given by:
A -o M. Similarly, A represents the difference between the second-highest effective
mean and the effective mean of arm under strategy π, defined as: A - (2) Pk The regret of Algorithm
| with respect to the second highest effective mean can be upper bounded as in 75
R
Σ
Σ
2 (Ta (T)]
k:o an (4)23
R:o "" (8)22
2 log(())
+ E (T
Th o ()
-0 (2))
+E
K
(122)
Hence is crucial to upper bound M(nx(T))
By applying Lemma E.1 multiple times, we bound each component of the regret. First step:
Σ
AT)
E
2 (T)
(123)
koo (k)23
k:o (A)22
Σ
AT max
3M
162 log (T)
E
2 max
3M
162 log (T)
6K
A
(Ag)²
A
(Ag)²
T
k:o (1)23
Noo (A)22
(124)
162 log (T)
162 162log (T)
Σ
max 3M,
Σ
2max 3M,
+ o(1)
(125)
A
A A
k:o (K)23
(1)23
k:o H (k)22
Second step:
log((T)
E
(8log(T)E((F)
(126)
s (88og(())
E [T]
(concavity of square root function)
(127)
< /8log(T))
2
E [mx(T))
(128)
kio um (k)22
3M
162 log (T)
2
$ /8logg(T)
2
Σ
max
AT
(AT)²
T
(129)
k:o # (k)22
3M
162 log (T)
4K
S (8llgTT)
2
max
A (AT)²
+
T2
(130)
kio 1 (k)22
3M
162 lo2 (T)
/ 16
max
(Ag)²
+ o(1)
(131)
lio a (6)22
Fac
162 log (T)
max
3M,
+ o(1)
(132)
A m
l:o 4 (1)22
(133)
Third step:
E (T () (2 (2)
10 (2)) o(1)
(similar arguments
86 92
(134)
21

---

Combining the three steps gives:
log(T) D
log(T) D
}
RJ S O
E
max
M,
E
max
M,
(135)
A: (M)22
k:o pa (8)23
F Empirical Analysis
We conducted experiment with six arms, where the rewards followed the order (W1 A42 M4 14 > SAs > pe). The experiment spanned a horizon of 10 time steps and was averaged over 100 epochs. The game's dynamics inherently complex, arm strategies are typically intractable in practical scenarios. To gather empirical evidence, we fixed certain strategies and monitored the player's regret while using Algorithm
[
Our study examined three specific scenarios:
Untruthful Arbitrary Reporting: At each round, the selected arm randomly reports 100%, 60%, 40%, 10%, or 0% of its observed reward.
2. Truthful Reporting: This corresponds to the Dominant SPE.
3. "Optimal" Reporting: Here we use the term "optimal" somewhat loosely. In this scenario, only the two best arms report truthfully, while the remaining suboptimal arms report O.
1753
mobriin
Cam 7agee
0083
733
2000
1880
1000
Figure 1: Cumulative regret under different strategies: 1. Under untruthful arbitrary reporting, where arbitrarily choose keep portion of their reward. Under truthful reporting, where arms adhere dominant truthful SPE. 3. Under "optimal" reporting, where only the two hest arms report truthfully and the remaining suboptimal arms withhold the entirety of their observed reward.
2000
Trutnfus Reporting
Reporting
1750
1250
Utility
1000
250
Arms
Figure 2: Comparison of arms' utilities between truthful reporting and arbitrary untruthful strategics
In Figure D we present the cumulative regret of the player for each strategy, where the final point of each curve represents the bonus paid to the arms at the end of the game. The results are averaged over
22

---

multiple epochs, As expected, the worst regret is observed in the first scenario, where arms withhold an arbitrary portion of the observed reward. For the two remaining scenarios, both exhibit logarithmic cumulative regret, with the "optimal" reporting scenario demonstrating a better factor. This is because the algorithm eliminates suboptimal arms more quickly and transitions faster to the second phase where it achieves better performance. While "optimal" reporting is challenging to achieve, S-SE effectively incentivizes arms to report truthfully, creating a dominant SPE and guaranteeing the player logarithmic regret.
Within the same experiment, calculated the total gains for each arm under two scenarios: truthful reporting (i.e., the dominant Subgame Perfect Equilibrium, SPE) and arbitrary untruthful reporting, where arms misreport portion of the observed rewards. As shown in Figure we observed that under truthful reporting, the arms' utilities were higher compared to those under untruthful reporting, consistent with the theoretical predictions.
23

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The assertions presented in the abstract and introduction align with the theoret- ical findings expounded in the core of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not 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 include aspirational goals as motivation as long 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]
The discussion and future work section poses limitations in the form of questions, thus expanding the scope for future research endeavors.
Justification:
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 separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are 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 on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is 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 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 fairesss.
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

---

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 paper meticulously details the complete set of assumptions underlying each theoretical result, with all comprehensive and correct proofs provided 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: [NA]
Justification:
The paper does not include any experimental results.
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 on 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.
25

---

(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 describe 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: [NA]
Justification:
The paper does not include any experimental results.
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/ www.gdee/ooeeuusiieeeeeeeeeeeeee
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)
/ htappp..c//pllllcc/giiee////dddd htw.:iddeee/ooeeuuinsssiiiooooo
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
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?
Question:
Answer: [NA]
Justification:
The paper does not include any experimental results.
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.
26

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include any experimental results.
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 to 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:
The paper does not include any experimental results.
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 https http::/:////uuru.s..cooooo http://wwwrp.c.ppp...///ccccttta
27

---

Answer: [Yes]
Justification:
The NeurlPS Code of Ethics is reviewed and adhered to with respect.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The work performed does not have a societal impact.
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 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 to particular applications, let alone deployments. However, if there is 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 disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to 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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to 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: The paper does not pose any risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
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
28

---

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 challenging, and many papers do not 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 (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not utilize existing assets.
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 is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com ddtasets 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 it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset'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:
The paper does not introduce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of 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 was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects

---

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: The paper does not involve crowdsourcing or research with human subjects.
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
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?
Question:
Answer[[NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
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.
30


Reviews:
[{"review_id": "hEPzmp08qy", "reviewer": "Reviewer_byTp", "summary": "This paper studies a multi-armed bandit setting with stochastic arms but where the arms are strategic agents -- when an arm is pulled it can choose what fraction of the reward to keep for itself and what fraction of the reward to pass on to the principal (the learning algorithm picking the arms). The principal can only see the reward they receive (not the amount received by the agent), and all parties want to maximize their total reward.\n\nThis setting was originally studied by Braverman et al., who showed that if the principal runs a standard no-regret learning algorithm then there are subgame perfect “colluding” equilibria where the principal receives nothing -- on the other hand, the principal can always asymptotically achieve the second highest average payoff by essentially running a second-price auction at the beginning of the game and only pulling the winner.\n\nThis strategy proposed by Braverman et al. has two issues. One is that (naively implemented) it may require agents (the arms) to report a higher value in some early rounds than the value they actually achieve. Even if you fix this issue (by converting this idea into an explore-then-commit style algorithm), the regret of the principal -- the gap between their expected utility and actually receiving the second-highest average per round -- will be a suboptimal O(T^{2/3}).\n\nThis paper shows how to get O(sqrt(TlogT)) instance-independent and O((log T)/Delta) instance-dependent regret bounds for this problem, on par with regret bounds achievable for standard bandit problems. The main idea is to adapt the Successive Elimination bandit algorithm (and its analysis) to this strategic setting. At a high level, the algorithm runs SE until there is only arm left, and then requires this arm to contribute (on average) at least the second-highest average reward per round. Finally, all participating agents are given a bonus designed to make bidding their true value incentive compatible.", "questions": "Is it possible to modify the S-SE algorithm to work with sublinear bonuses?\n\nDo the regret lower bounds from standard bandits carry over? (I.e., are the regret bounds in this paper tight?).\n\nFeel free to reply to any other aspect of the review.", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Understanding how to adapt standard learning algorithms to strategic settings is an important question. This paper provides an improved solution to a natural strategic learning environment and presents (what I would guess to be) tight regret bounds for learning in this environment. Although the algorithm is an adaptation of a standard no-regret algorithm (successive elimination), analyzing its performance in this strategic environment is non-trivial (as it involves pinning down the worst possible equilibrium behavior of the individual arms). The paper was well-written and easy to read.", "weaknesses": "I think it is a little unsatisfactory that the optimal learning algorithm still takes the form “auction off the business to the best-arm for the second-best-arm’s price”, even if this auction is now done in a slightly smoother way (via successive arm elimination over several rounds, instead of a sublinear exploration period where arms simply reveal their price). I.e., both this algorithm and the previous algorithm have the property that after some stage of the game, they will only ever select one specific arm. I think it would be a more interesting result if the principal’s strategy was more time-stable and could e.g. handle arms entering or leaving the market (or adversarial rewards, although that would require more changes to the problem set-up). \n\nAnother aspect of the solution that bothers me a little bit is that the new scheme requires bonuses that grow linearly in T. This seems to require a lot of trust on behalf of the agents that they will in fact eventually get reimbursed. In contrast, the previous algorithm of Braverman et al. also implements some bonus scheme (through rewarding the agents in some extra rounds at the end of the game), but these bonuses are sublinear in the time horizon.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer byTp,\n\nWe express our sincere gratitude for your invaluable review and the time you have dedicated to it.\n\nThis paper, motivated by various real-world applications such as e-commerce and repeated trades with balanced budgets, delves into strategic arms under debt-free reporting. Our primary objective is to address an open problem in [8], which involves improving the regret under debt-free reporting, aiming to progress from $T^{2/3}$ to $\\sqrt{T \\log(T)}$. Therefore, we adopt the same setting as in [8], including a fixed number of strategic arms. On one hand, this setting inherently includes the scenario of arms exiting the market, equivalent to arms deciding to report 0 for all subsequent steps. On the other hand, accommodating arms entering the market would necessitate significant changes to the setting (compared to [8]) and would require introducing concepts of adversarial rewarding or even non-stationary systems. While we agree that this is a fascinating proposal, we demonstrate that even within the same setting as [8], there are substantial improvements (such as a more suitable incentive-compatible algorithm, better/tighter regret bounds, robustness to small deviations, etc.), which form the core of this paper. We assure you that the notion of a time-variant market will be included in the future work section, as we recognize that it will motivate further significant research.\n\nIn the strategic setting, under the most unfavorable circumstances, it is impossible to guarantee gains surpassing $\\mu_2$. This limitation arises because the optimal arm only needs to report a marginally higher value than the second-best arm to be chosen as the superior option by the player, as formally presented in Lemma 14 of [8]. Therefore, providing a bonus of $O(T \\Delta_{12})$ to the best arm to ensure truthful reporting remains optimal for the player, as it guarantees a return of $\\mu_{2}$ each time the best arm is played. Generally speaking, the harmful bonus in the strategic case is the one subtracted from $\\mu_{2}$, i.e., the ones paid to the suboptimal arms, which is sublinear in our case (on the order of $\\log(T) / \\Delta$). As a side note, even [8] rewards the best arms with $O(T \\Delta_{12})$ (refer to Mechanism 2, Line 3), which is entirely acceptable since it does not contribute to the regret.\n\nIn the paragraph \"Tightness of Regret\" (line 271 of our paper), we discussed that the upper bound on the regret is tight and that the lower bound is of the same order as the result given in (12).\n\nAdditionally, we want to highlight the contributions of our paper. There is a notable technicality worth mentioning regarding the definition and proof of our solution concept. Our setting involves an extensive game, as opposed to a simultaneous one (as in Braverman et al., 2019, where learning occurs once at the beginning). In our extensive game, the equilibrium strategy of each arm at each node must consider the updated history of the entire game up to that point. This task is generally intractable (Ben-Porath, 1990; Conitzer and Sandholm, 2002). Interestingly, we demonstrate that our mechanism ensures truthfulness as the best response to adversarial strategies independent of history. Our approach entails consistent truthful reporting, regardless of the equilibrium path. Notably, this remains an equilibrium irrespective of past events, resembling sub-game perfect equilibrium. While the adaptivity of our algorithm introduces a more complicated solution concept for the analysis, it is crucial for the improvement in regret that we present. This adaptivity necessitates well-tailored and less harmful incentivizing bonuses, which are key to better regret. The paper also includes an additional bound which nicely characterizes the regret under deviations  giving an idea about the robustness of the algorithm.\n\nWe appreciate your feedback and assure you that this discussion will be incorporated into the final version of our work. We hope this addresses your concerns and contributes positively to your evaluation, leading to a better score.", "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": "3TdlUS6hWm", "reviewer": "Reviewer_JBtJ", "summary": "The paper addresses a strategic bandit setting. Specifically, the player (algorithm) can select between K arms as in standard bandits but each arm can choose the reward it reports instead. Because of the debt-free assumptions, the reported value cannot exceed the realized reward. The papers gives an algorithm that rewards the arms based on the values they report.  The regret is defined with respect to the second highest mean + the total payment given to the arms. The given algorithm can achieve logarithmic regret which is an improvement over the regret of [8].", "questions": "Please adress the above points under weaknesses.", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-The paper essentially resolves an open problem of [8] where the arms are only debt-free. \n\n-The paper also includes an additional bound which nicely characterizes the regret under deviations.", "weaknesses": "-The motivation of the paper does not feel strong. Specifically, the paper answers a small question from reference [8].\n\n-While [8] rewards using rounds, here the reward is through payment which gives higher flexibility. Can the algorithm be generalized to allow payments through rounds instead (assuming a fixed horizon T)? \n\n\n-If the player knows the minimum gap $\\Delta$ can an explore then commit based algorithm similar to [8] be used to achieve log T regret?\n\nBelow are Minor representation issues: \n\n\n-typo: t → $t$ in line 17\n\n\n\n\n\n\n-Bullet 2 in the contribution: the regret having $\\Delta_{2k}$ suggests that we should instead have $\\mu_2 > \\mu_3 $, i.e. strict inequality.\n\n\n\n-There is a latex problem  for algorithm 1 block, it refers to the model on page 2 instead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JBtJ,\n\nWe appreciate your review and the time you've dedicated to it.\n\nIn this paper, we concentrate on strategic arms under debt-free reporting, driven by various real-world applications such as interactions on e-commerce platforms and repeated trades with budget constraints [9, 10], where reported values cannot surpass observed ones. Under the unconstrained payment setting, where arms can report any value, [8] presented an optimal mechanism with constant regret. However, when this assumption is relaxed to restricted payments (i.e., debt-free reporting), [8] proposes a mechanism that suffers from a regret of $T^{2/3}$. Hence, moving from unrestricted payment to debt-free reporting increases the regret from a constant value to $T^{2/3}$. This observation motivated us to focus on this setting.\n\nWhile [8] employs additional rounds at the end of the game as incentives, we propose using payments at the end. Both types of bonuses are allocated at the end of the game, and bonuses are subtracted from player revenue and considered in the regret calculation, regardless of their nature. By using payments as incentives, defining truthful reporting as a dominant subgame perfect equilibrium (SPE) is straightforward. However, with additional rounds, we refer to a pseudo-truthful strategy since truthfulness applies only to rounds excluding the additional bonus rounds, specifically during the initial phase when the algorithm is learning the statistics of each arm. During the additional bonus rounds, which occur at the end of the game, the player ignores the values reported by the arms, as clearly stated in [8]. Given that actual payment is a common practice in typical mechanism designs for procurement auctions, we chose actual payments to maintain a more direct intuition and facilitate the presentation. In fact, a modified version of our algorithm that includes playing each arm $\\frac{\\Psi_k}{\\mu_k}$ at the end effectively regains the payment through rounds. As already mentioned in Section 6, the improvement in regret does not depend on the type of incentives, whether they are additional bonus rounds or bonus payments. This is because bonuses are subtracted from player revenue and considered in the regret calculation, irrespective of their nature. Therefore, replacing the additional rounds in [8] with payments will not lead to an improvement in regret. The improvement is mainly due to the adaptivity of the algorithm, which allows for more tailored and less harmful bonuses. However, this adaptivity also necessitates a more technical solution concept due to the extensive nature of the game, as opposed to the simultaneous one used in [8].\n\nIf the player knows the minimum gap $\\Delta$, an explore-then-commit-based algorithm similar to [8] can achieve $\\log T$ regret. In fact, it suffices to explore each arm for $\\log(T)/\\Delta^2$ rounds instead of $T^{2/3}$. However, the purpose of bandit algorithms is to overcome the lack of this knowledge and effectively address cases where $\\Delta$ is unknown.\n\nWe thank you for pointing out the representation issues, and we assure you that we will adjust the final version of our work accordingly.\n\nWe hope this addresses your concerns and contributes positively to your evaluation.", "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": "c0ELJj3rLh", "reviewer": "Reviewer_3dvn", "summary": "Multi-armed bandit problems capture explore-exploit scenarios under different reward structures including stochastic and adversarial. In this paper, the authors consider bandit problems where the arms report rewards strategically. To tackle such a problem, the authors devise a successive elimination scheme, where arms are eliminated till the best arm is identified (with high probability). To encourage truthful reporting, the authors devise a bonus scheme, so that the best arm is pulled unless it dips below the second-best arm, which encourages truthful reporting. In scenarios where arms fail to report truthfully, the authors develop regret bounds detailing the performance of algorithms.", "questions": "1. Could you further detail the types of scenarios or real-world regimes where such bandits exist?", "limitations": "The future work section discusses additional questions that could be answered, though authors should more explicitly label this as a limitations section", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Problem Formulation is Interesting** - The authors investigate debt-free reporting under the scenario of a bonus structure. The problem structure/formulation is interesting as it covers incentives, in the form of bandits reporting arms strategically, and the explore-exploit dilemma found across bandit works. \n2. **Dominant Strategy is Detailed and Analyzed** - In Section 4, the authors characterize the dominant strategy for arms, under a certain type of bonus payoff, and show that this results in truthful reporting from arms. Such a characterization helps us better understand how no-regret algorithms can be derived and provides an important piece of information on these types of bandits. \n3. **Regret Bounds in both Strategic and Non-Strategic Scenarios** - The authors derive regret bounds in both strategic and non-strategic scenarios. For non-strategic scenarios, the truthfulness of the arms makes it easier to determine optimal arm pulls, while for non-truthful scenarios, they use the upper bound on savings, M, to characterize regret. It would be nice to understand how the regret bound proved in Theorem 5.1 corresponds to some type of function of T. \n4. **Bonus Structure as Payment Improves Regret Bounds** - Table 1 lists a comparison between the method proposed in their work (S-SE) and previous work (S-ETC). The two models differ in their bonuses, and they show that by modifying this, they go from a T^2/3 bound to a T^1/2 bound.", "weaknesses": "1. **Lack of Empirical Verification** - On page 8, the authors discuss the tightness of the regret bounds, and argue that while the actual regret might change, the order of the regret is roughly the same across scenarios. However, it would be interesting to understand how tight such regret bounds are across different scenarios. Under what types of scenarios are the regret bounds tight and under which are regret bounds loose? An empirical analysis, with even simulated data, would provide a nice complement to the theoretical analysis proposed in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 3dvn,\n\nThank you for your insightful feedback and for the time you dedicated to reviewing our paper.\n\nIn the current version of our paper, we did not include experimental results, which is indeed quite common in game theory, due to the fact that the dynamics of the game are intrinsically dependent on arm strategies that are generally intractable in real-world scenarios. Consequently, we provided a theoretical analysis of the dominant Subgame Perfect Equilibrium (SPE) and discussed the tightness of its regret. However, inspired by your review, we have conducted a simulated experiment where we fix the arm strategies from the beginning and track the cumulative regret. Specifically, we consider six strategic arms with $\\mu_{1} > \\mu_{2} > \\mu_{3} > \\mu_{4} > \\mu_{5} > \\mu_{6}$. The experiment is run over a horizon of 10,000 and averaged over 100 epochs. We examine three scenarios:\n\n1. **Untruthful Arbitrary Reporting**: At each round, the selected arm randomly reports 100%, 60%, 40%, 10%, or 0% of its observed reward.\n2. **Truthful Reporting**: This corresponds to the Dominant SPE.\n3. **\"Optimal\" Reporting**: Here we use the term \"optimal\" somewhat loosely. In this scenario, only the two best arms report truthfully, while the remaining suboptimal arms report 0.\n\nThe results are detailed in the attached PDF. As expected, the worst regret corresponds to the first scenario. However, for the two remaining scenarios, both exhibit logarithmic cumulative regret, with the \"optimal\" reporting scenario demonstrating a better factor since the algorithm eliminates suboptimal arms more quickly and transitions faster to the second phase where it achieves better performance. While \"optimal\" reporting is challenging to achieve, **S-SE** effectively incentivizes arms to report truthfully, creating a dominant SPE and guaranteeing the player logarithmic regret.\n\nOur model is inspired by several real-world applications and can be seen as a multi-agent extension of the principal-agent problem in contract theory. It deals with dynamic agency issues where a principal must select one of K agents to carry out tasks on their behalf, with the cost of these tasks remaining unknown to the principal (e.g., choosing among K contractors for a job). A crucial aspect is that the principal does not know in advance the exact cost or benefit of the actions performed. The concept of debt-free reporting of strategic arms is inspired by e-commerce transactions, where a platform may choose to cancel a sale but cannot create one. This generalizes to binary bandits, where it is easy to hide a success and report a fake failure but difficult to create a success. Additionally, it is motivated by repeated trades with budget constraints, where an arm cannot report more than it possesses.\n\nWe also agree with your suggestion regarding the relabeling of the limitations section and will make the necessary corrections.\n\nWe hope that we have addressed your concerns and answered your questions satisfactorily, contributing positively to your evaluation.", "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": "SM22na4x0J", "reviewer": "Reviewer_VQPm", "summary": "This paper considers a strategic variant of the multi-armed bandit problem with payments. It thereby builds upon a problem studied by Braverman et al. The paper formally introduces the problem formulation and proposes an algorithm, S-SE, that combines successive elimination with a meticulously chosen payment rule. It is shown that truthfulness is a dominant SPE under which the proposed algorithm suffers logarithmic regret. The paper also analyzes the utility of the arms under S-SE and the dominant SPE. Finally, the performance of the algorithm under arbitrary arm strategies is analyzed.", "questions": "- Line 269: You say that the best arm is incentivized with a bonus of $O(\\Delta_{12} T)$. Is this a typo? If the bonus payment would be of order $T$, then your regret bound would be of order $T$. It also doesn't seem necessary to make such a large bonus payment, since you'd only need to compensate the best arm for its truthful reporting in the first $\\tau$ rounds. \n\n\n**Minor things:**\n- Consider splitting the text in Section 2 into several paragraphs to improve readability. Also, clearly highlighting the observational model and assumptions using \\paragraph or some kind of \\emph would be helpful, in my opinion. \n- Typos: \"tof\", \"understrategy\"", "limitations": "Limitations are adequately addressed in my opinion.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The studied problem, which is at the intersection of bandit learning and mechanism design, is very interesting. \n- The paper is well-written and easy to follow. \n- It is interesting to see that the regret achieved by Braverman et al. can be improved using an extension of successive elimination + payment rule (under debt-free reporting). \n- The paper proves that truthfulness is a *dominant* SPE. \n- The provided regret bound appears to be near-optimal and the dependence on the gaps $\\Delta_{1k}$ and $\\Delta_{2k}$ is quite interesting. \n- Overall, even though many aspects of this problem have already been studied by Braverman et al., I believe that this papers makes some insightful and novel contributions.", "weaknesses": "- The paragraph **Tightness of Regret** is a very hand-wavy. In strategic settings like the one you study here, one easily mistakes an intuition about \"rational agent behavior\" for a rigorous argument. In particular, you write \n \"The optimal arm only needs to report a slightly higher value than the second-best arm to be chosen by the player as the superior option [*you here assume a class of mechanisms that do in fact choose the arm with highest reported value in some specific way*]. Consequently, **all efficient low-regret mechanisms** must ensure truthfulness, at least for the two best arms.\" \nIntuitively, yes, I agree. However, this is a claim that, I think, is very difficult to prove rigorously. I recommend to adapt the language used in this paragraph and emphasize that you're providing intuition only. \n- Similar hand-wavy language and statements are used a few times in the text (not as bad as the above one). Please make sure to be clear whether you provide intuition (which is great) or you actually proved the statement (even better). \n- A minor thing that is also about the use of slightly imprecise language and might come across as nitpicking. Lemma 14 in Braverman et al. actually shows that you cannot achieve $(\\alpha \\mu_1 + (1-\\alpha) \\mu_2)T$ utility for *constant* $\\alpha > 0$. Hence, you can achieve more than $\\mu_2 T$ revenue, e.g., let $\\alpha = 1/\\sqrt{T}$, despite you saying in line 126 that \"no mechanism can guarantee more than $\\mu_2 T$ revenue\". This is not a serious issue, since I think we can all agree that defining regret w.r.t. $\\mu_2 T$ is still the right choice in view of Lemma 14. I still wanted to make you aware of this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer VQPm,\n\nThank you very much for your detailed and insightful review. We greatly appreciate the time and effort you dedicated to it.\n\nWe are computing regret with reference to $\\mu_{2}$, which involves incentivizing the best arm with $O(T \\Delta_{12})$. This approach is not harmful, as it offsets the difference between $\\mu_{1}$ and $\\mu_{2}$ while preserving $\\mu_{2}$ for the player. Essentially, we allocate all values greater than $\\mu_{2}$ to the best arm throughout the game. Additionally, the incentive should address the second phase. If not properly incentivized during this phase, the best arm might withhold a portion of the reward (especially since the second-best mean is not communicated), leading to reported values that are less than $\\mu_{2}$ on average. This could result in linear regret, given that the second phase lasts much longer than the first. Thus, incentivizing the best arm with $O(T \\Delta_{12})$ appears necessary (as also done by Braverman et al.), which is acceptable given the definition of regret. However, improvements have been achieved through the new bonus structure assigned to suboptimal arms, which has been optimized due to the adaptiveness of the new algorithm.\n\nWe appreciate your feedback on the weaknesses in our representations, language, and typos. We will address these issues and make the necessary corrections in the final version.\n\nWe hope that we have addressed your concerns and answered your questions clearly, contributing positively to your evaluation.", "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:
Here we present the complementary experimental results to our theoretical analysis, as suggested by Reviewer 3dvn.

Meta-review: Reviewers are all positive about the paper. They mention that the paper studies an interesting and important problem and resolves an open problem of prior work Braverman et al.. Reviewers also have some comments on writing and it would be good to address them in the camera ready version.
Decision: Accept (poster)