Moving target defense (MTD) against advanced persistent threats (APTs) in industrial control systems (ICS) has well-established game-theoretic formulations, but their practical value hinges on equilibrium computation, which faces two gaps: full-rank value iteration is prohibitively expensive at industrial scale, and the resulting defense strategies admit no certified robustness against adversarial perturbations. We first reveal that the attack and defense influence matrices of ICS dynamics are intrinsically low-rank: APTs infiltrate through a handful of entry points and MTD reconfigures only a few components per cycle. Our theory makes four contributions. First, an augmented gradient matrix certifies that the low-rank structure propagates through the non-smooth Bellman operator of the zero-sum stochastic game, so that every Bellman target lies near a low-dimensional subspace and low-rank truncation incurs an explicit error bound (Lemma 1, Theorem 1). Second, we propose the Dynamical Low-Rank Nash Equilibrium algorithm, named DLR-NE, which augments the rank-r search space each iteration, regularizes the core matrix spectrum, and retracts via truncated SVD, and prove that it converges geometrically to a neighborhood whose error decomposes into five physically interpretable sources (Theorem 2). Third, its per-step cost is O(nr^2), a Theta(n/r^2) speedup over full-rank value iteration (Theorem 3). Fourth, a single weight trades accuracy against a certified sensitivity bound of the induced defense strategy under core-matrix perturbations (Corollary 1). Six experiments on a nonlinear power-system testbed confirm each prediction, with 94% parameter compression at 2.3% utility loss. All experimental data and code are publicly available.
Figures & tables
Exp.
Theoretical prediction
Measured result
1
Thm. 1 : truncation error bounded by the EYM certificate; ICS coupling is low-rank
error 3.3×10−2→2.0×10−3 for r=5→100 , >2 orders below the certificate; spectrum cliffs at i≈202≈n/5
2
Thm. 2 : geometric decay γk then a plateau set by five error sources
two phases on all configurations; s∗ dominates the plateau ( 20× ); a priori bound 3×103 vs. measured plateau ≈2 (conservative)
3
Thm. 3 : per-step O(nr2) , Θ(n/r2) speedup
log–log slopes consistent with O(nr2) vs. O(n2) ; FLOPs speedup ≈12× at n=2000
4
Cor. 1 : linear sensitivity with a β -tunable constant
Fixed-Basis stagnates; No-Retraction destabilizes late; full algorithm stable at a low plateau
Table 1: Summary of the six experiments: theoretical prediction versus measured result.
Figure 1: Experiments 1–3 at n=m=1000 . (a),(b) Truncation error and singular-value spectrum of the trained full-rank benchmark: the error sits two orders of magnitude below its certificate, and the spectrum exhibits a sharp cliff at i≈202≈n/5 , evidencing the physical low-rank structure of ICS coupling. (c)–(e) Convergence of DLR-NE: geometric decay along the γk envelope into a plateau governed by the inner-loop budget s∗ , with the a priori bound three orders of magnitude conservative. (f)–(h) Complexity scaling: fitted slopes are consistent with O(nr2) against O(n2) , and the speedup grows linearly with n , reaching ≈12× in FLOPs at n=2000 .
Figure 2: Experiments 4–6 at n=m=1000 . (a),(b) Robustness: value deviation is linear in the core perturbation in all eight networks, while the fitted sensitivity does not track the condition number—the certificate of Corollary 1 is valid but conservative. (c) Compression–accuracy trade-off: r=5 removes ≈94% of the parameters at ≈2.3% utility loss. (d) Ablation: disabling basis augmentation stagnates convergence and skipping retraction destabilizes it—both mechanisms are necessary.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Category
Parameter
Value
System
State dimension n
{100,500,1000,2000} (default 1000 )
Hidden width m
m=n
Attacker coupling rank ra
3
Defender coupling rank rd
5
Reward coupling rank rr
5
Discount factor γ
0.95
Appendix
Table 2: Hyperparameter configuration for the numerical experiments.
We present a finite-sample analysis of decentralized learning in two-player zero-sum matrix games and stochastic games, with a focus on best-response-based learning algorithms. In matrix games, the learning algorithm is payoff-based and symmetric: each player updates its policy using only its own payoff observations, incrementally moving toward an estimated smoothed best response to the opponent's latest policy. For stochastic games, we build on this matrix-game primitive to develop a learning algorithm called value iteration with smoothed best response (VI-SBR), which combines smoothed-best-response learning in induced matrix games with a decentralized, model-free approximation of minimax value iteration. We establish finite-sample guarantees in both settings. For matrix games, our results imply a sample complexity of O(ε−1) for finding an ε-Nash distribution and, with explicit exploration, O~(ε−8) for finding an ε-Nash equilibrium. For stochastic games, we prove that the exploration-enhanced VI-SBR algorithm achieves a sample complexity of O~(ε−8) for finding an ε-Nash equilibrium. Technically, our analysis develops a coupled Lyapunov-drift framework. This framework simultaneously handles stochastic iterative algorithms with multiple interacting stochastic iterates, the non-zero-sum auxiliary games generated by independently updated value functions, and the time-inhomogeneous Markovian noise induced by time-varying policies. The resulting tools may be useful more broadly for analyzing learning algorithms with coupled stochastic iterates and nonstationary sampling processes.
Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar +2
IE, Purdue University. · ECE, University of Maryland, College Park. · CMS, Caltech. +1
Low-rank matrix optimization is often carried out via the Burer-Monteiro (BM) formulation, but choosing the factorization rank r is delicate and can substantially slow optimization. We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve optimization efficiency even when the target rank is unknown. We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization. The first, overparameterized DMD, uses a rank r larger than necessary and enjoys faster convergence as r increases. The second, recursive DMD, is motivated by the incremental eigenpair learning, or saddle-to-saddle, behavior of overparameterized DMD. It achieves lower memory and computational costs, complementing overparameterized DMD. Both approaches are exponentially faster than gradient descent applied to the BM formulation. Numerical experiments on matrix factorization, sensing, and completion corroborate our theoretical findings and demonstrate the practical effectiveness of DMD.
Yudong Wei, Liang Zhang, Bingcong Li +1
Department of Mathematics, ETH Zurich, Zurich, Switzerland · Department of Computer Science, ETH Zurich, Zurich, Switzerland
Concurrent games are a standard model for multi-agent systems, with Nash equilibrium as their central solution concept. The associated \emph{constrained existence problem}---does a game admit a Nash equilibrium whose expected payoff lies within a prescribed interval for every player?---is undecidable, and remains so even for 10-player \emph{stopping} games, in which a terminal state is reached almost surely under every strategy profile. We give two routes to tractability. We first relax exactness and consider the problem of approximate constrained existence problem, parametrised by ε-NE, which decides whether an ε-Nash equilibrium with the prescribed payoffs exists. The algorithm runs in exponential time, and only polynomially in the bit-size of ε. We complement it with a \PSPACE-hardness lower bound that holds already for turn-based games, and for pure equilibria as well. We then relax the solution concept, turning to \emph{extreme risk-sensitive equilibria} (XRSE), recently introduced for turn-based stochastic games. Here the players are partitioned into optimists and pessimists, who evaluate a strategy profile by the best, respectively the worst, payoff attainable with positive probability, instead of the expected payoff. We prove that the constrained existence problem for XRSE is \NP-complete on concurrent games, as for turn-based games.
Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini
Institute of Science & Technology Austria · Université Libre de Bruxelles