PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-Free Mean-Field Reinforcement Learning: Mean-Field MDP and Mean-Field Q-Learning

René Carmona, Mathieu Laurière, Zongjun Tan

arXiv:1910.12802v2math.OCcs.LG

TL;DR

Model-free learning for mean-field control must address a population distribution that enters the system alongside common noise and randomized actions. The paper formulates a mean-field MDP, relates its policies and values to MFC, and develops tabular and deep RL methods. It proves equality of open-loop and closed-loop optimal values and existence of an optimal stationary closed-loop policy.

  • Problem

    Model-free mean-field learning seeks solutions from sampled trajectories without access to transition and cost functions, while the population distribution remains part of the control problem.

    Source: §1 · p. 2

  • Method

    The paper formulates an MFMDP with population distribution as its state, connects its policies and value functions to MFC, and adapts tabular and deep RL methods.

    Source: §1 · p. 3

  • Results

    The paper proves equality of MFC open-loop and closed-loop optimal values and establishes existence of an optimal stationary closed-loop policy.

    Source: §4.2 · p. 16

  • Takeaways & Limitations

    Tabular Q-learning can use simplex discretization, while the deep RL method handles continuous spaces without discretizing the mean-field state.

    Source: §1 · p. 3

    The optimal MFMDP policy is pure, so the corresponding MFC policy does not depend on the common policy randomization.

    Source: §4.2 · p. 16

Abstract

from arXiv · show

We study infinite horizon discounted Mean Field Control (MFC) problems with common noise through the lens of Mean Field Markov Decision Processes (MFMDP). We allow the agents to use actions that are randomized not only at the individual level but also at the level of the population. This common randomization allows us to establish connections between both closed-loop and open-loop policies for MFC and Markov policies for the MFMDP. In particular, we show that there exists an optimal closed-loop policy for the original MFC. Building on this framework and the notion of state-action value function, we then propose reinforcement learning (RL) methods for such problems, by adapting existing tabular and deep RL methods to the mean-field setting. The main difficulty is the treatment of the population state, which is an input of the policy and the value function. We provide convergence guarantees for tabular algorithms based on discretizations of the simplex. Neural network based algorithms are more suitable for continuous spaces and allow us to avoid discretizing the mean field state space. Numerical examples are provided.

1. Introduction

The paper addresses model-free learning for cooperative mean-field control with common noise and population-level action randomization. It connects this setting to mean-field MDPs and develops theoretical results and RL methods.

1. Introduction

  • Model-free mean-field learning seeks solutions from sampled trajectories without access to transition or cost functions, extending reinforcement-learning ideas beyond single-agent MDPs.Mean-field approximations replace pairwise interactions with interactions between a representative agent and the population distribution.Source: §1 · p. 2
  • The framework connects MFC open- and closed-loop policies with Markov policies for a mean-field MDP whose state is the population distribution.The model includes idiosyncratic and common noise, along with action randomization at both the individual and population levels.Source: §1 · p. 3
  • The paper proves a dynamic programming principle for the MFMDP, equality of open-loop and closed-loop MFC values, and existence of an optimal stationary closed-loop policy.It also proves a dynamic programming principle for the MFMDP state-action value function and proposes tabular and deep RL methods.Source: §1 · p. 3
  • The paper uses simplex discretization for tabular learning and neural networks to handle continuous spaces without discretizing the mean-field state.Its numerical examples illustrate features of the MFMDP with common noise and randomized actions.Source: §1 · p. 3

2. Model Description and Notations

The model describes an infinite population of interacting agents through individual and population-level randomness. Its setup motivates a mean-field control problem in which the state-action distribution participates in the dynamics.

2.1. Probabilistic set-up of the MFC model.

  • The MFC model specifies state and action spaces, idiosyncratic and common noise, a system function, a bounded one-stage cost, and a discount factor.The system function evolves an agent's state from its state, action, mean-field interaction term, and two noise terms.Source: §2.1 · pp. 3–4

2.1.1. Motivation from Finitely Many Player Models.

  • In the limiting formulation, the control objective depends on the joint state-action law, making the dynamics McKean–Vlasov rather than an ordinary MDP.The formulation is motivated by conditional independence of individual state evolutions as the population size tends to infinity.Source: §2.1.1 · p. 4
  • The finite-agent motivation has a central unit randomize a policy for the population while individual agents sample their actions, leaving population-level randomization in the infinite-population limit.The model also allows a common random environment, which affects all agents.Source: §2.1.1 · p. 5

2.1.2. Back to the MFC problem formulation.

  • The probabilistic setup separates idiosyncratic noise, common noise, individual action randomization, and central-unit policy randomization as independent sources.Atomless randomization spaces provide uniform random variables, and the Blackwell-Dubins function samples from a specified probability distribution using such a variable.Source: §2.1.2 · pp. 5–6

2.2. Probabilistic framework and classes of policies.

The framework distinguishes actions from randomized controls and separates information available to an individual agent from information used by the population-level controller. It defines state evolution and two policy classes for the MFC model.

2.2.1. Filtrations, action processes, and control processes.

  • The framework distinguishes level-0 agent actions and controls from level-1 objects in the lifted stochastic optimization model.Actions are realizations of controls, and the control process is adapted to its designated filtration.Source: §2.2 · p. 6, §2.2.1 · p. 7
  • A level-0 mixed control is a random probability measure on the action space, while an action process realizes that control through individual randomization.The paper states that realizations of the same control process have matching conditional distributions for bounded measurable tests.Source: §2.2.1 · p. 7

2.2.2. Conditional distribution and state process.

  • The state process is defined from an initial state distribution and an action process, with its conditional state distribution taken relative to common noise and common randomization.The system function describes state evolution using the state, action, mean-field interaction term, and noise sources.Source: §2.2.2 · pp. 7–8

2.2.3. Open-loop and closed-loop policies.

  • An open-loop policy maps its specified information history to a distribution over actions, whereas a closed-loop Markov strategy maps the agent's state, population distribution, and common policy randomization to such a distribution.Actions under a closed-loop policy are sampled from the policy's distribution using individual randomization.Source: §2.2.3 · p. 8

2.3. Optimization and value functions.

This section introduces action-process values and the optimal values associated with open-loop and closed-loop policies.

2.3. Optimization and value functions.

  • For a level-0 action process, the value function Jα is defined on initial state distributions.The value is well-defined because the one-stage cost is measurable and bounded.Source: §2.3 · p. 9
  • The value Jα(μ) depends only on the sequence of one-dimensional marginal distributions of the state-action process.Source: §2.3 · p. 9
  • The optimal open-loop and closed-loop value functions are defined as infima of policy values over their respective policy classes.Source: §2.3 · p. 9

3. Mean-Field MDP

The paper lifts mean-field control to an MDP whose state is the population distribution and whose feasible actions are distributions over state-action pairs consistent with that state. Under the stated assumptions, its value function satisfies a dynamic programming principle and admits an optimal stationary pure policy.

3.1. Mean-field MDP framework.

  • The MFMDP uses the population distribution as its state and a distribution over state-action pairs as its action, constrained to have the current state as its first marginal.This lift lets the mixed closed-loop policy value be viewed as an MDP value function.Source: §3.1 · p. 10

3.2. Assumptions and optimization problem for MFMDP.

  • H1 supplies continuity conditions for the DPP analysis, while H2 assumes compact state and action spaces for optimal-policy existence.Under H1, the lifted system function is continuous for fixed common noise and the one-stage cost is bounded and lower semi-continuous.Source: §3.2 · p. 11

3.3. Dynamic Programming principle for MFMDP.

  • Under H1 continuity and H2 compactness, the MFMDP's optimal value is the unique bounded lower semi-continuous solution of its dynamic programming equation.The Bellman operator is a strict contraction on bounded lower semi-continuous functions.Source: §3.3 · pp. 12–13
  • Under H2, the MFMDP has an optimal stationary pure Borel-measurable policy.The paper establishes the DPP for Borel-measurable mixed Markov policies as well as existence of an optimal pure stationary policy.Source: §3.3 · pp. 12–13

4. Relations between the models

Common randomization supports value-preserving correspondences between MFC closed-loop policies and MFMDP policies, including stationary policies. The paper uses these links to establish equality of optimal open-loop and closed-loop MFC values and existence of an optimal stationary closed-loop policy.

4.1. Relations between MFC closed-loop policies and MFMDP policies.

  • With common randomization, MFC closed-loop and MFMDP policies match values policy by policy, including in the stationary case.The paper contrasts this policy-by-policy identity with [33], which proves equality of optimal values without central randomization.Source: §4.1 · pp. 14, 16

4.2. Relations between MFC closed-loop and open-loop policies.

  • Under H1 and H2, the original MFC has an optimal stationary closed-loop Markov policy.The result follows by transferring an optimal pure stationary MFMDP policy through the policy correspondence.Source: §4.2 · p. 16
  • Under H1, the optimal open-loop and closed-loop MFC values are equal, with the proof linking policy values through the MFMDP before taking optima.The proof derives inequalities between the optimal values and uses the MFMDP value equality to show they are equal.Source: §4.2 · pp. 16–17

5. Mean-Field Q-Learning

This section develops model-free mean-field Q-learning, establishing a Bellman characterization of the optimal state-action value function and tabular convergence guarantees for mixed and pure controls using simplex discretization. It then turns to deep reinforcement learning for continuous settings where discretization is limiting.

5.1. State-action value function.

  • Under (H1) and (H2), the optimal state-action value function is the unique fixed point of a strict-contraction Bellman operator.Its minimum over feasible actions equals the optimal state value, and a measurable minimizing selector exists.Source: §5.1 · pp. 18–20

5.2. Controls for finite state and action spaces.

  • For finite state and action spaces, distributions are represented by simplexes, and two model-free algorithms are built around the optimal state-action value function.The section defines a transformed value function over population distributions and strategy functions to express the Bellman equation in this representation.Source: §5.2 · pp. 20–21

5.3. Simplex discretization and tabular MFQ-learning.

  • After discretizing the simplexes, tabular Q-learning converges for both mixed and pure level-0 controls; for pure controls, the optimizer also converges.Source: §5.3 · p. 21

5.3.1. Q-learning with controls that are mixed at level-0.

  • For mixed level-0 controls, projection onto finite simplex subsets yields a finite MDP whose Q-table approximates the original value function and is shown to converge under regularity and coverage assumptions.The stated assumptions include bounded Lipschitz costs, Lipschitz transitions in expectation and optimal values, and finite covering time.Source: §5.3.1 · pp. 22–23
  • Under H3–H5 and polynomial visit-count learning rates, tabular Q-learning on discretized state and action simplexes achieves a high-probability uniform Q-function error bound after enough episodes.The discretization contributions to the error vanish as the simplex approximations are refined, and the target accuracy can be reduced by increasing the episode count.Source: §5.3.1 · p. 23

5.3.2. Q-learning with controls that are pure at level-0.

  • For pure level-0 controls, Theorem 36 gives an analogous high-probability uniform Q-function guarantee without an εA-discretization error.Unlike the mixed-control method, this approach does not approximate P(A) with an εA-net, so its error bound is independent of εA.Source: §5.3.2 · pp. 26–27
  • Under action-gap assumption H6, Corollary 37 gives an optimizer guarantee, with softmin regularizing the best action predicted by the estimated Q-function.The action-gap condition separates the best from the second-best action values.Source: §5.3.2 · pp. 26–27

5.4. Deep reinforcement learning for MFMDP.

  • Deep RL replaces costly simplex tabulation with function approximation, using finite-dimensional mean-field representations and DDPG actor–critic networks for continuous state and action spaces.Discretizing P(A) can grow exponentially with the size of A, while P(S) is infinite-dimensional; the described DDPG method adds Gaussian action noise for exploration and target networks for stability.Source: §5.4 · pp. 27–28

6. Numerical Examples

The numerical examples apply tabular Q-learning and DDPG to cyber security, target-distribution planning, and swarm motion. Learned controls reproduce benchmark behavior or approach the specified target in the reported settings.

6.1. Example 1: Cyber security model.

  • The tabular Q-learner approximately matches the benchmark value function and distribution flows across three cyber-security initial conditions.The benchmark is computed by an ODE method; the tabular state space uses a discretized simplex.Source: §6.1 · p. 29, Figure 1 · p. 30, Figure 2 · p. 30
  • With common noise, DDPG drives cyber-security distributions from test and training initial conditions toward a configuration with no defended agents and roughly 0.43 undefended infected and 0.57 undefended susceptible agents.The distributions oscillate around that configuration, and trajectories from a uniformly discretized simplex concentrate near it over time.Source: §6.1 · p. 31, Figure 4 · p. 32, Figure 5 · p. 32

6.2. Example 2: Discrete distribution planning.

  • For discrete distribution planning, DDPG brings tested distributions close to the target, including when common noise is rather strong.Training runs are truncated at 100 time steps; target matching generally requires individual-level action randomization in this setup.Source: §6.2 · p. 33

6.3. Example 3: Swarm motion.

  • In swarm motion, after 160 episodes DDPG drives Gaussian initial distributions toward the analytical stationary distribution and learns an approximate stationary optimal control to maintain that regime.The model uses a Monte Carlo particle environment and a histogram representation of the population distribution.Source: §6.3 · p. 34
  • The swarm-motion initial-distribution control is not expected to match the optimal ergodic control, which applies after the distribution reaches the ergodic regime.The learned control for the initial distribution is shown only for comparison.Source: §6.3 · p. 34

Appendix A. Auxiliary results for Section 2

The auxiliary results establish properties of control realizations and the induced population dynamics. They also provide regularity results for the MFMDP transition and cost functions.

Appendix A. Auxiliary results for Section 2

  • Any level-0 control process has a level-0 action-process realization, and bounded functions of the action have the same expectation across its realizations.The appendix also expresses a realization through a conditional distribution of actions.Source: Appendix A · p. 40
  • For a fixed open-loop policy, the law of the random measure of states and actions does not depend on which realization of its generated action process is used.Source: Appendix A · p. 40
  • Under assumption H1, the MFMDP transition is Borel measurable and continuous in its state-action variables for fixed common noise, while its one-stage cost is bounded and lower semi-continuous.Source: Appendix A · p. 41
  • Two state-action process pairs generated by the same policy and initial population state have state processes with matching laws.The proof proceeds by induction over time.Source: Appendix A · p. 41

Appendix B. Proofs for Section 4.1

The appendix proves the stated property (19) inductively, using independence of the next common-noise term and the conditional-probability relation established in Lemma 23.

Appendix B. Proofs for Section 4.1

  • The proof extends property (19) from time n to n+1 by matching the state law and then the joint law with the accompanying measure.The argument uses independence of the next common-noise term, the tower property, and Lemma 23.Source: Appendix B · p. 42
  • The induction concludes by applying the shared regular version of the conditional probability to obtain property (19) at n+1.Source: Appendix B · p. 42

Appendix C. Proofs for Section 4.2

The proof constructs an open-loop policy from a closed-loop-generated process while preserving the associated state and action trajectories.

Appendix C. Proofs for Section 4.2

  • The constructed level-0 control is adapted to the common filtration and represented by measurable functions, yielding an open-loop policy whose state process is associated with the same action process.The proof uses this construction to relate the open-loop policy value to the value of the original policy.Source: Appendix C · p. 43

Appendix D. Disintegration of kernels

Appendix D defines compositions of measures and probability kernels with kernels, producing measures or kernels on product spaces. The definitions specify their action through non-negative measurable functions.

Appendix D. Disintegration of kernels

  • Composing a probability measure P with a kernel K gives a measure on the product space C × D.The definition evaluates this measure on non-negative measurable functions of (x, y).Source: Appendix D · p. 43
  • Composing kernels μ and K gives a kernel from G to the product space C × D.Here μ maps G to probability measures on C, while K is indexed by G and C.Source: Appendix D · p. 43
  • The composition’s evaluation uses the integral of f(x, y) against K(s, x, dy).This is the integrand shown for non-negative measurable f on C × D.Source: Appendix D · p. 43

E.1. Proof of Theorem 36.

The proof bounds the error between projected and original state-action value functions by controlling learning error and the effects of simplex discretization. It uses finite-state Q-learning convergence and regularity assumptions to establish these bounds.

E.1. Proof of Theorem 36.

  • With assumptions H3 and H5 and the chosen learning rates, finite state-action Q-learning bounds the learned Q-function error with probability at least 1 − δ.The proof invokes asynchronous Q-learning results with polynomial learning rates and an episode count of order (34).Source: §E.1 · pp. 43–44
  • Projecting the mean-field state onto the discretized simplex perturbs the value function, with the proof bounding that error using Lipschitz continuity and the simplex discretization properties.The transition is projected at each step; the final projection comparison uses assumptions H3 and H4.Source: §E.1 · pp. 44–45
  • The projected and original state-action value functions differ by at most a bound proportional to the simplex discretization error εS.The stated bound includes γ/(1 − γ) and a Lipschitz constant for the state value function.Source: §E.1 · pp. 44–45

E.2. DDPG algorithm.

Algorithm 2 adapts DDPG to MFC, with actor and critic networks trained from sampled transitions. Its output is a strategy function for the central planner represented by the target actor network.

E.2. DDPG algorithm.

  • The algorithm returns a central-planner strategy represented by the target network π1.It initializes actor and critic parameters, copies them to target networks, and runs for a specified number of episodes.Source: §E.2 · p. 45
  • Each transition stores the projected population state, action, cost, and next projected state, then minibatches are sampled from the replay buffer.The algorithm repeats this interaction within each episode for T steps.Source: §E.2 · p. 45
  • The critic is updated by minimizing a loss, the actor by a sampled policy gradient, and both target networks by soft updates.The target updates use τ for the online-network contribution.Source: §E.2 · p. 45
Loading 1910.12802v2…