Thompson Sampling 2D: Belief-Space Bandit Charts |…

What is Thompson Sampling?

Thompson Sampling is a Bayesian approach to the multi-armed bandit problem, where an agent must choose among several options (or 'arms') with unknown rewards. The algorithm selects actions based on sampling from the posterior distribution of each arm's reward probability. This method allows for a balance between exploration and exploitation by probabilistically favoring arms that are either known to have high rewards or whose true reward is uncertain.

The key idea behind Thompson Sampling is that it leverages Bayesian inference, updating beliefs about the underlying parameters (win rates) based on observed data, and then uses these updated beliefs to guide future decisions.

How Does It Work?

At each step, Thompson Sampling selects an arm by sampling from its posterior distribution. If this sample is above a threshold that reflects the current best estimate of the win rate for other arms, the sampled arm is chosen; otherwise, another arm with higher estimated win rates is selected. This process ensures that the algorithm explores less promising arms while exploiting those that have shown promise.

The Beta(α,β) distribution is commonly used as a conjugate prior for the binomial likelihood of rewards, allowing for straightforward updates to beliefs about each arm's reward probability based on observed outcomes.

live demo · related simulation● LIVE

Why Does It Matter?

Thompson Sampling has been shown to achieve near-optimal performance in terms of cumulative regret compared to other algorithms, making it a popular choice in applications such as online advertising, recommendation systems, and clinical trials. Its ability to balance exploration and exploitation effectively is crucial for optimizing long-term rewards.

Moreover, Thompson Sampling's probabilistic nature allows for more nuanced decision-making, providing insights into the uncertainty associated with each action and enabling better strategic planning.

Real-World Applications

Thompson Sampling has found applications in various fields. For instance, it is used to optimize online advertising by dynamically choosing which ads to show based on historical performance data. In clinical trials, it helps allocate patients to different treatment arms while balancing the need for exploration of new treatments against the exploitation of known effective ones.

In recommendation systems, Thompson Sampling can be employed to personalize content or products based on user feedback, ensuring a balance between recommending popular items and exploring less-known but potentially more valuable options.

Frequently asked questions

How does Thompson Sampling differ from other bandit algorithms?

Thompson Sampling uses Bayesian inference to model the uncertainty in reward probabilities, whereas other methods like epsilon-greedy or UCB (Upper Confidence Bound) rely on fixed exploration strategies. This makes Thompson Sampling more adaptive and often results in better performance over time.

Can Thompson Sampling be used for problems with more than two arms?

Yes, Thompson Sampling can handle multi-armed bandit problems with any number of arms. The algorithm simply samples from the posterior distribution of each arm's reward probability and selects the one with the highest sample value.

What is cumulative regret in the context of Thompson Sampling?

Cumulative regret measures the total difference between the rewards obtained by following the chosen strategy and the optimal strategy that always chooses the best arm. Minimizing cumulative regret is a key objective in bandit algorithms, including Thompson Sampling.

How does Thompson Sampling handle uncertainty in reward probabilities?

Thompson Sampling handles uncertainty by sampling from the posterior distribution of each arm's reward probability after updating it based on observed outcomes. This probabilistic approach allows for a nuanced balance between exploration and exploitation, making decisions that account for both known and unknown information.

Try it live

Everything above runs in your browser — open Thompson Sampling 2D: Belief-Space Bandit Charts and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Thompson Sampling 2D: Belief-Space Bandit Charts simulation