Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis¶

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper introduces AC-SMFG, a single-loop actor-critic algorithm for Stackelberg Mean Field Games (SMFGs)—a hierarchical setting with one leader and an infinite follower population. It is the first SMFG algorithm with non-asymptotic (finite-time, finite-sample) convergence guarantees, achieving rate Õ(k⁻¹/²). Simulations on economic environments show faster convergence and better policy quality than prior nested-loop and MARL baselines.

Problem¶

Existing algorithms for SMFGs and related major-minor MFGs suffer from three compounding limitations: (1) restrictive leader-follower independence assumptions that effectively decouple the hierarchy, (2) nested-loop structures that require inner-loop convergence before each outer update, making them sample-inefficient and impractical, and (3) only asymptotic convergence guarantees, giving no finite-time performance bounds.

Method¶

AC-SMFG formulates the SMFG as a bi-level optimization: the leader maximizes its discounted reward anticipating the mean field equilibrium (MFE) response of followers. Rather than solving the inner MFG to convergence at each step, the algorithm maintains simultaneous iterates for the leader policy (ω), follower policy (θ), mean field estimate (µ̂), and value functions (Vl, Vf), updating all in a single loop with multi-time-scale step sizes (ζk ≤ ξk ≤ αk ≤ βk ∝ k⁻¹/²). Two Markovian sample trajectories are used per iteration—one tracking discounted occupancy, one tracking the stationary distribution. Policy gradient updates use tabular softmax parameterization (extensible to neural networks). Convergence is established via a coupled Lyapunov function under a novel gradient alignment assumption: the partial gradient ∇ωJl(ϕω, µ⋆(ϕω)) makes an acute angle with the full Stackelberg gradient ∇ωΦ(ϕω), which is weaker than prior independence assumptions. A key technical innovation handles the lower-level non-convexity using the Polyak-Łojasiewicz (PL) condition satisfied by the follower's regularized objective.

Key Contributions¶

First non-asymptotic SMFG algorithm: AC-SMFG converges to a stationary point of the Stackelberg objective at rate Õ(k⁻¹/²), the same sample complexity.
Single-loop design: eliminates nested inner-loop convergence requirements of prior work (Cui et al. 2024, Dayanıklı & Laurière 2024).
Rate improvement over bi-level baselines: surpasses Hong et al. 2023 (Õ(k⁻²/⁵)) for bi-level optimization with lower-level strong convexity, despite the SMFG lower-level having only a PL condition (weaker than strong convexity).
Gradient alignment assumption: a strictly weaker condition than leader-follower independence; permits leader reward to depend on the mean field and follower reward/transitions to depend on the leader's action.
PL-based bi-level analysis: novel error decomposition enabling tight bounds under non-convex lower-level problems; claimed to be of independent interest for general bi-level optimization.
Function approximation extension: neural network policies + Gaussian mean field parameterization demonstrated on continuous state/action Equilibrium Pricing.

Results¶

Convergence rate: Õ(k⁻¹/²) to a stationary point of Φ(ϕ); two samples per iteration gives identical sample complexity.
Market Entrance: AC-SMFG converges significantly faster than OneByOne, CuiKoeppl, and ADAGE (PPO-based MARL) for both leader and follower rewards (Figure 2a).
Shop Positioning: significantly faster leader convergence vs. all baselines; slightly slower follower convergence than CuiKoeppl due to limited leader influence (Figure 2b), but still substantially better than ADAGE for both agents.
Equilibrium Pricing: significantly better leader and follower rewards than existing SMFG algorithms; competitive with ADAGE (neural network baseline) when using Gaussian mean field approximation, with a small gap attributed to distributional mismatch (Figure 2c, Figure 4).
All experiments bootstrapped over 30 runs with 5% confidence intervals.

Limitations¶

Requires sufficiently large entropy regularization weight τ for Assumption 4 (contraction) to hold; does not find equilibria of the original unregularized problem—an open problem even for standard MFGs.
Convergence is to a stationary point (not global optimum), because the Stackelberg objective Φ is a composite function through µ⋆ and does not satisfy gradient domination.
Homogeneity assumption over followers is embedded in the mean field formulation; inapplicable when follower heterogeneity matters.
MFG approximates the N-agent game asymptotically; approximation error is non-negligible for small follower populations, where ABM may be more appropriate.
Gaussian mean field parameterization for continuous spaces is a simplification that introduces distributional mismatch errors.

Relevance to Agentic AI / LLM Agents¶

SMFGs provide a tractable mathematical foundation for the class of problems where one autonomous agent (a leader—analogous to an orchestrator or policy-setting LLM agent) must learn to influence the emergent collective behavior of a large population of agents. The non-asymptotic guarantees and single-loop design of AC-SMFG are directly relevant to practical multi-agent system design, where runtime efficiency and convergence predictability matter. The gradient alignment condition and PL-based bi-level analysis offer tools for reasoning about hierarchical optimization that appears in LLM agent orchestration, reward shaping, and principal-agent RL fine-tuning settings. While this work targets tabular/economic domains, its theoretical machinery (multi-time-scale actor-critic, mean field abstraction of population dynamics) is a building block for scalable hierarchical agentic frameworks where one controller shapes a swarm of specialized sub-agents.