Strategic Linear Contextual Bandits

Summary

The authors studied the problem of strategic agents who can modify their context in order to game the system under the linear contextual bandit framework. In this setting, each arm is a self-interested agent who wants to maximizes number of times it gets pulled by the learner. Prior work that did not explicitly consider the incentives of these arms suffers linear regret in the strategic setting. The authors proposed two mechanisms, first to deal with the case when the underlying parameter of the reward function is known to the learner in advance, and then when it is unknown to the learner. In either case, the proposed mechanism can incentivize the arms to be approximately truthful in reporting their true context to the learner. Furthermore, the authors provided strategic regret guarantee for each of the proposed mechanism that scales with $O(K^2 \sqrt{KT})$ when the latent parameter is known and $O(dK^2 \sqrt{KT})$ when the latent parameter is unknown.

Strengths

- The studied problem of strategic linear contextual bandits is interesting, and the setup is novel. - The paper is well-written and easy to follow. - The theoretical bounds are clearly listed, and justifications for the differences in regret compared to non-strategic setting is provided.

Weaknesses

- 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. - 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). - The paper relied on a key assumption that the arms do not under-report their value. While this assumption seems intuitive, the authors did discussed in Appendix C that there might be cases where under-reporting may make sense for the arms. - The authors did not provide experiments to support their theoretical findings.

Questions

- 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?

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors have addressed the limitations of their work.

Summary

This paper studies a variant of the linear contextual bandit problem, where each arm is an agent and can strategically misreport its feature vector to the learner. The authors propose the Optimistic Grim Trigger Mechanism (OptGTM) that incentivizes the agents to report their feature vectors truthfully while simultaneously minimizing the regret. The paper first shows that if an algorithm does not explicitly consider the incentives of the agents, it can incur a linear regret. Then, the authors propose GGTM for known $\theta^*$ and OptGTM for unknown $\theta^*$, which achieve sublinear regrets.

Strengths

1. The paper addresses an important and novel problem. The setting is innovative and has practical implications. 2. The algorithm design is simple and intuitive, and the theoretical analysis is rigorous. 3. The proposed OptGTM algorithm works for unknown $\theta^*$, which is an impressive result for me. 4. The readability is excellent (arguably the best among all the papers I reviewed). The problem setting is well-motivated, the model is clearly defined, the algorithm is easy to understand, and the flow of writing is logically coherent.

Weaknesses

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. 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. Update after rebuttal: The authors added some experiments.

Questions

See Weaknesses.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Limitations are adequately discussed in the paper.

Summary

This paper studies the strategic linear contextual bandit problem, where the agents can strategically change (report) their covariate to the principal. The authors propose an Optimistic Grim Trigger Mechanism (OptGTM) to encourage agents be truthful and achieve sublinear regret.

Strengths

The authors design a new framework and new theoretical guarantees to both achieve the Nash equilibrium and minimize regret.

Weaknesses

see my questions.

Questions

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? 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 $eta_i$. 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. Could the authors also comment on this point? 3. Could the authors conduct some numerical studies to support their theoretical findings?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

The paper introduces a new strategic variant to the stochastic contextual bandit, where the contexts of the arms are not public but are made available to the arms only. The arms may choose to strategize by misreporting their context to sway the decisions of the learning algorithms. The model is analyzed in two settings: known and unknown \theta^*. The primary results are algorithmic (truthful mechanism) contributions and corresponding regret bounds.

Strengths

The paper is exceptionally well-written and easy to understand and follow. The proofs are laid out well. The strategic variant of linear contextual bandit is very neat and interesting. I look forward to more results, hopefully with fewer assumptions or in more general settings.

Weaknesses

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_ T(i) . 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. 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?

Questions

Please refer to the above comments and reply accordingly. I am willing to engage in the rebuttal phase.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

NA