aiqbench analysis
This paper gives regret guarantees for online learning among strategic agents whose actions shape a shared linear dynamical system under adversarial disturbances. It extends nonstochastic online control to multi-agent settings and shows that, in the common-interest case, the problem becomes a time-varying potential game with equilibrium tracking. For ML readers, the useful part is the theory: near-optimal regret under specific feedback and stability assumptions, not an empirical or deployable result.
Online Learning in Stabilized Linear Dynamical Games with Adversarial Disturbances
arXiv:2506.18814v3 Announce Type: replace Abstract: We study online learning in linear dynamical games where multiple strategic agents act on a shared state evolving according to a linear dynamical system subject to adversarial disturbances. This setting lies beyond both single-agent nonstochastic online control and classical linear-quadratic games, which typically focus on quadratic objectives and noiseless or stochastic dynamics. Each agent seeks to minimize its own sequence of convex losses under full-state observability. Following the stabilizing-baseline paradigm in nonstochastic online control, we assume access to linear controllers that stabilize the noiseless system and focus on online adaptation by learning disturbance-action corrections. This extends adversarial online control to strategic multi-agent shared-state systems, where each agent's actions shape the state trajectory and hence the realized losses of all learners. Under state-only and aggregate-input feedback models, we analyze agents running online gradient descent with memory to update their own disturbance-action policies. We prove per-agent regret bounds that are sublinear and near-optimal in the time horizon, with population dependence that varies under the specified feedback, opponent policy, and stability assumptions. In the common-interest case, where all agents have identical cost functions, we show that the induced online problem forms a time-varying potential game and derive equilibrium tracking guarantees. Together, our results provide a theoretical framework for adversarial online learning in stabilized linear dynamical games, connecting online control with learning in games.
Abstract:We study online learning in linear dynamical games where multiple strategic agents act on a shared state evolving according to a linear dynamical system subject to adversarial disturbances. This setting lies beyond both single-agent nonstochastic online control and classical linear-quadratic games, which typically focus on quadratic objectives and noiseless or stochastic dynamics. Each agent seeks to minimize its own sequence of convex losses under full-state observability. Following the stabilizing-baseline paradigm in nonstochastic online control, we assume access to linear controllers that stabilize the noiseless system and focus on online adaptation by learning disturbance-action corrections. This extends adversarial online control to strategic multi-agent shared-state systems, where each agent's actions shape the state trajectory and hence the realized losses of all learners. Under state-only and aggregate-input feedback models, we analyze agents running online gradient descent with memory to update their own disturbance-action policies. We prove per-agent regret bounds that are sublinear and near-optimal in the time horizon, with population dependence that varies under the specified feedback, opponent policy, and stability assumptions. In the common-interest case, where all agents have identical cost functions, we show that the induced online problem forms a time-varying potential game and derive equilibrium tracking guarantees. Together, our results provide a theoretical framework for adversarial online learning in stabilized linear dynamical games, connecting online control with learning in games.
Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC)
arXiv:2506.18814 [cs.LG]
(or arXiv:2506.18814v3 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2506.18814 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 322 words
Related coverage
Temporal Difference Learning of Probabilistic Reach-Avoid Value Functions
arXiv · Oct 21, 2026
Taming the Adversary: A Cost-to-Disturbance Ratio Approach to Adversarial Reinforcement Learning
arXiv · Sep 22, 2026
AdvNav: Behavior-Guided Black-Box Adversarial Attacks on Vision-Language Navigation
arXiv · Jul 23, 2026
Adversarial Reinforcement Learning for Robust Planetary Landing
arXiv · Oct 15, 2026