Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent
Nivasini Ananthakrishnan, Yuval Dagan, Kunhe Yang · 2025
Read Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent by Nivasini Ananthakrishnan, Yuval Dagan, Kunhe Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22471.txt.
Introduction
Nivasini Ananthakrishnan and two co-authors study how a leader can do well in repeated dealings with an agent that learns from experience. Computing the best global strategy against such a learner can take a huge number of rounds, so exact planning is out of reach. The team shifts the goal to local equilibria, where no small change of plan helps the leader.
Within a smoothed analysis setting, they give an approximation scheme that runs in time polynomial in the agent action count. One cost grows fast as the allowed error shrinks, and they prove that cost cannot be avoided. The trade off makes local planning practical.
Catalog record
| CREATOR | Nivasini Ananthakrishnan, Yuval Dagan, Kunhe Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22471
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent Nivasini Ananthakrishnan, Yuval Dagan, Kunhe Yang Abstract 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 by Brown et al. 2024b 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 ε \varepsilon -approximate local Stackelberg equilibrium. Notably, the algorithm’s runtime is polynomial in the size of the agent’s action space yet exponential in ( 1 / ε ) (1/\varepsilon) —a dependency we prove to be unavoidable. 1 Introduction In repeated games, agents often have incomplete information about the game and resort to using a learning algorithm to optimize their utility over time. We consider a repeated game between a strategic player, referred to as the principal , and a player who follows a learning algorithm, referred to as the agent . When the principal anticipates the learning algorithm used by the agent, how should she adjust her strategy to maximize her utility over time? The answer depends on both the information available to the principal and the specific learning dynamics of the agent. In this paper, we study the setting where the principal has no knowledge of the agent’s utility function, and the agent employs a mean-based learning algorithm. A mean-based learner is a learning algorithm that selects its strategy based on the empirical distribution of the principal’s past actions. Specifically, at each round, the learner plays an approximate best response to the time-averaged history of the principal’s play. This class includes fundamental algorithms such as Fictitious Play, Follow the Regularized/Perturbed Leader, and Multiplicative Weights Update. In particular, we focus on Fictitious Play, where the agent exactly best responds to the empirical distribution of the principal’s actions up to the current round. Given that the agent is a mean-based learner, what should the principal aim to achieve? A natural goal is to devise a strategy that maximizes her cumulative utility over time, among all possible strategies. This objective has been considered in Mechanism Design ( Braverman et al. 2018 ; Cai et al. 2023 ; Rubinstein and Zhao 2024 ) , Contract Design ( Guruganesh et al. 2024 ) , Information Design ( Lin and Chen 2024 ) , and general games ( Deng et al. 2019 ; Mansour et al. 2022 ; Brown et al. 2024b ) . However, even when the principal has full knowledge of the agent’s utility function, computing the optimal long-term strategy is NP-hard in general games ( Assos et al. 2024 ; Assos et al. 2025 ) . An alternative benchmark is the Stackelberg equilibrium of the one-shot game. If the principal knows the agent’s utility function, she can compute a Stackelberg strategy in polynomial time and play it repeatedly. Since a mean-based learner best responds to the empirical distribution of the principal’s past actions, this ensures that the agent selects the Stackelberg best response in each round, thereby approximately yielding the one-shot Stackelberg value to the principal in each round. When the principal does not have access to the agent’s utility function, she could approximate the Stackelberg equilibrium using a best-response oracle —an oracle that, given a mixed strategy of the principal, returns the agent’s best response Letchford et al. 2009 ; Peng et al. 2019 ; Blum et al. 2014 . If the only information available about the agent comes from observing its decisions over time, the principal may attempt to influence the agent’s learning process to induce best responses. This approach has been analyzed in various settings Haghtalab et al. 2022 ; Haghtalab et al. 2024 . However, for the fundamental class of mean-based learners, reducing the problem to learning via a best-response oracle introduces an exponential overhead. That is due to the fact that mean-based learners remember the whole history of play, hence they cannot be easily manipulated to produce best responses. In fact, Brown et al. 2024b established that approximating the Stackelberg equilibrium in this setting requires exponential time. 1.1 Our contribution The impossibility result of Brown et al. 2024b raises the question of what can be learned from interactions with a mean-based learning agent when the optimizer lacks direct access to the agent’s utility function. A key challenge arises from the fact that mean-based learners are slow to forget—they adjust their strategy based on the cumulative history of play rather than responding to individual queries. As a result, querying their best response to widely varying mixed strategies is infeasible, since shifting the empirical distribution of past plays requires many rounds. This makes traditional approaches based on best-response oracles impractical. Given these constraints, the optimizer can only infer information from how the agent gradually adapts its strategy over time. Consequently, the optimizer’s best option is to perform a local search by making small adjustments to its historical play—modifying the empirical distribution of past actions incrementally—and observing the agent’s response. Through this process, the optimizer can progressively optimize its utility. A natural target for such an optimization process is an approximate local equilibrium , where the optimizer cannot significantly improve its utility through small deviations in its historical play. In this work, we study the problem of efficiently finding an \epsilon -approximate local equilibrium, leveraging the structure of mean-based learning dynamics to design an algorithm for this setting. We present a PTAS: an algorithm whose iteration complexity is exponential in 1/\epsilon but polynomial in the size of the game, with each iteration running in polynomial time. Furthermore, we prove that this exponential dependence on 1/\epsilon is unavoidable. To achieve our runtime guarantees, we impose a few natural assumptions to prevent adversarial instances and to ensures that the vectors in the learner’s utility matrix are in general position. Technical Contributions. Optimizing against a mean-based learner introduces several challenges: \bullet Local versus Global Queries: Prior work reduced the problem of finding an approximate Stackelberg equilibrium via interactions with a learner to a query-based approach: given an optimizer’s mixed strategy x\in\Delta(\mathcal{A}) , one can query the learner’s (exact or approximate) best response y\in\mathrm{BR}(x) . However, for mean-based learners, queries are expensive if the mixed strategies differ substantially. To query \mathrm{BR}(x) and then \mathrm{BR}(x^{\prime}) when x and x^{\prime} are far apart, the optimizer must play enough rounds to adjust the average history from one strategy to the other. Our key insight is to design an algorithm that only makes local changes—ensuring that successive queries remain close—thus circumventing the high cost associated with large shifts in the history. \bullet Discontinuities in the Objective: One might naturally attempt to apply standard local-search methods to our problem since our algorithm operates via local steps. However, the optimization target is not globally continuous: the learner’s best response can change abruptly as the optimizer’s mixed strategy crosses the boundaries between different regions of \Delta(\mathcal{A}) .