Thompson Sampling

Thompson Sampling operates on a Bayesian framework, maintaining a probability distribution over the unknown reward of each action rather than a point estimate. For each pricing decision, the algorithm samples a value from each posterior distribution and selects the action with the highest sample. This intrinsic randomness ensures that actions with high uncertainty are explored proportionally to their chance of being optimal. As data accumulates, the posterior distributions narrow, naturally shifting behavior from exploration to exploitation without requiring an explicit exploration parameter like epsilon in epsilon-greedy strategies.

The core mechanism is probability matching: an action is selected with a frequency equal to the probability that it is the best action given current knowledge. This is fundamentally different from optimistic initialization or epsilon-greedy approaches. Key properties include:

• Uncertainty-driven exploration: Actions with wide posterior distributions are selected more frequently
• Automatic annealing: Exploration naturally decreases as confidence grows
• No hyperparameter tuning: The exploration-exploitation trade-off emerges from the Bayesian update process itself
• Regret minimization: Achieves logarithmic expected regret, matching the theoretical lower bound for stochastic bandits

Thompson Sampling achieves computational efficiency through the use of conjugate priors, which allow posterior distributions to be updated analytically rather than through expensive numerical methods. Common pairings include:

• Beta-Bernoulli: For binary outcomes like click/no-click or purchase/no-purchase at a given price point
• Gaussian-Gaussian: For continuous rewards like revenue per transaction, assuming known variance
• Gamma-Poisson: For count-based rewards like units sold per time period
• Dirichlet-Multinomial: For categorical outcomes with more than two possible results This analytical tractability makes Thompson Sampling suitable for real-time pricing systems requiring sub-millisecond decision latency.

The basic Thompson Sampling framework extends naturally to contextual bandits, where pricing decisions depend on observable features like customer segment, time of day, or inventory level. In the linear contextual variant, the algorithm maintains a multivariate Gaussian posterior over the coefficient vector of a linear reward model. For each decision, it samples a coefficient vector from this posterior and selects the price that maximizes the predicted reward given the current context. This enables personalized dynamic pricing that adapts to individual customer characteristics while maintaining the elegant exploration properties of the base algorithm.

Thompson Sampling provides strong theoretical guarantees that make it attractive for revenue-critical pricing applications:

• Logarithmic regret bound: The cumulative difference between the algorithm's rewards and the optimal policy grows only logarithmically with time, proven for Bernoulli and many other reward distributions
• Asymptotic optimality: Converges to selecting the truly optimal action with probability approaching 1 as data accumulates
• Finite-time bounds: Recent research provides explicit bounds on performance after a finite number of trials, enabling practical risk assessment
• Robustness to non-stationarity: When combined with discounting or sliding windows, adapts to slowly changing market conditions while maintaining theoretical guarantees

Deploying Thompson Sampling in production dynamic pricing requires careful engineering considerations:

• Prior specification: Weakly informative priors (e.g., Beta(1,1) for Bernoulli) prevent strong initial bias while allowing rapid learning
• Warm-starting: Historical transaction data can inform initial prior parameters, avoiding the cold-start period
• Batch updating: In high-throughput systems, posterior updates can be batched to reduce computational load without significant regret increase
• Non-stationarity handling: Exponential decay weighting or sliding window approaches allow adaptation to shifting demand curves
• Constraint integration: Business rules like minimum margins or MAP compliance can be enforced as post-processing on sampled actions without breaking the Bayesian framework

An extension of the standard bandit framework that incorporates contextual features (e.g., user demographics, time of day) into the decision. While Thompson Sampling solves the basic explore/exploit dilemma, contextual bandits use a model to predict the reward of an action given the current context, enabling true real-time personalization.

A sequential design strategy for optimizing black-box objective functions that are expensive to evaluate. It uses a probabilistic surrogate model (often a Gaussian Process) and an acquisition function to decide where to sample next. Unlike Thompson Sampling, which selects discrete arms, Bayesian Optimization is ideal for tuning continuous hyperparameters like the exact discount percentage in a pricing model.

A broader family of algorithms where an agent learns an optimal pricing policy through trial-and-error interaction with a market environment. Techniques include:

• Q-Learning: Learns the value of a price in a specific state.
• Policy Gradients: Directly optimizes the pricing policy. Thompson Sampling is often categorized as a simple, effective form of reinforcement learning for the multi-armed bandit sub-problem.

A foundational econometric technique that quantifies how the quantity demanded of a product changes in response to a price change. While Thompson Sampling learns optimal prices through direct experimentation, elasticity modeling provides the causal understanding of the demand curve. The two are complementary: elasticity estimates can form the prior distribution for a Thompson Sampling algorithm.

A production testing architecture where a new pricing model (the challenger) is deployed alongside the incumbent model (the champion). A small percentage of traffic is routed to the challenger to empirically validate its performance. Thompson Sampling naturally implements this by continuously allocating traffic to the best-performing price points, making it an ideal algorithm for automated champion-challenger testing.

The phenomenon where the statistical relationship between price and demand changes over time in unforeseen ways. A static Thompson Sampling model with fixed priors can become stale. To combat this, implementations often use a sliding window or discount factor to weight recent observations more heavily, ensuring the algorithm adapts to shifting market conditions and consumer behavior.