PaperlayerView exact revision on arXiv

Source-linked AI summary

Full error analysis of policy gradient learning algorithms for exploratory linear quadratic mean-field control problem in continuous time with common noise

Noufel Frikha, Huyên Pham, Xuanye Song

arXiv:2408.02489v1math.OCstat.ML

TL;DR

The paper addresses convergence and sample complexity for policy-gradient learning in infinite-horizon exploratory LQ mean-field control with common noise. It derives an entropy-regularized policy and analyzes exact and model-free gradient descent, reporting global linear convergence and polynomial sample complexity for the model-free algorithm.

  • Problem

    Convergence analysis for RL in mean-field control remains in its infancy, particularly for learning policies and value functions defined over probability measures.

    Source: §1 · p. 3

  • Method

    The paper derives a Riccati-based optimal randomized policy and studies policy-gradient methods, using two-point estimates from trajectory and population-distribution samples in the model-free setting.

    Source: §1 · pp. 3–4

  • Results

    The model-free analysis establishes global linear convergence with polynomial computational sample complexity, while the exact gradient-descent method also has a convergence guarantee.

    Source: §1 · p. 4, §3.2 · p. 11

  • Takeaways & Limitations

    The analyzed policy-gradient algorithms have convergence guarantees for exploratory LQ mean-field control with common noise and entropy regularization.

    Source: §1 · pp. 3–4

    The formulation assumes unique positive-definite algebraic Riccati solutions; positive definiteness of M̂ under the stated construction requires d0 ≥ d − 1.

    Source: §2.1 · p. 6

Abstract

from arXiv · show

We consider reinforcement learning (RL) methods for finding optimal policies in linear quadratic (LQ) mean field control (MFC) problems over an infinite horizon in continuous time, with common noise and entropy regularization. We study policy gradient (PG) learning and first demonstrate convergence in a model-based setting by establishing a suitable gradient domination condition.Next, our main contribution is a comprehensive error analysis, where we prove the global linear convergence and sample complexity of the PG algorithm with two-point gradient estimates in a model-free setting with unknown parameters. In this setting, the parameterized optimal policies are learned from samples of the states and population distribution.Finally, we provide numerical evidence supporting the convergence of our implemented algorithms.

1 Introduction

The paper studies policy-gradient learning for exploratory infinite-horizon LQ mean-field control with common noise, addressing limited convergence analysis for RL in this setting. It derives an entropy-regularized optimal policy and analyzes model-based and model-free convergence.

1 Introduction

  • RL for mean-field control must learn policies and value functions on an infinite-dimensional space of probability measures, while convergence analysis remains in its infancy.The paper focuses on infinite-horizon continuous-time LQ mean-field control with common noise, using randomized policies and entropy regularization to encourage exploration.Source: §1 · p. 3
  • The paper studies policy-gradient methods for exploratory LQ mean-field control in continuous time, with common noise and entropy regularization.It places its work alongside discrete-time common-noise results [6] and continuous-time results without entropy regularization [23].Source: §1 · pp. 3–4
  • The paper derives the optimal randomized solution using coupled algebraic Riccati equations, extending [2] to include entropy regularization.It parameterizes Gaussian policy means with two matrix-valued coefficients and shows the resulting cost satisfies gradient domination.Source: §1 · pp. 3–4
  • The model-free analysis accounts for perturbation, horizon truncation, time and particle discretization, statistical, and optimization errors, establishing global linear convergence with polynomial computational sample complexity.The paper also gives convergence guarantees for gradient descent in exact and model-free settings.Source: §1 · p. 4

Notations.

  • The notation defines vector scalar products and matrix inner products, and identifies symmetric, nonnegative, and positive-definite matrix sets.The matrix inner product is M : N = tr(MN^⊺).Source: Notations · p. 5

2 Problem formulation

The problem is an infinite-horizon stochastic control problem over randomized feedback policies, with costs regularized by entropy. Its model-free formulation parameterizes Gaussian policies and separates optimization over state deviations and conditional means.

2.1 Setup and preliminaries

  • The setup uses independent Brownian motions for idiosyncratic and common noise, and denotes conditional expectation given the common-noise filtration by E0[·].The dynamics also involve constant matrices B, B̄, D, γ, and γ0.Source: §2.1 · p. 5
  • The objective minimizes a quadratic cost with entropy regularization over randomized controls with feedback densities and finite second moments.The stated cost weights include Q, Q̄, and R, with Q and Q + Q̄ positive definite.Source: §2.1 · pp. 5–6
  • Assumption 2.1 requires unique positive-definite Riccati solutions; positive definiteness of M̂ under the stated construction requires the augmented initial-data matrix to have rank d.The text states this rank condition requires d0 ≥ d − 1.Source: §2.1 · p. 6
  • Under Assumption 2.1, the optimal randomized control has feedback form and its cost is expressed using the positive-definite solutions K and Λ of the coupled Riccati equations.The stated optimal cost is J(π*; λ) = K : M + Λ : M̂ + υ(λ).Source: §2.1 · p. 6

2.2 Model free perspective and reparametrization

  • When dynamics parameters are unknown, the Riccati-based optimal policy cannot be implemented directly, motivating the model-free formulation.The unknown parameters are B, B̄, D, γ, and γ0.Source: §2.2 · p. 7
  • The randomized policy is parameterized as Gaussian, with its mean linear in the state deviation from the conditional mean and in the conditional mean itself.The two matrix-valued coefficients are θ and ζ.Source: §2.2 · p. 7
  • The state deviation and conditional-mean processes depend separately on θ and ζ, allowing the parameterized cost to be decomposed into separate minimizations.The minimizations are restricted to sets on which the problems are well-posed.Source: §2.2 · pp. 8–9
  • The parameterized cost functions have Lyapunov-equation representations, and at the optimal parameters their matrices recover the coupled Riccati solutions and optimal cost.The text identifies Kθ* = K and Λζ* = Λ.Source: §2.2 · pp. 7, 9

3 Model-based PG algorithm

The model-based policy-gradient method uses exact gradients to learn optimal parameters and offers an alternative to solving the Riccati system. Its convergence analysis establishes gradient domination and global linear convergence under a suitable constant step size.

3 Model-based PG algorithm

  • Exact-gradient descent offers an alternative to solving the computationally intensive Riccati system, and its convergence result is dimension-free.The analysis assumes full knowledge of model parameters and starts from a stabilizing initial parameter.Source: §3 · p. 10

3.1 Gradient domination condition

  • The cost functions satisfy a Polyak-Lojasiewicz gradient-domination condition on their parameter sets.This condition is used to analyze convergence in the nonconvex setting.Source: §3.1 · p. 10

3.2 Global convergence of model-based PG algorithm

  • With a suitably chosen common constant step size, exact gradient descent stays in the selected level sets and converges linearly.The method truncates the stabilizing sets to compact subsets where the gradients are Lipschitz continuous, allowing the step size to remain fixed across iterations.Source: §3.2 · pp. 11, 14

4 Model-free PG algorithm

The model-free method replaces unavailable exact gradients with a population-simulator-based stochastic policy-gradient algorithm. Theorem 4.1 gives convergence conditions requiring suitable choices of perturbation radius, horizon, time grid, particle count, and gradient-estimation samples.

4.1 Notations

  • The model-free objective combines the two policy parameters Θ = (θ, ζ) in H, and its bounded level sets R(b) are compact.The paper defines the total gradient as the pair of gradients with respect to θ and ζ, and removes a known λ-dependent constant from the objective for the level-set analysis.Source: §4.1 · pp. 14–15

4.2 Model-free PG algorithm with population simulator

  • Because the exact gradient is unavailable, a stochastic population simulator approximates the controlled dynamics and cost for the model-free policy-gradient algorithm.The simulator uses a finite time grid and interacting-agent trajectories under randomized actions.Source: §4.2 · pp. 15–16
  • Algorithm 1 estimates the gradient with a biased estimator based on simulated average costs from perturbed feedback parameters.The average cost is computed over a finite horizon using population samples; the resulting gradient estimate is used to update both policy parameters with a positive learning rate.Source: §4.2 · pp. 16–17
  • Theorem 4.1 guarantees convergence of the model-free policy-gradient sequence for a prescribed accuracy when the perturbation radius is sufficiently small and the horizon, grid size, particle count, and sample count are sufficiently large.The result also specifies a constant learning rate; the listed conditions give the required parameter choices.Source: §4.2 · pp. 17–18

5 Numerical example

A one-dimensional numerical example illustrates convergence in both model-based and model-free policy gradient algorithms. In the model-free experiment, gradient estimates cluster near exact gradients, and the cost error and error rate vanish after approximately 200 iterations.

5 Numerical example

  • The numerical analysis uses a one-dimensional example, with both algorithms initialized at (−2, −2) and optimal parameters (−0.00126, −0.00255).The corresponding optimal costs are J1(θ∗) = 0.005051 and J2(ζ∗) = 0.010205.Source: §5 · p. 19

5.1 Model-based algorithm

  • In the model-based experiment, the value-function error and error rate converge to zero after roughly 200 iterations for different learning rates.The parameter sequence and the relative errors of J1 and J2 are plotted in Figures 1 and 2.Source: Figure 1 · p. 19, §5.1 · p. 20, Figure 2 · p. 20

5.2 Model-free algorithm

  • Figure 3 presents 100 gradient estimations against exact ∇θJ(θ, ζ) and ∇ζJ(θ, ζ); most points cluster around the dashed exact-gradient lines, within 10^-2 above and below.The authors suggest that, with high probability, gradient-estimation error is controlled within 10^-2.Source: Figure 3 · p. 21, §5.2 · p. 21
  • In the model-free experiment, both cost error and error rate vanish after approximately 200 iterations.Figure 5 plots the cost error and error rate against iteration number.Source: Figure 5 · p. 22, §5.2 · p. 22

A Explicit solution to LQ MFC

The appendix gives an explicit optimal randomized control for the LQ mean-field problem under a unique-positive-definite-solution assumption for coupled Riccati equations. Its proof uses a martingale argument and establishes optimality through a nonnegative term that vanishes at the proposed policy.

A Explicit solution to LQ MFC

  • Under the assumption that the coupled Riccati equations have unique positive definite solutions, the optimal randomized control is Gaussian and in feedback form.The stated feedback uses the state and its conditional mean; the setup assumes one-dimensional Brownian motions, with a multidimensional extension noted separately.Source: A Explicit solution to LQ MFC · pp. 23, 27
  • The proof uses a martingale approach and shows that a nonnegative term vanishes for the proposed policy, yielding optimality.The argument invokes strict positive-definiteness of R and solutions to the coupled equations.Source: A Explicit solution to LQ MFC · pp. 23, 26, 27
  • When R, Q, and Q + Q̄ are positive definite, a positive definite Riccati solution is guaranteed, while the stated assumption is needed for uniqueness.This is the qualification given in Remark A.1.Source: A Explicit solution to LQ MFC · p. 27
  • The proof also notes that the result can extend to multidimensional Brownian motions.The multidimensional case is referred to Remark 5.2 in [2].Source: A Explicit solution to LQ MFC · p. 27

B.1 Proof of Proposition 2.1

The appendix proofs use Lyapunov equations and stability to establish positive definite solutions, then rewrite the parameter-dependent equations in standard form. The second proof applies Itô’s rule and the cost definitions to complete its argument.

B.1 Proof of Proposition 2.1

  • Lemma B.1 concerns solutions to an ODE for symmetric matrix-valued functions and is cited when functions solve an ODE of the form (B.1).Source: §B.1 · pp. 27–28
  • The proof of Proposition 2.1 uses Lyapunov equations and stability of the associated matrices to establish positive definite solutions.It expresses (2.16) in standard Lyapunov form and uses integration by parts.Source: §B.1 · pp. 28–29

B.2 Proof of the Proposition 2.2

  • For Proposition 2.2, the parameter-dependent equations are written in standard form and have unique positive definite solutions when (θ, ζ) lies in S × Ŝ.The proof then uses Itô’s rule and the definitions of J1 and J2.Source: §B.2 · p. 29

C.1 Proof of Proposition 3.1

This section presents proof material supporting the policy-gradient convergence analysis, including regularity results and model-free convergence arguments. The Proposition 3.1 fragment establishes a high-probability event and applies Lemma D.1 over a specified range of ρ, ending with an induction step whose resulting statement is not included.

C.1 Proof of Proposition 3.1

  • The proof derives the gradient of J1 by differentiating Kθ’s Lyapunov equation, using a matrix-valued differentiability result for Kθ.The proof states that the corresponding argument for J2 is similar.Source: §C.1 · pp. 31–33

C.2 Proof of Theorem 3.2

  • A perturbation identity for J1, together with stability of B − β/2 Id + Dθ and the Lyapunov-equation solution, yields the proof of the Polyak–Łojasiewicz inequality.The proof treats J2 by similar reasoning.Source: §C.2 · pp. 33–34

C.3.3 Proof of Proposition 3.3

  • The proof of Proposition 3.3 uses the gradient representation from Proposition 3.1 and the preceding bounds to establish Lipschitz regularity of ∇J1 and ∇J2.The setup states that it proves the claim for ∇J1, treating ∇J2 similarly.Source: §C.3 · p. 35, §C.3.3 · p. 40

C.3.1 Auxiliary results

  • On the cost sublevel sets, the auxiliary bounds control the norms of θ, Kθ, and Σθ, with analogous bounds stated for ζ, Λζ, and ˆΣζ.The displayed bounds for Kθ and Σθ use J1(θ) ≤ ℓ and the minimum eigenvalues of M and Q, respectively.Source: §C.3.1 · pp. 35–36

C.3.2 Lipschitz regularity of Σθ, ˆΣζ, Kθ and Λζ.

  • The regularity proof establishes Lipschitz continuity of Kθ and Λζ on their sublevel sets and handles Σθ and ˆΣζ with similar arguments.The remaining technical details for Λζ are omitted.Source: §C.3.2 · pp. 38–40

D.1 Strategy of proof of Theorem 4.1

  • The model-free proof strategy controls perturbations of the policy parameters so perturbed policies remain in an enlarged admissible region.The strategy combines high-probability gradient-estimation events with the Polyak–Łojasiewicz inequality to ensure progress when the cost gap exceeds ε.Source: §D.1 · pp. 41–42

D.2 Proof of Theorem 4.1

  • The proof of Theorem 4.1 decomposes the algorithm’s gradient estimates into perturbation, truncation, time-discretization, and state-trajectory randomness components.It defines finite-horizon truncated and time-discretized cost functionals, with action execution noise in the discretized dynamics.Source: §D.2 · pp. 42–43
  • The proof bounds the probability of M1 ∩ M2 below by 1 − 4(d ˜ε)^−d, then invokes Lemma D.1 for ρ ∈ (0, 4/9ˇL(b)).The excerpt states that the induction step eventually yields a conclusion, but does not supply it.Source: §D.2 · p. 44

D.3 Analysis of the single step GD algorithm

The section analyzes a general single-step gradient-descent update and establishes conditions under which the update remains in the admissible parameter region. It also gives a Lipschitz bound for the gradient and identifies a positive range of step sizes.

D.3 Analysis of the single step GD algorithm

  • The gradient of J is Ľ(b)-Lipschitz on R(b), with Ľ(b) defined from the component-gradient Lipschitz constants.The constants for ∇J1 and ∇J2 are taken on S(b) and Ŝ(b), respectively.Source: §D.3 · p. 45
  • The maximal feasible step size ρmax is positive and finite for the considered update direction.The passage attributes positivity to the descent-direction condition and finiteness to compactness of R(b).Source: §D.3 · p. 45
  • For Θ in R(b) and a direction G satisfying (D.6), the update Θρ=Θ−ρG remains in R(b) for 0<ρ<2ν1ν2Ľ(b).The stated range follows from the bound on ρmax.Source: §D.3 · pp. 45–46

D.4 Error analysis of J and its gradient

This section establishes error bounds for the objective and gradient quantities used in the analysis. Its subsections address gradient estimation, finite-horizon cost approximation, time discretization, and statistical errors.

D.4 Error analysis of J and its gradient

  • The section bounds five terms in the error decomposition for the population gradient estimator, with probability at least 1−(d/ε)−d uniformly over Θ in R(b).The stated bounds include constants with at most polynomial growth in b, 1/r, and 1/ε.Source: §D.4 · pp. 47–48

D.4.4 Proof of Proposition D.5

  • The statistical gradient-estimator analysis uses finite sub-Gaussian norms for the sampled processes to derive its probability bounds.The proposition states bounds for all ε>0 under restrictions on the smoothing radius r and sample-size parameters.Source: §D.4 · p. 48, §D.4.4 · pp. 59–60

D.4.1 Proof of Proposition D.2

  • The gradient-estimation proof smooths J by averaging over independent uniform perturbations, then controls Monte Carlo and smoothing errors.The passage identifies the estimator as a Monte Carlo approximation to the gradient of the smoothed objective.Source: §D.4.1 · pp. 48–49

D.4.2 Proof of Proposition D.3

  • Finite-horizon cost differences are bounded by constants depending on b and λ, with the constants non-decreasing in b.The cited lemma supplies positive constants for the bound over R(b).Source: §D.4.2 · pp. 49, 51

D.4.3 Proof of Proposition D.4

  • The weak time-discretization error for the cost is bounded by a constant with at most polynomial growth in the parameter norm.The proof combines weak-approximation and Riemann-integral bounds; compactness lets the constant depend on b over R(b).Source: §D.4.3 · p. 55

D.4.5 Proof of Proposition D.6.

The proof combines bounds for empirical and discretized quantities to complete the stated error estimate. It also applies the bound to perturbed parameters lying in an expanded admissible region.

D.4.5 Proof of Proposition D.6.

  • The empirical-noise estimate uses E|ξ̄N_l|²=d/N for each time index l.This variance identity is used in the preceding bounds combined by the proof.Source: §D.4.5 · pp. 64–65
  • The proof combines the preceding upper bounds and completes the estimate with a right-hand side uniformly bounded by a constant depending only on b.Compactness of R(b) is used to obtain the uniform bound.Source: §D.4.5 · p. 65
  • The bound for the perturbed parameters follows from (D.8) because the perturbations lie in R(2b).The proof applies the earlier estimate after placing Θi in the expanded region.Source: §D.4.5 · p. 65

Related papers

Loading 2408.02489v1…