Strategic Linear Contextual Bandits

Dear Reviewer 8u5z, thank you for taking the time to review our paper and your helpful comments. We respond to your questions and comments below.

• The paper did not provide matching lower bound analysis on the strategic regret in the two settings: when $\theta^*$ is known in advance and when it is unknown in advance by the learner.

These are interesting questions for future work. In general, deriving lower bounds in strategic settings like ours is very challenging due to the intricate relationship between the learning algorithm and the equilibrium strategies that it induces. Note that we do inherit the $\Omega(d \sqrt{T})$ lower bound from the standard linear contextual bandit in the case where $\theta^*$ is unknown. However, as we conjecture in the discussion (Section 6), we believe the lower bound for the strategic problem to be $\Omega(d \sqrt{KT})$.

• The notation in the Introduction is somewhat confusing. The authors refer to the strategic agents as arms, and use learner to denote the (what would typically be called) bandit agent. Furthermore, in the main contributions, the regret bound for the setting where $\theta^*$ is unknown in advance uses $d$, which has not been introduced at this point (and only introduced in Section 3 later on).

Thanks for pointing this out. We made according modifications to the text addressing these things.

• The authors did not provide experiments to support their theoretical findings.

Based on your and the other reviewers' suggestion, we added experiments to the paper. You can find the experiments and the experimental details in the rebuttal pdf.

• Does manipulation budget for each arm matter in this setting? That is, does the current analysis change if the arms are only allowed to modify their true context by at most some (maybe unknown) values?

Thanks for the interesting question. Assuming a manipulation budget would not really change the setting. The main difference would be if we were to assume an extremely small manipulation budget of, e.g., constant size $C= O(1)$. For such small budgets, incentivizing the arms to be truthful is not necessary (after all, the amount of manipulation is almost insignificant). Instead, taking an adversarial (instead of strategic) approach would suffice, where we would slightly enlargen our confidence sets / increase exploration parameters to minimize regret. However, if the budget is large, then our approach, which does not rely on any assumption about the budget but instead bounds the effect of the arms' manipulation on our regret and the arms' utility, is necessary and much more effective. It is also worth mentioning that artificially assuming a manipulation budget can be unrealistic in practice and is one of the shortcomings of purely adversarial settings (see also reference [10] in the paper).

Dear Reviewer 7kzE, thank you for reviewing our paper. Your time is highly appreciated. We respond to your questions below.

1. The authors assumed that the inequality in Assumptions 1 and 2 holds. Could the authors change it to inequality after taking expectations over X? What if these assumptions fail?

We assume a possibly adversarial sequence of true contexts $x_{t,i}^*$. However, if we were to assume stochastically sampled contexts (which is a stronger assumption), we could indeed take an expectation over this distribution and our results still hold. When the assumption is violated and the arms can under-report their value, the problem appears to be intractable in some special cases (without other arguably stronger assumptions). We provided an example and discussion of this observation in Appendix C.

2. Some related works are missing. Typically, when agents are strategic and incentivized to change their features, their private types can confound the observed covariates $x_{t,i}$ and the noise etai. Consequently, applying the loss in equation (3) would result in a biased estimator for $\theta$. Relevant works include: Harris et al. Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses. Yu et al. Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments.

Thank you for pointing us to these papers. While this is a quite different perspective on strategic learning to ours, we agree that strategic regression and, in general, feature confounding based on types is quite relevant to our work. We added a brief discussion highlighting similarities and differences to Section 2 (Related Work) under 'Strategic Learning'.

3. Could the authors conduct some numerical studies to support their theoretical findings?

Following your and the other reviewers' suggestion, we have added experiments to the paper (see rebuttal.pdf). We believe thes experimental results are quite interesting and nicely illustrate the effectiveness of OptGTM and the necessity of a mechanism design approach in the strategic linear contextual bandit.

Dear Reviewer QjK5, thank you for your time and your review. We respond to your comments below.

1. There is no experimental evaluation in the paper. While I understand that many theoretical papers do not include experiments, it would be beneficial to see some empirical results to validate the theoretical claims.

Thanks for the suggestion. We added experiments to the paper, which you can find in the rebuttal pdf. In the experiments, we adopt the perspective of each strategic arm greedily updating its strategy to maximize its utility. The results support our theoretical results and the effectiveness and generality of the proposed mechanism design approach.

2. The assumption of the constant optimality gap (Lines 150-151) is unusual for regret minimization. Is there any reason for this assumption? It would be better if the authors could provide some rationale behind this assumption.

Without this assumption, the equilibrium behavior of the arms becomes difficult to analyze. For instance, consider the case where every time arm 1 is optimal it is only better than arm 2 by an amount $1/T$ (in terms of rewards). Then, roughly speaking, arm 2 only has to manipulate its contexts by a total amount $\leq 1 = T\times 1/T$ to "poach" all selections from arm 1. This tiny amount of manipulation by arm 2 is statistically undetectable so that we cannot prevent arm 1 losing all its utility when being truthful. In other words, we cannot promise arm 1 that truthfulness is a viable strategy (not much worse than untruthful reporting). This does not consequently mean that arm 1 will heavily manipulate its contexts in NE, but it does mean that we cannot use the truthful strategy as a "benchmark" when analyzing the NE (in the proofs of Theorem 4.2 and 5.2, we use that each arm's NE strategy must be a better response than the truthful strategy). We added a foonote to the main text explaining this and discuss this in an additional paragraph in the appendix.

Dear Reviewer XxQv, thank you for taking the time to read and review our paper. We respond to your questions below.

1. Regarding model description, my biggest concern is the assumption that the arms respond to the learning algorithm $M$ in Nash Equilibrium. Specifically, the definition of NE for arm i depends on future stochasticity (randomness in M and sampling noise or rewards) via $\eta$. This is quite weird. What does it mean for a real-life setting? To calculate NE, each arm should not only know $\theta^*$ but also the true contexts of other arms (in addition to future stochasticity). Is my understanding correct? I urge the authors to better explain this assumption (maybe in the appendix) with a real-life example and highlight the necessary information model.

Yes, you are correct in that the arms account for future stochasticity and contexts (in expectation). The reason for these assumptions is that we must ensure that the NE is well-defined. Without such knowledge, it is not clear what a best response for an arm is and we would instead need to, e.g., assume that the arms have a prior over the contexts etc. Even then, it can be unrealistic to assume that the arms reach an equilibrium (even in less complex models than ours). To this end, analyzing $\varepsilon$-NE can be helpful.

In the added experiments (see rebuttal.pdf), we also study the case where the arms optimize their strategy over time using gradient ascent, which is a fairly natural model of strategic adaptation. Importantly, in this case, we do not need to assume that the arms have any prior knowledge (neither $\theta^*$ nor anything else). Instead, the arms learn to adapt their strategies purely based on sequential interaction. In future work, it would be interesting to also theoretically analyze these types of situations (e.g., arms are no-regret learners). We additional explanations to the main text and added a thorough discussion of this to the appendix. Thank you for bringing this to our attention. In the appendix, we now also mention that the regret bounds of Theorem 4.2 and 5.2 directly extend to the case where the arms do not reach equilibrium but instead play any $O(\sqrt{KT})$-NE and $O(d\sqrt{KT})$-NE, respectively.

2. In the result of Theorem 4.2. Is it possible to give regret bound in terms of $d$, not $K$? From my understanding of bandit literature, the cost of manipulation may be calculated in terms of $d$. Can you comment if it is possible to calculate the cost of the mechanism in terms of $d$ instead of $K$?

In the setting of Theorem 4.2, the latent parameter $\theta^*$ is known to the learner in advance. As a result, the regret bound does not involve $d$. In general, any dependence on the dimension $d$ is only expected when we have to learn $\theta^*$. Unfortunately, we also cannot artificially swap the dependence on $K$ for a dependence on $d$, as the reason for the $K$ dependence is the fact that we need to incentivize all strategic arms to be approximately truthful, which automatically yields a dependence on the number of arms.

We are not really sure in what part of the literature the cost of manipulation is calculated in terms of $d$. In the literature on linear contextual bandits with adversarial corruptions, the manipulation is typically captured by an additive or multiplicative term $C$. Sometimes $C$ is defined as the total amount of context manipulation so that it is somewhat related to $d$ (however, $C$ is not expressed as a function of $d$). Please let us know if you have any other questions or if we misunderstood your question.