You know how to update your beliefs about a single option using a Beta distribution and Bernoulli rewards. Now, let's put that knowledge into action to make decisions. Thompson Sampling provides a simple, elegant loop for choosing between multiple competing options, often called a multi-armed bandit problem.

The core idea is to let the data guide your choices in a probabilistic way. Instead of committing to the option that looks best right now, you sample from your belief about each option. The option that wins this random draw gets picked for the next trial. This naturally balances exploring uncertain options and exploiting ones that have proven successful.

Let's formalize this into an algorithm. Imagine you have $k$ arms, or options, to choose from. For each arm $i$, you maintain a posterior distribution that represents your current belief about its success rate. Since we're dealing with win/loss (Bernoulli) outcomes, we use a Beta distribution for each arm, $Beta(\alpha_i, \beta_i)$. Initially, you might start with a $Beta(1, 1)$ prior for all arms, representing complete uncertainty. The loop then proceeds as follows, for each round of decision-making:

This loop repeats, continuously refining your beliefs. As you gather more data, the Beta distributions for each arm become narrower and more representative of their true success rates. An arm that frequently gives rewards will see its $\alpha$ parameter grow, shifting its distribution towards 1. An unsuccessful arm will see its $\beta$ parameter grow, shifting its distribution towards 0.

The selection step, $a_t = \text{argmax}_i(\theta_i)$, is where the magic happens. You aren't picking the arm with the highest expected value. Instead, you're giving each arm a chance to prove itself based on a random snapshot of its potential. An arm with high uncertainty (a wide Beta distribution) might occasionally produce a very high sample, giving it a chance to be explored. An arm with a proven track record (a narrow distribution peaked at a high value) will consistently produce high samples, leading to its exploitation.

Let's consider a simple two-arm bandit problem. Arm A has a posterior of $Beta(3, 2)$, and Arm B has a posterior of $Beta(1, 1)$.

• Arm A has seen 2 successes ($α = 1+2=3$) and 1 failure ($β = 1+1=2$). Its expected value is $3/(3+2) = 0.6$.
• Arm B is unexplored. Its posterior is the uniform $Beta(1, 1)$ prior. Its expected value is $1/(1+1) = 0.5$.

A purely greedy approach would always pick Arm A. But what if Arm B is actually better? Its uniform distribution means it has a chance, albeit small, of producing a sample higher than Arm A's. Let's say we sample from both:

We choose Arm B, pull it, and observe a success (reward = 1). We then update Arm B's posterior to $Beta(1+1, 1) = Beta(2, 1)$. Arm A's posterior remains $Beta(3, 2)$. In the next round, both arms have stronger posteriors, and we repeat the sampling process. This simple mechanism, proposed by William R. Thompson back in 1933, is remarkably effective and forms the basis for many modern reinforcement learning systems.