COMPX270 — Randomised and Advanced Algorithms
Chapter 12: Learning from Experts
Online prediction with expert advice: from the consistent expert algorithm and halving to the powerful Multiplicative Weights Update framework and its randomised variant.
Potential functions, logarithmic bounds, randomised rounding, trade-off analysis
The Expert Advice Setting
Problem Setup
Over \(T\) time steps, we have \(n\) experts \(A_1, \ldots, A_n\). At each step \(t\):
- Receive advice \(v_{i,t} \in \{0, 1\}\) from each expert \(A_i\).
- Make a prediction \(u_t \in \{0, 1\}\).
- Observe the truth \(\bar{u}_t\) and pay cost \(c_t = \mathbf{1}[u_t \neq \bar{u}_t]\).
Our total cost over \(T\) rounds is \(C(T) = \sum_{t=1}^{T} c_t\). Expert \(A_i\) has total cost \(C_i(T) = \sum_{t=1}^{T} \mathbf{1}[v_{i,t} \neq \bar{u}_t]\). The best expert cost is \(C^*(T) = \min_i C_i(T)\).
Regret
The regret of the algorithm is the difference \(C(T) - C^*(T)\). A good algorithm has regret growing slowly with \(T\) (e.g., logarithmically), meaning we eventually perform almost as well as the best expert.
Bad News: Lower Bounds
Deterministic Algorithms
A deterministic algorithm is doomed: an adversary who sees our prediction before choosing the truth can always set \(\bar{u}_t = 1 - u_t\), forcing \(C(T) = T\).
Randomised Algorithms (without experts)
Even if we randomise, without expert advice the best we can achieve is \(\mathbb{E}[C(T)] \geq T/2\). We are essentially guessing a fair coin.
Fact 56.3 (Factor 2 is necessary)
For deterministic algorithms with 2 experts, one always predicting 0 and the other always predicting 1, any deterministic prediction algorithm has:
\[C(T) \geq 2 \cdot C^*(T)\]The adversary sets \(\bar{u}_t = 1 - u_t\). One expert is always correct while the other is always wrong, so \(C^*(T) \leq T/2\) while \(C(T) = T\).
Consistent Expert Algorithm
Algorithm 22: Consistent Expert
Assumption: There exists a perfect expert with \(C^*(T) = 0\).
Initialise: \(S_1 = \{A_1, \ldots, A_n\}\) (all experts are "alive")
- At time \(t\), pick any expert \(A_i \in S_t\) and predict \(u_t = v_{i,t}\).
- Observe \(\bar{u}_t\). Remove from \(S_t\) all experts who were wrong: \(S_{t+1} = \{A_i \in S_t : v_{i,t} = \bar{u}_t\}\).
Theorem (Consistent Expert Bound)
If \(C^*(T) = 0\), the Consistent Expert algorithm makes at most \(n - 1\) mistakes:
\[C(T) \leq n - 1\]Potential function: \(\Phi_t = |S_t|\). Initially \(\Phi_1 = n\). The perfect expert is never eliminated, so \(\Phi_t \geq 1\) always. Each time we make a mistake, our chosen expert was wrong, so it (and possibly others) get removed: \(\Phi_{t+1} \leq \Phi_t - 1\). Since \(\Phi\) starts at \(n\) and cannot drop below 1, we make at most \(n - 1\) mistakes. \(\square\)
Halving Algorithm
Algorithm 23: Halving
Assumption: There exists a perfect expert with \(C^*(T) = 0\).
Initialise: \(S_1 = \{A_1, \ldots, A_n\}\)
- At time \(t\), take a majority vote among experts in \(S_t\): predict \(u_t\) as the value predicted by more than half of \(S_t\).
- Observe \(\bar{u}_t\). Eliminate all wrong experts: \(S_{t+1} = \{A_i \in S_t : v_{i,t} = \bar{u}_t\}\).
Theorem (Halving Bound)
If \(C^*(T) = 0\), the Halving algorithm makes at most \(\lfloor\log_2 n\rfloor\) mistakes:
\[C(T) \leq \lfloor\log_2 n\rfloor\]Potential function: \(\Phi_t = |S_t|\). Initially \(\Phi_1 = n\), and \(\Phi_t \geq 1\) always (the perfect expert survives). When we make a mistake, the majority was wrong, so more than half of \(S_t\) get eliminated. Therefore \(\Phi_{t+1} \leq \Phi_t / 2\). After \(k\) mistakes: \(\Phi \leq n/2^k\). Since \(\Phi \geq 1\): \(n/2^k \geq 1 \Rightarrow k \leq \log_2 n\). \(\square\)
Interactive: Halving Algorithm Survivor Set
Watch how the halving algorithm eliminates experts each round. Expert #7 (the hidden perfect expert) always matches the truth. Each mistake halves the survivor set.
\(|S_t|\) Over Time (halves on each mistake)
Basic Multiplicative Weights Update
Motivation
The Halving algorithm requires a perfect expert (\(C^* = 0\)). What if no expert is perfect? We need to be more forgiving: instead of eliminating wrong experts, we down-weight them.
Algorithm 24: Basic MWU
Initialise: \(w_{i,1} = 1\) for all \(i \in [n]\). Total weight \(W_1 = n\).
- At time \(t\), predict \(u_t\) by weighted majority: predict the value with total weight \(> W_t/2\).
- Observe \(\bar{u}_t\). For each expert \(A_i\) that was wrong (\(v_{i,t} \neq \bar{u}_t\)), set \(w_{i,t+1} = w_{i,t} / 2\). Otherwise \(w_{i,t+1} = w_{i,t}\).
- Update \(W_{t+1} = \sum_i w_{i,t+1}\).
Theorem (Basic MWU Bound)
The Basic MWU algorithm satisfies:
\[C(T) \leq 2.41\bigl(C^*(T) + \log_2 n\bigr)\]Potential function: \(\Phi_t = W_t = \sum_i w_{i,t}\).
Upper bound on \(\Phi\): Initially \(W_1 = n\). When we make a mistake, the weighted majority was wrong, so the wrong experts have total weight \(> W_t/2\). Their weights halve, reducing \(W_t\) by more than \(W_t/4\). So:
\[W_{t+1} \leq W_t - \frac{W_t}{4} = \frac{3}{4} W_t\]After \(C(T)\) mistakes: \(W_{T+1} \leq n \cdot (3/4)^{C(T)}\).
Lower bound on \(\Phi\): The best expert \(i^*\) has weight \(w_{i^*,T+1} = (1/2)^{C^*}\), and \(W_{T+1} \geq w_{i^*,T+1}\). So:
\[(1/2)^{C^*} \leq n \cdot (3/4)^{C(T)}\]Taking logarithms: \(-C^* \leq \log_2 n + C(T) \log_2(3/4)\), which gives:
\[C(T) \leq \frac{C^* + \log_2 n}{\log_2(4/3)} \leq 2.41(C^* + \log_2 n)\]\(\square\)
MWU with Parameter \(\beta\)
Algorithm 25: MWU(\(\beta\))
Parameter: \(\beta \in (0, 1)\)
Initialise: \(w_{i,1} = 1\) for all \(i\).
- Predict by weighted majority: \(u_t =\) value with total weight \(> W_t/2\).
- Penalise wrong experts: \(w_{i,t+1} = \beta \cdot w_{i,t}\) if \(v_{i,t} \neq \bar{u}_t\), else \(w_{i,t+1} = w_{i,t}\).
Theorem (MWU(\(\beta\)) Bound)
For any \(\beta \in (0, 1)\), the MWU(\(\beta\)) algorithm satisfies:
\[C(T) \leq \frac{C^* \cdot \log(1/\beta) + \log n}{\log\!\big(\frac{2}{1+\beta}\big)}\]Upper bound: When we make a mistake, the wrong side has weight \(> W_t/2\). Their weights get multiplied by \(\beta\). So:
\[W_{t+1} \leq \frac{1 + \beta}{2} W_t\]After \(C(T)\) mistakes: \(W_{T+1} \leq n \cdot \left(\frac{1+\beta}{2}\right)^{C(T)}\).
Lower bound: Best expert: \(w_{i^*} = \beta^{C^*}\), so \(W_{T+1} \geq \beta^{C^*}\). Combining:
\[\beta^{C^*} \leq n \cdot \left(\frac{1+\beta}{2}\right)^{C(T)}\]Taking logarithms and rearranging gives the bound. \(\square\)
Trade-off in \(\beta\)
\(\beta \to 0\) (aggressive penalty)
Additive term (\(\log n\)) gets smaller, but the multiplicative factor on \(C^*\) grows. Better when \(C^*\) is small.
\(\beta \to 1\) (gentle penalty)
Multiplicative factor on \(C^*\) approaches 1, but the additive term grows. Better when \(C^*\) is large.
Setting \(\beta = 1/2\) recovers the Basic MWU bound: \(C(T) \leq 2.41(C^* + \log_2 n)\).
Randomised MWU
Why Randomise?
Deterministic MWU has a factor of 2 overhead (Fact 56.3). By randomising our prediction, we can remove this factor entirely!
Algorithm 26: Randomised MWU(\(\beta\))
Parameter: \(\beta \in (0, 1)\)
Initialise: \(w_{i,1} = 1\) for all \(i\).
- At time \(t\), sample an expert \(A_j\) with probability \(w_{j,t} / W_t\) and predict \(u_t = v_{j,t}\).
- Penalise wrong experts: \(w_{i,t+1} = \beta \cdot w_{i,t}\) if \(v_{i,t} \neq \bar{u}_t\), else \(w_{i,t+1} = w_{i,t}\).
Theorem (Randomised MWU Bound)
The Randomised MWU(\(\beta\)) algorithm satisfies:
\[\mathbb{E}[C(T)] \leq \frac{C^* \cdot \ln(1/\beta) + \ln n}{1 - \beta}\]Key observation: At time \(t\), \(\Pr[\text{mistake}] = \Pr[v_{j,t} \neq \bar{u}_t] = F_t / W_t\) where \(F_t\) is the total weight of wrong experts.
The weight update gives \(W_{t+1} = W_t - (1-\beta)F_t\), so \(F_t = (W_t - W_{t+1})/(1-\beta)\).
Expected cost:
\[\mathbb{E}[C(T)] = \sum_{t=1}^{T} \frac{F_t}{W_t} = \frac{1}{1-\beta}\sum_{t=1}^{T} \frac{W_t - W_{t+1}}{W_t} \leq \frac{1}{1-\beta}\sum_{t=1}^{T} \ln\frac{W_t}{W_{t+1}} = \frac{\ln(W_1/W_{T+1})}{1-\beta}\](using \(1 - x \leq -\ln x\) for \(x = W_{t+1}/W_t\))
Since \(W_1 = n\) and \(W_{T+1} \geq \beta^{C^*}\):
\[\mathbb{E}[C(T)] \leq \frac{\ln n - C^* \ln\beta}{1 - \beta} = \frac{C^* \ln(1/\beta) + \ln n}{1 - \beta} \qquad \square\]Interactive: MWU Weight Evolution
Watch how expert weights change over time. Configure the number of experts, the penalty parameter \(\beta\), and observe weight dynamics against an adversarial sequence.
Expert Weights
Mistake History
Summary & Comparison
| Algorithm | Assumption | Bound | Type |
|---|---|---|---|
| Consistent Expert (Alg 22) | \(C^* = 0\) | \(C(T) \leq n - 1\) | Deterministic |
| Halving (Alg 23) | \(C^* = 0\) | \(C(T) \leq \log_2 n\) | Deterministic |
| Basic MWU (Alg 24) | None | \(C(T) \leq 2.41(C^* + \log_2 n)\) | Deterministic |
| MWU(\(\beta\)) (Alg 25) | None | \(\displaystyle\frac{C^*\log(1/\beta)+\log n}{\log(2/(1+\beta))}\) | Deterministic |
| Rand. MWU(\(\beta\)) (Alg 26) | None | \(\displaystyle\frac{C^*\ln(1/\beta)+\ln n}{1-\beta}\) | Randomised |
Key Takeaways
- Consistent Expert is the simplest: eliminate wrong experts. Bound of \(n-1\) is linear.
- Halving uses majority vote to cut the survivor set in half each mistake, achieving \(O(\log n)\).
- MWU generalises to \(C^* > 0\) by down-weighting instead of eliminating. The potential argument is the core technique.
- Tuning \(\beta\) trades off between the multiplicative factor on \(C^*\) and the additive \(\log n\) term.
- Randomisation removes the factor of 2, giving a strictly better bound in expectation.
Tutorial Problems
Work through these problems to solidify your understanding of the expert advice framework.
Problem 1 Warm-up
Plot the MWU(\(\beta\)) bound \(\frac{C^*\log(1/\beta)+\log n}{\log(2/(1+\beta))}\) as a function of \(\beta\) for \(n = 100\) and \(C^* \in \{0, 10, 50, 100\}\). What value of \(\beta\) minimises the bound for each \(C^*\)?
For \(C^* = 0\): the bound is \(\frac{\log n}{\log(2/(1+\beta))}\), which is minimised as \(\beta \to 0\) (giving \(\log_2 n \approx 6.64\)). For large \(C^*\), the bound is dominated by the \(C^* \log(1/\beta)\) term. Setting \(\beta\) close to 1 makes the multiplicative factor \(\frac{\log(1/\beta)}{\log(2/(1+\beta))} \to 1\), but the additive term diverges. The optimal \(\beta\) depends on the ratio \(C^*/\log n\). In general, \(\beta \approx 1 - \sqrt{\log n / C^*}\) is near-optimal for large \(C^*\). \(\square\)
Problem 2 Warm-up
Given \(n\) experts and a known upper bound \(C^*\), determine the optimal setting of \(\beta\) for the deterministic MWU(\(\beta\)) algorithm. Show that with the right choice of \(\beta\), the bound becomes \(C^* + O(\sqrt{C^* \log n})\).
The randomised bound is \(\frac{C^*\ln(1/\beta)+\ln n}{1-\beta}\). Setting \(\beta = 1 - \varepsilon\) with small \(\varepsilon\): \(\ln(1/\beta) = -\ln(1-\varepsilon) \approx \varepsilon + \varepsilon^2/2 \approx \varepsilon\). So the bound is approximately \(\frac{C^*\varepsilon + \ln n}{\varepsilon} = C^* + \frac{\ln n}{\varepsilon}\). To minimise, set \(\varepsilon = \sqrt{\ln n / C^*}\), giving \(C^* + 2\sqrt{C^* \ln n}\). For the deterministic case, a similar analysis with \(\beta = 1-\varepsilon\) gives \(2C^* + O(\sqrt{C^* \log n})\). \(\square\)
Problem 3 Problem Solving ⭐
Prove Fact 56.3: with 2 experts, one always predicting 0 and the other always predicting 1, any deterministic algorithm has \(C(T) \geq 2 \cdot C^*(T)\).
The adversary sets \(\bar{u}_t = 1 - u_t\) (always the opposite of our prediction). Then \(C(T) = T\). At each step, exactly one of the two experts is correct (the one who predicted \(\bar{u}_t\)). So expert 1 makes \(T - C_1(T)\) correct predictions and \(C_1(T)\) mistakes, while expert 2 makes \(C_2(T) = T - C_1(T)\) mistakes. Since \(C_1(T) + C_2(T) = T\), the better expert has \(C^* = \min(C_1, C_2) \leq T/2\). Therefore \(C(T) = T \geq 2 \cdot T/2 \geq 2 \cdot C^*\). \(\square\)
Problem 4 Advanced ⭐⭐
Prove a modified MWU bound: by setting \(\beta = 1 - \varepsilon\) with \(\varepsilon = \sqrt{\log n / C^*}\), show that \(C(T) \leq 2C^* + O(\sqrt{C^* \log n} + \log n)\).
Set \(\beta = 1 - \varepsilon\) with \(\varepsilon = \sqrt{\log n / C^*}\). In the deterministic MWU(\(\beta\)) bound:
\[C(T) \leq \frac{C^* \log(1/\beta) + \log n}{\log(2/(1+\beta))}\]For small \(\varepsilon\): \(\log(1/\beta) = -\log(1-\varepsilon) \approx \varepsilon/\ln 2\), and \(\log(2/(1+\beta)) = \log(2/(2-\varepsilon)) \approx \varepsilon/(2\ln 2)\). So:
\[C(T) \lesssim \frac{C^* \cdot \varepsilon/\ln 2 + \log n}{\varepsilon/(2\ln 2)} = 2C^* + \frac{2\log n \cdot \ln 2}{\varepsilon}\]Substituting \(\varepsilon = \sqrt{\log n / C^*}\): \(\frac{2\log n \cdot \ln 2}{\varepsilon} = 2\ln 2 \cdot \sqrt{C^* \log n}\). Therefore:
\[C(T) \leq 2C^* + O(\sqrt{C^* \log n})\]Adding the lower-order terms gives the full bound \(2C^* + O(\sqrt{C^* \log n} + \log n)\). \(\square\)
Problem 5 Advanced ⭐⭐
Chunked MWU: Consider a modified MWU where at time \(t\), we only penalise expert \(A_i\) (multiply by \(\beta\)) if \(w_{i,t} \geq W_t / (3n)\) (weight is at least \(1/3\) of the average). For a time interval \([t_1, t_2]\), show that \(C(t_1, t_2) \leq O(C^*(t_1, t_2) + \log n)\).
When we make a mistake at time \(t\), the wrong side has total weight \(> W_t/2\). Among the wrong experts with \(w_{i,t} \geq W_t/(3n)\), their total weight is significant. After penalising them by \(\beta\):
\[W_{t+1} \leq \frac{5 + \beta}{6} W_t\]For the lower bound, any expert that is alive at time \(t_1\) has weight at least:
\[w_{i,t_1} \geq \frac{\beta \cdot W_{t_1}}{3n}\]Combining the upper and lower bounds on the total weight, taking logarithms, and rearranging gives \(C(t_1, t_2) = O(C^*(t_1, t_2) + \log n)\). \(\square\)
Problem 6 Advanced ⭐⭐
Known mistake bounds: Suppose we know that expert \(k\) makes at most \(k\) mistakes. We assign initial weight \(w_{k,1} = \beta^k\) to expert \(k\). Show that the total weight satisfies \(W \geq \beta(1 - \beta^n)/(1 - \beta)\), and derive a tighter bound.
With initial weights \(w_{k,1} = \beta^k\), the total initial weight is:
\[W_1 = \sum_{k=1}^{n} \beta^k = \frac{\beta(1 - \beta^n)}{1 - \beta}\]After \(T\) rounds, expert \(k\) (making at most \(k\) mistakes) has weight \(w_{k,T+1} = \beta^k \cdot \beta^{C_k} \geq \beta^k \cdot \beta^k = \beta^{2k}\). Therefore:
\[W_{T+1} \geq \beta^{2k} \text{ for any } k\]Using the same potential argument: \(\beta^{2k} \leq W_1 \cdot \left(\frac{1+\beta}{2}\right)^{C(T)}\) for the deterministic case. Taking logarithms:
\[C(T) \leq \frac{2k\log(1/\beta) + \log W_1}{\log(2/(1+\beta))}\]This gives a bound that depends on the specific expert \(k\) we are competing against, potentially yielding much tighter bounds when \(k\) is small. \(\square\)
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).