Online learning

Problem

A fraud model scores card payments. You trained it on last quarter's data and it worked. Then fraudsters changed tactics, a new merchant category launched, and a holiday shifted spending. The model still answers every request, with the same confidence, and gets steadily worse. Retraining from scratch every night on all history is slow and still averages the old world with the new one.

A second version of the same problem: a news site must choose which of three headlines to show. It only learns whether a headline gets clicks by showing it. Show the current favourite every time and you never find out that another headline is better; show them all equally and you waste traffic on the bad ones. Here the learner's own choices decide which labels it collects.

Without online learning, a model is frozen at the moment it was fitted. Online methods keep it current in constant memory, at the cost of new failure modes: forgetting, sensitivity to the step size, and noisy updates.

Intuition

Think of a thermostat rather than a blueprint. It does not plan the year's heating in advance; it measures, nudges, and measures again. An online learner does the same: for each new example it first predicts, then sees the true answer, scores its mistake, and nudges its weights a little to make that mistake smaller. It never revisits old data. Its memory of the past lives only in its current weights.

How big each nudge is decides everything. Big nudges forget the past quickly, which is good when the world changes and bad when it does not (the model chases noise). Small nudges average over a long history, which is good when the world is stable and bad after a change (the model is stuck in the past). A step size that shrinks over time, the classic choice for a fixed problem, slowly turns the learner into a frozen model.

Bandits add a second dial: explore or exploit. You can only learn how good an option is by trying it. The good strategies try each option enough to be confident, then spend most of their time on the best one, and they keep a little doubt alive for options they have tried only rarely.

Mechanics

The online protocol

At each round t = 1, 2, …, T the learner holds weights w_t, receives x_t, predicts, then suffers loss ℓ_t(w_t). Online gradient descent updates

w_t+1 = w_t − η_t ∇ℓ_t(w_t)

which is stochastic gradient descent (see optimizers) with each example used once. Scoring each example before training on it is called prequential evaluation; its running average is an unbiased estimate of the learner's current error, without a held-out set.

Regret

With no assumption that the data are i.i.d., or even random, the yardstick is the best single fixed model chosen with hindsight:

Regret_T = Σ_t=1..T ℓ_t(w_t) − min_w Σ_t=1..T ℓ_t(w)

An algorithm "learns" if regret is sublinear, so Regret_T/T → 0: on average it does as well as the best fixed model. For convex losses with bounded gradients, online gradient descent with η_t ∝ 1/√t has regret O(√T) (Zinkevich, 2003); for strongly convex losses, η_t ∝ 1/t gives O(log T). Regret against a fixed comparator is the wrong yardstick once the data drift; then the comparator is allowed to move, and decaying step sizes are no longer the right choice.

Concept drift

Drift means the joint distribution p(x, y) changes over time. Covariate shift changes p(x) only; concept drift changes p(y | x), the rule itself. It can be sudden, gradual, or recurring (seasons). The standard responses are:

• Forget on purpose. A constant step size weights an example k steps old by roughly (1 − η·c)^k, an exponential moving window. A sliding-window refit does the same with a hard edge.
• Detect and reset. Monitor the prequential error; when it rises significantly (tests such as DDM, Page–Hinkley or ADWIN), retrain or raise the step size. A later page on monitoring and drift covers detection in production.
• Ensembles over time. Keep models trained on different periods and weight them by recent accuracy.

partial_fit in scikit-learn

Estimators that can learn incrementally expose partial_fit(X, y). SGDClassifier.partial_fit runs one epoch of SGD over the batch it is given (it calls _partial_fit with max_iter=1), and needs classes= on the first call because a batch may not contain every label. It keeps the step counter t_ across calls: _partial_fit sets it to 1.0 only if it does not exist yet (lines 655–656), and each fit adds the number of samples it processed (line 776). The schedules read that counter inside the Cython loop (_sgd_fast.pyx.tp 457–488):

• "optimal", the classifier's default: η = 1 / (α·(t₀ + t − 1)), with t₀ chosen by Bottou's heuristic so the first step is a sensible size.
• "invscaling", the regressor's default: η = eta0 / t^power_t, with eta0=0.01 and power_t=0.25.
• "constant": η = eta0, which keeps adapting forever.
• "pa1"/"pa2": the passive-aggressive updates (Crammer et al., 2006), which step only as far as needed to fix the current mistake.

Because t_ only grows, a long-running partial_fit loop with a decaying schedule ends up taking tiny steps: it converges on a stationary stream and stops adapting on a drifting one.

Bandits

A K-armed bandit has arms with unknown mean rewards μ₁, …, μ_K. Each round the learner pulls one arm and sees only that arm's reward. Its (pseudo-)regret after T rounds is

Regret_T = Σ_t (μ* − μ_at) = Σ_a Δ_a · E[N_a(T)]

where Δ_a = μ* − μ_a is arm a's gap and N_a its pull count. Lai and Robbins (1985) showed any consistent policy must pull each bad arm Ω(log T) times, so logarithmic regret is the best possible. Three standard policies:

• ε-greedy. With probability ε pull a random arm, otherwise the arm with the best empirical mean. Simple, but with fixed ε it keeps exploring forever, so its regret grows linearly at ε·(average gap) per round.
• UCB1 (Auer, Cesa-Bianchi and Fischer, 2002). Pull each arm once, then the arm maximizing μ̂_a + √(2 ln t / N_a). The bonus is large for rarely tried arms ("optimism in the face of uncertainty") and shrinks as evidence accumulates. Regret O(Σ_a log T / Δ_a).
• Thompson sampling (Thompson, 1933). Keep a posterior per arm, for 0/1 rewards a Beta(1 + successes, 1 + failures); each round draw one sample from each posterior and pull the arm with the largest draw. It explores in proportion to the probability that each arm is the best, and matches the Lai–Robbins bound for Bernoulli arms.

Contextual bandits (LinUCB, linear Thompson sampling) condition the choice on features x_t; full reinforcement learning adds state that the actions change.

Worked example

Every number below comes from tested helpers in ml_models_docs.py with fixed seeds.

Implementation

Streaming a classifier with partial_fit, scoring each batch before training on it, and a constant step so it keeps adapting; then Thompson sampling for a Bernoulli bandit in plain Python:

import numpy as np, random
from sklearn.linear_model import SGDClassifier

clf = SGDClassifier(loss="log_loss", learning_rate="constant", eta0=0.01, alpha=1e-4)
classes = np.array([0, 1])
errors = []
for i, (X_batch, y_batch) in enumerate(stream_of_batches()):   # never holds the full data
    if i > 0:
        errors.append(1 - clf.score(X_batch, y_batch))          # prequential: test, then train
    clf.partial_fit(X_batch, y_batch, classes=classes if i == 0 else None)

def thompson(pull, n_arms, rounds):
    wins, losses = [0] * n_arms, [0] * n_arms
    for _ in range(rounds):
        draws = [random.betavariate(1 + wins[a], 1 + losses[a]) for a in range(n_arms)]
        a = max(range(n_arms), key=draws.__getitem__)
        if pull(a):          # 1 if the user clicked
            wins[a] += 1
        else:
            losses[a] += 1
    return wins, losses

Other scikit-learn estimators with partial_fit include MultinomialNB, MiniBatchKMeans, IncrementalPCA and MLPClassifier. Preprocessing must be online too: a StandardScaler fitted on the first day leaks a stale mean into every later prediction, so update it with its own partial_fit or use stateless features such as hashing. In PyTorch, online learning is just a training loop that calls optimizer.step() once per arriving batch and never loops over epochs (see the training loop).

Tradeoffs

• Online versus periodic retraining. Online updates react within seconds and use constant memory, but a bad batch (a bot attack, a logging bug) goes straight into the weights. Nightly retraining on a window is easier to test, roll back and reproduce. Many systems retrain periodically and update only a few parameters (a bias term, a bandit) online.
• Step size is the forgetting rate. Decaying schedules (sklearn's defaults) suit stationary data; under drift, use a constant step, a sliding window or a drift detector that resets.
• Catastrophic forgetting. A neural net trained online on a changed distribution can lose old skills entirely; replay buffers or regularizing toward old weights reduce it.
• Delayed and biased labels. Fraud labels arrive weeks later, and a model that blocks transactions never sees whether the blocked ones were fraud. Bandit-style exploration or holdout traffic is the only fix for the second.
• Bandits versus A/B tests. A bandit earns more during the experiment by shifting traffic to the winner; an A/B test with fixed allocation gives cleaner, unbiased effect estimates. Logged bandit data needs propensity weighting to evaluate a new policy (see causal inference).
• Policy choice. Thompson sampling is usually the best default for Bernoulli rewards and is easy to extend; UCB gives deterministic, analyzable behaviour; ε-greedy is the easiest to explain but never stops paying for exploration unless ε decays.

Connections

References

• Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML 2003.
• Hazan. Introduction to Online Convex Optimization. 2016, revised 2019. arXiv:1909.05207
• Bottou. Large-Scale Machine Learning with Stochastic Gradient Descent. COMPSTAT 2010.
• Crammer, Dekel, Keshet, Shalev-Shwartz and Singer. Online Passive-Aggressive Algorithms. JMLR, 2006.
• Gama, Žliobaitė, Bifet, Pechenizkiy and Bouchachia. A Survey on Concept Drift Adaptation. ACM Computing Surveys, 2014.
• Lai and Robbins. Asymptotically Efficient Adaptive Allocation Rules. Advances in Applied Mathematics, 1985.
• Auer, Cesa-Bianchi and Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 2002.
• Thompson. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 1933.
• Russo, Van Roy, Kazerouni, Osband and Wen. A Tutorial on Thompson Sampling. 2018. arXiv:1707.02038
• Lattimore and Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
• scikit-learn 1.9.1: SGDClassifier, SGDRegressor, step-size schedules.