Explore-Exploit Tradeoff

A foundational heuristic strategy that balances exploration and exploitation through a simple, tunable probability parameter (ε).

• Exploitation: With probability 1-ε, the agent selects the action with the highest current estimated reward.
• Exploration: With probability ε, the agent selects a random action uniformly from all available options.

While simple and widely used in practice (e.g., initial A/B testing), its exploration is undirected and inefficient for large action spaces, as it does not consider the potential value of the actions it explores.

A deterministic, optimism-in-the-face-of-uncertainty principle that selects the action with the highest statistical upper bound on its potential reward.

The algorithm calculates an index for each action a: UCB(a) = SampleMean(a) + c * sqrt( log(TotalPlays) / Plays(a) )

• SampleMean(a): The current empirical average reward (exploitation term).
• sqrt(...): An exploration bonus proportional to the uncertainty about action a. Less-played actions have higher uncertainty.
• Constant c: Controls the exploration weight.

By always choosing the action with the maximum UCB index, the algorithm automatically directs exploration towards promising but uncertain options, providing strong theoretical regret guarantees.

A Bayesian probability matching algorithm that naturally balances exploration and exploitation by sampling from posterior distributions.

Core Mechanism:

1. Maintain a prior distribution (e.g., Beta for Bernoulli rewards, Gaussian for continuous) over the expected reward of each action.
2. For each decision, sample a single reward estimate from each action's current posterior distribution.
3. Select the action with the highest sampled value.
4. Observe the real reward and update the posterior for the chosen action using Bayes' Theorem.

This elegantly ties exploration to uncertainty: actions with wider (more uncertain) posteriors are more likely to yield high samples and be chosen. It is asymptotically optimal and highly performant in practice, forming the basis for many modern contextual bandit systems.

A generalization of the multi-armed bandit where decisions are informed by observed context or features, enabling personalization. Instead of learning a single best action, the algorithm learns a policy that maps contexts to actions.

Key Algorithms:

• LinUCB: Uses linear models to estimate rewards and compute UCB-style confidence intervals in the feature space.
• Thompson Sampling with Linear Models: Samples weights from a posterior over a linear model to predict rewards for a given context.

Real-World Application: This is the core architecture for systems like news article recommendation, where the 'context' is user features (browsing history, location) and article features, and the 'arm' is which article to show.

A framework for the non-stochastic setting where rewards are not generated from a stationary probability distribution but can be arbitrarily assigned by an 'adversary'. This models highly dynamic or competitive environments.

Core Challenge: Classic stochastic algorithms like UCB can fail because they rely on convergence assumptions. Adversarial algorithms must be robust to reward sequences with no statistical guarantees.

Key Algorithm: EXP3 (Exponential-weight algorithm for Exploration and Exploitation)

• Maintains a weight for each action.
• Selects actions probabilistically, with probability proportional to the weights.
• Updates weights using an exponential function of the estimated reward.
• It introduces intentional randomness to ensure exploration and provides regret bounds against any sequence of rewards.

The theoretical performance of explore-exploit algorithms is rigorously compared using regret, defined as the difference between the cumulative reward of the optimal policy and the algorithm's cumulative reward.

Typical Regret Bounds:

• Epsilon-Greedy: O(T^{2/3}) or O(log T) with a decaying ε schedule. Simple but sub-optimal theoretically.
• UCB1 (for stochastic bandits): O(log T). Optimal logarithmic regret for stationary environments.
• Thompson Sampling (stochastic): O(log T). Also achieves optimal logarithmic regret.
• EXP3 (adversarial): O(sqrt(T)). The optimal regret bound for the adversarial setting.

This analysis guides algorithm selection: use UCB/Thompson for stable environments, and adversarial algorithms like EXP3 when rewards are non-stationary or unpredictable.

A sequential decision-making framework that formalizes the explore-exploit dilemma. An agent faces a set of actions ("arms"), each with an unknown reward distribution. The goal is to maximize cumulative reward by deciding which arm to pull at each timestep. It is the canonical model for online experimentation (A/B/n testing) and recommendation systems.

• Stochastic Bandits: Rewards are drawn i.i.d. from a fixed distribution per arm.
• Adversarial Bandits: Rewards can be assigned arbitrarily by an opponent.
• Contextual Bandits: The agent receives side information (context) before each decision, allowing for personalization.

The primary theoretical framework for analyzing online learning and bandit algorithms. Regret measures the cumulative loss incurred by the algorithm compared to the best fixed action in hindsight. The goal of an algorithm is to achieve sublinear regret, meaning the average regret per round goes to zero over time. This proves the algorithm is learning efficiently and not just exploiting poorly.

• Pseudo-Regret: Compares against the best single action.
• External Regret: Compares against the best sequence of actions from a fixed class.
• Regret Bound: A theoretical guarantee, often expressed as O(√T) or O(log T), where T is the number of rounds.

A Bayesian algorithm for solving the multi-armed bandit problem. It maintains a posterior probability distribution for the reward of each arm. At each step, it samples a potential reward value from each arm's posterior and selects the arm with the highest sampled value. This elegantly balances exploration (sampling from uncertain posteriors) and exploitation (selecting high sampled values).

• Natural Probabilistic Exploration: Exploration is proportional to the current uncertainty.
• Asymptotic Optimality: Achieves the theoretical lower bound on regret for stochastic bandits.
• Widely Used: The foundation for many modern Bayesian optimization and contextual bandit systems.

A deterministic principle and family of algorithms for bandit problems. UCB selects the action with the highest upper confidence bound on its expected reward. This bound is the current empirical average reward plus an exploration bonus (e.g., based on the Hoeffding inequality). The bonus shrinks as an arm is pulled more, naturally transitioning from exploration to exploitation.

• Optimism in the Face of Uncertainty: Assumes the unknown reward is as high as plausibly possible.
• UCB1: A classic algorithm with a simple, provable log(t) regret bound.
• LinUCB: A linear variant for contextual bandits that models reward as a linear function of context.

A simple, heuristic strategy for balancing exploration and exploitation. With probability ε (epsilon), the algorithm selects a random action (exploration). With probability 1-ε, it selects the action with the highest current estimated reward (exploitation). It is easy to implement and tune but is often less efficient than probability-matching methods like Thompson Sampling.

• ε-Decay: A common improvement where the exploration rate ε is gradually reduced over time (e.g., ε = 1/t).
• Fixed vs. Adaptive: A fixed ε leads to perpetual, inefficient exploration. Decaying ε schedules more exploration early on.
• Common Baseline: Often used as a simple benchmark against which more sophisticated algorithms are compared.

An advanced bandit framework that incorporates side information (context). Before choosing an action, the algorithm observes a feature vector (e.g., user profile, page content). The goal is to learn a policy that maps contexts to actions to maximize reward. This is the standard model for personalized recommendations, dynamic pricing, and clinical trials where patient history informs treatment choice.

• Linear Models: Algorithms like LinUCB and Linear Thompson Sampling assume reward is a linear function of context.
• Neural Bandits: Use deep neural networks to model complex, non-linear reward functions from high-dimensional contexts.
• Reduces to Standard Bandits: If the context is null or constant, the problem reduces to the classic multi-armed bandit.