Reasonable Effectiveness of the Multiplicative Weights Update Algorithm (2017)

Having studied this myself a couple of years ago, I believe an intuitive way to understand its power is that MWU approximately optimizes an l_\infty-norm by approximating it with a sum of exponentials (the potential function from the proof). The analogy isn't perfect, but it helped me reason about it.

There is also a tentative link to tropical geometry because of this. When you have a problem that by its nature is "tropical" (using addition and taking maximums), the MWU method may be useful via translating into the non-tropical world of multiplication and addition, respectively.

The idea is that optimizing a weighted sum of squared distances is trivial: the optimum is just the weighted average. Thus you set up the weights, iteratively, to the inverse distances, so that you end up minimizing the actual sum of distances.

[0] Iteratively Re-weighted Least Squares

>In the more general event that you have rewards for all objects (if not, the reward-producing function can output zero), you would perform this weight update on all objects

with the following justification of its properties then it kind of seems like the guarantee that it gets close to the maximum reward only holds if:

1. You know the rewards for all options and update the weights accordingly

or

2. You consider the rewards for all options not taken 0 (in which case you trivially got the maximum reward possible).

This kind of seems to limit its applicability somewhat, unless I'm missing something?

- The algorithm not amenable to this problem

- You have a buggy implementation

Which is true? This is one of the issues that genetic algorithms run into as a similar powerful and chronically underutilised tool.

Being nondeterministic isn't the end of the world, but the payoffs have to be much higher than using simple deterministic methods.