Bayesian Bandit

The core mechanism of a Bayesian Bandit is the continuous updating of a posterior distribution over each arm's reward probability. Starting with a prior belief (e.g., a Beta distribution for binary rewards), the algorithm observes the outcome of a chosen action and applies Bayes' theorem to compute a new, more informed posterior. This posterior encodes both the estimated reward rate and the uncertainty around that estimate, shrinking as more data is collected. This principled uncertainty quantification is what distinguishes Bayesian methods from frequentist approaches like Upper Confidence Bound (UCB).

Thompson Sampling is the most prominent action selection strategy for Bayesian Bandits. At each decision step, the algorithm draws a single random sample from the current posterior distribution of each arm. It then selects the arm with the highest sampled value. This elegant mechanism achieves a natural balance:

• Exploitation: Arms with high estimated means are sampled more frequently.
• Exploration: Arms with high uncertainty have wide posteriors, giving them a chance to produce a high sample and be selected. This probability matching approach has been proven to minimize cumulative regret asymptotically.

To make posterior updates analytically tractable and computationally fast, Bayesian Bandits heavily leverage conjugate priors. A conjugate prior is a distribution that, when combined with a specific likelihood function via Bayes' theorem, yields a posterior in the same distributional family.

• Beta-Bernoulli: For binary click/no-click rewards, a Beta prior is conjugate to the Bernoulli likelihood.
• Normal-Normal: For continuous, normally distributed rewards (e.g., revenue per session), a Normal prior is conjugate.
• Dirichlet-Multinomial: For categorical outcomes with more than two possibilities. This allows for simple, closed-form parameter updates without expensive Markov Chain Monte Carlo (MCMC) methods.

Unlike Epsilon-Greedy, which explores blindly at random, a Bayesian Bandit directs exploration toward arms where the value of information is highest. An arm with a wide posterior distribution represents a high degree of uncertainty—it could be terrible or excellent. Thompson Sampling naturally prioritizes these ambiguous arms to reduce uncertainty. This targeted exploration is far more sample-efficient, avoiding wasting trials on arms already known with high confidence to be suboptimal. The posterior variance serves as an intrinsic, dynamic exploration bonus that decays as knowledge is gained.

A significant practical advantage of the Bayesian framework is the ability to warm-start the model with existing knowledge. If a product team has historical data from a previous campaign or expert intuition about a new item's performance, this can be encoded directly into the prior distribution. For example, a Beta(α=20, β=80) prior on a new banner's click-through rate expresses a strong belief that the rate is around 20%, based on similar past creatives. This prevents the bandit from starting with a completely random, high-regret exploration phase and accelerates convergence to an optimal policy.

In dynamic retail environments, consumer preferences drift over time, violating the stationary assumption of standard bandits. Bayesian Bandits can be adapted for non-stationary reward distributions by introducing a forgetting mechanism. Instead of updating posteriors indefinitely, a discount factor is applied to past observations, or the posterior variance is artificially inflated over time. This causes the model to gradually forget old data and increase its uncertainty, triggering a fresh wave of targeted exploration to re-learn the current optimal action in a shifting landscape.

The core mathematical object in a Bayesian Bandit. Rather than storing a single point estimate of an arm's reward, the agent maintains a full probability distribution (the posterior) representing its belief. Common choices include the Beta distribution for binary rewards (click/no-click) and the Gaussian distribution for continuous rewards. As data is observed, Bayes' theorem updates this distribution, shrinking its variance as confidence grows.

The fundamental dilemma that Bayesian Bandits solve probabilistically. Exploitation means choosing the arm with the highest current expected reward to maximize immediate gains. Exploration means choosing a suboptimal arm to gather more data and reduce uncertainty. A Bayesian Bandit encodes this trade-off directly in the posterior variance: it automatically explores more when uncertainty is high and exploits more as the model converges.

A mathematical convenience that makes Bayesian Bandits computationally tractable. A conjugate prior is a prior distribution that, when combined with a specific likelihood function via Bayes' theorem, yields a posterior in the same distributional family. For example:

• Beta-Binomial: Beta prior + Binomial likelihood = Beta posterior (for click data)
• Gaussian-Gaussian: Gaussian prior + Gaussian likelihood = Gaussian posterior (for revenue data) This allows for simple, closed-form updates without expensive Markov Chain Monte Carlo (MCMC) methods.

The standard optimization objective for evaluating a bandit algorithm. Regret is defined as the difference between the cumulative reward of an optimal oracle policy (always picking the true best arm) and the reward accumulated by the learning agent. A Bayesian Bandit aims to minimize Bayesian regret, which averages over the prior. The key insight is that the prior's quality heavily influences early performance: a well-specified prior leads to a warm-start and dramatically lower initial regret.

An extension where the reward distribution depends on a contextual feature vector observed before the decision. Instead of a single posterior per arm, a model (like a Bayesian Logistic Regression or a Neural Network with Dropout uncertainty) maps context to a posterior distribution over rewards. This allows the agent to personalize actions: the same arm might have a high reward probability for one user segment and a low probability for another, all inferred through the Bayesian lens.