Expert Problem and Hedge Algorithm

Core Idea

The expert problem is the canonical online learning setting: at each round, a learner must choose among N experts' advice, then suffers the loss of the chosen expert. The goal is to achieve cumulative loss close to the best expert in hindsight. The Hedge algorithm (also called the exponential weights algorithm) solves this by maintaining a probability distribution over experts, updated multiplicatively: p_i^{(t+1)} proportional to p_i^{(t)} * exp(-eta * loss_i^{(t)}). Hedge achieves regret O(sqrt(T * ln N)), which is optimal — no algorithm can do better against an adversary. The expert problem serves as the theoretical foundation for ensemble methods, model selection, and boosting.

Explainer

The expert problem is the simplest and most fundamental setting in online learning. Each round, N experts offer advice (implicitly, through their predicted actions), the learner chooses one or randomizes among them, and then nature reveals the outcome and each expert's loss. The learner's goal is to minimize regret — the gap between its cumulative loss and the best expert's cumulative loss in hindsight. No assumptions are made about how the losses are generated; they could be adversarial.

The Hedge algorithm solves this problem optimally. It maintains a weight w_i for each expert, initialized to 1. At each round: assign probability p_i = w_i / sum_j w_j to expert i, sample an expert according to this distribution (or play the mixed strategy directly if losses are linear), observe all experts' losses, and update w_i <- w_i * exp(-eta * loss_i). The exponential update is the defining feature: experts with high loss see their weights decrease exponentially, while low-loss experts maintain or increase their relative weight. Over time, the distribution concentrates on consistently good experts.

The regret analysis uses a potential function argument. Define Phi_t = ln(sum_i w_i^{(t)}). The potential decreases each round by at least eta * (learner's expected loss) - eta^2 (a second-order correction). At the end, the potential is at least ln(w_best^{(T)}) = -eta * (best expert's total loss). Combining the upper and lower bounds on the potential change gives: learner's loss <= best expert's loss + (ln N)/eta + eta * T. The optimal eta = sqrt(ln(N)/T) balances these terms, yielding regret 2 * sqrt(T * ln N).

The O(sqrt(T * ln N)) regret bound is optimal — a matching lower bound shows no algorithm can achieve o(sqrt(T * ln N)) regret in the worst case. The logarithmic dependence on N is remarkable and practically important: the cost of including additional experts is negligible. This makes the expert framework a natural foundation for ensemble methods (combine many base learners), model selection (compete with a pool of candidate models), and online portfolio selection (compete with the best stock in hindsight). The Hedge algorithm also serves as the template for more sophisticated online learning algorithms — online mirror descent generalizes Hedge from discrete experts to continuous action spaces, inheriting its optimal regret guarantees.