The Non-Stochastic Control Framework

on YouTube ↗34m

" summary

Provides an efficient algorithm for known, fully observed linear time invariant systems with adversarial bounded disturbances that guarantees O(√T) regret against the class of disturbance‑feedback controllers, using convexification of the control via disturbance‑feedback parameters, a mild strongly‑stable (ρ(A−BK) ≤ 1−δ) assumption, reduction to online convex optimization with memory, and an OGD‑style update with horizon H = O(log T). Implementation is polynomial in system parameters, logarithmic in time, and code is available.

AI-written summary · about

" chapters (9)

1. 0:00Introduction
2. 3:05Optimal Control
3. 11:31The Problem
4. 13:27Online Control
5. 18:20Reasonable Comparative Policies
6. 23:14General Control
7. 26:03Convexification
8. 27:26Stability
9. 30:39OCO with Memory

" related talks

• 31mLearning to Control Unknown SystemsRahul Jain · Societal Networks 2018
• 38mBest of Both World Algorithms from I.I.D. to Adversarial DataJulian Zimmert · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 43mLearning from DynamicsAnkur Moitra · Joint IFML/MPG Symposium 2024
• 42mA Regret Minimization Approach to Mutli-Agent Control and RLElad Hazan · Multi-Agent Reinforcement Learning and Bandit Learning
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 15mBridging Stochastic and Adversarial BanditsThodoris Lykouris · Data-Driven Decision Processes Boot Camp 2022
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)