Online Learning

Why Online Learning Matters

In traditional batch machine learning, algorithms train offline on a static dataset to produce a fixed model. However, real-world systems—such as ad click-through rate (CTR) prediction, financial portfolio management, real-time routing, and automated trading—operate in dynamic, non-stationary, or even adversarial environments. Data arrives sequentially as a stream, data distributions drift over time, and delayed offline retraining is far too slow. Online Learning solves this fundamental challenge by updating predictions incrementally round by round, learning directly from streaming feedback without storing historical data or making statistical assumptions about the underlying data-generating distribution.

Instead of optimizing for static statistical accuracy, Online Learning minimizes regret: the difference between the algorithm's cumulative loss and the cumulative loss of the best fixed action (or "expert") selected with the benefit of hindsight. The curriculum scope covers four cornerstone framework algorithms:

1. Multiplicative Weights Update Algorithm (MWUA): A foundational decision-making framework that maintains a set of weights over $K$ experts, penalizing poor performers multiplicatively at each round.
2. Hedge: The continuous, exponential generalization of MWUA for arbitrary real-valued loss vectors $\ell_t \in [0, 1]^K$, achieving optimal $O(\sqrt{T \ln K})$ regret against an adversarial opponent over $T$ rounds.
3. Follow the Leader (FTL): A greedy strategy that picks the action minimizing cumulative past loss, which performs well in benign environments but fails catastrophically ($O(T)$ regret) under adversarial conditions.
4. Follow the Regularized Leader (FTRL): A robust framework that stabilizes FTL by adding a convex regularizer $R(w)$ to the cumulative loss objective, uniting online gradient descent, mirror descent, and Hedge under a single unified mathematical principle.

After completing this lesson, you will be able to formulate online decision problems, compute per-round weight updates and regret bounds, implement production-ready Hedge and FTRL algorithms in Python, C++, and Java, and identify when to apply regularization to prevent adversarial oscillation.

Core Concepts and Terminology

Online Learning operates as an iterative game played between a learner (decision-maker) and an environment (which may be stochastic or malicious) over $T$ discrete time rounds $t = 1, 2, \dots, T$.

At each round $t$:

• The learner maintains a probability distribution $p_t = (p_{t,1}, p_{t,2}, \dots, p_{t,K})$ over $K$ candidate actions or experts, where $\sum_{i=1}^K p_{t,i} = 1$ and $p_{t,i} \ge 0$.
• The learner selects an action (or plays the distribution $p_t$).
• The environment simultaneously or reactively reveals a loss vector $\ell_t = (\ell_{t,1}, \ell_{t,2}, \dots, \ell_{t,K}) \in [0, 1]^K$.
• The learner incurs an expected loss $\langle p_t, \ell_t \rangle = \sum_{i=1}^K p_{t,i} \ell_{t,i}$.
• The learner updates its internal state (weights or cumulative losses) to produce $p_{t+1}$ for the next round.

The central performance metric is Cumulative Regret after $T$ rounds, defined as:

$$R_T = \sum_{t=1}^T \langle p_t, \ell_t \rangle - \min_{i \in \{1, \dots, K\}} \sum_{t=1}^T \ell_{t,i}$$

An online learning algorithm is considered successful if its regret is sublinear in $T$ (i.e., $R_T = o(T)$), which guarantees that the average per-round regret vanishes as $T \to \infty$: $\lim_{T \to \infty} \frac{R_T}{T} = 0$.

How Online Learning Works, Step by Step

The operational sequence for Hedge / Multiplicative Weights follows a systematic three-stage loop per round $t$:

1. Normalize Weights to Probability Distribution: Given current unnormalized weights $w_{t} = (w_{t,1}, \dots, w_{t,K})$, compute total mass $W_t = \sum_{i=1}^K w_{t,i}$. Set $p_{t,i} = \frac{w_{t,i}}{W_t}$ for all $i \in \{1, \dots, K\}$.

1. Commit Action & Observe Loss: Predict distribution $p_t$. Observe loss vector $\ell_t = (\ell_{t,1}, \dots, \ell_{t,K})$. * Compute suffered expected round loss $\ell_{\text{alg}, t} = \langle p_t, \ell_t \rangle$.

1. Multiplicative Weight Decay: * For each expert $i$, penalize weight exponentially based on its individual loss $\ell_{t,i}$:

$$w_{t+1, i} = w_{t, i} \cdot \exp(-\eta \ell_{t,i})$$

• High-loss experts experience rapid exponential decay, shifting future distribution mass toward consistently low-loss experts.

flowchart TD
A[Start: Initialize weights w_1 = 1 for all K experts, η > 0] --> B[Loop Round t = 1 to T]

```

B --> C[Compute sum W_t = sum_i w_t,i]
C --> D[Normalize probabilities: p_t,i = w_t,i / W_t]
D --> E[Play distribution p_t]
E --> F[Observe environment loss vector ℓ_t]
F --> G[Incur expected algorithm loss: ⟨p_t, ℓ_t⟩]
G --> H[Accumulate total algorithm loss and expert losses]

H --> I{Algorithm Type?}
I -- Hedge / MWUA --> J[Update weights: w_{t+1,i} = w_{t,i} * exp\(-η * ℓ_{t,i}\)]
I -- FTL --> K[Set next action: argmin_i sum_{s=1}^t ℓ_{s,i}]
I -- FTRL --> L[Solve argmin_w \(sum_{s=1}^t ⟨w, ℓ_s⟩ + R\(w\)/\eta\)]

J --> M[Advance to Round t + 1]
K --> M
L --> M
M --> B

B -- Round T Finished --> N[Output Final Regret: R_T = Total Alg Loss - Min Expert Loss]

```

Worked Example with a Full Trace

Let us execute a complete step-by-step trace of the Hedge algorithm over $T = 4$ rounds with $K = 3$ experts and learning rate $\eta = 0.5$.

Setup:

• $K = 3$ experts ($E_1, E_2, E_3$).
• Initial weights: $w_1 = [1.0, 1.0, 1.0]$.
• Learning rate: $\eta = 0.5$.
• Sequence of loss vectors $\ell_t$:
• $t=1$: $\ell_1 = [0.0, 1.0, 0.5]$
• $t=2$: $\ell_2 = [1.0, 0.0, 0.5]$
• $t=3$: $\ell_3 = [0.2, 0.8, 0.0]$
• $t=4$: $\ell_4 = [0.0, 0.5, 1.0]$

Step-by-Step Calculation Trace

• Round 1:
• Unnormalized weights $w_1 = [1.0, 1.0, 1.0]$, sum $W_1 = 3.0$.
• Probabilities $p_1 = [0.3333, 0.3333, 0.3333]$.
• Loss vector $\ell_1 = [0.0, 1.0, 0.5]$.
• Algorithm loss $\langle p_1, \ell_1 \rangle = 0.3333(0.0) + 0.3333(1.0) + 0.3333(0.5) = 0.5000$.
• Weight updates ($w_{2,i} = w_{1,i} \cdot e^{-0.5 \cdot \ell_{1,i}}$):
• $w_{2,1} = 1.0 \cdot e^{0} = 1.0000$
• $w_{2,2} = 1.0 \cdot e^{-0.5} = 0.6065$
• $w_{2,3} = 1.0 \cdot e^{-0.25} = 0.7788$
• Sum $W_2 = 2.3853$.

• Round 2:
• Probabilities $p_2 = [1.0/2.3853, 0.6065/2.3853, 0.7788/2.3853] = [0.4192, 0.2543, 0.3265]$.
• Loss vector $\ell_2 = [1.0, 0.0, 0.5]$.
• Algorithm loss $\langle p_2, \ell_2 \rangle = 0.4192(1.0) + 0.2543(0.0) + 0.3265(0.5) = 0.5825$.
• Weight updates ($w_{3,i} = w_{2,i} \cdot e^{-0.5 \cdot \ell_{2,i}}$):
• $w_{3,1} = 1.0000 \cdot e^{-0.5} = 0.6065$
• $w_{3,2} = 0.6065 \cdot e^{0} = 0.6065$
• $w_{3,3} = 0.7788 \cdot e^{-0.25} = 0.6065$
• Sum $W_3 = 1.8196$. Notice all weights equalized!

• Round 3:
• Probabilities $p_3 = [0.3333, 0.3333, 0.3333]$.
• Loss vector $\ell_3 = [0.2, 0.8, 0.0]$.
• Algorithm loss $\langle p_3, \ell_3 \rangle = 0.3333(0.2 + 0.8 + 0.0) = 0.3333$.
• Weight updates:
• $w_{4,1} = 0.6065 \cdot e^{-0.1} = 0.5488$
• $w_{4,2} = 0.6065 \cdot e^{-0.4} = 0.4066$
• $w_{4,3} = 0.6065 \cdot e^{0} = 0.6065$
• Sum $W_4 = 1.5619$.

• Round 4:
• Probabilities $p_4 = [0.5488/1.5619, 0.4066/1.5619, 0.6065/1.5619] = [0.3514, 0.2603, 0.3883]$.
• Loss vector $\ell_4 = [0.0, 0.5, 1.0]$.
• Algorithm loss $\langle p_4, \ell_4 \rangle = 0.3514(0.0) + 0.2603(0.5) + 0.3883(1.0) = 0.5185$.

• Summary Totals:
• Cumulative Algorithm Loss: $0.5000 + 0.5825 + 0.3333 + 0.5185 = 1.9343$.
• Expert $E_1$ Cumulative Loss: $0.0 + 1.0 + 0.2 + 0.0 = 1.2000$.
• Expert $E_2$ Cumulative Loss: $1.0 + 0.0 + 0.8 + 0.5 = 2.3000$.
• Expert $E_3$ Cumulative Loss: $0.5 + 0.5 + 0.0 + 1.0 = 2.0000$.
• Best Expert in Hindsight: $E_1$ with loss $1.2000$.
• Final Regret $R_4 = 1.9343 - 1.2000 = 0.7343$.

Implementation in Python, C++, and Java

The code below implements a production-ready Hedge simulation in Python, C++, and Java using identical logic, identical floating-point precision, and the exact 4-round reference input from the worked example.

## Complete, runnable Hedge Online Learning Simulator in Python
import math

def run_hedge_simulation():
    num_experts = 3
    eta = 0.5
    loss_matrix = [
        [0.0, 1.0, 0.5],  # Round 1
        [1.0, 0.0, 0.5],  # Round 2
        [0.2, 0.8, 0.0],  # Round 3
        [0.0, 0.5, 1.0]   # Round 4
    ]

    weights = [1.0] * num_experts
    cum_expert_losses = [0.0] * num_experts
    cum_alg_loss = 0.0

    print("--- Hedge Online Learning Simulation ---")
    for t, losses in enumerate(loss_matrix, 1):
        sum_w = sum(weights)
        p = [w / sum_w for w in weights]

        round_alg_loss = sum(p[i] * losses[i] for i in range(num_experts))
        cum_alg_loss += round_alg_loss

        for i in range(num_experts):
            cum_expert_losses[i] += losses[i]
            weights[i] *= math.exp(-eta * losses[i])

        p_str = "[" + ", ".join(f"{x:.4f}" for x in p) + "]"
        print(f"Round {t}: p = {p_str}, Loss = {round_alg_loss:.4f}, Cum Loss = {cum_alg_loss:.4f}")

    best_expert_loss = min(cum_expert_losses)
    best_expert_idx = cum_expert_losses.index(best_expert_loss)
    final_regret = cum_alg_loss - best_expert_loss

    print("-" * 50)
    print(f"Cumulative Algorithm Loss: {cum_alg_loss:.4f}")
    print(f"Best Expert (E{best_expert_idx}) Cumulative Loss: {best_expert_loss:.4f}")
    print(f"Final Regret: {final_regret:.4f}")

if __name__ == "__main__":
    run_hedge_simulation()

// Complete, runnable Hedge Online Learning Simulator in C++
#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <algorithm>

void run_hedge_simulation() {
    const int num_experts = 3;
    const double eta = 0.5;
    const std::vector<std::vector<double>> loss_matrix = {
        {0.0, 1.0, 0.5},
        {1.0, 0.0, 0.5},
        {0.2, 0.8, 0.0},
        {0.0, 0.5, 1.0}
    };

    std::vector<double> weights(num_experts, 1.0);
    std::vector<double> cum_expert_losses(num_experts, 0.0);
    double cum_alg_loss = 0.0;

    std::cout << std::fixed << std::setprecision(4);
    std::cout << "--- Hedge Online Learning Simulation ---\n";

    for (size_t t = 0; t < loss_matrix.size(); ++t) {
        const auto& losses = loss_matrix[t];
        double sum_w = 0.0;
        for (double w : weights) sum_w += w;

        std::vector<double> p(num_experts);
        double round_alg_loss = 0.0;
        for (int i = 0; i < num_experts; ++i) {
            p[i] = weights[i] / sum_w;
            round_alg_loss += p[i] * losses[i];
        }
        cum_alg_loss += round_alg_loss;

        for (int i = 0; i < num_experts; ++i) {
            cum_expert_losses[i] += losses[i];
            weights[i] *= std::exp(-eta * losses[i]);
        }

        std::cout << "Round " << (t + 1) << ": p = [";
        for (int i = 0; i < num_experts; ++i) {
            std::cout << p[i] << (i + 1 < num_experts ? ", " : "");
        }
        std::cout << "], Loss = " << round_alg_loss
                  << ", Cum Loss = " << cum_alg_loss << "\n";
    }

    auto min_it = std::min_element(cum_expert_losses.begin(), cum_expert_losses.end());
    double best_expert_loss = *min_it;
    int best_expert_idx = std::distance(cum_expert_losses.begin(), min_it);
    double final_regret = cum_alg_loss - best_expert_loss;

    std::cout << "--------------------------------------------------\n";
    std::cout << "Cumulative Algorithm Loss: " << cum_alg_loss << "\n";
    std::cout << "Best Expert (E" << best_expert_idx << ") Cumulative Loss: " << best_expert_loss << "\n";
    std::cout << "Final Regret: " << final_regret << "\n";
}

int main() {
    run_hedge_simulation();
    return 0;
}

// Complete, runnable Hedge Online Learning Simulator in Java
import java.util.Arrays;

public class Main {
    public static void runHedgeSimulation() {
        int numExperts = 3;
        double eta = 0.5;
        double[][] lossMatrix = {
            {0.0, 1.0, 0.5},
            {1.0, 0.0, 0.5},
            {0.2, 0.8, 0.0},
            {0.0, 0.5, 1.0}
        };

        double[] weights = new double[numExperts];
        Arrays.fill(weights, 1.0);
        double[] cumExpertLosses = new double[numExperts];
        double cumAlgLoss = 0.0;

        System.out.println("--- Hedge Online Learning Simulation ---");

        for (int t = 0; t < lossMatrix.length; t++) {
            double[] losses = lossMatrix[t];
            double sumW = 0.0;
            for (double w : weights) sumW += w;

            double[] p = new double[numExperts];
            double roundAlgLoss = 0.0;
            for (int i = 0; i < numExperts; i++) {
                p[i] = weights[i] / sumW;
                roundAlgLoss += p[i] * losses[i];
            }
            cumAlgLoss += roundAlgLoss;

            for (int i = 0; i < numExperts; i++) {
                cumExpertLosses[i] += losses[i];
                weights[i] *= Math.exp(-eta * losses[i]);
            }

            StringBuilder pStr = new StringBuilder("[");
            for (int i = 0; i < numExperts; i++) {
                pStr.append(String.format("%.4f", p[i])).append(i + 1 < numExperts ? ", " : "");
            }
            pStr.append("]");

            System.out.printf("Round %d: p = %s, Loss = %.4f, Cum Loss = %.4f\n",
                    (t + 1), pStr.toString(), roundAlgLoss, cumAlgLoss);
        }

        double bestExpertLoss = cumExpertLosses[0];
        int bestExpertIdx = 0;
        for (int i = 1; i < numExperts; i++) {
            if (cumExpertLosses[i] < bestExpertLoss) {
                bestExpertLoss = cumExpertLosses[i];
                bestExpertIdx = i;
            }
        }
        double finalRegret = cumAlgLoss - bestExpertLoss;

        System.out.println("--------------------------------------------------");
        System.out.printf("Cumulative Algorithm Loss: %.4f\n", cumAlgLoss);
        System.out.printf("Best Expert (E%d) Cumulative Loss: %.4f\n", bestExpertIdx, bestExpertLoss);
        System.out.printf("Final Regret: %.4f\n", finalRegret);
    }

    public static void main(String[] args) {
        runHedgeSimulation();
    }
}

Complexity, Correctness, and Invariants

Evaluating online learning algorithms involves analyzing per-round time overhead, space footprint, and theoretical regret bounds against adversarial inputs.

Variants, Pitfalls, and Optimizations

Why Follow the Leader (FTL) Fails Without Regularization

A classic pitfall in online decision making is relying on unregularized Follow the Leader (FTL). In adversarial settings, FTL suffers $O(T)$ linear regret due to extreme sensitivity to past losses.

Consider a 2-expert game over $T$ rounds where the adversary alternates loss vectors:

• Round 1: $\ell_1 = [0.5, 0.0] \implies$ FTL picks $E_2$ for Round 2.
• Round 2: $\ell_2 = [0.0, 1.0] \implies$ Cumulative losses $[0.5, 1.0] \implies$ FTL switches to $E_1$.
• Round 3: $\ell_3 = [1.0, 0.0] \implies$ Cumulative losses $[1.5, 1.0] \implies$ FTL switches back to $E_2$.

FTL gets "chased around" by the adversary, incurring maximum loss at every step ($R_T = \Omega(T)$). Adding regularization (FTRL / Hedge) stabilizes decisions, keeping predictions smooth and preventing single-round overreaction.

Practice Problems and Real-World Use

Online learning algorithms are core primitives across high-frequency finance, ad networks, recommendation engines, and optimization theory.