Source-linked AI summary
Online Control with Adversarial Disturbances
Naman Agarwal, Brian Bullins, Elad Hazan, Sham M. Kakade, Karan Singh
TL;DR
The paper studies online control when disturbances and convex costs are adversarial, seeking low regret against the best linear controller in hindsight. It uses regret minimization with online-learning and convex-relaxation techniques to obtain an efficient algorithm. The result extends prior guarantees to bounded adversarial disturbances and arbitrary convex loss functions.
Problem
Online control must handle disturbances without distributional assumptions while competing in hindsight with a best linear controller under convex costs.
Method
The paper combines regret minimization with online learning for losses with memory and improper learning through convex relaxation.
Results
The paper gives an efficient regret algorithm that applies with bounded adversarial disturbances and arbitrary convex loss functions.
Takeaways & Limitations
Regret minimization provides an online adaptive control framework for adversarial disturbances and general convex costs.
Takeaways & Limitations
The interaction model assumes disturbances are not known to the learner in advance, and an approximation result assumes the comparator matrix is (κ, γ)-strongly stable.
Abstract
from arXiv · showhide
We study the control of a linear dynamical system with adversarial disturbances (as opposed to statistical noise). The objective we consider is one of regret: we desire an online control procedure that can do nearly as well as that of a procedure that has full knowledge of the disturbances in hindsight. Our main result is an efficient algorithm that provides nearly tight regret bounds for this problem. From a technical standpoint, this work generalizes upon previous work in two main aspects: our model allows for adversarial noise in the dynamics, and allows for general convex costs.
1 Introduction
The paper extends online control of linear dynamical systems to bounded adversarial disturbances and arbitrary convex costs, using regret minimization to obtain an efficient algorithm.
- The controller observes states while an adversary selects convex costs and disturbances, and seeks controls minimizing the resulting costs.
- The paper addresses arbitrary disturbances through an online adaptive approach rather than assuming i.i.d. Gaussian noise or anticipating all future noise.
- It targets efficient control with arbitrary convex costs, generalizing methods whose efficient computation relied on quadratic costs.
- Regret compares an algorithm’s cost with that of the best linear controller from a specified comparator class.
- The main result is an efficient algorithm with a stated regret bound, while previous bounds required disturbances drawn from a zero-mean, bounded-variance distribution.
- The approach uses online learning with memory and improper learning through convex relaxation.
2 Related Work
Related work spans online learning, linear-system control, robust control, adversarial MDPs, and changing-cost LQR. The paper distinguishes its approach by adapting to disturbances online while targeting general costs and efficient regret guarantees.
- Online Learning: The approach draws on regret minimization in online learning, especially online learning with memory, and treats worst-case regret as robust under adversarial noise.
- Learning and Control in Linear Dynamical Systems: Prior linear-dynamical-system work established sample-complexity and regret results mainly for Gaussian noise, with separate work on convex or non-observable settings.
- Robust Control: H∞ control handles adversarial perturbations by optimizing against worst-case future noise, whereas this paper adjusts to encountered noise iteratively.
- Non-stochastic MDPs: Reduction to adversarially changing MDPs yields regret dependent on the usually exponential state-space size and scales as Ω(T^3).
- Non-stochastic MDPs: Related MDP results avoid explicit state-space dependence but assume fixed dynamics without adversarial noise.
- LQR with changing costs: Changing-cost LQR work considered stochastic noise with quadratic costs, while the present setting addresses adversarial disturbances and general convex costs.
3 Problem Setting
The paper studies online control of linear dynamical systems with convex costs and disturbances that are arbitrary and unknown in advance. It competes with the best strongly stable linear controller using a disturbance-action parameterization and a reduction to online convex optimization with memory.
- Interaction Model: The system evolves as xt+1 = Axt + But + wt, with convex cost ct(xt, ut) incurred after observing the current state.The disturbance sequence is not assumed to follow a distribution and is not revealed beforehand.
- Regret Formulation: The controller’s regret is measured against the best linear controller in the class of (κ, γ)-strongly stable policies.Strong stability requires a similarity-transformed closed-loop matrix with norm at most 1 − γ and bounded controller and transformation matrices.
- Policy Class: The policy class uses past disturbances as linear features, yielding a convex relaxation intended to handle general convex costs and adversarial disturbances.The paper contrasts this with alternative parameterizations that may rely on quadratic costs, stochastic disturbances, or produce non-convex losses.
- Reduction to OCO with Memory: Choosing an appropriate horizon H reduces control to online convex optimization with memory, enabling gradient-based optimization of truncated losses.The reduction is designed to approximate the true counterfactual costs while retaining computational efficiency.
4 Preliminaries
The preliminaries introduce disturbance-action policies, transfer and ideal-state notation, and the truncation used to manage control costs that depend on past decisions. This produces convex losses with memory to which memory-based online gradient descent can be applied.
- Disturbance-Action Policies: A disturbance-action controller chooses actions as linear maps of past disturbances, making the resulting state linear in its policy parameters.This parameter linearity permits efficient optimization over the policy parameters, unlike direct optimization over linear-controller parameters.
- Disturbance-Action Policies: A disturbance-action policy π(M, K) is specified by disturbance-response matrices M and a fixed stabilizing matrix K.Past disturbances can be reconstructed from observed states and previous controls, so the policy is executable online.
- State Evolution: The disturbance-state transfer matrix Ψ^K_t,i describes how disturbance wt−i affects the future state under the policy sequence.The notation supports expressing state evolution under non-stationary policies composed of time-varying disturbance-action controllers.
- Ideal State and Truncation: Ideal states, ideal actions, and ideal costs reset the state H steps earlier, isolating the recent policy and disturbance history.The resulting truncated losses support efficient planning despite the counterfactual dependence of control costs on earlier decisions.
- OCO with Memory: Because ideal actions are linear in the recent controllers and ideal costs are convex, the ideal cost ft is convex in the recent policy parameters.This makes the truncated problem amenable to online convex optimization with memory.
- OCO with Memory: Memory-based online gradient descent bounds policy regret for Lipschitz losses with memory whose diagonalized losses are convex.The framework models each loss as depending on the current and previous H decisions.
5 Algorithm & Main Result
The paper’s algorithm maintains a disturbance-action controller and applies memory-based online gradient descent over a constrained policy class. Its analysis establishes regret guarantees under strong stability and bounded disturbances, with constant-time-per-step implementation.
- Algorithm: Algorithm 1 maintains a disturbance-action controller while controlling the linear dynamical system online.The controller requires a pre-specified (κ, γ)-strongly stable matrix K.
- Algorithm: The algorithm uses memory-based online gradient descent on the loss ft(·), updating Mt by projected gradient descent.The update defines gt(M) = ft(M, . . . M) and projects the gradient step onto M.
- Main result: The algorithm maintains O(1) parameters and can be implemented in O(1) time per time step, up to polynomial factors in γ^-1, κB, κ, and d.This efficiency statement accompanies the theorem’s regret guarantee.
- Algorithm: The policy class constrains each disturbance-response matrix M[i] by a geometrically decaying spectral-norm bound.The memory horizon is set as H = 2κBκ^3γ^-1 log(T).
- Analysis: Disturbance-action policies can represent any fixed linear policy, enabling comparison with the optimal strongly stable linear policy in hindsight.This equivalence is established by the sufficiency lemma for strongly stable matrices.
- Analysis: The regret analysis bounds approximation and stability effects for policy sequences under bounded disturbances and strongly stable control matrices.The proof combines the main regret analysis with bounds on the loss variation caused by changing one historical policy.
6 Conclusion
The conclusion presents regret minimization as a way to control linear dynamical systems with adversarial disturbances while accommodating general convex costs. The resulting controller learns and adapts to encountered noise rather than anticipating all future noise in the H∞-control sense.
- The paper controls linear dynamical systems with adversarial disturbances through regret minimization and handles general convex costs.
- The robust controller learns and adapts according to the noise encountered during operation.The conclusion contrasts this with H∞-control, which seeks a control for worst-case anticipation of future noises.
B Proof of Theorem 4.6
The proof uses standard online gradient-descent analysis to relate delayed-memory losses to the contemporaneous loss. The displayed bound controls this discrepancy through the Lipschitz constant.
- Standard OGD analysis bounds the difference between the delayed-memory loss ft(xt−H, . . . , xt) and the contemporaneous loss ft(xt, . . . , xt).The bound is expressed using the Lipschitz constant L.