- 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 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 () Nash equilibrium, and they state sublinear regret bounds under truthful reporting and, under an additional assumption and an advantage constant , 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 -NE half of the proof (Sec. C.2.1, Eqs. 16–17) bounds a deviating agent's number of selections by reusing Eq. (14), , which was derived under from the confidence ellipsoid for . 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 ". Concretely, in Example 2 of Sec. B.1 (, , , , agent 2 reports ): since for , agent 2 has exactly twice the UCB of agent 1 whenever , which holds with high probability, and is therefore always selected; , so and LOOM never fires. Step 5 never excludes agent 2: at , , and for it compares , which tends to , with ; the former stays below the latter for the parameters used in the paper (e.g., ). Finally, the ridge estimate converges to , exactly the bias predicted by Lemma 2. Since agent 2 is suboptimal in every round, it is selected at most times under truthful reporting, so the deviation gain is against the claimed , 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 , which Theorem 2 claims not to.
2. No sublinear strategic-regret guarantee is actually established (Theorems 4–5). The regret bound carries the advantage constant of Definition 5, which the main text presents as a constant. By Eq. (27), , so whenever agent 's features are orthogonal to those of the other agents, e.g., in the -armed special case with canonical features and truthful reporting, where Assumption 1 holds with high probability. Hence and the bound becomes the trivial ; Example 2 of Sec. B.1 exhibits the same growth. The only general bound offered, , 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, 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 (a downward bias according to the authors' own Case 2 argument) to remain optimistic at the inflated reported features . Under persistent misreporting, this bias term does not vanish with while the width does (in Example 2 it converges to ), so this is a condition on the outcome of the interaction rather than on the instance; in Example 2 it fails: while . 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 contains the deviator's corrupted data (again in Example 2, ). 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
Response [2/2]
No sublinear strategic-regret guarantee is actually established (Theorems 4–5). The regret bound carries the advantage constant of Definition 5, which the main text presents as a constant. By Eq. (27), , so whenever agent's features are orthogonal to those of the other agents, e.g., in the -armed special case with canonical features and truthful reporting, where Assumption 1 holds with high probability. Hence and the bound becomes the trivial ; Example 2 of Sec. B.1 exhibits the same growth. The only general bound offered, , 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, 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 (a downward bias according to the authors' own Case 2 argument) to remain optimistic at the inflated reported features . Under persistent misreporting, this bias term does not vanish with while the width does (in Example 2 it converges to ), so this is a condition on the outcome of the interaction rather than on the instance; in Example 2 it fails: while . ...
Theorems 4–5 are conditional bounds. The reviewer is correct that is not a constant in general. When an agent's features are orthogonal to those of all other agents (e.g., the -armed case with canonical features), . In that case, and in Example 2, and the bound is vacuous. Theorems 4 and 5 therefore give sublinear regret only when and Assumption 1 holds. The unconditional sublinear guarantee in our paper is the truthful-reporting bound of Theorem 2, which does not involve . 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 . In Fig. 7f–7h, the maximum value of increases only during roughly the first 300 rounds and then remains flat until . It is about 4.0–4.2 across and about 4.2–5.5 across . growth would roughly quadruple it over this range. The increase across curves reflects the dimension , not . 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 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 ( while
).
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, contains the deviator's corrupted data, as the reviewer's computation in Example 2 shows (
).
In summary, we prove sublinear regret under truthful reporting and a regret bound under misreporting that depends on peer coverage through 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.
Response [1/2]
We thank the reviewer for the careful review. We appreciate the recognition of four aspects of the work:
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 σ⋆. Example 2, in contrast, allows misreporting: agent 2 reports xt,2=1 instead of its true feature xt,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:
Regret: RT(COBRA,σ⋆)=O~(dT).
No penalty for truthful agents: each truthful agent a receives ST(a)≥ST⋆(a)−O~(dT) selections (Eq. (15)), and with probability at least 1−δt,ax−δt,ay no truthful agent is eliminated by LOOM (Theorem 1). In other words, a truthful agent loses at most O~(dT) 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 ε-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 C (Definition 5), which quantifies peer coverage. In Example 2, C=Θ(T) (Sec. B.1), so this guarantee correctly reduces to the trivial O~(dT). This is why we keep C explicit: the guarantee degrades continuously as peer coverage deteriorates.
↓ ↓ ↓ Continued below ↓ ↓ ↓