onlinelearning.py, which recomputes what the entry states: the script block by block · open in ColabDictionary of Applied Machine Learning: 114 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here
Updated on 2026-10-29
Readiness 100/100
See also stochastic gradient descent gradient descent empirical risk minimization reinforcement learning linear regression
Online learning refers to machine learning (ML) methods that continuously update the model parameters as new data points arrive over time. This contrasts with offline methods such as linear regression, which solve empirical risk minimization (ERM) once over a fixed training set. The updates are based on some form of feedback: examples are an entire loss function determined by the new data point, or a reward signal. Online gradient descent (online GD) uses an entire loss function as feedback; bandit and reinforcement learning (RL) methods replace the unavailable gradient by an estimate from the feedback. The figure of merit is the regret: the accumulated loss minus that of fixed model parameters chosen in hindsight. A method is successful if its regret per round vanishes as the number of rounds grows.
onlinelearning.py, which recomputes what the entry states: the script block by block · open in ColabB-dataA weather station reports one
temperature reading per hour, and a forecast for the next hour must
be issued before that reading arrives. An offline method such as
linear regression first collects readings into a training set and trains
a model on it once. It then forecasts with the learned
model parameters, which stay fixed from then on: while it collects, it issues no
forecast, and after it has trained, it no longer learns. An online
learning method instead adapts its model parameters every time a
new reading arrives; Fig. 1 shows
both on three days of readings.
pythondemos/onlinelearning.py
Some online learning applications provide only a single loss
or reward value as feedback, called bandit feedback in
contrast to full information
(Fig. 2). For example, a clinic
that gives one of several treatments observes the outcome of that
treatment alone, which is a multiarmed bandit (MAB)
(Lattimore and Szepesvári, 2020, Ch. 1). A thermostat whose heating
decision changes the temperature it faces in the next hour receives
a reward together with a new state, which is
reinforcement learning (RL) (Sutton and Barto, 2018, Ch. 3).
pythondemos/onlinelearning.py
With full information, the data point ${\mathbf z}^{(t)}$ is revealed, and it determines $f^{(t)}({\mathbf w}) = L\left({\mathbf z}^{(t)},{\mathbf w} \right)$ for every ${\mathbf w} \in \mathcal{W}$. On the temperature stream, the data point ${\mathbf z}^{(t)} = ({\mathbf x}^{(t)}, y^{(t)})$ has as features, collected in the feature vector ${\mathbf x}^{(t)}$, the readings of the previous hours, and as label the reading of hour $t$. Its loss function $f^{(t)}$ is the squared error loss of the forecast $h^{({\mathbf w})}({\mathbf x}^{(t)})$.
With bandit feedback, only the value $f^{(t)}({\mathbf w}^{(t)})$ is revealed. In an MAB with $A$ actions, the model parameters ${\mathbf w}^{(t)} \in \Delta^{A-1}$ form the probability mass function (pmf) from which the action $a^{(t)}$ is drawn. The environment fixes a loss vector $\boldsymbol{\ell}^{(t)} \in [0,1]^{A}$, whose entry $\ell^{(t)}_{a}$ is the loss of action $a$ in round $t$, so the expected loss of the draw is $f^{(t)}({\mathbf w}) = \langle \boldsymbol{\ell}^{(t)}, {\mathbf w} \rangle$. The clinic observes the single entry $\ell^{(t)}_{a^{(t)}}$, the loss of the action drawn, and no other entry.
With RL feedback, the immediate reward $r(s^{(t)}, a^{(t)})$ of the action taken and the next state $s^{(t+1)}$ of a Markov decision process (MDP) are revealed. The loss $f^{(t)}({\mathbf w})$ is the negative expected reward of the policy with model parameters ${\mathbf w}$ in the state $s^{(t)}$. That state depends on the actions of the earlier rounds, so the environment's losses depend on the method's own past.
B-roundsThe method then updates the model parameters using the feedback,
\begin{equation}
\label{equ_def_onlinelearning_update_dict}
{\mathbf w}^{(t+1)} :=
\mathcal{F}^{(t)}\big({\mathbf w}^{(t)}, r^{(t)}\big)
\text{,}
\end{equation}
with an update operator $\mathcal{F}^{(t)}$ specific
to the method, the counterpart of the operator $\mathcal{F}$
of a fixed-point iteration (Fig. 3). The time
index is also the iteration index: one update for any newly
arriving data point. This contrasts with batch learning,
which solves empirical risk minimization (ERM) once over a fixed training set and then uses
the learned hypothesis.
With full information, online GD uses the gradient ${\mathbf g}^{(t)} := \nabla f^{(t)}({\mathbf w}^{(t)})$ in a projected gradient step. Online mirror descent (online MD) replaces the Euclidean distance of the projection by a Bregman divergence, e.g., the Kullback–Leibler divergence (KL divergence) on the probability simplex, which gives the Hedge update of the pmf over the actions (Hazan, 2022, Sect. 5.4). Follow-The-Regularized-Leader (FTRL) commits, in every round, to a minimizer of the accumulated loss of all rounds so far plus a regularizer (Hazan, 2022, Sect. 5.2).
With bandit feedback, the gradient of $f^{(t)}$ is not available, since only one entry of $\boldsymbol{\ell}^{(t)}$ is observed. Exp3 forms an unbiased estimate of $\boldsymbol{\ell}^{(t)}$ by dividing the observed entry by the probability of the drawn action, and applies the online MD update to the estimate (Auer et al., 2002, Sect. 3).
With RL feedback, Q-learning changes one entry of a table of action values, the entry of the state visited and the action taken. The entry moves by a fixed fraction of the difference between its target, the reward received plus the discounted largest value of the next state, and its current value. This is a stochastic step of the Bellman operator, a contraction (Bertsekas, 2007, Sect. 1.2), so Q-learning, unlike online GD, does have a fixed point interpretation (Sutton and Barto, 2018, Sect. 6.5). Policy gradient methods instead estimate the gradient of the expected reward from the rewards collected along the visited states (Sutton and Barto, 2018, Ch. 13).
The figure of merit of an online learning method is not the decrease of an objective function along the iterates, which measures the progress of GD: online learning has no fixed objective function. The loss function $f^{(t)}$ of round $t$ is evaluated once, around ${\mathbf w}^{(t)}$, and the next round brings a different loss function. Instead, an online learning method is evaluated by its regret.
The regret is the excessive accumulated loss compared to that of a fixed choice ${\mathbf w} \in \mathcal{W}$ of the model parameters. This fixed choice ${\mathbf w}$ is kept for all rounds $t = 1, \ldots, T$ and can be chosen after all losses are known. After $T$ rounds, the regret relative to ${\mathbf w} \in \mathcal{W}$ is \[ \mathrm{Regret}_{T}({\mathbf w}) := \sum_{t=1}^{T} f^{(t)}({\mathbf w}^{(t)}) - \sum_{t=1}^{T} f^{(t)}({\mathbf w}) \text{.} \] In an MAB, the fixed ${\mathbf w}$ of interest is the pmf concentrated on one action. The regret is then measured against the best single action in hindsight; in RL, against the best fixed policy (Jaksch et al., 2010, Sect. 2).
No assumption is made on how the losses are generated: the regret is defined for every sequence $f^{(1)}, f^{(2)}, \ldots$, even one chosen by an opponent who has seen ${\mathbf w}^{(t)}$. An online learning method is successful if its regret per round, $\mathrm{Regret}_{T}({\mathbf w})/T$, vanishes as $T$ grows for every ${\mathbf w} \in \mathcal{W}$ (Shalev-Shwartz, 2012, Sect. 1.1).
Regret bounds. The rate at which the regret per round vanishes depends on the feedback. With full information and convex losses whose gradients have norm at most $G$ on a parameter space of diameter $D$, online GD with the learning rate $\eta^{(t)} = D/(G\sqrt{t})$ has $\mathrm{Regret}_{T}({\mathbf w}) \le \tfrac{3}{2} DG\sqrt{T}$ (Hazan, 2022, Thm. 3.1). No online algorithm can guarantee a regret below a constant times $DG\sqrt{T}$ for every sequence: for each algorithm there is a sequence of losses on which its regret is at least that (Hazan, 2022, Thm. 3.2).
With bandit feedback over $A$ actions, the expected regret of Exp3 is at most $2\sqrt{(e-1) T A \ln A}$ (Auer et al., 2002, Cor. 3.2): observing one entry of $\boldsymbol{\ell}^{(t)}$ instead of all of them costs the factor $\sqrt{A}$. With RL feedback in an MDP with $S$ states and $A$ actions, the UCRL2 method has regret at most a constant times $S \sqrt{A T \ln T}$, the constant depending on how many steps it takes to reach any state from any other (Jaksch et al., 2010, Thm. 2). In each case the regret per round vanishes as $T$ grows.
B-regretFig. 4 shows the regret per
round of online GD and of follow-the-leader, the FTRL
method without its regularizer, which commits in every round
to a minimizer of the accumulated loss so far, on a year of
hourly temperature readings. For linear regression with the
squared error loss, that minimizer is computed by
the recursive least-squares update, which carries the least-squares
solution from time $t - 1$ to time $t$ in closed form
(Haykin, 2002).
pythondemos/onlinelearning.py
With full information, all five errors are observed after each hour and Hedge updates the pmf; with bandit feedback, only the error of the forecaster used is observed and Exp3 updates the pmf from its estimate of the loss vector.
B-banditThe regret of Hedge after $T$ rounds is at most
$\sqrt{2 T \ln A}$ for losses in $[0,1]$, a
weakening of the bound $\ln A / \eta + \eta T / 8$
of Cesa-Bianchi and Lugosi (2006, Thm. 2.2) at the learning rate
$\eta = \sqrt{2 \ln A / T}$; for Exp3, the
bound on the expected regret stated for bandit feedback
applies with $A = 5$. Both
regrets per round vanish, and the regret of Exp3
stays larger than that of Hedge, the increase in regret
caused by
bandit feedback.
pythondemos/onlinelearning.py
See also: online gradient descent, online algorithm, regret, Hedge, Exp3, online mirror descent, mirror descent, Follow-The-Regularized-Leader, stochastic gradient descent, gradient descent, gradient step, empirical risk minimization, risk, multiarmed bandit, reinforcement learning, Markov decision process, Q-learning, batch learning, fixed-point iteration, linear regression.
@misc{dictml_onlinelearning,
author = {Jung, Alexander},
editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
title = {online learning},
howpublished = {Dictionary of Applied Machine Learning (course edition)},
year = {2026},
doi = {10.5281/zenodo.21569296},
note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-03},
url = {https://dictionaryofml.org/terms/onlinelearning.html}
}