Recommendations with Thompson Sampling
Jun 05, 2014/
This is the second in a series of three blog posts on bandits for recommendation systems.
If you read the last blog post, you should now have a good idea of the challenges in building a good algorithm for dishing out recommendations in the bandit setting. The most important challenge is to balance exploitation with exploration. That is, we have two somewhat conflicting goals: (a) quickly find the best arm to pull and (b) pull the best arm as often as possible. What I dubbed the naive algorithm in the preceding blog post fulfilled these two goals in a direct way: explore for a while, and then exploit forever. It was an OK approach, but we found that more sophisticated approaches, like the UCB family of bandit algorithms, had significantly better performance and no parameters to tune.
In this post, we'll introduce another technique: Thompson sampling (also known as probability matching). This has been well covered elsewhere, but mostly for the binary reward case (zeros and ones). I'll also go over Thompson in the log-normal reward case, and offer some approximations that can work in for any reward distribution.
Before I define Thompson sampling, let's build up some intuition. If we have an infinite amount of pulls, then we know exactly what the expected rewards are, and there is no reason to ever explore. When we have a finite number of pulls, then we have to explore and the reason is that we are uncertain of what is the best arm. The right machinery to quantify uncertainty is the probability distribution. The UCB algorithms are implicitly using a probability distribution, but only one number from it: the upper confidence bound. In Bayesian thinking, we want to use the entire probability distribution. In the preceding post I defined , the probability distribution from which rewards are drawn. That's what controls the bandit. It would be great if we could estimate this entire distribution, but we don't need to. Why? Because all we care about is its mean . What we will do is encode our uncertainty of in the probability distribution , and then use that probability distribution to decide when to explore and when to exploit.
You may be confused by now because there are two related probability distributions floating around, so let's review:
- - the probability distribution that bandit uses to generate rewards when it is pulled.
- - the probability distribution of where we think the mean of after observing some data.
With Thompson sampling you keep around a probability distribution that encodes your belief about where the expected reward is for arm . For the simple coin-flip case, we can use the convenient Beta-Bernoulli model, and the distribution at round after seeing successes and failures for arm is simply:
where the added 1's are convenient priors.
So now we have a distribution that encodes our uncertainty of where the true expected reward is. What's the actual algorithm? Here it is, in all its simple glory:
- Draw a random sample from for each arm .
- Pull the arm which has the largest drawn sample.
That's it! It turns out that this approach is a very natural way to balance exploration and exploitation. Here is the same simulation from last time, comparing the algorithms from the preceding blog post to Thompson Sampling:
Continuous Variables and the Normal Approximation
The Bernoulli case is well known and well understood. But what happens when you want to maximize, say, revenue instead of click-through rate? To find out, I coded up a log-normal bandit where each arm pays out strictly positive rewards drawn from a log-normal distribution (the code is messy, so I won't be posting it).
For Thompson sampling, I used a full posterior with priors over the log-normal parameters and as described here (note that these are not the mean and standard deviation of the log-normal; read the linked blog post for a lot more info).
Finding that the full posterior was unwieldy and slow, I also implemented a normal approximation to exact Thompson sampling is (using Central Limit Theorem arguments):
where and , are the sample mean and sample variance, respectively, of the rewards observed from arm at round , and is the number of times arm has been pulled at round .
Two UCBs were compared against. For a model-specific UCB, I used the modified Cox method of computing confidence bounds for the log-normal distribution from here. The UCB normal approximation is identical to that in the previous simulation.
For all algorithms, I used the log of the observed rewards to compute sufficient statistics. The results:
- Epsilon-Greedy is still the worst performer.
- The normal approximations are slightly worse than their hand-designed counterparts - green is worse than orange and gray is worse than purple.
- UCB is doing better than Thompson sampling over this horizon, but Thompson sampling is maybe poised to do better in the long run.
The Trouble with UCB
In the above experiments UCB beat out Thompson sampling. It sounds like a great algorithm and performs well in simulations, but it has a key weakness when you actually get down to productionizing your bandit algorithm. Let's say that you aren't Google and you have limited computational resources, which means that you can only update your observed data in batch every 2 hours. For the delayed batch case, UCB will pull the same arm every time for those 2 hours because it is deterministic in the absence of immediate updates. While Thompson sampling relies on random samples, which will be different every time even if the distributions aren't updated for a while, UCB needs the distributions to be updated every single round to work properly.
Given that the simulated performance differences between Thompson sampling and UCB are small, I heartily recommend Thompson sampling over UCB; it will work in a larger variety of practical cases.
Avoiding Trouble with Thompson Sampling
RichRelevance sees gobbles of data. This is usually great, but for Thompson sampling this may mean a subtle pitfall. To understand this point, first note that the variance of a Beta distribution with parameters and is:
For our recommender system, is the number of successes (clicks) and is the number of failures (non-clicks). As the amount of total data goes up, the variance shrinks, and quickly. After a while, the posteriors will be so narrow, that exploration will effectively cease. This may sound good - after all, didn't we learn what the best lever to pull is? In practice, we're dealing with a moving target so it is a good idea to put an upper bound on , so that exploration can continue indefinitely. For details, see Section 7.2.3 here.
Analogously, if you're optimizing for revenue instead of click-through rate and using a Normal approximation, you can compute sample means and sample variances in an incremental fashion, using decay as per the last page here. This will ensure that older samples have less influence than newer ones and allow you to track changing means and variances.
Coming up next: contextual bandits!