What Does Thompson Sampling Optimize?

0:00You know, it's a dilemma that you face almost every single day, even if you don't really have a name for it. Oh, absolutely. It's the classic exploit tradeoff. Like, do you stick with the strategy, you know, yields a solid return? Or do you take a risk and try something totally unproven because, you know, it might just be the next big thing. Right. Which is always the question. Yeah. And you see this everywhere in how businesses allocate marketing budgets or how streaming platforms decide which movie to put on your home screen. Even how you decide where to invest your savings. Totally. You want to maximize your returns, but to find the best returns, you inevitably have to waste some time and money exploring suboptimal options.

0:42Yeah. And in the fields of computer science and statistics, we actually call this the multi-armed bandit problem. The multi-armed bandit. I love that name. It's great. Right. Imagine standing in a casino in front of a row of slot machines. You know, the one arm bandits. Each machine has a different, totally unknown probability of paying out. Okay, so you have no idea which one is the lucky one. Exactly. And your goal is to walk away with the most money possible. So to do that, you have to pull different levers to learn their payout rates. Right. That would be the exploration phase. Yes, exactly.

1:14But you also need to spend as many turns as possible pulling the lever of the machine you think is the luckiest, which is the exploitation phase. And I imagine balancing those two perfectly is like incredibly difficult. It is. It's actually one of the foundational challenges in machine learning. Well, and what is genuinely wild about this is that the most successful, most widely deployed algorithm for solving this problem, it wasn't invented in Silicon Valley 10 years ago. No, not at all. It goes all the way back to 1933. This researcher named W.R. Thompson was trying to figure out how to allocate treatments in medical trials.

1:50Which is pretty much the ultimate high stakes explore exploit scenario. Right. I mean, he needed to maximize patient survival, giving them the treatment that seemed to be working best, while simultaneously gathering enough data to statistically prove which treatment was actually the optimal one. Yeah. And Thompson, he couldn't afford to just run a standard A-B test where, you know, half the patients get a bad treatment just for the sake of data collection. Right. You can't do that with human lives. Exactly. He needed the trial to adapt in real time. So he devised this heuristic, a mathematical rule of thumb, really, that we now call Thompson sampling.

2:29Thompson sampling. Right. And today, this algorithm is essentially the invisible engine of the Internet. I mean, it dynamically tests which headlines get the most clicks. It writes network traffic. It drives product recommendation engines. It's just everywhere. It is everywhere. But there is a massive catch here. For over 90 years, despite this algorithm basically running the digital world, nobody actually understood the underlying mathematical engine driving it. Which is kind of terrifying if you think about it. It is. It was just this statistical black box. Like, it worked, but we didn't know how it optimized its choices so perfectly.

3:04We really didn't. Well, the mission for this deep dive is to finally unpack the groundbreaking new mathematical research that solves this 90-year-old mystery. We are going to look under the hood of Thompson sampling, break down the optimization engine hidden inside it, and learn how to actually upgrade it. Yeah, and to appreciate what this new math reveals, we first have to recognize why Thompson sampling has always been viewed with deep, deep suspicion by theoretical computer scientists. Like they didn't trust it? Oh, not at all. Historically, it was the absolute oddball of the algorithm family.

3:42Kind of the black sheep that somehow became the most successful. Exactly. Okay, let's compare it to the algorithms that theorists actually like. You know, the ones where the math is completely transparent. Sure. So most modern multi-armed banded algorithms, they're engineered from the ground up to minimize something called regret. Regret. Yeah, regret is just the mathematical difference between the reward you actually collected and the maximum possible reward you could have collected if you had magically known the best option from the start. Okay, that makes sense. So how do the other algorithms handle that?

4:10Well, take an algorithm like UCB, which stands for upper confidence bound. It calculates a statistical confidence interval for every single option. Right. It basically looks at the average reward an option has given you so far, and then it artificially inflates that value based on how little data you have. It forces the system to be optimistic in the face of uncertainty. Okay, so it actively builds a mathematical buffer to ensure it doesn't ignore an option just because of, like, a few bad initial results? Correct. You don't want to write off a good option too early. Yeah. And then you have adversarial algorithms.

4:46Where are those? Those are designed for environments where the payouts are constantly shifting. These explicitly maintain a probability distribution over all the options. So they're tracking everything constantly? Yes. At every single step, they calculate these really complex weight updates, aggressively penalizing the options that perform poorly while simultaneously injecting, you know, calculated randomness to ensure they don't get trapped in a local optimum. But the main point is these algorithms wear their objectives on their sleeves. You can look at the code and point to the exact line of math where the algorithm actively balances regret against new information.

5:25OK, let's unpack this for a second. If those algorithms are these highly engineered machines calculating confidence intervals and weight distributions in real time, what exactly is Thompson sampling doing? Well, it just relies on Bayesian updates. Wait, that's it? Pretty much. It maintains a belief about the world, like a posterior distribution representing the likely payout of each option. But instead of calculating a complex optimization metric, in each round, it just randomly draws a single sample from each of those distributions. So it's literally just pulling a random number. Yeah. Whichever sample happens to have the highest numerical value, it pulls that arm.

6:02That is the entire process. You're kidding. No, I mean, there is no explicit regret minimization equation. There's no calculation of confidence bounds. It is just a randomized heuristic. Okay, so if UCB is like a highly analytical person who uses, I don't know, a color-coded spreadsheet with standard deviations to pick the optimal restaurant for dinner. Right. Very meticulous. Then Thompson's sampling is basically someone who just closes their eyes, throws a dart at a map of places they have vaguely good vibes about, and goes wherever the dart lands. That is surprisingly accurate, yes. Yet somehow, the dart thrower consistently eats better food than the spreadsheet user.

6:41Yeah, and the math actually backs up that comparison. Because it operated like a dart thrower, the theoretical community largely ignored Thompson's sampling for decades. They just didn't take it seriously. Right. It was considered far too simple, almost mathematically naive. But that all changed around 2011. What happened in 2011? Researchers, most notably Chappelle and Leigh at Yahoo, they ran these massive empirical studies testing these algorithms on live display advertising, basically predicting ad click-through rates at an enormous scale. Real-world high-stakes testing. Exactly. And Thompson sampling absolutely crushed the sophisticated, mathematically rigorous algorithms.

7:20it wasn't even close. It performed so well in the real world that the theorists were just forced to stop ignoring it. They had to play catch-up. Throughout the 2010s, mathematicians worked fiercely and finally managed to prove frequentist invasion regret bounds for Thompson's sampling. Meaning they mathematically proved that it works. Right, but bounding an algorithm's overall regret over a long time horizon doesn't explain the mechanics of how the algorithm makes its decisions step-by-step. So the inner workings, like why pulling a random sample achieves such a perfect balance between exploring and exploiting, that remained a total mystery.

7:56Exactly. Until now. Which brings us to the breakthrough. How did the math in this new research finally decode the dart thrower? Well, the researchers managed it by changing the analytical lens entirely. They decided to model the bandit problem as a Markov decision process, or an MDP. All right, an MDP. What does that actually look like? In this framework, you're moving through a sequence of states. The state of your system is simply your current posterior belief about the arms, and the action is the specific arm you choose to pull. Got it. But the true innovation was how they redefined the objective of the algorithm.

8:31Because typically, the objective is to minimize cumulative regret over an infinite timeline. Exactly, which is notoriously difficult to optimize at a single instantaneous point in time because the horizon is boundless. I mean, you can't easily weigh a tiny loss today against a theoretical gain 10 ,000 steps from now. Yeah, that sounds impossible. So to solve this, the researchers introduced a time-invariant notion of regret. Instead of tracking standard cumulative regret, they shifted to minimizing cumulative squared regret. Okay, I'm going to need you to break that down. Why does squaring the regret change the game so much?

9:07Well, think about what happens when you square a fraction. And regret is essentially a fractional gap between your current knowledge and perfect knowledge. The smaller the fraction, the smaller the resulting square. By optimizing for squared regret, the penalty for being wrong shrinks exponentially as you gather more data. Oh, wow. So it creates a mathematically bounded finite target. Precisely. And because the target is no longer stretching into infinity, the researchers were able to formulate a Bellman equation for the problem. Okay. I know the Bellman equation comes up heavily in dynamic programming and reinforcement learning, but what does it actually represent in this specific context?

9:48Think of the Bellman equation as the blueprint for absolute theoretical perfection. It defines the Bellman optimal policy. Perfection. Yeah, if an algorithm followed this policy, it would be the mathematical equivalent of a chess grandmaster who can see every possible future move and works perfectly backward to choose the absolute best move for the current moment. So it calculates the precise, optimal way to balance exploring and exploiting to minimize that squared regret. Exactly. It's the gold standard. Okay, but this circles back to the core mystery. I mean, the researchers built a theoretical benchmark of perfection using a Markov decision process and a Bellman equation.

10:27But Thompson sampling is still just pulling random samples from a probability distribution. Right. There is no Bellman equation programmed into its logic. And that is the big reveal of the findings. The researchers mathematically reverse-engineered Thompson sampling's randomized behavior. They translated the act of drawing random samples into an online optimization format. Wait, really? Yes. And when they laid the formula side by side, they discovered that Thompson sampling possesses a hidden implicit optimization structure that perfectly mimics the architecture of the Bellman optimal policy. You mean it accidentally wrote the perfect code without actually writing any code?

11:05It is uncanny. In its hidden optimization form, at every single round, Thompson Sampling is actively trying to minimize immediate instantaneous squared regret. Which is the exploitation side, right? Acting greedily based on what it knows. Exactly. But that greediness is mathematically held back by a specific penalty term, a regularizer, that forces it to explore. It's executing the exact same structural balancing act as the flawless Bellman equation. That's insane. It's like finding out the person throwing darts at the map is actually subconsciously calculating wind resistance, trajectory, and geographic density in their head before every single throw.

11:43That's a great way to put it. Okay, so if Thompson sampling and the perfect Bellman equation share this identical structure, you know, greediness held back by a regularizer, what is the actual difference between the two? Well, what's fascinating here is that because we have the mathematical structures, we can pinpoint the exact difference between pretty good and perfect. The difference lies entirely in what they use as their regularizer. Okay, what does Thompson sampling use? In Thompson sampling, the regularizer is driven by a very specific measure of uncertainty. Mathematically, it operates on the bisereal covariance between the reward gap of the arms and the identity of the optimal arm.

12:19Whoa, okay. Biserial covariance is a very dense term. Please translate how that actually functions when the algorithm makes a choice. Sure, sure. It basically acts as a regret-scaled uncertainty measure. In plain terms, it tracks how much the credible intervals of your different options overlap. Okay, overlapping intervals. Yeah, so Thompson Sampling decides to explore an arm primarily because it is uncertain about it. If there's a statistical probability that the arm you currently think is the best might actually be a fluke, Thompson Sampling's regularizer pushes it to explore the alternative.

12:54So its engine runs purely on unresolved uncertainty. Exactly. And how does that compare to the perfect Bellman benchmark? Well, the Bellman optimal policy doesn't care about uncertainty just for the sake of uncertainty. Its regularizer is based entirely on tension. Tension. Yes, the tension between immediate reward and future information. How did it define that tension? The Bellman equation only recognizes tension when one arm offers a higher immediate expected reward. But the other arm offers highly valuable information that will actively improve your future decisions. Okay, I think I'm getting it.

13:26If an unknown arm doesn't offer a strong informational payoff that mathematically outweighs the immediate loss for reward, the Bellman policy will just refuse to pull it, regardless of how uncertain you are about that arm. Right. Here's where it gets really interesting. Because I feel like we can map this reliance on uncertainty versus tension directly onto human behavior. Oh, totally. Let's go back to the restaurant analogy. You have a favorite local spot. Right. High reward. You know the menu. It's a guaranteed good meal. Yep, your go-to. But there's a poorly reviewed place down the street that you haven't been to in like five years.

14:02You're technically uncertain about it. Maybe they hired a new chef. Right. Thompson Sampling evaluates the overlapping credible intervals and says, Hey, there's enough unresolved variants here. Go eat at the poorly reviewed place tonight just to resolve the uncertainty. Exactly. It pushes you to take the risk simply because the data is stale. But the Bellman policy, the approach based on tension, looks at that exact same scenario and says, wait, your usual spot is excellent. The poorly reviewed place might be slightly different than you remember, but the actual information you gain by suffering through a mediocre male is not worth giving up your favorite burger.

14:42Yes, because there is no tension there. Right. The cost of exploring outweighs the value of the information. So it just says, go to your usual spot. The Bellman policy recognizes that not all uncertainty is actually worth resolving. But wait, if Thompson sampling relies purely on overlapping uncertainty, couldn't it get trapped investigating bad arms just because it hasn't looked at them in a while? Doesn't it get distracted? It absolutely gets distracted. And this brings us to the real world flaw of Thompson sampling that this mathematical translation finally exposed. OK, what is the flaw? Because its engine is fueled by uncertainty rather than true tension, it suffers from a condition known as incomplete learning.

15:20It has a systemic tendency to overexplore underperforming arms. Wow. It just can't let go of the what if. Exactly. And the research highlights this flaw by exposing a stunning mathematical phase transition in the Bellman policy. A phase transition. Yeah. They analyzed a Gaussian bandit scenario where the rewards follow a normal bell curve distribution. And they mapped out the exact threshold where the perfect Bellman policy completely stops exploring and switches to pure exploitation. Where is the threshold? It happens when the signal-to-noise ratio hits negative 0.276. Negative 0.276. Why that specific hyper-precise number?

16:01What is happening there? At that specific ratio, the expected loss from pulling the suboptimal arm massively outweighs the potential informational value hidden in the variance of the data. So the noise is overwhelming the signal? Yes. The Bellman equation essentially calculates that the cost of exploring this unknown R is now far greater than any informational arbitrage you could ever gain. The tension just vanishes entirely. So what does it do? It triggers a hard switch. It completely cuts off exploration and commits 100 % to the known better arm. It just shuts down. Yeah. But Thompson sampling can't do that.

16:34Because its regularizer is tied to lingering uncertainty rather than tension, it doesn't have a sharp cutoff. So it just keeps exploring. It just gradually, endlessly tapers off. It keeps casually pulling the suboptimal arm, wasting valuable time and resources. I'm struggling to visualize why it gets so confused, though. Walk us through how that failure actually plays out in the math. Sure. The research illustrates this beautifully, using beta distributions. Imagine comparing two options. Option A follows a beta 5, 4 distribution. Option B follows a beta 7, 7 distribution. Okay, wait. Break down what those numbers represent for the algorithm so we can follow along.

17:10The numbers basically represent the history of pulls. Option A, the beta 5 forearm, has five successes and four failures. Right. So that's nine total trials with an expected payout ratio favoring success. It's the objectively better choice. Now, option B, the beta 7 arm, has seven successes and seven failures. That's 14 total trials resulting in an expected payout ratio of exactly 50 percent. So it's underperforming. Yes, it is underperforming. So option B is a known loser. It has a worse expected payout, and it's been pulled 14 times compared to option A's 9 times. We have way more data proving it's mediocre.

17:49Precisely the point. The perfect Bellman policy looks at that scenario, realizes there is zero tension, and its regularizer drops to absolute zero. It behaves completely greedily, locking in option A. But Thompson's sampling. Its regularizer does not decay fast enough. It looks at option B, sees the flat distribution of seven successes and seven failures, and it detects a tiny sliver of overlapping uncertainty. Yeah, its engine tells it, let's just check it one more time to be absolutely sure. It temporarily halts pulling the proven better arm just to pull an overexplored underperforming arm. That is such a deeply human flaw.

18:29It's like it's the algorithmic equivalent of obsessively checking the tracking on a package you know isn't arriving until tomorrow. That's exactly what it is. You're uncertain, so you check, even though checking gives you zero actionable information and just wastes your time. So the researchers cracked the 90-year mystery of how the algorithm functions, and in the process, they exposed its greatest vulnerability. How do we fix it? Well, the fix they propose is actually brilliantly simple. Now that we know Thompson sampling is operating through this hidden online optimization framework, and we have the Bellman Optimal Policy serving as a clear benchmark.

19:05We can just perform a little regularizer engineering. Exactly. We could upgrade the engine we didn't even know we had. How do they do it? The researchers propose adding a shutdown criterion to Thompson sampling. You're essentially grafting a mathematical switch onto the algorithm. At every step, you evaluate the variance-based information gain of your options. You check to see if the arm that gives you the highest expected reward is also the arm that gives you the most information. Oh, I see. If the best arm for reward is also the best arm for learning, then there is no tension. Exactly. There is no exploit tradeoff left to make.

19:40Learning more and earning more are aligned on the exact same choice. And when that alignment happens? The shutdown criterion triggers. It forcibly overrides Thompson sampling, dropping its uncertainty regularizer down to zero. It forcibly stops the algorithm from being distracted by the lingering what-ifs of the lesser arms and compels it to exploit the optimal choice. That is profoundly elegant. I mean, we took a heuristic from 1933, a literal rule of thumb sketched out for medical trials, and for nearly a century, the tech world just trusted it blindly because the empirical data said it worked.

20:14They trusted the dart thrower. Right. But by passing it through the modern mathematical lens of a Markov decision process and shifting our objective metric to cumulative squared regret, we discovered it was secretly running a highly sophisticated optimization engine based on uncertainty all along. And if we connect this to the bigger picture, it just demonstrates the incredible power of having a theoretical benchmark. How so? Well, for decades, theorists were obsessed with proving that Thomson sampling worked. But this research dared to ask what it was secretly optimizing. By deriving the perfect Bellman equation for this specific setup, they built a compass.

20:51A compass to guide the math. Yes. Once you know what absolute perfection looks like mathematically and you finally decode the hidden machinery of your working algorithm, you can literally measure the gap between the two. You transform algorithm design from a dark art of trial and error into a true engineering science. You can engineer it to work better. We basically taught an algorithm that was obsessed with uncertainty how to finally understand true tension. We did. Which honestly leaves me with a thought I want you, the listener, to mull over today. We discussed how this entire branch of explore-exploit mathematics perfectly mirrors our own psychology.

21:30Think about the agonizing choices you face in your own life, whether it's a career pivot, a relationship, or deciding whether to move to a new city. It's all the same framework. It is. When you're stuck trying to make a difficult decision, take a step back and ask yourself, are you exploring out of true tension? Is one path offering safety while the other offers vital, life-changing information that genuinely outweighs the risk? That's the real question. Or are you just falling into the Thompson sampling trap? Are you actively giving your time, energy, and resources to a bad option, an underperforming scenario, simply because you are uncertain about it, even though it offers you no real reward and no valuable information?

22:07Maybe it is time to evaluate your own overlapping intervals, realize the noise is outweighing the signal, and trigger your own shutdown criterion. Thank you for joining us on this deep dive. We will catch you next time.