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:
- Partially Observed Systems: Ali̇ Devran Kara and Serdar Yuksel show in Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes that a finite window of history is often a "near-sufficient" statistic for control, meaning we don't need to track an infinite belief state.
- Infrastructure: In NoSQL Schema Design for Time-Dependent Workloads, Yusuke Wakuta and colleagues treat database reconfiguration as a stateful optimization problem where the "memory" is the cost of moving data between configurations.
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.