acceptodds
Desk rejected at ICLR 2027

COBRA: Contextual Bandit Algorithm for Ensuring Truthful Strategic Agents

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

This paper considers a contextual bandit problem involving multiple agents, where a learner sequentially observes the contexts and the agents' reported arms, and then selects the arm that maximizes the system's overall reward. Existing work in contextual bandits assumes that agents always truthfully report their arms, which is unrealistic in many real-life applications. For instance, consider an online platform with multiple sellers; some sellers may misrepresent product features to maximize reward, such as having the platform preferentially recommend their products to its users. To address this challenge, we propose an algorithm, COBRA, for contextual bandit settings involving strategic agents that disincentivize their strategic behavior without using any monetary incentives, while having an approximate Bayesian incentive compatibility and a sub-linear regret guarantee. Experimental results also validate our theoretical results and the different performance aspects of COBRA.

Primary area:
learning theory
Keywords:
Contextual bandits, Strategic agents, Incentive compatibility, 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_rwCbOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper considers strategic contextual bandits, where rational arms may misreport their contexts to maximize the number of times they are pulled over TT rounds, while the realized reward depends only on the true context. The authors propose LOOM, a VCG-inspired routine that compares, for each arm, a pessimistic estimate of its cumulative reward built from the other arms' data against an optimistic estimate built from its own observed rewards, and eliminates arms for which the former exceeds the latter. LOOM combined with a suitably adapted UCB selection rule constitutes the proposed COBRA algorithm, which the authors also extend to non-linear rewards via a class of "LOOM-compatible" base algorithms. The authors claim that under COBRA truthfulness is an approximate (O~(dT)\tilde O(d\sqrt T)) Nash equilibrium, and they state sublinear regret bounds under truthful reporting and, under an additional assumption and an advantage constant CC, for any Nash equilibrium played by the arms. The authors also provide empirical results on synthetic problem instances to support their theoretical claims.

Critical strengths

The problem and the LOOM idea are well motivated and conceptually clean. Incentive-compatible selection without payments in a contextual bandit, where agents control their reported features but not the realized reward, is a relevant setting (marketplaces, recommendation) with little prior work beyond Kleine Buening et al. (2024). Testing an agent against a reward estimate built only from the other agents' data, so that the agent cannot influence the statistic used to judge it, is a natural transfer of the VCG exclusion principle to a learning setting, and the LOOM test itself is simple to state and to plug into any algorithm with valid confidence widths.

Critical weaknesses

1. The approximate incentive-compatibility result (Theorem 2, and Theorem 3 by the same argument) is incorrect, and the paper's own Example 2 is a counterexample. The ε\varepsilon-NE half of the proof (Sec. C.2.1, Eqs. 16–17) bounds a deviating agent's number of selections by reusing Eq. (14), ∑t1(at≠at⋆)≤O~(dT)\sum_t \mathbf{1}(a_t \neq a^\star_t) \le \tilde O(d\sqrt T), which was derived under xt,a=xt,a⋆x_{t,a}=x^\star_{t,a} from the confidence ellipsoid for θ^t\hat\theta_t. Lemma 2 shows that this ellipsoid can be invalid once agent aa misreports (as happens in the example below), and no part of the argument invokes LOOM, elimination, or peer coverage; Sec. C.2.1 in fact states that the proof "does not involve the advantage constant CC". Concretely, in Example 2 of Sec. B.1 (d=1d=1, θ⋆=1\theta_\star=1, xt,1⋆=1/2x^\star_{t,1}=1/2, xt,2⋆=1/4x^\star_{t,2}=1/4, agent 2 reports 11): since UCBt(x)=x,(θ^t+αt/Vt)\mathrm{UCB}_t(x) = x\\,(\hat\theta_t + \alpha_t/\sqrt{V_t}) for x>0x > 0, agent 2 has exactly twice the UCB of agent 1 whenever θ^t+αt/Vt>0\hat\theta_t + \alpha_t/\sqrt{V_t} > 0, which holds with high probability, and is therefore always selected; Ot,−2=∅\mathcal{O}_{t,-2}=\emptyset, so LCBt,2(x)<0<UCBt,2(y)\mathrm{LCB}^{(x)}_{t,2} < 0 < \mathrm{UCB}^{(y)}_{t,2} and LOOM never fires. Step 5 never excludes agent 2: at t=1t=1, α1,−2≥α1\alpha_{1,-2} \ge \alpha_1, and for t≥2t \ge 2 it compares UCBt(1)=θ^t+αt/λ+St(2)\mathrm{UCB}_t(1) = \hat\theta_t + \alpha_t/\sqrt{\lambda + S_t(2)}, which tends to 1/41/4, with UCBt,−2(1)=αt,−2/λ≥S≥1\mathrm{UCB}_{t,-2}(1)=\alpha_{t,-2}/\sqrt{\lambda} \ge S \ge 1; the former stays below the latter for the parameters used in the paper (e.g., λ=0.01\lambda = 0.01). Finally, the ridge estimate converges to 1/41/4, exactly the bias predicted by Lemma 2. Since agent 2 is suboptimal in every round, it is selected at most O~(dT)\tilde O(d\sqrt T) times under truthful reporting, so the deviation gain is T−o(T)=Θ(T)T-o(T)=\Theta(T) against the claimed O~(dT)\tilde O(d\sqrt T), while every hypothesis of Theorem 2 is satisfied (bounded features, shared reward function, a single over-reporting deviator, no collusion). This is consequential because approximate Bayesian incentive compatibility is the paper's headline contribution and the reason mechanism design is being done at all; without it, COBRA is a Lin-UCB variant with an elimination filter whose incentive effect is unproven. The example also shows that any correct bound on a deviator's gain must depend on peer coverage, i.e., on CC, which Theorem 2 claims not to.

2. No sublinear strategic-regret guarantee is actually established (Theorems 4–5). The regret bound O~(CdT+NT)\tilde O(Cd\sqrt T+\sqrt{NT}) carries the advantage constant CC of Definition 5, which the main text presents as a constant. By Eq. (27), Ct,a2=1+λmax⁡(Vt,−a−1/2Gt,aVt,−a−1/2)C_{t,a}^2 = 1+\lambda_{\max}\big(V_{t,-a}^{-1/2}G_{t,a}V_{t,-a}^{-1/2}\big), so Ct,a2=1+St(a)/λC_{t,a}^2 = 1+S_t(a)/\lambda whenever agent aa's features are orthogonal to those of the other agents, e.g., in the KK-armed special case with canonical features and truthful reporting, where Assumption 1 holds with high probability. Hence C=Θ(T)C=\Theta(\sqrt T) and the bound becomes the trivial O~(dT)\tilde O(dT); Example 2 of Sec. B.1 exhibits the same growth. The only general bound offered, Ct,a≤1+St(a)L/λC_{t,a} \le \sqrt{1+S_t(a)L/\lambda}, grows with the number of pulls of the agent, and the authors state that bounding CC theoretically is open. They instead rely on measurements on synthetic instances where all agents' features are drawn from a common distribution, i.e., where peer coverage is favorable; even there, CC keeps increasing in Fig. 7f–7h. Moreover, the bound rests on Assumption 1, which requires a UCB built from an estimator that Lemma 2 shows to be shifted by −Vt−1∑sxsηs-V_t^{-1}\sum_s x_s\eta_s (a downward bias according to the authors' own Case 2 argument) to remain optimistic at the inflated reported features f(xt,a)f(x_{t,a}). Under persistent misreporting, this bias term does not vanish with tt while the width does (in Example 2 it converges to −3/4-3/4), so this is a condition on the outcome of the interaction rather than on the instance; in Example 2 it fails: f(xt,2)=1f(x_{t,2})=1 while UCBt(1)→1/4\mathrm{UCB}_t(1) \to 1/4. Lemma 3's claim that the assumption is realizable "with no assumption at all" via leave-one-out selection holds only when the optimal arm is itself the deviator; otherwise Ot,−at⋆\mathcal{O}_{t,-a^\star_t} contains the deviator's corrupted data (again in Example 2, UCBt,−1(1/2)→1/8<1/2=f(xt,1⋆)\mathrm{UCB}_{t,-1}(1/2) \to 1/8 < 1/2 = f(x^\star_{t,1})). This is consequential because the abstract and contribution list advertise "a sub-linear regret guarantee" that the results do not deliver; what is proven is a regret bound conditional on an unverified, trajectory-dependent quantity and on an assumption that effectively presupposes the mechanism works.

Questions for authors

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

4 comments
AuthorsOpenReview ↗

Response [1/2]

We thank the reviewer for the careful review. We appreciate the recognition of four aspects of the work:

  • that the problem and the LOOM idea are well motivated and conceptually clean;
  • that incentive-compatible selection without payments is a relevant setting with prior work beyond Kleine Buening et al. (2024);
  • that testing an agent against a reward estimate built only from the other agents' data, which the agent cannot influence, is a natural transfer of the VCG exclusion principle to a learning setting;
  • that the LOOM test is simple to state and to plug into any algorithm with valid confidence widths. We address each weakness as follows:

The approximate incentive-compatibility result (Theorem 2, and Theorem 3 by the same argument) is incorrect, and the paper's own Example 2 is a counterexample. The -NE half of the proof (Sec. C.2.1, Eqs. 16–17) bounds a deviating agent's number of selections by reusing Eq. (14), ∑t1(at≠at⋆)≤O~(dT)\sum_t \mathbf{1}(a_t \neq a^\star_t) \le \tilde O(d\sqrt T), which was derived under xt,a=xt,a⋆x_{t,a}=x^\star_{t,a} from the confidence ellipsoid for θ^t\hat\theta_t. Lemma 2 shows that this ellipsoid can be invalid once agent misreports (as happens in the example below), and no part of the argument invokes LOOM, elimination, or peer coverage; Sec. C.2.1 in fact states that the proof "does not involve the advantage constant CC". ...

Thank you for this careful check. Theorem 2 is stated for the setting in which all agents report truthfully, i.e., under the truthful profile σ⋆\boldsymbol{\sigma}^\star. Example 2, in contrast, allows misreporting: agent 22 reports xt,2=1x_{t,2} = 1 instead of its true feature xt,2⋆=1/4x^\star_{t,2} = 1/4. We included it in Sec. B.1 deliberately, as a failure case of LOOM in which the misreporting agent's direction is never covered by other agents' observations.

Under the truthful profile, Theorem 2 establishes two guarantees:

  1. Regret: RT(COBRA,σ⋆)=O~(dT)\mathfrak{R}_T(\text{COBRA}, \boldsymbol{\sigma}^\star) = \tilde{O}(d\sqrt{T}).

  2. No penalty for truthful agents: each truthful agent aa receives ST(a)≥ST⋆(a)−O~(dT)S_T(a) \ge S^\star_T(a) - \tilde{O}(d\sqrt{T}) selections (Eq. (15)), and with probability at least 1−δt,ax−δt,ay1 - \delta^x_{t,a} - \delta^y_{t,a} no truthful agent is eliminated by LOOM (Theorem 1). In other words, a truthful agent loses at most O~(dT)\tilde{O}(d\sqrt{T}) selections due to estimation error.

Both guarantees remain valid, and Example 2 does not contradict them.

Gains from misreporting are not covered by Theorem 2. Since Theorem 2 considers only truthful agents, the ε\varepsilon-NE in its statement quantifies the selections a truthful agent may lose due to estimation error (Eq. (15)). It does not bound the gain of an agent that misreports while others remain truthful.

Guarantee under misreporting. Misreporting is covered by Theorem 4 (and Theorem 5 in the non-linear case). It controls a misreporting agent via LOOM (Lemma 6) and explicitly depends on the advantage constant CC (Definition 5), which quantifies peer coverage. In Example 2, C=Θ(T)C = \Theta(\sqrt{T}) (Sec. B.1), so this guarantee correctly reduces to the trivial O~(dT)\tilde{O}(dT). This is why we keep CC explicit: the guarantee degrades continuously as peer coverage deteriorates.

↓ ↓ ↓ Continued below ↓ ↓ ↓

AuthorsOpenReview ↗

Response [2/2]

No sublinear strategic-regret guarantee is actually established (Theorems 4–5). The regret bound O~(CdT+NT)\tilde O(Cd\sqrt T+\sqrt{NT}) carries the advantage constant CC of Definition 5, which the main text presents as a constant. By Eq. (27), Ct,a2=1+λmax⁡(Vt,−a−1/2Gt,aVt,−a−1/2)C_{t,a}^2 = 1+\lambda_{\max}\big(V_{t,-a}^{-1/2}G_{t,a}V_{t,-a}^{-1/2}\big), so Ct,a2=1+St(a)/λC_{t,a}^2 = 1+S_t(a)/\lambda whenever agent's features are orthogonal to those of the other agents, e.g., in the KK-armed special case with canonical features and truthful reporting, where Assumption 1 holds with high probability. Hence C=Θ(T)C=\Theta(\sqrt T) and the bound becomes the trivial O~(dT)\tilde O(dT); Example 2 of Sec. B.1 exhibits the same growth. The only general bound offered, Ct,a≤1+St(a)L/λC_{t,a} \le \sqrt{1+S_t(a)L/\lambda}, grows with the number of pulls of the agent, and the authors state that bounding theoretically is open. They instead rely on measurements on synthetic instances where all agents' features are drawn from a common distribution, i.e., where peer coverage is favorable; even there, CC keeps increasing in Fig. 7f–7h. Moreover, the bound rests on Assumption 1, which requires a UCB built from an estimator that Lemma 2 shows to be shifted by −Vt−1∑sxsηs-V_t^{-1}\sum_s x_s\eta_s (a downward bias according to the authors' own Case 2 argument) to remain optimistic at the inflated reported features f(xt,a)f(x_{t,a}). Under persistent misreporting, this bias term does not vanish with while the width does (in Example 2 it converges to −3/4-3/4), so this is a condition on the outcome of the interaction rather than on the instance; in Example 2 it fails: f(xt,2)=1f(x_{t,2})=1 while UCBt(1)→1/4\mathrm{UCB}_t(1) \to 1/4. ...

Theorems 4–5 are conditional bounds. The reviewer is correct that CC is not a constant in general. When an agent's features are orthogonal to those of all other agents (e.g., the KK-armed case with canonical features), Ct,a2=1+St(a)/λC_{t,a}^2 = 1 + S_t(a)/\lambda. In that case, and in Example 2, C=Θ(T)C = \Theta(\sqrt{T}) and the bound is vacuous. Theorems 4 and 5 therefore give sublinear regret only when C=o(T)C = o(\sqrt{T}) and Assumption 1 holds. The unconditional sublinear guarantee in our paper is the truthful-reporting bound O~(dT)\tilde{O}(d\sqrt{T}) of Theorem 2, which does not involve CC. The claim of "a sub-linear regret guarantee" in the abstract should be read in this restricted sense, and we agree that, as written, it overstates the strategic case.

Empirical behavior of CC. In Fig. 7f–7h, the maximum value of CC increases only during roughly the first 300 rounds and then remains flat until T=5000T = 5000. It is about 4.0–4.2 across NN and about 4.2–5.5 across dd. Θ(T)\Theta(\sqrt{T}) growth would roughly quadruple it over this range. The increase across curves reflects the dimension dd, not TT. We agree, however, that these instances have favorable peer coverage, since all agents' features are drawn from a common distribution, so they do not establish boundedness of CC in general.

Assumption 1. We agree that Assumption 1 is a condition on the interaction rather than on the instance. Under persistent misreporting, the bias in Lemma 2 does not vanish while the confidence width does, and in Example 2 the assumption fails (f(xt,2)=1f(x_{t,2}) = 1 while

UCBt(1)→1/4\mathrm{UCB}_t(1) \to 1/4).

Under truthful reporting, it holds with high probability (Lemma 4).

Lemma 3. The reviewer is correct. The leave-one-out argument holds only when the optimal agent is the deviator. Otherwise, Ot,−at⋆\mathcal{O}_{t,-a^\star_t} contains the deviator's corrupted data, as the reviewer's computation in Example 2 shows (

UCBt,−1(1/2)→1/8<1/2\mathrm{UCB}_{t,-1}(1/2) \to 1/8 < 1/2).

In summary, we prove sublinear regret under truthful reporting and a regret bound under misreporting that depends on peer coverage through CC and on Assumption 1. Replacing both with verifiable, instance-level conditions is the main open problem left by our work.

We thank the reviewer again for the careful review, which will help us improve the paper. We hope these additions address your concerns and strengthen your view of our work.

Thank you for your response. I’m raising my score to 2. Good luck with your paper!

We sincerely thank you for the feedback and for increasing your score.

Reviewer_VwrPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies contextual bandits with strategic agents who may misreport their features to increase their selection frequency. The authors propose COBRA, which incorporates a leave-one-out-based mechanism (LOOM) to discourage misreporting without monetary incentives. The paper establishes approximate incentive-compatibility and regret guarantees for linear and non-linear reward functions, supported by numerical experiments.

Critical strengths
  1. The paper addresses an important problem at the intersection of contextual bandits and mechanism design. Using information from other agents to detect strategic misreporting provides an interesting approach to incentivizing truthful behavior.

  2. The proposed approach exploits shared information across agents and achieves improved leading-order regret guarantees under suitable conditions. The extension to non-linear reward functions further broadens its applicability.

Critical weaknesses
  1. The regret guarantees rely on Assumption 1 and sufficient cross-agent feature coverage. In particular, the coverage constant CC can grow as Θ(T)\Theta(\sqrt{T}), making the regret bound potentially linear. These requirements limit the generality of the theoretical improvements.

2.The proof of Theorem 2 appears to apply the bound on suboptimal selections derived under truthful reporting (Eq. (14) in Appendix C.2.1) to unilateral deviations. However, strategic misreporting may bias the reward estimator, invalidating the confidence bounds used in the argument.

Questions for authors
  1. Under what conditions can Assumption 1 and a bounded coverage constant CC be guaranteed? Could the authors further clarify the trade-offs relative to OptGTM and provide more direct empirical evidence of incentive compatibility by measuring agents' gains from strategic deviations?

2.In Appendix C.2.1, Eq. (14) appears to be derived under truthful reporting, relying on the equality between reported and true features. However, it is subsequently applied to unilateral deviations in deriving Eq. (17). Could the authors clarify why this bound remains valid under strategic misreporting?

2 comments
AuthorsOpenReview ↗

Response [1/2]

We thank the reviewer for a careful review. We appreciate the recognition of the importance of the problem at the intersection of contextual bandits and mechanism design, the use of information from other agents to detect strategic misreporting, and the extension to non-linear reward functions with theoretical guarantees. We have addressed each of the reviewer’s concerns as follows:

The regret guarantees rely on Assumption 1 and sufficient cross-agent feature coverage. In particular, the coverage constant CC can grow as Θ(T)\Theta(\sqrt{T}), making the regret bound potentially linear. These requirements limit the generality of the theoretical improvements.

We agree that Theorems 4 and 5 depend on Assumption 1 and on the coverage constant CC, and that the bound becomes vacuous when C=Θ(T)C = \Theta(\sqrt{T}). We offer three points of context.

Truthful reporting does not depend on CC. When agents report truthfully, Theorem 2 gives regret O~(dT)\tilde{O}(d\sqrt{T}) with no dependence on CC, and Assumption 1 holds with high probability (Lemma 4). Both requirements matter only for bounding the effect of misreporting.

Some coverage condition is needed for leave-one-out detection. LOOM detects misreporting by comparing an agent's rewards with predictions built from other agents' data. If no other agent's observations cover a direction, a misreport in that direction cannot be detected. Example 2 makes this concrete: C=Θ(T)C = \Theta(\sqrt{T}) and COBRA incurs Θ(T)\Theta(T) regret. The dependence on CC therefore reflects a real limitation of leave-one-out detection, not just an artifact of the analysis.

CC is small in practice. In our experiments, the empirical advantage constant remains small (Figs. 7–8), because the agents' features jointly cover the feature space.

Replacing Assumption 1 and CC with weaker, verifiable conditions is an important open problem, which we acknowledge as a limitation.

The proof of Theorem 2 appears to apply the bound on suboptimal selections derived under truthful reporting (Eq. (14) in Appendix C.2.1) to unilateral deviations. However, strategic misreporting may bias the reward estimator, invalidating the confidence bounds used in the argument. In Appendix C.2.1, Eq. (14) appears to be derived under truthful reporting, relying on the equality between reported and true features. However, it is subsequently applied to unilateral deviations in deriving Eq. (17). Could the authors clarify why this bound remains valid under strategic misreporting?

The reviewer is correct about Eq. (14). However, Theorem 2 establishes the following for the setting in which all agents report truthfully:

  • regret O~(dT)\tilde{O}(d\sqrt{T});
  • no false elimination (Theorem 1);
  • no penalty for truthful agents relative to the oracle selection (Eq. (15)).

Unilateral deviations (or misreporting), where the estimator is contaminated, are handled by Theorems 4 and 5. Their proofs do not use Eq. (14). Instead, they control the contamination through the leave-one-out bounds, the validity check (Step 5), and Assumption 1, at the cost of the advantage constant CC.

↓ ↓ ↓ Continued below ↓ ↓ ↓

AuthorsOpenReview ↗

Response [2/2]

Under what conditions can Assumption 1 and a bounded coverage constant CC be guaranteed? Could the authors further clarify the trade-offs relative to OptGTM?

When Assumption 1 and bounded CC hold. Under truthful reporting, Assumption 1 holds with high probability (Lemma 4). Under misreporting, we do not have a general sufficient condition, and Example 2 shows that it can fail. For CC, a simple sufficient condition follows from Definition 5 in the linear case. Suppose the other agents' observations grow linearly in every direction, i.e., λmin⁡(Vt,−a)≥κt\lambda_{\min}(V_{t,-a}) \ge \kappa t for some κ>0\kappa > 0. Then

∣x∣Vt,−a−1∣x∣Vt−1\frac{|x|_{ V_{t,-a}^{-1} } }{|x|_{V_t^{-1}}}

$ \le \sqrt{\frac{\lambda + tL^2}{\kappa t}} \le \sqrt{\frac{\lambda + L^2}{\kappa}},$

and since αt,−a/αt=O(1)\alpha_{t,-a}/\alpha_t = O(1), this gives C=O((λ+L2)/κ)C = O\big(\sqrt{(\lambda + L^2)/\kappa}\big). The condition holds, for example, when other agents are selected in a constant fraction of rounds, and their features are diverse, i.e., have covariance bounded away from zero. Example 2 violates it because there λmin⁡(Vt,−a)\lambda_{\min}(V_{t,-a}) grows only as T\sqrt{T}. Empirically, the maximum value of CC remains small across NN and dd (Fig. 8, bottom row).

Trade-offs relative to OptGTM. OptGTM detects misreporting with agent-specific estimators built from the agent's own observations. COBRA uses leave-one-out estimators built from other agents' observations.

-Advantage of COBRA: a misreporting agent cannot influence the estimator used to test it, and the approach extends beyond linear rewards. Cost of COBRA: detection relies on peer coverage, which is reflected in CC. The structural conditions are similar: OptGTM's Theorem 5.2 relies on its Assumption 2, which plays the same role as our validity check (Step 5) (see Sec. B). Empirically, COBRA outperforms OptGTM even under truthful reporting (Fig. 3a).

Agents' gains from deviation. Our experiments measure the learner's regret under two adaptive deviation strategies: feature adaptation via finite-difference gradient ascent, and systematic over-reporting (Sec. 5). They do not directly measure each agent's utility. We agree that comparing a deviating agent's cumulative selections with those under truthful reporting would provide more direct evidence of incentive compatibility.

We thank the reviewer again for the careful review, which will help us improve the paper. We hope these additions address your concerns and strengthen your view of our work.

Reviewer_nRXwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The authors present an algorithm COBRA for contextual bandit problem where the agents may misreport the feature vectors corresponding to their arms. The algorithm is derived as a combination of leave-one-out mechanism (LOOM) over general UCB-style algorithm, and it enjoys regret guarantees as well as guarantee that being truthful is an approximate Nash equilibrium for agents. Finally, the authors performed multiple numerical experiments where they show the improved performance of their methods against standard contextual bandit methods as well as another method designed to handle strategic manipulations.

Critical strengths

I enjoy the method’s generality: an ability to use any reasonable UCB-inspired method as a black box for more general problem is definitely a strong part of the paper.

Critical weaknesses
  1. dTd\sqrt{T}-NE statement of Theorem 2: it does not seem to hold as stated because of Example 2 of Section B.1: for this example you exactly show that an unilateral deviation from the truthfulness have TT selections of the deviated arm, so truthfulness seems to be only TT-NE which is trivial. Do I understand that correctly, or maybe I misunderstand your example or statement?

  2. Theorems 4 and 5. There are two issues:

    a. They hold only if the agents’ strategies form NE, but, at the same time, the truthfulness is proven only to be dTd\sqrt{T} NE. Additionally, it is unclear why the set of NE is non-empty, it was never proven. So I believe the formulation of Theorems 3 and 4 should be changed.

    b. Assumption 1 has a lot of discussions in the Appendix but still seems to be very strong: essentially, UCB derived from arbitrary corrupted data should be a valid UCB for all arms. In particular, this assumption seems to be false on Example 2 of Section B.1, which is not discussed.

Questions for authors
  1. Why do you call your incentive compatibility condition “Bayesian”, do you have prior over types or anything like that? Also, Definition 3 seems to be imprecise as stated in the “i.e.” block: current wording “i.e., reporting the true arm features is the best response for agents.” reads like DSIC condition, where for your case, I believe, the wording should be “reporting the true arm features is the best response for agents if all other agents are truthful”. Also, there is only a definition of ε\varepsilon-NE but there is no definition of Bayesian NE in the text, which formally makes Definition 3 incomplete. Overall, I’d suggest either define a proper Bayesian setting or drop a word “Bayesian” completely.

  2. Regarding Figure 2: is the set Nt\mathcal{N}_t given by the environment (as defined in Section 2) or is it result of LOOM agent pruning, as it seems to be from Figure 2? In any case, I do not fully understand the message under that figure, I’d be happy to understand it better.

  3. Connected to the previous question: could you please write down the whole interaction protocol of your algorithm with environment? Especially, do agents observe the user features ctc_t?

  4. Expectation over which random variables is taken in Definition 2?

  5. Line 334: you mentioned “Eliminating agents who satisfy the LOOM condition defined in Eq. (2) from future rounds ensures agents report truthfully”, is it actually proven somewhere? Because it reads like a strong DSIC-style condition, which was never stated or proven.

Small additional remarks:

  1. I strongly believe that a section “Connection between LOOM and VCG mechanism” from Appendix should be in the main text since, if one read only the main text, the connection seems to be much stronger that it is in reality.

  2. Please introduce the example of linear bandits earlier, because for me it was very hard to go through Section 3 without any proper example in mind. You partially introduced it after Definition 5 but I believe that all earlier definitions will also benefit from it. Also, on line 287 the LaTeX is a bit malformed for the lower index.

  3. COBRA (TS) were never defined in the main text, although it is clear what does it mean, it would be good to have a proper definition before using it or at least a reference to Appendix.

  4. In the sketch of proof of Theorem 1 you mentioned “ellipsoid lemma” which seems to be applicable only in the linear setting.

  5. There is a multiple clash of notation on how agents are described: as n∈Ntn \in \mathcal{N}_t or as a∈Ata \in \mathcal{A}_t. I do understand that we have a bijection between these sets, but I would prefer to use only one set of notation or explicitly state that you are using this bijection with an abuse of notation: it appears, for example, in a definition of STS_T.

  6. Is there any hope to show stability of the algorithm: is it possible show that agents are incentivized to converge to any NE? Currently, as far as I understand, the only proven result is that truthfulness is dTd\sqrt{T}-NE but we don’t have any insights on any convergence properties if, for example, all agents play some specific type of policies.

6 comments
AuthorsOpenReview ↗

Response [1/6]

We thank the reviewer for a careful review. We appreciate the recognition of the method's generality, and in particular of the ability to use any reasonable UCB-inspired method as a black box for the more general problem. We have addressed each of the reviewer’s concerns as follows:

dTd\sqrt{T}-NE statement of Theorem 2: it does not seem to hold as stated because of Example 2 of Section B.1: for this example you exactly show that an unilateral deviation from the truthfulness have TT selections of the deviated arm, so truthfulness seems to be only TT-NE which is trivial. Do I understand that correctly, or maybe I misunderstand your example or statement?

Thank you for this careful check. Theorem 2 is stated for the setting in which all agents report truthfully, i.e., under the truthful profile σ⋆\boldsymbol{\sigma}^\star. Example 2, in contrast, allows misreporting: agent 22 reports xt,2=1x_{t,2} = 1 instead of its true feature xt,2⋆=1/4x^\star_{t,2} = 1/4. We included it in Sec. B.1 deliberately, as a failure case of LOOM in which the misreporting agent's direction is never covered by other agents' observations.

Under the truthful profile, Theorem 2 establishes two guarantees:

  1. Regret: RT(COBRA,σ⋆)=O~(dT)\mathfrak{R}_T(\text{COBRA}, \boldsymbol{\sigma}^\star) = \tilde{O}(d\sqrt{T}).

  2. No penalty for truthful agents: each truthful agent aa receives ST(a)≥ST⋆(a)−O~(dT)S_T(a) \ge S^\star_T(a) - \tilde{O}(d\sqrt{T}) selections (Eq. (15)), and with probability at least 1−δt,ax−δt,ay1 - \delta^x_{t,a} - \delta^y_{t,a}, no truthful agent is eliminated by LOOM (Theorem 1). In other words, a truthful agent loses at most O~(dT)\tilde{O}(d\sqrt{T}) selections due to estimation error.

Both guarantees remain valid, and Example 2 does not contradict them.

Gains from misreporting are not covered by Theorem 2. Since Theorem 2 considers only truthful agents, the ε\varepsilon-NE in its statement quantifies the selections a truthful agent may lose due to estimation error (Eq. (15)). It does not bound the gain of an agent that misreports while others remain truthful.

Guarantee under misreporting. Misreporting is covered by Theorem 4 (and Theorem 5 in the non-linear case). It controls a misreporting agent via LOOM (Lemma 6) and explicitly depends on the advantage constant CC (Definition 5), which quantifies peer coverage. In Example 2, C=Θ(T)C = \Theta(\sqrt{T}) (Sec. B.1), so this guarantee correctly reduces to the trivial O~(dT)\tilde{O}(dT). This is why we keep CC explicit: the guarantee degrades continuously as peer coverage deteriorates.

Theorems 4 and 5. There are two issues: a. They hold only if the agents’ strategies form NE, but, at the same time, the truthfulness is proven only to be dTd\sqrt{T} NE. Additionally, it is unclear why the set of NE is non-empty, it was never proven. So I believe the formulation of Theorems 3 and 4 should be changed. b. Assumption 1 has a lot of discussions in the Appendix but still seems to be very strong: essentially, UCB derived from arbitrary corrupted data should be a valid UCB for all arms. In particular, this assumption seems to be false on Example 2 of Section B.1, which is not discussed.

We address your points as follows (We read the reference to Theorems 3 and 4 as referring to Theorems 4 and 5):

(a) Existence of NE. We agree that the existence of an exact NE is not established. However, the proofs of Theorems 4 and 5 do not use the equilibrium property of σ\boldsymbol{\sigma}. The regret bound (Eqs. (18)–(21)) relies only on: (i) agents over-report, i.e., f(xt,a⋆)≤f(xt,a)f(x^\star_{t, a}) \le f(x_{t,a}); (ii) Assumption 1; (iii) Step 5 of COBRA; and (iv) Lemma 6, which follows from the fact that an agent still active has not triggered the LOOM condition. None of these requires σ\boldsymbol{\sigma} to be an equilibrium. Hence the bound O~(CdT+NT)\tilde{O}(Cd\sqrt{T} + \sqrt{NT}) (resp. O~(Cd~T+NT)\tilde{O}(C\tilde{d}\sqrt{T} + \sqrt{NT})) holds for every strategy profile satisfying (i)–(ii), and in particular for every NE whenever one exists. The statement is therefore not vacuous if NE(COBRA)\mathrm{NE}(\text{COBRA}) is empty. Moreover, the same argument (Eqs. (22)–(26)) bounds ∑t1(at≠at⋆)\sum_t \mathbb{1}(a_t \neq a_t^\star) under any such profile, so the truthful profile σ⋆\boldsymbol{\sigma}^\star is an O~(CdT+NT)\tilde{O}(Cd\sqrt{T} + \sqrt{NT})-NE against unilateral deviations under which Assumption 1 holds. The set of approximate NE is therefore non-empty, with the dependence on peer coverage made explicit through CC.

↓ ↓ ↓ Continued below ↓ ↓ ↓

AuthorsOpenReview ↗

Response [2/6]

(b) Assumption 1. We agree that Assumption 1 is strong, and its role is as follows. Once an agent misreports, its data contaminates every estimator that uses it: the full-data estimator and the leave-one-out estimators of the other agents. Lemma 2 shows these estimators become biased. Without a condition limiting the effect of this contamination, no sublinear regret guarantee is possible. Example 2 is exactly such a case: COBRA incurs regret 1/41/4 in every round, i.e., Θ(T)\Theta(T) in total. Assumption 1 isolates the condition under which optimism survives contamination, and Theorems 4 and 5 are conditional on it. Its violation in Example 2 is consistent with the Θ(T)\Theta(T) regret there. Under truthful reporting, Assumption 1 holds with high probability (Lemma 4). Replacing it with a verifiable condition, e.g., an explicit bound on the corruption or on peer coverage, is an open problem for future work.

Why do you call your incentive compatibility condition “Bayesian”, do you have prior over types or anything like that? Also, Definition 3 seems to be imprecise as stated in the “i.e.” block: current wording “i.e., reporting the true arm features is the best response for agents.” reads like DSIC condition, where for your case, I believe, the wording should be “reporting the true arm features is the best response for agents if all other agents are truthful”. Also, there is only a definition of ϵ\epsilon-NE but there is no definition of Bayesian NE in the text, which formally makes Definition 3 incomplete. Overall, I’d suggest either define a proper Bayesian setting or drop a word “Bayesian” completely.

Thank you for this comment. We agree with all three points.

Use of "Bayesian". Our intended meaning was that the utility E[ST(a)∣σ]\mathbb{E}[S_T(a) \mid \boldsymbol{\sigma}] in Definition 2 is an expectation over the randomly generated contexts ctc_t, which determine every agent's true features xt,a⋆=φ(ct,a)x^\star_{t,a} = \varphi(c_t, a), as well as over the reward noise and the algorithm's randomness. Each agent observes neither the other agents' features nor the learner's estimates (Sec. E), so it best-responds in expectation over this randomness. However, we did not specify a prior over types or define a Bayesian game, so the term "Bayesian" is not formally justified. The notion we actually establish is the ε\varepsilon-Nash equilibrium of Definition 2.

Wording of Definition 3. We agree that the "i.e." clause reads like dominant-strategy incentive compatibility. The intended condition is: reporting the true arm features is a best response for each agent when all other agents report truthfully, i.e., truthfulness is a Nash equilibrium σ⋆\boldsymbol{\sigma}^\star. Our guarantee is moreover approximate: truthfulness is an ε\varepsilon-NE in the sense of Definition 2, with ε\varepsilon given in Theorems 4 and 5 (depending explicitly on the advantage constant CC), rather than an exact best response.

Missing definition. We agree that Definition 3 refers to a Bayesian NE that is never defined. The precise statement of our incentive guarantee is in terms of the ε\varepsilon-NE of Definition 2 alone.

Regarding Figure 2: is the set Nt\mathcal{N}_t given by the environment (as defined in Section 2) or is it result of LOOM agent pruning, as it seems to be from Figure 2? In any case, I do not fully understand the message under that figure, I’d be happy to understand it better.

In COBRA, Nt\mathcal{N}_t is the result of LOOM pruning. The algorithm starts from the input set

N1\mathcal{N}_1,

and after each round sets Nt+1=Nt∖a\mathcal{N}_{t+1} = \mathcal{N}_t \setminus {a} for every agent aa satisfying the LOOM condition in Eq. (2) (Algorithm, Line 9). No other mechanism changes the active set in our algorithm or analysis. The phrase "set of active agents" in Sec. 2 refers to this set of agents not yet eliminated.

Message of Figure 2. The figure contrasts a standard contextual bandit algorithm with COBRA.

  • (a) Standard algorithm: In each round, the learner observes the context ctc_t, selects an arm ata_t using its estimates built from the history (xs,as,ys)s<t{(x_{s,a_s}, y_s)}_{s < t}, and observes a noisy reward. Agents' reports are taken at face value.

  • (b) COBRA: The estimation and arm-selection components of the underlying LOOM-compatible algorithm are unchanged (apart from the validity check in Step 5). The only addition is LOOM, applied as a post-processing step after each round. Using the same history, LOOM tests every active agent aa via Eq. (2) and outputs the active set Nt+1\mathcal{N}_{t+1} from which the next round's arm is selected.

↓ ↓ ↓ Continued below ↓ ↓ ↓

AuthorsOpenReview ↗

Response [3/6]

The key point is that the observed reward depends on the true features, yt=f(xt,at⋆)+εty_t = f(x^\star_{t,a_t}) + \varepsilon_t, while the learner sees only the reported features xt,atx_{t,a_t}. (The reward label in the figure should be read in this sense.) LOOM exploits this gap. For each agent aa, it compares a pessimistic estimate of the reward its reports promise,

LCBt,a(x)\mathrm{LCB}^{(x)}_{t,a},

built from the observations of all other agents so that agent aa cannot influence it, with an optimistic estimate of the reward actually realized when aa was selected,

UCBt,a(y)\mathrm{UCB}^{(y)}_{t,a}.

An agent whose promised reward exceeds its realized reward is removed from Nt+1\mathcal{N}_{t+1}. In short, COBRA turns any LOOM-compatible algorithm into one robust to over-reporting simply by restricting, round by round, the set of agents it selects from.

Connected to the previous question: could you please write down the whole interaction protocol of your algorithm with environment? Especially, do agents observe the user features ctc_t?

The full COBRA interaction protocol is as follows. COBRA takes as input the initial set of agents N1\mathcal{N}_1, a confidence parameter δ∈(0,1)\delta \in (0,1), and a regularization parameter λ>0\lambda > 0. For each round t=1,2,…t = 1, 2, \ldots:

  1. Context. The environment generates a context ctc_t. For each active agent

a∈Nta \in \mathcal{N}_t,

this determines its true context–arm feature vector xt,a⋆=φ(ct,a)x^\star_{t,a} = \varphi(c_t, a).

  1. Reports. Each active agent aa observes its own true features xt,a⋆x^\star_{t,a}, and hence the context ctc_t to the extent it enters xt,a⋆x^\star_{t,a}. It then reports

xt,a=σa(xt,a⋆,Ht,a)x_{t,a} = \sigma_a(x^\star_{t,a}, \mathcal{H}_{t,a}),

where

Ht,a\mathcal{H}_{t,a}

is its own history of past feedback (step 5). Agents do not observe other agents' reports, the learner's estimates ftf_t or ft,−af_{t,-a}, or the reward function ff (Sec. E).

  1. Selection. The learner observes ctc_t and the reports

xt,aa∈Nt{x_{t,a}}_{a \in \mathcal{N}_t},

but not the true features. It selects

at=arg⁡max⁡a∈NtUCBt(xt,a)a_t = \arg\max_{a \in \mathcal{N}_t} \mathrm{UCB}_t(x_{t,a})

(Line 4), subject to the validity check

UCBt(xt,at)≤UCBt,−at(xt,at)\mathrm{UCB}_t(x_{t,a_t}) \le \mathrm{UCB}_{t,-a_t}(x_{t,a_t})

(Lines 5–7).

  1. Reward. The environment generates yt=f(xt,at⋆)+εty_t = f(x^\star_{t,a_t}) + \varepsilon_t, which depends on the true features of the selected agent. The learner observes yty_t.

  2. Agent feedback. Each agent observes whether it was selected and, if so, its share of the realized reward. This is the only information agents receive.

  3. LOOM update. The learner adds (xt,at,yt)(x_{t,a_t}, y_t) to its observations, updates the full and leave-one-out estimators, and evaluates the LOOM condition

LCBt,a(x)>UCBt,a(y)\mathrm{LCB}^{(x)}_{t,a} > \mathrm{UCB}^{(y)}_{t,a}

(Eq. (2)) for every

a∈Nta \in \mathcal{N}_t.

Agents satisfying it are removed: Nt+1=Nt∖a\mathcal{N}_{t+1} = \mathcal{N}_t \setminus {a}. If Nt+1=∅\mathcal{N}_{t+1} = \emptyset, the interaction stops.

Each agent's utility is its expected number of selections, E[ST(a)∣σ]\mathbb{E}[S_T(a) \mid \boldsymbol{\sigma}].

On whether agents observe ctc_t. In our model, an agent's private information in round tt is its true feature vector xt,a⋆=φ(ct,a)x^\star_{t,a} = \varphi(c_t, a), which it knows before reporting. In this sense, it observes the user context as far as it determines its own features. Importantly, our guarantees do not depend on this choice. Strategies σa\sigma_a are arbitrary history-dependent maps, and Theorems 4 and 5 restrict reports only through over-reporting and Assumption 1. An agent that observes ctc_t fully is therefore the strongest adversary covered by our analysis, and the guarantees apply equally to agents with less information, such as the type I agent in our experiments, which adapts using only its binary selection signal.

Expectation over which random variables is taken in Definition 2?

In Definition 2, E[ST(a)∣σ]\mathbb{E}[S_T(a) \mid \boldsymbol{\sigma}] is the expectation over all randomness in the interaction for a fixed strategy profile σ\boldsymbol{\sigma}, namely:

  1. Contexts c1,…,cTc_1, \ldots, c_T, generated by the environment. They determine every agent's true features xt,a⋆=φ(ct,a)x^\star_{t,a} = \varphi(c_t, a), and hence also the oracle selection counts ST⋆(a)S^\star_T(a).

  2. Reward noise ε1,…,εT\varepsilon_1, \ldots, \varepsilon_T, which affects the learner's estimates, its arm selections, and the LOOM test.

  3. The learner's internal randomness, if any, e.g., the posterior sampling in COBRA (TS). COBRA (UCB) is deterministic given the history.

  4. The agents' internal randomness, if their strategies are randomized (e.g., the type II agents in our experiments draw their over-reporting factor at random).

The reward function ff (equivalently, θ⋆\theta_\star in the linear case) is fixed and unknown; it is not random, and our analysis is frequentist.

↓ ↓ ↓ Continued below ↓ ↓ ↓

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

Related papers

Discussion (0)

Sign in to comment.