acceptodds
Under review as a conference paper at ICLR 2027

Pure, Mixed and Behavioral Strategy Learning in Mean Field Games

Abstract

Mean Field Games (MFGs) provide a scalable framework for multi-agent reinforcement learning, but traditionally rely on two assumptions: agents are homogeneous (i.e., they use identical policies) and their policies are stochastic (i.e., their actions are random). We challenge the necessity for these two foundational assumptions by establishing equivalence between standard MFGs and a novel system with heterogeneous agents playing deterministic strategies. We prove that for any behavioral strategy Nash equilibrium (NE) in an MFG, there exists an equivalent mixed strategy NE over a population of agents with diverse, deterministic policies. This is analogous to classical game-theoretical insights from Kuhn's theorem, suitably adjusted to MFGs for the first time. The equivalence is constructive, enabling the approximation of Nash equilibria in large -agent games using only pure strategies, which are simpler to implement and analyze. Our insight reframes the role of stochasticity in MFGs as a population-level sufficient condition rather than a necessary requirement for individual agents. Algorithmically, this perspective gives rise to a new class of learning methods, including Fictitious Play and finite-agent variants that operate with pure policies. We explore the performance, scalability, and behavioral implications of this framework on multi-agent reinforcement learning tasks, leveraging deep reinforcement learning for general tractability.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Mean field games, Nash equilibrium, Kuhn's theorem, Fictitious Play, Reinforcement Learning

Reviews

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

This paper relaxes the two assumptions in the classical mean-field games: the homogeneity of agents and the stochasticity of their policies. Instead, the authors assume that the agents can take heterogeneous deterministic policies and theoretically prove the equivalence of the equilibria between the classical MFG system and the one established in this paper. Then, the authors establish the novel algorithms based on this new perspective and integrate RL to handle the large state and action spaces. Experiments demonstrate that the new system shows the same macro behavior as the classical MFG system while allowing heterogeneous individual policies for each agent.

Critical strengths
  • The motivation of this paper is clear and sensible. The authors clearly explain how classical assumptions limit the applicability of classical MFGs. Allowing the agents to have heterogeneous individual policies has practical implications.

  • The authors provide theoretical contributions by proving the equivalence of the equilibria between the classical MFG system and the one established in this paper, which is sound and provides a fundamental understanding of the field of MFGs.

  • The experiments also demonstrate the effectiveness of the established system.

  • Also, this paper is well-written and easy to follow, presenting a well-executed research plan with sound theoretical results and convincing experimental results.

Critical weaknesses

I see no significant weaknesses, but only one minor question: the agents' heterogeneity is defined in terms of their individual pure deterministic strategies, yet they appear to share the same population-level mixed strategy σ\sigma. Does that mean the agents are still somewhat homogeneous?

Questions for authors

See weaknesses.

1 comment

Response to Reviewer PbPR

We thank the reviewer for the positive assessment and for the precise questions: the agents are heterogeneous in their individual pure strategies, yet they share the population-level mixed strategy σ\sigma. Does that mean they are still somewhat homogeneous?

We have two answers.

Part 1: In Section 3.2, agents are homogeneous ex ante. Ex ante, agents are exchangeable and draw from the same σ\sigma similar to standard MFG (however, see also Answer 2). Ex post, each agent holds one deterministic policy, so the population is heterogeneous. In a homogeneous behavioral MFG, every agent randomizes at every decision. Here, no individual agent randomizes at all and the randomization is only "ex ante" at the population level.

Part 2: Theorem 3 gives a deterministic finite-NN profile without a shared behavioral policy. The shared σ\sigma is not necessary in the finite game of actual interest. For any finite NN, Theorem 3 finally constructs a tuple of deterministic pure policies (π1,…,πN)(\pi^1,\dots,\pi^N), one per agent (e.g., by proportional assignment from σ∗\sigma^\ast), that is an ϵ(N)\epsilon(N)-Nash equilibrium of the NN-agent game in expectation, with ϵ(N)→0\epsilon(N)\to 0. Each agent has its own fixed deterministic policy, and no agent randomizes. The construction may assign the same pure policy to several agents. When σ∗\sigma^\ast has more than one policy in its support, the population is heterogeneous. The population-level σ\sigma is only the limiting mean field solution used to choose the finite list. So the finite-NN statement does not require a shared behavioral policy; it is deterministic ex post. Rock–Paper–Scissors makes this concrete: the unique MFNE is (1/3,1/3,1/3)(1/3,1/3,1/3), but a homogeneous pure population of e.g. 100 agents is never an exact equilibrium, since 100 is not divisible by 3. But an approximate equilibrium exists with around 1/31/3 of agents playing each pure policy.

We have added the ex ante/ex post paragraph after the SMFNE definition in Section 3.2, including the sentence on the Theorem 3 finite-NN construction, and the abstract now says "behavioral homogeneity (a single policy is shared by all agents)" to avoid the same ambiguity.

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

This paper theoretically shows a constructive equivalence between standard MFGs and a system with heterogeneous agents playing deterministic strategies. So, for any Nash equilibrium strategy, there is an equivalent mixed Nash strategy over a population of agents with deterministic policies, which mirrors Kuhn's theorem from game theory. The resultant policies are simpler to analyze (as they are deterministic), and show that stochasticity is an unnecessary condition in MFGs. More broadly, this work establishes (but doesn't point out as a strength, unfortunately) that MFGs can be derandomized, which is a very exciting contribution. Finally, they verify the framework in numerical settings (using deep RL to study infinite state-space settings).

Critical strengths

This paper theoretically shows a constructive equivalence between standard MFGs and a system with heterogeneous agents playing deterministic strategies. So, for any Nash equilibrium strategy, there is an equivalent mixed Nash strategy over a population of agents with deterministic policies, which mirrors Kuhn's theorem from game theory. In doing so, it shows that MFGs can be derandomized, which is a very cool result. The math is generally clean to follow and appears right (though I have missed some details).

Critical weaknesses

I'm skeptical about how interesting the connection to Fictitious play is: for instance, Karlin's conjecture is a classic instantiation of fictitious play, but it was proved that the convergence rate can be exponentially slow in some pathological settings, and polynomially slow in a variety of other settings [1,2]. Can the authors comment on this?

References:

[1] A Counter-Example to Karlin's Strong Conjecture for Fictitious Play (2014)

[2] Arbitrarily Slow Polynomial Convergence of Fictitious Play (2026)

Questions for authors
  1. The paper says that the agents need to be homogeneous, but that's not true. The paper also mischaracterizes one of the citations. It says that "While extensions to heterogeneous populations exist, they typically model agents with fixed and exogenous 'types' (with different dynamics or reward functions)", and cites Caines & Huang's work on graphon mean-field games [1], but that work (also, in [2]) shows that there can be arbitrary types that don't need to be fixed. In [2], the graphon setting allows the interactions to depend on the underlying graphon W:[0,1]2→[0,1]W:[0,1]^2\to[0,1], which can take on infinite values as it's continuous. The authors should really clarify this more carefully.

  2. In equation 3, the first decomposition depends on xt−1x_{t-1}, but I thought this system was Markovian and also stochastic. Why is that justified without adding a term for the distribution of xt−1x_{t-1}?

  3. In line 687, you need that the integrand is finite before applying Fubini. Can the authors add a justification for why that's true? The integrand does, after all, have an integral over an infinite continuous space X\mathcal X, so it's not obvious why the integrand is finite.

References:

[1] Graphon mean field games and their equations (2021)

[2] Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning (2026)

1 comment

Response to Reviewer 2xVF

We thank the reviewer for the careful reading and for the derandomization framing. We agree with the corrections and have made them.

Fictitious play and slow convergence

We agree: the connection to FP is not a rate claim. We added a paragraph to Related Work:

  • FP can converge exponentially slowly in two-player zero-sum games [1] and at arbitrarily slow polynomial rates [2]. Karlin's O(1/t)O(1/\sqrt t) conjecture is false in general.
  • Rates do exist for subclasses: for monotone potential MFGs with Lipschitz rewards, discrete-time FP is Frank–Wolfe and has an O(1/t)O(1/\sqrt t) exploitability rate [3], consistent with the conjecture in [4]. This is a subclass. Outside it, monotonicity gives asymptotic convergence without a general rate.

Proposition 2 is also now explicitly continuous-time, with the discrete algorithm as its Euler discretization. We claim no discrete-time rate.

Heterogeneity in graphon MFGs

We thank the reviewer for the corrected discussion of related work. We no longer say that heterogeneous extensions "typically model fixed and exogenous types." The revised text says that much of the literature uses exogenous type labels, while graphon MFGs go further: the interaction kernel depends on a graphon, so the population can be indexed by a continuum of positions and need not be described by a finite list of fixed types [5, 6].

Instead, our heterogeneity is behavioral: agents that are structurally identical (e.g., same state, same type, same graphon index) differ in their pure policy (behavior), which is orthogonal to type/graphon heterogeneity. The word "homogeneous" now refers to behavioral homogeneity in the standard formulation (one behavioral policy shared by all agents), not to a claim about all MFG models. The abstract now says "behavioral homogeneity (a single policy is shared by all agents)."

Equation (3) and the distribution of μ\mu

Equation (3) is in fact not Markovian if we only consider the state to be xtx_t. The reason for this is that each agent must randomly choose a policy πp\pi^p, and depending on it, the state distribution will differ greatly. As the reviewer suggested, the second step does add the term for the distribution of xt−1x_{t-1}, conditional on πp\pi_p, as P(xt−1=x∣πp)=∏s=0t−2p(dxs+1∣xs,πsp(xs),μs)μ0(dx0)\mathbb P(x_{t-1} = \mathbf x \mid \pi^p) = \prod_{s=0}^{t-2} p(\mathrm dx_{s+1} \mid x_s, \pi_s^p(x_s), \mu_s) \mu_0(\mathrm dx_0).

Fubini

The reviewer is right that finiteness must be checked, especially because Πpure\Pi_{\rm pure} can be continuous. Note that the integrand is nonnegative and bounded, 0≤μt∣πpσ(x)≤10\le \mu^\sigma_{t\mid\pi^p}(x)\le 1 and 0≤p(x′∣x,u,μ)≤10\le p(x'\mid x,u,\mu)\le 1, and the sums over x∈Xx\in\mathcal X and u∈Uu\in\mathcal U are finite. Hence the double sum/integral is finite, and Tonelli's theorem (measurability and nonnegativity, no continuity in πp\pi^p) justifies the exchange. We added this at the Fubini step in Appendix A.1 and referenced it at the later grouping step.

Other

We thank the reviewer for the derandomization framing! The introduction now says: "MFG equilibria can be derandomized at the individual level: any equilibrium value achievable with a shared behavioral policy is achievable by a population of deterministic agents."

[1] A Counter-Example to Karlin's Strong Conjecture for Fictitious Play (2014)

[2] Arbitrarily Slow Polynomial Convergence of Fictitious Play (2026)

[3] Concave Utility Reinforcement Learning: the Mean-field Game Viewpoint (2021)

[4] Fictitious Play for Mean Field Games: Continuous Time Analysis and Applications (2020)

[5] Graphon mean field games and their equations (2021)

[6] Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning (2026)

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

The paper studies whether a mean-field Nash equilibrium represented by a shared behavioral policy can instead be implemented through a heterogeneous population of deterministic policies. It constructs transformations between behavioral policies and distributions over pure policies, claims approximate Nash guarantees for finite populations, and introduces mixed and deterministic fictitious-play procedures. Numerical studies examine exploitability, memory requirements, deep reinforcement learning best-response oracles, and individual behavior across several synthetic environments.

Critical strengths
  1. The occupancy-weighted transformation provides a clear explanation of how population-level policy diversity can reproduce the state distributions generated by individual randomization.
  2. The paper connects this representation to concrete implementation choices, including storing deterministic best-response policies and assigning them across agents. The memory experiment identifies a potentially useful tradeoff between action-space size and the number of retained policies, although the evidence currently supports a narrower conclusion than the manuscript claims.
Critical weaknesses
  1. The proof of the finite-population guarantee incorrectly removes the dependence between an agent’s current state and its assigned pure policy. Appendix A.4 defines the transition operator although fixed policy assignments generally make the state and policy dependent after the first transition. A counterexample uses binary states and actions, deterministic dynamics, and equally weighted policies A and B:

xt+1=ut,x0=0x_{t+1}=u_t,\qquad x_0=0,

A0=0,B0=1,A_0=0,\qquad B_0=1,\qquad A1(x)=x,B1(x)=1−xA_1(x)=x,\qquad B_1(x)=1-x.

The actual population returns entirely to state zero, whereas the displayed operator predicts a uniform distribution:

μ2=δ0,\mu_2=\delta_0,\qquad Φ1(μ1,σ)=12δ0+12δ1\Phi_1(\mu_1,\sigma) = \frac12\delta_0+\frac12\delta_1.

The claimed sampling-error estimate does not follow, and Theorem 3 requires a new argument tracking the joint state–policy distribution or an appropriate coupling. This identifies a defect in the supplied proof rather than a counterexample to the theorem itself.

  1. The algorithmic guarantees do not match the full scope of the presented algorithms. Algorithm 1 averages mean fields generated by individual best responses, which agrees with the mean field induced by the mixed strategy only under mean-field-independent transitions. Appendix A.5 analyzes continuous-time fictitious play rather than the supplied discrete algorithm, while Appendix A.6 establishes a conditional-mean update identity rather than convergence of fixed-population DFP. These distinctions affect the central claim that the framework provides learning methods with convergence guarantees.
Questions for authors
  1. Can Theorem 3 be proved while retaining the joint state–policy distribution? For Theorem 4, how is the expected distance from the target mean field controlled before applying bounded differences, given that the mean-field map is nonlinear?

  2. Is Algorithm 1 intended exclusively for mean-field-independent transitions, and what update was used in the SIS experiments? What precise discrete-time convergence result is available for MFP, and what result is claimed for DFP beyond its conditional-mean identity?

  3. How was exploitability evaluated, particularly for the DRL experiments? Since an approximate deviation oracle can underestimate exploitability, can the reported policies be evaluated using exact dynamic programming on the tabular-solvable benchmarks, with the environment definitions, DFP schedule, run counts, and uncertainty estimates supplied?

  4. Does the memory advantage remain when FP uses sparse action-probability storage and methods are compared at matched exploitability? After a finite number of deterministic best responses, the behavioral average need not contain a dense probability vector at every state–time pair, which materially affects the claimed resource advantage.

2 comments

Response to Reviewer 19w8

We thank the reviewer for their exceptionally careful and constructive review, which directly improved the paper. We are highly grateful for the time taken. The main theorems remain unchanged.

W1: finite-population proof

The reviewer's suggestion is correct: after the first transition the state and the assigned policy are dependent.

Appendix A.4 now tracks the joint law ηtN(x,πp)=1N∑i1{xti=x, πi=πp}\eta_t^N(x,\pi^p)=\frac1N\sum_i\mathbf 1_{\{x_t^i=x,\ \pi^i=\pi^p\}} of (state, policy). The decomposition then gives et+1≤C1/N+(1+Lp)ete_{t+1}\le C_1/\sqrt N+(1+L_p)e_t, hence O(1/N)O(1/\sqrt N). The theorem's bound is unchanged, and we made the expectation explicit, E[Ei]≤ϵ(N)\mathbb E[\mathcal E^i]\le\epsilon(N).

W2: algorithmic guarantees

The reviewer is right on the three points, and we discuss as follows.

(a) Algorithm 1's mean-field average. The linear update is exact only if pp is independent of μ\mu (Assumption 1). Without the assumption, the algorithm is still well defined and used. We now note that it gives μk+1=Λˉ(σk+1)\mu^{k+1}=\bar\Lambda(\sigma^{k+1}) under Assumption 1. We also reran the implementation with ζ(σk+1)\zeta(\sigma^{k+1}) with matching results in our experiments.

(b) A.5 is continuous-time. Proposition 2 is now stated for continuous-time MFP. The discrete algorithm is its Euler discretization. We do not claim a separate discrete-time theorem or rate. The mean-field-independence assumption matches the finite-horizon scope of Perrin et al. The algorithm itself is defined for mean-field-dependent transitions.

(c) A.6 is a conditional-mean identity. We agree with the reviewer, a fixed-population convergence theorem is not available. We state explicitly that a fixed-NN convergence proof is open.

Q1: Theorem 3 with the joint distribution; Theorem 4 nonlinearity

Theorem 3: Yes. The proof is in W1 (joint state–policy distribution). The statement now makes the expectation over the finite-population randomness explicit; the O(1/N)O(1/\sqrt N) bound is unchanged.

Theorem 4: The earlier proof applied McDiarmid to Λˉ(σN)\bar\Lambda(\sigma^N) around μ∗\mu^\ast, but McDiarmid controls the function around its mean, and EΛˉ(σN)≠Λˉ(σ∗)\mathbb E\bar\Lambda(\sigma^N)\neq\bar\Lambda(\sigma^\ast) because Λˉ\bar\Lambda is nonlinear. We split ∥Λˉ(σN)−Λˉ(σ∗)∥≤∥Λˉ(σN)−EΛˉ(σN)∥+∥EΛˉ(σN)−Λˉ(σ∗)∥\|\bar\Lambda(\sigma^N)-\bar\Lambda(\sigma^\ast)\|\le\|\bar\Lambda(\sigma^N)-\mathbb E\bar\Lambda(\sigma^N)\|+\|\mathbb E\bar\Lambda(\sigma^N)-\bar\Lambda(\sigma^\ast)\|. The first term is the McDiarmid fluctuation, O(log⁡(1/δ)/N)O(\sqrt{\log(1/\delta)/N}). The second is the bias. The joint-distribution Lipschitz bound gives E[B]≤(c2/2)K/N\mathbb E[B]\le (c_2/2)\sqrt{K/N} with K=∣Πpure∣K=|\Pi_{\rm pure}| and c2=∑t(1+Lp)tc_2=\sum_t(1+L_p)^t, and McDiarmid is applied around EB\mathbb E B rather than around μ∗\mu^\ast. Term A is the standard propagation-of-chaos bound O(1/N)O(1/\sqrt N).

Q2: Algorithm 1 scope; SIS update; discrete-time MFP and DFP

Algorithm 1 / SIS: See W2(a).

Discrete MFP/DFP: See W2(b),(c).

Q3: exploitability evaluation

We define E(σ)=sup⁡π^J(π^,Λˉ(σ))−J(σ,Λˉ(σ))\mathcal E(\sigma)=\sup_{\hat\pi}J(\hat\pi,\bar\Lambda(\sigma))-\mathcal J(\sigma,\bar\Lambda(\sigma)).

  • Tabular benchmarks (RPS, Braess, SIS): both terms are computed exactly by backward dynamic programming and exact library evaluation.
  • DRL: the Double-DQN is used only as the best-response oracle during learning. Exploitability is computed exactly by backward DP.
  • Protocol: the DRL population size and horizon are specified as (1,0001{,}000 agents, T=20T=20), and the DFP schedule is αk=1/(k+1)\alpha_k=1/(k+1). FP and MFP are deterministic in the mean-field limit, so a single run is exact. DFP is finite-NN and stochastic. Its curves report the mean over five independent seeds. The DFP-DRL experiments are single-run.

Q4: memory vs. sparse FP

The reviewer is right. After KK best responses the behavioral average is a convex combination of KK deterministic policies, so at each (t,x)(t,x) it has support at most KK (and at most ∣U∣|\mathcal U|). Stored sparsely it needs O(min⁡(K,∣U∣)∣X∣T)O(\min(K,|\mathcal U|)|\mathcal X|T) entries, the same order as MFP's library.

We have made the comparison. At ∣U∣=1000|\mathcal U|=1000: peak memory is 0.9920.992 MB (dense FP), 0.1670.167 MB (sparse FP), 0.1640.164 MB (MFP). The factor-∣U∣|\mathcal U| gap is thus a property of the dense representation, not of MFP itself.

Still, what remains is an either/or trade-off, sharpest with neural policies. To form the final behavioral average, sparse FP must either keep the per-policy mean fields or re-simulate past best responses at O(K2)O(K^2) total cost. Either way it needs an extra pass beyond the best-response loop. With neural best responses, weight averaging is invalid, and distillation adds an approximation not covered by the theory. In contrast, each MFP agent samples one policy once, and DFP keeps exactly NN policies. Section 5 now presents this trade-off rather than a memory factor.

We hope the revision is responsive, and we would be grateful if the reviewer would reassess the paper in light of the changes.

Thank you for addressing my main concerns. I do not have any additional comments. I will increase the score based on the responses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.