acceptodds
Under review as a conference paper at ICLR 2027

Low-Regret Learning in Strategic Bandits via Incentive Design

Abstract

Online platforms often recommend products based on information reported by providers, who are self-interested and may misreport information to maximize their own profits. To help platforms make decisions, we study how the learner can minimize its regret against arms' misreporting features in strategic bandits. We propose the PALinUCB algorithm whose efficacy roots from a delicately designed contract utility. We show that, under PALinUCB, the regret is largely determined by the deviation incentive of the optimal arm. In particular, when the optimal arm behaves appropriately, the resulting joint strategy profile forms a -approximate Nash equilibrium, where each suboptimal arm is selected only times. Moreover, under Nash equilibrium, PALinUCB achieves a regret. Further, numerical results corroborate our theoretical findings and indicate that our contract design can substantially shape arms' strategic behavior for the interest of the learner, and PALinUCB remains robust under strategic reporting.

Primary area:
reinforcement learning
Keywords:
strategic linear contextual bandits, regret minimization, mechanism design.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_ASw9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies strategic linear contextual bandits in which self-interested arms can manipulate their reported features to influence the learner's decisions. The authors propose a reward-dependent contract, and develop PALinUCB, which maintains separate linear estimators for individual arms. The main theoretical contribution is a regret bound characterized by the unilateral deviation incentive of the optimal arm. Under the proposed assumptions, PALinUCB achieves polylogarithmic regret at Nash equilibrium. The paper further establishes an approximate Nash equilibrium guarantee when the optimal arm adopts a non-pessimistic reporting strategy and provides numerical experiments to support the theoretical results.

Critical strengths

1.The paper considers an interesting problem at the intersection of online learning and mechanism design. Incorporating strategic incentives into regret minimization is a meaningful direction, particularly in applications where self-interested participants can manipulate their reported information.

2.The regret bound in terms of the optimal arm's unilateral deviation incentive provides an interesting perspective on how strategic behavior affects the learner's performance. The paper establishes approximate Nash equilibrium guarantees for a class of reporting strategies and investigates cases where the proposed incentive mechanism fails to achieve sublinear regret.

Critical weaknesses

1.My main concern is that the theoretical results rely on rather strong assumptions. In particular, the existence of a uniformly optimal arm substantially simplifies the contextual bandit problem. Moreover, the analysis requires the manipulation level of each suboptimal arm to satisfy ϵi<Δi\epsilon_i<\Delta_i. This assumption becomes particularly restrictive for nearly optimal arms and may be difficult to enforce when the learner does not know the true reward parameters.

2.The claimed improvements over OptGTM and COBRA are based on substantially different assumptions. A more careful comparison of the strategy spaces and structural assumptions is needed to clarify the significance of the theoretical improvements.

3.Although the analysis contains some technically interesting arguments, the main proof techniques largely build on standard UCB concentration arguments, self-normalized inequalities, and elliptical potential bounds. The per-arm estimation structure is also closely related to existing approaches such as OptGTM. The subsequent regret–exploitability and approximate equilibrium results are derived mainly through comparisons of arm utilities and selection counts. Overall, I find the technical contributions reasonable but not particularly substantial.

Questions for authors
  1. How essential is the uniformly optimal arm assumption for achieving polylogarithmic regret, and could the analysis be extended to settings where the optimal arm varies across contexts?

2.Given that the condition ϵi<Δi\epsilon_i<\Delta_i is crucial to the main results, how can it be justified or enforced in practice when the true optimality gaps are unknown, and can the theoretical guarantees be extended to settings where this condition is relaxed?

3.Can the authors provide a more systematic comparison with OptGTM and COBRA under comparable assumptions?

4 comments

Thanks for all reviews.

W1,Q1,Q2 Uniformly Optimal Arm

Current assumptions (i.e., the existence of uniformly optimal arm) allow us to analyze how incentives drive strategic misreporting among arms, thereby bounding suboptimal pull counts and establishing regret bounds for PALinUCB. More specific comparision with those of OptGTM and COBRA are listed in Common Response 1.2 Assumptions. The possible extension is also discussed in Common Response 1.2 Assumptions. Extending our analysis to general contextual settings with context-dependent optimal arms is a natural avenue for future research. Nonetheless, this study serves as a foundational step toward that broader setting.

Q2 Justification, Enforcement, and Relaxation of the Gap Condition

Discussion about the assumption εi≤Δ‾i\varepsilon_i\leq\underline{\Delta}_i is listed in Common Response 1.2 Assumption. Actually this gap separation assumption is posted on instances and is unknown to the learner. This assumption specifies the instances and strategy classes covered by our theoretical results (Theorem 5 and 7). While existing works are also built on some constraints on εi\varepsilon_i , we think the relaxation of the assumption is also a potential avenue for future research. Our current assumptions and the corresponding analysis serve as fundenmental steps to more general settings.

W2,Q3 Comparison with OptGTM and COBRA

We provide detailed comparison with OptGTM and COBRA from perspective of mechanism design and assumptions in Common Response 1. Positioning Our Work Relative to Prior Work.

W3 Technical Contributions

Beyond the standard UCB framework,our work additionally involve contract design to shape arms' incentives of strategic reporting. The contribution is detailed in Common Response 2.3 technical contribution.

Dear Reviewer, thank you again for your helpful review—we kindly encourage you to check our rebuttal and revised manuscript above, and please let us know if anything further needs clarification.

Thank you for the response. The clarification has helped me better understand the comparison with prior work. I find the problem interesting, although I am less familiar with this particular line of literature. My main concern remains the strength of the assumptions, and I am still uncertain whether they are sufficiently well justified for the intended setting.

AuthorsOpenReview ↗

Response to Reviewer ASw9

Thank you for your response. While we agree that further relaxing these assumptions is a promising direction for future work, we note that our assumptions are comparatively mild relative to existing literature, as shown in our comparison in Common Response 1.2 and as below, providing a foundational step forward:

Comparison with OptGTM

As in the table above, when OptGTM assumes exact match of reported mean values and true mean values (see Eq. 1), our work relaxs the requirement that reported-feature predictions exactly match true mean rewards, allowing discrepancies of either sign that may vary over time (see Eq. 3).

Comparison with COBRA

As in the table above, when COBRA assumes that all arms maintain optimism over all rounds (see Eq. 2), our analysis does not assume all suboptimal arms to satisfy such optimism conditions. In our results for non-pessimistic strategies (see Eq. 4), the similar optimism condition is imposed only on the optimal arm. Theorem 5 of our work establishes the regret–exploitability relationship through a calibrated benchmark deviation of the optimal arm, without assuming all arms' joint strategy profile maintains optimism.

We hope our responses can help address your concerns, and we would be grateful if you would consider raising your overall evaluation of our work.

Reviewer_8cm4OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies strategic linear contextual bandits, in which, after observing the context, each arm may manipulate the learner's choice by reporting an untruthful feature vector. The setting is motivated by real-world applications, such as recommendation platforms, where rational arms have an incentive to misreport their descriptions. The authors propose PALinUCB, an adaptation of LinUCB in which the estimators and UCB indices are computed separately for each arm. They combine it with a contract design in which the selected arm receives rt,i−ηr_{t,i} - \eta. First, for any admissible strategy profile, they establish a regret upper bound that depends on the instance parameters and on the deviation incentive of the optimal arm, Expli∗(σ)\mathrm{Expl}_{i^{\ast}}(\sigma). Second, they show that any admissible joint strategy profile in which the optimal arm follows a non-pessimistic strategy forms a ρT\rho_T-Nash equilibrium with ρT=poly(log⁡T)\rho_T = \mathrm{poly}(\log T). Combined with the first result, this yields a corresponding regret upper bound, and poly(log⁡T)\mathrm{poly}(\log T) regret at an exact Nash equilibrium. Numerical experiments are provided to corroborate the theoretical findings.

Critical strengths

Clarity and presentation. The paper is well written and easy to follow. The setting is clearly introduced, and the results are well organized and presented in a logical order.

Motivation. The problem is well motivated, and the real-world applications behind the model, such as recommendation platforms where providers may misreport product features, are realistic and relevant.

Critical weaknesses

W1. Game-theoretic modeling and solution concept. I have concerns about the conceptual foundations of the setting and of the game.

  • Solution concept. The Nash equilibrium in Definitions 1 and 2 is defined on the total expected utilities, i.e., on the normal-form representation of the game. However, the interaction induced by the algorithm is a repeated, dynamic (extensive-form) game. In such games, a Nash equilibrium may rely on non-credible threats off the equilibrium path. It is therefore unclear whether the Nash equilibrium is the appropriate solution concept here, or whether a refinement such as a subgame perfect equilibrium (as used in [1]) would be more suitable. The authors should justify this choice.
  • Consistency of the strategy space. Section 2.2 defines a strategy as a randomized, history-dependent reporting policy. In Theorem 5, however, a strategy is written as a fixed sequence σi={xt,i}t=1T\sigma_i = \lbrace x_{t,i} \rbrace_{t=1}^{T}. Similarly, in the experiments (Appendix F), the reports are kept fixed within each epoch. These strategies are therefore not history-dependent, and the experiments do not compute an equilibrium.

Since the main results (Theorems 5 and 7) are stated in terms of these equilibrium notions, this point is central to the interpretation of the contributions.

W2. Restrictive assumptions and limited novelty.

  • Uniformly optimal arm. Assuming that a single arm is optimal under every context is very restrictive. It removes most of what makes the contextual setting interesting.
  • Admissible strategies. The class Σi(εi,θi∗)\Sigma_i(\varepsilon_i, \theta^{\ast}_i), together with the condition εi<Δ‾i\varepsilon_i \lt \underline{\Delta}_i, seems tailored to make the analysis go through. There is no indication of whether these conditions are necessary, or whether they are merely sufficient. Note that this constraint implies ⟨θi∗,xt,i⟩≤μi(ct)+εi<μi(ct)+Δ‾i≤μi∗(ct)\langle \theta^{\ast}_i, x_{t,i} \rangle \le \mu_i(c_t) + \varepsilon_i \lt \mu_i(c_t) + \underline{\Delta}_i \le \mu_{i^{\ast}}(c_t). In other words, a suboptimal arm can never appear better than the optimal arm under its own parameter, which strongly limits the scope of manipulation.
  • Role of θi∗\theta^{\ast}_i. The necessity of introducing the arm-specific parameter θi∗\theta^{\ast}_i is unclear to me. I believe the reported feature xt,ix_{t,i} alone is sufficient to describe the strategic interaction.
  • Novelty. The contribution appears too incremental compared to previous work. PALinUCB is very close to OptGTM: both rely on per-arm LinUCB estimators and a similar selection rule. Given the techniques available in the literature, and given the strength of the assumptions and of the restrictions on the strategy class, the analysis is not surprising.
  • Positioning with respect to prior work. I find the criticism of prior work in the introduction and in the related work (around l. 157) overstated. First, OptGTM is criticized for assuming that the reported features preserve the arms' true mean rewards. In the present framework, this corresponds to εi=0\varepsilon_i = 0 with θi∗=θ⋆\theta^{\ast}_i = \theta^{\star}. The relaxation εi<Δ‾i\varepsilon_i \lt \underline{\Delta}_i is itself strong: it still guarantees that no suboptimal arm can appear better than the optimal arm (see my comment on admissible strategies). Second, COBRA is criticized for assuming that the UCB index computed from each arm's reported feature is never smaller than the arm's true mean reward. This assumption is natural: it is the standard optimism property of UCB indices, and an arm that maximizes its number of pulls has no incentive to under-report. Moreover, the present paper relies on the same type of condition for the optimal arm. Under the non-pessimistic strategy class (mt,i∗≥0m_{t,i^{\ast}} \ge 0), eqs. (3)–(5) in the proof of Lemma 13 give exactly UCBt,i∗≥μi∗(ct)\mathrm{UCB}_{t,i^{\ast}} \ge \mu_{i^{\ast}}(c_t). The claimed relaxation of the assumptions of prior work should therefore be qualified.

Together, these points limit the significance of the theoretical results.

Other weaknesses.

  • Missing related work. The related-work paragraph on strategic MAB (Braverman et al., Feng et al., Esmaeili et al.) omits [1], which studies strategic arms under a reporting constraint and uses subgame-perfect equilibrium as the solution concept. It should be cited and briefly positioned, particularly since it bears on the solution-concept question raised in W1.
  • Arms' knowledge of θ⋆\theta^{\star}. The assumption that each arm knows the true parameter θ⋆\theta^{\star} appears only in Remark 6. It should be stated explicitly as part of the model in Section 2.2.
  • Notation. In Theorem 7, the non-pessimistic class is defined through Σi(εi)\Sigma_i(\varepsilon_i), which is never defined; only Σi(εi,θi∗)\Sigma_i(\varepsilon_i, \theta^{\ast}_i) is defined, in Theorem 5. The notation for the arm-specific parameter is also inconsistent: it is written θi∗\theta^{*}_i in Theorems 5 and 7, but θi⋆\theta^{\star}_i in Remark 6 and the appendix.

[1] A. Ben Yahmed, C. Calauzènes, and V. Perchet. Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting. NeurIPS 2024.

Questions for authors

Please feel free to address any of the points raised above.

4 comments

Thanks for all reviews.

W1.1 Solution Concept: NE versus SPE

We adopt NE to characterize deviation incentives over the full horizon, allowing randomized, history-dependent reporting strategies. This does not reduce the dynamic interaction to independent one-round decisions or restrict strategies to static reporting sequences. This solution concept is also consistent with the most closely related works, OptGTM and COBRA.

More importantly, Theorem 5 does not assume that the strategy profile is a NE. It establishes a regret–exploitability bound Expl⁡i⋆(σ)\operatorname{Expl}_{i^\star}(\sigma) on for any admissible strategy profile, with NE being the special case where exploitability is zero. Since every SPE is also a NE, the same regret guarantee applies to any admissible SPE under the stated conditions. See Common Response 2.2, Interpretation of Results. We recognize the additional requirements that SPE imposes on off-path behavior. We now discuss the related work adopting SPE in Section 1.2.

W1.2 History-Dependent Strategies and Sequence Notation

As described in Section 2.2 in manuscript, our strategies are potentially randomized, history-dependent reporting policies:

xt,i∼σi(⋅∣ht−1,xict).x_{t,i}\sim\sigma_i(\cdot\mid h_{t-1},x_i^{c_t}).

The notation {xt,i}t=1T\{x_{t,i}\}_{t=1}^{T} in the theorems denotes the reporting process induced by a policy during the interaction, rather than a sequence fixed before the interaction begins. We consistently use σi\sigma_i for the policy and xt,ix_{t,i} for its generated report. The policy-space definition and its relationship to admissibility are explained in Common Response 2.1, Strategy Space.

W1.2 Experimental Strategies and Equilibrium Verification

In Appendix F.2, what remains fixed within each epoch is the base reporting parameter ziz_i, while the actual report varies with the context:

xi(ct)=ct⊙zi,rt,i=⟨θ∗,xt(ct)⟩+ξt,i,x_{i}(c_t)=c_t\odot z_i\quad, r_{t,i}=\langle\theta^{*},x_{t}(c_t)\rangle+\xi_{t,i},

where ziz_i is fixed for each arm ii and the true features xi(ct)x_{i}(c_t) varies with context ctc_t, the ξt,i\xi_{t,i} is the noise. Appendix F.1 describes how reported features xt,ix_{t,i} are generated, which are to simulate strategic behaviors of arms under contract design-based utiliy with finite-difference method. Under such design, reported features are not fixed within epoches. We agree with your observation that these experiments do not compute or certify an equilibrium over the full strategy space. Their purpose is to evaluate the learner's performance as arms repeatedly adjust their reports to improve utility, rather than to verify equilibrium existence or convergence.

W2.1 Uniformly Optimal Arm

The uniformly optimal arm allows us to analyze how incentives drive strategic misreporting among arms, thereby bounding suboptimal pull counts and establishing regret bounds for PALinUCB. More explanations are listed in Common Response 1.2 Assumptions.

W2.2 Admissible Strategies and the Gap Condition

The gap separation condition εi≤Δ‾i\varepsilon_i\leq\underline{\Delta}_i allows us to analyze how incentives drive strategic misreporting among arms, thereby bounding suboptimal pull counts and establishing regret bounds for PALinUCB. More explanations are listed in Common Response 1.2 Assumptions. The admissible strategy space is discussed in 2.1, Strategy Space; the role of the condition and possible extensions are discussed in 1.2, Assumptions; and the technical contributions are summarized in 2.3, Technical Contributions.

W2.3 Role of θi∗\theta_i^{*}

The parameter θi∗\theta_i^{*} characterizes the relationship between reported features and true mean rewards; it is neither an additional action submitted by the arm in each round nor a quantity that the learner or other arms must know. Whereas OptGTM (Eq. 1) restricts arm behavior to a strictly linear function of a latent feature and COBRA (Eq. 2) restricts arm behavior to be optimistic, our analysis relaxes the corresponding requirements (Eq. 3), allowing reported features to deviate from an exact linear mapping of the underlying latent representation and does not assume the optimistic behaviors of arms. The detained explanation is listed in 2.1, Strategy Space.

W2.4 Algorithmic and Technical Novelty

PALinUCB and OptGTM use similar per-arm estimation structures and UCB selection rules. Our distinction lies in shaping competitive incentives through contract design and connecting learning performance to deviation gains without any additional detection or elimination mechanism. The mechanism and algorithmic novelty are explained in Common Response 1.1, Mechanism Design, and the analytical contributions are summarized in 2.3, Technical Contributions.

W2.5 Positioning Relative to OptGTM and COBRA

We have listed the detailed comparisons between our work and OptGTM, COBRA in Common Response 1, Positioning Our Work Relative to Prior Work. Specifically, when OptGTM assumes exact match of reported mean values and true mean values (see Eq. 1), our work relaxs the requirement that reported-feature predictions exactly match true mean rewards, allowing discrepancies of either sign that may vary over time. Besides, when COBRA assumes that all arms maintain optimism over all rounds (see Eq. 2), our analysis does not assume any suboptimal arm to satisfy such optimism conditions.

Q1 Missing Related Work

Thank you for pointing out Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting by Ben Yahmed, Calauzènes, and Perchet (NeurIPS 2024). We now add this reference and discuss its reporting constraint and use of SPE in Section 1.2 of our manuscript:

"Moreover, Ben Yahmed et al. (2024) studied another strategic bandit model under a debt-free reporting constraint --- where arms may retain part of their realized rewards --- and designed a mechanism that induces truthful reporting as a subgame-perfect equilibrium. In contrast, we study strategic feature reporting in contextual bandits. In specific, we apply the contract design to shape arms' incentives, which enables the learner to minimize the regret."

Q2 Arms' Knowledge of the True Parameter

Our theoretical results do not assume arms to know θ∗\theta^{*}. The corresponding statement in Remark 6 belongs to an illustrative market interpretation, rather than constituting a knowledge assumption of the formal model. The detailed explanation is listed in Common Response 2.1 Strategy Space.

Q3 Notation Corrections

Thank you for identifying these issues. We make the following corrections:

  • Explicitly define the strategy set used in Theorem 7 and align it with Theorem 5.
  • Consistently use θ∗\theta^{*} for the true reward parameter and θi∗\theta_i^{*} for an arm-specific fixed witness parameter.
  • Consistently use σi\sigma_i for a reporting policy and xt,it=1T\\{x_{t,i}\\}_{t=1}^{T} for its induced reporting process.

Dear Reviewer,

Thank you again for your helpful review—we kindly encourage you to check our rebuttal and revised manuscript above, and please let us know if anything further needs clarification. We hope our responses can help address your concerns, and we would be grateful if you would consider raising your overall evaluation of our work.

Best,

Authors

I thank the authors for their response. After reading the discussion with the other reviewers, I think a slight increase is warranted, so I’m raising my score to 2. I wish the authors good luck with their paper.

Reviewer_XEgvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a strategic bandit problem in which arms can manipulate their reported features. The manipulation strategies may be randomized, adaptive to past observations, and chosen separately at each round, subject to a bound on the discrepancy between the perceived reward induced by the reported features and the arm's true expected reward.

The authors propose a contract design that charges a fixed platform fee each time an arm is selected, together with a UCB-based algorithm that maintains a separate estimator for each arm. Under the assumption that a single arm is strictly optimal across all contexts, the paper establishes a poly⁡(log⁡T)\operatorname{poly}(\log T) regret bound.

Critical strengths
  • Clear application motivation: The problem is motivated by a practical application in e-retail.
  • Flexible feature manipulation model: The formulation allows a broader class of feature manipulation strategies than some prior work. In particular, it does not require reported features to preserve the true expected reward or their UCB estimates to exceed the true expected reward. Instead, it bounds the discrepancy between the perceived reward induced by the reported features and the arm's true expected reward.
  • Equilibrium existence in certain instances: The authors show that a Nash equilibrium exists for the proposed learner algorithm and arms' feature manipulation strategies in some instances.
Critical weaknesses
  • Concerns regarding assumptions and contract design: I have several concerns about the assumptions and the proposed contract design, as detailed in my questions below.

  • Clarity of presentation: I believe the writing could be improved by making the contributions and supporting references more explicit. In particular:

    • In Section 1.2, I encourage the authors to discuss the differences between this work and prior studies more directly, rather than primarily describing previous results. For example, at the end of the "Bandits With Strategic Arms" paragraph, it would be helpful to specify which restrictions are relaxed and what is most novel about the proposed incentive design.
    • In Section 2.2, under "Utility Function of Arms," the authors write "Later, our study indicates..." I encourage them to provide a specific reference to the section or result supporting this statement.
Questions for authors
  • Assumption that providers know the true market state: I have concerns about the assumption that providers know the true market state θ⋆\theta^\star. First, is this a standard assumption in the strategic bandit literature, or is it introduced in this work as a trade-off for allowing more flexible feature manipulation? Second, what does this assumption imply in practical applications, and under what circumstances might it be satisfied? In particular, could the authors clarify how the admissible manipulation constraint in Theorem 5 would be determined or enforced in practice, given that it depends on the true expected reward or market state?

  • Role and novelty of the proposed contract design: If I understand correctly, the proposed contract is intended to encourage the truly optimal arm to seek selection while weakening the incentives of less rewarding arms to compete. However, it remains unclear to me whether the contract also helps enforce or encourage compliance with the admissible manipulation constraint. Could the authors clarify this relationship? More broadly, I would appreciate a clearer explanation of what makes the proposed fixed-fee contract design novel, beyond the introduction of a platform fee charged upon each selection.

2 comments

Thank you for all reviews.

W2.1 Differences from Prior Work and Novelty of the Contract

The central distinction is that OptGTM and COBRA constrain reporting through detection and elimination mechanisms under selection-count utilities, whereas we shape arms' incentives through contract design and connect regret to deviation incentives without an additional detection or elimination mechanism.

The mechanism and algorithmic differences are detailed in Common Response 1.1, Mechanism Design; the assumptions are compared in 1.2, Assumptions; and the additional analytical contributions are discussed in 2.3, Technical Contributions. We will clarify these distinctions in Section 1.2 of the manuscript.

W2.2 Reference Supporting the Statement in Section 2.2

The most direct theoretical support for this statement is Theorem 5, which connects the learner's regret to the utility improvement available to the optimal arm through a unilateral deviation. Theorem 7 further establishes an approximate equilibrium guarantee when the optimal arm adopts a non-pessimistic strategy.

We have added "(see Theorem 5)" to the sentence beginning with "Later, our study indicates..." to clearly attribute the statement. The interpretation of these results is also provided in Common Response 2.2, Interpretation of Results.

Q1 Market State and Manipulation Constraint in Practice

Our theoretical results do not assume providers to know the true parameter θi∗\theta_i^{*}. Remark 6 uses a recommendation-platform example to explain the relationship between the true market parameter, witness parameters, and reporting discrepancies. The statement that providers know θi∗\theta_i^{*} belongs only to this illustrative example, rather than constituting an additional knowledge assumption of the formal model.

We do not introduce knowledge of the true parameter as a trade-off for allowing more flexible feature manipulation, nor does our argument rely on treating this knowledge as a standard assumption in strategic bandits. The Remark 6 is simply an illustrative interpretation. Furthermore, θi∗\theta_i^{*} is a fixed witness parameter characterizing an admissible reporting policy, not a parameter that the provider must submit. Its definition and role are explained in Common Response 2.1, Strategy Space.

Whereas OptGTM (Eq. 1) restricts arm behavior to a strictly linear function of a latent feature and COBRA (Eq. 2) restricts arm behavior to be optimistic, our analysis relaxes the corresponding requirements (Eq. 3), allowing reported features to deviate from an exact linear mapping of the underlying latent representation and does not assume the optimistic behaviors of arms.

Q2 Role and novelty of the proposed contract design
The admissbile strategy space defined with the contraint manipulation is a specific set of feasible strategies and the contract cannot enforce it. The role and novelty of contract design are explained in Common Response 1.1 Mechanism design.

Dear Reviewer,

Thank you again for your helpful review—we kindly encourage you to check our rebuttal and revised manuscript above, and please let us know if anything further needs clarification. We hope our responses can help address your concerns, and we would be grateful if you would consider raising your overall evaluation of our work.

Best,

Authors

Comments on the paper

3 comments
AuthorsOpenReview ↗

Common Response to all reviews

Thanks for all Reviewers!

Overview and Comparison Table

The Table 1 in Appendix G compares our results to existing works. We also detail the results here.

Algorithm / ResultArm UtilityMechanismKey AssumptionsRegret BoundApplicable Profiles
OptGTM, Theorem 5.2UicountU_i^{\mathrm{count}}Grim-trigger eliminationUCBt,i(xt,i)≥μi(ct)\mathrm{UCB}_{t,i}(x_{t,i})\geq\mu_i(c_t) (Assumption 3)O~(dK2KT)\widetilde O(dK^2\sqrt{KT})Any NE
OptGTM, Corollary E.9UicountU_i^{\mathrm{count}}Grim-trigger elimination⟨θi⋆,xt,i⟩=μi(ct)\langle\theta_i^\star,x_{t,i}\rangle=\mu_i(c_t) (Eq.1 Lemma E.1)O~(dKT)\widetilde O(d\sqrt{KT})Any NE under the stated condition
COBRA, Theorem 3UicountU_i^{\mathrm{count}}Leave-one-out eliminationμi(ct)≤⟨θ⋆,xt,i⟩≤UCBt(xt,i)≤UCBt,−i(xt,i)\mu_i(c_t)\leq\langle\theta^\star,x_{t,i}\rangle\leq\mathrm{UCB}_t(x_{t,i})\leq\mathrm{UCB}_{t,-i}(x_{t,i}) (Eq.2, Assumption 1)O~(dT+KT)\widetilde O(d\sqrt T+\sqrt{KT})Any NE
PALinUCB, Theorem 5UicontractU_i^{\mathrm{contract}}Contract design; no eliminationE\mathcal EΔmax⁡g1(g2BT+Expl⁡i⋆(σ))\frac{\Delta_{\max}}{g_1}\bigl(g_2B_T+\operatorname{Expl}_{i^\star}(\sigma)\bigr)Any admissible profile
PALinUCB, NE corollary of Theorem 5UicontractU_i^{\mathrm{contract}}Contract design; no eliminationE\mathcal EΔmax⁡g2g1BT\frac{\Delta_{\max}g_2}{g_1}B_TAny admissible NE
PALinUCB, Lemma 13 and Theorem 7UicontractU_i^{\mathrm{contract}}Contract design; no eliminationE\mathcal EΔmax⁡BT\Delta_{\max}B_Tσ=(σi⋆∈Σi⋆np,σ−i∗)\mathbf{\sigma}=(\sigma_{i^\star}\in\Sigma_{i^\star}^{\mathrm{np}},\sigma_{-i^{*}}) forms a ρT\rho_T-NE

(1) Utility functions are defined as below

Uicount=E![∑t=1T1it=i],Uicontract=E![∑t=1T1it=i(rt,i−η)].U_i^{\mathrm{count}} = \mathbb E\\!\left[\sum_{t=1}^{T}\mathbf 1\\{i_t=i\\}\right], \qquad U_i^{\mathrm{contract}} = \mathbb E\\!\left[\sum_{t=1}^{T}\mathbf 1\\{i_t=i\\}(r_{t,i}-\eta)\right].

(2) Our assumptions E\mathcal{E}. We assume that there exists a uniformly optimal arm over the context space, that is, there exists an arm i∗i^{*} such that μi∗(c)>μj(c)\mu_{i^{*}}(c) > \mu_j(c) under any context c∈Cc\in\mathcal{C} for any arm j≠i∗j\neq i^{*}. The admissible strategy space Σi(εi)\Sigma_i(\varepsilon_i) is defined as

\Sigma_i(\varepsilon_i):=\left\\{\sigma_i=(\theta_i^{*},\\{x_{t,i}\\}_{t=1}^T):\lVert\theta_i^{*}\rVert_2\leq 1, \bigl\lvert\bigl\langle\theta_i^{*},\\,x_{t,i}\bigr\rangle-\mu_i(c_t)\bigr\rvert\le\varepsilon_i,\quad\forall t\in[T]\right\\}\quad\text{(Eq. 3)}

with 0≤εi<Δ‾i0\leq\varepsilon_i < \underline{\Delta}_i for all i≠i∗i\neq i^{*}. For the optimal arm i∗i^{*}, there exist constants 0<g1≤g2<∞0 < g_1\leq g_2 < \infty such that g1≤μi∗(c)−η≤g2,∀c∈C.g_1\leq\mu_{i^{*}}(c)-\eta\leq g_2,\forall c\in\mathcal{C}.

(3) The non-pessimistic strategy class Σinp\Sigma_{i}^{\mathrm{np}} of arm ii is defined as

\Sigma_i^{\mathrm{np}}:=\left\\{\sigma_i\in\Sigma_i(\varepsilon_i):\mathbb{P}_{\sigma_i,\boldsymbol{\sigma}_{-i}}\left(m_{t,i}\geq 0,\\ \forall t\in[T]\right)=1,\\ \forall\boldsymbol{\sigma}_{-i}\in\prod_{j\neq i}\Sigma_j(\varepsilon_j)\right\\}\quad\text{(Eq. 4)}

with mt,i=εt,i−xt,i⊤Vt,i−1∑s<tεs,ixs,i⋅1(is∗=i)m_{t,i}=\varepsilon_{t,i}-x_{t,i}^\top V_{t,i}^{-1}\sum\limits_{s < t}\varepsilon_{s,i}x_{s,i}\cdot\mathbf{1}(i_s^{*}=i) and 0≤εi∗<Δ‾i0\leq\varepsilon_i^{*} < \underline{\Delta}_i for all i≠i∗i\neq i^{*}. BTB_T denotes the suboptimal-selection bound used in our analysis, with

BT=O~!(d2∑i≠i⋆1κi3Δi2),κi=1−εiΔi.B_T = \widetilde O\\!\left(d^2\sum_{i\neq i^\star}\frac{1}{\kappa_i^3\Delta_i^2}\right), \qquad \kappa_i=1-\frac{\varepsilon_i}{\Delta_i}.

For fixed problem parameters, BTB_T and the approximation tolerance ρT\rho_T in Theorem 7 grow polylogarithmically in TT.

1. Positioning Our Work Relative to Prior Work

1.1 Mechanism Design

The deigsn of OptGTM, COBRA, and our PALinUCB all follow the principle of optimism in the face of uncertainty. The central distinction is that OptGTM and COBRA assume arms aim to maximize its expected cumulative selection Ui=E![∑t=1T1it=i]U_i=\mathbb{E}\\!\left[\sum_{t=1}^{T}\mathbf{1}\\{i_t=i\\}\right] and apply elimination rules to constrain arms' strategic behaviors. Specifically, OptGTM detects inflated reports by comparing the cumulative lower confidence bounds associated with reported features against an upper confidence bound on cumulative realized rewards. COBRA instead constructs a detection mechanism using leave-one-out estimation. Both mechanisms use the threat of elimination to constrain strategic behavior.

In contrast, our PALinUCB algorithm considers arms to maximize Ui=E![∑t=1T1it=i(rt,i−η)]U_i=\mathbb{E}\\!\left[\sum_{t=1}^{T}\mathbf{1}\\{i_t=i\\}(r_{t,i}-\eta)\right], which shapes arms' incentives directly. Under our contract design, selection is no longer unconditionally beneficial to an arm: its value depends on the difference between the true reward and the fee. Our contract design changes the payoff structure of competition, aligning arms' incentives to pursue their own utility with the learner's objective and thereby helping minmize the learner's regret through incentive design.

The novelty of our work lies in integrating utility design with the learning algorithm to establish a connection between arms' gains from deviation incentives, selection counts, and the learner's regret. Algorithmically, PALinUCB uses a per-arm estimation structure and a UCB selection rule similar to those of OptGTM, but requires no additional detection or elimination mechanism. Our experiments also show that (Appendix F.3), in the settings tested, even standard LinUCB performs well when equipped with our contract design, providing empirical support for this approach. Although our analysis builds in part on standard UCB framework, it additionally controls the cumulative impact of strategic reports on historical estimates (Corollary 11) and connects learning performance to arms' incentives to deviate (Theorem 5).

1.2 Assumptions

The differences between our assumptions and those of OptGTM and COBRA should be understood in conjunction with their respective utility functions and mechanisms. All three methods follow the principle of optimism in the face of uncertainty. However, an optimistic selection rule does not automatically ensure optimism under strategic reports from every arm. Our contract changes arms' incentives to compete, and our analysis does not assume that all arms satisfy a common optimism condition.

Comparison with OptGTM

As in the table above, when OptGTM assumes exact match of reported mean values and true mean values (see Eq. 1), our work relaxs the requirement that reported-feature predictions exactly match true mean rewards, allowing discrepancies of either sign that may vary over time. (see Eq. 3)

Comparison with COBRA

As in the table above, when COBRA assumes that all arms maintain optimism over all rounds (see Eq. 2), our analysis does not assume all suboptimal arms to satisfy such optimism conditions. In our results for non-pessimistic strategies (see Eq. 4), the similar optimism condition is imposed only on the optimal arm. Theorem 5 of our work establishes the regret–exploitability relationship through a calibrated benchmark deviation of the optimal arm, without assuming all arms' joint strategy profile maintains optimism.

Relationship to incentives.

Under a utility function E[∑t=1T1(it=i)]\mathbb{E}[\sum\limits_{t=1}^T\mathbb{1}(i_t=i)], seeking a higher selection index (i.e., UCB) has a natural motivation. However, an arm may not aim to maximize its UCB and to be pulled in every round. For example, underreporting in some round may help the arms to be pulled in many more rounds in the future, which may lead to UCB(xt,i)≤μt,i\text{UCB}(x_{t,i})\leq\mu_{t,i} Hence, Eq. 2 may not be a necessary condition when arms aim to maximize E[∑t=1T1(it=i)]\mathbb{E}[\sum\limits_{t=1}^T\mathbb{1}(i_t=i)]. Under our utility function, the benefits of selection depends on the per round's contract, which allows all arms to have more reporting choices.

Interpretation of Our Assumptions

Current assumptions allow us to analyze how incentives drive strategic misreporting among arms, thereby bounding suboptimal pull counts and establishing regret bounds for PALinUCB. Extending our analysis to general contextual settings with context-dependent optimal arms is a natural avenue for future research, where the regret would may depend on each arm's probability of being optimal Pr⁡!(i⋆(ct)=i)\Pr\\!\left(i^\star(c_t)=i\right), Nonetheless, this study serves as a foundational step toward that broader setting.

2. Strategy Space and Interpretation of Results

2.1 Strategy Space

Reporting policies. Arms' strategies are potentially randomized, history-dependent reporting policies, rather than predetermined sequences of reports. Specifically, arm ii generates its report based on its observable history and current true features:

xt,i∼σi!(,⋅∣ht−1,xict).x_{t,i}\sim\sigma_i\\!\left(\\,\cdot\mid h_{t-1},x_i^{c_t}\right).

The notation xt,it=1T\\{x_{t,i}\\}_{t=1}^{T} in the theorems denotes the reporting process induced by such a policy during the interaction, it does not assume reports to be fixed in advance. We consistently use σi\sigma_i for the policy and xt,ix_{t,i} for its generated report to clarify this distinction.

Admissibility and the arm-specific parameter. For each admissible reporting policy σi\sigma_i, there exists a fixed witness parameter θi⋆\theta_i^\star such that the reporting process induced by that policy satisfies

ϵt,i:=⟨θi⋆,xt,i⟩−μi(ct),∣ϵt,i∣≤εi.\epsilon_{t,i}:=\langle\theta_i^\star,x_{t,i}\rangle-\mu_i(c_t),\qquad\lvert\epsilon_{t,i}\rvert\leq\varepsilon_i.

Different policies may admit different fixed witness parameters θi∗\theta_i^{*}, but the parameter associated with a given policy remains fixed throughout the interaction. The parameter θi∗\theta_i^{*} characterizes the relationship between reported features and true mean rewards; it is neither an additional action submitted by the arm in each round nor a quantity that the learner or other arms must know. Whereas OptGTM (Eq. 1) restricts arm behavior to a strictly linear function of a latent feature and COBRA (Eq. 2) restricts arm behavior to be optimistic, our analysis relaxes the corresponding requirements (Eq. 3), allowing reported features to deviate from an exact linear mapping of the underlying latent representation and does not assume the optimistic behaviors of arms.

Non-pessimistic strategies of the optimal arm. Within the admissible strategy space, we identify a class of non-pessimistic strategies. The defining condition (Eq. 4) accounts for both the current reporting discrepancy and the effect of historical discrepancies on the current estimate:

mt,i=ϵt,i−xt,i⊤Vt,i−1∑s<t\is=iϵs,ixs,i.m_{t,i}=\epsilon_{t,i}-x_{t,i}^{\top}V_{t,i}^{-1}\sum_{\substack{s < t\\\i_s=i}}\epsilon_{s,i}x_{s,i}.

A non-pessimistic strategy of the optimal arm assumes mt,i⋆≥0m_{t,i^\star}\geq0 in every round against any admissible stratgies of the other arms. This condition concerns the relationship between current reporting discrepancies and their historical estimation effects, rather than merely assuming optimism in each round. Theorem 7 imposes this condition on the optimal arm, while allowing the remaining arms to use arbitrary admissible policies.

2.2 Interpretation of the Main Theorems

Theorem 5: Connecting regret to the optimal arm's incentive to deviate. Theorem 5 does not assume that the strategy profile is a Nash equilibrium. Instead, it establishes a regret–exploitability bound for any admissible strategy profile. Specifically,

Expl⁡i⋆(σ)=sup⁡σi⋆′∈Σi⋆(εi⋆)[Ui⋆(σi⋆′,σ−i⋆)−Ui⋆(σ)]\operatorname{Expl}_{i^\star}(\sigma)=\sup_{\sigma'_{i^\star}\in\Sigma_{i^\star}(\varepsilon_{i^\star})}\left[U_{i^\star}(\sigma'_{i^\star},\sigma_{-i^\star})-U_{i^\star}(\sigma)\right]

measures the largest utility improvement the optimal arm can obtain by unilaterally changing its strategy. Regardless of the strategies adopted by the arms, Expli⋆(σ)\text{Expl}_{i^\star}(\sigma) captures their impact on the regret of PALinUCB, ensuring that Theorem 5 remains applicable.

Theorem 7: Sufficient conditions for approximate equilibrium. Theorem 7 proceeds in the other direction: if the optimal arm adopts a non-pessimistic strategy, then the resulting profile forms a ρT\rho_T-Nash equilibrium with the bound stated in the theorem, regardless of which admissible strategies the other arms adopt.

2.3 Technical Contributions

Beyond the standard UCB framework,our work additionally involve contract design to shape arms' incentives of strategic reporting. We summarize the key proof steps as below. First, in Lemma 10, we distinguish statistical uncertainty from strategic reporting bias and control them separately: the former is analyzed with concentration inequalities, while the latter depends both on current reporting bias and the cumulative effects of historical bias on parameter estimates. Secondly, regardless of arms' reporting strategies, Corollary 11 bounds the cumulative reporting bias, enabling Lemma 13 to bound the selection counts of suboptimal arms. Finally, in Theorem 5, we use the contract's structure to translate these learning guarantees into a quantitative relationship between regret and the optimal arm's gains from unilateral deviations, and further derive approximate equilibrium guarantees. The additional technical contributions therefore lie in controlling strategic bias and its dynamic accumulation, and connecting learning errors to strategic incentives.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.