Mean field for Markov Decision Processes: from Discrete to Continuous Optimization

• The optimal reward of a large-object Markov decision process converges to the solution of a continuous HJB equation based on its mean-field approximation.The abstract also reports explicit bounds on reward differences and a constructive way to derive an approximate discrete-system solution from the HJB solution.Source: continue · p. 4
• The approach is illustrated through investment strategies, population-dynamics control, and resource allocation.Source: continue · p. 4
• The paper's focus is mean field, HJB, optimal control, and Markov decision processes.Source: continue · p. 4

1 Introduction

• The paper studies centralized dynamic optimization for Markov decision processes composed of many interacting objects.The system has a shared environment, and transitions depend on the population state and controller decisions.Source: §1 · p. 5

Contributions

• The mean-field limit yields an ODE optimization problem whose HJB solution approximates the optimal reward, and its optimal policy is asymptotically optimal for the discrete system.The analysis uses stochastic-approximation bounds and couples each discrete sample path to an ODE trajectory controlled by random actions.Source: Contributions · p. 5
• The convergence result supports constructing controlled ODE approximations and using an HJB equation instead of discrete dynamic programming, whose state space grows exponentially in the number of objects.The paper contrasts centralized control with prior mean-field work on uncontrolled systems and games, and notes that related value-function approximations differ from its proof of asymptotic optimality.Source: Contributions · p. 5, §1 · p. 5, Related Work · p. 6

Related Work

• Related work includes discrete-time limits for intensity O(1), whereas this paper focuses on intensity o(1), yielding a continuous-time limit.It also distinguishes its centralized global optimization setting from distributed-control and Nash-equilibrium approaches.Source: Related Work · p. 6

Structure of the paper

• The paper proceeds from definitions and hypotheses to theoretical results, examples and algorithm, proofs, and concluding perspectives.Source: Structure of the paper · p. 6

2.1 System with N Objects

• With a finite state set, the system is represented by an empirical occupancy measure whose components give the proportions of objects in each state.Permutation-invariant transitions make this measure a Markov process under a fixed action sequence.Source: §2.1 · p. 7

2.2 Action, Reward and Policy

• The centralized controller selects actions, and state observability plus permutation invariance lets policies depend on the occupancy measure rather than object identities.The paper defines policy value over a finite horizon and seeks a policy maximizing expected reward.Source: §2.2 · pp. 7–8

2.3 Scaling Assumptions

• When the expected drift is small and its rescaled form converges to a Lipschitz function, time is rescaled by the intensity to obtain a continuous-time process.The intensity also represents the order of magnitude of objects changing state per unit time and the duration of a time slot.Source: §2.3 · p. 8

2.4 Limiting System (Mean Field Limit)

• Under the scaling, the stochastic occupancy process converges to a deterministic mean-field limit, and a time-varying action function drives its ODE.The limiting equation has a unique solution for a fixed initial condition under the stated regularity conditions; the paper defines its finite-horizon value and optimal value.Source: §2.4 · pp. 8–9

2.5 Table of Notations

• The notation distinguishes the finite-system empirical measure and drift from their limiting counterparts, and policies from time-indexed action functions.The limiting system's value under an action function is distinct from its optimal value.Source: §2.5 · p. 9

2.6 Summary of Assumptions

• Convergence of the discrete stochastic optimization problem to a continuous deterministic one is established under permutation-invariant transitions, per-slot transition-count expectation ≤c1 and standard deviation ≤c2, I(N), I0(N) tending to zero, Lipschitz continuity, and bounded rewards.Source: §2.6 · pp. 9–10

3.1 Main Results

• The optimal values for the N-object system and the mean-field limit converge as N grows, under the stated assumptions and initial-state convergence condition.The result holds almost surely or in probability, matching the mode of initial-state convergence.Source: §3.1 · p. 10
• An optimal action function for the limiting system is asymptotically optimal for the N-object system, and such state-independent policies become as good as adaptive policies as N grows.Adaptive policies may perform better for very small N, and convergence is generally impossible to prove for adaptive policies.Source: §3.1 · p. 11

3.2.1 Second Auxiliary System

• The proof compares finite-system policies with limiting-system trajectories by deriving a time-varying action function from each policy trajectory.For each trajectory, the action function records the controller’s action at each time slot and controls the limiting ODE.Source: §3.2.1 · p. 11

3.2.2 Convergence of Controlled System

• The controlled finite system converges in probability to its associated limiting controlled system with explicit bounds, without requiring regularity of the policy.The result applies under Assumptions (A0) to (A3).Source: §3.2.2 · p. 12

3.2.3 Convergence of Value

• The value under the trajectory-derived action function converges uniformly with an error that can be bounded.The section states this result as Theorem 6.Source: §3.2.3 · p. 12

3.2.4 Putting Things Together

• The two auxiliary systems bound the finite-system optimum from opposite directions, showing that the finite and limiting optimal values are close for large N.The first supplies a finite-system strategy from a limiting action function; the second supports the reverse comparison.Source: §3.2.4 · p. 12

4.1 Hamilton-Jacobi-Bellman Equation and Dynamic Programming

• Finite-system optimal values can be computed by discrete dynamic programming, while the limiting system’s optimal value and policy follow from its HJB equation.The finite-horizon recursion uses the terminal reward and the next-state value; the limiting problem is posed over the continuous horizon.Source: §4.1 · p. 13

4.2 Algorithms

• For the system with N objects over [0,H], Algorithm 1 uses an HJB control and deterministic differential-equation estimate from the initial occupancy measure to construct a static discrete policy that is asymptotically optimal.Source: §4.2 · p. 13

4.3.1 Utility Provider Pricing

• In the simplified pricing example, the mean-field optimum has a closed-form solution, with a high price chosen when x > 1/2 or x > 1 − exp(−(T − t)), and a low price otherwise.The example contrasts higher immediate profit at higher prices with customer losses that reduce later gains.Source: §4.3.1 · pp. 14–15

4.3 Examples

• The applications include a simplified investment problem whose infinite-system optimization is analytically solvable, although the original large finite system is difficult to solve numerically.The examples also include population control and volunteer-computing queue brokering to illustrate construction of controlled ODEs and continuous optimization.Source: §4.3.1 · p. 14, §4.3 · p. 14

4.3.2 Infection Strategy of a Viral Worm

• For the infection problem, the mean-field policy is asymptotically optimal, is close to optimal even at N = 10, and outperforms the constant-probability heuristic by more than 20%.The numerical comparison reports that the limiting and finite-system optimal values, and the value under the limiting policy, are already close for small N.Source: §4.3.2 · pp. 16–17, Figure 2 · p. 17
• The viral-worm example formalizes the link between individual-level optimization and the differential-equation problem: the limiting bang-bang policy is asymptotically optimal for the discrete system.In the reported numerical example, the limiting policy waits until t = 4.9, then kills machines at the maximum rate.Source: §4.3.2 · pp. 15–17

4.3.3 Brokering Problem

• The brokering example replaces optimization over JN states with an HJB system of (J + 2)C ODEs, which is more tractable; the discrete problem cannot be solved numerically beyond 10 processors.The broker routes jobs among clusters and minimizes queue size and job losses.Source: §4.3.3 · pp. 17–19

5.2 Proof of Theorem 1

• Permutation invariance implies that functions of the global state can be expressed through occupancy measures, which allows the proof to show that the occupancy-measure process is Markov.States with the same occupancy measure differ only by a permutation; the transition kernel’s permutation symmetry is then used in the Markov argument.Source: §5.2 · p. 20

5.3 Proof of Theorem 5

• Theorem 5’s trajectory argument bounds deviations using martingale estimates and an integral formula.The proof bounds the martingale component with high probability and the remaining component through an integral formula.Source: §5.3 · pp. 21–23

5.4 Proof of Theorem 6

• Theorem 6’s proof controls reward differences using a high-probability event and the reward function’s Lipschitz continuity in the occupancy measure.The supplied proof passage also bounds a residual term by I(N) times the supremum norm of the reward.Source: §5.4 · p. 24

5.5 Proof of Theorem 3

• Theorem 3’s proof approximates a piecewise Lipschitz action by a stepwise policy and uses Grönwall’s inequality to bound the resulting difference.The approximation accounts for intervals containing discontinuities and for a possible final partial time interval.Source: §5.5 · pp. 24–25

5.6 Proof of Theorem 2

• Theorem 2’s proof combines the lower bound from near-optimal limiting controls with an upper bound from Theorem 6 to establish convergence of finite-system optimal values.The proof obtains the lower bound by applying Theorem 3 to an ε-optimal action function, and the upper bound by applying Theorem 6.Source: §5.6 · p. 25

6 Conclusion and Perspectives

• In general, optimal policies may be nonunique and discontinuous because of thresholds, so their convergence is not guaranteed.Limit theorems are available for some cases, such as best response dynamics, but at substantially greater complexity; the general problem remains open.Source: §6 · pp. 25–26
• For bounded rewards, the result that a mean-field-optimal policy is near-optimal for finite systems also holds for infinite-horizon discounted problems.A finite horizon T approximates the discounted value with an error below ε.Source: §6 · p. 26
• For infinite-horizon problems without discount and for average-reward problems, value convergence as N grows is not guaranteed in general.The authors identify finding natural assumptions for convergence as future work.Source: §6 · p. 26