# Online estimation and control with optimal pathlength regret

arXiv: https://arxiv.org/abs/2110.12544 · HTML: https://mlsanity.com/paper/2110.12544/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 18 references that are in the map.
- First posted on arXiv 24 Oct 2021.

## Builds on (most cited first, 10 of 10)

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019)
- [Regret-optimal Estimation and Control](https://mlsanity.com/paper/2106.12097/) (2021)
- [Competitive Control](https://mlsanity.com/paper/2107.13657/) (2021)
- [Regret-optimal measurement-feedback control](https://mlsanity.com/paper/2011.12785/) (2020)

## Abstract (arXiv)

A natural goal when designing online learning algorithms for non-stationary environments is to bound the regret of the algorithm in terms of the temporal variation of the input sequence. Intuitively, when the variation is small, it should be easier for the algorithm to achieve low regret, since past observations are predictive of future inputs. Such data-dependent "pathlength" regret bounds have recently been obtained for a wide variety of online learning problems, including OCO and bandits. We obtain the first pathlength regret bounds for online control and estimation (e.g. Kalman filtering) in linear dynamical systems. The key idea in our derivation is to reduce pathlength-optimal filtering and control to certain variational problems in robust estimation and control; these reductions may be of independent interest. Numerical simulations confirm that our pathlength-optimal algorithms outperform traditional H2 and H∞ algorithms when the environment varies over time.