Chapter 5: Contextual Bandit: Optimizing Stochastic One-step Decisions
This introduction motivates bandits as experience-based decision methods and distinguishes pure from contextual bandits.
After this chapter you will be able to
- Unknown transition model limitation. Explain why the dynamic programming approach described in the previous chapter is difficult to apply when business system transitions are unknown.
- Bandit learning cycle. Describe the repeated learning cycle of a multi-armed bandit and how it simplifies decision making compared with a full Markov decision process.
- Pure and contextual bandits. Distinguish a pure multi-armed bandit from a contextual bandit using the role of state or context.
- Lightweight Bandit Learning. Explain why bandits are a lightweight form of reinforcement learning and when they fit a business decision.
- Bandit and RL Settings. Distinguish multi-armed bandits, contextual bandits, and full reinforcement learning by their treatment of state and decisions.
- Exploration and exploitation tradeoff. Explain exploration and exploitation and why balancing them supports long-term cumulative reward.
- Action choices shape learning. Explain how action choices determine the data available for learning, and distinguish what exploration reveals in bandits, contextual bandits, and full reinforcement learning.
- Ad campaign bandit model. Describe how the simulated ad campaign represents a bandit problem and how the agent receives feedback.
- Baseline and epsilon strategies. Distinguish random, greedy, and epsilon-greedy ad selection and explain their exploration trade-offs.
- Upper confidence bound selection. Explain how UCB combines estimated ad value and uncertainty to choose where to explore.
- Thompson sampling decisions. Trace how Thompson Sampling uses beliefs about ad click rates to balance exploration and exploitation.
- Regret as missed opportunity. Explain regret as the reward lost by choosing actions rather than acting optimally from the beginning.
- Exploration and regret patterns. Explain how excessive exploration and premature exploitation produce regret, and what their cumulative regret patterns reveal.
- Regret bounds and deployment. Explain why regret is useful for comparing algorithms even when actual numerical regret cannot be calculated in a real campaign.
- Contextual discounting decision. Explain how a contextual bandit frames personalized discounting and how context differs from a dynamic reinforcement-learning state.
- LinUCB linear reward model. Describe how LinUCB predicts rewards for different discounts and learns the weights from observed data.
- Context specific exploration. Explain how LinUCB selects a discount by balancing predicted reward and uncertainty for the current context.
- Historical replay evaluation. Trace how the example trains and evaluates agents using historical customer records rather than a live environment.
- Drift and stale evidence. Explain why changing payoffs can make old evidence misleading and describe ways a bandit can adapt.
- Continuous personalized experimentation. Explain why production bandits should keep exploring, personalize with context, and plan for drift rather than operate as a one-time test.
What it builds on
- Hands-on code: solving a resource allocation problem (chapter 4) · The previous example of solving a Markov decision process with dynamic programming.
- Markov decision process (chapter 2) · The state, action, reward, and transition framing of a Markov decision process.
- State: Anatomy of sequential decision making (chapter 2) · The role of state in decision making.
Section by section
Introduction
This introduction motivates bandits as experience-based decision methods and distinguishes pure from contextual bandits.
- Unknown transition model limitation: Explain why the dynamic programming approach described in the previous chapter is difficult to apply when business system transitions are unknown.
Why it matters: This explains why learning from experience is useful when a business cannot specify how its system changes. - Bandit learning cycle: Describe the repeated learning cycle of a multi-armed bandit and how it simplifies decision making compared with a full Markov decision process.
Why it matters: The cycle shows how a bandit learns while avoiding the transition modeling required by a full sequential problem. - Pure and contextual bandits: Distinguish a pure multi-armed bandit from a contextual bandit using the role of state or context.
Why it matters: This distinction helps identify when information about the current decision can be included in a bandit problem.
Key terms: transition probabilities, transition function, dynamic programming, multi-armed bandit, action, reward, beliefs, state transitions, contextual bandit, state
5.1 Bandits as lightweight reinforcement learning
This section explains bandits as lightweight reinforcement learning, compares bandit settings with full reinforcement learning, and illustrates their business applications.
- Lightweight Bandit Learning: Explain why bandits are a lightweight form of reinforcement learning and when they fit a business decision.
Why it matters: This helps you recognize decisions where learning from immediate outcomes is simpler than planning a sequence. - Bandit and RL Settings: Distinguish multi-armed bandits, contextual bandits, and full reinforcement learning by their treatment of state and decisions.
Why it matters: The distinction helps you choose a formulation that matches whether information and future states matter. - Business Decision Bandit Mapping: Apply the bandit framing to a business example by identifying its choices and immediate measurable outcome.
Why it matters: Mapping choices and outcomes makes it easier to recognize a practical bandit problem.
Key terms: bandit algorithms, action, reward, strategy, lightweight reinforcement learning, multi-armed bandit, contextual bandit, state, static context, full reinforcement learning
5.2 Tradeoff between exploitation and exploration
This section explains why learning decision-makers balance exploration and exploitation and outlines how several algorithms approach that balance.
- Exploration and exploitation tradeoff: Explain exploration and exploitation and why balancing them supports long-term cumulative reward.
Why it matters: Balancing what you know with what you could learn helps avoid settling too early or wasting opportunities. - Action choices shape learning: Explain how action choices determine the data available for learning, and distinguish what exploration reveals in bandits, contextual bandits, and full reinforcement learning.
Why it matters: The actions you select determine what you get a chance to learn. - Algorithm approaches to balance: Describe at a high level how ε-greedy, Upper Confidence Bound, and Thompson Sampling approach exploration and exploitation.
Why it matters: These approaches illustrate different ways to balance learning and earning.
Key terms: exploration, exploitation, long-term cumulative reward, multi-armed bandit, contextual bandit, contexts, future states, ε-greedy, Upper Confidence Bound, UCB
5.3 Simulating an Ad campaign problem with bandit algorithms
This section simulates an ad campaign and compares bandit strategies for learning which ad earns the most clicks.
- Ad campaign bandit model: Describe how the simulated ad campaign represents a bandit problem and how the agent receives feedback.
Why it matters: This model makes clear what the agent can learn from and what remains hidden. - Baseline and epsilon strategies: Distinguish random, greedy, and epsilon-greedy ad selection and explain their exploration trade-offs.
Why it matters: These strategies show why neither random choice alone nor early commitment reliably balances learning and reward. - Incremental reward estimate: Explain how an agent updates an ad's estimated average reward without keeping every past outcome.
Why it matters: Incremental updates let an agent revise its estimates efficiently as feedback arrives. - Upper confidence bound selection: Explain how UCB combines estimated ad value and uncertainty to choose where to explore.
Why it matters: UCB shows how an agent can favor uncertain ads without exploring purely at random. - Bernoulli and Beta beliefs: Distinguish the Bernoulli model of a click from the Beta belief about an ad's unknown click-through rate.
Why it matters: The distinction separates uncertainty about an ad's click rate from the randomness of an individual click. - Thompson sampling decisions: Trace how Thompson Sampling uses beliefs about ad click rates to balance exploration and exploitation.
Why it matters: Sampling from beliefs lets the agent pursue strong ads while still giving uncertain ones a chance.
Key terms: arms, action, reward, click-through rate, environment, random agent, greedy agent, ε-greedy, exploration, exploitation
5.4 Quantifying bandit algorithms performance with Regret
This section explains regret as a measure of bandit performance, its relationship to exploration and exploitation, and its practical use in comparing algorithms.
- Regret as missed opportunity: Explain regret as the reward lost by choosing actions rather than acting optimally from the beginning.
Why it matters: Regret gives you a way to describe the cost of decisions that fall short of the best available choice. - Exploration and regret patterns: Explain how excessive exploration and premature exploitation produce regret, and what their cumulative regret patterns reveal.
Why it matters: The shape of cumulative regret helps reveal whether a policy is learning effectively or continuing to miss opportunities. - Regret bounds and deployment: Explain why regret is useful for comparing algorithms even when actual numerical regret cannot be calculated in a real campaign.
Why it matters: Regret theory can guide an algorithm choice even when the best possible real-world reward is unavailable. - Contextual bandit distinction: Distinguish contextual bandits from the classic bandits used so far by describing how extra information can tailor decisions.
Why it matters: Context lets a bandit adapt its choices to the situation instead of treating every decision alike.
Key terms: regret, reward, optimal reward, exploration, exploitation, cumulative regret, UCB, Thompson Sampling, true CTRs, theoretical regret
5.5 Dynamic personalized discounting with contextual bandits
This section models personalized discounting with LinUCB and compares it with a non-contextual baseline using historical customer data.
- Contextual discounting decision: Explain how a contextual bandit frames personalized discounting and how context differs from a dynamic reinforcement-learning state.
Why it matters: Context lets a discounting policy respond to customer differences instead of applying one offer to everyone. - LinUCB linear reward model: Describe how LinUCB predicts rewards for different discounts and learns the weights from observed data.
Why it matters: The per-discount linear models let the agent estimate which offer may work for a particular customer. - Context specific exploration: Explain how LinUCB selects a discount by balancing predicted reward and uncertainty for the current context.
Why it matters: Targeted exploration helps the agent learn about offers where its predictions for a customer are uncertain. - Model and evaluation assumptions: Describe the assumptions and limitations of the LinUCB discounting example.
Why it matters: These assumptions limit how confidently the example's results can be applied to changing real-world conditions. - Historical replay evaluation: Trace how the example trains and evaluates agents using historical customer records rather than a live environment.
Why it matters: Replay makes it possible to test decisions with recorded data while recognizing that rewards for unchosen historical actions are unavailable. - Discounting comparison results: Describe the reported comparison between LinUCB and epsilon-greedy, including the agents' different starting conditions.
Why it matters: The results illustrate the potential value of personalized offers, while the different starting conditions matter when interpreting the comparison.
Key terms: contextual bandit, context, state, action, reward, LinUCB, context features, expected reward, weights, evidence matrix
5.6 Beyond stationary bandit problems
This section explains practical challenges and design principles for keeping bandit systems useful beyond stationary, immediate-feedback settings.
- Drift and stale evidence: Explain why changing payoffs can make old evidence misleading and describe ways a bandit can adapt.
Why it matters: A bandit must adapt when yesterday’s best choice stops performing well. - Delayed reward feedback: Describe why delayed rewards complicate learning and how proxy rewards or buffered outcomes can help.
Why it matters: Real customer outcomes may not be visible when a choice is made. - Multiple business objectives: Explain why optimizing clicks alone can conflict with business goals and how rewards or constraints can reflect those goals.
Why it matters: The most-clicked option is not necessarily the most valuable or acceptable business choice. - Slates and adversarial environments: Distinguish choosing a slate from choosing one arm, and describe how an adversarial reward process differs from ordinary drift.
Why it matters: Some applications involve a whole set of choices or competitors who react to the system. - Context shift and cold starts: Describe context shift and cold starts, and identify practical responses to each.
Why it matters: A system must handle both a changing audience and options or customers with little history. - Continuous personalized experimentation: Explain why production bandits should keep exploring, personalize with context, and plan for drift rather than operate as a one-time test.
Why it matters: A useful production bandit needs to keep working as customers and markets change.
Key terms: stationary, drift, non-stationarity, forgetting mechanisms, sliding windows, delayed rewards, proxy rewards, pending outcomes, multiple objectives, shape rewards
5.7 Summary
Where this is used later
- Temporal difference learning (chapter 6) · Sequential reinforcement learning builds on the distinction between immediate decisions and evolving state.
Concepts explained in this chapter
- upper confidence boundAn upper confidence bound method selects actions using an optimistic estimate that combines estimated reward with an uncertainty-based confidence bonus.
- epsilon-greedyAn epsilon-greedy strategy selects a random action with probability epsilon and otherwise selects an action with the highest estimated value.
- Thompson samplingA Bayesian bandit action-selection algorithm that samples each action's expected reward from its posterior distribution and selects the action with the best sample.
- contextual banditA contextual bandit is a sequential decision model in which an agent observes static context, selects an action, and receives an immediate reward without action-induced state transitions.
- exploration-exploitation trade-offThe exploration-exploitation trade-off is the tension between gathering information through unfamiliar actions and selecting actions currently expected to yield high rewards.
- multi-armed banditA multi-armed bandit is a sequential decision model in which an agent repeatedly chooses among actions and observes their rewards without modeled state transitions.
- greedy agentA greedy agent always selects the action with the highest current estimated payoff and does not deliberately explore alternatives.
- LinUCBA contextual bandit algorithm that models expected reward as a linear function of context and uses upper confidence bounds to balance exploration and exploitation.
- contextContext is observable information about a decision situation that is available before an action is selected.
- AI agentAn entity in reinforcement learning that observes an environment, selects actions, and improves its behavior from feedback.
- actionAn action is a choice made by an agent that can affect the subsequent state of its environment.
- beta distributionA continuous probability distribution on the interval from zero to one, commonly used to represent uncertainty about a Bernoulli probability.
- environmentAn environment is the external system or setting with which an agent interacts and whose responses produce consequences for the agent's actions.
- reward signalA reward is a numerical feedback signal indicating the desirability of an outcome or transition after an agent's action.
- uncertainty bonusAn additive score component that favors options whose estimated values are less certain or based on fewer observations.
- offline evaluationOffline evaluation estimates an agent's performance by replaying previously collected interaction data instead of interacting with a live environment.
- EXP3EXP3 is an adversarial bandit algorithm that uses exponentially weighted action estimates to select actions under potentially adversarial rewards.
- adversarial problemAn adversarial environment is an environment in which other agents or processes can react strategically to the decision maker's actions.
- cold start problemThe cold start problem is the difficulty of making effective recommendations or decisions when a new action, item, user, or system has little or no interaction data.
- combinatorial banditA combinatorial bandit is a bandit model in which each decision selects a combination or set of actions whose joint outcome determines the payoff.
- covariate shiftCovariate shift is a distribution change in which the distribution of input contexts changes while the conditional outcome relationship may remain stable.
- delayed or censored rewardA delayed reward is feedback whose value becomes observable only after a time interval following the associated action.
- exploration floorAn exploration floor is a lower bound on the probability or frequency with which an agent continues trying less-established actions.
- forgettingForgetting is an adaptation technique that reduces the influence of older observations when estimating changing payoff relationships.
- non-stationarityNon-stationarity is a condition in which the statistical relationships governing contexts, actions, or outcomes change over time.
- optimistic priorAn optimistic prior assigns favorable initial beliefs to uncertain actions or parameters before sufficient observations are available.
- sliding windowA sliding window is a method that restricts estimation to observations from the most recent fixed or adaptive time interval.
- warm startA warm-start approach initializes a new decision model from prior data, parameters, or a related trained model.
- regretRegret is the difference between the reward obtained by an algorithm and the reward it could have obtained by acting optimally over the same decisions.
- sublinear regretSublinear regret is regret whose growth is slower than linearly with the number of decisions, causing average regret to approach zero.
- bandit algorithmA bandit algorithm selects among actions and updates its action-selection strategy from observed rewards while balancing exploration and exploitation.
- Q-learningQ-learning is a model-free reinforcement-learning algorithm that estimates the optimal action-value function through temporal-difference updates using the maximum estimated value of the next state.
- TD-learningTemporal-difference learning updates value estimates incrementally using observed rewards and estimates of subsequent values.
- constrained banditA constrained bandit is a bandit model in which action selection must satisfy resource, exposure, fairness, or other operational constraints.
- personalizationPersonalization is the adaptation of decisions, recommendations, or treatments to individual users or contexts.
- proxy reward functionA proxy reward is an observable signal that serves as an approximation for a later or less observable desired outcome.
- exploitationExploitation is choosing the action currently believed to produce the greatest reward based on available knowledge.
- explorationExploration is the selection of actions whose outcomes are uncertain in order to gather information about their payoffs.
- reinforcement learningReinforcement learning is a machine-learning paradigm in which an agent learns to choose actions through interactions with an environment and feedback about their consequences.
- replay bufferA replay buffer is a storage structure that retains interaction records for later processing or learning updates.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
