PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear-Quadratic Mean-Field Reinforcement Learning: Convergence of Policy Gradient Methods

René Carmona, Mathieu Laurière, Zongjun Tan

arXiv:1910.04295v2math.OCcs.LG

TL;DR

The paper studies how large cooperative populations can learn policies through mean-field reinforcement learning, including in LQ systems with common noise. It analyzes the control problem and proves convergence results for exact and model-free policy-gradient methods, with numerical evidence of robustness in finite-agent settings.

  • Problem

    The paper addresses how to learn policies for large interacting agent populations, where standard reinforcement-learning algorithms target a single agent and multi-agent models become difficult to analyze.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes discrete-time LQ mean-field control and studies exact and model-free policy gradients, including zeroth-order gradient estimation for model-free methods.

    Source: §1 · pp. 2–3, §4.4 · p. 21

  • Results

    The authors prove global convergence results for exact gradients and two simulator-based gradient estimators, and report numerical robustness for finite-agent models with nonexchangeable agents and noisy dynamics.

    Source: §1 · p. 3

  • Takeaways & Limitations

    A finite population can collaborate to learn a control that is approximately optimal for the mean-field control problem.

    Source: §1 · p. 3

    Although the admissible parameter set Θ is convex, its cost-bounded level set need not be convex.

    Source: §2.3 · p. 8

Abstract

from arXiv · show

We investigate reinforcement learning in the setting of Markov decision processes for a large number of exchangeable agents interacting in a mean field manner. Applications include, for example, the control of a large number of robots communicating through a central unit dispatching the optimal policy computed by maximizing an aggregate reward. An approximate solution is obtained by learning the optimal policy of a generic agent interacting with the statistical distribution of the states and actions of the other agents. We first provide a full analysis this discrete-time mean field control problem. We then rigorously prove the convergence of exact and model-free policy gradient methods in a mean-field linear-quadratic setting and establish bounds on the rates of convergence. We also provide graphical evidence of the convergence based on implementations of our algorithms.

1. Introduction

The paper extends reinforcement learning to cooperative mean-field systems, where a representative agent learns alongside a population distribution. It analyzes a discrete-time LQ mean-field control problem and proves convergence results for policy-gradient methods.

1. Introduction

  • Mean Field Reinforcement Learning extends single-agent reinforcement learning to large interacting populations by having a representative agent learn from both its own feedback and the aggregated population.The finite-agent problem is related to its mean-field approximation, whose convergence depends on the equilibrium concept.Source: §1 · p. 1
  • The study focuses on cooperative LQ models with mean-field interactions and common noise, a setting whose mean-field limit simplifies population interactions but remains difficult to solve generally.In LQ problems, optimality conditions can instead be expressed through algebraic Riccati equations.Source: §1 · p. 2
  • The two model-free algorithms estimate gradients with zeroth-order optimization by evaluating costs at perturbed parameters and combining them into a direction for improving the objective.The paper also treats common noise as a source of exploration, although it complicates convergence analysis.Source: §1 · p. 2
  • The paper proves existence and uniqueness of an optimal control for discrete-time LQ mean-field control with common noise, and shows it is linear in the state and conditional mean.A discrete-time Pontryagin maximum principle yields this form, reducing the search to a parametric control class and linking the mean-field solution to approximately optimal finite-population learning.Source: §1 · p. 3
  • Three global convergence results cover exact policy gradients, an idealized mean-field simulator, and a finite-population simulator, with numerical experiments also supporting robustness to nonexchangeable agents and noisy dynamics.The finite population can learn a control approximately optimal for the mean-field control problem.Source: §1 · p. 3

2. Models

This section defines the finite-agent linear-quadratic model, its common-noise mean-field limit, and conditions for a well-defined control problem and admissible processes. It also specifies admissible parameterized policies and notes that convergence analysis must account for potentially nonconvex objective level sets and a more restrictive admissibility condition than in [21].

2. Models

  • The model uses linear dynamics with idiosyncratic and common noise and a quadratic one-step cost that penalizes deviations from conditional means and aggregate state and action.The dynamics include both individual and mean state/action terms, while the cost separately weights deviations from and levels of the means.Source: §2 · p. 4

2.1. Model for a finite number of agents. `

  • The finite population’s symmetric interactions yield a discounted social LQ control problem, and the representative-agent mean-field model is its limit as N tends to infinity.Finite-sample averaging noise is expected to shrink for large N, although common shocks affect all agents.Source: §2.1 · pp. 4–5, §2.2 · p. 5

2.2. The limit mean-field control model.

  • In the mean-field model, conditional expectations of state and action given the common-noise history enter the dynamics and the expected quadratic cost.The interaction is through both the conditional mean state and conditional mean control.Source: §2.2 · pp. 5–6

2.3. Standing assumptions and well-definiteness.

  • Under H2, every admissible control yields a unique square-integrable state and finite mean-field cost; with H3, finite cost is equivalent to admissibility.H2 imposes discounted stability conditions on A and A + ¯A, while H3 requires positive control-cost matrices.Source: §2.3 · pp. 6–8
  • Admissible feedback parameters enforce discounted stability, making feedback controls admissible; the next section establishes a unique time-invariant linear optimal feedback in state and conditional mean.The control is linear in the state and its conditional mean, with coefficients independent of time.Source: §2.3 · p. 8
  • Under the standing assumptions, the constructed control belongs to Uad and its associated state process satisfies the required state-space condition.The proof uses the stability condition γ‖A − BK‖² < 1 to establish the relevant state-process membership.Source: §2.3 · p. 8
  • A parameter θ = (K, L) defines the policy πθ(x, x̄) = −K(x − x̄) − Lx̄; controls generated by this policy are denoted uθ, with corresponding state Xθ.The collection of admissible parameterized control processes is denoted UΘ.Source: §2.3 · p. 8
  • The parameter set Θ is convex, but its objective level set {θ | J(uθ) ≤ C0} may be nonconvex, motivating level-set considerations for policy-gradient convergence.The paper notes that the importance of level sets for global convergence was discussed for a continuous-time LQMFC problem with common noise [24].Source: §2.3 · p. 8
  • The paper’s admissibility condition is more restrictive than the spectral-radius condition in [21], whose admissible K set is nonconvex.The passage notes that ρ(A − BK) ≤ ‖A − BK‖ and says the admissibility of the optimal control therefore requires further analysis.Source: §2.3 · p. 9

3. Analysis of the MFC Problem

This section analyzes the MFC problem by deriving a Pontryagin-style first-order condition and characterizing optimal controls through a forward-backward system. Under the stated assumptions, it establishes the admissibility, existence, and uniqueness of the optimal linear-feedback control.

3. Analysis of the MFC Problem

  • Under Assumptions (H2) and (H3), the MFC problem has a unique optimal control in linear feedback form, with gains determined by two matrix Riccati equations.The feedback is linear in the state and its mean.Source: §3 · p. 9

3.1. Admissibility of the optimal control.

  • Under Assumptions (H2) and (H3), the optimal feedback parameter is admissible, and its policy process belongs to the admissible control set.The result establishes both parameter admissibility and admissibility of the corresponding control process.Source: §3.1 · pp. 10–11

3.2. Duality and Pontryagin Maximum Principle.

  • Under (H2), each admissible state process has a unique adjoint; the Gateaux derivative yields a necessary stationarity condition for an optimal control.The condition is B^T p_t + 2R u_t + B̄^T p̄_t + 2R̄ ū_t = 0 for every t.Source: §3.2 · pp. 12, 14
  • For an optimal control, the Pontryagin condition is B^T p_t + B̄^T p̄_t + 2R u_t + 2R̄ ū_t = 0, P-a.s., for every t ≥ 0.The directional derivative of the cost in every admissible perturbation direction must be nonnegative.Source: §3.2 · p. 14

3.4. Proof of Theorem 8.

  • Under Assumptions (H2) and (H3), Theorem 8’s feedback control is optimal and unique for the MFC problem.The policy is linear in the deviation from the conditional mean and in the conditional mean state.Source: §3.3 · p. 15, §3.4 · p. 17

3.3. Identification of the optimal control.

  • A solution of the forward-backward system yields an optimal admissible control, whose state and unique adjoint process are identified.The resulting control is admissible and optimal for the MFC problem.Source: §3.3 · pp. 16–17

4. Policy gradient algorithms

This section develops policy-gradient methods for searching admissible control parameters θ=(K,L) to approximate an optimal parameter, including model-based and model-free algorithms. It establishes convergence guarantees for model-free methods using exact-mean MKV and finite-population simulators.

4.1. Reformulation of the MFC problem

  • The cost separates as C(K,L)=Cy(K)+Cz(L), reducing optimization over Θ to independent problems for K and L.The separation follows from the auxiliary processes being independent and Θ being the product of their admissible parameter sets.Source: §4.1 · pp. 18–19

4.2. Additional notations

  • Non-degenerate sub-Gaussian noise supports convergence analysis without assumptions on initial states, while dependent quadratic-form entries and unbounded noise require more delicate arguments.The passage contrasts this setting with noise-free arguments requiring non-degenerate bounded-support initial perturbations.Source: §4.2 · p. 19

4.3. Exact PG for MFC

  • Exact policy gradient converges globally under (H2)–(H4) and a sufficiently small learning rate, with cost nonincreasing from C0 at every iteration.The theorem also ensures the iterates remain admissible.Source: §4.3 · pp. 20–21

4.4. Model free PG for MFC with an MKV simulator

  • The MKV-simulator method estimates gradients from sampled, truncated costs using perturbation directions; suitable truncation horizon T, sample count M, and radius τ yield a target-precision estimator.The estimator is biased, and the method aims to compute the optimal parameter without using model knowledge.Source: §4.4 · pp. 21–22

4.4. Model free PG for MFC with an MKV simulator.

  • With an MKV simulator, model-free policy gradient reaches an ε-approximation to optimal cost in k = O(log(1/ε)) iterations with high probability.The guarantee applies under the stated learning-rate and simulation-parameter conditions and maintains admissible parameters with bounded cost.Source: §4.4 · pp. 23–24

4.5. Model-free PG for MFC with a population simulator.

  • The population simulator uses state and social-cost sample averages from N homogeneous agents, all applying the same perturbed control, rather than exact mean processes.The passages describe this simulator as more realistic but less powerful than the MKV simulator, which generates exact means.Source: §4.5 · pp. 24–25
  • The population-simulator scheme achieves global linear convergence in social cost, reaching ε-accuracy with high probability under the theorem’s agent-count, learning-rate, and simulation-parameter conditions.The method approximates the mean-field cost and sampled population policy gradient using an N-agent simulator.Source: §4.5 · p. 26
  • The authors expect the population-simulator convergence theorem may hold without the noise non-degeneracy assumption, because finite-population sample means remain stochastic even without common noise.This is presented as an expectation, not as a proved result.Source: §4.5 · p. 27

5. Proofs of the technical results from Section 4.3

This section proves technical lemmas adapted from [21] to account for idiosyncratic and common noise in the state dynamics.

5. Proofs of the technical results from Section 4.3

  • The proofs adapt lemmas from [21] to handle idiosyncratic and common noise, proving only results for process y and control parameter K because processes y and z are strongly similar.The authors include the proofs to make the paper self-contained.Source: §5 · p. 27

5.1. Cost expression and gradient expression.

The section represents costs through value functions and discrete-time Lyapunov equations, then relates cost gradients and cost changes to the variance matrix. These expressions provide the basis for evaluating and approximating policy costs and gradients.

5.1.1. Cost expressions.

  • The auxiliary cost uses the quadratic form f(ξ,K,Q,R) = ξᵀ(Q + KᵀRK)ξ, with expectations taken over idiosyncratic and common noise.The cost and value-function expressions are presented for two processes with respective dynamics and initial values.Source: §5.1.1 · pp. 27–28
  • The value functions can be computed from solutions to discrete-time Lyapunov equations, and the cost C_y(K) is expressed as the expected value function.The cost expression is given for random initial states.Source: §5.1.1 · pp. 27–28

5.1.2. Gradient expression.

  • The cost gradient ∇KC_y(K) is expressed in terms of the variance matrix Σ_K, which is central to its approximation.The passage says gradient approximation should hinge on estimating Σ_K.Source: §5.1.2 · p. 28

5.1.3. Cost variation expression.

  • The section gives a cost-variation expression for changing K to K1, with ΔK defined as K1 − K.The stated variation formula involves E_K, Σ_K1, and P_y, though the supplied equation is incomplete.Source: §5.1.3 · p. 28

5.2. Solution of the discrete-time Lyapunov equations.

For admissible controls, the discrete-time Lyapunov equations have unique positive-definite solutions. The Riccati-derived controls are admissible because their associated linear systems are stable.

5.2. Solution of the discrete-time Lyapunov equations.

  • Every admissible control has a unique positive-definite solution pair for the discrete-time Lyapunov equations.The solutions follow from the corresponding stable closed-loop matrices and positive-definite cost matrices.Source: §5.2 · pp. 28–29
  • The Riccati-derived matrices satisfy the Lyapunov equations for K* and L*, and the resulting control θ* is admissible.The argument establishes stability for both associated linear systems.Source: §5.2 · p. 29

5.3. Perturbation analysis.

Section 5.3 bounds how changes in the control parameter affect the variance matrix, the DLE solution, and the policy gradient. These perturbation estimates are stated for sufficiently small changes.

5.3.1. Perturbation of the variance.

  • The variance-matrix perturbation is controlled through the operators F_K and T_K when the change in K is sufficiently small.Lemma 37 bounds the operator norms and their perturbation; Lemma 38 applies these bounds to the variance matrices.Source: §5.3.1 · pp. 30–31

5.3.2. Perturbation of the DLE solution.

  • The difference between DLE solutions at K and K1 is bounded by a K-dependent factor times the size of the parameter change.The stated condition is fvar(K)||K1-K|| <= 1.Source: §5.3.2 · p. 31

5.3.3. Perturbation of the gradient.

  • When fvar(K)||K1-K|| <= 1, the gradient difference is bounded by fgrad(K)||K1-K||.This gives a local perturbation bound for the policy gradient.Source: §5.3.3 · p. 31

5.4. Admissibility of perturbed control parameters.

This section shows that a sufficiently small perturbation of a stable control parameter preserves the stability condition used to define admissibility.

5.4. Admissibility of perturbed control parameters.

  • The section frames the result as preservation of admissibility under sufficiently small perturbations of both K and L.The stated conclusion concerns θ1=(K1,L1) remaining in Θ.Source: §5.4 · p. 32
  • If γ||A-BK||^2 < 1 and fvar(K)||K1-K|| <= 1, then γ||A-BK1||^2 < 1.Thus the stated perturbation radius preserves this stability condition for K1.Source: §5.4 · p. 32
  • The proof uses a convex ball around K and continuity to rule out a point in that ball where the stability condition fails.The argument connects the boundary estimate for the variance to the stability condition.Source: §5.4 · p. 32

5.5. Proof of Proposition 20.

The proof establishes a Polyak–Łojasiewicz condition for the cost and derives a gradient-based bound on the cost gap. It also uses a comparison control chosen so that the advantage quantities attain their lower bounds.

5.5. Proof of Proposition 20.

  • The proof also gives a bound linking the cost gap C_y(K)-C_y(K*) to the squared Frobenius norm of the policy gradient.The displayed coefficient includes ||Σ_K*||, λ_min(R), and λ_min(Σ_K).Source: §5.5 · p. 33
  • The cost C_y satisfies a ν_y-PL condition with ν_y=4λ_min(R)(λ_1^y)^2/||Σ_K*||.The stated conclusion uses the lower bound on λ_min(Σ_K) from Lemma 36.Source: §5.5 · p. 33
  • For a comparison control K1, the advantage quantities attain their lower bounds, yielding a comparison with C_y(K)-C_y(K*).The construction uses R>0 and P_K^y>0.Source: §5.5 · p. 33

5.6. Proof of Proposition 21.

The proof obtains the local smoothness inequality for C_y by considering a gradient step and applying the preceding gradient and advantage bounds. It also identifies coefficient bounds needed for the exact policy-gradient descent analysis.

5.6. Proof of Proposition 21.

  • The proof takes a gradient step ∆K=-η∇_K C_y(K) with η>0 when deriving the local smoothness result.The step is substituted into the gradient formula before applying Lemma 33.Source: §5.6 · p. 33
  • Combining the gradient argument with Lemma 33 yields the local smoothness inequality (71) for C_y.This is the stated conclusion of the proof.Source: §5.6 · p. 33
  • Bounds on λ_var,y and λ_hess,y are needed for the convergence analysis of the exact PG descent algorithm 23.The passage identifies these coefficients as those introduced in Proposition 21.Source: §5.7 · p. 33

5.7. Perturbation analysis bounds.

Under the stated parameter and cost bound, the section gives bounds on variation, gradient norm, and parameter norm, with analogous bounds for the z functions.

5.7. Perturbation analysis bounds.

  • For θ ∈ Θ with C(θ) ≤ C0, fvar(K) is bounded by hsmall-pert,y(C0).Source: §5.7 · p. 33
  • Under the same condition, the gradient norm ∥∇K Cy(K)∥ is bounded by hgrad,y(C0).Source: §5.7 · p. 33
  • Under the same condition, ∥K∥ is bounded by hK(C0), and analogous bounds hold for the z functions after the stated replacements.Source: §5.7 · pp. 33–34

5.8. Perturbations of the cost function.

The section bounds how costs and gradients change under parameter perturbations, including corresponding cost bounds for the combined K,L setting.

5.8. Perturbations of the cost function.

  • When fvar(K)∥K1 − K∥ ≤ 1, the cost change is at most hcost,y(C0)∥K1 − K∥.Source: §5.8 · p. 35
  • For combined K,L perturbations, the cost-bound constant is defined as the sum of the y- and z-cost constants.Source: §5.8 · p. 35
  • With the stated sub-gaussian norm bounds, the cost and gradient differences are bounded proportionally to ∥∆K∥.Source: §5.8 · p. 35

6. Proofs of technical results from Section 4.4

This section develops derivative-free gradient estimation through smoothing and proves approximation-error bounds for perturbation, truncation, and simulator sampling. It shows how choices of truncation horizon, perturbation radius, and perturbation size can make the approximated policy gradient close to the exact gradient with high probability.

6.1. Intuition for zeroth order optimization.

  • Gaussian smoothing expresses a gradient using function values at random perturbations, motivating exact, perturbed, truncated, and sampled policy-gradient estimators.The section introduces these estimators to analyze how Algorithm 1's sampled gradient approximates the exact policy gradient.Source: §6.1 · pp. 35–36

6.2. Approximation by a smoothed cost.

  • With bounded cost, a sufficiently small perturbation radius and enough independent directions make the perturbed policy gradient approximate the exact gradient to target precision with high probability.The lemmas give conditions on the radius and sample count for a specified precision and failure probability.Source: §6.2 · pp. 36–37

6.3. Approximation by a truncated cost.

  • The cited lemma setups require bounded cost C(θ) ≤ C0: Lemma 47 uses any ε > 0 with T ≥ 2 and T ≥ φ_truncation(ε), while Lemma 48 uses T ≥ max{2, φ_trunc,T(ε, τ, C0)}.Source: §6.3 · pp. 38–39

6.4. Costs with MKV simulator.

  • The proofs establish that quadratic forms of sub-Gaussian states are sub-exponential and provide bounds for simulator-based costs and sampled-gradient approximation.The sampled-direction probability bound is stated for independent perturbation directions, with probability taken over simulator randomness rather than direction randomness.Source: §6.4 · pp. 39–40
  • The concentration bound for dependent-coordinate quadratic forms uses sub-exponential Matrix Bernstein rather than Hanson–Wright or classical bounded-variable Bernstein.The proof obtains the tail bound using a discount coefficient γ.Source: §6.4 · pp. 40–41
  • With perturbation size M large enough, the sampled policy gradient is within ε of the truncated policy gradient with probability at least 1 − δ_sample.Lemma 52 gives the guarantee for independently and uniformly sampled perturbation directions, subject to its stated conditions.Source: §6.4 · p. 41
  • With sufficiently large T and M and sufficiently small τ, Algorithm 1’s approximated policy gradient is close to the exact policy gradient with high probability.The stated guarantee applies under the paper’s specified parameter conditions.Source: §6.5 · p. 42

6.5. Proof of Proposition 25.

  • The quantities ϕpert,radius (126), ϕpert,size (127), ϕtrunc,T (136), and ϕsample,size (143) are polynomial in pd, ℓ, C0, pλ1, zq−1, Cinit,noise, ε^-1, τ^-1, and model parameters defined in Sections 6.2, 6.3, and 6.4.Source: §6.5 · p. 42

7. Proofs of technical results from Section 4.5

The technical proofs construct auxiliary N-agent costs and establish bounds connecting social-cost gradient estimators to the exact policy gradient.

7. Proofs of technical results from Section 4.5

  • The proof section compares Algorithm 2’s model-free population gradient estimator with the exact policy gradient using perturbed and truncated social costs.Source: §7.1 · p. 42, §7.2 · p. 43

7.1. Auxiliary costs for the N-agent problem.

  • For the N-agent problem, auxiliary processes define costs that can be expressed using matrices solving the DLEs.Source: §7.1 · pp. 42–43

7.2. Proof of Proposition 28.

  • The Proposition 28 proof establishes bounds for the social-cost gradient estimators and uses a sample-size condition for the perturbation directions.Source: §7.2 · pp. 43–44

7.3. Proof of Proposition 29.

  • The Proposition 29 proof is presented as an immediate consequence of Lemmas 53 and 46.Source: §7.3 · p. 44

8. Numerical Results

The simulations test model-free policy gradients in one-dimensional mean-field models, including heterogeneous finite populations. Learned controls approach the relevant mean-field or population social-cost optima, while heterogeneity and the discount factor affect the approximation and convergence.

8. Numerical Results

  • The numerical example uses one-dimensional state and action spaces, with heterogeneous agents modeled by sampling q^(n) uniformly from [q−h, q+h].The heterogeneity factor h bounds the coefficient deviation from q.Source: §8 · p. 45, §8.1 · p. 45

8.1. Details on the numerical results.

  • For 5000 iterations, model-free PG took roughly 10 hours with the MKV simulator and 48 hours with the N-agent population simulator at N=10.Displayed curves average 10 realizations; shaded regions, when present, show mean ± standard deviation.Source: §8.1 · p. 45

8.2. Simulation with model-free PG algorithms.

  • For N>1, both simulators learn controls with approximately optimal mean-field cost, while populations learn approximately optimal own social cost even at N=1.A single agent cannot learn K, whereas N=2 converges almost as well as N≥10 but more slowly.Source: §8.2 · pp. 45–46, Figure 1 · p. 46

8.3. Approximate optimality of the MFC for the N´agent problem.

  • Although heterogeneous N-agent and MKV optimal controls differ, their social costs are almost the same and approach the theoretical MKV social cost, with a small heterogeneity-related discrepancy.The control-coefficient gap decreases with N but does not vanish for heterogeneous agents.Source: §8.3 · pp. 46–47, Figure 3 · p. 48
  • As heterogeneity decreases, the social-cost difference between N-agent and MKV controls declines, and policy-gradient relative errors concentrate toward the mean-field case.The reported comparisons include heterogeneity decreasing from 0.4 to 0.1 and from 0.1 to 0.Source: §8.3 · p. 47

8.4. Effect of the discount coefficient γ.

  • At γ=0.5, about 100 iterations reach 10^-3 relative error in mean-field cost, compared with 3000 iterations at γ=0.9.The paper notes that higher γ makes learning harder and requires more perturbation directions and a longer truncated horizon.Source: §8.4 · pp. 47–48

Related papers

Loading 1910.04295v2…