Thompson sampling

As explained in Bayesian Optimization in Action

Thompson sampling is a Bayesian decision policy that samples a plausible model or parameter value from a posterior distribution and selects the action that is optimal under that sample.

Thompson sampling (TS) is a Bayesian policy for choosing the next evaluation in optimization under uncertainty. Rather than using a single optimistic estimate, it maintains a probabilistic belief about an unknown quantity, draws one plausible realization, and acts as though that realization were true. The resulting randomness naturally visits both promising regions and uncertain regions of a search space. section 5.3 section 5.3.1 section 5.5

A sampled weather outcome

To decide whether to bring an umbrella when sunny weather has probability 66%, TS can flip a coin biased two-thirds toward sunny. Heads is treated as a sunny day, so no umbrella is chosen; tails is treated as rain, so an umbrella is chosen. The sample is not a forecast bound—it is a temporary stand-in for the unknown outcome that drives one decision. section 5.3.1 section 5.3.1

Figure 5.12 Samples drawn from a GP and data points that maximize the corresponding samples. Whichever sample is drawn, TS selects the data point that maximizes that sample as the next point at which to evaluate the objective function.

Each draw from a Gaussian-process posterior represents a plausible objective function. TS selects the input that maximizes the particular function draw, so different draws can recommend different next evaluations. section 5.3.1

For Bayesian optimization, fit a GP model to observed objective values, sample a possible objective from its posterior, and evaluate the point where that sample is largest. High predicted values can win because they look good in a draw; uncertain areas can also win because some draws assign them high values. This differs from Upper Confidence Bound, which chooses through an explicitly optimistic estimate and a user-set trade-off parameter. section 5.3.1 section 5.5

A practical finite-candidate implementation replaces an impossible sample of an entire GP function with these steps:

• Generate many candidate points across the search space, commonly with a Sobol sequence that aims to cover a region evenly. section 5.3.2
• Draw from the multivariate normal distribution of GP predictions at those candidates. section 5.3.2
• Choose the candidate with the highest sampled value, evaluate the objective there, then add that observation and refit the loop. section 5.3.2

Figure 5.13 Flowchart of the implementation of TS in BoTorch. We use a Sobol sequence to populate the search space, draw a sample from the GP on the sequence, and choose the point in the sequence that maximizes the sample to evaluate the objective function at.

The flowchart makes the finite approximation explicit: evenly populate the space, sample GP predictions over those points, and query the sampled maximizer. section 5.3.2

In PyTorch and BoTorch, a SobolEngine can generate candidates and MaxPosteriorSampling can select a sampled maximizer without optimizing a conventional acquisition score. The policy may explore at first and then increasingly focus on the global optimum. For a batch, draw multiple GP samples and collect one maximizer per draw until the batch reaches the required size. section 5.3.2 section 7.3

Batch hyperparameter tuning

When several evaluations can run in parallel, set the number of TS samples to the batch size. Each posterior draw yields a potentially different maximizer, assembling a batch of candidate hyperparameter settings to evaluate together. section 7.3

How Bayesian Optimization in Action covers it

How deep it goes

Explains posterior-sampling intuition and a finite Sobol-candidate GP implementation, while deferring full-function sampling as computationally impossible.

Examples

Uses a biased weather coin flip, GP function draws, one-dimensional optimization progress, and batch hyperparameter tuning.

What it assumes

Uses Gaussian-process beliefs and Bayesian-optimization loops while teaching the sampling decision rule from a weather example.

What you can do after

Apply it via BoTorch to select sequential or batch Bayesian-optimization queries from GP posterior samples.

How it connects

Connects Thompson sampling to Bayesian optimization, multi-armed bandits, Gaussian processes, Sobol sequences, and Upper Confidence Bound.

liveBookmanning.com

Read Bayesian Optimization in Action on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Experimentation for EngineersThompson sampling is a Bayesian bandit algorithm that samples each alternative's expected reward from its posterior distribution and selects an alternative according to those samples.

Compare how 2 books explain Thompson sampling →

Related concepts

• MaxPosteriorSamplingimplemented by · MaxPosteriorSampling is a BoTorch sampler that draws posterior samples at candidate points and selects candidates maximizing those samples.
• multi-armed banditkind of · A multi-armed bandit is a sequential decision problem in which an agent chooses among options with uncertain rewards, balancing reward seeking with gathering information about those options.
• Bayes' theoremuses · Bayes' theorem is a probability rule that expresses a conditional probability in terms of a prior probability, a likelihood, and the evidence.
• exploration-exploitation trade-offaddresses · The exploration-exploitation trade-off is the decision problem of balancing actions that gather information about uncertain alternatives with actions chosen for their currently expected payoff.
• epsilon-greedycontrasts with · Epsilon-greedy is an action-selection strategy that chooses a random action with probability epsilon and otherwise selects the currently highest-valued action.
• randomized probability matchinguses · Randomized probability matching is a decision rule that selects each alternative with probability equal to the estimated probability that the alternative is optimal.

This explainer was generated by Manning's knowledge graph from the text of Bayesian Optimization in Action. The section links point to the parts of the book it draws on.