Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting

Authors: ahmed ben yahmed
clément  calauzènes
vianney  perchet
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 10:15:04

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).

Main paper: 
 introduction: 
 The multi-armed bandit (MAB) problem serves as a fundamental modeling framework for exploring the interplay between a decision-making agent (or player) and a 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, at each time step t, the player selects one arm k t from the set {1, 2, . . . , K} and receives a reward, denoted as r kt,t . These rewards can either be generated stochastically or determined adversarially. The player's overarching objective is to strike a balance between two key aspects: exploration and exploitation. Initially, he must explore all arms adequately to gain confidence in identifying the best-performing arm. Once this is accomplished, he 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 [1, 2, 3] . This modeling framework has broad real-world applications, including domains such as clinical trials [4, 5] , recommender 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 r kt,t to the player.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: The assertions presented in the abstract and introduction align with the theoretical 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 be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
problem statement: 
 The concept of the strategic multi-armed bandit builds upon the foundation of the classic multi-armed bandit problem, introducing a novel element wherein the arms possess the capability to retain a portion of the reward for themselves. Within this framework, we contemplate a collection of K stochastic arms denoted by k ∈ {1, . . . , K}, where each arm possesses a bounded reward distribution D k supported on [0, 1]. Each arm is distinguished by its reward mean, denoted as µ k . To maintain generality without loss of clarity, we assume, for the presentation and the analysis, an ordering such that µ 1 ≥ µ 2 ≥ • • • ≥ µ K (unknown to the player). In each round t, the player selects an arm denoted as k t . This arm k t then observes a reward r kt,t ∈ [0, 1]. Subsequently, the arm reports a quantity x kt,t to the player and retains r kt,t -x kt,t as its own utility. In this scenario, it is important to note that solely arm k t possesses knowledge of the actually observed reward r kt,t , whereas the player is privy only to x kt,t and remains unaware of the withheld portion. Hence the decision of the player is based on the information gathered until time t which can formally encoded in F P,t = {k s , x ks,s } s<t implying that k t is σ (F P,t ) measurable. Conversely, the arm k t 's available information is succinctly represented by F kt,t = {k s , r ks,s , x ks,s , k t , r kt,t } s<t:ks=kt ∪ {k s } s<t and x kt,t is σ (F kt,t ) 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 kt,t , implying the following constraint 0 ≤ x kt,t ≤ r kt,t ∀t ≥ 1.In the context of strategic bandits, the player has the option to allocate a bonus Ψ k to each arm k ∈ {1, . . . , K} 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 to the arms, similar to payments in the usual mechanism design for procurement auctions [11] . In this work, the latter option has been chosen for use, i.e. a bonus payment-based algorithm. Therefore, the interaction between the player and the arms can be encapsulated in the Model 1.Player commits to an algorithm A, which is public to the arms for t = 1, . . . , T do Player selects arms k t ∈ {1, . . . , K} according to the chosen algorithm A Arm k t observes reward r kt,t ∼ D kt Arm k t reports x kt,t ∈ [0, r kt,t ] to the player end Player assigns bonuses Ψ k to each arm k ∈ {1, . . . , K}Let us denote by P, the set of all possible arm strategies, by π k = (π k,t ) t:kt=k ∈ P the strategy of arm k and by π = (π 1 , . . . , π k ) the strategy profile of the arms. Explicitly, P is the set of mappings from the past history T s=1 [0, 1] 2s × {0, 1} T to [0, 1]. Here, [0, 1] 2s denotes the accumulated observed and announced rewards, and {0, 1} T indicates the rounds during which this arm has been selected thus far. Let x k ∈ R T ⋆ (and r k ∈ R T ⋆ ) be the sequence of the reported values (and rewards, respectively) by arm k across T rounds where R ⋆ = R ∪ {⋆}, and the symbol '⋆' is used for rounds when the arm is not observed. We also refer to x k as the path of arm k under strategy π. Let x -k denote the K -1 paths of all arms except k. As a result, the utility associated with arm k is defined in an ex-post fashion as follows: (1) (1)U k (π k , π -k ) = T t=1 (r kt,t -x kt,t ) • 1 [kt=k] + Ψ k (x k , x -k )which is the cumulative savings over rounds plus the corresponding assigned bonus (we slightly abused notations here, as Ψ k only depends on the observations of the player, and not the full vector x k ). 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 a SPE if π ⋆ k is an optimal strategy for any arm k, considering any history and given any strategy π -k ∈ P K-1 adopted by other arms, at any time t.In the strategic scenario, the player, under the most unfavorable circumstances, cannot guarantee to achieve gains surpassing µ 2 . 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 µ 2 and the value reported by the selected arm k t over T rounds, along with the bonus values, is defined as follows:EQUATIONA simplified instance of the strategic bandit problem has been examined within the context of the principal-agent problem in contract theory [12, 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 to maximize its own utility and accumulate private savings. Consequently, the strategic bandit problem can be viewed as a principal-multiagents problem. Additionally, drawing inspiration from the field of online advertising, several studies have delved into dynamic mechanisms to address similar scenarios [14, 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. In this scenario, each strategic arm aims to maximize the total number of rounds it is selected rather than cumulative savings. The authors demonstrate that stochastic MAB algorithms are robust to strategic manipulation, allowing the player to achieve µ 1 T with a sublinear regret. Under their utility definition, an arm is content to report the entirety of its reward as long as it is selected, justifying their use of the best mean µ 1 as a comparator for regret.A comparable study was conducted by [23] , albeit with a variation in the arm'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) 1 [] is the indicator function:1 [a=b] = 1 if a = b 0 otherwiseinformation 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 (1) . Their work revealed that if the player aims for the highest mean µ 1 -i.e., employs a 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 not only on sequential decision-making but also on incorporating incentive mechanisms to enhance truthfulness. In this context, Lemma 14 of [8] establishes that no mechanism can guarantee more than µ 2 T as revenue for the player in the worst case. This observation justifies the use of µ 2 as a comparator in the regret definition. As a solution, they propose a 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 a revenue of µ 2 T with sub-linear cumulative regret. However, under debt-free reporting, the player incurs an additional regret of O(T3 ) within a given Nash equilibrium among the arms.The central question we address is whether there exist, under debt-free reporting, an algorithm for the player that establishes a 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, especially when striving to minimize regret. Our overarching goal is to achieve a regret of O( log(T ) ∆ ). 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 a regret guarantee better than O(T 2 3 ).Furthermore, this observation underscores that achieving incentive-compatibility cannot be solely contingent on the bonus, as it tends to become prohibitively costly for the player. To address this, we shall rely on the adaptive elimination of arms, introducing a secondary trade-off for the arms that enables a reduction in the bonus requirement. The less faithful an arm behaves, the more swiftly it 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.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 1: S-SE, which integrates mechanism design and online learning techniques. This algorithm adeptly motivates favorable arm strategies, minimizing regret by adjusting a well-calibrated bonus. This introduces a strategic tradeoff for arms, balancing high savings through dishonesty with the risk of swift elimination.2. We demonstrate that under Algorithm 1, there is a dominant-strategy SPE in our game, where each arm simply reports truthfully, as proven in Theorem 4.1. Under this equilibrium, the player provably obtain an expected revenue of µ 2 T , up to a sub-linear regret that is bounded byO K k=3 log(T ) ∆ 2k + K k=2 log(T ) ∆ 1kwhere gaps are defined as: ∆ ij = µ i -µ j , ∀i, j ∈ {1, . . . , K}. In the worst-case scenario with significantly small gaps, the regret bound is ofKT log(T ) , as outlined in Theorem 4.2. This result outperforms the regret bound of O(T 2/3 ) presented in the literature within the examined setting (see Table 1 ).3. Under additional technical assumptions, we analyze the player's regret incurred when employing Algorithm 1 within any arms strategy profile. This analysis aims to provide a comprehensive characterization of a broad range of potential equilibria. ]. We also denote by σ a a bijection from {1, . . . , K} to itself that gives the index of the k th highest element in vector a. For example, if a ⊤ = [1, 10, 4, 6] , then σ a (1) represents the index of the highest value in a, which is 2. Likewise, σ a (2) = 4, σ a (3) = 3, and σ a (4) = 1. The inverse of this mapping provides the rank associated with a given index. When the context is clear, we can simplify the notation and omit the vector a, proceeding directly with σ and its inverse σ -1 .Let S be a set; then we denote the cardinality of S by |S|.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The discussion and future work section poses limitations in the form of questions, thus expanding the scope for future research endeavors.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
algorithm presentation: 
 Algorithm 1 closely integrates a strategy that combines successive elimination and bonus allocation, hence it is referred to as Strategic Successive Elimination (S-SE). It is structured into two distinct phases:The Initial Phase. It is composed of the first τ rounds (a random stopping time defined in ( 8)), where an adaptive exploration technique is employed, based on round-robins on active arms leading to a series of successive eliminations aimed at identifying the best-performing arm. To achieve this, the player keeps track of the number of times n k (t) each arm k is pulled up to time t, defined as:EQUATIONAdditionally, the empirical average of received rewards from arm k at time t is computed as:EQUATIONThis is distinct from the empirical average of observed rewards:EQUATIONwhich is observable only by the concerned arm k. The relevant quantity to the player is μt = (μ k,t ) k∈[K] and its ordering mapping σ μt . However, to alleviate cumbersome notations, we shall use from now on σ t instead of σ μt .Leveraging a Hoeffding confidence bound and denoting α k,t = 2 log(T ) n k (t) , the algorithm effectively eliminates arms that are likely to perform worse than the best arm with high probability. Hence, an arm k is eliminated at time t if the following event is happening:EQUATIONwhich leads to define the stopping time at which arm k is eliminated, with the convention that inf ∅ = +∞,EQUATIONAlgorithm 1: Strategic Successive Elimination (S-SE)Let A 1 = {1, . . . , K} the set of all arms and t=1 while t ≤ T and|A t | > 1 do Play k ∈ {k ∈ A t : argmin k∈At n k (t -1)} Update n k (t) and μk,t if n k (t) = n k ′ (t), ∀k, k ′ ∈ A t then At+1 = At \ {k ∈ At : μσ t (1),t -α σ t (1),t ≥ μk,t + α k,t } ▷ Drop bad arms else A t+1 = A t end t=t+1 end ▷ τ is the length of the first phaseIdentify the arm with the highest average σ τ (1), denoted ask ⋆ for t = τ + 1, • • • , T do Play k ⋆ and receive the reported value x k ⋆ ,t Compute xk ⋆ ,t = 1 t-τ t s=τ +1 x k ⋆ ,s if xk ⋆ ,t < min(μ στ (2),τ , μστ (1),τ -2 log(T ) t-τ ) then Set Ψ k ⋆ = 0 ▷ IncentiveStop playing k ⋆ immediately and move to step 21▷ Incentive end end Allocate bonuses Ψ k∈{1,...,K} ▷ IncentiveConsequently, the number of active arms in the set A t progressively reduces over time until, eventually, only the best-performing arm remains. Hence, the duration of this initial phase, represented as τ , is a random stopping time. It is not fixed from the outset but dynamically adapted to the statistical characteristics of the arms, and it is defined as:τ = inf{t ∈ [T ] : |A t | = 1} = inf t ∈ [T ] : ∃S t ⊂ {1, . . . , K} s.t |S t | = K -1 and k∈St E t k (8)The Second Phase. It starts after stage τ and thus may never happen, as in classical MAB. In such case, for t > τ , the best arm, i.e. k = σ τ (1), is required to report an average value that surpasses at least the second-highest average achieved at the conclusion of the initial phase, denoted as μστ (2),τ . If the player confidently detects the best arm is defecting and fails to report as much, it 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, a bonus denoted as Ψ k is assigned to each arm k, based on μ[τ] and its rank σ -1 τ (k). 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 τ k represent the last time when arm k is active. Let τ and τ ′ respectively denote the duration of the first and second phases. Then the bonus function Ψ k is defined as following:EQUATIONHence, contingent on their ranking at the conclusion of the first phase:The highest-performing arm: if it refrains from defecting during the second phase, it will be rewarded with a 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.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 1), the algorithm introduces a 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 a more robust guarantee. In contrast to the fixed design with a 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 to the exploration phase) to ensure truthfulness, which is more costly than the bonus given in Definition 3.1.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 crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to 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. 
dominant-strategy spe: 
 Algorithm 1 combines elements of a bandit algorithm and an incentive mechanism, creating a 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 k under the truthful strategy π ⋆ k dominates its utility under any other strategy π k , given any fixed history (2) h k,t = {k z , r kz,z , x kz,z } z≤t:kz=k ∪ {k z } z≤t . Formally, we define the subgame utility of arm k under strategy profile (π k , π -k ), at time t given any history h k,t-1 as:EQUATIONwhere the history h k,t-1 is implicitly considered within Ψ k (x k , x -k ).Theorem 4.1 (Incentive-Compatibility). Under Algorithm 1 and using the bonus function in Definition 3.1, for any arm k, any strategy π k , any strategy profile of other arms π -k , at any time t, and given any history h k,t-1 , the truthful reporting strategy π ⋆ k satisfies:EQUATIONProof. See Appendix C.Therefore, truthful reporting is a 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 4.1, we compute the player's regret over T rounds. As previously discussed, the regret is calculated in relation to µ 2 . 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.Theorem 4.2 (Regret Bound). Let T ≥ 1. The regret of Algorithm 1 is upper-bounded as:EQUATIONThe instance-independent regret upper-bound is given by:EQUATIONProof. See Appendix D.(2) By definition, the history combines the information available to the arm to make a decision concerning the reporting, in addition to the reported value, i.e h k t ,t = F k t ,t ∪ {x k t ,t }. Theorem 4.2 demonstrates that the regret bound under the considered setting is significantly lower than the regret attained in the Nash equilibrium presented in [8] 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 is 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 eliminations 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 a regular MAB O . This second term comes from the additional need to correctly estimate the value of the second-best arm to make sure to "bill" accurately the best arm during the second phase. The less accurate the estimation of µ 2 , 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 µ 2 impacts the regret.It's worth noting that the truthful SPE highlighted in Theorem 4.1 might raise questions about the regret comparator µ 2 . In other words, if truthfulness exists, why can't we expect to achieve rewards of µ 1 ? 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 utility and contribute to making truthful reporting the best response that maximizes utility. Specifically, the best arm is incentivized with a bonus of O(T ∆ 12 ). Since the bonus is integral to the regret calculation, we compute the regret relative to µ 2 in a manner similar to the approach justified in Lemma 14 of [8] .Tightness of Regret. For simplicity, let's consider three arms with µ 1 ≥ µ 2 ≥ µ 3 . 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. 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 a regret of log(T ) ∆12 . Additionally, distinguishing between the second and the third arm is required to estimate the second-best mean accurately, resulting in a regret of log(T ) ∆23 . 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(T ), where ∆23 is the difference between the true mean µ 2 and an effective mean μ3 , which can be different from µ 3 . Ideally, μ3 = 0 to minimize the corresponding regret i.e incentivizing non-truthful strategies for arms k ≥ 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 in (12) . In Appendix F, we conducted an experimental analysis on 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:EQUATIONProof. See Appendix D.1.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it 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 be 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 a 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 is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to 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 to replicate the results, access to 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.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.• The full details can be provided either with the code, in appendix, or as supplemental material. 
regret analysis across arbitrary strategy profiles: 
 In the previous section, we assessed the regret of Algorithm 1 when the arms adhere to the dominant strategy SPE. General profiles and equilibria in extensive games are known to be intractable [27, 28] . 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 inequality cannot be directly applied. Consequently, determining the algorithm's output becomes non-trivial. To address this, we introduce an additional technical assumption regarding the boundedness of gains through dishonesty. Withthis 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 T k = T s=1 (r ks,s -x ks,s ) • 1 [ks=k] as the cumulative savings of arm k up to round T . We assume the existence of some upper-bound M on cumulative saving, i.e., such that for all arms k ∈ [K] and for any strategy π, it must hold that S T k ≤ M . We define the effective mean under strategy π as µ π k , and letµ π = (µ π k ) k∈[K]. Therefore, we define ∆ π k as the difference between the highest effective mean under strategy π and the effective mean of arm k, given by : ∆ π k = µ π σ µ π (1) -µ π k . Similarly, ∆ π k represents the difference between the second-highest effective mean and the effective mean of arm k under strategy π, defined as:∆ π k = µ π σ µ π (2) -µ π k .We show that when arms use the strategy profile π, even under non-i.i.d. reported variables, Algorithm 1 outputs the second highest effective mean, and the regret is provided by the following theorem.Theorem 5.1. For any arbitrary strategy profile π with M -bounded savings, the regret of Algorithm 1 is bounded by:EQUATIONProof. See Appendix E.2.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.1. In particular, it is demonstrated to be sublinear in T provided that M = o(T ). The upper bound exhibits a similar form to the problem-dependent upper bound in Theorem 4.2. Specifically, under the truthful equilibrium π ⋆ where M = 0,µ π ⋆ k = µ k , ∆ π ⋆ k = ∆ 1k , and ∆ π ⋆ k = ∆ 2k, we retrieve the result from (12) . Additionally, in the debt-free reporting setting, it is observed that for any strategy π, µ π σ µ π (2) ≤ µ 2 . This suggests that the player's revenue drops when arms diverge from the honest SPE in a way that affects the second-highest mean.Sensitivity of Algorithm 1 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 µ π 2 is of the same order as the regret. In this scenario, the player's revenue is µ 2 T , up to a sublinear regret R π T = O (R T ). Hence, even though the savings are not zero, we retrieve results comparable to those with truthful reporting. 
limitations and future work: 
 The algorithm S-SE, presented as an efficient solution to the strategic MAB, combines elements of successive elimination 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 a question is reserved for future work. However, our intuition is that this would be challenging because, in a similar setting, [29] argue that a truthful mechanism under the strategic MAB problem needs to be exploration-separated. In other words, at 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.Despite the similarity between the algorithm of [8] and our algorithm S-SE, both being strategic versions of exploration-separated algorithms, there is a major difference in the nature of the games generated by both algorithms. In [8] , all arms are played sequentially for a predetermined number of explorations each before committing to the best arm, creating a simultaneous-like game. In contrast, Algorithm 1 uses an adaptive design permitting lower regret. However, this adaptability involves an extensive game requiring a 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 [8] 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. 
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 a more complex problem compared to the standard setting due to the game-like dynamics involved. We proved that by employing a strategic variant of successive elimination algorithm, it is possible to design a bonus-based incentive structure, resulting in a 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.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, confidence intervals, or statistical significance tests, at 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 or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
 
 Appendix: Theorem A.1 (Hoeffding's Inequality). Let X 1 , . . . , X n be a collection of n i.i.d. sampled values from a distribution D with expected value µ. Define μ = 1 n n i=1 X i . Then, for any ϵ > 0, we have:EQUATION)Fact A.1. For sufficiently large T , the following inequality holds:EQUATIONFact A.2.EQUATIONIn the non-strategic case, we assume directly that arms are truthful, i.e., x k,t = r k,t for all k ∈ {1, . . . , K} and t ∈ [T ] and are independent and identically distributed (i.i.d). The classic successive elimination algorithm is as follows: During the first phase, the Algorithm 2 plays arms and then eliminates those that are performing poorly, leveraging the corresponding confidence bound α .,. . Consequently, the number of active arms in the set A t progressively reduces over time until only the best-performing arm remains and is then played until the end of the game. Let n k (T ) be the number of rounds each arm k is played before being eliminated, and let τ be the total length of the first phase.Algorithm 2: Successive Elimination Let A 1 = {1, . . . ,Theorem B.1. Suppose that ∆ 1k > 0, for k = 2, . . . , K. Then under successive elimination algorithm (Algorithm 2):• with probability at least 1 -4 T 2 :EQUATION• with probability at least 1 -4K T 2 :EQUATION)Proof of Theorem B.1. For a given time instance t and arm k ∈ A t , leveraging the Hoeffding's inequality, we can assert the following inequality:EQUATIONEmploying the union bound, we can deduce that with a probability of at least 1 -2 T 2 , for any time t and arm k, the following condition holds:EQUATIONConsequently, with a probability exceeding 1 -2K T 2 , the elimination of the best arm is avoided.Consider any arm k such that µ k ≤ µ 1 , i.e., arms that are worse than the best arm. We focus on the last round τ k when we did not deactivate k yet. This happens when the first time τ k , the confidence intervals of k and the best arm do not overlap, i.e the first time when event E t k is valid. A suboptimal arm k, is played at time t if its upper confidence bound exceeds the lower confidence bound of arm 1, indicating that:EQUATIONUsing ( 22), we get:EQUATIONHence with probability at least 1 -4 T 2 :EQUATIONEQUATIONEQUATIONImplying that with probability at least 1 -4 T 2 , n k (T ) ≤ t k such that:EQUATIONSo in this case,with a probability of at least 1 -4K T 2 , τ ≤ t 1 such that:EQUATIONC Proof of Theorem 4.1Theorem 4.1 (Incentive-Compatibility). Under Algorithm 1 and using the bonus function in Definition 3.1, for any arm k, any strategy π k , any strategy profile of other arms π -k , at any time t, and given any history h k,t-1 , the truthful reporting strategy π ⋆ k satisfies:EQUATIONProof. Let's give k ∈ [K], π k ∈ P and π -k ∈ P K-1 . The subgame utility of arm k when the player is using Algorithm 1 and given any history h k,t-1 isEQUATIONwhere the history h k,t-1 explicitly appears in Ψ k (x k , x -k ). For ease of presentation, for t ′ ≥ t, we define the windowed savings average St:t ′ k = 1 n k (T ) t ′ s=t (r k,s -x k,s ) • 1 [ks=k], which represents the contribution of the time window [t, t ′ ] to the complete average of savings by arm k.The idea is to analyze both optimal and suboptimal arms.Case 1 -∃t ≤ T, s.t. μk,t + α k,t < μσt(1),t -α σt(1),t : Let τ k be the last node or round of the extensive game where arm k is played.In such case, τ k ≤ T andU k (π k , π -k )[t : T |h k,t-1 ] = T s=t-1 (r k,s -x k,s ) • 1 [ks=k] + Ψ k (x k , x -k ) (32) = τ k s=t-1 (r k,s -x k,s ) • 1 [ks=k] + Ψ k (x k , x -k ) (33) = n k (τ k ) St:τ k k + Ψ k (x k , x -k ) (def. of St-1:τ k k ) (34) = n k (τ k ) St:τ k k + 16 log(T ) μστ k -1(1),τk -1 -μk,τ k -1 + x k,τ k (def. of Ψ k ) (35) = 2 log(T ) α 2 k,τ k St:τ k k + 16 log(T ) μστ k -1(1),τk -1 -μk,τ k -1 + x k,τ k (def. of α k,τ k )(36) Considering that the final reported value at τ k is fully reimbursed to the arm as a bonus, it is dominantto have r k,τ k = x k,τ k implying that St:τ k k ≤ St:τ k -1 k. The utility is upper-bounded as follows:EQUATIONThen, by definition of τ k , the following inequalities holds,EQUATIONEQUATIONBy rearranging terms, we obtain:EQUATIONHence:EQUATIONThis concludes the first case.Case 2 -∃τ ≤ T, s.t. μk,τ -α k,τ > μστ (2),τ + α στ (2),τ . In such a case, τ k = τ + τ ′ , where τ is the length of the first period, and τ ′ is the length of the second one.EQUATIONEQUATION)If t > τ , meaning that t is in the second phase:EQUATION) (54)Then, we obtain three cases that depend on St:TEQUATIONEQUATION• If St:T k ̸ = 0 in a 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 τ ′ = 2 log(T )EQUATIONHence, it is dominant to report truthfully:EQUATIONIf t ≤ τ , meaning that t is in the first phase:U k (π k , π -k )[t : T |h k,t-1 ] = n k (T ) St:T k + n k (T )(μ k,T -S1:T k -μσ τ -1 (2),τ -1 ) + x k,τ 1 [τ ′ =T -τ ] (62) = n k (T )( St:τ k + Sτ+1:T k ) + n k (T )(μ k,T -S1:t-1 k -St:τ k -Sτ+1:T k -μσ τ -1 (2),τ -1 ) + x k,τ 1 [τ ′ =T -τ ](63) Using results from the previous part:EQUATION≤ U k (π ⋆ k , π -k )[t : T |h k,t-1 ](66) This concludes the second case.Case 3 -∀t ≤ T, μk,t + α k,t ≥ μσt(1),t -α σt(1),t and μk,t -α k,t ≤ μσt(2),t + α σt(2),t . In such a case, τ , which represents the length of the first phase, is equal to T , meaning that there is no exploitation phase. The utility is:U k (π k , π -k )[t : T |h k,t-1 ] = n k (T ) St:T k + Ψ k (x k , x -k ) (67) ≤ n k (T ) St:T k + n k (T ) μk,T -μστ k -1 (2),T -1 + x k,T 1 [σ -1 T (k)=1](68)+ 16 log(T ) μσ T -1 (1),T -1 -μk,T -1 + x k,T 1 [σ -1 T (k)≥2] (69) ≤ n k (T ) St:T k + n k (T ) μk,T -μσ T -1 (2),T -1 + r k,T 1 [σ -1 T (k)=1](As in case 2) (70)+ n k (T ) St:T k + 16 log(T ) μσ T -1 (1),T -1 -μk,T -1 + r k,T 1 [σ -1 T (k)≥2](As in case 1) (71)Hence, we retrieve the two previous cases, and we can conclude that:EQUATIOND Proof of Theorem 4.2 Theorem 4.2 (Regret Bound). Let T ≥ 1. The regret of Algorithm 1 is upper-bounded as:EQUATIONThe instance-independent regret upper-bound is given by:EQUATIONProof. Theorem 4.1 demonstrates the incentivized truthfulness of the arms. Consequently, we calculate the regret while operating under the assumption that arms adhere to truthfulness, accurately reporting their real values. As previously discussed, the regret is calculated in relation to µ 2 . 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 our analysis by closely examining the Bonus function, denoted as Ψ k :EQUATIONEQUATION,τk -1 + r k,τ k and given that regret is computed with respect to the second-highest mean then this bonus contributes to the regret only with r k,τ k ≤ 1.EQUATIONInterestingly, the term (b) of the upper-bound is 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, 2∆ 1k throughout the first phase.Then the regret is as follows:EQUATIONYet, we will evaluate each term of the regret separately:EQUATIONEQUATIONEQUATIONEQUATIONThe final inequality is a result ofEQUATIONEQUATIONEQUATION≤ 8 log(T ) 2EQUATIONEQUATIONEQUATIONOn the other hand:EQUATIONEQUATIONEQUATION) However, we have:EQUATIONEQUATIONEQUATIONHence:EQUATIONBonus regret R 3 T :EQUATIONEQUATIONEQUATIONBy considering (79), ( 93) and (97) then with a high probability exceeding 1 -O 1 T 2 , the total regret is bounded by:EQUATIONFurther analysis can be conducted to eliminate the gaps in the aforementioned regret. To address the variable ∆ ij , let us select a fixed ϵ > 0 and proceed as follows:• Arms k where ∆ ij ≤ ϵ contribute a maximum of ϵ per round, yielding a cumulative contribution of ϵT .• Arms k where∆ ij ≥ ϵ contribute at most O log(T ) ϵ .By combining these points, the following can be established:EQUATIONConsequently:EQUATIONThis analysis serves to bridge the gaps in the regret computation, leading to a more refined understanding of the upper bound on the regret.Corollary 4.1 (Utilities Upper Bound). Under the truthful SPE, the utility of any arm is upper bounded as follows:EQUATIONProof. For the suboptimal arms: k ∈ {2, . . . , K}, using 74 we have:EQUATIONEQUATIONEQUATIONFor the optimal arm k = 1, the result directly follows from the definition of the corresponding bonus.E Proof of Theorem 5.1Lemma E.1. For any strategy π with bounded savings by M , the expected number of times that a suboptimal arm k is pulled up to time T can be bounded as follow:EQUATIONProof. For simplicity, we omit the dependency on the strategy profile π in our notation, since it is clear that we focus on an arbitrary profile π.Let ζ k (T ) = max 6M ∆ π k , 162 log(T ) (∆ π k ) 2be a threshold on the number of pulls of a suboptimal arm k.EQUATIONEQUATIONEQUATIONNext, we bound the probability P k t = k, n k (t -1) ≥ ζ k (T ) using a 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 an arm k is played at time t, then we have α k ⋆ ,t-1 = α k,t-1 .EQUATIONWhere (a), (b), and (d)respectively depend on l ≥ ζ k (T ) ≥ 3M ∆ k , l ≥ ζ k (T ) ≥ 162 log T ∆ 2 k, and the Hoeffding's inequality. (c) is because that 1) . Hence:-µ k ⋆ + µ k ≤ -∆ π k + M n k (t-EQUATIONE.2 Proof of Theorem 5.1 Theorem 5.1. For any arbitrary strategy profile π with M -bounded savings, the regret of Algorithm 1 is bounded by:EQUATIONProof. Fix an arbitrary strategy profile π. For each arm k, we define S T k = T s=1 (r ks,s -x ks,s ) • 1 [ks=k] , representing the cumulative savings of arm k up to round T . We assume that for all arms k ∈ [K] and for any strategy π, the cumulative savings satisfy S T k ≤ M . We define the effective mean under strategy π as µ π k , and let µ π = (µ π k ) k∈ [K] . Therefore, we define ∆ π k as the difference between the highest effective mean under strategy π and the effective mean of arm k, given by : ∆ π k = µ π σ µ π (1) -µ π k . Similarly, ∆ π k represents the difference between the second-highest effective mean and the effective mean of arm k under strategy π, defined as:∆ π k = µ π σ µ π (2) -µ π k .The regret of Algorithm 1 with respect to the second highest effective mean can be upper bounded as in 75:EQUATION)Hence it is crucial to upper bound E[n k (T )].By applying Lemma E.1 multiple times, we bound each component of the regret.First step:EQUATIONEQUATIONEQUATIONSecond step:EQUATION≤ 8 log(T ) E [τ ] (concavity of square root function) (127)EQUATION≤ 8 log(T ) 2EQUATION≤ 16 log(T )EQUATION(133)Third step:EQUATIONCombining the three steps gives:EQUATIONWe conducted an experiment with six arms, where the rewards followed the order (µ 1 > µ 2 > µ 3 > µ 4 > µ 5 > µ 6 ). The experiment spanned a horizon of 10 4 time steps and was averaged over 100 epochs. The game's dynamics are inherently complex, as 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 1. Our study examined three specific scenarios:1. 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 0. In Figure 1 , 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 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, we 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 a portion of the observed rewards. As shown in Figure 2 , we observed that under truthful reporting, the arms' utilities were higher compared to those under untruthful reporting, consistent with the theoretical predictions.NeurIPS Paper Checklist 


Decision: 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.

Reviews: review: paper_summary: paper_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.

This 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.

This 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}).

This 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.
strength_weakness: strength_weakness: 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). 

Another 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.
questions: questions: Is it possible to modify the S-SE algorithm to work with sublinear bonuses?

Do the regret lower bounds from standard bandits carry over? (I.e., are the regret bounds in this paper tight?).

Feel free to reply to any other aspect of the review.
limitations: limitations: Limitations are adequately addressed.
paper_summary: paper_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].
strength_weakness: strength_weakness: -The motivation of the paper does not feel strong. Specifically, the paper answers a small question from reference [8].

-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)? 


-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?

Below are Minor representation issues: 


-typo: t → $t$ in line 17






-Bullet 2 in the contribution: the regret having $\Delta_{2k}$ suggests that we should instead have $\mu_2 > \mu_3 $, i.e. strict inequality.



-There is a latex problem  for algorithm 1 block, it refers to the model on page 2 instead.
questions: questions: Please adress the above points under weaknesses.
limitations: limitations: Limitations are adequately addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: 1. Could you further detail the types of scenarios or real-world regimes where such bandits exist?
limitations: limitations: The future work section discusses additional questions that could be answered, though authors should more explicitly label this as a limitations section
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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 
 "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." 
Intuitively, 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. 
- 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). 
- 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.
questions: 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. 


**Minor things:**
- 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. 
- Typos: "tof", "understrategy"
limitations: limitations: Limitations are adequately addressed in my opinion.

Comments: title: Thank you for your new experiments
comment: Thank you very much for your valuable feedback and the insightful discussion.
Thank you for the detailed response. After reading the response and other reviews, I have decided to increase my score slightly.
Thank you very much for your valuable feedback and the insightful discussion.
Thank you very much for your valuable feedback and the insightful discussion.
Thanks for clarifying. When I wrote the questions I forgot that your benchmark is the second best arm. 

I decide to keep my original score with the primary reason being that, even though the paper makes some novel contributions, these are to some degree incremental. I'm still in favor of acceptance.
Thank you for your clarifications and the new experiments. I am satisfied with these experiments and am happy to raise my score to an 8.