ACM Comm 2016 11 Sex as an Algorithm (Notes) (The Experts Problem)

ACM Comm 2016 11 Sex as an Algorithm (Notes) (The Experts Problem)

Original material is in Sex as an Algorithm's appendix. The entire sidebar is reproduced here for clarity.

The Experts Problem

Imagine that every day over five years you receive financial advice from ten experts. If you follow the advice of any one of them, that day you will realize a gain somewhere between −1 and +1 (you fill in the units). You have no idea how good each of them is, and yet each day you must choose one expert. What is a good algorithm for choosing an expert, day after day, so you will end up doing well?

This is not a well defined problem, because in our objective “to do well” we have not specified “compared to what?” Let us set a very ambitious goal. You want to choose experts in such a way that, five years later, you can look back and say: “In retrospect, Expert 4 was the best, because if I had followed her advice throughout I would be better off than if I had followed the advice of any other single expert. But I did not know this in the beginning. Still, I managed to do almost as well as if I had followed exclusively the advice of Expert 4.” In other words, we want to find an algorithm which picks the best expert — give or take something very small — from the start and in hindsight! At first sight, this might seem impossible. Note that we are not assuming anything about any probabilistic distribution of the experts’ performance. In fact, it is instructive to think that the outcomes of the experts’ advice each day are chosen by an adversary who wants you to fail in your goal.

Very surprisingly, this feat is made possible by a very simple algorithm called multiplicative weight updates (MWU). It has a long history: It was discovered in the 1950s by economists, then in the 1980s in the mathematics of finance, then in the 1990s by researchers in AI (where it has been called first “Winnow,”“Hedge,” and finally “Boosting”), and finally by theoreticians as MWU. The algorithm is the following:

Fix a very small number \( \epsilon > 0 \) (see below for appropriate value)
Give each expert \(i\) (out of \(n\)) the same probability \(p_{i}= \frac{1}{n}\)
At each day \(t=1,...,T\) do the following:

Pick an expert at random, where you choose \(i\) with probability \(p_{i}\)

Let \(g_{i}\) be the gain you would have obtained if you had chosen expert \(j\), for \(j=1,...,n\)

For \(j=1,...,n\), update the probabilities as follows: \(p_{j} \leftarrow p_{j}(1+ \epsilon g_{j})\),

and divide all \(p_{j}\)'s by \(\sum_{i=1}^{n}p_{j}\) (to keep them adding to one).

That is, each day you boost (or decrease) the probability of each expert by a small amount

proportional to its gain (or loss). The theorem says that, if you choose:

$$ \epsilon = \sqrt{ \frac{\ln n}{T}} $$

your total gain in the end of \(T\) days will be, in expectation, within \(\sqrt{T \ln n}\) of the optimum. For large \(T\) this will be insignificant, compared to the range \([-1,+1]\). In our example with \(n=10\) and \(T=1825\), on an average day you are guaranteed to be only about 0.05 units of gain below the performance of the best expert.

Notes

You can't get to the ideal, but you can get real close. Sometimes close enough so the difference does not matter.

Internal Links

Parent Article: ACM Comm 2016 11 Sex as an Algorithm (Notes)