Steady-state Based Approach to Online Non-stochastic Control

1. Problem Statement

The paper addresses Online Non-stochastic Control (ONC), a framework where a learner controls a linear time-invariant (LTI) system subject to adversarial disturbances and adversarial convex cost functions. The goal is to minimize the cumulative cost over a time horizon $T$.

• System Dynamics: $x_{t+1} = Ax_t + Bu_t + w_t$, where $x_t$ is the state, $u_t$ is the input, and $w_t$ is an adversarial disturbance.
• The Challenge: The learner must select inputs $u_t$ without knowledge of future costs $f_t$ or disturbances $w_t$.
• Performance Metric: The standard metric is regret, defined as the difference between the learner's cumulative cost and the cost incurred by the best controller in a specific "benchmark class" chosen in hindsight.

The Gap:
Previous ONC literature typically benchmarks against:

1. Linear Feedback Controllers: (e.g., Agarwal et al.) which can be hard to interpret for general convex costs.
2. Constant Input Steady States: (The authors' previous work [13]) which compares the learner to the best steady state achievable by a constant input $u$.
   • Limitation: This benchmark is restrictive. It ignores the potential of feedback control to stabilize the system at steady states that are unreachable by open-loop constant inputs, particularly in underactuated systems.

The Objective:
The authors aim to design an algorithm that achieves sublinear regret against a richer benchmark: the set of all steady states attainable by affine stabilizing controllers of the form $u_t = -Kx_t + v$, where $K$ is a stabilizing gain and $v$ is a constant offset.

2. Methodology

The proposed solution, BatchFTPL, combines Follow-the-Perturbed-Leader (FTPL) from online non-convex optimization with a batching strategy to ensure system stability.

A. The Benchmark Set (Closed-Loop Steady State Manifold)

The authors define a new benchmark set $\mathcal{Z}$, which is the union of all steady states achievable by any strongly stabilizing affine controller:
$$\mathcal{Z} = \bigcup_{K \in \mathcal{K}} \{ z \mid z = (A - BK)z + Bv, \, v \in \mathcal{U} \}$$
where $\mathcal{K}$ is the set of strongly stabilizing gains.

• Key Difficulty: Unlike the constant-input set, $\mathcal{Z}$ is generally non-convex because it is a union of convex sets parameterized by $K$. This rules out standard projection-based methods (like Projected Gradient Descent).

B. Algorithm Design: BatchFTPL

To handle the non-convexity and the dynamic nature of switching controllers, the algorithm employs:

1. Batching: The time horizon $T$ is divided into batches of length $H$.
2. FTPL Update: At the start of each batch $n$, the learner selects a target steady state $z_n \in \mathcal{Z}$ using an FTPL update:
   $$z_n = \mathcal{O}_\epsilon \left( -\sum_{\tau=0}^{(n-1)H} f_\tau(z) + \langle \sigma, z \rangle, \mathcal{Z} \right)$$
   where $\sigma$ is an exponential random variable (perturbation) and $\mathcal{O}_\epsilon$ is an $\epsilon$-approximate minimization oracle.
3. Controller Synthesis: Once $z_n$ is selected, the learner finds a pair $(K_n, v_n)$ such that $z_n$ is the steady state for the controller $u = -K_n x + v_n$.
4. Execution: The controller $(K_n, v_n)$ is held fixed for the duration of the batch ($H$ steps).

C. Stability Mechanism

Switching between arbitrary stable controllers can destabilize a system. The authors ensure stability by:

• Strong Stabilization: Using controllers that guarantee a specific convergence rate ($\gamma, \kappa$).
• Batch Size Selection: Choosing $H$ large enough (specifically $H \approx \frac{\ln(2\kappa)}{-\ln(1-\gamma)}$) so that the system state converges close to the target steady state $z_n$ before the controller switches. This creates a "geometric decay" of tracking errors from previous batches.

3. Key Contributions

1. Richer Benchmark Definition: The paper extends the steady-state ONC framework from constant inputs to affine stabilizing controllers. This significantly broadens the comparison class, allowing the algorithm to compete against controllers that utilize feedback to reach steady states previously considered unattainable.
2. Algorithm for Non-Convex ONC: They propose BatchFTPL, the first algorithm to achieve sublinear regret against a non-convex benchmark set in ONC. It successfully navigates the non-convexity of $\mathcal{Z}$ and the stability risks of switching controllers.
3. Regret Guarantees: The authors prove that the algorithm achieves $O(\sqrt{T})$ expected regret with respect to the affine benchmark.
   • The regret bound depends on system stability parameters ($\kappa, \gamma$) and the accuracy of the optimization oracle ($\epsilon$).
   • Crucially, they show that an approximate solution to the non-convex subproblem is sufficient; exact optimization is not required.
4. Disturbance Handling: While the theoretical analysis assumes zero disturbances for clarity (using superposition to decouple disturbance effects), the method is extended to handle adversarial disturbances in simulations.

4. Results

Theoretical Results

• Theorem 8: Establishes the $O(\sqrt{T})$ regret bound. The bound is instance-independent (static regret), contrasting with dynamic regret bounds that often scale with the variation of the optimal trajectory.
• Stability: Lemma 7 proves that the system state remains bounded throughout the execution, provided the batch size $H$ is chosen correctly.

Empirical Results (Simulations)

• Setup: A 3-state, 2-input system with quadratic costs and uniform adversarial disturbances.
• Comparison: BatchFTPL was compared against the Disturbance Action Controller (DAC) from Agarwal et al. [5].
• Performance:
  • Cost: BatchFTPL consistently achieved lower cumulative cost than DAC, validating that the richer affine benchmark translates to better practical performance.
  • Computation:
    • A single oracle call in BatchFTPL is more expensive than a DAC update (as it scans a bank of 100 stabilizing gains and solves convex subproblems).
    • However, because BatchFTPL updates the policy only once every $H$ steps (while DAC updates every step), the total runtime of BatchFTPL was lower than DAC in the experiments.
• Conclusion: The method is both more performant and computationally efficient in the tested setting, despite the theoretical complexity of non-convex optimization.

5. Significance and Future Work

Significance:
This work bridges the gap between online learning and control by demonstrating that steady-state analysis can be generalized beyond simple open-loop inputs. It proves that one can compete against sophisticated feedback controllers in an adversarial setting without needing to know the future, provided the controller class is restricted to stabilizing affine laws. The use of batching to manage stability during policy switching is a novel and robust technique for online control.

Limitations & Future Directions:

• Computational Cost: While efficient in the specific simulation, the reliance on an optimization oracle for non-convex sets can be heavy for high-dimensional systems.
• Future Work: The authors suggest extending this approach to:
  • Dynamic Linear Feedback: Moving from static affine controllers to dynamic controllers (e.g., PID or state-space observers).
  • Safety Constraints: Incorporating hard constraints on states and inputs.
  • Partial Observability: Extending the framework to settings where the full state $x_t$ is not directly observable.

In summary, this paper provides a rigorous theoretical foundation and practical algorithm for online control that outperforms existing methods by leveraging a more powerful, feedback-based benchmark, all while maintaining the $O(\sqrt{T})$ regret guarantee essential for online learning.