5 Contextual Bandit: Optimizing Stochastic One-step Decisions

The chapter introduces bandits as a practical, lightweight form of reinforcement learning for one-step decisions when the full dynamics of a system are unknown or unnecessary. Rather than modeling transitions as in a Markov decision process, bandit methods repeatedly choose an action, observe an immediate reward, and update beliefs from experience. This makes them well suited to problems such as ad placement, email optimization, website testing, and promotional offers, where the goal is to learn which option works best while acting. The chapter also distinguishes simple multi-armed bandits from contextual bandits, where observable information like customer profile or time of day can guide the decision even though the context itself does not evolve in response to the action.

A central theme is the exploration–exploitation trade-off: exploitation uses current knowledge to choose the best-known option, while exploration tries less certain actions to gather information and avoid premature commitment. The chapter explains this balance through several algorithms, starting with random and greedy baselines, then moving to epsilon-greedy, UCB, and Thompson Sampling. Epsilon-greedy injects randomness to keep learning, UCB adds a structured uncertainty bonus to favor under-sampled arms, and Thompson Sampling uses Bayesian belief updates with Beta distributions to sample actions according to uncertainty. All of these methods rely on incremental updates of value estimates, allowing them to learn efficiently without storing full histories.

The later part of the chapter extends these ideas to contextual bandits through LinUCB, using personalized discounting as the business example. Here, each customer impression comes with features such as customer segment, purchase behavior, and timing, and the algorithm learns separate linear models per action to predict reward from context. By combining predicted reward with an uncertainty term, LinUCB can target exploration more intelligently than non-contextual epsilon-greedy, and in the example it produces substantially higher revenue on offline test data. The chapter closes by stressing regret as the formal way to measure learning performance, and by warning that real environments are often non-stationary, delayed, multi-objective, and subject to cold start and drift—so successful bandit systems must keep exploring, personalize decisions, and adapt continuously.

Comparing multi-armed bandits, contextual bandits, and full reinforcement learning.

Incremental update formula applied in all bandit algorithms.

Upper confidence bound (UCB) core algorithm.

Bernoulli mass distribution.

Beta distribution and its components.

Evolution of probability beliefs for one Ad (arm) in Thomson sampling.

Comparison of running bandit algorithms after 5000 iterations.

Cumulative Regret comparisons of different policies for 500 iterations (for better comparison).

Expected reward (payoff) in LinUBC algorithm.

LinUCB algorithms and its components.

Performance comparison on the test set.

• Bandits are the lightweight version of reinforcement learning with no state transitions, just choose observe update.
• Bandit algorithms are best for problems with immediate payoffs and static context such as ads emails layouts and discounts.
• The central challenge in bandit algorithms is balancing exploration and exploitation to maximize long term reward.
• We do balance between exploration and exploitation because we don’t know the true probability distributions, and we have to estimate.
• Multi armed bandits ignore context and look for the best arm overall.
• Contextual bandits use features like demographics or time of day to personalize decisions in real time.
• Random strategies are baselines and should always be beaten.
• Greedy agents often underperform because they lock in too early on a suboptimal option.
• Epsilon greedy ensures steady exploration with occasional random actions.
• UCB uses confidence bounds to target exploration where uncertainty is high.
• Thompson Sampling is a Bayesian approach that balances exploration and exploitation automatically.
• Incremental update formulas allow efficient learning without storing the full history.
• Regret is the theoretical way to measure algorithm performance and the goal is sub linear regret growth.
• In real campaigns true regret cannot be calculated so proxies like business KPIs must be used.
• Off policy evaluation with logged data is a conservative but reliable way to test contextual bandits offline.
• LinUCB learns to target discounts intelligently maximizing revenue and protecting margin.
• Exploration must never be eliminated completely to avoid policy collapse.
• Drift and non-stationarity are inevitable in real markets and demand techniques like forgetting, sliding windows, or resets.
• Delayed or censored rewards require proxies and buffers to keep learning timely and accurate.
• Multiple objectives must be handled explicitly by shaping rewards or adding constraints to respect profit and business rules.
• Combinatorial bandits extend to slates, bundles, or rankings where payoffs depend on sets of actions, not single choices.
• Adversarial environments like auctions or reactive competitors may require robust algorithms such as EXP3.
• Covariate shift means contexts change over time and exploration floors are essential to avoid blind spots.
• Cold start problems for new ads or users can be tackled with optimistic priors or warm-start approaches.
• Bandits should be treated as continuous experimentation systems rather than one-off A/B tests.
• The three guiding principles are simple but powerful: keep exploring, personalize with context and expect drift.

FAQ