Policy Synthesis for Finite Populations of MDP Agents under Aggregate Reach-Avoid Chance Constraints
In the authors' words
Consider a finite population of agents with decoupled Markov transition dynamics and empirical-density feedback, subject to the following constraints: with probability at least , at least a fraction of agents must reach a target region at some time , while, at each time up to , the unsafe population fraction must remain below with probability at least . However, standard mean-field methods enforce these constraints only in expectation, which fails to account for stochastic fluctuations at finite fleet size . To address this control problem, we propagate the second-order moment (variance) of the empirical density alongside the mean-field trajectory via a discrete-time Lyapunov recursion, and apply the Cantelli inequality to convert chance constraints into tractable deterministic conditions on the moments of the empirical density. We then incorporate these moment-based surrogate constraints into a gradient-based sequential convex approximation procedure for density-feedback policy synthesis. We further introduce additional moment-error bounds to construct a rigorous finite- certificate. The method is evaluated on a gridworld environment and a power-system EV-charging aggregation problem and compared with a standard deterministic population-level LP baseline.
Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8 pages, 2 figures. Submitted to the 2027 American Control Conference