CS Paper Radar

Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability

Yuxin Jin, Wang Yao, Xiao Zhang

eess.SY math.OC ·submitted 2026-09-10 11:52 UTC · v2

Abstract

We study asynchronous continuation replanning in a two-population linear--quadratic mean field game with deterministic open-loop controls and heterogeneous, possibly erroneous initial information. At exogenous opportunities, one population recomputes its continuation response from the physical aggregate state reached, with the opponent's active plan frozen. The state--plan target needed to initialize replanning is recoverable from local aggregate observations if and only if a kernel-inclusion condition holds; full recovery of the hidden initial input is unnecessary. For revisions accumulating before the terminal time, spectral stability of the limiting two-response cycle yields bounded physical execution and a finite state left limit. The zero-extended continuation plans then converge strongly to the mean field equilibrium restarted from that state. A scalar counterexample shows that well-posed continuation problems and a convergent physical state can coexist with divergent remaining plans. We also construct an exact causal implementation from local aggregate observations and establish finite-population robustness on every fixed finite opportunity prefix. Revision records match with probability tending to one, and the mean-square implementation error truncated to the matching event is \(O(N_*^{-1})\), where \(N_*\) is the smaller population size.

Closest papers

Nearest neighbours by meaning across the whole index.

Infinite Horizon Mean-Field Terminal Value Problem

eess.SY math.OC ·2026-09-11 ·Uğur Aydın, Tamer Başar, Naci Saldi
similarity 0.63
Abstract · 39 pages, 2 figures

We introduce a class of finite- and infinite-horizon discrete-time control problems for studying macroscale systems in discrete time, which we refer to as mean-field terminal value problems (MFTVPs). An MFTVP takes a terminal \(Q\)-function as input and, starting from this terminal \(Q\)-function, seeks an indefinite backward evolution of optimal policies and state measures, as required for an infinite-horizon non-stationary mean-field equilibrium (MFE) of a discrete-time mean-field game (MFG). We study the existence and uniqueness properties of this problem. As an application, using the uniqueness properties of MFTVPs, we show that, in the average-cost setting (and in the discounted setting for sufficiently small discount factors), MFTVPs can be used as an intermediate step to develop approximation schemes between finite-horizon MFEs and average-cost MFEs (respectively, stationary MFEs). In contrast to approaches that use infinite-horizon MFGs as intermediate problems, MFTVPs can be employed when the discount factor is sufficiently small (or, in the average-cost setting, when the drift factor is sufficiently small), together with a regularizer, to approximate a stationary MFE. Assuming uniqueness of the solution of a MFTVP, the restrictions we impose on the Lipschitz parameters of the system are weaker than the contraction conditions available for regularized stationary MFGs, and our approximation scheme remains applicable even in the presence of multiple stationary MFEs.

0.30

Symmetry-breaking in a discrete-choice LQG mean field game

eess.SY math.DSmath.APmath.OC+1 ·2026-10-05 ·Ali Akbar Rezaei Lori, Piyush Grover
similarity 0.59
Abstract · 26 pages, 4 figures. Originally submitted for review 5/18/26. v2 fixes issue with proof of lemma 4.3 related to terminal differentiability o…

Mean-field games provide a continuum framework for modeling the dynamics of large, interacting populations of non-cooperative agents. This paper studies symmetry-breaking in a finite-horizon, two-choice min-LQG mean-field game in which identical agents with linear stochastic dynamics choose one of two equally desirable terminal destinations, while trading off control effort against social pressure to conform. The model has an odd symmetry between the two destinations and therefore always admits a symmetric, dynamic Nash equilibrium in which the population splits evenly between them, producing a deadlock collective state at final time. Numerical studies have suggested that, as the penalty for social nonconformity increases, this symmetric equilibrium loses stability as a fixed point of an associated scalar, self-consistency map, and asymmetric consensus Nash equilibria emerge, where most agents select the same destination. By analyzing the linearized forward-backward PDE system through the scalar map representation, we provide a proof of this loss of stability of the symmetric equilibrium. Together with the odd symmetry of the map, this implies the existence of symmetry-broken mean-field game equilibria corresponding to consensus on either destination.

0.35

Policy Synthesis for Finite Populations of MDP Agents under Aggregate Reach-Avoid Chance Constraints

eess.SY cs.MA ·2026-10-08 ·Jie Fu, Anamika Dubey
similarity 0.59
Abstract · 8 pages, 2 figures. Submitted to the 2027 American Control Conference

Consider a finite population of agents with decoupled Markov transition dynamics and empirical-density feedback, subject to the following constraints: with probability at least $1-δ_r$, at least a fraction $α_r$ of agents must reach a target region at some time $t^*$, while, at each time up to $t^*$, the unsafe population fraction must remain below $β_u$ with probability at least $1-δ_u$. However, standard mean-field methods enforce these constraints only in expectation, which fails to account for stochastic fluctuations at finite fleet size $N$. 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-$N$ 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.

0.29

SafeAdapt-Poker: Counterfactual Risk Calibration for Budgeted Adaptation under Opponent Shift

cs.AI cs.GTcs.LG ·2026-10-14 ·Miaobo Hu, Shuhao Hu, Xiaobo Guo, Xin Wang, Bokun Wang +2 more
similarity 0.58
Abstract · 16 pages, 8 figures

Opponent histories can mislead after behavioral shifts. SafeAdapt-Poker formulates budgeted adaptation under opponent shift as a dual-counterfactual sequential-control problem using only information available before each decision. At each decision the controller asks two distinct questions: what local downside a deviation from the frozen anchor would induce under matched legal continuations, and what future adaptation value would be lost by consuming part of the remaining deviation budget now. The first question is answered by a monotone strategic-risk model over deviation intensity; the second by a paired budget-state continuation model that prices current budget consumption. The controller selects among support-preserving candidate deviations by trading immediate adaptation value against these two quantities, a pathwise cumulative-KL ledger bounds total anchor-relative deviation, and a finite family of frozen controllers is screened on complete paired calibration sessions before held-out interaction. A finite-candidate perturbation bound shows that the allocation objective degrades continuously with continuation-value estimation error. Evaluation covers exact-game exploitation and safety, four opponent shifts, local-risk calibration, delayed-opportunity allocation, direct opportunity-value estimation, value-error robustness, factorial mechanism attribution, budget sensitivity, abstract-HUNL cross-play, and player/time-held-out public-history behavior. On exact Leduc the full controller attains a matched weak-pool gain of +0.0718 with a worst-opponent delta of -0.0126, raises delayed-opportunity capture from 0.6318 under myopic allocation to 0.7841 under the same session budget, and reaches +42.7 mbb/hand in abstract-HUNL cross-play; the retained public-history screen reports 0.5820 action accuracy and 0.9277 log loss versus 0.5039 and 0.9778 for a public prior.

0.22

A Multistage Extension of Witsenhausen's Counterexample with Linear Signaling

eess.SY math.OC ·2026-11-08 ·Quanyan Zhu, Tamer Başar
benchmark similarity 0.57
Abstract · 8 pages, 3 figures

We study a multistage scalar extension of Witsenhausen's counterexample in which controller 1 observes the initial state exactly, whereas every subsequent controller observes only a local noise-corrupted state and does not inherit its predecessors' observations, so that every nonterminal action both regulates the state and shapes the signal available to the next controller. Restricting the signaling controllers to linear policies while leaving the terminal controller unrestricted, we compute the exact value within this class and reduce the optimization to a deterministic dynamic program in a single propagated variance. The optimal intermediate gains are shown to have a shrinkage form, and the value functions of that program are concave. For two stages, the benchmark admits a closed form on a matching locus, where for small effort weights it has two distinct minimizers, and at the standard parameter instance on that locus a two-point nonlinear policy strictly improves upon it. For three stages, numerical continuation at a reference instance reveals three distinct local minima, and two values of the initial variance at which the lowest of the three changes abruptly. Under the terminal-cost normalization we further prove, for every finite horizon, that the optimal linear value becomes asymptotically equal to the signaling-idle benchmark as the initial variance tends to infinity.

0.35

Equilibrium Learning in Unbounded Stochastic Games with Gaussian Transitions

cs.LG stat.ML ·2026-10-12 ·Jonathan Anthony Mavroforas, Fred Roosta
theory similarity 0.57
Abstract

Learning equilibria from data is difficult when several decision makers interact indefinitely and the system state has no prescribed bounds. We examine discounted general-sum stochastic games with compact action sets and an unknown nonlinear drift observed through Gaussian transition noise. The proposed procedure uses a single uninterrupted trajectory to update Gaussian-process models of the drift and to solve successively refined finite games. We prove a perturbation result showing that stability of equilibrium selection, together with uniform KL accuracy of Gaussian transition models, is sufficient for regional uniform convergence of the induced values and approximate Nash behavior in the original game. The region specifies where the guarantees are evaluated; strategies and dynamics continue to act on the entire Euclidean state space. For GP estimators, simultaneous confidence bounds yield a rate controlled by posterior uncertainty, kernel information gain, and joint-state dimension. Numerical studies illustrate how kernel choice and dimension appear in the predicted convergence behavior.

0.11

Horizon-Independent Contraction for Continuous-Time Discounted Regularized Mean-Field Games

cs.GT eess.SYmath.OC ·2026-08-27 ·Junji Yan, Uğur Aydın, Tamer Başar
similarity 0.56
Abstract · 34 pages. Full version including complete proofs

We study contraction properties of non-stationary continuous-time mean-field games (MFGs) under discounting and entropy regularization. The state of the representative agent evolves according to a controlled continuous-time Markov chain, and both the state and action spaces are finite. In contrast to the undiscounted case, we show that, under a sufficiently large discount rate, finite-horizon MFGs admit a horizon-independent contraction condition, which also coincides with the corresponding infinite-horizon non-stationary contraction condition. As a byproduct, we obtain an explicit convergence rate between finite- and infinite-horizon mean-field equilibria. For each finite horizon, we further derive a refined contraction criterion from the spectral radius of a positive operator that majorizes the propagation of policy errors, and show that its large-horizon limit agrees with the horizon-independent contraction factor. Finally, we provide an explicit error bound between discounted and undiscounted finite-horizon regularized equilibria.

0.32

High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

cs.LG cs.GTcs.MAeess.SY+1 ·2026-09-14 ·S. Rasoul Etesami
similarity 0.56
Abstract

We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $α$-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order $\widetilde O(T^{-1/4})$ and $\widetilde O(T^{-2/15})$ for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error $α$. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov $α$-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.

0.42