Exploration-Exploitation Tradeoff

The simplest bandit algorithm that selects the best-known action with probability 1-ε and a random action with probability ε. The epsilon parameter controls the exploration rate.

• Mechanism: A random number is drawn; if it falls below ε, a uniform random action is chosen, otherwise the action with the highest estimated value is exploited.
• Decay Schedules: In practice, ε is often annealed from a high initial value (e.g., 0.1) to a low floor (e.g., 0.01) to favor exploration early and exploitation later.
• Limitation: Explores uniformly, wasting resources on clearly suboptimal actions instead of focusing on promising uncertain ones.

A deterministic algorithm that selects actions based on an optimism in the face of uncertainty principle. It calculates an upper confidence bound for each action's expected reward and chooses the one with the highest bound.

• Formula: The score combines the empirical mean reward with an exploration bonus proportional to sqrt(ln(t) / n_i), where t is the total number of rounds and n_i is the count of times action i was chosen.
• Behavior: Actions with high uncertainty (low n_i) get a large bonus, forcing exploration. As data accumulates, the bonus shrinks and the empirical mean dominates.
• Regret: Achieves logarithmic regret, making it theoretically optimal for stationary bandit problems.

A Bayesian approach that maintains a posterior probability distribution over each action's reward. At each decision point, it samples a reward estimate from each distribution and selects the action with the highest sample.

• Natural Balance: The probability an action is chosen matches the probability it is optimal given current data. This provides a seamless, probabilistic exploration-exploitation balance.
• Prior Selection: Commonly uses a Beta-Bernoulli conjugate pair for binary rewards or a Gaussian model for continuous rewards, updated with each observed outcome.
• Empirical Performance: Often outperforms UCB in practice, especially in non-stationary environments, and is robust to delayed feedback.

A strategy that selects actions probabilistically according to a Gibbs distribution, where the probability of choosing an action is proportional to the exponential of its estimated value divided by a temperature parameter τ.

• Temperature Control: High τ makes the distribution nearly uniform (more exploration); low τ concentrates probability on the highest-valued action (more exploitation).
• Advantage: Unlike epsilon-greedy, the probability of selecting a suboptimal action is proportional to its estimated value, so the second-best action is explored more than the worst.
• Annealing: τ is typically decreased over time to shift from exploration to exploitation as the agent gains confidence in its value estimates.

Extends the multi-armed bandit framework by incorporating side information (context) about the user or situation before selecting an action. The agent learns a function mapping context to expected reward for each action.

• Linear UCB: Assumes the expected reward is a linear function of the context features and uses ridge regression to estimate parameters, with a confidence ellipsoid providing the exploration bonus.
• Neural Bandits: Uses a deep neural network as the function approximator, with the final layer's uncertainty used for exploration, enabling non-linear relationships.
• Application: The foundational model for real-time Next-Best-Action systems where user features (demographics, browsing history) serve as the context.

A sequential design strategy for optimizing black-box objective functions that are expensive to evaluate. It builds a probabilistic surrogate model, typically a Gaussian Process, and uses an acquisition function to decide where to sample next.

• Acquisition Functions: Common choices include Expected Improvement (EI), which measures the expected gain over the current best observation, and Upper Confidence Bound (UCB), which balances the predicted mean and uncertainty.
• Exploration-Exploitation: The acquisition function explicitly encodes the tradeoff, favoring points with high predicted value (exploitation) or high uncertainty (exploration).
• Use Case: Hyperparameter tuning of machine learning models, where each evaluation requires a full training run and is computationally costly.

When a new fashion line drops, the system has zero interaction data. Exploiting known best-sellers would ignore the new inventory entirely.

• The Dilemma: Allocate zero impressions and guarantee zero sales, or allocate a statistically significant exploration budget to gather initial click-through data.
• Mechanism: A Contextual Bandit assigns the new SKU a high prior uncertainty, forcing impressions alongside proven items.
• Outcome: Within hours, the system collects enough feedback to either promote the item to the exploitation pool or suppress it as a dud.

A returning customer sees a hero banner. The system must decide between the category they always buy (exploit) and a new adjacent category (explore).

• The Dilemma: Showing the familiar running shoes banner guarantees a click. Showing a hiking boots banner risks a bounce but might unlock a higher Customer Lifetime Value (CLV) trajectory.
• Mechanism: Thompson Sampling samples from the posterior distribution of conversion probabilities for each banner. If the hiking banner's distribution has a long tail of high values, it gets served.
• Outcome: The user discovers a new passion, and the retailer expands share of wallet.

A grocery chain has premium strawberries nearing expiration. The pricing engine must balance margin protection with waste reduction.

• The Dilemma: Exploiting the known $5.99 price point maximizes immediate margin but risks a 100% write-off. Exploring a $3.99 flash discount sacrifices margin but tests price elasticity.
• Mechanism: A Markov Decision Process (MDP) models the state as (inventory, time-to-expiry). The Q-function learns that the long-term value of selling at a discount exceeds the value of waste.
• Outcome: The algorithm triggers a dynamic markdown, clearing inventory and training the system on the true demand curve for future pricing.

A CRM system must decide when to hit 'send' on a promotional email to maximize open rates for a specific user segment.

• The Dilemma: The historical data says 10:00 AM Tuesday is the global peak (exploit). But this specific segment of night-shift workers might respond better at 8:00 PM (explore).
• Mechanism: An Epsilon-Greedy strategy sends 90% of emails at the known best time and 10% at random off-peak hours to test responsiveness.
• Outcome: The system discovers a 40% lift in open rates for the night-shift segment, updating the policy and demonstrating the cost of pure exploitation.

A physical retailer uses a digital twin to optimize the product mix on a high-traffic endcap display, balancing proven volume drivers with new vendor partnerships.

• The Dilemma: The top-selling cola brand guarantees footfall conversion. A new kombucha brand offers a higher margin but unknown sell-through rate.
• Mechanism: Upper Confidence Bound (UCB) selection scores each product by its mean sales plus an exploration bonus proportional to uncertainty. The kombucha's high uncertainty gives it a temporary boost.
• Outcome: The system gathers statistically valid sales data, proving the kombucha's viability without a long-term commitment to shelf space.

A streaming service recommends the next episode. Pure exploitation creates a filter bubble; pure exploration destroys user trust.

• The Dilemma: After a user binges a crime drama, the collaborative filtering signal is overwhelmingly strong for more crime dramas. Recommending a documentary is high-risk exploration.
• Mechanism: A Deep Q-Network (DQN) learns a policy that maximizes long-term session length, not just next-click probability. It learns that occasional diverse recommendations prevent churn.
• Outcome: The agent strategically inserts a single exploratory documentary recommendation after a binge session, measuring the regret of a potential skip against the reward of discovering a new genre affinity.

A reinforcement learning algorithm that chooses actions based on contextual information (e.g., user demographics, time of day) to maximize cumulative rewards. Unlike a simple A/B test, it continuously adapts by balancing the exploration of new actions with the exploitation of known high-reward actions.

• Uses side information to personalize decisions in real-time.
• Minimizes regret compared to a theoretical optimal policy.
• Core algorithm for dynamic headline optimization and product recommendations.

A Bayesian algorithm that selects actions randomly according to their posterior probability of being optimal. It naturally balances exploration and exploitation by allocating traffic proportionally to the uncertainty and expected value of each option.

• Maintains a probability distribution over the reward of each action.
• Automatically reduces exploration as confidence increases.
• Highly effective for cold start scenarios with limited data.

An optimization framework where the objective is to minimize the difference between the cumulative reward obtained and the reward that would have been obtained by an optimal oracle strategy that always selects the best action.

• External regret measures performance against the single best fixed action in hindsight.
• Swap regret measures performance against a policy that can modify its actions.
• Drives algorithm design in adversarial and stochastic bandit settings.

A simple heuristic where the agent exploits the best-known action with probability 1-ε and explores a random action with probability ε. The parameter ε is often decayed over time to shift from exploration to exploitation.

• Computationally trivial to implement.
• Does not account for the uncertainty of individual actions.
• Can waste exploration on clearly suboptimal options.

A deterministic algorithm that selects actions based on an optimistic estimate of their potential reward. It calculates an upper confidence bound for each action's expected value and chooses the one with the highest bound.

• The bound is the sum of the estimated mean reward and an exploration bonus.
• The bonus is proportional to the uncertainty, shrinking as an action is tried more often.
• Provides strong theoretical guarantees on cumulative regret.

A set of statistical techniques used to estimate the performance of a new target policy using historical data collected by a different, often suboptimal, behavior policy. This is critical for safely evaluating exploration strategies without deploying them live.

• Inverse Propensity Scoring (IPS) re-weights logged events to correct for selection bias.
• Doubly Robust Estimation combines IPS with a reward model for lower variance.
• Enables offline validation of new exploration heuristics.