Introduction to
Online Nonstochastic Control

Graduate text in learning to control

Elad Hazan and Karan Singh

Abstract:

This text presents an introduction to an emerging paradigm in control of dynamical systems and differentiable reinforcement learning called online nonstochastic control. The new approach applies techniques from online convex optimization and convex relaxations to obtain new methods with provable guarantees for classical settings in optimal and robust control.

The primary distinction between online nonstochastic control and other frameworks is the objective. In optimal control, robust control, and other control methodologies that assume stochastic noise, the goal is to perform comparably to an offline optimal strategy. In online nonstochastic control, both the cost functions as well as the perturbations from the assumed dynamical model are chosen by an adversary. Thus the optimal policy is not defined a priori.

Rather, the target is to attain low regret against the best policy in hindsight from a benchmark class of policies.

This objective suggests the use of the decision making framework of online convex optimization as an algorithmic methodology. The resulting methods are based on iterative mathematical optimization algorithms, and are accompanied by finite-time regret and computational complexity guarantees.

Table of Contents

Background in Control and RL

1. Introduction

   1. What is This Book About?

   2. The Origins of Control

   3. Formalization and Examples of a Control Problem

   4. Simple Control Algorithms

   5. Classical Theory: Optimal and Robust Control

   6. The Need for a New Theory

2. Dynamical systems

   1. Examples of Dynamical Systems

   2. Solution Concepts for Dynamical Systems

   3. Intractability of Equilibrium, Stabilizability and Controllability

3. Markov Decision Processes

   1. Reinforcement Learning

   2. Markov Decision Processes

   3. The Bellman Equation

   4. Value Iteration

4. Linear Dynamical Systems

   1. General Dynamics as LTV Systems

   2. Stabilizability of Linear Systems

   3. Controllability of LDS

   4. Quantitative Definitions

5. Optimal Control of Linear Dynamical Systems

   1. The Linear-Quadratic Regulator

   2. Optimal Solution of the LQR

   3. Infinite Horizon LQR

   4. H∞ Control

Basics of Nonstochastic Control

6. Policy Classes for Dynamical Systems

   1. Relating the Power of Policy Classes

   2. A Quantitative Comparison of Policy Classes for LTI Systems

   3. Policy Classes for Partially Observed LDS

7. Online Nonstochatic Contro

   1. From Optimal and Robust to Online Control

   2. The Online Nonstochastic Control Problem

   3. The Gradient Perturbation Controller

8. Online Nonstochastic Control with Partial Observation

   1. Disturbance Response Controllers

   2. The Gradient Response Controller

9. Online Nonstochastic System Identification

   1. Nonstochastic System Identification

Learning and Filtering

Appendix

10. A Concepts from Online Convex Optimization

    1. Online Gradient Descent