- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studied the problem of strategyproofness for linear bandits with private contexts. They first design an algorithm based on the explore-then-commit framework and derive regret upper bounds. Then they derive the lower bound of for the problem. In order to capture the optimality of the theoretical results, they propose the CGT-UCB algorithm based on the optimism principle and get the problem-independent regret matching lower bound on and logarithmic problem-dependent regret. The authors also run experiments on both synthetic and real-world data to verify their theoretical findings.
Critical strengths
-
The work makes solid theoretical contributions. The work provides both upper bounds and lower bounds for the problem of linear bandits with private contexts. The bounds match on .
-
The paper has both synthetic and real-world datasets to run experiments to support their theoretical findings.
Critical weaknesses
The upper bounds and lower bounds have gaps on and .
Questions for authors
ETC and UCB frameworks are classical in the bandit area. What is the technique novelty in your upper bounds and lower bound proofs?
4 comments
Response to Reviewer uZsU (2/2)
d. Deriving the threshold from the two distinct costs of strategyproof learning in Page 31 and 32. A smaller threshold reduces the regret tolerated on exploitation rounds but demands more information before exploration can stop. A larger threshold has the opposite effect. Our analysis quantifies these costs through a term proportional to for unresolved rounds and a term involving for resolved rounds. Balancing them determines both the threshold schedule and its dependence on the type distribution and feature dimension, yielding the final bound.
Novelty of our upper-bound proof for CGT-UCB in Theorem 5. Proving problem-dependent bound again requires new techniques different from Theorem 4 and other existing methods. Our proof requires additional arguments connecting the minimum positive optimality gap , the confidence-gate thresholds, and the allocations produced by the strategyproof LP. We highlight two technical novelties.
-
Using the gap–threshold relationship to separate approximate exploitation from exact optimality in Pages 32 and 33. We divide the horizon into a prefix, during which some confidence gate thresholds exceed , and a subsequent period in which all thresholds fall below . We control the prefix using the analysis underlying Theorem 4. For the subsequent period, we exploit the fact that a regret certificate below the minimum positive gap implies zero regret. Thus, when all types pass the gate, their proposed actions are optimal, and the LP returns these proposals unchanged. This argument eliminates the exploitation contribution to regret after the prefix.
-
Connecting remaining positive regret to informative exploration through Lemma 4. Even after the confidence gate thresholds fall below , some gates may remain activated. Our key additional result, Lemma 4 shows that if the algorithm still incurs regret, at least one unresolved type must have substantial uncertainty about its proposed action. Constraint (10) ensures that the LP retains enough exploration of this action to reduce that uncertainty. Thus, we establish that the algorithm continues to learn and reduce regret, limiting how often positive regret can occur and yielding the problem-dependent regret guarantee.
We have added a discussion of these technical novelties in the last sentence on page 8 of the revised manuscript, referring readers to Appendix B.3.
Novelty of the lower-bound proof. Classical KL-based lower bounds capture the statistical difficulty of distinguishing alternative instances. Our lower-bound proof additionally quantifies the regret imposed by strategyproofness constraints, even on agents whose rewards are fully known. Our construction includes common agent types with identical contexts and known rewards, whose total arrival probability is 1/2. The remaining types each arrive with probability 1/(2K−2) and have small optimality gaps, making their optimal actions difficult to identify. Under the strategyproofness constraint, the common types collectively incur an additional regret cost proportional to K−1 times the expected number of pulls of the suboptimal informative action for a hard type. Without strategyproofness, the common types can incur zero regret because their rewards are known. This additional cost arises from preventing strategic misreporting and is not captured by the classical KL-based argument alone. Combining this strategyproofness-induced regret cost with the statistical difficulty quantified by KL divergence establishes our specific regret lower bound.
We thank you again for your careful review and hope that our responses have addressed your concerns. We would be happy to answer any further questions. If you find our responses satisfactory, we would appreciate your consideration of a higher score.
Thanks for the detailed response. I keep my positive score.
Response to Reviewer uZsU
We sincerely thank you for your thoughtful feedback and careful consideration of our responses.
Response to Reviewer uZsU (1/2)
Thank you for your careful review and thoughtful feedback. We address your comments point by point below.
1. Response to weakness.
Our upper bound in Theorem 4 matches the lower bound in Theorem 3 in its dependence on T, up to logarithmic factors in T. Matching the optimal dependence on the horizon while leaving gaps in other problem parameters also occurs in the bandit and reinforcement learning literature:
[1] Botao Hao, Tor Lattimore, and Mengdi Wang. High-Dimensional Sparse Linear Bandits. NeurIPS, 2020.
[2] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably Efficient Reinforcement Learning with Linear Function Approximation. COLT, 2020.
We have added these references in lines 412–414 on page 8.
Closing the remaining gap in the dependence on M and d is challenging because strategyproofness couples learning decisions across agent types. In standard bandits, exploration primarily addresses uncertainty about rewards. In our setting, uncertainty about one type can force the algorithm to assign suboptimal actions to other types, even when their rewards are already well understood, to prevent misreporting. Thus, the cost of learning depends on both the unknown reward directions and how incentives link different types. Algorithm 1 already introduces novel design components to address this interaction: the confidence gate prevents excessive exploration, while Constraint (10) preserves the exploration necessary for learning under strategyproofness. Together, these components carefully balance information acquisition and incentive compatibility, enabling us to achieve the optimal dependence on T up to logarithmic factors. We will further investigate how to close this gap through a sharper analysis of this interaction.
1. Response to question.
Novelty of our algorithm design. We would like to clarify that our proposed algorithm, CGT-UCB, differs fundamentally from ETC and UCB, both of which perform poorly in our setting. We introduce ETC only as a strategyproof bandit benchmark for analysis and comparison. Theorem 1 establishes its unfavorable regret bound, and the experimental results in Figures 2, 3, 4, and 7 further demonstrate its poor performance. Moreover, UCB is not strategyproof and can incur linear regret.
The algorithmic novelties are the confidence gate and its threshold in lines 7–10, together with LP (8)–(11), in Algorithm 1. The UCB action is only one component of CGT-UCB. In Phase I of Algorithm 1, types that do not pass the confidence gate receive UCB proposal actions, while types that pass the gate receive estimated-optimal proposal actions. These proposals are then passed to the LP, which outputs the final action-selection distribution. Our ablation study in Figures 5 and 6 further shows that removing either key component can compromise the established O(T2/3) regret guarantee.
Novelty of our upper-bound proof for CGT-UCB in Theorem 4. Our analysis must account for the interaction between the confidence gate and the strategyproof LP. This creates challenges specific to our problem and algorithm design that existing analyses do not directly address. We highlight four technical novelties.
a. Decomposing regret according to the collective state of the confidence gates in Page 30 and 31. Although each type has its own exploration or exploitation proposal, the strategyproofness constraints couple their final action allocations. To disentangle the coupled action allocations produced by the LP, we distinguish whether at least one type fails to pass the gate or all types pass, and analyze regret under these two events separately.
b. Converting gate activation into information acquisition after the LP adjustment by Lemma 3. The proposed actions may differ from those actually selected, so uncertainty associated with the proposed actions does not directly imply that the algorithm acquires the information needed to reduce it. We therefore establish the novel key result in Lemma 3, which bridges this gap through Constraint (10) and bounds gate activation in terms of the expected squared confidence width of the action actually selected. This argument controls regret when exploration is still needed to reduce uncertainty.
c. Establishing a regret bound when all types pass the gate in Pages 31 and 32. In this case, every type receives its estimated-optimal action, making the complete proposal strategyproof. We show that this proposal is feasible and achieves an LP objective value of zero, forcing the LP to return it unchanged. This property allows the gate certificates to translate directly into a regret bound, despite the cross-type constraints present in the LP.