Research map / Multi-agent systems and games / Games and equilibria
Finite-Time Convergence Rates in Stochastic Stackelberg Games with Smooth Algorithmic Agents
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.
Theoretical study of finite-time convergence for decision-makers influencing stochastic learning agents in time-varying Stackelberg games, giving drift-to-noise tracking bounds and two epoch-based algorithms (repeated gradient and derivative-free) for performatively stable and Stackelberg equilibria.
Problem
Decision-makers must optimize against competing learning agents whose responses are stochastic and time-varying, with unknown agent objectives and environmental noise, so the equilibrium being tracked drifts over time.
Approach
Decouples agents' equilibrium tracking error into optimization error, drift, and noise terms for ρ-contracting stochastic agent algorithms, and uses epoch lengths chosen from this drift-to-noise analysis to control the decision-maker's induced drift, yielding finite-time rates for performatively stable and Stackelberg equilibria.
Key results
- Repeated gradient method converges to an approximate performatively stable equilibrium in O(log(1/ε) + σ²/ε) epochs.
- Derivative-free method converges to an approximate Stackelberg equilibrium with total iteration complexity O(d²/ε² log(1/ϵτ) + σa²/ϵτ) in the stated analysis.
- Stochastic gradient play in the low drift-to-noise regime can be accelerated with staged step-size reduction, lowering the achievable target error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a stage-based stochastic gradient play algorithm that reduces the step size across stages | Agent stochastic gradient play · Time-varying strongly monotone games in the low drift-to-noise regime | iteration complexity: T ≲ L2_a/µ2 log(2∥x0−x⋆0∥2/ε)+σ2_a/(µ2ε) | Helped |
| Use the derivative-free method to estimate the full gradient, including the effect of agents' responses | Decision-maker optimization · Stackelberg equilibrium | equilibrium optimality: O(d2/ε2) epochs | Helped |
| Use the derivative-free method instead of stochastic repeated gradient | Decision-maker optimization · Decision-maker sample efficiency | sample complexity: O(log(1/ε) + σ2/ε) epochs; O(d2/ε2) epochs | Hurt |
| Use stochastic repeated gradient while ignoring the agents' reaction in the gradient | Decision-maker optimization · Performatively stable equilibrium | epoch complexity: O(log(1/ε) + σ2/ε) | Helped |
| Increase the decision-maker's epoch length τ | RGM and DFM with stochastic gradient play agents · Convex quadratic game | equilibrium error | Helped |
Surprising findings
- Performatively stable equilibrium can be suboptimal relative to the Stackelberg equilibrium, so cheaper repeated gradient methods may converge to a worse point than the more expensive derivative-free method.
Limitations
- Assumes strong monotonicity of the induced agent game and strong convexity of the decision-maker's loss.
- Derivative-free method assumes convexity of the composed loss, which may fail in practice; local convergence only explored numerically.
- Parameters such as contraction rate and Lipschitz constants are often unavailable in practice.
Experimental setup
Metrics: equilibrium tracking error E||u_t - u*||^2 iteration complexity
Baselines: repeated gradient method (RGM) derivative-free method (DFM)
Builds on: performative prediction Cutler et al. 2023 stochastic optimization tracking single-point derivative-free optimization (Agarwal et al. 2010) stochastic gradient play
Closest papers by meaning
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.88)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.88)
- Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis (NeurIPS 2025 · similarity 0.87)
- Maximizing utility in multi-agent environments by anticipating the behavior of other learners (NeurIPS 2024 · similarity 0.87)
- Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium (AAAI 2025 · similarity 0.86)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.86)
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.