acceptodds
Under review as a conference paper at ICLR 2027

Learning from Population Marginals: Minimax Regret in Stackelberg Mean-Field Games

Abstract

In Stackelberg mean-field games, a leader interacting with a large population observes population states, while followers' actions are often hidden. We study reinforcement learning (RL) in such games with boundedly rational followers under state observation (SO), where the leader's population feedback consists only of the state distribution. Under SO, we establish the minimax regret over episodes, with other model parameters fixed, where is the effective dimension, is the follower feature dimension, is the number of leader actions, and are the numbers of follower states and actions. We develop an optimistic RL algorithm that attains this minimax rate by evaluating candidate follower responses using observed leader rewards and transitions, and a matching lower bound establishes the optimal dependence on . The exponent of increases with , quantifying how a larger effective dimension makes learning harder in the worst case. We then consider marginal observation (MO), which additionally reveals the action marginal distribution without state–action correspondence. When the SO rate is governed by the follower parameter dimension, we give a necessary and sufficient geometric condition for SO and MO to have the same minimax temporal order. We also establish matching separations for a family allowing arbitrarily large follower action spaces, showing when action marginal observation strictly improves the optimal regret rate.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, Stackelberg games, mean-field games

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_eM2VOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies linear Stackelberg mean-field games with myopic quantal-response followers. It compares three feedback settings. State observation (SO) reveals the population-state marginal. Marginal observation (MO) also reveals the action marginal, but not the state–action pairing. Complete observation (CO) reveals the joint distribution.

Critical strengths
  1. The paper clearly distinguishes observing both marginals from observing the joint distribution. This captures a meaningful difference in information.
  2. The effective dimension explains which parameters determine the exponent of T. This gives more insight than an upper bound alone.
  3. The lower-bound sketch accounts for the full observable history. It also specifies shared feature maps within each testing family. These details help address possible information leakage.
  4. The MO capacity criterion explains when the extra observation gives no improvement in the worst case. This is more informative than simply showing that more information cannot hurt.
Critical weaknesses

none

Questions for authors

none

2 comments
AuthorsOpenReview ↗

Response to Reviewer eM2V

Dear Reviewer eM2V,

Thank you for your review and for recognizing the paper’s theoretical contributions and their implications for learning from population marginals. The distinction you highlight between observing both marginals and observing the joint state–action distribution motivates our comparison of feedback settings.

The effective dimension determines the minimax regret exponent under state observation. In the parameter-limited regime of Theorem 5, observing the action marginal alongside the state marginal lowers that exponent exactly when the linear blindness capacity is smaller than the follower parameter dimension.

We will add a two-state, two-action example beside Table 1 and refer back to it before the capacity definition. The example shows how changes in conditional responses can cancel across states, leaving both marginals fixed while the joint distribution changes.

Thank you for the response. The proposed example should help make the distinction between marginal and joint observations more concrete. My assessment remains positive.

Reviewer_V7TEOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies reinforcement learning in Stackelberg mean-field games where a leader observes only population marginals, not individual follower actions. The authors establish regret bounds under two observation regimes (state-only vs. state-plus-action marginals), propose an optimistic algorithm achieving these bounds, and provide a geometric condition characterizing when action marginals accelerate learning. The effective dimension governing learning difficulty is the minimum of follower parameter dimension, leader action space size, and conditional-response complexity.

Critical strengths
  1. Paper provides a tight minimax characterization. The effective dimension formula elegantly reveals how the learning bottleneck shifts based on problem structure.
  2. Paper provides necessary-sufficient condition for when marginal observation helps the learning process, which provides actionable guidance for system designers on when investing in richer observations is worthwhile.
Critical weaknesses
  1. I found the paper hard to read (dense notation without intuitive scaffolding). Key concepts need concrete examples or illustrations before formal definitions.
  2. Still unclear if algorithm is computationally practical for realistic instances. Ideally we would need a formal complexity analysis. Or even only empirical runtime measurements showing how wall-clock time scales with problem size.
Questions for authors

Can you provide concrete per-episode runtime measures as a function of problem dimensions? When does the algorithm become computationally prohibitive?

4 comments
AuthorsOpenReview ↗

Response to Reviewer V7TE (I)

Dear Reviewer V7TE,

Thank you for recognizing the paper's theoretical contribution and significance. We address computational practicality with measured costs and specify how we will improve readability with intuitive examples and illustrations of key concepts.

1. Computational practicality and per-episode cost (W2/Q1)

W2: Quantitative evidence for computational practicality

Across the paper's five experimental settings, mean learner time is 0.69–2.91 ms/episode. We completed 15 runs of 10,000 episodes (three seeds per setting). We also give dimension-dependent operation and memory costs, with controlled measurements varying dFd_F, candidate count, commitment resolution and history length. We will add the analysis, timing tables, scaling plots and measurement protocol in App. H.6, with links from H.3 and §4.1.

Q1(a): Measured per-episode and refresh times

We timed the original H.3 implementation with H=3H=3, S=A=X=B=4S=A=X=B=4, dL=5d_L=5 and grid denominator q=12q=12. After startup, planning refreshes every 10 episodes and parameter refinement is scheduled every 250. The table reports mean milliseconds: learner/episode includes planning, observation processing and amortized initialization; refresh columns give the full planning-call cost with or without refinement.

SettingdFd_FLearner/episodeOrdinary refreshRefinement refresh
Uninformative SO21.329.0842.69
Uninformative SO32.6721.8173.61
Uninformative MO32.7620.0384.56
Informative SO32.9123.0690.00
Informative MO30.693.40not needed

All 15 runs completed in 17.7–68.0 seconds each, with peak resident memory below 123 MiB. Full-run times include simulation, true-value evaluation and I/O; learner times exclude them.

Informative MO's lower cost has a direct explanation: Eq. (60) identifies the follower parameter after the first uniform commitment, concentrating the planning set to tolerance and stopping refinement.

Q1(b): Costs of fitting, search and refinement

Let KallK_{\mathrm{all}} count candidates in the auxiliary fit, KretK_{\mathrm{ret}} bound retained planning candidates at each step, and MM count searched commitments. The implementation already caches sufficient statistics, avoiding repeated historical scans when continuation values change. These statistics reconstruct the full regression objective. Incremental updates cost O(HKall(dL2+dF))O(HK_{\mathrm{all}}(d_L^2+d_F)) per episode.

In H.3, the population is fixed, noninitial states use pure-action search, and state-0 features use only two coordinates, with response values cached. With an existing commitment pool and the fixed solver budget, a routine backward refresh costs O(HKall[SdL+dL3]+HKret[(S−1)AdL2+M]).O\left(HK_{\mathrm{all}}[Sd_L+d_L^3]+HK_{\mathrm{ret}}[(S-1)Ad_L^2+M]\right). The first term fits all candidates; the second searches over retained candidates. The response cache uses O(KallM)O(K_{\mathrm{all}}M) words; H.6 will give the full memory and pool-reconstruction bounds.

Over each complete 250-episode block after the initial planning refresh, average per-episode cost is at most the average execution and update cost plus 1/101/10 of the block's maximum routine-refresh cost and 1/2501/250 of its additional refinement/rebuild cost. Each refinement objective/gradient evaluation costs O(ndF)O(nd_F) on nn past episodes; the total refinement/rebuild cost includes all such evaluations, optimizer overhead and reconstruction of historical statistics for new candidates.

AuthorsOpenReview ↗

Response to Reviewer V7TE (II)

Q1(c): Measured scaling and practical limits

The base grid contains (q+dFdF)\binom{q+d_F}{d_F} commitments, and the full pool satisfies M≤(q+dFdF)+A+1+KallM\le\binom{q+d_F}{d_F}+A+1+K_{\mathrm{all}}. Refinement can add at most two candidates every 250 episodes. At the original environment sizes, we vary dFd_F, search budgets and history length using recorded SO histories. Grid and candidate comparisons fix each seed's history. With n=100n=100 and 257+dF257+d_F initial candidates, warm-refresh times (cache already built) are:

Grid denominator qqdF=2d_F=2: MM / msdF=3d_F=3: MM / ms
6232 / 6.59220 / 6.42
12295 / 8.00590 / 12.49
24529 / 10.753,060 / 46.58
481,429 / 24.4620,960 / 487.05

Each entry averages per-seed median refresh times over three seeds. At dF=3,q=12d_F=3,q=12, increasing the initial bank from 68 to 1,028 candidates raises refresh time from 3.10 to 69.40 ms. With a fixed 260-candidate bank, increasing history from 1,000 to 10,000 episodes changes routine refresh from 11.66 to 13.29 ms, while refresh with refinement rises from 36.57 to 78.40 ms. This separates the benefit of cached routine fitting from the history-dependent work of refinement.

Feasibility depends on the search budget and the application's time and memory constraints. At dF=3,q=24d_F=3,q=24, the table's warm-refresh statistic is 46.58 ms, below an illustrative 100 ms refresh budget; mean refresh time including cache construction is 137.69 ms, above that budget. The growth factors are combinatorial commitment grids, candidate fitting and the KallMK_{\mathrm{all}}M cache, dense dL3d_L^3 solves, and history-dependent refinement/reconstruction.

2. Intuitive examples and illustrations (W1)

We will add intuitive examples and illustrations to key concepts in the main text. The submitted main text already explains the three dimensions and regret exponent after Thm. 2 (p. 6), with a summary in App. B.3, Table 2. To meet the nine-page submission limit, the experimental overview and illustration from our original main text were moved to App. H. We will use the permitted extra main-text page to restore representative material and place examples and explanations alongside the definitions of key concepts.

At the observation regimes, before the capacity definition: for two equally populated follower states and two actions, consider the joint distribution P(ρ)=12(ρ1−ρ1−ρρ),0<ρ<1.\mathcal P(\rho)=\tfrac12\begin{pmatrix}\rho&1-\rho\\\\1-\rho&\rho\end{pmatrix},\qquad 0<\rho<1. Rows are follower states and columns are actions. Both marginals stay (1/2,1/2)(1/2,1/2) as ρ\rho changes: MO observes action totals but not their state association. Opposite logit contrasts t,−tt,-t, with ρ=et/(1+et)\rho=e^t/(1+e^t), generate this cancellation. With aligned contrasts, both conditional-response rows are (ρ,1−ρ)(\rho,1-\rho) and the action marginal reveals ρ\rho. We will place this example beside Table 1 and recall it before Definition 2: the capacity measures how many independent linear logit directions aggregation can conceal.

Before the algorithm's formulas: we will expand the existing §4 roadmap before Eq. (4). A candidate follower parameter predicts the hidden joint distribution and hence the leader feature vector; observed leader rewards and transitions test the resulting Bellman predictions, and the learner commits to an optimistic policy among the surviving candidates. Before Eq. (8), we will explain the excess-loss comparison: each candidate and its auxiliary comparator are evaluated against the same regression targets, with the continuation held fixed.

Before Thm. 2: a compact Table 2 preview will explain dFd_F, A−1A-1 and X(B−1)X(B-1) as parameter, commitment and conditional-logit dimensions. They give alternative bounds on the same learner's uncertainty; the tightest bound yields the minimum in the temporal exponent.

Alongside the SO/MO results: we will bring forward a compact illustration from App. H.1, Fig. 1. It connects response dimension and marginal information to learning: cancellation leaves the paired SO/MO trajectories coincident, whereas informative marginals accelerate learning in games with the same leader rewards and transitions.

The above changes give a reading path from the observation example, through observable Bellman testing, to the effective dimension and capacity criterion.

Final remarks

We hope our responses resolve your questions and concerns. Please let us know if any of them remain. If your concerns are fully resolved, we would appreciate your considering a higher overall evaluation. Thank you.

Thank you for your clarifications! However, the scaling tables confirm my concern: exponential growth with grid resolution and dimension makes larger problems prohibitive. Despite this limitation, the theoretical contribution merits publication. I maintain my weak accept recommendation.

AuthorsOpenReview ↗

Response to Reviewer V7TE (III)

Dear Reviewer V7TE,

Thank you for your follow-up. We sincerely appreciate your positive assessment that our theoretical contribution merits publication.

We would like to clarify one point regarding the scaling results. The tables report the computational costs of our finite numerical implementation, whose base commitment grid has (q+dFdF)\binom{q+d_F}{d_F} points. For fixed dFd_F, this grows polynomially, rather than exponentially, with the grid resolution qq. The joint dependence on resolution and dimension can nevertheless be combinatorial. We have clarified this distinction in the revised manuscript (Appendix H.6).

Thank you again for your constructive feedback!

Reviewer_deD6OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper provides a new leader-follower mean field game formulation that rigorously reduces to a single-agent RL problem via establishing a Bellman equation. The problem cannot be reduced to a single-agent RL problem without lifting, because the leader reward term depends not only on leader actions, but also the leader strategy πh\pi_h itself (since followers will respond against that). The authors thus propose a suitable lifting of the problem and a Bellman equation, together with improved RL algorithms for the specific model that accordingly appear plausible, and minimax regret rates. The authors design an algorithm based on optimistic model-based RL with strong minimax rates on regret. They also consider various observability settings such as observing only the follower state marginal, their state-action distribution, or their state and action marginals.

Critical strengths
  • The direction seems promising and useful: The concept of learning without observing the actions of the followers seems realistic and useful for certain scenarios.
  • The presentation of the work is rigorous and appropriate for the topic, though more discussion could help, see below.
  • The rates are strong, and the differentiation between rates for SO and MO case are interesting and intuitive.
Critical weaknesses
  • The model appears to be limited to 1. finite-dim. linear mean field games with 2. fully myopic and 3. bounded rational follower agents, which is a little bit limiting and specific as a model. A generalization or at least discussion of why generalization is not possible would be helpful to show the frontier / limitations.
  • Regarding the order of execution: 1. leader announces π\pi 2. at each step, myopic followers "announce" their strategy against leader strategy 3. then draw leader action and continue; this order seems very specific, and just to be sure, use cases should be verified against it.
  • It seems no connection to the finite problem of interest is stated (NN finite follower agents), though I think it should be straightforward.
  • The order of execution implies the problem cannot be reduced to a single-agent RL problem without lifting and having a simplex-valued action space, because the leader reward term depends not only on leader actions, but also the leader strategy πh\pi_h itself. Thus, authors lift the problem to a Bellman equation over πh\pi_h itself at each step instead of leader actions, which transforms the problem into a single-agent RL problem. Authors essentially reduce the problem to a lifted single-agent RL problem, which could be clarified better and could warrant some more discussion or comparison to generic RL baseline solutions on this lifted problem, see questions below.
Questions for authors
  1. Can we generalize the model along the axes of 1. finite-dim. linear mean field games with 2. fully myopic and 3. bounded rational follower agents?
  2. The leader knows that the followers are myopic bounded rational, and thus the action marginal could be inferred if the reward model was known. Is the reasoning correct that the marginal or complete observation helps, because the leader does not know the reward model?
  3. Authors lift the problem to a Bellman equation over πh\pi_h itself at each step instead of leader actions, which transforms the problem into a single-agent RL problem. Is this correct, does the model cleanly reduce to a high-dimensional single-agent control problem? In which case I am curious how your specialized algorithm compares against generic RL on the lifted problem (model-based or model-free)?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.