In classical online learning, we often assume a "stateless" world. An agent makes a decision, receives a penalty, and moves on. The next round is a fresh start. However, real-world systems—from robotic controllers to data center schedulers—rarely behave this way. In these environments, an action taken today echoes into the future, influencing both the costs we pay and the states we inhabit tomorrow.
This research direction, often termed Online Convex Optimization with Memory (OCO-M) or Non-stochastic Control, seeks to bridge the gap between the reactive nature of online learning and the persistent dynamics of control theory.
The Ghost of Decisions Past
The fundamental challenge in these systems is temporal coupling. In a standard model, the loss at time $t$ depends only on the current action $x_t$. But as Anava et al. describe, many scenarios involve "adversaries with memory," where the loss function $f_t$ depends on a sequence of past decisions $(x_t, x_{t-1}, \dots, x_{t-m})$.
Consider a few intuitive examples of this coupling:
- Physical Wear-and-Tear: In industrial equipment, toggling a machine on and off frequently incurs "switching costs." As Li et al. and Krishnasamy et al. note, these costs create a dependency where your current choice is constrained by your previous one to avoid inefficiency or damage.
- System Dynamics: In robotics, a control input doesn't just produce a cost; it changes the robot's position and velocity. Simchowitz demonstrates that these dynamical systems can be modeled as OCO where the loss depends on an affine combination of previous decisions.
- Resource Constraints: In sequential bin packing, György et al. show that every item placed reduces the capacity available for future items, creating a memory effect that traditional regret-minimization algorithms fail to capture.
Why Standard Algorithms Fail
If you apply a standard Online Gradient Descent (OGD) algorithm to a system with memory, it tends to be "myopic." It optimizes for the immediate loss without realizing that a slightly higher cost now might prevent a catastrophic cost later.
As Karapetyan et al. argue, traditional methods fail because they do not account for how current decisions propagate through system dynamics. This propagation means that the feedback received at any moment is "biased" by the history of past explorations, a problem particularly acute when only bandit feedback (a single scalar loss) is available, as explored by Gradu et al..
Bridging the Gap: Memory-Aware Optimization
To solve this, researchers have developed frameworks that explicitly incorporate history into the optimization step. The core intuition is to optimize a surrogate loss function that accounts for the "long-term" impact of a decision.
- Policy Parametrization: Instead of choosing an action $x_t$ directly, the agent chooses a policy. Cassel et al. and Sun et al. use "Disturbance-Action" policies, which represent the control input as a linear combination of past disturbances. This turns a stateful control problem into a stateless optimization problem over the policy parameters.
- Memory Buffers: Algorithms like those proposed by Liu et al. and Jiang et al. use memory-aware subroutines. By maintaining a buffer of past actions, the controller can estimate how a change in the current policy would have affected the costs over the entire memory horizon.
- Meta-Learning for Non-Stationarity: In environments that change over time, Zhao et al. introduced Scream, which uses a meta-base decomposition to handle both memory and non-stationary costs, achieving optimal dynamic regret.
Efficiency and Safety
Moving from theory to practice requires addressing two final hurdles: computational speed and safety.
For high-speed applications, Zhou et al. introduced Meta-OFW, a projection-free algorithm. By replacing expensive quadratic projections with simpler linear optimizations (Frank-Wolfe), they achieved significant speedups while maintaining robust performance in time-varying environments.
Regarding safety, Preiss et al. and Jiang et al. have developed methods to ensure system stability and constraint satisfaction. By creating "buffer zones" or using stability-guaranteed switching mechanisms, these algorithms ensure that the learning process doesn't cause the system to "blow up" while it searches for the optimal strategy.
Ultimately, this research direction proves that we can learn to control complex, adversarial systems as effectively as simple ones, provided we respect the persistent "memory" of the physical world.
Key Foundational Work
On-line Sequential Bin Packing. (2008) — contributed 1 concept elements to this direction.
Online Learning for Adversaries with Memory: Price of Past Mistakes (2015) — contributed 1 concept elements to this direction.