Thompson Sampling

Thompson Sampling, also known as Bayesian Bandit, is a strategy used in the context of multi-armed bandit problems, where the goal is to maximize rewards over a series of choices among different options (or "arms") with uncertain outcomes.

This approach is rooted in Bayesian probability theory and addresses the exploration-exploitation dilemma by probabilistically determining which arm to pull next based on past results. Each arm is associated with a probability distribution reflecting the belief about its reward potential, which is updated as more data is gathered.

In each round, Thompson Sampling randomly selects an arm to play by drawing from these distributions, favoring arms with higher expected rewards but also occasionally exploring less chosen arms to refine their reward estimates. This method dynamically balances the need to exploit known reward opportunities with the need to explore less certain options, optimizing long-term performance.

‍

An application of Thompson Sampling can be found in online advertising, where an advertiser needs to decide which version of an ad to display to maximize user engagement (clicks). Each version of the ad is considered an "arm" of the bandit problem. Thompson Sampling is used to select which ad to show to each user, based on the historical click-through rates (CTR) of the ads.

Initially, all ads have similar probabilities of being chosen, but as data accumulates, the algorithm updates the reward probability distributions for each ad.

Ads with higher CTRs are more likely to be selected, but those with fewer impressions also get a chance to be tested, allowing for the discovery of potentially better-performing ads. This method ensures that the advertising strategy adapts over time, continually optimizing the balance between exploring new ads and exploiting known high-performing ads to maximize overall engagement.

‍