acceptodds
Under review as a conference paper at ICLR 2027

Strategyproof algorithms in linear contextual bandits with private contexts

Abstract

Contextual bandits have broad applications, including clinical trials and LLM routing. In a clinical trial, a doctor uses patients’ private information, such as symptoms and family history, to assign treatments and learn from observed outcomes. To improve overall patient welfare, the doctor may assign seemingly suboptimal treatments to some patients to reduce uncertainty, whereas individual patients seek to maximize their immediate outcomes. This misalignment may incentivize patients’ misreporting to avoid exploration, substantially biasing treatment-effect estimates and reducing long-term patient welfare. It is therefore important for bandit algorithms to be strategyproof, ensuring patients cannot benefit from misreporting their contexts. In this paper, we conduct a comprehensive study of strategyproof algorithms for linear bandits with private contexts. We first establish complementary gaps of classical strategyproof bandit algorithms. Explore-then-commit and truthful Thompson sampling either lack problem-dependent regret guarantees or can incur linear problem-independent regret, while non-strategyproof algorithms such as LinUCB generally suffer linear regret in strategic settings. Secondly, we establish a novel minimax regret lower bound of for strategyproof bandit algorithms, revealing the fundamental challenge posed by strategic misreporting. Motivated by this, we propose Confidence-Gated Truthful UCB (CGT-UCB), which first employs a confidence gate to construct a proposal policy that adaptively switches between greedy and optimistic policies for agents with different contexts. This mechanism avoids the excessive exploration induced by the standard optimism-in-the-face-of-uncertainty principle. CGT-UCB then feeds the proposal policy into a specially designed linear programming problem that enforces strategyproofness while balancing exploration and exploitation under strategyproofness. CGT-UCB simultaneously achieves \(O(T^2/3)\) problem-independent regret and \(O(polylog T)\) problem-dependent regret. Experiments on synthetic and real-world datasets support our theoretical findings and demonstrate the practical effectiveness of CGT-UCB.

Primary area:
reinforcement learning
Keywords:
Contextual linear bandit, strategyproof algorithm, game theory

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_uZsUOpenReview ↗
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 Ω(T2/3)\Omega(T^{2/3}) 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 TT and logarithmic problem-dependent regret. The authors also run experiments on both synthetic and real-world data to verify their theoretical findings.

Critical strengths
  1. 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 TT.

  2. 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 MM and dd.

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
AuthorsOpenReview ↗

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 TT, up to logarithmic factors in TT. 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 MM and dd 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 TT 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)\widetilde O(T^{2/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.

AuthorsOpenReview ↗

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 1/ϵT21/\epsilon_T^2 for unresolved rounds and a term involving ∑tϵt∑mβm\sum_t\epsilon_t\sum_m\sqrt{\beta_m} for resolved rounds. Balancing them determines both the t−1/3t^{-1/3} threshold schedule and its dependence on the type distribution and feature dimension, yielding the final O~(T2/3)\widetilde O(T^{2/3}) 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 Δmin⁡\Delta_{\min}, the confidence-gate thresholds, and the allocations produced by the strategyproof LP. We highlight two technical novelties.

  1. 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 Δmin⁡\Delta_{\min}, and a subsequent period in which all thresholds fall below Δmin⁡\Delta_{\min}. 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.

  2. Connecting remaining positive regret to informative exploration through Lemma 4. Even after the confidence gate thresholds fall below Δmin⁡\Delta_{\min}, 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.

AuthorsOpenReview ↗

Response to Reviewer uZsU

We sincerely thank you for your thoughtful feedback and careful consideration of our responses.

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

This paper studies linear contextual bandits where agents may misreport their private contexts to receive better actions. The authors examine existing strategyproof algorithms and show that they struggle to achieve good regret guarantees in both worst-case and problem-dependent settings. They establish an Ω(T2/3)\Omega(T^{2/3}) minimax regret lower bound and propose CGT-UCB, which uses confidence-based exploration and a linear program to maintain strategyproofness. The main result is that CGT-UCB achieves O~(T2/3)\widetilde O(T^{2/3}) worst-case regret while also obtaining polylogarithmic problem-dependent regret. Experiments on synthetic data and the Warfarin dataset show lower regret than the baselines considered in the paper.

Critical strengths

One of the main strengths of this paper is the regret lower bound, which gives a better understanding of how strategyproofness makes learning more difficult in contextual bandits. I also find the proposed CGT-UCB algorithm interesting, especially how it combines confidence-based exploration with a linear program to ensure strategyproofness. More importantly, the algorithm achieves both sublinear worst-case regret and polylogarithmic problem-dependent regret, something the existing approaches considered in the paper do not achieve together. The experimental results are also encouraging and provide additional support for the theoretical findings.

Critical weaknesses

My main concern is with the lower bound in Theorem 3. In Appendix A.3, the authors choose K=min⁡(M,d+1)K=\min(M,d+1), but it is not clear to me whether the same lower bound holds for an arbitrary fixed KK. The proof also works with a parameter in Rd+1\mathbb{R}^{d+1}, while the theorem is stated for dimension dd. I think these points need some clarification, given that the lower bound is one of the main results. I also have a small question about the strategyproofness assumption. The paper assumes agents make decisions based on the public estimate rather than the true expected rewards. If an agent gets the same expected reward from telling the truth and misreporting, and misreporting has no cost, would the regret analysis still hold if the agent chooses to misreport? I may be misunderstanding something here, so I would appreciate it if the authors could correct me if I am wrong.

I also think the experimental section could be improved. The ETC algorithm in Equation (19) appears to differ from the version described in Appendix D, where the parameter estimate is frozen after exploration. It is unclear which version was used in the experiments and whether this difference affects the comparison. I would also like to see an ablation study to better understand the individual contributions of the confidence gate and the LP's exploration-retention constraint, while preserving strategyproofness. These are the main points I would like the authors to address.

Questions for authors

Based on the Weaknesses I described I have some questions for Authors:

  1. In Theorem 3, the authors choose K=min⁡(M,d+1)K=\min(M,d+1) in the lower-bound construction. Does the same lower bound hold for an arbitrary fixed KK? Also, the proof uses a parameter in Rd+1\mathbb{R}^{d+1}, while the theorem is stated for dimension dd. Could the authors clarify these points?

  2. The strategyproofness condition is based on the public estimate rather than the true expected rewards. If an agent gets the same expected reward from truthful reporting and misreporting, and misreporting has no cost, would the regret analysis still hold if the agent chooses to misreport?

  3. In Equation (19), ETC uses the current parameter estimate after exploration, while Appendix D mentions using a frozen estimate. Could the authors clarify which version was used in the experiments and whether this difference affects the comparison?

  4. Could the authors include an ablation study to show how much of the improvement comes from the confidence gate and how much comes from the LP constraints? I think this would help better understand the contribution of each component.

4 comments
AuthorsOpenReview ↗

Response to Reviewer ML6Z (1/2)

Thank you for your careful review and thoughtful feedback. We address your comments point by point below and have revised the manuscript accordingly.

1. Response to Question 1

Our lower bound holds for arbitrary K>1K>1. Our original analysis actually considers 2≤K≤min⁡M,d+12\leq K\leq\min{M,d+1}, as stated in lines 1213–1214 on page 23 of the original manuscript, regardless of whether we use K≤min⁡M,d+1K\leq\min{M,d+1} for an instance with total dimension d+1d+1 or K≤min⁡M,dK\leq\min{M,d} for an instance with total dimension dd.

In the original proof, we consider K≤min⁡M,d+1K\leq\min{M,d+1} because, for clarity of presentation, we use dd to denote the number of unknown parameter coordinates of θ\theta, alongside one known coordinate, giving d+1d+1 dimensions in total. Replacing dd with d−1d-1 throughout the proof therefore yields d−1d-1 unknown coordinates and one known coordinate, giving dd dimensions in total and recovering the result stated in Theorem 3. To avoid confusion, we have revised the construction to use K≤min⁡M,dK\leq\min{M,d} actions, one known parameter coordinate, and d−1d-1 unknown coordinates, consistently with Theorem 3 in the revised manuscript.

Furthermore, the analysis can be readily extended to K>min⁡M,dK>\min{M,d}. To construct an instance for this case, we use the same feature construction as in the preceding proof for the first min⁡M,d\min{M,d} actions. Any additional actions duplicate the type–action features of the existing actions. Aggregating the allocation probabilities and observation counts of duplicate actions reduces the analysis to the case with min⁡M,d\min{M,d} effective actions. The preceding lower-bound argument then applies directly to this construction. We have added the details of this extension on pages 28–29 of Appendix A.3 in the revised manuscript.

2. Response to Question 2

Public estimate. In the Bayesian setting, the public estimate is the posterior mean under the prior shared by the agents and the system, so it exactly represents the agents’ expected reward when they have the same information. In the frequentist setting, assuming that agents evaluate rewards using the public estimate is a reasonable modeling choice, as it provides a transparent, statistically grounded estimation rule that agents can also adopt when forming their own estimates.

We can extend our model to accommodate differences between agents’ personal reward estimates and the public estimate. Specifically, suppose that each agent’s personal reward estimate f^t(m,a)\hat f_t(m,a) differs from the public reward estimate by at most ε/2\varepsilon/2:

sup⁡m,a∣f^t(m,a)−⟨ϕ(m,a),θ^t⟩∣≤ε/2.\sup_{m,a}|\hat f_t(m,a)-\langle\phi(m,a),\hat\theta_t\rangle|\leq\varepsilon/2.

Under this assumption, the inequality in Definition 1 implies ε\varepsilon-strategyproofness with respect to agents’ personal estimates:

EA∼qmt[f^t(m,A)]+ε/2≥EA∼qmt[⟨ϕ(m,A),θ^t⟩]≥EA∼qjt[⟨ϕ(m,A),θ^t⟩]≥EA∼qjt[f^t(m,A)]−ε/2,E_{A\sim q_m^t}[\hat f_t(m,A)]+\varepsilon/2\geq E_{A\sim q_m^t}[\langle\phi(m,A),\hat\theta_t\rangle]\geq E_{A\sim q_j^t}[\langle\phi(m,A),\hat\theta_t\rangle]\geq E_{A\sim q_j^t}[\hat f_t(m,A)]-\varepsilon/2,

where we denote qmt=π(m∣Ft)q_m^t=\pi(m\mid\mathcal F_t).

Thus, an agent can improve their personally estimated expected reward by at most ε\varepsilon through misreporting. Approximate strategyproofness is an established relaxation in mechanism design, studied, for example, by Dütting et al. (2019) and Kleine Buening et al. (2024). In these works, it is also commonly assumed that agents report truthfully when they can gain at most ε\varepsilon by misreporting.

Misreporting when truthful reporting yields the same reward. If an agent receives the same expected reward from truthful reporting and misreporting, and misreporting is costless, the regret may incur additional error term if the agent chooses to misreport. In this case, truthful reporting is called a weakly dominant strategy. However, it is commonly accepted in the literature to assume that agents report truthfully when misreporting offers no gain, since designing mechanisms that make truthful reporting weakly dominant is already challenging in many problems (Roughgarden et al., 2017).

Under an even more relaxed behavioral assumption, some works assume that agents do not misreport when the gain from misreporting is at most ε\varepsilon, as discussed above for works on approximate strategyproofness.

Moreover, we can add a small positive margin to the right-hand side of the inequality in Definition 1 and Constraint (9) of the LP to make truthful reporting a strictly dominant strategy, provided that the LP remains feasible, so that agents achieve the highest expected reward only by reporting truthfully:

(qmt−qjt)⊤Φmθ^t≥δ,∀m≠j.(q_m^t-q_j^t)^\top\Phi_m\hat\theta_t\geq\delta,\quad\forall m\neq j.

If the modified Constraint (9) preserves LP feasibility, our regret analysis applies similarly. This allows us to design an algorithm that discourages misreporting as strictly as feasibility permits.

We have also added these discussions after Definition 1 on page 4, referring readers to Appendix E on pages 43–44 in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer ML6Z (2/2)

3. Response to Question 3

We should retain the version of ETC defined in Eq. (19), since only this version satisfies the strategyproofness requirement in Definition 1. Traditional ETC methods that use a frozen estimate are not strategyproof under this definition: agents evaluate rewards using the current public estimate at each round tt, which may differ from the estimate frozen at T0T_0 after exploration ends. Consequently, allocations based on the frozen estimate may create incentives to misreport.

In the experimental results in the revised manuscript, we now consistently use the version of ETC with the current public estimate in Figures 2, 3, 4, 7. The results remain similar, and our experimental conclusions continue to hold.

4. Response to Question 4

Following your suggestion, we have added an ablation study in Figures 5 and 6 in the revised manuscript to evaluate our two key algorithmic components: the confidence gate and Constraint (10). Crucially, removing either component can compromise the O~(T2/3)\widetilde O(T^{2/3}) guarantee established for CGT-UCB in Theorem 4 and may lead to linear regret.

We consider a problem instance with d=M=K=3d=M=K=3, θT∗=(1,0.9,−T−1/2)\theta_T^*=(1,0.9,-T^{-1/2}), β=(0.55,0.40,0.05)\boldsymbol{\beta}=(0.55,0.40,0.05), and ϕ(m,a)=em\phi(m,a)=\mathbf{e}_m if a=ma=m, and 0\mathbf{0} otherwise. Each type’s diagonal action therefore provides the only information about its corresponding parameter coordinate.

Figure 5 shows cumulative regret on a fixed instance with T=20000T=20000. CGT-UCB incurs substantially lower regret than both ablation variants, whose regret appears to grow linearly. Figure 6 reports terminal regret normalized by T2/3T^{2/3} across varying horizons TT. Both ablations incur substantially higher regret than CGT-UCB, and their normalized regret increases rapidly with TT. In contrast, the normalized regret of CGT-UCB decreases as TT increases. Figures 5 and 6 suggest that removing either component can compromise the O~(T2/3)\widetilde O(T^{2/3}) guarantee established for CGT-UCB in Theorem 4, supporting the importance of both designs.

We explain why the ablations fail in this instance as follows. In this instance, without the gate, OFUL can continue proposing action 3 for the infrequent type 3, whose diagonal reward mean is −T−1/2-T^{-1/2}. The strategyproofness Constraint 9 can then impose prolonged exploration costs on other types, even after their optimal actions have been accurately identified. The confidence gate limits this unnecessary exploration. Without Constraint (10), the LP can eliminate an informative action and prevent an incorrect estimate from being corrected. In particular, an initially negative estimate of the second coordinate of θT∗\theta_T^* can cause the LP without Constraint (10) to assign zero probability to action 2 for type 2, preventing further observations of that coordinate. This estimate remains nonpositive throughout the horizon in 223 of 1000 runs without Constraint (10), compared with none of the CGT-UCB runs. Constraint (10) preserves exploration when an OFUL action is proposed, allowing CGT-UCB to correct such errors. Together, these results illustrate the complementary roles of the gate and retention constraint in supporting the sublinear problem-independent regret guarantee.

The corresponding discussion of the experimental results has been added on pages 9–10 and 43 of the revised manuscript.

We also provide more extensive experimental results in Figure 3 to further assess the consistency of empirical regret scaling with our minimax regret lower bound and the upper bounds for the different algorithms.

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.

Thank you for the detailed response and for revising the manuscript. I appreciate the clarifications on the lower-bound construction and the strategyproofness assumptions. The updated ETC comparison and the new ablation study address my questions about the experiments. My final recommendation is 3 (weak acceptance).

AuthorsOpenReview ↗

Response to Reviewer ML6Z

We are pleased that our clarifications have addressed your concerns. We sincerely thank you for your thoughtful feedback and careful consideration of our responses.

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

The author(s) studies linear contextual bandits with private contexts where agents may misreport their true types to improve the immediate rewards in a non-repeated interaction model. The authors analyzes existing strategyproof algorithms, establishes a minimax regret lower bound, and proposes Confidence-Gated Truthful UCB (CGT-UCB) based algorithm. The proposed algorithm considers adaptive exploration with an LP-based strategyproofness constraint and achieves sublinear problem-independent and problem-dependent regret.

Critical strengths
  1. The proposed problem is well motivated at the intersection of online learning and mechanism design.
  2. The paper is well written with clear research gap. The proposed algorithm CGT-UCB is interesting, combining confidence-gated exploration with an LP-based mechanism.
  3. Theoretical results are supported by experiments.
Critical weaknesses
  1. If I understood correctly, the problem setting relies on known type-action feature vectors and a specific strategic model. The practical implications under model misspecification and more realistic incentives remain unclear.

  2. The experimental evaluation is limited, with a short horizon and few synthetic configurations. The empirical evidence for the claimed regret scaling is therefore not conclusive.

Questions for authors
  1. Please see the weakness noted above.

  2. Could you please discuss in detail how did you get the equations 8-11 in the LP formulations. Also discuss the computational scalability of solving the LP at every round.

  3. How CGT-UCB will perform when the type distribution is unknown or changes over time?

  4. Is it possible to generalize CGT-UCB for non-linear reward model?

4 comments
AuthorsOpenReview ↗

Response to Reviewer KMuN (1/3)

Thank you for your careful review and thoughtful feedback. We address your comments point by point below and have revised the manuscript accordingly.

1. Response to Weakness 1

Known type–action feature vectors. We have sought to minimize the prior knowledge required by our framework. For example, Appendix B.6 extends our method from known to unknown agent-type arrival distributions. However, we still require some basic assumptions, such as knowing the type–action feature vectors. This is a standard assumption in the bandit literature, including the following works:

[1] Wagenmaker et al. Experimental Design for Regret Minimization in Linear Bandits. AISTATS, 2021.

[2] Fiez et al. Sequential Experimental Design for Transductive Linear Bandits. NeurIPS, 2019.

[3] Tirinzoni et al. An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits. NeurIPS, 2020.

We have added citations to these works in the first paragraph of Section 2. This assumption is practically well motivated since the system can predefine profile categories and feature encodings. For example, in medical trials, a hospital can specify patient profiles using age and genotype categories, as in our Warfarin experiment, and construct the corresponding type–action features in advance. Knowing these type–action features does not require knowing an arriving patient’s true profile, which remains private in our model.

Extending our framework to unknown type–action feature mappings could involve discretizing the continuous space of possible context vectors. Controlling approximation errors and analyzing regret over this space pose significant additional challenges beyond our scope.

Model misspecification. Our framework can extend to misspecified linear reward models. Following standard assumptions for misspecified linear reward models, suppose that the potentially nonlinear expected reward function f(m,a)f(m,a) admits a linear approximation satisfying sup⁡m,a∣f(m,a)−⟨θ,ϕ(m,a)⟩∣≤ε\sup_{m,a}|f(m,a)-\langle\theta,\phi(m,a)\rangle|\leq\varepsilon. Let f^t(m,a)\hat f_t(m,a) denote the agents’ estimate of f(m,a)f(m,a). Suppose that sup⁡m,a∣f^t(m,a)−⟨θ^t,ϕ(m,a)⟩∣≤ε\sup_{m,a}|\hat f_t(m,a)-\langle\hat\theta_t,\phi(m,a)\rangle|\leq\varepsilon for every round tt, so that the system’s public linear estimate uniformly approximates the agents’ estimate. Let qmt=π(m∣Ft)q_m^t=\pi(m\mid\mathcal F_t). Strategyproofness with respect to the public linear estimate then implies, for all types m,jm,j,

EA∼qmt[f^t(m,A)]+ε≥EA∼qmt[⟨ϕ(m,A),θ^t⟩]≥EA∼qjt[⟨ϕ(m,A),θ^t⟩].\mathbb E_{A\sim q_m^t}[\hat f_t(m,A)]+\varepsilon \geq \mathbb E_{A\sim q_m^t}[\langle\phi(m,A),\hat\theta_t\rangle] \geq \mathbb E_{A\sim q_j^t}[\langle\phi(m,A),\hat\theta_t\rangle].

EA∼qjt[⟨ϕ(m,A),θ^t⟩]≥EA∼qjt[f^t(m,A)]−ε.\mathbb E_{A\sim q_j^t}[\langle\phi(m,A),\hat\theta_t\rangle] \geq \mathbb E_{A\sim q_j^t}[\hat f_t(m,A)]-\varepsilon.

This establishes 2ε2\varepsilon-approximate strategyproofness with respect to the agents’ reward estimates: misreporting improves estimated expected reward by at most 2ε2\varepsilon. Approximate strategyproofness is a common design objective in mechanism design. Under the common assumption that agents do not misreport for gains of at most 2ε2\varepsilon, truthful reporting is preserved (e.g., Kleine Buening et al. (2024)). Replacing the exploitation and exploration actions in lines 4 and 5 of Algorithm 1 with misspecification-aware counterparts, while retaining the LP constraints, yields an algorithm satisfying 2ε2\varepsilon-approximate strategyproofness for misspecified linear reward models. We have added this discussion of the extension to the conclusion on page 10 of the revised manuscript.

Realistic incentive We would like to clarify that the conflict between agents’ immediate rewards and the system’s long-term learning objective reflects a realistic and important incentive in applications where the system learns through interactions with many agents. The medical setting in the introduction and Figure 1 is one example. Similar incentives arise in recommendation and service-allocation systems, where users may modify reported preferences or requirements to obtain a more desirable allocation.

This tension has also been extensively studied in the incentivized-exploration literature in settings different from our strategic misreporting setting. Representative works include Mansour et al. (2020), Sellke and Slivkins (2021), and Hu et al. (2022).

We agree that our work does not cover all strategic incentive scenarios. Our goal is to comprehensively understand and effectively address the important setting where myopic agents strategically report private contexts to maximize immediate expected rewards. Accommodating arbitrary reporting behavior would include adversarial misreporting, and methods guarding against such worst-case behavior may be overly conservative for agents following our incentive structure. Allowing arbitrary behavior would also obscure the structure induced by these incentives, which is central to our algorithm design and theoretical analysis.

AuthorsOpenReview ↗

Response to Reviewer KMuN (2/3)

2. Response to Weakness 2

We have substantially expanded the experimental evaluation and extended the time horizons on pages 9–10 of the revised manuscript. Specifically, we have added new experimental results in Figures 3, 5, and 6 of the revised manuscript. In the new Figure 3 of the revised manuscript, we vary the horizon TT from 20002000 to 10510^5 and report terminal regret normalized by T2/3T^{2/3} on the instance underlying our minimax regret lower bound for Theorem 3. CGT-UCB achieves the lowest regret among all methods at every tested horizon. For CGT-UCB and ETC, the T2/3T^{2/3}-normalized regret varies only slightly around a constant as TT increases, suggesting T2/3T^{2/3} regret scaling over the tested range, consistent with our upper bounds in Theorems 1 and 4. In contrast, the normalized regret increases overall for TTS and R-TTS, particularly for R-TTS, suggesting faster regret growth over this range. This is consistent with the possibility of linear worst-case regret established for R-TTS in Theorem 2. Together, these results provide empirical support for our Ω(T2/3)\Omega(T^{2/3}) regret lower bound.

We additionally include an ablation study in Figures 5 and 6 to evaluate our two key algorithmic components: the confidence gate and Constraint (10). The confidence gate prevents excessive exploration under the strategyproofness constraints, while constraint (10) ensures that the LP retains the necessary exploration prescribed by the OFUL proposal actions. Figure 5 shows cumulative regret on a fixed instance with T=20000T=20000. CGT-UCB incurs substantially lower regret than both ablation variants, whose regret appears to grow linearly. Figure 6 reports terminal regret normalized by T2/3T^{2/3} across varying horizons TT. Both ablations incur substantially higher regret than CGT-UCB, and their normalized regret increases rapidly with TT. In contrast, the normalized regret of CGT-UCB decreases as TT increases. Figures 5 and 6 suggest that removing either component can compromise the O~(T2/3)\widetilde O(T^{2/3}) guarantee established for CGT-UCB in Theorem 4, supporting the importance of both designs.

3. Response to Question 2

Design of the LP. The design of LP (8)–(11) is introduced in the fourth paragraph of Section 4 on page 6 of the manuscript. To clarify the design further, we provide a more detailed explanation below and have also included it in Appendix B.1 on page 29.

In our LP, Constraint (9) enforces the strategyproofness condition in Definition 1, ensuring that our algorithm is strategyproof. Constraint (11) ensures that each output action-selection rule is a valid probability distribution.

Objective (8) and Constraint (10) both aim to preserve the exploration and exploitation decisions in the confidence-gated proposal distribution. Objective (8) encourages this by minimizing the distance between CGT-UCB’s action-selection distribution and the proposal distribution. Constraint (10) provides a stronger guarantee by imposing a hard requirement that sufficient exploration be retained. It is therefore essential for establishing the regret upper bounds in Theorems 4 and 5 while satisfying the strategyproofness and probability constraints in (9) and (11).

Specifically, in lines 7–10 of Algorithm 1, the confidence gate proposes exploration or exploitation actions for different agent types. These proposed actions are then passed to the LP. Without Constraint (10), the LP solution may not preserve enough exploration to guarantee sublinear regret. With Constraint (10), we establish the key intermediate result in Lemma 3, which relates confidence-gate activation to the expected squared confidence width under the action-selection distribution actually executed by CGT-UCB, allowing CGT-UCB to control the uncertainty encountered during learning. Also, the new ablation results in Figure 5 on page 9 of the revised manuscript suggest that removing Constraint (10) can compromise the O~(T2/3)\widetilde O(T^{2/3}) guarantee established for CGT-UCB.

Scalability. A standard dense interior-point method can solve the LP with a conservative per-round complexity of O~((MK+M2)3.5)\widetilde{O}((MK+M^2)^{3.5}). For problem instances with large MM and KK, we can directly construct a feasible solution of LP (8)–(11) at low computational cost, as described in the proof of Lemma 1 in Appendix B.2 on page 29. All theoretical results for Algorithm 1 continue to hold with this feasible solution, since our proofs do not require an exact optimal solution to the LP. Therefore, our method can efficiently scale to large problem instances. We have added this discussion before Lemma 1 on page 7 and Appendix B.2 of the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer KMuN (3/3)

4. Response to Question 3

Our algorithm already accommodates an unknown type distribution, as discussed in lines 395–398 and detailed in Algorithm 3 in Appendix B.3 of the original manuscript. Theorem 10 establishes the corresponding problem-independent frequentist regret bound, at the cost of an additional factor of 1/βmin⁡1/\beta_{\min}, where βmin⁡\beta_{\min} is a lower bound on the type arrival probabilities. Thus, when the type distribution is unknown, we additionally assume that βmin⁡\beta_{\min} is bounded below by a positive constant to preserve the same problem-independent regret order as in the known-distribution setting.

We also observe that Algorithm 3 and Theorem 10 apply directly to time-varying type distributions. Following your suggestion, we have expanded the discussion in lines 402–405 of the revised manuscript to cover both unknown and time-varying type distributions. For completeness, we have also added Theorem 11 in Appendix B.6, which establishes the corresponding problem-dependent regret upper bound.

5. Response to Question 4: Nonlinear reward models

Yes, we can extend our framework to nonlinear reward models. First, for models that can be represented exactly as polynomials in the unknown parameters, our framework applies directly by incorporating the corresponding powers and products into a lifted parameter vector. More generally, most commonly used nonlinear reward models can be approximated by polynomials with bounded approximation errors. The same construction then yields a misspecified linear reward model. For example, consider θ=(θ(1),θ(2))\theta=(\theta^{(1)},\theta^{(2)}) and a quadratic approximation fθ(m,a)=c0(m,a)+c1(m,a)θ(1)+c2(m,a)θ(2)+c11(m,a)(θ(1))2+c12(m,a)θ(1)θ(2)+c22(m,a)(θ(2))2+bθ(m,a),f_\theta(m,a)=c_0(m,a)+c_1(m,a)\theta^{(1)}+c_2(m,a)\theta^{(2)}+c_{11}(m,a)(\theta^{(1)})^2+c_{12}(m,a)\theta^{(1)}\theta^{(2)}+c_{22}(m,a)(\theta^{(2)})^2+b_\theta(m,a), where sup⁡m,a∣bθ(m,a)∣≤ϵ.\sup_{m,a}|b_\theta(m,a)|\leq\epsilon. Define the lifted parameter vector θ~=(1,θ(1),θ(2),(θ(1))2,θ(1)θ(2),(θ(2))2)⊤\widetilde\theta=(1,\theta^{(1)},\theta^{(2)},(\theta^{(1)})^2,\theta^{(1)}\theta^{(2)},(\theta^{(2)})^2)^\top and the known feature vector ϕ~(m,a)=(c0(m,a),c1(m,a),c2(m,a),c11(m,a),c12(m,a),c22(m,a))⊤.\widetilde\phi(m,a)=(c_0(m,a),c_1(m,a),c_2(m,a),c_{11}(m,a),c_{12}(m,a),c_{22}(m,a))^\top. Then the linear reward model in Section 2 becomes fθ(m,a)=⟨θ~,ϕ~(m,a)⟩+bθ(m,a)f_\theta(m,a)=\langle\widetilde\theta,\widetilde\phi(m,a)\rangle+b_\theta(m,a), yielding an ϵ\epsilon-misspecified linear reward model in a finite-dimensional lifted parameter space. The same construction applies to higher-degree polynomial approximations by including the corresponding powers and products of the coordinates of θ\theta. This construction can then be handled by the extension to misspecified reward models described in Response 1. We have also added this discussion to the conclusion on page 10 of the revised manuscript.

6. Response to typos

We have corrected the typos and formatting issues in Figure 1 of the revised manuscript. Please let us know if you have any further comments on the figure.

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.

I would like to thank the authors for the detailed rebuttal. Yes, my concerns are resolved and I would like to keep my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.