Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908612395270144 |
|---|---|
| author | Ananthakrishnan, Nivasini Dagan, Yuval Yang, Kunhe |
| author_facet | Ananthakrishnan, Nivasini Dagan, Yuval Yang, Kunhe |
| contents | Motivated by the question of how a principal can maximize its utility in repeated interactions with a learning agent, we study repeated games between an principal and an agent employing a mean-based learning algorithm. Prior work has shown that computing or even approximating the global Stackelberg value in similar settings can require an exponential number of rounds in the size of the agent's action space, making it computationally intractable. In contrast, we shift focus to the computation of local Stackelberg equilibria and introduce an algorithm that, within the smoothed analysis framework, constitutes a Polynomial Time Approximation Scheme (PTAS) for finding an epsilon-approximate local Stackelberg equilibrium. Notably, the algorithm's runtime is polynomial in the size of the agent's action space yet exponential in (1/epsilon) - a dependency we prove to be unavoidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22471 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent Ananthakrishnan, Nivasini Dagan, Yuval Yang, Kunhe Computer Science and Game Theory Machine Learning Motivated by the question of how a principal can maximize its utility in repeated interactions with a learning agent, we study repeated games between an principal and an agent employing a mean-based learning algorithm. Prior work has shown that computing or even approximating the global Stackelberg value in similar settings can require an exponential number of rounds in the size of the agent's action space, making it computationally intractable. In contrast, we shift focus to the computation of local Stackelberg equilibria and introduce an algorithm that, within the smoothed analysis framework, constitutes a Polynomial Time Approximation Scheme (PTAS) for finding an epsilon-approximate local Stackelberg equilibrium. Notably, the algorithm's runtime is polynomial in the size of the agent's action space yet exponential in (1/epsilon) - a dependency we prove to be unavoidable. |
| title | Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2510.22471 |