Online Convex Optimization with Memory and Control

This direction is split into other directions: temporal decision coupling. Its last version stays readable and citable here.

Version 1 of 189 papers123 conceptsfrozen 2026-10-04

In standard machine learning, we often assume that the world is "stateless." When an algorithm makes a decision, it incurs a cost, and the next round starts with a clean slate. However, in physical systems—like a drone fighting wind gusts or a power grid managing fluctuating demand—the world has a memory. An action taken now doesn't just affect the immediate cost; it ripples through the system, influencing future states and future costs for a long time.

This "temporal coupling" is the fundamental challenge of merging control theory with online learning. Recent research has developed a framework to handle these dependencies by treating control as Online Convex Optimization (OCO) with Memory.

The Challenge of Temporal Coupling

In a classic OCO setting, a learner chooses an action $x_t$ and suffers a loss $f_t(x_t)$. In a dynamical system, the loss is instead $f_t(x_t, x_{t-1}, \dots, x_{t-h})$, where $h$ represents the system's memory. As Elad Hazan, Oren Anava, and Shie Mannor point out in Online Learning for Loss Functions with Memory and Applications to Statistical Arbitrage, this path-dependency breaks the independence assumptions of standard regret minimization.

If you ignore this memory, you might take an action that looks cheap now but forces the system into an "expensive" or unsafe state later. This is particularly visible in inventory management, where Massil Hihat and colleagues demonstrate in Online Inventory Problems: Beyond the i.i.d. Setting with Online Convex Optimization that the feasible set of actions today is strictly constrained by the decisions made yesterday.

Why Memory is Tractable: Exponential Decay

The reason we can solve these problems at all is that most stable physical systems eventually "forget" the distant past. This property is often framed as contractive perturbations or exponential decay.

Yiheng Lin, Adam Wierman, and others show in Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations that if the influence of past actions on current costs decays quickly enough, we can treat the system as a sequence of nearly-decoupled optimization problems.

To quantify this, Raunak Kumar, Sarah Dean, and Robert Kleinberg introduced the concept of effective memory capacity in Online Convex Optimization with Unbounded Memory. This metric allows researchers to derive regret bounds even when the memory is technically infinite, provided the "tail" of the influence is thin. This insight bridges the gap between simple sliding-window approaches and the true, long-term dependencies of dynamical systems.

Non-Stochastic Control and Disturbance-Action Policies

A major breakthrough in this field was the shift from stochastic control (where noise is random) to non-stochastic control (where noise can be adversarial). In Making Non-Stochastic Control (Almost) as Easy as Stochastic, Max Simchowitz showed that we can achieve optimal learning rates by preconditioning our updates based on the system's response geometry.

The standard tool for this is the Disturbance-Action policy. Instead of choosing a raw control input, the learner chooses how to react to past disturbances. Asaf Cassel and Tomer Koren demonstrate in Bandit Linear Control that this reparameterization makes the cost function convex with respect to the policy parameters, allowing us to use the full machinery of OCO.

Safety and Constraints in Stateful Systems

In real-world engineering, performance is secondary to safety. If an online optimizer explores a high-cost action that pushes a robot into a wall, the "regret" is the least of the engineer's worries.

To address this, Subhro Das, Yingying Li, and Na Li developed Online Gradient Descent with Buffer Zones (OGD-BZ) in Online Optimal Control with Affine Constraints. By "tightening" the safety constraints with a buffer, the algorithm ensures that even if a past action has a lingering effect, the system has enough room to recover without violating hard physical boundaries.

From Robotics to Databases

While the intuition for this research direction often comes from robotics, the mathematical framework is remarkably general. For example:

By treating memory not as a nuisance but as a structured kernel within a convex optimization landscape, this research direction provides a rigorous way to build systems that learn and adapt in the real, stateful world.

Papers in this version

Showing 60 of 89 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_online_convex_optimization_with_memory_a_f9e1b199,
  title = {Online Convex Optimization with Memory and Control},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-convex-optimization-with-memory-and-control/rdr_f9e1b19951644f29a664d86eecc3a5fb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_online_convex_optimization_with_memory_a_f9e1b199_v1,
  title = {Online Convex Optimization with Memory and Control},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-convex-optimization-with-memory-and-control/rdr_f9e1b19951644f29a664d86eecc3a5fb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}