CS Paper Radar

Sparse One-Step-Ahead Optimal Control of Time-Varying Affine Opinion Networks: Tracking and Competitive Games

Gabriel Gentil, Amit Bhaya

eess.SY cs.GT ·submitted 2026-09-17 14:17 UTC · v1

Abstract

This paper studies resource-limited external influence in time-varying opinion networks when a controller must choose both a small set of agents and a scalar intervention at each update. We use the affine free response, which includes DeGroot and Friedkin--Johnsen dynamics, followed by a direct sparse action. Eliminating the scalar action reduces the one-step problem to a cardinality-constrained support objective whose global optimum is obtained from the largest or smallest residual components. Hence exact sparse one-step-ahead optimal control requires one sort and \(O(|\mathcal T|\log|\mathcal T|)\) operations, where \(\mathcal T\) is the support set. For periodic affine dynamics, the resulting state-dependent low-rank feedback admits cycle-based ultimate bounds and exact tracking of model-invariant targets. The DeGroot and Friedkin--Johnsen specializations expose the role of target invariance and the affine mismatch term. With several competing external players, each sparse best response retains the same sorting structure and the complete binary--continuous stage game is an exact potential game, so a pure-strategy equilibrium exists at every frozen state. Same-state welfare benchmarks separate loss due to scalar competition from the additional loss due to strategic support selection. Numerical examples validate exact support selection and illustrate switching-order effects, DeGroot/Friedkin--Johnsen tracking, resource tradeoffs, and competitive implementations.

Comment
18 pages, 8 figures, 9 tables, under review by European Journal of Control

Closest papers

Nearest neighbours by meaning across the whole index.

Competitive One-Step-Ahead Control of Friedkin--Johnsen Networks: Potential Games, Stability, and the Price of Competition

eess.SY ·2026-08-27 ·Gabriel Gentil, Amit Bhaya
similarity 0.59
Abstract · 11 pages, 2 figures. Submitted to IEEE Transactions on Control of Network Systems

This paper studies competitive one-step-ahead control of Friedkin-Johnsen networks with overlapping player influence. The one-step interaction is an exact potential game with a unique Nash equilibrium obtained from a symmetric positive-definite system. Sequential best-response sweeps converge for every frozen network state, parallel sweeps obey an exact Jacobi condition (and always converge with two players), and one-sweep implementations require an augmented state-action stability test. For marginal networks, a signed left-right damping condition is sufficient for exact-equilibrium stability and becomes a sharp first-order instability test when its sign is reversed. A resolvent identity clarifies the feedback geometry, while a control-aware centrality identifies the goal conflicts that matter most. We characterize attainable equilibria under unconstrained, convex, and sparse goal restrictions and give a closed form for the same-state welfare loss caused by competition. Numerical examples verify the stability thresholds, geometry, and welfare predictions.

0.55

Online Constrained Control of Storage Systems via Simplex Disturbance-Action Policies

eess.SY ·2026-09-07 ·Kamiar Asgari, Michael J. Neely
theory similarity 0.58
Abstract

We study online control of a scalar storage system with nonnegative adversarial resource arrivals and state-dependent action constraints. The adversarial, time-varying cost depends on both state and action. At each time, the controller selects a feasible action before the current resource arrival and cost are revealed. To handle the coupling between feasibility and online learning, we introduce Simplex Disturbance-Action Control (SDAC), whose policies have $H$ nonnegative parameters summing to at most one. Every fixed SDAC policy is feasible by construction. Our online SDAC controller updates these parameters using entropic online mirror descent while preserving feasibility along the time-varying trajectory. We prove a regret bound of $O\!\left(\sqrt{T\log(H+1)}\right)$ relative to the best fixed SDAC policy and a minimax lower bound showing that the dependence on $T$ is tight. We also introduce infinite-memory SDAC policies, which include every feasible fixed-fraction policy. SDAC policies approximate this class with an error that decreases geometrically with $H$. For a suitable choice $H=Θ(\log T)$, the resulting regret against infinite-memory SDAC policies is $O\!\left(\sqrt{T\log\log T}\right)$. The framework applies to energy-harvesting batteries and other storage-constrained resource systems.

0.48

Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

cs.LG cs.GT ·2026-10-05 ·Yuheng Zhang
similarity 0.57
Abstract

We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a $\widetilde{\mathcal{O}}(t^{-1/4})$ duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the $\widetilde{\mathcal{O}}(t^{-1/(9+ν)})$ rate of Cai et al. (2023), for any fixed $ν>0$, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.

0.19

Last-Iterate Convergence of Policy Dynamics in Zero-Sum Networked Separable Markov Games

cs.GT ·2026-09-08 ·Zailin Ma
similarity 0.57
Abstract

Solving Nash equilibria for general multi-player Markov games is computationally intractable, while two-player zero-sum Markov games admit fast last-iterate policy-optimization methods. Zero-sum networked separable Markov games occupy an important middle ground: they retain global multi-player competition structure through pairwise interactions, while preserving computational tractability of Nash equilibria (NE) in the finite-horizon setting. Existing algorithms for this class either proceed through equilibrium-collapse arguments for a simplified setting where a single controller determines the transition probability, or backward dynamic programming that relies on equilibrium solvers at each stage. However, the design and analysis of direct policy-update approaches remain inadequate. To address this issue, we propose the entropy-regularized optimistic multiplicative weights update (ER-OMWU), a complementary single-loop policy dynamic that updates players' policies symmetrically and returns an approximate NE in the last iteration. We provide the first last-iterate convergence analysis of policy dynamics in the games of interest: after $\widetilde O\left(1/ε\right)$ iterations, the returned policy is an $ε$-approximate Nash equilibrium. The result preserves the near-linear convergence rate achieved by policy optimization in two-player zero-sum Markov games, but extends the policy-dynamics viewpoint to a more complicated but structured multi-player setting.

0.20

Optimistic Distributed Submodular Coordination with Applications to Multi-Target Tracking with Multiple Robots

eess.SY ·2026-10-14 ·Pranjal Sharma, Atharva Navsalkar, Zirui Xu, Vasileios Tzoumas
hot direction similarity 0.57
Abstract · 8 pages, 1 figure, under review for the American Control Conference (ACC 2027)

We provide a distributed online algorithm for multi-agent submodular coordination in bandit environments, i.e., environments whose evolution is unknown a priori and may even adapt to the agents' actions. We are motivated by multi-robot tasks such as target tracking, where the optimal actions change over time and the agents must track them rather than a single fixed optimum. To address such problems, we provide the Optimistic Distributed Online Greedy (O-DOG) algorithm, that leverages predictions about the environment's behavior and improves regret guarantees. The agents select actions simultaneously over arbitrary, possibly time-varying, network topologies, and each agent acts optimistically, i.e., leveraging predictions of its upcoming rewards, e.g., from forecasts of the targets' motion and of its neighbors' actions. We bound O-DOG's tracking regret in terms of the agents' prediction error and the bound never exceeds its prediction-free counterpart. Particularly, it is sublinear even when the optimal action changes at every time step, provided the predictions are accurate enough. We further quantify the suboptimality due to decentralization as a function of the network structure, and show that accurate predictions accelerate convergence. We validate O-DOG in simulated multi-robot target tracking.

0.31

Planning Against Learning in Rank-1 Games

cs.GT ·2026-08-18 ·William Overman
similarity 0.57
Abstract

Learning algorithms are often used to make decisions in repeated multi-agent environments. When another player understands how a learner adapts from past experience, that player can plan strategically across rounds to influence the learner's future behavior. Recent work shows that optimizing against Replicator Dynamics, the continuous-time analogue of Multiplicative Weights Update, is tractable in zero-sum games but can be hard in unrestricted general-sum games. We study the first structured class beyond zero sum: bimatrix games satisfying $\text{rank}(A+B)=1$, for which Nash equilibria can be computed in polynomial time. Our main result shows that this equilibrium tractability does not extend to planning against learning dynamics. Unless $\mathsf{P}=\mathsf{NP}$, approximating the optimizer's optimal continuous-time reward within a fixed additive constant is NP-hard even when $\text{rank}(A+B)=1$, the learner starts from the uniform state, and the optimizer is restricted to constant strategies. The hardness persists for bounded payoff matrices and polynomially bounded horizons. We complement this result with structural characterizations of several tractable special cases. Thus rank-one games already separate efficient equilibrium computation from strategic planning against a learning opponent.

0.06

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

cs.LG cs.GT ·2026-09-28 ·Yuheng Zhang
theory similarity 0.56
Abstract

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t$. This improves the dimension dependence of the best previously known guarantee by a factor of $d^{3/2}$. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only $\mathcal{O}(d)$ time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.

0.33

$Q$ Can Play That Game: Online Fitted $Q$-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation

cs.GT cs.MA ·2026-10-02 ·Kushagra Gupta, Jingqi Li, Cade Armstrong, Lasse Peters, Ross E. Allen +2 more
code/data similarity 0.56
Abstract

Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function ($Q$-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the $Q$-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted $Q$-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame.

0.33