Online Learning
Online learning is the machine learning paradigm in which a model learns sequentially from a stream of data, updating its predictions after each observation rather than training on a fixed batch. Unlike supervised learning, which assumes a static training distribution, online learning treats the data-generating process as potentially non-stationary and the learner as perpetually adapting. The framework is essential for any setting where data arrives continuously and where the underlying distribution may shift without warning — financial markets, recommendation systems, network traffic, and sensor streams.
The formal model is starkly different from batch learning. At each round t, the learner receives an input x_t, makes a prediction ŷ_t, observes the true outcome y_t, and incurs a loss L(y_t, ŷ_t). The learner then updates its hypothesis before the next round. There is no separation between training and testing; every prediction is a test, and every observation is a training example. The goal is not to minimize empirical risk on a fixed sample but to minimize cumulative regret: the difference between the learner's total loss and the total loss of the best fixed hypothesis in hindsight.
The Regret Framework
The central analytical tool in online learning is regret. An algorithm has sublinear regret if its average per-round regret approaches zero as the number of rounds grows. This is the online analogue of statistical consistency: it guarantees that the learner performs, in the long run, as well as the best strategy that could have been chosen with full knowledge of the future. The no-regret property is surprisingly achievable: algorithms like Hedge, Online Gradient Descent, and Follow-the-Regularized-Leader achieve O(√T) or O(log T) regret under mild assumptions.
The regret framework is powerful because it makes minimal assumptions about the data. The sequence need not be independent, identically distributed, or even stationary. It can be adversarial — chosen by an opponent who knows the learner's algorithm — and the regret bound still holds. This robustness makes online learning the natural bridge between machine learning and game theory, where opponents are strategic rather than stochastic. The connection is precise: a no-regret learning algorithm, when played by all agents in a repeated game, converges to the set of correlated equilibria.
Bandit Problems and Partial Information
In many online settings, the learner does not observe the full feedback structure. A recommendation system knows whether a user clicked, but not what they would have clicked had other items been shown. A drug trial observes the outcome of the chosen treatment, not the counterfactual outcomes of alternatives. These are bandit problems, named after the slot machine analogy: the learner chooses among arms (actions), observes the reward of the chosen arm, and must balance exploration (trying uncertain arms to gather information) with exploitation (choosing the arm with the highest estimated reward).
The multi-armed bandit was introduced by Robbins in 1952 and has become one of the most studied problems in online learning. The regret bounds are typically worse than in the full-information setting — O(√T) rather than O(log T) for stochastic bandits — but the algorithms are remarkably effective in practice. Thompson sampling, Upper Confidence Bound (UCB), and exponential weighting schemes have been deployed in web advertising, clinical trials, and dynamic pricing with measurable success.
Adaptation and Non-Stationarity
The deepest challenge in online learning is not the absence of a training set but the possibility that the problem itself changes. A model that minimizes cumulative regret against a fixed best hypothesis will fail when the best hypothesis changes over time — what is called regime shift or concept drift. This connects online learning directly to the problem of structural breaks in econometrics and to continual learning in artificial intelligence.
Recent approaches use change-point detection to reset the learning algorithm when drift is detected, or maintain a portfolio of specialists each tuned to a different regime. These methods are still imperfect: detecting change is itself a statistical problem with tradeoffs between false positives and delayed detection. The fundamental tension is that adaptation requires forgetting, but indiscriminate forgetting sacrifices the knowledge accumulated during stable periods.
Online learning is not merely a technical variant of batch learning. It is a different epistemological stance: the assumption that the world changes, that the model must change with it, and that the only test of a learner is its performance on the stream it actually faces. The batch learning paradigm — learn once, deploy forever — is a Newtonian fantasy that assumes a stationary universe. Online learning is the thermodynamics of machine learning: it acknowledges that entropy increases, that distributions shift, and that the only sustainable strategy is perpetual adaptation. The field that treats online learning as a niche topic for streaming data, rather than as the default framework for real-world deployment, is still living in the batch-learning delusion.