Strategy-Aware Contextual Bandits

Keegan Harris, Chara Podimata, Steven WuTSRML @ NeurIPS 2022 · OpenReview

TL;DR

This paper introduces the "strategy-aware contextual bandit" problem, where decision-makers must choose actions based on contexts that strategic agents can manipulate. They show that achieving optimal performance (no regret) is possible with two actions but becomes impossible with three or more actions, highlighting a critical limitation in multi-action strategic decision-making.

What Problem Does This Paper Address?

Imagine an online store deciding which discount to offer a customer. The customer, knowing their past purchase history (their "context"), might strategically "pretend" to be a different type of shopper to get a better deal. This is the core of the problem: how can an algorithm (the decision-maker) make optimal choices when the data it receives (the context) is intentionally manipulated by strategic agents (the customers) trying to game the system?

Existing work on "strategic classification" often assumes agents have only two choices (e.g., positive/negative) and that the decision-maker sees the "true" outcome after the fact. This paper tackles a more realistic scenario:

  1. Multiple Actions: The decision-maker can choose from n different actions (e.g., different discount levels, loan types).
  2. Bandit Feedback: The decision-maker only observes the reward for the action they actually took, not what would have happened with other actions.

This setting is crucial for applications like personalized recommendations, loan applications, and dynamic pricing, where agents have incentives to influence outcomes.

Methods

The authors formalize this as a strategy-aware contextual bandit problem. The key elements are:

  • Decision Maker (DM): Learns a policy $\pi: X \to A$ to map contexts to actions.
  • Strategic Agent (Γt): Has a private type $x_t$ and chooses a context $x$ to maximize their reward, subject to a constraint on how much they can alter their context from their private type ($\|x - x_t\| \le \delta$).
  • Bandit Feedback: The DM observes the reward $r_p(a)$ for the chosen action $a$, but not the agent's reward $r_A(a)$ or the true context $x_t$.
  • Goal: Minimize strategic regret, which is the difference between the cumulative reward of the DM's policy and the cumulative reward of the best possible fixed policy in hindsight, assuming agents were truthful.

They propose an "explore-first" algorithm for the two-action case. This algorithm first spends a phase exploring by taking arbitrary actions to gather data, then uses this data to estimate the underlying parameters, and finally acts greedily based on these estimates for the remaining time.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and introduces a formal model rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Two-Action Sweet Spot: For the specific case of only two actions, it's possible to design algorithms that achieve "no strategic regret." This means the decision-maker can learn to effectively account for agent manipulation and perform as well as if agents were always truthful.
  • The Curse of Three (or More) Actions: When the number of actions increases to three or more, achieving sublinear strategic regret becomes impossible in many scenarios. This is a significant theoretical barrier, suggesting that simple linear policies or even more complex ones might fail to adapt to strategic behavior in multi-action settings.
  • Strategic Classification vs. Contextual Bandits: The paper highlights a crucial distinction. Standard strategic classification often assumes full feedback (knowing the true label), which makes learning easier. The addition of bandit feedback (only knowing the reward of the chosen action) significantly complicates the learning problem, especially in multi-action settings.
  • Impossibility Results: The paper derives strong impossibility results for multi-class strategic classification, showing that even with linearly separable data before strategic manipulation, perfect classification under strategic responses can be impossible with three or more classes.

Key Results

  • Two Actions: An algorithm is presented that achieves $O(T^{2/3})$ strategic regret for the two-action setting, meaning it performs nearly optimally in the long run.
  • Three or More Actions: The paper proves that for $n \ge 3$ actions, there exist scenarios where no algorithm can achieve sublinear strategic regret. This implies that the decision-maker's performance will degrade linearly with time $T$ in the worst case.
  • Multi-Class Strategic Classification: Impossibility results are shown for scenarios with three or more classes, even when agents' private types are linearly separable.

Limitations and Future Work

  • Linear Policies: The impossibility results for $n \ge 3$ actions are shown for linear policies. The authors hypothesize that these results might extend to more expressive policy classes and suggest this as a future research direction.
  • Lower Bounds: While an upper bound of $O(T^{2/3})$ is achieved for the two-action setting, it's unclear if this is tight. Deriving a matching lower bound for the two-action case would be valuable.
  • Stackelberg Regret: Given the difficulty of achieving strategic regret in multi-action settings, the authors suggest exploring alternative benchmarks like Stackelberg regret, which might be more achievable.
  • Generalizing Impossibility: Identifying precise conditions under which the impossibility results for $n \ge 3$ actions hold would be a significant contribution.

Summary updated

Abstract

Algorithmic tools are often used to make decisions about people in high-stakes domains. In the presence of such automated decision making, there is incentive for strategic agents to modify their input to the algorithm in order to receive a more desirable outcome. While previous work on strategic classification attempts to capture this phenomenon, these models fail to take into account the multiple actions a decision maker usually has at their disposal, and the fact that they often have access only to bandit feedback. Indeed, in standard strategic classification, the decision maker's action is to either assign a positive or a negative prediction to the agent, and they are assumed to have access to the agent's true label after the fact. In contrast, we study a setting where the decision maker has access to multiple actions but only can see the outcome of the action they assign. We formalize this setting as a contextual bandit problem, in which a decision maker must take actions based on a sequence of strategically modified contexts. We provide an algorithm with no regret compared to the best fixed policy in hindsight if the agents' were truthful when revealing their contexts (i.e., no-strategic-regret) for the two action setting, and prove that sublinear strategic regret is generally not possible for settings in which the number of actions is greater than two. Along the way, we obtain impossibility results for multi-class strategic classification which may be of independent interest.
BibTeX
@inproceedings{harris2022strategy,
  author = {Keegan Harris and Chara Podimata and Steven Wu},
  title = {{Strategy-Aware Contextual Bandits}},
  booktitle = {TSRML @ NeurIPS},
  year = {2022},
  url = {https://openreview.net/forum?id=A5I7icgiCKx},
}
Figure