Thompson Sampling

What is Thompson Sampling?

Thompson sampling is a heuristic learning algorithm that chooses an action which maximizes the expected reward for a randomly assigned belief. The problem this sampling addresses is also called the exploration-exploitation dilemma.

In these decision problems, actions must be performed sequentially and in a way to balance for two competing goals:
  1. Consuming resources and time to exploit what is already known to maximize immediate performance.
  2. Investing resources and time to accumulate new information that might improve future performance.
Algebraically, this is expressed as playing the action:

To maximize the probability of achieving the maximum reward from either course of action, like so:



When is Thompson Sampling used?

This sampling approach is an efficient solution for a wide range of problems with many variables, where the action taken on one affects the outcomes of other potential actions. Some of the most common situations include: