Persuading a Learning Agent

Tao Lin, Yiling Chen

Introduction

In classical economic theory, the "principal-agent" framework—encompassing everything from contract design to Bayesian persuasion—relies on the assumption of perfect rationality. In these models, the agent is an omniscient optimizer who perfectly understands the rules of the game and responds with mathematical precision to the principal's strategy. However, in real-world applications, agents often lack complete information about the environment or the underlying probabilities. Instead of calculating a best response from first principles, they learn how to act through repeated interactions and experience.

This paper investigates the consequences of replacing the perfectly rational agent with a learning agent. Specifically, the researchers ask: Does a principal gain or lose power when facing an agent who uses a learning algorithm? By bridging game theory and machine learning, the authors establish the theoretical bounds of the "Stackelberg value" ($U^*$)—the maximum utility a principal can achieve against a rational actor—within the context of adaptive behavior.

A Unified Framework for Principal-Agent Problems

To address this question across diverse economic scenarios, the authors propose a Generalized Principal-Agent Problem. This model abstracts the core mechanics of several distinct games:

  1. Stackelberg Games: Where a leader commits to a strategy and a follower responds.
  2. Contract Design: Where a principal offers a reward structure to incentivize specific effort from an agent.
  3. Bayesian Persuasion: Where a sender provides filtered information to influence a receiver's decision.

By stripping these problems down to a core interaction—a principal making a decision and an agent responding—the researchers can apply a unified mathematical analysis. They demonstrate that a learning agent’s behavior over time is equivalent to a "$\delta$-best response." In this state, the agent is "almost" optimal, with their margin of error ($\delta$) directly tied to their cumulative "regret" (the difference between their actual performance and the performance of the best possible fixed strategy).

The Stability of the Stackelberg Value

The study’s most significant contribution is the identification of "no-swap-regret" learning as a critical threshold. No-swap-regret is a sophisticated learning property where an agent does not regret failing to consistently swap one action for another.

The authors prove that if an agent employs a no-swap-regret algorithm, the principal’s utility is effectively capped at the classic Stackelberg value ($U^*$). Specifically, the principal is limited to $U^* + O(\text{SReg}(T)/T)$. As time ($T$) approaches infinity, the principal’s advantage over the classic theoretical limit vanishes. This finding provides a powerful justification for the continued use of $U^*$ as a benchmark in economic theory, even when the assumption of perfect rationality is relaxed.

Furthermore, this result extends to Bayesian persuasion. The paper provides the first proof that in information-sharing games, a sender cannot exploit a no-swap-regret receiver to gain more utility than they would against a rational receiver, despite the sender's inherent informational advantage.

Exploiting Simpler Learners

While sophisticated learners are resilient, simpler "no-regret" algorithms—such as Multiplicative Weights Update or EXP-3—are more vulnerable. These are categorized as "mean-based" learners because they respond primarily to historical averages of performance.

The researchers show that a clever principal can exploit mean-based agents to achieve utilities far exceeding $U^*$. By "tricking" the agent in early rounds to establish a specific historical record, the principal can manipulate the agent's future responses. Once the agent's history is sufficiently biased, the principal can switch strategies to reap a massive reward in later rounds. This suggests that the specific architecture of an agent's learning algorithm determines whether the principal can extract "excess" profit.

The Asymmetry of Learning Errors

The analysis reveals a fascinating mathematical asymmetry in how learning affects the principal’s bottom line. The researchers found that:

  • The Downside: The principal’s "worst-case" utility against a learner can drop significantly, decreasing by the square root of the regret ($O(\sqrt{\delta})$).
  • The Upside: The principal’s "best-case" utility against a no-swap-regret learner only increases linearly ($O(\delta)$).

This asymmetry occurs because learning algorithms are often randomized. A small error in the agent's probability of taking a specific action can lead to a disproportionately large "hit" to the principal’s utility, whereas the gains from the agent's sub-optimal play are more constrained.

Conclusion and Future Directions

This research establishes that the classic Stackelberg value is a robust predictor of outcomes when agents are sophisticated learners (no-swap-regret), but it also highlights a significant vulnerability in simpler learning models.

Future work remains to be done in environments where the agent possesses private information, such as secret costs or preferences. Previous studies suggest that private information makes agents much easier to exploit; characterizing the exact boundary where this exploitation becomes possible is a key next step. Additionally, moving toward "two-sided learning" models—where both the principal and the agent are learning simultaneously—would provide a more realistic, albeit more complex, view of modern economic interactions.

Summary updated

BibTeX
@inproceedings{lin2025persuading,
  author = {Tao Lin and Yiling Chen},
  title = {{Persuading a Learning Agent}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=LqTz13JS2P},
}
Figure