Research map / Bandits and online learning / Online convex optimization and games
Learning to Steer Learners in Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that an optimizer cannot in general learn to steer a general no-regret learner to Stackelberg equilibrium without knowing its payoffs, and gives payoff-recovery-based steering algorithms that succeed for ascent learners (n=2) and stochastic mirror ascent learners with known regularizer.
Problem
Steering a no-regret learner to a Stackelberg equilibrium in repeated bimatrix games when the optimizer does not know the learner's payoff matrix.
Approach
Impossibility result for general no-regret learners with unknown payoffs; reduces steering to recovering the learner's payoff structure (facets / payoff matrix class up to equivalence), using pessimism for robustness and explore-then-commit; shows recovery is feasible for ascent and known mirror-ascent learners.
Key results
- Theorem: for general no-regret learners, there exist two games with the same optimizer payoff A such that any optimizer algorithm suffers linear Stackelberg regret on one of them against some no-regret learner.
- Pessimistic facet steering yields Stackelberg regret O(sqrt(T f(T))) against f-no-regret learners, shown to be essentially optimal via a lower bound.
- For n=2 ascent learners, a binary-search explore-then-commit algorithm achieves regret O(f(T)/d + dT - log d), e.g. O(T^{(1+alpha)/2}) for f=T^alpha.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Attempt to steer without additional assumptions on the learner beyond no-regret | Any optimizer algorithm against a general no-regret learner · Repeated bimatrix games with unknown learner payoff | Stackelberg regret: o(T) on G_1; cT on G_2 | Hurt |
| Use known d_1-pessimistic facets separated from other facets by d_2 | Pessimistic-facet steering · Repeated bimatrix games with an f-no-regret learner | Stackelberg regret: O(f(T)/d_2 + d_1T) | Helped |
| Estimate the learner payoff class to error ε = O(g(T)/T) and commit to a pessimistic solution | Payoff-class estimation and pessimistic commitment · Repeated bimatrix games with an f-no-regret learner | Stackelberg regret: O(√(Tf(T)) + g(T)) | Helped |
| Use binary search and pessimistic facet estimation | Binary-search ascent steering · Repeated 2×2 games with an ascent f-no-regret learner | Stackelberg regret: O(f(T)/d + dT - log d) | Helped |
| Estimate the learner payoff class from stochastic mirror-ascent updates with known regularizer and step sizes | Mirror-ascent payoff-class estimation · Repeated bimatrix games with stochastic mirror ascent | Stackelberg regret: O(√(Tf(T)) + g(T) + (T/g(T))^2) | Helped |
| Choose g(T) = √(Tf(T)) in mirror-ascent payoff-class estimation | Mirror-ascent payoff-class estimation · Repeated bimatrix games with stochastic mirror ascent | Stackelberg regret: O(√(Tf(T))) | Helped |
| Use a payoff-class estimate instead of exact recovery of the learner payoff matrix | Pessimistic steering · Repeated bimatrix games | Stackelberg regret: O(√(Tf(T)) + g(T)) | Helped |
Surprising findings
- Against general no-regret learners, no optimizer algorithm can achieve sublinear Stackelberg regret on all game instances, even when it knows the learner is no-regret and the game is two-player.
Limitations
- Positive results for general m, n are open; the n=2 ascent algorithm relies on the two-action setting.
- Assumes the optimizer knows the learner's update rule and regularizer for the mirror ascent case.
- Steering analysis assumes the inducibility gap is nonzero (non-degenerate games).
Experimental setup
Metrics: Stackelberg regret learner regret
Builds on: Stackelberg steering of no-regret learners with known payoffs inducibility gap stochastic mirror ascent
Closest papers by meaning
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.88)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.88)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.88)
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.88)
- Adaptively Perturbed Mirror Descent for Learning in Games (ICML 2024 · similarity 0.87)
- Maximizing utility in multi-agent environments by anticipating the behavior of other learners (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.