Lecture 24: Multiplicative Weights

18.409 An Algorithmist’s Toolkit Lecture 24 Lecturer: Jonathan Kelner Multiplicative Weights In this lecture we will introduce Multiplicative Weights, a simple technique with many applications. We start with an example. Example Suppose Mr. X wants to bet on football games but does not know much about football himself. Before each game, X can check the predictions of n experts. Is there an algorithm that allows Mr. X to perform well in the long run? Two potential ideas are: (1) For each game, bet according to what the majority of experts predict (2) Wait a few games to see which of the experts get it right most of the time and then follow their advice These strategies work well in some cases but not in others: (1) fails when only a few experts make good predictions, and (2) fails when there is an expert that performs well for the first few games and then never makes a correct prediction again. Instead, we will consider a combination of the two approaches: for each game, we will consider the opinion of all experts, but each expert’s opinion will be weighted according to his past performance. More precisely, let wit denote the weight of expert i after t games, and consider the following algorithm: 1. Set wi0 = 1 for i = 1, ..., n 2. Make � a prediction for game t based on a weighted majority of experts where expert i gets weight wit−1 / j wjt−1 3. After game t update the weights as follows: if expert i’s prediction for game t was wrong then set wit = (1 − �)wit−1 ; otherwise set wit = wit−1 For this algorithm, we have the following: Theorem Let mti denote the number of mistakes that expert i makes in the first t games and mt denote the number of mistakes that Mr. X makes in the first t games. Then for all i and t, 2log(n) + 2(1 + �)mti � and in particular, this holds for the i that minimizes mti . mt ≤ � Proof Define Φk = i wik . If Mr. X makes a mistake at game k, then a weighted majority of the experts must have made a wrong prediction for game k. The weights of all these experts drop by a factor of (1 − �) and so we have Φk ≤ (1 − �/2)Φk−1 . Then over the first t games we have � t � t Φt ≤ (1 − )m Φ0 = n(1 − )m 2 2 t On the other hand we have wit = (1 − �)mi and so 24-1 t Φt ≥ wit = (1 − �)mi Therefore, t � t n(1 − )m ≥ (1 − �)mi 2 Rearranging this inequality gives mt ≤ log(n) log(1 − �) + mti −log(1 − �/2) log(1 − �/2) This bound is slightly stronger than the one in the statement of the theorem. Using the inequalities �/2 ≤ −log(1 − �/2) and � + �2 ≥ −log(1 − �) converts it to the required form and completes the proof. Next, we will modify our algorithm to get rid of the factor of 2 on the right hand side of the bound above. Consider the following: 1. Set wi0 = 1 for i = 1, ..., n 2. To make a prediction for � game t, do the following: for i = 1, ...n, follow expert i’s prediction with probability pti = wit−1 / j wjt−1 3. After game t update the weights as follows: if expert i’s prediction for game t was wrong then set wit = (1 − �)wit−1 else set wit = wit−1 For this algorithm, we have the following: Theorem Let mti denote the number of mistakes that expert i makes in the first t games and let mt denote the random variable equal to the number of mistakes that Mr. X makes in the first t games. Then for � < 1/2 and for all i and t, log (n) + (1 + �)mti � and in particular, this holds for the i that minimizes mti . E(mt ) ≤ The proof of this Theorem is similar to before and we will omit it. Instead, we will introduce our most general version of the multiplicative weights algorithm. In the example above, we had only two possibilities for the relation between event outcomes and expert predictions: the outcome of game t either matched expert i’s prediction or it did not. Our measure of performance for individual experts and for the algorithm as a whole was simply counting wrong predictions. We want to generalize the algorithm to allow for an arbitrary set P of possible outcomes to events. In this setting, we will measure the performance of the algorithm as follows: we will say that at each step, following expert i’s prediction when the true outcome is j incurs a penalty of M (i, j). More precisely, we have the following: 0. The input of the algorithm consists of: a set P of possible outcomes to events. For i = 1, ...n and for j ∈ P a number M (i, j) from the interval [−l, ρ]. We will refer to ρ as the width; we will also have the restriction l < ρ. 1. Set wi0 = 1 for i = 1, ..., n 2. To make a prediction for � event t, do the following: for i = 1, ...n, follow expert i’s prediction with probability pti = wit−1 / j wjt−1 24-2 3. Let j t denote the outcome of event t. Update the weights as follows: t wit = { wit−1 (1 − �)M (i,j )/ρ t wit−1 (1 + �)−M (i,j )/ρ if M (i, j t ) ≥ 0 if M (i, j t ) < 0 A similar analysis to before gives: Theorem Let Dt denote the probability distribution {pt1 , . . . , ptn } with which we pick experts to make a prediction for event t. Let M (Dt , j t ) denote the expected value of our penalty when following the distribution Dt for event t and when the actual outcome is j t . Then for � ≤ 1/2 and for all T and i, T � t=1 M (Dt , j t ) ≤ ρlog(n) + (1 + �) � � M (i, j t ) + (1 − �) t:M (i,j t )≥0 � M (i, j t ) t:M (i,j t )<0 Corollary For any δ, for � ≤ min(1/2, δ/4ρ), for T = 16ρ2 log(n)/δ 2 rounds and for all i, the average penalty we get per round obeys: �T �T M (Dt , j t ) M (i, j t ) ≤ δ + t=1 T T and in particular our average penalty per round is at most δ bigger than the average penalty of the best expert. t=1 Applications of Multiplicative Weights Our first application of the Multiplicative Weights algorithm will be to zero-sum games. In a zero-sum game, we have a row player, R, and a column player, C. If R plays strategy i and C plays strategy j, then R pays C the amount M (i, j). Players can also play mixed strategies, i.e. probability distributions over the sets of pure strategies. We will extend our payoff notation so that M (D, P ) denotes the expected amount that R pays C when R plays the mixed strategy D and C plays the mixed strategy R. Recall that von Neumann’s Minimax Theorem states that minD maxj M (D, j) = maxP mini M (i, P ) We will denote the above quantity by λ; it is known as the value of the game. We are now ready to state the zero-sum game problem: given the sets of strategies for R and C and the payoffs M (i, j), estimate the value of the game λ. Our approach will be to associate elements of the current problem to appropriately chosen elements of the Multiplicative Weights algorithm, then directly apply what we already know about Multiplicative Weights to conclude that we do indeed get a good approximation to λ in a reasonable amount of time. The details of the argument will be presented next lecture. 24-3