Paper deep dive
Mean-Field Reinforcement Learning without Synchrony
Shan Yang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 7/20/2026, 10:53:10 PM
Summary
The paper introduces the Temporal Mean Field (TMF) framework for multi-agent reinforcement learning, addressing the limitation of existing Mean-Field RL methods that require synchronous agent actions. By replacing the mean action with the population distribution (the fraction of agents at each observation), the framework handles asynchronous decision-making where agents act at different times. The authors prove the existence and uniqueness of TMF equilibria, establish an O(1/√N) finite-population approximation bound, and propose a policy gradient algorithm (TMF-PG) that converges to the unique equilibrium. Experiments confirm that TMF-PG performs consistently across different levels of asynchrony.
Entities (8)
Relation Signals (6)
Temporal Mean Field (TMF) → uses → Population Distribution
confidence 98% · We therefore construct the Temporal Mean Field (TMF) framework around the population distribution μ from scratch
TMF-PG → convergesto → TMF Equilibrium
confidence 96% · prove convergence of a policy gradient algorithm (TMF-PG) to the unique equilibrium
Temporal Mean Field (TMF) → handles → Asynchrony
confidence 95% · Addressing asynchrony therefore requires a different summary statistic... We therefore construct the Temporal Mean Field (TMF) framework
Temporal Mean Field (TMF) → provides → O(1/√N) approximation bound
confidence 94% · establish an O(1/√N) finite-population approximation bound that holds regardless of how many agents act per step
Temporal Mean Field (TMF) → unifies → Synchronous and Asynchronous Decision-Making
confidence 93% · covering the full spectrum from fully synchronous to purely sequential decision-making within a single theory
Mean-Field Reinforcement Learning → replaces → Mean Action
confidence 90% · Mean-field reinforcement learning (MF-RL) scales multi-agent RL to large populations by reducing each agent's dependence on others to a single summary statistic -- the mean action.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Mean-field reinforcement learning (MF-RL) scales multi-agent RL to large populations by reducing each agent's dependence on others to a single summary statistic -- the mean action. However, this reduction requires every agent to act at every time step; when some agents are idle, the mean action is simply undefined. Addressing asynchrony therefore requires a different summary statistic -- one that remains defined regardless of which agents act. The population distribution $\mu \in \Delta(\mathcal{O})$ -- the fraction of agents at each observation -- satisfies this requirement: its dimension is independent of $N$, and under exchangeability it fully determines each agent's reward and transition. Existing MF-RL theory, however, is built on the mean action and does not extend to $\mu$. We therefore construct the Temporal Mean Field (TMF) framework around the population distribution $\mu$ from scratch, covering the full spectrum from fully synchronous to purely sequential decision-making within a single theory. We prove existence and uniqueness of TMF equilibria, establish an $O(1/\sqrt{N})$ finite-population approximation bound that holds regardless of how many agents act per step, and prove convergence of a policy gradient algorithm (TMF-PG) to the unique equilibrium. Experiments on a resource selection game and a dynamic queueing game confirm that TMF-PG achieves near-identical performance whether one agent or all $N$ act per step, with approximation error decaying at the predicted $O(1/\sqrt{N})$ rate.
Tags
Links
- Source: https://arxiv.org/abs/2602.18026v1
- Canonical: https://arxiv.org/abs/2602.18026v1
Trouble viewing inline? Open PDF directly →
Full Text
92,335 characters extracted from source content.
Expand or collapse full text
Mean-Field Reinforcement Learning without Synchrony Shan Yang Abstract Mean-field reinforcement learning (MF-RL) scales multi-agent RL to large populations by reducing each agent’s dependence on others to a single summary statistic—the mean action. However, this reduction requires every agent to act at every time step; when some agents are idle, the mean action is simply undefined. Addressing asynchrony therefore requires a different summary statistic—one that remains defined regardless of which agents act. The population distribution μ∈Δ()μ∈ (O)—the fraction of agents at each observation—satisfies this requirement: its dimension is independent of N, and under exchangeability it fully determines each agent’s reward and transition. Existing MF-RL theory, however, is built on the mean action and does not extend to μ. We therefore construct the Temporal Mean Field (TMF) framework around the population distribution μ from scratch, covering the full spectrum from fully synchronous to purely sequential decision-making within a single theory. We prove existence and uniqueness of TMF equilibria, establish an O(1/N)O(1/ N) finite-population approximation bound that holds regardless of how many agents act per step, and prove convergence of a policy gradient algorithm (TMF-PG) to the unique equilibrium. Experiments on a resource selection game and a dynamic queueing game confirm that TMF-PG achieves near-identical performance whether one agent or all N act per step, with approximation error decaying at the predicted O(1/N)O(1/ N) rate. Machine Learning, ICML, Mean-Field RL, Asynchronous MARL, Population State Measure 1 Introduction Mean-field reinforcement learning (MF-RL) (Yang et al., 2018) makes multi-agent RL tractable in large populations: each agent replaces the full joint action with a single summary statistic, the mean action a¯ a, averaged over neighboring agents. This reduction, however, rests on a structural assumption that is easy to overlook: every agent must choose an action at every time step, so that a¯ a is always well-defined. In many real-world domains, such as traffic networks, cloud schedulers, and wireless spectrum markets, the assumption rarely holds—agents routinely act at different times, with some committing to actions while others wait, are in transit, or have not yet arrived. For any agent that does not act at step t, its action simply does not exist, and the mean action a¯ a cannot be formed. Several recent methods address asynchronous execution in MARL—through macro-actions (Xiao et al., 2020), delay randomization (Yu et al., 2023), communication ordering (Ding et al., 2023), or Stackelberg decomposition (Zhang et al., 2024)—but none provides a mean-field formulation, and all still build on synchronous Markov games in which every agent must act before the environment steps. Any replacement for a¯ a must satisfy three requirements: it must be defined at every step regardless of which agents act (persistence), its dimension must not grow with the number of agents N (scalability), and it must carry enough information to determine each agent’s reward and transition (sufficiency). One natural candidate is the global state: it persists across time steps regardless of which agents act. However, it records every agent’s observation individually, so its dimension grows with N—violating the scalability requirement. What does satisfy all three is the distribution of agents across observations: every agent i occupies a well-defined observation oi∈o_i at every step whether or not it acts. Denoting this distribution by μ∈Δ()μ∈ (O)—the population distribution—its dimension is |||O|, independent of N, and under exchangeability, μ fully determines each agent’s reward and transition. This makes μ the unique mean-field object that remains well-defined, scalable, and sufficient under any timing of agent decisions. However, adopting μ does not by itself resolve the problem: the Bellman equations, equilibrium definitions, and convergence results in MF-RL are all built around a¯ a, so a new theory around μ must be developed from scratch. We therefore construct a new framework—the Temporal Mean Field (TMF) framework—around the population distribution μ. The framework is parameterized by the number of agents that act at each step, ranging from all N (fully synchronous) to just one (purely sequential), and covers the entire spectrum within a single theory. Our contributions: 1. Unified framework (Section 3). We formalize how μ evolves when any subset of agents acts, define each agent’s value function conditioned on μ, and introduce an equilibrium concept that couples the policy and the population distribution. 2. Theoretical guarantees (Section 4). We prove existence and uniqueness of the equilibrium (Theorem 4.4) and establish an O(1/N)O(1/ N) finite-population approximation bound that holds regardless of how many agents act per step (Theorem 4.5). 3. TMF Reinforcement Learning (Section 5). We propose TMF-PG, a policy gradient algorithm, and prove that it converges to the unique equilibrium (Theorem 5.1). 4. Experimental validation (Section 7). On a resource selection game and a dynamic queueing game, TMF-PG achieves near-identical performance whether one agent or all N act per step, with approximation error decaying at the predicted O(1/N)O(1/ N) rate. 2 Preliminaries 2.1 Markov Games and Mean-Field RL A Markov game (Littman, 1994) for N exchangeable agents is defined by ⟨,,,P,r,γ⟩ ,O,A,P,r,γ , where S is the system (global) state space, O the individual observation space, A the shared action space, P the transition function, r the reward function, and γ∈[0,1)γ∈[0,1) the discount factor. The system state st∈s_t captures global environment variables; each agent i receives a local observation oti∈o_t^i (e.g., its position, assigned task, or service status). Agents are homogeneous: they share the same observation and action spaces and the same reward structure. At each time step, agents choose actions ati∈a_t^i and the system transitions via st+1∼P(⋅|st,t)s_t+1 P(·|s_t, a_t), where t=(at1,…,atN) a_t=(a_t^1,…,a_t^N) is the joint action. To scale to large N, Yang et al. (2018) proposed the mean-field approximation: Qj(s,aj,−j)≈Qj(s,aj,a¯j),a¯j=1|N(j)|∑k∈N(j)ak,Q^j(s,a^j, a^-j)≈ Q^j(s,a^j, a^j), a^j= 1|N(j)| _k∈ N(j)a^k, (1) where N(j)N(j) denotes agent j’s neighbors. This reduces the exponential dependence on joint actions to a single sufficient statistic a¯j a^j, enabling tractable learning in large populations. Note that under exchangeability the system state is simply the joint observation profile, st=(ot1,…,otN)s_t=(o_t^1,…,o_t^N), so the Q-function’s dependence on s is equivalently a dependence on all agents’ observations. 2.2 Synchrony as a Structural Requirement The tractability of the mean-field approximation, however, rests on a structural assumption that is seldom made explicit: all agents must act simultaneously. To see why, we first formalize the notion of a decision protocol. Definition 2.1 (Decision protocol). A decision protocol Π=ℬtt=0∞ =\B_t\_t=0^∞ specifies, for each time step t, a subset ℬt⊆[N]B_t [N] of agents that act, with batch size Bt=|ℬt|B_t=|B_t|. A protocol is synchronous if Bt=NB_t=N for all t, and asynchronous otherwise (1≤Bt≤N1≤ B_t≤ N, possibly varying over time). Under any asynchronous protocol (Bt<NB_t<N), agents outside ℬtB_t do not act at time t, so their actions are undefined and the mean action a¯j a^j in Equation 1 cannot be computed. A natural workaround is to substitute stale actions—the most recent action of each inactive agent—but this is unsatisfactory. Stale actions introduce a bias that does not vanish with N. Moreover, mean-field Q-learning is an iterative scheme in which agents best-respond to the current mean action, which itself reflects the current policy; substituting outdated actions breaks this consistency loop and invalidates the convergence guarantees. The difficulty is fundamental: the mean action is not merely hard to estimate under asynchrony, but undefined as a quantity whenever Bt<NB_t<N. Addressing this requires replacing the mean field action a¯j a^j with a different summary statistic. 2.3 The Population Distribution as Mean Field Unlike actions, agent observations persist across time steps: every agent occupies an observation oti∈o_t^i at every time step, regardless of whether it acts. At any time t, we can therefore measure the fraction of agents at each observation o: μt(o)=1N∑i=1N[oti=o], _t(o)= 1N _i=1^N 1[o_t^i=o], (2) where [⋅] 1[·] is the indicator function. Collecting these fractions into a vector gives the population distribution μt=(μt(o))o∈ _t=( _t(o))_o , which lies in the probability simplex Δ() (O). Because μt _t is defined entirely from observations, it is well-defined under any decision protocol. Can μt _t replace the mean action a¯j a^j as the mean-field object? Under exchangeability and a shared policy π, knowing μt _t and π determines the aggregate action statistics, so μt _t in principle carries the information that a¯j a^j provides. However, the existing MF-RL Bellman equation and Q-iteration are expressed in terms of a¯j a^j, and their convergence and approximation guarantees rely on the simultaneous-move structure. Replacing a¯j a^j with μt _t therefore requires new dynamics that describe how μt _t evolves under partial updates, a new Bellman equation conditioned on μt _t, and a new equilibrium concept—which is the subject of the next section. 3 The Temporal Mean Field Framework We now present the TMF framework, in which each agent’s policy is conditioned on the population distribution μt _t rather than the mean action a¯t a_t. The framework consists of three components: a dynamic that describes how μt _t evolves when any subset of agents acts (Section 3.1), a Bellman equation that defines each agent’s value conditioned on μt _t (Section 3.2), and an equilibrium concept that couples the policy and the population trajectory (Section 3.3). 3.1 TMF Dynamic As established in Section 2.3, exchangeability ensures that each agent’s reward and transition depend on other agents only through μt _t. The evolution of the population therefore reduces to tracking how μt _t changes as agents act. Suppose all agents follow a shared policy π(a∣o,μ)π(a o,μ) that maps each agent’s observation and the current population state to a distribution over actions. At step t, BtB_t of the N agents each choose an action ati∼π(⋅|oti,μt)a_t^i π(·|o_t^i, _t) and transition to ot+1i∼P(⋅|oti,ati,μt)o_t+1^i P(·|o_t^i,a_t^i, _t); we call these agents active (ℬtB_t). The remaining N−BtN-B_t passive agents transition via ot+1j∼P0(⋅|otj,μt)o_t+1^j P_0(·|o_t^j, _t), where P0P_0 captures environment-driven changes that occur without an explicit action. Given these transitions, the mean-field approximation yields a deterministic recursion for μt _t by replacing per-agent contributions with their expectations: Definition 3.1 (TMF Dynamic). μ¯t+1(o)=∑o′μt(o′)[BtN∑aπ(a|o′,μt)P(o|o′,a,μt)+N−BtNP0(o|o′,μt)]. μ_t+1(o)= _o _t(o ) [ B_tN _aπ(a|o , _t)\,P(o|o ,a, _t)\\ + N-B_tN\,P_0(o|o , _t) ]. (3) For each current observation o′o , the bracketed term blends two contributions: a fraction Bt/NB_t/N of agents act under π and transition via P, while the remaining (N−Bt)/N(N-B_t)/N transition passively via P0P_0. Definition 3.1 defines a deterministic map μt↦μ¯t+1 _t μ_t+1 for any fixed π. Iterating from μ0 _0 therefore produces a unique sequence μtt≥0\ _t\_t≥ 0, which we call the population trajectory. Remark 3.2. Definition 3.1 unifies all decision protocols through the batch size BtB_t. When Bt=NB_t=N (synchronous), every agent is active, the P0P_0 term vanishes, and the recursion reduces to the Kolmogorov forward equation. When Bt=1B_t=1 (sequential), only one agent acts while the remaining N−1N-1 transition passively via P0P_0. By varying BtB_t between these extremes, the TMF dynamic captures synchronous, sequential, and all intermediate protocols. 3.2 TMF Bellman Equation Given the TMF dynamic, we can define each agent’s expected return under a shared policy. When active, each agent selects actions via a shared stochastic policy π(⋅|o,μ)∈Δ()π(·|o,μ)∈ (A), conditioned on its own observation o and the current population distribution μ. Given π, the TMF dynamic determines the entire future trajectory from any μt _t, so the value function depends only on (o,μt)(o, _t): Vπ(o,μt)=∑aπ(a|o,μt)[r(o,a,μt)+γ∑o′P(o′|o,a,μt)Vπ(o′,μt+1)],V^π(o, _t)= _aπ(a|o, _t) [r(o,a, _t)\\ +γ _o P(o |o,a, _t)\,V^π(o , _t+1) ], (4) where μt+1 _t+1 follows from Equation 3. Because VπV^π depends on μt _t rather than on individual agent states, and the TMF dynamic provides a deterministic evolution for μt _t under any batch size BtB_t, this Bellman equation is well-defined for any active agent regardless of the decision protocol. 3.3 TMF Equilibrium We now define the TMF equilibrium given the TMF dynamic and the Bellman equation above. Because μt _t evolves according to the policy π while π is optimized against μt _t, the equilibrium requires not only that π is optimal given a population trajectory μt\ _t\, but also that μt\ _t\ is the trajectory that π itself induces. Definition 3.3 (TMF Equilibrium). A policy π∗π^* is a TMF equilibrium policy if, when μt∗\ _t^*\ is the population trajectory generated by π∗π^* through Equation 3, Vπ∗(o,μt∗)≥Vπ(o,μt∗)∀π,o,t.V^π^*(o, _t^*)≥ V^π(o, _t^*) ∀\,π,\,o,\,t. Unlike a Nash equilibrium in the Markov game, which requires only that each agent’s strategy is a best response, the TMF equilibrium additionally incorporates the feedback loop between the shared policy and the aggregate population dynamics. The TMF equilibrium formalizes the self-consistency between the policy π∗π^* and the population trajectory μt∗\ _t^*\ it induces, and is well-defined for any decision protocol. Together, the TMF dynamic, the TMF Bellman equation, and the TMF equilibrium form a complete asynchronous mean-field framework. Whether this equilibrium exists, is unique, and approximates the finite-agent game remains to be established. 4 Theoretical Guarantees for TMF The TMF framework defines an equilibrium as a self-consistent policy-trajectory pair (π∗,μt∗)(π^*,\ _t^*\), but does not guarantee that such a pair exists or that it is unique. We now establish both properties under mild regularity conditions, and show that the equilibrium approximates the finite N-agent game at rate O(1/N)O(1/ N), all independent of the decision protocol. 4.1 Assumptions The analysis requires three standard assumptions: Lipschitz continuity and ergodicity of the transition functions, and a displacement monotonicity condition that guarantees uniqueness. To formalize these assumptions, we first define a distance on Δ() (O) to quantify how sensitively the model primitives respond to changes in the population distribution. Let 1(μ,ν)=∑o∈|μ(o)−ν(o)|W_1(μ,ν)= _o |μ(o)-ν(o)| denote the ℓ1 _1 distance on Δ() (O). Assumption 4.1 (Lipschitz continuity). The reward r, active transition function P, passive transition function P0P_0, and policy π are Lipschitz continuous in μ with respect to 1W_1: |r(o,a,μ)−r(o,a,μ′)| |r(o,a,μ)-r(o,a,μ )| ≤Lr1(μ,μ′), ≤ L_r\,W_1(μ,μ ), (5) 1(P(⋅|o,a,μ),P(⋅|o,a,μ′)) _1(P(·|o,a,μ),P(·|o,a,μ )) ≤LP1(μ,μ′), ≤ L_P\,W_1(μ,μ ), (6) 1(P0(⋅|o,μ),P0(⋅|o,μ′)) _1(P_0(·|o,μ),P_0(·|o,μ )) ≤LP01(μ,μ′), ≤ L_P_0\,W_1(μ,μ ), (7) ∥π(⋅|⋅,μ)−π(⋅|⋅,μ′)∥∞ \|π(·|·,μ)-π(·|·,μ )\|_∞ ≤Lπ1(μ,μ′), ≤ L_π\,W_1(μ,μ ), (8) where Lr,LP,LP0,Lπ>0L_r,L_P,L_P_0,L_π>0 are the respective Lipschitz constants. The LπL_π condition is satisfied by softmax and entropy-regularized policies. In the proofs, LπL_π bounds how much the optimal policy changes when μ shifts. Lipschitz continuity bounds how the model primitives respond to changes in μ, but does not ensure that a single transition step contracts the distance between agents at different observations. To quantify this contraction, define the active transition matrix Kπ,μ(o′|o)=∑aπ(a|o)P(o′|o,a,μ)K_π,μ(o |o)= _aπ(a|o)\,P(o |o,a,μ) and its Dobrushin contraction coefficient ρ(Kπ,μ)=maxo1≠o212∑o′|Kπ,μ(o′|o1)−Kπ,μ(o′|o2)|.ρ(K_π,μ)\;=\; _o_1≠ o_2 12 _o |K_π,μ(o |o_1)-K_π,μ(o |o_2) |. Denote by ρP=supμ,π:π(a|o)>0∀a,oρ(Kπ,μ) _P= _μ,\,π:\,π(a|o)>0\;∀ a,oρ(K_π,μ) the worst-case contraction coefficient over all policies and population distributions, and by ρP0=supμρ(P0(⋅|⋅,μ)) _P_0= _μρ(P_0(·|·,μ)) the analogous coefficient for passive transitions. Assumption 4.2 (Ergodicity of active transitions). The active transition matrix satisfies ρP<1 _P<1. Assumption 4.2 requires that agents at different observations become strictly closer after one active transition step, regardless of the policy and population distribution. This holds whenever there exists an observation reachable from every other observation under some action—the case in resource selection and scheduling, where every agent can choose any resource. Since P0P_0 is a stochastic matrix, ρP0≤1 _P_0≤ 1 holds automatically and requires no additional assumption. Together with Assumption 4.1, ergodicity supports the existence and approximation results in Theorems 4.4 and 4.5; uniqueness additionally requires a monotonicity condition. Assumption 4.3 (Discrete monotonicity). For any two population distributions μ,μ′∈Δ()μ,μ ∈ (O) and their corresponding optimal policies πμ _μ, πμ′ _μ : ∑o(μ(o)−μ′(o))[Vπμ(o,μ)−Vπμ′(o,μ′)]≥η1(μ,μ′)2, _o(μ(o)-μ (o)) [V_ _μ(o,μ)-V_ _μ (o,μ ) ]≥η\,W_1(μ,μ )^2, (9) where η>0η>0 is the monotonicity constant. Assumption 4.3 is a discrete monotonicity condition: when two population distributions differ, the corresponding value functions “push back” against the difference, preventing multiple equilibria. This is the finite-state counterpart of the Lasry–Lions monotonicity condition (Lasry & Lions, 2007), standard for uniqueness in continuous-state mean-field games. It holds naturally in congestion games, resource allocation, and epidemic models, where increased crowding in a state reduces its value. 4.2 Existence and Uniqueness of the TMF Equilibrium A key question is whether the TMF equilibrium is robust to asynchrony: does the equilibrium exist and remain unique regardless of how many agents act per step? Theorem 4.4 (Existence and uniqueness). Under Assumptions 4.1–4.3, if the monotonicity constant satisfies η>LV+RmaxLπ(1−γ)2,η>L_V+ R_ \,L_π(1-γ)^2, (10) where LV=(Lr+γLPRmax/(1−γ))/(1−γ)L_V=(L_r+γ L_PR_ /(1-γ))/(1-γ) is the value sensitivity constant (Lemma B.1), then for any batch size B∈1,…,NB∈\1,…,N\, a TMF equilibrium (π∗,μt∗)(π^*,\ _t^*\) exists and is unique. The right-hand side comprises two sources of sensitivity to μ: LVL_V measures how the value function changes when the population trajectory is perturbed (Lemma B.1), while RmaxLπ/(1−γ)2R_ \,L_π/(1-γ)^2 captures how the optimal policy shifts in response to the same perturbation. The condition is easier to satisfy when the discount factor γ is small or when the transition function depends weakly on μ (small LPL_P); the precise bound arises from the uniqueness proof (Appendix C). Uniqueness holds for every batch size B∈1,…,NB∈\1,…,N\: regardless of how agents are scheduled, there is exactly one self-consistent policy–trajectory pair, giving agents a well-defined learning target without coordination. 4.3 Finite-Population Approximation The TMF equilibrium is defined in the mean-field limit. To justify its use in finite systems, we bound the exploitability ϵN _N: the maximum gain any single agent can achieve by deviating from π∗π^* in the N-agent game. Writing μ^πN μ^N_π for the empirical distribution trajectory when all agents follow π, the exploitability is ϵN=maxisupπi[Vπi(o0i,μ^πi,π∗,−iN)−Vπ∗(o0i,μ^π∗N)] _N= _i _π^i[V_π^i(o_0^i, μ^N_π^i,π^*,-i)-V_π^*(o_0^i, μ^N_π^*)]. Theorem 4.5 (N-agent approximation). Under Assumptions 4.1–4.3, let (π∗,μt∗)(π^*,\ _t^*\) be the TMF equilibrium. For any batch size B such that α=BN(ρP+LP)+(1−BN)(ρP0+LP0)<1α= BN( _P+L_P)+(1- BN)( _P_0+L_P_0)<1: ϵN≤CN, _N≤ C N, (11) where C depends on LrL_r, LPL_P, LP0L_P_0, ρP _P, ρP0 _P_0, |||O|, and T, but not on B. Theorem 4.5 guarantees that the TMF equilibrium is an O(1/N)O(1/ N)-approximate Nash equilibrium of the finite-agent game for any batch size satisfying α<1α<1. Together with Theorem 4.4, both the equilibrium and its finite-population guarantee are invariant to the batching protocol, so the batch size can be chosen based on system constraints, provided it satisfies the condition on α. The proof is given in Appendix D. Remark 4.6 (Batch size and passive coupling). The condition α<1α<1 links the minimum number of active agents to the strength of passive coupling: weaker coupling allows smaller batches. Since α interpolates linearly between ρP+LP _P+L_P (at B=NB=N) and ρP0+LP0 _P_0+L_P_0 (at B=0B=0), increasing B reduces α whenever ρP+LP<ρP0+LP0 _P+L_P< _P_0+L_P_0. The condition requires that agents’ transitions are not dominated by population-level coupling, which is the regime where mean-field modeling is appropriate. When ρP+LP<ρP0+LP0 _P+L_P< _P_0+L_P_0, α<1α<1 is equivalent to BN>ρP0+LP0−1ρP0+LP0−ρP−LP. BN> _P_0+L_P_0-1 _P_0+L_P_0- _P-L_P. When idle agents transition independently of μ (LP0≈0L_P_0≈ 0, e.g., remaining at their current observation), the lower bound is non-positive and any B≥1B≥ 1 suffices. Conversely, if the active transition’s dependence on μ is so strong that ρP+LP≥1 _P+L_P≥ 1, then α≥1α≥ 1 for all B and the bound does not apply. In most applications passive coupling is moderate, and the condition permits small batches. 5 TMF Reinforcement Learning Having established the TMF equilibrium and its theoretical properties, we now present a policy gradient algorithm for learning it and prove its convergence. The TMF equilibrium requires a self-consistent policy-trajectory pair, but improving π changes μt\ _t\, which in turn changes what π should be. To resolve this coupling, we propose the TMF Policy Gradient (TMF-PG) algorithm, which alternates between data collection and policy improvement: • Rollout. Execute πθ _θ in the N-agent system for T stages, producing the empirical trajectory μ^t\ μ_t\ and per-agent rewards rtj\r_t^j\ directly from interaction (model-free). This is standard RL data collection. • Policy update. Treating μ^t\ μ_t\ as fixed, compute advantage estimates A^tj=Q^tj−V^tj A_t^j= Q_t^j- V_t^j and update the policy by gradient ascent: θ←θ+α∑t,j∇θlogπθ(atj|otj,μ^t)A^tj.θ←θ+α _t,j _θ _θ(a_t^j|o_t^j, μ_t)\, A_t^j. (12) This reduces to a standard single-agent policy gradient given the fixed trajectory μ^t\ μ_t\. Each agent’s update requires only its own trajectory and μ^t μ_t, so the per-agent computational cost is independent of N. The full pseudocode is given in Algorithm 1 (Appendix A). Convergence. We show that if the policy update at each iteration produces an increasingly accurate best response to the current trajectory—as guaranteed by standard policy gradient convergence—then the alternating iteration converges to the unique TMF equilibrium. Theorem 5.1 (Convergence of TMF-PG). Under the conditions of Theorem 4.4, suppose the backward pass at each iteration k produces a policy πk _k satisfying ‖πk−π(k)‖∞≤ϵk,ϵk→0,\| _k- _ μ^(k)\|_∞≤ _k, _k→ 0, where π(k) _ μ^(k) denotes the exact best response to the current trajectory (k) μ^(k). Then the TMF-PG iterates converge to the unique TMF equilibrium: maxt1(μt(k),μt∗)→0as k→∞, _tW_1( _t^(k), _t^*)→ 0 k→∞, and correspondingly ‖πk−π∗‖∞→0\| _k-π^*\|_∞→ 0. The convergence holds for any batch size B satisfying the condition of Theorem 4.5. The condition ϵk→0 _k→ 0 is achievable in practice: for a fixed trajectory μ^t\ μ_t\, each agent faces a finite-horizon MDP, so running sufficiently many policy gradient steps per iteration drives the policy toward the best response. The outer loop converges because the rollout–best-response alternation is contracting under the monotonicity conditions of Theorem 4.4, and the approximation errors ϵk _k are absorbed as they vanish. The proof is given in Appendix E. 6 Related Work Mean-field MARL. The mean-field approach to MARL was introduced by Yang et al. (2018), who used the mean action a¯ a as the mean field. Subramanian & Mahajan (2019) subsequently used the empirical state-action distribution as the mean-field object, moving beyond a¯ a, but still under synchronous dynamics. Extensions along the spatial dimension include multi-type MF-MARL (Subramanian et al., 2020), which partitions agents by type; major-minor MF-MARL (Cui et al., 2024), which distinguishes influential “major” agents from a homogeneous “minor” population; and graph-structured MFG approaches using graphon (Zhou et al., 2024) and graphex (Fabian et al., 2024) limits. All these works assume synchronous decision-making. Our framework opens the orthogonal temporal dimension by removing this assumption entirely. Asynchronous MARL. Several works address asynchronous execution, but all remain on top of synchronous game models. MacDec-POMDP (Xiao et al., 2020) adds temporally extended macro-actions to Dec-POMDP; ACE (Yu et al., 2023) applies delay randomization to MAPPO; SeqComm (Ding et al., 2023) introduces priority-based communication ordering; STEER (Zhang et al., 2024) decomposes within-step action selection into a Stackelberg hierarchy. These methods engineer around the consequences of asynchrony—variable durations, delays, sequential ordering—but the underlying state transition remains synchronous: all agents must act before the environment advances. Our framework removes this requirement at the model level, providing a mean-field formulation—dynamics, Bellman equation, and equilibrium—that is natively defined for any number of active agents per step, without an underlying synchronous substrate. Mean-field game theory. The population distribution μt _t is a central object in continuous-time MFG theory (Lasry & Lions, 2007; Huang et al., 2006; Carmona & Delarue, 2018), but in a fundamentally different setting: continuous time, infinite populations, and PDE-based analysis. Discrete-time MFG theory (Gomes et al., 2010; Saldi et al., 2018) and its learning algorithms—fictitious play (Perrin et al., 2020), Q-iteration (Anahtarci et al., 2023), policy gradient (Carmona et al., 2019)—all assume synchronous dynamics. Our work addresses a different regime—discrete time, finite populations, asynchronous decision-making—using model-free RL. Approximation theory for MARL. The approximation of finite-N games by mean-field limits has been studied through propagation of chaos results (Carmona & Delarue, 2018; Lacker, 2020). Yardim et al. (2024) show that mean-field RL can be PPAD-hard without structural assumptions. Both lines of work assume synchronous dynamics. Our O(1/N)O(1/ N) bound (Theorem 4.5) establishes the first finite-population approximation guarantee under asynchronous dynamics. 7 Experiments We validate the theoretical findings on two environments: a Sequential Resource Selection Game (SRSG) for clean theoretical verification, and a Dynamic Queueing Game (DQG) that demonstrates practical value in a multi-step asynchronous setting. All experiments use 40 independent seeds; error bars and ± denote one standard deviation. 7.1 Sequential Resource Selection Game (SRSG) To validate robustness to batch size and O(1/N)O(1/ N) concentration, we design a congestion game in which agents arrive in batches, each choosing one of several resources whose reward decreases with congestion. The batch size B can be varied from 11 (fully sequential) to N (fully synchronous). We consider a setting where N agents arrive in batches of size B and irrevocably choose among M=5M=5 resources over T=⌈N/B⌉T= N/B steps. Agent i’s reward upon choosing resource m is rm(μ)=vm−αμ[m]2r_m(μ)=v_m-α\,μ[m]^2, where v=(0.5,0.75,1.0,1.25,1.5)v=(0.5,0.75,1.0,1.25,1.5), α=1.0α=1.0, and μ[m]μ[m] is the fraction of agents already allocated to resource m. The quadratic congestion penalizes overloaded resources, creating a tension between attractive high-value resources and the cost of congestion. We evaluate all policies by per-agent welfare—the average reward across agents—which reflects how efficiently the population spreads across resources: higher welfare means less congestion waste. For reference, welfare equals 0.50.5 when all agents crowd onto the best resource (v5−α=0.5v_5-α=0.5) and approaches 1.51.5 in the uncongested limit. We train the policy using TMF-PG (Algorithm 1) and compare against a Myopic policy that maximizes the instantaneous reward rm(μ)r_m(μ) without anticipating future arrivals. Existing mean-field RL methods require synchronous updates and do not apply here; Myopic ablates the forward planning that distinguishes TMF-PG, so the performance gap isolates the benefit of anticipating the population trajectory. Experiment 1: Robustness across batch sizes (Figure 1). We fix N=100N=100 and vary the batch size B∈1,2,5,10,25,50,100B∈\1,2,5,10,25,50,100\, spanning from fully sequential (B=1B=1) to fully synchronous (B=NB=N). TMF-PG achieves welfare between 1.1091.109 and 1.1581.158 at every B—consistently above 70%70\% of the congestion-free maximum—with less than 5%5\% variation across the entire range. The policy performs equally well whether agents decide one at a time or all at once. By contrast, Myopic welfare depends heavily on B: at B=1B=1, agents arrive one at a time and naturally spread across resources, yielding welfare 1.1071.107 comparable to TMF-PG; at B=100B=100, all agents choose simultaneously, each selects the highest-value resource, and welfare collapses to 0.5000.500. Figure 1: SRSG (N=100N=100): per-agent welfare vs. batch size B. TMF-PG achieves above 70%70\% of the congestion-free maximum at every B; Myopic matches at B=1B=1 but collapses to 0.50.5 when all agents choose simultaneously. Experiment 2: Finite-population accuracy (Figure 2). TMF-PG is trained on an infinite-population model; how accurate is this approximation for finite N? We fix B=1B=1 (fully sequential) and sweep N∈10,20,50,100,200,500,1000,2000N∈\10,20,50,100,200,500,1000,2000\, measuring two indicators. The first is the cross-run welfare standard deviation: we run 100100 simulations with the same policy and record how much per-agent welfare fluctuates—smaller fluctuation means the infinite-population prediction is more reliable. The second is the trajectory prediction error: the L1L_1 distance between the deterministic population trajectory predicted by Equation 3 and the realized μt _t from the N-agent simulation. Both shrink rapidly with N: welfare standard deviation drops from 0.0160.016 (N=10N=10) to 0.0010.001 (N=2000N=2000), and prediction error drops from 0.0190.019 (N=50N=50) to 0.0030.003 (N=2000N=2000), meaning the model tracks the true dynamics to within 0.3%0.3\%. On log-log axes, both decay at least as fast as O(1/N)O(1/ N), consistent with the upper bound of Theorem 4.5. Additional results in Appendix F (Figure 4) confirm that the prediction error remains stable across batch sizes. (a) Welfare standard deviation (b) Trajectory prediction error Figure 2: SRSG (B=1B=1): both welfare standard deviation (a) and trajectory prediction error (b) decay as O(1/N)O(1/ N) (dashed reference line), consistent with Theorem 4.5. Taken together, Experiments 1 and 2 validate the two central predictions of the TMF framework under the contraction condition: performance and approximation quality are both independent of the batch size B, and the finite-population error vanishes at rate O(1/N)O(1/ N). 7.2 Dynamic Queueing Game (DQG) Many resource allocation problems involve repeated decisions over time: an agent who joins a queue today is unavailable for reassignment until service completes. To test whether TMF-PG can exploit such temporal structure, we design a DQG in which agents repeatedly choose servers, wait in queues, and return for reassignment, so that current allocation decisions shape future queue states. We consider a DQG with N agents choosing among M=5M=5 heterogeneous servers over a horizon of H=80H=80 steps. Each server has a quality, a service rate, and a capacity threshold; when the number of queued agents exceeds capacity, the service rate drops sharply (multiplicative cliff factor κ=0.2κ=0.2). Upon completing service, an agent collects a quality-dependent reward and re-enters the free pool. Because only agents who have finished service choose at each step, the effective batch size B varies with the queue dynamics—a natural instance of variable B that the TMF framework handles without modification. The servers are designed with a “honey-trap”: the highest-quality server (quality =3.0=3.0, rate =3.0=3.0) has the smallest capacity (c=3c=3), so agents drawn to its high reward risk triggering the cliff penalty once the queue fills. We evaluate by per-agent reward—total reward summed over all agents and all time steps, divided by N—the multi-step analogue of per-agent welfare in the SRSG. We compare TMF-PG against the same Myopic baseline, which greedily selects the server with the highest immediate expected reward given current loads. In this setting, Myopic systematically overloads the honey-trap server; TMF-PG anticipates the collective load trajectory and spreads allocation to avoid congestion collapse. Experiment 3: Value of forward planning in DQG (Figure 3). We sweep N∈50,100,150N∈\50,100,150\ with capacities scaled linearly (cm∝N/50c_m N/50). TMF-PG achieves 1010–30%30\% higher per-agent reward by distributing load away from the honey-trap server before its queue overflows: at N=50N=50, per-agent reward is 8.298.29 (TMF-PG) vs. 6.386.38 (Myopic); at N=100N=100, 4.594.59 vs. 3.803.80. The gap narrows to +10%+10\% at N=150N=150. With linearly scaled capacities, the cliff threshold grows in proportion to N (e.g., the honey-trap server holds c=9c=9 agents instead of 33), so each agent’s marginal contribution to congestion shrinks as O(1/N)O(1/N) and even Myopic rarely triggers the cliff. Sensitivity analysis (Appendix F, Figure 5) confirms that the advantage is robust across cliff intensities (κ∈[0.05,0.5]κ∈[0.05,0.5]) and horizons (H∈[30,120]H∈[30,120]). Figure 3: DQG: per-agent reward vs. N. TMF-PG avoids the cliff penalty on the honey-trap server by anticipating collective load, yielding 1010–30%30\% higher reward than Myopic. 8 Conclusion In this work, we identified a structural limitation of mean-field RL: the mean action, the standard summary statistic, is undefined whenever some agents do not act, making existing MF-RL methods inapplicable to asynchronous or sequential decision-making. To address this, we constructed the TMF framework from scratch around the population distribution μ—the only mean-field object that remains well-defined, scalable, and sufficient regardless of which agents act. We formalized the TMF dynamic, Bellman equation, and equilibrium concept; proved existence and uniqueness of the equilibrium (Theorem 4.4); established an O(1/N)O(1/ N) finite-population approximation bound that holds regardless of how many agents act per step (Theorem 4.5); and proposed TMF-PG, a policy gradient algorithm that provably converges to the unique equilibrium (Theorem 5.1). Experiments on a resource selection game and a dynamic queueing game confirm that TMF-PG achieves near-identical performance whether one agent or all N act per step, with approximation error decaying at the predicted O(1/N)O(1/ N) rate. Relation to existing practice. It is worth noting that several recent asynchronous MARL methods already rely, implicitly, on population-state information: ACE (Yu et al., 2023) conditions on delayed joint observations, MacDec-POMDP (Xiao et al., 2020) aggregates agent histories through centralized critics, and sequential decision frameworks such as STEER (Zhang et al., 2024) and SeqComm (Ding et al., 2023) condition on predecessors’ actions or communication messages that implicitly encode distributional information. These mechanisms can be viewed as heuristic approximations to the population distribution. Our framework provides a principled explanation for why such approaches work: the population distribution is a sufficient statistic for mean-field interaction under exchangeability, and the equilibrium it induces is robust to the batching protocol. In this sense, TMF offers theoretical grounding for a design pattern that practitioners have already adopted, while also identifying the precise conditions under which the approach is guaranteed to succeed. Future directions. Several extensions are natural. First, combining the population-measure approach (temporal dimension) with structured interaction models such as graphon or graphex limits (spatial dimension) would yield a fully general mean-field framework for networked systems. Second, extending the theory to partial observability—where agents estimate μt _t from local information rather than observing it directly—would broaden applicability. Third, relaxing exchangeability to accommodate heterogeneous agent types within the TMF dynamic would extend the framework to settings where agents differ in capabilities or objectives. References Anahtarci et al. (2023) Anahtarci, B., Kariksiz, C. D., and Saldi, N. Learning mean-field games with discounted and average costs. Journal of Machine Learning Research, 24(316):1–46, 2023. Carmona & Delarue (2018) Carmona, R. and Delarue, F. Probabilistic Theory of Mean Field Games with Applications I-I. Springer, 2018. Carmona et al. (2019) Carmona, R., Laurière, M., and Tan, Z. Linear-quadratic mean-field reinforcement learning: Convergence of policy gradient methods. arXiv preprint arXiv:1910.04295, 2019. Cui et al. (2024) Cui, K., Fabian, C., Tahir, A., and Koeppl, H. Major-minor mean field multi-agent reinforcement learning. In International Conference on Machine Learning, p. 9603–9632. PMLR, 2024. Ding et al. (2023) Ding, Z., Hong, W., Zhu, L., Huang, T., and Lu, Z. Sequential communication in multi-agent reinforcement learning. In International Conference on Learning Representations, 2023. Fabian et al. (2024) Fabian, C., Cui, K., and Koeppl, H. Learning mean field games on sparse graphs: A hybrid graphex approach. In International Conference on Learning Representations, 2024. Gomes et al. (2010) Gomes, D. A., Mohr, J., and Souza, R. R. Discrete time, finite state space mean field games. Journal de Mathématiques Pures et Appliquées, 93(3):308–328, 2010. Huang et al. (2006) Huang, M., Malhamé, R. P., and Caines, P. E. Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle. In Communications in Information and Systems, volume 6, p. 221–252, 2006. Lacker (2020) Lacker, D. On the convergence of closed-loop Nash equilibria to the mean field game limit. The Annals of Applied Probability, 30(4):1693–1761, 2020. Lasry & Lions (2007) Lasry, J.-M. and Lions, P.-L. Mean field games. Japanese journal of mathematics, 2(1):229–260, 2007. Littman (1994) Littman, M. L. Markov games as a framework for multi-agent reinforcement learning. Machine Learning Proceedings, p. 157–163, 1994. Perrin et al. (2020) Perrin, S., Pérolat, J., Laurière, M., Geist, M., Elie, R., and Pietquin, O. Fictitious play for mean field games: Continuous time analysis and applications. In Advances in Neural Information Processing Systems, volume 33, p. 13199–13213, 2020. Saldi et al. (2018) Saldi, N., Başar, T., and Raginsky, M. Markov–Nash equilibria in mean-field games with discounted cost. SIAM Journal on Control and Optimization, 56(6):4256–4287, 2018. Subramanian & Mahajan (2019) Subramanian, J. and Mahajan, A. Reinforcement learning in stationary mean-field games. In International Conference on Autonomous Agents and Multi-Agent Systems, p. 251–259, 2019. Subramanian et al. (2020) Subramanian, S. G., Poupart, P., Taylor, M. E., and Hegde, N. Multi type mean field reinforcement learning. In International Conference on Autonomous Agents and Multi-Agent Systems, p. 411–419, 2020. Xiao et al. (2020) Xiao, Y., Hoffman, J., and Amato, C. Macro-action-based deep multi-agent reinforcement learning. In Conference on Robot Learning, p. 1146–1161. PMLR, 2020. Yang et al. (2018) Yang, Y., Luo, R., Li, M., Zhou, M., Zhang, W., and Wang, J. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, p. 5571–5580. PMLR, 2018. Yardim et al. (2024) Yardim, B., Goldman, A., and He, N. When is mean-field reinforcement learning tractable and relevant? In International Conference on Autonomous Agents and Multi-Agent Systems, 2024. Yu et al. (2023) Yu, C., Gao, X., Liu, W., Xu, J., Yu, Y., and Wang, Y. Asynchronous coordination explorer for multi-agent reinforcement learning. In International Conference on Autonomous Agents and Multi-Agent Systems, 2023. Zhang et al. (2024) Zhang, B., Mao, H., Li, L., Xu, Z., Li, D., Zhao, R., and Fan, G. Sequential asynchronous action coordination in multi-agent systems: A stackelberg decision transformer approach. In International Conference on Machine Learning. PMLR, 2024. Zhou et al. (2024) Zhou, F., Zhang, C., Chen, X., and Di, X. Graphon mean field games with a representative player: Analysis and learning algorithm. In International Conference on Machine Learning. PMLR, 2024. Appendix A Algorithm Algorithm 1 presents the full pseudocode of TMF-PG. Each iteration consists of a rollout (executing the current policy in the N-agent system to collect trajectories and observe μ^t\ μ_t\) followed by a policy update (computing returns and updating the policy by policy gradient). In the convergence analysis, these two phases correspond to the forward map FwdFwd and the backward map BRBR of the operator Γ . Algorithm 1 TMF Policy Gradient (TMF-PG) 0: Initial policy parameters θ0 _0, initial distribution μ0 _0, batch size B, horizon T, number of iterations K, learning rate α 1: for k=0,1,…,K−1k=0,1,…,K-1 do 2: // Rollout: execute policy and collect trajectories 3: Initialize o0i∼μ0o_0^i _0 for all agents i=1,…,Ni=1,…,N 4: μ^0(o)←1N∑i=1N[o0i=o] μ_0(o)← 1N _i=1^N 1[o_0^i=o] 5: for t=0,1,…,T−1t=0,1,…,T-1 do 6: Sample batch ℬt⊆1,…,NB_t \1,…,N\ with |ℬt|=B|B_t|=B 7: for i∈ℬti _t do 8: Sample ati∼πθk(⋅|oti,μ^t)a_t^i _ _k(·|o_t^i, μ_t) 9: Observe reward rtir_t^i and next observation ot+1i∼P(⋅|oti,ati,μ^t)o_t+1^i P(·|o_t^i,a_t^i, μ_t) 10: end for 11: for j∉ℬtj _t do 12: Transition ot+1j∼P0(⋅|otj,μ^t)o_t+1^j P_0(·|o_t^j, μ_t); set rtj←0r_t^j← 0 13: end for 14: μ^t+1(o)←1N∑i=1N[ot+1i=o] μ_t+1(o)← 1N _i=1^N 1[o_t+1^i=o] 15: end for 16: // Policy update: compute returns and update policy 17: Compute returns Gti=∑s≥tγs−trsiG_t^i= _s≥ tγ^s-tr_s^i for all agents i and stages t 18: Compute advantage estimates A^ti A_t^i (e.g., via baseline Vψ(o,μ^t)V_ψ(o, μ_t)) 19: Update: θk+1←θk+α∑t,i∇θlogπθk(ati|oti,μ^t)A^ti _k+1← _k+α _t,i _θ _ _k(a_t^i|o_t^i, μ_t)\, A_t^i 20: end for 21: return πθK _ _K Computational complexity. The rollout simulates N agents for T stages, requiring O(NT)O(NT) transitions per iteration (BTBT active transitions via P and (N−B)T(N-B)T passive transitions via P0P_0). The policy update computes returns and policy gradients in O(NT)O(NT) time. The per-agent complexity is independent of N because the mean-field approximation decouples the agents: each agent’s update depends on its own trajectory and the observed population distribution μ^t μ_t, not on the states of all other agents individually. Appendix B Value Function Sensitivity The following Lipschitz bound on the value function with respect to the population trajectory is used in the proofs of both Theorem 4.4 and Theorem 4.5. Lemma B.1 (Value sensitivity). Under Assumption 4.1, for any fixed policy π and two measure trajectories μt\ _t\, μt′\ _t \ with maxt1(μt,μt′)=d _tW_1( _t, _t )=d: ‖Vπ(⋅,μ)−Vπ(⋅,μ′)‖∞≤LVd,where LV=Lr+γLPRmax/(1−γ)1−γ.\|V_π(·,μ)-V_π(·,μ )\|_∞≤ L_V\,d, L_V= L_r+γ L_PR_ /(1-γ)1-γ. (13) Proof. For a fixed policy π, the Bellman equation gives: Vπ(o,μt)=∑aπ(a|o)[r(o,a,μt)+γ∑o′P(o′|o,a,μt)Vπ(o′,μt+1)].V_π(o, _t)= _aπ(a|o) [r(o,a, _t)+γ _o P(o |o,a, _t)\,V_π(o , _t+1) ]. Taking the difference Vπ(o,μt)−Vπ(o,μt′)V_π(o, _t)-V_π(o, _t ) and adding and subtracting P(o′|o,a,μt)Vπ(o′,μt+1′)P(o |o,a, _t)\,V_π(o , _t+1 ) inside the sum: Vπ(o,μt)−Vπ(o,μt′) V_π(o, _t)-V_π(o, _t ) =∑aπ(a|o)[r(o,a,μt)−r(o,a,μt′)⏟(i) reward difference = _aπ(a|o) [ r(o,a, _t)-r(o,a, _t )_(i) reward difference +γ∑o′[P(o′|o,a,μt)−P(o′|o,a,μt′)]Vπ(o′,μt+1′)⏟(i) transition difference +γ _o [P(o |o,a, _t)-P(o |o,a, _t ) ]\,V_π(o , _t+1 )_(i) transition difference +γ∑o′P(o′|o,a,μt)[Vπ(o′,μt+1)−Vπ(o′,μt+1′)]⏟(i) recursive term]. +γ _o P(o |o,a, _t)\, [V_π(o , _t+1)-V_π(o , _t+1 ) ]_(i) recursive term ]. Taking absolute values and bounding each term: Term (i): reward difference. By Assumption 4.1: |r(o,a,μt)−r(o,a,μt′)|≤Lr1(μt,μt′)≤Lrd.|r(o,a, _t)-r(o,a, _t )|≤ L_r\,W_1( _t, _t )≤ L_r\,d. Term (i): transition difference. We first apply Hölder’s inequality (∑o|aobo|≤‖a‖1‖b‖∞ _o|a_o\,b_o|≤\|a\|_1\,\|b\|_∞) to factor out V: |∑o′[P(o′|o,a,μt)−P(o′|o,a,μt′)]Vπ(o′,μt+1′)|≤∥Vπ∥∞∑o′|P(o′|o,a,μt)−P(o′|o,a,μt′)|. | _o [P(o |o,a, _t)-P(o |o,a, _t ) ]V_π(o , _t+1 ) |≤\|V_π\|_∞ _o |P(o |o,a, _t)-P(o |o,a, _t ) |. On a discrete state space, ∑o′|P(o′)−P′(o′)| _o |P(o )-P (o )| is the L1L_1 distance between two distributions, which equals 1(P(⋅|o,a,μt),P(⋅|o,a,μt′))W_1 (P(·|o,a, _t),\,P(·|o,a, _t ) ). By Assumption 4.1 (LPL_P-Lipschitz): 1(P(⋅|o,a,μt),P(⋅|o,a,μt′))≤LP1(μt,μt′)≤LPd.W_1 (P(·|o,a, _t),\,P(·|o,a, _t ) )≤ L_P\,W_1( _t, _t )≤ L_P\,d. So term (i) is bounded by γ‖Vπ‖∞LPdγ\,\|V_π\|_∞\,L_P\,d. Term (i): recursive term. Denoting δt=‖Vπ(⋅,μt)−Vπ(⋅,μt′)‖∞ _t=\|V_π(·, _t)-V_π(·, _t )\|_∞, this contributes γδt+1γ\, _t+1. Combining. Summing the three contributions: δt≤Lrd+γ‖Vπ‖∞LPd+γδt+1. _t≤ L_r\,d+γ\,\|V_π\|_∞\,L_P\,d+γ\, _t+1. Since ‖Vπ‖∞≤Rmax/(1−γ)\|V_π\|_∞≤ R_ /(1-γ) by the geometric series of discounted rewards (where Rmax=maxo,a,μ|r(o,a,μ)|R_ = _o,a,μ|r(o,a,μ)|), substituting and unrolling the recursion with γ<1γ<1: δt≤(Lr+γLPRmax/(1−γ))d+γδt+1≤Lr+γLPRmax/(1−γ)1−γd=LVd.∎ _t≤ (L_r+γ L_PR_ /(1-γ) )\,d+γ\, _t+1≤ L_r+γ L_PR_ /(1-γ)1-γ\,d=L_V\,d. Appendix C Proof of Theorem 4.4 Theorem 4.4 (Existence and uniqueness). Under Assumptions 4.1–4.3 and the contraction condition (Equation 10), for any batch size B∈1,…,NB∈\1,…,N\, a TMF equilibrium (π∗,μt∗)(π^*,\ _t^*\) exists and is unique. Proof. We first define the forward-backward operator underlying the proof, then establish existence (via Brouwer) and uniqueness (via contraction). C.1 The Forward-Backward Operator Define Γ:Δ()T→Δ()T : (O)^T→ (O)^T as the operator that maps a distribution trajectory μtt=0T\ _t\_t=0^T to a new trajectory Γ(μt)=μt′ (\ _t\)=\ _t \ via: πμ(⋅|o) _μ(·|o) =argmaxπ∑aπ(a|o)[r(o,a,μ)+γ∑o′P(o′|o,a,μ)Vμ(o′)], = *arg\,max_π _aπ(a|o) [r(o,a,μ)+γ _o P(o |o,a,μ)\,V_μ(o ) ], (14) μt+1′(o′) _t+1 (o ) =∑oμt′(o)[BN∑aπμ(a|o)P(o′|o,a,μt)+(1−BN)P0(o′|o,μt)],μ0′=μ0, = _o _t (o) [ BN _a _μ(a|o)\,P(o |o,a, _t)+ (1- BN )P_0(o |o, _t) ], _0 = _0, (15) where VμV_μ is the value function obtained by solving the Bellman equation (Equation 4) given μt\ _t\, and πμ _μ is the corresponding optimal policy. By Assumption 4.1, πμ _μ is LπL_π-Lipschitz in μ. A fixed point of Γ corresponds to a TMF equilibrium (π∗,μt∗)(π^*,\ _t^*\). The operator Γ decomposes as Γ=Fwd∘BR =Fwd , where BR:↦πBR μ _ μ is the best-response map (Equation 14) and Fwd:π↦′Fwd π μ evolves the population distribution under π via the TMF dynamic (Equation 15). We refer to these as the backward pass and forward pass throughout the proofs. C.2 Existence via Brouwer’s Fixed-Point Theorem The operator Γ satisfies the conditions of Brouwer’s fixed-point theorem: 1. Compact convex domain. Δ()T (O)^T is a compact convex subset of ℝ||×TR^|O|× T (since O is finite). 2. Self-mapping. The TMF dynamic (Equation 3) preserves the probability simplex at each step, so Γ maps Δ()T (O)^T into itself. 3. Continuity. VμV_μ is continuous in μ by Assumption 4.1 (Lipschitz continuity of r and P); πμ _μ is continuous in μ by Assumption 4.1 (LπL_π-Lipschitz); FwdFwd is continuous by the Lipschitz property of P and P0P_0. Therefore Γ has at least one fixed point—a TMF equilibrium exists. C.3 Uniqueness via Monotonicity Suppose for contradiction that two distinct TMF equilibria exist: (π,μt)(π,\ _t\) and (π′,μt′)(π ,\ _t \) with d=maxt1(μt,μt′)>0d= _tW_1( _t, _t )>0. Both are fixed points of Γ (Equations 14–15), so at each equilibrium the policy is optimal given the trajectory, and the trajectory is self-consistent under the policy. Step 1: Monotonicity lower bound. Let t¯=argmaxt1(μt,μt′) t= _tW_1( _t, _t ), so that 1(μt¯,μt¯′)=dW_1( _ t, _ t )=d. By Assumption 4.3: ηd2≤∑o(μt¯(o)−μt¯′(o))[Vπ(o,μt¯)−Vπ′(o,μt¯′)].η\,d^2≤ _o ( _ t(o)- _ t (o) ) [V_π(o, _ t)-V_π (o, _ t ) ]. (16) Step 2: Hölder upper bound. By Hölder’s inequality (∑o|aobo|≤‖a‖1‖b‖∞ _o|a_o\,b_o|≤\|a\|_1\,\|b\|_∞), the right-hand side of Equation 16 satisfies: RHS of Equation 16≤d⋅‖Vπ(⋅,μt¯)−Vπ′(⋅,μt¯′)‖∞.RHS of Equation~ eq:mono_lower≤ d·\|V_π(·, _ t)-V_π (·, _ t )\|_∞. Dividing by d>0d>0: ηd≤‖Vπ(⋅,μt¯)−Vπ′(⋅,μt¯′)‖∞.η\,d≤\|V_π(·, _ t)-V_π (·, _ t )\|_∞. (17) Step 3: Value sensitivity upper bound. We bound the value difference by decomposing it via triangle inequality. Adding and subtracting Vπ(⋅,μt¯′)V_π(·, _ t ): ‖Vπ(⋅,μt¯)−Vπ′(⋅,μt¯′)‖∞≤‖Vπ(⋅,μt¯)−Vπ(⋅,μt¯′)‖∞⏟(I) trajectory sensitivity+‖Vπ(⋅,μt¯′)−Vπ′(⋅,μt¯′)‖∞⏟(I) policy sensitivity.\|V_π(·, _ t)-V_π (·, _ t )\|_∞≤ \|V_π(·, _ t)-V_π(·, _ t )\|_∞_(I) trajectory sensitivity+ \|V_π(·, _ t )-V_π (·, _ t )\|_∞_(I) policy sensitivity. (18) Bounding term (I). This is the value sensitivity under the same policy π but different trajectories. By Lemma B.1: ‖Vπ(⋅,μt¯)−Vπ(⋅,μt¯′)‖∞≤LVd.\|V_π(·, _ t)-V_π(·, _ t )\|_∞≤ L_V\,d. Bounding term (I). This is the value difference under the same trajectory μt′\ _t \ but different policies. Since π′π is optimal for μt′\ _t \, we have Vπ′(o,μ′)≥Vπ(o,μ′)V_π (o,μ )≥ V_π(o,μ ) for all o. We now bound this gap. For a fixed trajectory μt′\ _t \, write the Bellman equations for both policies: Vπ′(o) V_π (o) =∑aπ′(a|o)[r(o,a,μ′)+γ∑o′P(o′|o,a,μ′)Vπ′(o′)], = _aπ (a|o) [r(o,a,μ )+γ _o P(o |o,a,μ )\,V_π (o ) ], Vπ(o) V_π(o) =∑aπ(a|o)[r(o,a,μ′)+γ∑o′P(o′|o,a,μ′)Vπ(o′)]. = _aπ(a|o) [r(o,a,μ )+γ _o P(o |o,a,μ )\,V_π(o ) ]. Subtracting, and adding and subtracting ∑aπ(a|o)[⋯Vπ′(o′)] _aπ(a|o)[·s V_π (o )] to separate the policy difference from the value difference: Vπ′(o)−Vπ(o) V_π (o)-V_π(o) =∑a(π′(a|o)−π(a|o))[r(o,a,μ′)+γ∑o′P(o′|o,a,μ′)Vπ′(o′)] = _a (π (a|o)-π(a|o) ) [r(o,a,μ )+γ _o P(o |o,a,μ )\,V_π (o ) ] +γ∑aπ(a|o)∑o′P(o′|o,a,μ′)[Vπ′(o′)−Vπ(o′)]. +γ _aπ(a|o) _o P(o |o,a,μ ) [V_π (o )-V_π(o ) ]. (19) First term (policy difference). The bracketed expression satisfies: |r(o,a,μ′)+γ∑o′P(o′|o,a,μ′)Vπ′(o′)|≤Rmax+γ∥Vπ′∥∞≤Rmax+γRmax1−γ=Rmax1−γ. |r(o,a,μ )+γ _o P(o |o,a,μ )\,V_π (o ) |≤ R_ +γ\,\|V_π \|_∞≤ R_ + γ R_ 1-γ= R_ 1-γ. So the first term is bounded by ‖π′−π‖∞⋅Rmax/(1−γ)\|π -π\|_∞· R_ /(1-γ). Second term (recursive). Let Δ=‖Vπ′−Vπ‖∞ =\|V_π -V_π\|_∞. Since |Vπ′(o′)−Vπ(o′)|≤Δ|V_π (o )-V_π(o )|≤ for all o′o , and π(⋅|o)π(·|o) and P(⋅|o,a,μ′)P(·|o,a,μ ) are probability distributions: γ|∑aπ(a|o)∑o′P(o′|o,a,μ′)[Vπ′(o′)−Vπ(o′)]|≤γ∑aπ(a|o)∑o′P(o′|o,a,μ′)⏟=1⋅Δ=γΔ.γ | _aπ(a|o) _o P(o |o,a,μ ) [V_π (o )-V_π(o ) ] |≤γ _aπ(a|o) _o P(o |o,a,μ )_=1· =γ\, . Combining. Substituting these bounds into Equation 19 and taking supo _o (the LHS becomes supo|Vπ′(o)−Vπ(o)|=Δ _o|V_π (o)-V_π(o)|= ): Δ≤‖π′−π‖∞⋅Rmax1−γ+γΔ⟹(1−γ)Δ≤‖π′−π‖∞⋅Rmax1−γ⟹Δ≤Rmax(1−γ)2‖π′−π‖∞. ≤\|π -π\|_∞· R_ 1-γ+γ\, (1-γ)\, ≤\|π -π\|_∞· R_ 1-γ ≤ R_ (1-γ)^2\,\|π -π\|_∞. By Assumption 4.1, ‖π−π′‖∞≤Lπd\|π-π \|_∞≤ L_π\,d. So term (I) of Equation 18 satisfies: (I)=Δ≤Rmax(1−γ)2Lπd=RmaxLπ(1−γ)2d.(I)= ≤ R_ (1-γ)^2\,L_π\,d= R_ \,L_π(1-γ)^2\,d. Step 4: Contradiction. Substituting both bounds into Equation 17: ηd≤LVd+RmaxLπ(1−γ)2d.η\,d≤ L_V\,d+ R_ \,L_π(1-γ)^2\,d. Dividing by d>0d>0: η≤LV+RmaxLπ(1−γ)2.η≤ L_V+ R_ \,L_π(1-γ)^2. This contradicts the condition in Equation 10. Therefore d=0d=0, and the TMF equilibrium is unique. □ Appendix D Proof of Theorem 4.5 Theorem 4.5 (N-agent approximation). Under Assumptions 4.1–4.3, let (π∗,μt∗)(π^*,\ _t^*\) be the TMF equilibrium. For any batch size B such that α=BN(ρP+LP)+(1−BN)(ρP0+LP0)<1α= BN( _P+L_P)+(1- BN)( _P_0+L_P_0)<1, the exploitability ϵN=maxisupπi[Vπi(o0i,μ^πi,π∗,−iN)−Vπ∗(o0i,μ^π∗N)]≤CN, _N= _i _π^i [V_π^i(o_0^i, μ^N_π^i,π^*,-i)-V_π^*(o_0^i, μ^N_π^*) ]≤ C N, where C depends on LrL_r, LPL_P, LP0L_P_0, ρP _P, ρP0 _P_0, |||O|, and T, but not on B. Proof. The proof follows the propagation-of-chaos framework (Carmona & Delarue, 2018). Unlike the standard synchronous setting, where all N agents update simultaneously in T steps, asynchronous batching produces τ=NT/Bτ=NT/B stages, each updating B agents while the remaining N−BN-B transition passively via P0P_0. We compare two population trajectories: • μt∗ _t^*: the planned trajectory, computed deterministically by the forward model (Equation 3) under the equilibrium policy π∗π^*; • μ^tN μ_t^N: the realized trajectory, the stochastic empirical distribution when N agents actually execute π∗π^*, i.e. μ^tN(o)=1N∑i=1N[oti=o] μ_t^N(o)= 1N _i=1^N 1[o_t^i=o]. The proof proceeds in five steps: reduce exploitability to the gap 1(μ^tN,μt∗)W_1( μ_t^N, _t^*) (Step 0), bound the initial gap (Step 1), analyze per-step error propagation (Step 2), accumulate errors over all time steps (Step 3), and convert to an exploitability bound (Step 4). Step 0: From exploitability to mean-field gap. We show that bounding ϵN _N reduces to bounding 1(μ^tN,μt∗)W_1( μ_t^N, _t^*). Consider any unilateral deviation where agent i switches from π∗π^* to some alternative πiπ^i, and write μ^N,dev μ^N,dev for the empirical trajectory that results (it differs from μ^N μ^N only in agent i’s states). We decompose the deviation gain by inserting the planned trajectory μ∗μ^* as a reference: Vπi(o,μ^N,dev)−Vπ∗(o,μ^N) V_π^i(o, μ^N,dev)-V_π^*(o, μ^N) =[Vπi(o,μ^N,dev)−Vπi(o,μ∗)]⏟(a)+[Vπi(o,μ∗)−Vπ∗(o,μ∗)]⏟(b)+[Vπ∗(o,μ∗)−Vπ∗(o,μ^N)]⏟(c). = [V_π^i(o, μ^N,dev)-V_π^i(o,μ^*) ]_(a)+ [V_π^i(o,μ^*)-V_π^*(o,μ^*) ]_(b)+ [V_π^*(o,μ^*)-V_π^*(o, μ^N) ]_(c). (20) We bound each term separately. Term (a). Agent i’s deviation changes exactly one agent’s state out of N, so the empirical distribution shifts by at most 1/N1/N in Wasserstein distance at each step: maxt1(μ^tN,dev,μt∗)≤maxt1(μ^tN,μt∗)+O(1/N). _tW_1( μ_t^N,dev, _t^*)≤ _tW_1( μ_t^N, _t^*)+O(1/N). Applying Lemma B.1 (Equation 13): |Vπi(o,μ^N,dev)−Vπi(o,μ∗)|≤LV⋅(maxt1(μ^tN,μt∗)+O(1/N)).|V_π^i(o, μ^N,dev)-V_π^i(o,μ^*)|≤ L_V· ( _tW_1( μ_t^N, _t^*)+O(1/N) ). Term (b). Since π∗π^* is the equilibrium policy for the mean-field game under trajectory μ∗μ^*, no deviation can improve the value: Vπi(o,μ∗)−Vπ∗(o,μ∗)≤0.V_π^i(o,μ^*)-V_π^*(o,μ^*)≤ 0. Term (c). Applying Lemma B.1 again: |Vπ∗(o,μ∗)−Vπ∗(o,μ^N)|≤LV⋅maxt1(μ^tN,μt∗).|V_π^*(o,μ^*)-V_π^*(o, μ^N)|≤ L_V· _tW_1( μ_t^N, _t^*). Combining (a)–(c): ϵN≤2LV⋅[maxt1(μ^tN,μt∗)]+O(LV/N), _N≤ 2L_V·E [ _tW_1( μ_t^N, _t^*) ]+O(L_V/N), (21) so bounding [maxt1(μ^tN,μt∗)]E[ _tW_1( μ_t^N, _t^*)] directly yields a bound on ϵN _N. Step 1: Initial error. At t=0t=0, each agent’s state is drawn i.i.d. from μ0 _0, so μ^0N μ_0^N is the empirical distribution of N independent samples. For each state o, μ^0N(o) μ_0^N(o) is a sample mean with variance μ0(o)(1−μ0(o))/N≤1/(4N) _0(o)(1- _0(o))/N≤ 1/(4N) (since p(1−p)≤1/4p(1-p)≤ 1/4 for all p∈[0,1]p∈[0,1]). By Jensen’s inequality ([|X|]≤[X2]E[|X|]≤ E[X^2]): [|μ^0N(o)−μ0(o)|]≤Var[μ^0N(o)]≤12N.E [| μ_0^N(o)- _0(o)| ]≤ Var[ μ_0^N(o)]≤ 12 N. Summing over all o∈o : [1(μ^0N,μ0)]=[∑o|μ^0N(o)−μ0(o)|]≤||2N.E[W_1( μ_0^N, _0)]=E [ _o| μ_0^N(o)- _0(o)| ]≤ |O|2 N. (22) Step 2: Per-step error propagation. We now bound how the gap 1(μ^tN,μt∗)W_1( μ_t^N, _t^*) evolves from step t to t+1t+1. The planned trajectory updates deterministically via the forward model: μt+1∗(o′)=∑oμt∗(o)[BN∑aπ∗(a|o)P(o′|o,a,μt∗)+(1−BN)P0(o′|o,μt∗)]. _t+1^*(o )= _o _t^*(o) [ BN _aπ^*(a|o)\,P(o |o,a, _t^*)+ (1- BN )P_0(o |o, _t^*) ]. In the N-agent system, the realized trajectory instead evolves stochastically: μ^t+1N(o′)=1N∑i=1N[ot+1i=o′], μ_t+1^N(o )= 1N _i=1^N 1[o_t+1^i=o ], where each agent i transitions using the realized distribution μ^tN μ_t^N in place of the planned μt∗ _t^*: active agents transition via P(⋅|oti,ati,μ^tN)P(·|o_t^i,a_t^i, μ_t^N) and passive agents via P0(⋅|oti,μ^tN)P_0(·|o_t^i, μ_t^N). Comparing these two updates, we decompose the gap at step t+1t+1 via the triangle inequality, inserting the conditional mean [μ^t+1N∣μ^tN]E[ μ_t+1^N μ_t^N] as a reference: [1(μ^t+1N,μt+1∗)∣μ^tN] [W_1( μ_t+1^N, _t+1^*) μ_t^N] ≤[1(μ^t+1N,[μ^t+1N∣μ^tN])∣μ^tN]⏟Noise+1([μ^t+1N∣μ^tN],μt+1∗)⏟Bias. ≤ E[W_1( μ_t+1^N,E[ μ_t+1^N μ_t^N]) μ_t^N]_Noise+ W_1(E[ μ_t+1^N μ_t^N], _t+1^*)_Bias. (23) We now bound each term separately. Bias (second term). The conditional mean [μ^t+1N∣μ^tN]E[ μ_t+1^N μ_t^N] and the planned trajectory μt+1∗ _t+1^* differ for two reasons: the transition parameters are evaluated at μ^tN μ_t^N instead of μt∗ _t^*, and the starting distributions μ^tN≠μt∗ μ_t^N≠ _t^* are different. For the parameter perturbation, the Lipschitz condition on P (Assumption 4.1) gives, for each active agent: 1(P(⋅|o,a,μ^tN),P(⋅|o,a,μt∗))≤LP1(μ^tN,μt∗).W_1 (P(·|o,a, μ_t^N),\;P(·|o,a, _t^*) )≤ L_P\,W_1( μ_t^N, _t^*). Similarly, for each passive agent i: 1(P0(⋅|o,μ^tN),P0(⋅|o,μt∗))≤LP01(μ^tN,μt∗).W_1 (P_0(·|o, μ_t^N),\;P_0(·|o, _t^*) )≤ L_P_0\,W_1( μ_t^N, _t^*). For the starting distribution difference, the Dobrushin contraction coefficients ρP _P, ρP0 _P_0 (Assumption 4.2) bound the propagation of the gap μ^tN≠μt∗ μ_t^N≠ _t^*. To separate the two contributions via the triangle inequality, define μ¯t+1(o′)=∑oμ^tN(o)[BN∑aπ∗(a|o)P(o′|o,a,μt∗)+N−BNP0(o′|o,μt∗)], μ_t+1(o )= _o μ_t^N(o)\, [ BN _aπ^*(a|o)\,P(o |o,a, _t^*)+ N-BN\,P_0(o |o, _t^*) ], which applies the planned transition parameters (μt∗ _t^*) to the realized starting distribution (μ^tN μ_t^N). By the triangle inequality: 1([μ^t+1N∣μ^tN],μt+1∗) _1 (E[ μ_t+1^N μ_t^N],\; _t+1^* ) ≤1(μ¯t+1,μt+1∗)+1([μ^t+1N∣μ^tN],μ¯t+1). _1( μ_t+1,\; _t+1^*)+W_1 (E[ μ_t+1^N μ_t^N],\; μ_t+1 ). (24) The first term compares two distributions obtained by applying the same transition (with parameters μt∗ _t^*) to different starting distributions μ^tN μ_t^N and μt∗ _t^*. By the Dobrushin contraction property (Assumption 4.2): 1(μ¯t+1,μt+1∗)≤(BNρP+N−BNρP0)1(μ^tN,μt∗).W_1( μ_t+1,\; _t+1^*)≤ ( BN\, _P+ N-BN\, _P_0 )\,W_1( μ_t^N, _t^*). The second term compares two distributions with the same starting distribution μ^tN μ_t^N but different transition parameters (μ^tN μ_t^N vs. μt∗ _t^*). By the per-agent Lipschitz bounds above: 1([μ^t+1N∣μ^tN],μ¯t+1)≤(BNLP+N−BNLP0)1(μ^tN,μt∗).W_1 (E[ μ_t+1^N μ_t^N],\; μ_t+1 )≤ ( BN\,L_P+ N-BN\,L_P_0 )\,W_1( μ_t^N, _t^*). Combining both terms: 1([μ^t+1N∣μ^tN],μt+1∗)≤[BN(ρP+LP)+N−BN(ρP0+LP0)]1(μ^tN,μt∗).W_1 (E[ μ_t+1^N μ_t^N],\; _t+1^* )≤ [ BN( _P+L_P)+ N-BN( _P_0+L_P_0) ]\,W_1( μ_t^N, _t^*). (25) Noise (first term). Conditionally on μ^tN μ_t^N, the N agents transition independently. The conditional variance of μ^t+1N(o′) μ_t+1^N(o ) for any o′o is: Var[μ^t+1N(o′)∣μ^tN]=1N2∑i=1NVar[[ot+1i=o′]∣oti,μ^tN]≤14N,Var [ μ_t+1^N(o ) μ_t^N ]= 1N^2 _i=1^NVar [ 1[o_t+1^i=o ] o_t^i, μ_t^N ]≤ 14N, (26) since each indicator [ot+1i=o′] 1[o_t+1^i=o ] is Bernoulli with parameter pi∈[0,1]p_i∈[0,1] and variance pi(1−pi)≤1/4p_i(1-p_i)≤ 1/4. For each o′o , applying Jensen’s inequality: [|μ^t+1N(o′)−[μ^t+1N(o′)∣μ^tN]||μ^tN]≤Var[μ^t+1N(o′)∣μ^tN]≤12N.E [| μ_t+1^N(o )-E[ μ_t+1^N(o ) μ_t^N]|\; |\; μ_t^N ]≤ Var[ μ_t+1^N(o ) μ_t^N]≤ 12 N. Summing over all o′∈o , we obtain the per-step noise bound on 1W_1: [1(μ^t+1N,[μ^t+1N∣μ^tN])∣μ^tN] [W_1( μ_t+1^N,E[ μ_t+1^N μ_t^N]) μ_t^N ] =∑o′∈[|μ^t+1N(o′)−[μ^t+1N(o′)∣μ^tN]||μ^tN] = _o E [| μ_t+1^N(o )-E[ μ_t+1^N(o ) μ_t^N]|\; |\; μ_t^N ] ≤∑o′∈12N=||2N. ≤ _o 12 N= |O|2 N. (27) Combined recursion. Substituting Equation 25 and Equation 27 into Equation 23: [1(μ^t+1N,μt+1∗)∣μ^tN]≤[BN(ρP+LP)+N−BN(ρP0+LP0)]1(μ^tN,μt∗)+||2N.E[W_1( μ_t+1^N, _t+1^*) μ_t^N]≤ [ BN( _P+L_P)+ N-BN( _P_0+L_P_0) ]\,W_1( μ_t^N, _t^*)+ |O|2 N. (28) Step 3: Error accumulation. Denote α=BN(ρP+LP)+N−BN(ρP0+LP0)α= BN( _P+L_P)+ N-BN( _P_0+L_P_0) (the coefficient in Equation 28) and let et=[1(μ^tN,μt∗)]e_t=E[W_1( μ_t^N, _t^*)]. Taking unconditional expectations in Equation 28: et+1≤αet+||2N.e_t+1≤α\,e_t+ |O|2 N. (29) Iterating t times: et≤αte0+||2N∑j=0t−1αj=αte0+||2N⋅1−αt1−α.e_t≤α^t\,e_0+ |O|2 N _j=0^t-1α^j=α^t\,e_0+ |O|2 N· 1-α^t1-α. (30) The condition α<1α<1 in Theorem 4.5 ensures that the geometric sum converges. When ρP+LP<ρP0+LP0 _P+L_P< _P_0+L_P_0 (active transitions contract more), solving α<1α<1 for B/NB/N yields the equivalent lower bound BN>ρP0+LP0−1(ρP0+LP0)−(ρP+LP), BN> _P_0+L_P_0-1( _P_0+L_P_0)-( _P+L_P), as stated in Remark 4.6. Under either form, 11−α 11-α is a finite constant independent of T. Since α<1α<1, Equation 30 gives a uniform bound over all t: αt≤1α^t≤ 1 and 1−αt1−α≤11−α 1-α^t1-α≤ 11-α, so et≤e0+||2N(1−α),for all t≥0.e_t≤ e_0+ |O|2 N(1-α), all t≥ 0. Substituting e0≤||2Ne_0≤ |O|2 N from Step 1 (Equation 22): supt≥0et≤||2N+||2N(1−α)=||2N⋅2−α1−α≤CN, _t≥ 0\,e_t≤ |O|2 N+ |O|2 N(1-α)= |O|2 N· 2-α1-α≤ C N, (31) where C=||(2−α)2(1−α)C= |O|(2-α)2(1-α) depends on ρP _P, LPL_P, ρP0 _P_0, LP0L_P_0, and |||O|, but not on T. Step 4: Exploitability bound. To complete the proof, we need to bound [maxt1(μ^tN,μt∗)]E[ _tW_1( μ_t^N, _t^*)] in Equation 21. Since the exploitability involves at most T+1T+1 decision periods, we can pass from supt[⋅] _tE[·] in Equation 31 to [maxt(⋅)]E[ _t(·)]: [max0≤t≤T1(μ^tN,μt∗)]≤∑t=0T[1(μ^tN,μt∗)]≤(T+1)suptet≤(T+1)CN.E [ _0≤ t≤ TW_1( μ_t^N, _t^*) ]≤ _t=0^TE[W_1( μ_t^N, _t^*)]≤(T+1)\, _te_t≤ (T+1)\,C N. This bound is loose: it replaces [maxt]E[ _t] with (T+1)supt[⋅](T+1)\, _tE[·], but since both quantities are O(1/N)O(1/ N), the looseness only affects the constant C′C , not the scaling in N. Substituting this bound into Equation 21: ϵN≤2LV⋅(T+1)CN+O(LV/N)≤C′N, _N≤ 2L_V· (T+1)\,C N+O(L_V/N)≤ C N, (32) where the constant C′C depends on LrL_r, LPL_P, LP0L_P_0, |||O|, and T, but not on B. Since the bound holds for each fixed B with the same constant C′C , it holds uniformly over all B∈1,…,NB∈\1,…,N\. In particular, the result extends to time-varying batch sizes BtB_t, as each stage’s contribution to the recursion depends only on the Lipschitz constants and not on BtB_t. □ Appendix E Proof of Theorem 5.1 Theorem 5.1 (Convergence of TMF-PG). Under the conditions of Theorem 4.4, suppose the backward pass at each iteration k produces a policy πk _k with ‖πk−π(k)‖∞≤ϵk\| _k- _ μ^(k)\|_∞≤ _k and ϵk→0 _k→ 0. Then maxt1(μt(k),μt∗)→0 _tW_1( _t^(k), _t^*)→ 0 and ‖πk−π∗‖∞→0\| _k-π^*\|_∞→ 0. The convergence holds for any B satisfying the condition of Theorem 4.5. Proof. We work in the large-population limit, where the rollout concentrates around the deterministic forward map FwdFwd, yielding a deterministic trajectory (k)=(μ0(k),μ1(k),…,μT(k)) μ^(k)=( _0^(k), _1^(k),…, _T^(k)) rather than a stochastic empirical distribution. The gap between the deterministic trajectory and the finite-N empirical distribution is bounded by Theorem 4.5. In this deterministic setting, each TMF-PG iteration approximately applies the operator Γ=Fwd∘BR =Fwd : the policy update produces an approximate best response πk≈BR((k)) _k ( μ^(k)) with error ϵk→0 _k→ 0, and the rollout produces the next trajectory (k+1)=Fwd(πk) μ^(k+1)=Fwd( _k). We show that these approximate iterations converge to the unique TMF equilibrium ∗ μ^*. The proof proceeds in three steps. Step 1: Γ is continuous. Recall that Γ=Fwd∘BR =Fwd , where BRBR is LπL_π-Lipschitz by Assumption 4.1. Since BRBR is Lipschitz, it suffices to show that FwdFwd is Lipschitz. Consider two policies π, π′π with ‖π−π′‖∞≤ϵ\|π-π \|_∞≤ε, and let =Fwd(π) μ=Fwd(π), ′=Fwd(π′) μ =Fwd(π ). Both trajectories share the same initial condition μ0=μ0′ _0= _0 , so 1(μ0,μ0′)=0W_1( _0, _0 )=0. We derive a per-step recursion bounding 1(μt+1,μt+1′)W_1( _t+1, _t+1 ) in terms of 1(μt,μt′)W_1( _t, _t ) and ϵε, then unroll it to obtain maxt1(μt,μt′)≤LFϵ _tW_1( _t, _t )≤ L_F\,ε. Per-step decomposition. To bound the gap 1(μt+1,μt+1′)W_1( _t+1, _t+1 ) at step t, we introduce an intermediate distribution μ~t+1 μ_t+1, defined as the result of evolving μt′ _t forward one step under π (rather than π′π ). This separates the gap into two sources: (a) the inherited gap from different starting distributions μt _t vs. μt′ _t , and (b) the policy discrepancy from using π vs. π′π on the same μt′ _t . By the triangle inequality: 1(μt+1,μt+1′)≤1(μt+1,μ~t+1)⏟inherited gap (contracts)+1(μ~t+1,μt+1′)⏟policy discrepancy.W_1( _t+1, _t+1 )≤ W_1( _t+1, μ_t+1)_inherited gap (contracts)+ W_1( μ_t+1, _t+1 )_policy discrepancy. Inherited gap (first term). Both μt+1 _t+1 and μ~t+1 μ_t+1 are evolved under the same policy π, but from different distributions μt _t and μt′ _t . By the same per-agent coupling as in the bias bound (Equation 25): 1(μt+1,μ~t+1)≤α1(μt,μt′),W_1( _t+1, μ_t+1)≤α\,W_1( _t, _t ), (33) where α=BN(ρP+LP)+N−BN(ρP0+LP0)<1α= BN( _P+L_P)+ N-BN( _P_0+L_P_0)<1 is the contraction coefficient from Equation 28. Policy discrepancy (second term). Both μ~t+1 μ_t+1 and μt+1′ _t+1 are evolved from the same μt′ _t , but under π vs. π′π . Expanding both using the forward model (Equation 3): μ~t+1(o′) μ_t+1(o ) =∑oμt′(o)[BN∑aπ(a|o,μt′)P(o′|o,a,μt′)+N−BNP0(o′|o,μt′)], = _o _t (o) [ BN _aπ(a|o, _t )\,P(o |o,a, _t )+ N-BN\,P_0(o |o, _t ) ], μt+1′(o′) _t+1 (o ) =∑oμt′(o)[BN∑aπ′(a|o,μt′)P(o′|o,a,μt′)+N−BNP0(o′|o,μt′)]. = _o _t (o) [ BN _aπ (a|o, _t )\,P(o |o,a, _t )+ N-BN\,P_0(o |o, _t ) ]. Since both use the same base distribution μt′ _t and the same population state μt′ _t in both P and P0P_0, the passive terms N−BNP0(o′|o,μt′) N-BNP_0(o |o, _t ) are identical (P0P_0 does not depend on the policy). Subtracting: μ~t+1(o′)−μt+1′(o′)=BN∑oμt′(o)∑a[π(a|o,μt′)−π′(a|o,μt′)]P(o′|o,a,μt′). μ_t+1(o )- _t+1 (o )= BN _o _t (o) _a [π(a|o, _t )-π (a|o, _t ) ]\,P(o |o,a, _t ). Taking the ℓ1 _1 norm over o′o , since μt′(o)≥0 _t (o)≥ 0 and P(o′|o,a,μt′)≥0P(o |o,a, _t )≥ 0, the triangle inequality moves the absolute value inside: 1(μ~t+1,μt+1′) _1( μ_t+1, _t+1 ) =∑o′|μ~t+1(o′)−μt+1′(o′)| = _o | μ_t+1(o )- _t+1 (o ) | ≤BN∑o′∑oμt′(o)∑a|π(a|o,μt′)−π′(a|o,μt′)|P(o′|o,a,μt′) ≤ BN _o _o _t (o) _a|π(a|o, _t )-π (a|o, _t )|\,P(o |o,a, _t ) =BN∑oμt′(o)∑a|π(a|o,μt′)−π′(a|o,μt′)|∑o′P(o′|o,a,μt′)⏟= 1 = BN _o _t (o) _a|π(a|o, _t )-π (a|o, _t )|\, _o P(o |o,a, _t )_=\,1 =BN∑oμt′(o)∑a|π(a|o,μt′)−π′(a|o,μt′)| = BN _o _t (o) _a|π(a|o, _t )-π (a|o, _t )| ≤BN∑oμt′(o)⏟= 1||‖π−π′‖∞=B||Nϵ. ≤ BN _o _t (o)_=\,1\;|A|\,\|π-π \|_∞= B\,|A|N\,ε. (34) Combining and unrolling. Adding the inherited gap (Equation 33) and the policy discrepancy (Equation 34) via the triangle inequality gives the per-step recursion: 1(μt+1,μt+1′)≤α1(μt,μt′)+B||Nϵ.W_1( _t+1, _t+1 )≤α\,W_1( _t, _t )+ B\,|A|N\,ε. (35) Since 1(μ0,μ0′)=0W_1( _0, _0 )=0, unrolling this recursion t times yields: 1(μt,μt′)≤B||Nϵ∑s=0t−1αsfor each t.W_1( _t, _t )≤ B\,|A|N\,ε _s=0^t-1α^s each t. Taking the maximum over t=0,…,Tt=0,…,T and bounding the geometric sum: max0≤t≤T1(μt,μt′)≤B||Nϵ⋅∑s=0T−1αs=B||N⋅1−αT1−αϵ≤B||N(1−α)ϵ=:LFϵ. _0≤ t≤ T\,W_1( _t, _t )≤ B\,|A|N\,ε· _s=0^T-1α^s= B\,|A|N· 1-α^T1-α\,ε≤ B\,|A|N(1-α)\,ε=:L_F\,ε. (36) This establishes that FwdFwd is LFL_F-Lipschitz. Since Γ=Fwd∘BR =Fwd is a composition of two Lipschitz maps (FwdFwd with constant LFL_F and BRBR with constant LπL_π), Γ is Lipschitz with constant LΓ=LFLπL_ =L_F\,L_π, and in particular continuous on the compact set Δ()T (O)^T. Step 2: Trajectory convergence. Let dk:=maxt1(μt(k),μt∗)d_k:= _tW_1( _t^(k), _t^*) denote the gap between the k-th iterate and the equilibrium trajectory. We show dk→0d_k→ 0 by establishing a contracting recursion across iterations. Since (k+1)=Fwd(πk) μ^(k+1)=Fwd( _k) and ∗=Fwd(BR(∗))=Γ(∗) μ^*=Fwd(BR( μ^*))= ( μ^*) (by definition of the TMF equilibrium), Step 1 gives dk+1=maxt1(Fwd(πk)t,Fwd(BR(∗))t)≤LF‖πk−BR(∗)‖∞.d_k+1= _tW_1 (Fwd( _k)_t,\,Fwd(BR( μ^*))_t )≤ L_F\,\| _k-BR( μ^*)\|_∞. (37) By the triangle inequality and the LπL_π-Lipschitz property of BRBR (Assumption 4.1): ‖πk−BR(∗)‖∞≤‖πk−BR((k))‖∞⏟≤ϵk+‖BR((k))−BR(∗)‖∞⏟≤Lπdk.\| _k-BR( μ^*)\|_∞≤ \| _k-BR( μ^(k))\|_∞_≤\, _k+ \|BR( μ^(k))-BR( μ^*)\|_∞_≤\,L_π\,d_k. (38) Substituting Equation 38 into Equation 37: dk+1≤LF(ϵk+Lπdk).d_k+1≤ L_F\,( _k+L_π\,d_k). (39) Recalling LF=B||N(1−α)L_F= B\,|A|N(1-α) from Equation 36 and defining LΓ:=LFLπL_ :=L_F\,L_π: LΓ=B||LπN(1−α),L_ = B\,|A|\,L_πN(1-α), so LΓ<1L_ <1 whenever N>B||Lπ1−αN> B\,|A|\,L_π1-α, which holds in the large-population regime. Equation 39 then becomes the contracting recursion: dk+1≤LΓdk+LFϵk.d_k+1≤ L_ \,d_k+L_F\, _k. (40) Unrolling by induction on k gives dk≤LΓkd0+LF∑j=0k−1LΓk−1−jϵj.d_k≤ L_ ^k\,d_0+L_F _j=0^k-1L_ ^k-1-j\, _j. (41) The first term satisfies LΓkd0→0L_ ^k\,d_0→ 0 since LΓ<1L_ <1. It remains to show that the second term in Equation 41 also vanishes. Fix any δ>0δ>0; we show that the second term is eventually less than δ. Since ϵj→0 _j→ 0 by assumption, we can choose K large enough that ϵj _j is small for all j≥Kj≥ K. Specifically, choose K such that ϵj≤δ(1−LΓ)2LFfor all j≥K. _j≤ δ(1-L_ )2\,L_F all j≥ K. (42) Now split the sum at j=Kj=K. For the terms j≥Kj≥ K, substitute Equation 42 and apply the geometric series formula ∑s=0∞rs=11−r _s=0^∞r^s= 11-r (with r=LΓ<1r=L_ <1): LF∑j=Kk−1LΓk−1−jϵj L_F _j=K^k-1L_ ^k-1-j\, _j ≤δ(1−LΓ)2∑j=Kk−1LΓk−1−j ≤ δ(1-L_ )2 _j=K^k-1L_ ^k-1-j ≤δ(1−LΓ)2⋅11−LΓ=δ2. ≤ δ(1-L_ )2· 11-L_ = δ2. (43) For the terms j<Kj<K, there are only finitely many (at most K), and each carries the factor LΓk−1−jL_ ^k-1-j. Since j≤K−1j≤ K-1 implies k−1−j≥k−Kk-1-j≥ k-K, the entire sum can be bounded by LΓk−KL_ ^k-K times a finite constant independent of k: LF∑j=0K−1LΓk−1−jϵj L_F _j=0^K-1L_ ^k-1-j\, _j =LΓk−K⋅LF∑j=0K−1LΓK−1−jϵj =L_ ^k-K· L_F _j=0^K-1L_ ^K-1-j\, _j ≤LΓk−K⋅LFmaxj<Kϵj1−LΓ. ≤ L_ ^k-K· L_F\, _j<K _j1-L_ . (44) Since LΓk−K→0L_ ^k-K→ 0 as k→∞k→∞, there exists k0k_0 such that Equation 44 is also less than δ/2δ/2 for all k≥k0k≥ k_0. Substituting Equation 43 and Equation 44 into Equation 41: dk≤LΓkd0+δfor all k≥k0.d_k≤ L_ ^k\,d_0+δ all k≥ k_0. Taking k→∞k→∞ and using LΓkd0→0L_ ^k\,d_0→ 0: lim supk→∞dk≤δ. _k→∞\,d_k≤δ. Since δ>0δ>0 was arbitrary, dk→0d_k→ 0. Step 3: Policy convergence. It remains to show ‖πk−π∗‖∞→0\| _k-π^*\|_∞→ 0. Since π∗=BR(∗)π^*=BR( μ^*) by the TMF equilibrium definition (Definition 3.3), the triangle inequality gives: ‖πk−π∗‖∞≤‖πk−BR((k))‖∞+‖BR((k))−BR(∗)‖∞.\| _k-π^*\|_∞≤\| _k-BR( μ^(k))\|_∞+\|BR( μ^(k))-BR( μ^*)\|_∞. The first term is at most ϵk→0 _k→ 0 by the theorem assumption on the backward pass. The second term is at most LπdkL_π\,d_k by the LπL_π-Lipschitz property of BRBR (Assumption 4.1), and dk→0d_k→ 0 by Step 2. Therefore ‖πk−π∗‖∞→0\| _k-π^*\|_∞→ 0. The TMF equilibrium to which the iterates converge is independent of the batch size B (Theorem 4.4), since the Lipschitz constants LPL_P, LP0L_P_0, LπL_π, and the monotonicity constant η are all properties of the game and do not depend on B. □ Remark E.1. Theorem 5.1 establishes convergence in the mean-field limit: as the number of iterations k grows, the trajectory (k) μ^(k) converges to the TMF equilibrium trajectory ∗ μ^* and the policy πk _k converges to π∗π^*. For a finite system with N agents, Theorem 4.5 bounds the gap between the N-agent empirical distribution and the mean-field trajectory under any fixed shared policy by O(1/N)O(1/ N). Combining these two results, after sufficiently many iterations, the N-agent system under the learned policy operates within O(1/N)O(1/ N) of the TMF equilibrium in the Wasserstein metric. Appendix F Additional Experimental Results This appendix provides supplementary experimental results referenced in Section 7. F.1 SRSG: Prediction Error across N×BN× B Figure 4 shows the L1L_1 prediction error for the forward model across the full N×BN× B grid. Figure 4: SRSG: L1L_1 forward prediction error across the N×BN× B grid (40 seeds). For each N, error is nearly constant across B; for each B, error decays as O(1/N)O(1/ N) (dashed reference line). Two key observations confirm Theorem 4.5: 1. Stability across B: Fixing N and varying B, the prediction error is nearly constant. For example, at N=500N=500, the error is 0.0070.007 for B=1,5,10,B=1,5,10, and 2525; only the fully synchronous case (B=NB=N) is slightly higher (0.0090.009), since a single batch offers no averaging across steps. 2. O(1/N)O(1/ N) decay: Fixing B and varying N, the error decreases from ≈0.019≈ 0.019 (N=50N=50) to ≈0.004≈ 0.004 (N=1000N=1000), matching the theoretical rate. F.2 DQG: Sensitivity Analysis Figure 5 examines TMF-PG’s advantage over Myopic under two parameter sweeps, both at N=50N=50: the cliff multiplier κ, which controls how sharply the service rate drops when a server’s queue exceeds its capacity (lower κ = harsher penalty), and the horizon H, the total number of decision steps. (a) Cliff multiplier sweep (H=80H=80) (b) Horizon sweep (κ=0.2κ=0.2) Figure 5: DQG sensitivity analysis (N=50N=50). TMF-PG consistently outperforms Myopic across all tested cliff intensities and horizons. Cliff sensitivity (Figure 5(a)). TMF-PG outperforms Myopic across all tested cliff intensities (κ∈[0.05,0.5]κ∈[0.05,0.5]). The advantage is most pronounced at moderate values (κ=0.2κ=0.2: +30%+30\%), where the penalty is severe enough to punish naive allocation but the problem retains nontrivial strategic structure. At mild cliff (0.050.05: +7%+7\%) the penalty is weak, so even greedy allocation rarely triggers it; at heavy cliff (0.50.5: +10%+10\%) the strong gradient aids reactive avoidance. Across the full range, anticipating future arrivals via the forward model consistently yields higher total reward. Horizon sensitivity (Figure 5(b)). TMF-PG’s advantage holds across all tested horizons (H∈[30,120]H∈[30,120]). At H=30H=30 (+45%+45\%), the advantage is largest because the short horizon amplifies the cost of early misallocation—a poor initial placement cannot be corrected by subsequent service cycles. As the horizon grows, agent cycling dilutes early mistakes, but TMF-PG retains a meaningful edge: +30%+30\% at H=80H=80 and +14%+14\% at H=120H=120. The diminishing but persistent advantage confirms that forward planning remains valuable even as the mixing time of the queueing dynamics increases.