Mean-field Markov decision processes with common noise and open-loop controls

1 Introduction

• The CMKV-MDP models mean-field interactions on states and actions with common noise and infinite-horizon optimization over open-loop controls.The framework is motivated by social planners coordinating large populations when individual states may be unobservable but environmental noises are observable.Source: §1 · pp. 2–3
• The paper proves conditional propagation of chaos for the N-agent model and, under Lipschitz assumptions on transitions and rewards, gives a convergence rate based on empirical-measure Wasserstein convergence.The finite-population state processes and gains converge to their CMKV-MDP counterparts.Source: §1 · p. 3
• The CMKV-MDP corresponds to a lifted MDP on probability measures; in the general setting, relaxed controls and an enlarged action space address the common-noise and measurability issues.Without common noise, or with finite state space, the lifted control reduces to the usual mixed or randomized strategy.Source: §1 · pp. 3–4
• The paper establishes a Bellman fixed point equation for the value function and Q-function, using an atomless initial-information filtration and measurable optimal Wasserstein couplings.The atomless filtration is assumed to be rich enough for the result.Source: §1 · p. 4
• Under a randomization hypothesis, the paper obtains ε-optimal randomized feedback controls and shows their value matches open-loop control, while pure feedback can have a strictly lower value.The introduction identifies this as a difference from classical MDP theory.Source: §1 · p. 4
• The Bellman equation is proposed as a basis for computing values and approximating optimal randomized feedback controls through value or policy iteration and discretization.The proposed discretizations cover both the state space and the space of probability measures.Source: §1 · p. 4

2 The N-agent and the limiting McKean-Vlasov MDP

• Open-loop controls use initial information and past idiosyncratic and common noises, but not agents’ states; an atomless random variable enables representing any probability measure as a law.The policies are non-anticipative, and the atomless probability space supports measure-valued randomization over states, actions, or state-action pairs.Source: §2 · p. 6
• Under continuity assumptions, finite-agent state processes converge almost surely to the conditional McKean–Vlasov dynamics, and fixed-policy gains converge.The section’s convergence argument also establishes convergence of expected gains for a fixed policy.Source: §2 · pp. 7, 9
• Under Lipschitz assumptions on transition and reward functions, convergence holds in L1, with optimal-value rates tied to empirical Wasserstein convergence.The regularity assumption on the transition function is in expectation, which accommodates finite state spaces.Source: §2 · p. 10
• For sufficiently large populations, an ε-optimal policy in either the finite-agent or limiting model is O(ε)-optimal in the other.The section states this transfer in both directions between the CMKV-MDP and the N-agent MDP.Source: §2 · p. 11
• When transition and reward depend on the joint state-action law only through its marginals, the rate can improve; for X,A ⊂ R, the alternative bound is ˜MN = O(N^-1/2).The section says this alternative rate is faster than MN in that setting.Source: §2 · pp. 12–13
• Theorem 2.1 provides a convergence rate for individualized open-loop controls in an infinite horizon.Unlike the cited prior results, it treats individualized controls and an infinite horizon; the passage does not give a complete rate expression.Source: §2 · p. 13
• For t ≤ t⋆, regularity of F keeps the N-agent and McKean-Vlasov processes and their rewards close; later, compactness of X limits their separation and discounting makes rewards negligible.The passage describes these effects as combining to ensure fast convergence despite accumulated errors over the infinite horizon.Source: §2 · p. 13

3 Lifted MDP on P(X)

• Conditioning the state law on common noise yields an MDP on P(X), with relaxed state-action controls determining its transitions and rewards.The lifted action space must have a σ-algebra that makes the model measurable and its controls adapted to common noise.Source: §3 · p. 14

3.1 Case without common noise

• Without common noise, the lifted problem is deterministic on P(X), and under the randomization hypothesis its value and ε-optimal controls correspond to those of the CMKV-MDP.The correspondence implies that the CMKV-MDP value depends on the initial state only through its law.Source: §3.1 · pp. 15–16

3.2 Case with finite state space X and with common noise

• With common noise and finite X, a sufficiently rich initial-information σ-algebra gives correspondence of values and ε-optimal controls between the CMKV-MDP and the lifted MDP.In this case the lifted state and action spaces are measurable, and the value function is law-invariant.Source: §3.2 · pp. 16–18
• For continuous X with common noise, the finite-state correspondence argument faces a measurability obstacle: the needed action-space σ-algebra may not exist.The obstacle concerns representing measurable lifted controls as state-dependent probability kernels, which is needed to establish surjectivity of the relaxed operator.Source: §3.2 · p. 18

4 General case and Bellman fixed point equation in P(X)

• The enlarged lifted MDP uses P(X × A) as its action space, and under the randomization hypothesis its value equals the CMKV-MDP value and Bellman fixed point.The stated equality is V(ξ) = Ṽ(µ) = V*(µ), for µ = L(ξ).Source: §4 · p. 18

4.1 A general lifted MDP on P(X )

• A measurable coupling maps a sample from one law to another while preserving the target law, including cases where a measurable transfer function for an optimal coupling is unavailable.The construction uses an independent uniform random variable to randomize when the source law has atoms.Source: §4.1 · p. 19

Lemma 4.2 (Measurable coupling projection)

• The measurable coupling projection adjusts a joint state-action measure to have the prescribed state marginal, while leaving it unchanged when that marginal already matches.This projection supports the lifted formulation with the required marginal constraint on actions.Source: §4.1 · p. 19, Lemma 4.2 (Measurable coupling… · p. 20

4.2 Bellman fixed point on P(X )

• The Bellman operator takes the supremum over actions of immediate reward plus discounted expected continuation value, and its fixed point is V*.The operator is expressed using the enlarged lifted MDP and its transition and reward functions.Source: §4.2 · pp. 21–22
• The direct lifted MDP with the earlier action space may be ill-posed because taking the supremum can produce a nonmeasurable function.The passage distinguishes this issue from the well-defined Bellman operator for the general construction.Source: §4.2 · p. 21
• Under (Hlip), the Bellman operator is monotone and β-contractive on bounded measurable functions over P(X), so it has a unique fixed point V*.The paper also establishes a γ-Hölder bound for V* in the Wasserstein distance.Source: §4.2 · pp. 22–23
• The general lifted-MDP value is bounded above by the Bellman fixed point at every probability measure.Source: §4.2 · p. 24

4.3 Building ǫ-optimal randomized feedback controls

• For each measurable lifted feedback policy, its π-Bellman operator is monotone and β-contractive and has a unique fixed point.Source: §4.3 · p. 24

Definition 4.1 (Lifted randomized feedback policy)

• A lifted randomized feedback policy is induced by a measurable action rule using the probability-measure state, an individual state, and a uniform random variable.The associated stationary randomized control uses an i.i.d. sequence of uniform variables independent of the initial state under the randomization hypothesis.Source: Definition 4.1 (Lifted randomized… · p. 25
• The paper establishes a verification result for the lifted MDP and, as a byproduct, for the CMKV-MDP.The associated randomized feedback control’s expected gain is identified with the lifted policy’s value.Source: Definition 4.1 (Lifted randomized… · p. 25

Proposition 4.3 (Verification result)

• An ε-optimal lifted policy yields an ε/(1−β)-optimal control for the original problem under the randomization hypothesis.The verification argument transfers the lifted policy's value bound to the original control problem.Source: Proposition 4.3 (Verification result) · pp. 25–26
• The proof constructs measurable randomized feedback policies by quantizing probability measures and coupling the corresponding states.Uniform continuity of the value and the measurable coupling support the construction.Source: Proposition 4.3 (Verification result) · pp. 26–28
• For every ε > 0, the theorem gives an ε-optimal lifted randomized feedback policy and identifies the CMKV-MDP value with the Bellman fixed point.The value satisfies the Bellman fixed point equation under the stated randomization hypothesis.Source: Proposition 4.3 (Verification result) · pp. 26–27
• The general result does not show that every lifted control can be represented by an original control, though restricting to representable controls preserves the optimal value.Consequently, existence of an optimal lifted control need not imply existence of an optimal original control.Source: Proposition 4.3 (Verification result) · pp. 28–29

4.4 Relaxing the randomization hypothesis

• Under (Hlip), the value function is γ-Hölder continuous in the L1 distance on initial states.The bound's constant depends only on the specified transition and discount parameters and the state-space diameter.Source: §4.4 · p. 29
• If the initial filtration is rich enough and (Hlip) holds, the value is law-invariant and equals the lifted value satisfying the Bellman fixed point equation.The supremum can be restricted to lifted randomized feedback policies.Source: §4.4 · p. 30
• Under the same conditions, an ε-optimal randomized feedback control exists for every ε > 0.The construction uses a quantized initial state and the result for the randomized setting.Source: §4.4 · p. 30

4.5 Feedback vs open-loop vs randomized controls

• When initial information is rich enough, randomized-feedback and open-loop optimal values coincide, although both can strictly exceed the feedback-only value.The strict gap is illustrated even when the initial state is atomless.Source: §4.5 · pp. 31–32
• When initial information is not rich enough, the three optimal values can be strictly ordered: randomized feedback above open-loop above feedback-only.The paper gives examples where the open-loop value does not satisfy a Bellman fixed point equation in this setting.Source: §4.5 · p. 31
• A randomized-feedback optimum can exist while an open-loop optimum does not, even when their optimal values agree.The open-loop example requires independent randomization for the optimal first action, which its initial information does not provide.Source: §4.5 · pp. 31, 33
• Without the additional uniform random variable, approximate open-loop controls may be more complex than the simple optimal randomized-feedback control.The construction described quantizes the initial state and builds an independent uniform variable for that quantized state.Source: §4.5 · p. 33

4.6 Computing value function and ǫ-optimal strategies in CMKV-MDP

• Value iteration repeatedly applies the Bellman operator, then selects an approximate optimal randomized feedback policy.Policy iteration alternates evaluation of a lifted policy and a greedy strategy update.Source: §4.6 · p. 33
• Discretizing the state space makes the conditional law finite-dimensional, so randomized feedback control computation becomes accessible but remains computationally challenging.For continuous state spaces, computing and storing the conditional state law is described as infeasible without such discretization.Source: §4.6 · pp. 33–34
• Under richness of initial information and (Hlip), a control for the discretized CMKV-MDP approximates an ε-optimal randomized feedback control in the original model.The approximation error is bounded at order O(η^γ + ε).Source: §4.6 · pp. 34–35
• An ε-optimal CMKV-MDP open-loop policy yields an O(ε)-optimal policy for the N-agent problem when N is sufficiently large.The described individual-agent construction does not require access to individual states.Source: §4.6 · p. 36
• The paper identifies the Q-function Bellman equation as a starting point for model-free Q-learning in the presence of common noise and mean-field dependence on control laws.The stated learning procedure discretizes the state and probability-measure spaces to obtain an approximate randomized feedback policy.Source: §4.6 · p. 36

• The paper develops CMKV-MDP theory for general state and action spaces with common noise and open-loop controls.Source: §5 · p. 37
• The CMKV-MDP is the asymptotic problem of a large cooperative-agent population, and the paper provides a convergence rate from the N-agent model.Source: §5 · p. 37
• The paper establishes correspondence with a lifted MDP on probability measures and emphasizes relaxed controls for characterizing solutions through a Bellman fixed point equation.Source: §5 · p. 37
• The Bellman equation yields approximate randomized feedback controls in a model-based framework; model-free algorithms are left for future work.Source: §5 · p. 37

• For measurable F, the lifted function ˆF(µ, x) := F(·, x) ⋆µ is measurable.Source: A Some useful results on conditional law · p. 37
• The appendix states that conditional laws exist when the conditioning space is Borel.Source: A Some useful results on conditional law · p. 37
• When Y = ϕ(X, Z) with Z independent of X, the conditional law of Y given X is the law of ϕ(x, Z); in the stated product case it is σ(X1)-measurable.Source: A Some useful results on conditional law · p. 37
• A probability kernel from S to P(T) can be represented as the law of a measurable function φ(s, U), with U uniform.Source: A Some useful results on conditional law · p. 37

• Under the stated independence assumptions and with compact Polish G, the conditional Wasserstein distance of the empirical measure converges almost surely to zero as N grows.Source: B Wasserstein convergence of the… · p. 38
• The proof conditions on X and applies the non-conditional result, using that Wasserstein distance metrizes weak convergence on compact G and that empirical measures converge weakly.Source: B Wasserstein convergence of the… · p. 38

• Every compact Polish space X is embedded into R by a map whose inverse is uniformly continuous.The construction encodes distances to a countable dense family and then groups decimal digits.Source: C Proof of coupling results · p. 39
• A measurable optimal coupling is constructed without assuming an optimal transfer function, which may fail to exist when one measure has atoms and the other does not.The construction uses a uniform variable to randomize when the source measure has atoms.Source: C Proof of coupling results · p. 40
• For the constructed coupling, sufficiently close measures yield a coupling with expected state distance below any prescribed ε.Source: C Proof of coupling results · p. 40