Thompson Sampling: A Bayesian Approach to Multi-Armed…

What is Thompson Sampling?

Thompson Sampling is a Bayesian approach to the multi-armed bandit problem. It aims to balance exploration (trying different options) and exploitation (choosing the best option based on current knowledge). The algorithm works by maintaining a posterior distribution over the reward probabilities of each arm, typically using a Beta distribution for binary outcomes.

At each step, Thompson Sampling selects an arm by sampling from its posterior distribution. This means that arms with higher probability estimates are more likely to be selected, but there's still a chance to explore less promising options.

How Does It Work?

Initially, the algorithm assumes a prior belief about the reward probabilities of each arm. As it receives feedback (rewards or lack thereof), it updates these beliefs using Bayesian updating rules. For binary outcomes, this often means updating a Beta distribution with parameters that reflect the number of successes and failures for each arm.

The key insight is that by sampling from the updated posterior distributions, Thompson Sampling naturally balances exploration and exploitation without needing to explicitly explore or exploit.

live demo · related simulation● LIVE

Why Does It Matter?

Thompson Sampling has gained significant attention in machine learning due to its simplicity and effectiveness. It often outperforms other algorithms like epsilon-greedy or UCB (Upper Confidence Bound) in terms of cumulative reward, especially when the number of arms is large.

In practical applications such as online advertising, recommendation systems, and clinical trials, Thompson Sampling can lead to better long-term performance by dynamically adapting to new information.

Real-World Applications

Thompson Sampling has been applied in various domains. For example, in online advertising, it helps decide which ad to show based on historical click-through rates while continuously learning from new data.

In clinical trials, it can optimize the allocation of treatments by balancing between trying different therapies and sticking with the most promising ones.

Frequently asked questions

How does Thompson Sampling balance exploration and exploitation?

Thompson Sampling balances exploration and exploitation by sampling from the posterior distribution of each arm's reward probability. This allows it to choose arms based on their current estimated probabilities while still occasionally exploring less promising options.

What is a multi-armed bandit problem?

A multi-armed bandit problem involves choosing between multiple options (or 'arms') with the goal of maximizing rewards. Each arm has an unknown reward distribution, and the challenge lies in balancing exploration to learn about all arms versus exploitation to choose the best known option.

Why is Thompson Sampling considered Bayesian?

Thompson Sampling is considered Bayesian because it uses a Bayesian approach to update beliefs about the reward probabilities of each arm based on observed data. It maintains a posterior distribution over these probabilities and samples from them to make decisions, which aligns with Bayesian inference.

Can Thompson Sampling be used for non-binary outcomes?

Yes, while Thompson Sampling is commonly described in the context of binary outcomes using Beta distributions, it can be extended to handle multi-armed bandit problems with continuous or categorical rewards by using appropriate posterior distributions such as Dirichlet for categorical outcomes.

Try it live

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

▶ Open Thompson Sampling: Bayesian Multi-Armed Bandit simulation

Thompson Sampling: A Bayesian Approach to Multi-Armed Bandits