liveBook · Manning

Thompson sampling

As explained in Applied Reinforcement Learning

A Bayesian bandit action-selection algorithm that samples each action's expected reward from its posterior distribution and selects the action with the best sample.

Thompson sampling helps choose between actions when their rewards are uncertain. For an ad campaign, it balances showing ads that appear effective with trying others that might perform better, aiming to increase reward over repeated impressions. section 5.2 section 5.3

Instead of keeping only one estimated click-through rate for each ad, the algorithm maintains a probability distribution over plausible rates. On each decision, it samples a rate from each ad’s distribution and selects the ad with the highest sample. Promising ads tend to win, while uncertain ads still have a chance to be tried. section 5.3

For binary click rewards, a simple implementation uses a Beta distribution for each ad:

  • Start each ad with Beta(1, 1), represented by parameters alpha and beta both set to 1. section 5.3
  • Sample a click-through rate from each ad’s Beta distribution and show the ad with the largest sample. section 5.3
  • After a click, increase the chosen ad’s alpha by 1; after no click, increase its beta by 1. Repeat with the updated beliefs. section 5.3
Listing 5.6 The Thompson Sampling Agent
class ThompsonSamplingAgent:
    def __init__(self, num_ads):
        self.num_ads = num_ads
        self.alphas = [1] * num_ads #A
        self.betas = [1] * num_ads #A
 
    def choose_action(self):
        sampled_ctrs = [np.random.beta(self.alphas[i],
        [CA]self.betas[i]) for i in range(self.num_ads)] #B
        return np.argmax(sampled_ctrs) #C
 
    def update(self, chosen_ad_index, reward):
        if reward == 1:
            self.alphas[chosen_ad_index] += 1 #D
        else:
            self.betas[chosen_ad_index] += 1 #E

The agent listing puts initialization, sampling, selection, and click-based updates together. section 5.3

Comparing ad policies

In a simulated campaign, clicks and non-clicks provide rewards for comparing Thompson sampling with alternatives such as epsilon-greedy and upper confidence bound. Cumulative regret measures missed reward relative to the best action: too much exploration wastes impressions, while exploiting too early can favor the wrong ad. In a real campaign, the true optimal reward is unknown, so actual numerical regret cannot be calculated; business KPIs can serve as proxies. section 5.3 section 5.4 section 5.7

How Applied Reinforcement Learning covers it

How deep it goes
Works through Beta beliefs, sampled action selection, and click-based updates in an agent implementation.
Examples
Uses a simulated ad campaign with binary clicks to compare Thompson sampling against other bandit policies.
What it assumes
Introduces Bernoulli outcomes and Beta beliefs through clicks and non-clicks.
What you can do after
Build a Thompson sampling agent for binary ad-click rewards and evaluate its simulated regret.
How it connects
Connects Bayesian inference and multi-armed bandits with exploration, exploitation, and cumulative regret.

Also explained in

Compare how 5 books explain Thompson sampling →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.