10. Reinforcement Learning and Sequential Decision-Making

Introduction and Context

Many important artificial intelligence problems are not solved by predicting a single label or estimating a fixed numerical quantity. An autonomous vehicle must repeatedly choose steering and braking actions; a recommendation system must decide which item to display while considering future user engagement; a warehouse robot must plan movements under uncertainty; and a pricing system must adapt prices as customers and competitors respond. In each case, decisions influence the environment, and the consequences of an action may appear only later. These are problems of sequential decision-making.

Reinforcement learning (RL) is a framework for learning how to act through interaction with an environment. An agent observes a situation, selects an action, receives a reward, and moves to a new situation. Over time, it learns a policy—a strategy for selecting actions—that seeks to maximize cumulative reward. Unlike supervised learning, RL generally does not require a dataset containing the correct action for every situation. Unlike unsupervised learning, it is explicitly concerned with goal-directed behavior.

RL combines probability, optimization, control theory, dynamic programming, statistics, and machine learning. Its central difficulty is that actions have both immediate and delayed consequences. An action that produces a small short-term loss may be essential for achieving a larger long-term gain. The agent must also balance exploration of uncertain alternatives with exploitation of actions already believed to be effective.

This chapter develops the mathematical foundations of reinforcement learning through Markov decision processes, value functions, Bellman equations, temporal-difference learning, Q-learning, and policy-based methods. It then examines applications, implementation choices, risks, governance issues, and an illustrative industrial case.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Explain sequential decision-making and the assumptions underlying Markov decision processes.

2. Define states, actions, rewards, transitions, policies, returns, value functions, and discount factors.

3. Derive and interpret Bellman expectation and optimality equations.

4. Distinguish model-based and model-free reinforcement learning.

5. Explain Monte Carlo learning, temporal-difference learning, SARSA, and Q-learning.

6. Compare value-based, policy-based, and actor–critic methods.

7. Analyze exploration–exploitation strategies and their operational consequences.

8. Evaluate reinforcement-learning applications in robotics, pricing, recommendations, operations, and autonomous systems.

9. Identify technical, ethical, safety, and governance risks in RL deployments.

From Immediate Prediction to Sequential Choice

A sequential decision problem consists of a decision-maker, an environment, available actions, observations or states, and outcomes associated with decisions. At time t, the agent receives a state S_t, chooses an action A_t, receives a reward R_(t+1), and transitions to S_(t+1). The process then continues.

A reward is a numerical signal representing the desirability of an outcome from the perspective of the task. It may be positive, negative, or zero. A reward is not necessarily the same as profit, and it should not be confused with a complete specification of organizational goals. For example, a delivery robot may receive rewards for completing deliveries, penalties for collisions, and a small time penalty for every minute consumed.

The return G_t is the cumulative future reward from time t. In a discounted formulation,

G_t = R_(t+1) + γR_(t+2) + γ²R_(t+3) + …,

where γ, the discount factor, lies between 0 and 1 in many continuing or infinite-horizon settings. A value near zero emphasizes immediate outcomes; a value near one gives greater importance to long-term consequences. Discounting may represent time preference, uncertainty about distant outcomes, or a mathematical device that ensures convergence.

An episode is a finite interaction that ends in a terminal state, such as a game ending or a robot completing a task. In continuing tasks, there may be no natural terminal state. The design of rewards and termination conditions strongly affects learned behavior. An agent optimizes the formal reward it receives, not the informal intention of its designers.

Markov Decision Processes

A Markov decision process (MDP) provides the standard formal model for finite or infinite sequential decision problems. It is commonly represented by the tuple (S, A, P, R, γ):

• S is the set of states.
• A is the set of actions.
• P(s' | s, a) is the probability of reaching state s' after action a in state s.
• R(s, a) or R(s, a, s') specifies the reward.
• γ is the discount factor.

The Markov property states that the current state contains all information needed to predict the distribution of the next state and reward. Formally, the future is conditionally independent of the past given the current state and action. In real systems, this property may not hold directly. A partially observed environment may require the agent to maintain a belief state, memory, or recurrent representation summarizing historical observations.

A policy π specifies how actions are selected. A stochastic policy gives a probability π(a|s) of selecting action a in state s. A deterministic policy chooses one action for each state. Policies may be fixed rules, parameterized functions, neural networks, or learned probability distributions.

The state-value function under policy π is

V^π(s) = E_π[G_t | S_t = s],

the expected return when beginning in state s and thereafter following π. The action-value function is

Q^π(s,a) = E_π[G_t | S_t = s, A_t = a].

The optimal value functions are defined by

V*(s) = max_π V^π(s),

and

Q*(s,a) = max_π Q^π(s,a).

An optimal policy selects actions that maximize the appropriate optimal value.

Bellman Reasoning and Dynamic Programming

The Bellman principle of optimality expresses a sequential problem recursively: an optimal plan consists of an optimal first decision followed by optimal decisions from the resulting state. For a fixed policy, the Bellman expectation equation is

V^π(s) = Σ_a π(a|s) Σ_s' P(s'|s,a)[R(s,a,s') + γV^π(s')].

For an optimal policy, the Bellman optimality equation is

V(s) = max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')].

The corresponding action-value equation is

Q(s,a) = Σ_s' P(s'|s,a)[R(s,a,s') + γ max_a' Q(s',a')].

These equations support dynamic programming algorithms when the transition model and reward function are known. Policy evaluation estimates the value of a specified policy. Policy improvement makes the policy greedy with respect to estimated values. Policy iteration alternates these steps. Value iteration applies Bellman optimality updates directly until values stabilize.

Dynamic programming can be computationally expensive when the state or action spaces are large. It also presumes access to an accurate environment model. These limitations motivate model-free learning, in which the agent estimates values or policies directly from experience.

How Reinforcement Learning Learns from Experience

Monte Carlo methods estimate values from complete episodes. After an episode ends, the observed return is used to update the value of each visited state. Monte Carlo learning is conceptually straightforward and does not require a model, but it can be slow and has high variance because it waits until the end of an episode.

Temporal-difference (TD) learning updates estimates after each transition, using a current estimate to predict the remaining return. A basic TD(0) update is

V(S_t) ← V(S_t) + α[R_(t+1) + γV(S_(t+1)) − V(S_t)],

where α is the learning rate. The term in brackets is the TD error. TD methods combine the sample-based character of Monte Carlo learning with the bootstrapping idea of dynamic programming. They can learn online and are suitable for continuing tasks.

For action values, SARSA performs an on-policy update:

Q(S_t,A_t) ← Q(S_t,A_t) + α[R_(t+1) + γQ(S_(t+1),A_(t+1)) − Q(S_t,A_t)].

It learns the value of the policy actually being followed, including its exploration behavior. Q-learning is an off-policy method:

Q(S_t,A_t) ← Q(S_t,A_t) + α[R_(t+1) + γ max_a Q(S_(t+1),a) − Q(S_t,A_t)].

Q-learning estimates the optimal greedy action values even if behavior includes exploration. This separation can be useful, but it may also create instability or overoptimism when estimates are inaccurate.

A simple exploration policy is ε-greedy selection. With probability 1−ε, the action with the highest current value is selected; with probability ε, an action is selected randomly. High ε promotes exploration, while low ε promotes exploitation. Alternatives include softmax action selection, upper-confidence-bound methods, optimistic initialization, parameter noise, and posterior-sampling approaches. Exploration must be constrained when actions can cause injury, financial loss, legal violations, or irreversible damage.

Function Approximation and Deep Reinforcement Learning

Tabular methods store one value for every state or state–action pair. This is infeasible for high-dimensional or continuous problems. Function approximation replaces tables with parameterized functions such as linear models, decision structures, or neural networks. A neural network may approximate Q(s,a), V(s), or the policy π(a|s).

Deep Q-networks (DQNs) approximate action values from high-dimensional observations. Important stabilizing ideas include experience replay, which trains on randomly sampled past transitions, and a target network, which changes more slowly than the online network. These mechanisms reduce harmful correlations and moving-target effects, although they do not eliminate instability.

Value-based methods are most natural when actions are discrete. Policy-gradient methods instead optimize policy parameters directly. If actions are sampled from π_θ, the objective J(θ) can be differentiated using the policy-gradient principle. In simplified form,

∇_θJ(θ) = E[∇_θ log π_θ(A_t|S_t) G_t].

The policy is adjusted to increase the probability of actions associated with high returns. Policy methods handle continuous actions naturally, but gradient estimates can have high variance.

Actor–critic methods combine the two perspectives. The actor represents the policy, while the critic estimates a value function and supplies a learning signal. Advantage estimates, often written A(s,a) = Q(s,a) − V(s), indicate whether an action performed better or worse than the policy’s average expectation at that state. Modern algorithms such as proximal policy optimization and soft actor–critic introduce mechanisms intended to improve stability, sample efficiency, or exploration, but their suitability depends on the environment and evaluation design.

Offline or batch RL learns from previously collected data without freely interacting with the environment. It is attractive in healthcare, finance, industrial control, and recommendation systems where online experimentation is costly or unsafe. However, offline methods can fail when the learned policy selects actions poorly represented in the data. This is known as distribution shift or out-of-distribution action selection.

Exploration, Exploitation, and the Value of Information

Exploration and exploitation are not merely algorithmic settings; they are strategic choices. Exploitation uses the best-known action to obtain immediate performance. Exploration gathers information that may improve future decisions. A recommendation platform that always displays the currently most-clicked item may miss emerging content. A pricing system that never tests a new price may fail to discover a more profitable market response.

The appropriate balance depends on uncertainty, opportunity cost, reversibility, and risk. Exploration is relatively safe when actions are inexpensive and outcomes are quickly observable. It is much more difficult when feedback is delayed, populations are vulnerable, or experiments affect public safety. Practical systems often use simulation, shadow deployment, conservative policy improvement, human approval, randomized experiments with guardrails, and explicit risk constraints.

Reward shaping can speed learning by adding intermediate signals, but poorly designed shaping can create unintended shortcuts. For example, rewarding a robot for moving quickly without adequately penalizing collisions may produce dangerous behavior. Reward design should therefore be connected to measurable outcomes, constraints, and stakeholder values. In multi-objective settings, a scalar reward may conceal important trade-offs; constrained or multi-objective RL may be more appropriate.

Applications Across Organizations and Industries

In robotics, RL can learn locomotion, grasping, navigation, and manipulation policies. Simulation-to-real transfer is common because real-world trial-and-error is expensive. Randomization of masses, friction, lighting, and sensor noise in simulation can improve robustness, but the resulting policy still requires validation on physical hardware.

In dynamic pricing, an agent may choose prices based on inventory, demand estimates, time, competitor signals, and customer segments. The reward may include margin, sales volume, inventory clearance, and fairness constraints. The system must account for delayed demand, competitor reactions, and the possibility that aggressive exploration damages customer trust.

Recommendation systems select content, products, or advertisements over a sequence of interactions. Immediate clicks are easy to measure, but long-term satisfaction, retention, diversity, and well-being may be more important. A policy optimized only for clicks can encourage repetitive, sensational, or polarizing content.

Operations applications include inventory control, vehicle routing, workforce scheduling, energy management, maintenance planning, and production control. RL is especially useful when decisions are repeated and the environment changes over time. Nevertheless, mathematical optimization, simulation, heuristics, and traditional control may outperform RL when the model is known or the action space is highly constrained.

Autonomous decision systems combine perception, prediction, planning, and control. RL usually operates within a larger architecture rather than replacing every component. A perception model may estimate the state, a planner may generate feasible actions, and an RL policy may select among them. Safety monitors, fallback controllers, and human intervention mechanisms are essential in high-consequence domains.

Illustrative Case Study: Inventory Replenishment for a Retail Network

Background

Consider an illustrative retail organization operating several stores. Each store sells products with uncertain daily demand. Excess inventory incurs holding and spoilage costs, while insufficient inventory produces lost sales and dissatisfied customers. Orders placed with suppliers arrive after variable lead times.

Situation and Problem

The organization initially uses a fixed reorder point and quantity. This rule performs adequately during stable demand but creates stockouts during promotions and excess inventory after demand declines. Management wants a system that adapts to demand, lead time, inventory position, and warehouse capacity.

Analysis

The state may include on-hand inventory, inventory in transit, recent demand, promotion status, supplier lead-time estimates, and available budget. The action is the order quantity or a discrete order-level category. The reward can combine sales margin, holding cost, stockout penalty, waste, and order-processing cost. A discount factor reflects the importance of future inventory consequences.

The problem is not simply to maximize sales on the current day. Ordering too little creates a future stockout; ordering too much ties up capital and may lead to spoilage. The MDP representation therefore captures the interaction between current decisions and later states. Because demand and supply conditions are stochastic, the transition model may be estimated from historical data or represented through a simulator.

Approach and Strategy

The organization first establishes a simulator calibrated against historical demand and lead-time distributions. A baseline policy based on the existing reorder rule is evaluated. A conservative offline RL method is then trained using historical transitions and simulated scenarios. The reward is constrained so that service levels remain above a specified threshold and order quantities remain within supplier and storage limits.

Before deployment, the policy is tested under demand surges, supplier delays, promotion errors, and missing data. It is initially used in shadow mode: it generates recommendations while the existing process remains in control. Managers review recommendations, and deviations are recorded. A limited pilot is then conducted for selected products with low safety risk and rapid feedback.

Outcome

The main organizational outcome is not simply a higher estimated reward. The project produces a policy with documented assumptions, monitored constraints, and a fallback rule. Performance is compared with the baseline using stockout rate, inventory turnover, waste, margin, service level, and stability across stores. If the RL policy improves one metric while harming another, management can revise the reward and constraints rather than accepting an opaque aggregate score.

Learning Points

The case illustrates that RL implementation begins with problem formulation, not algorithm selection. State design, reward definition, data quality, simulator validity, constraint handling, and evaluation methodology are at least as important as the learning algorithm. It also shows why offline evaluation and staged deployment are necessary when exploration in the real environment is costly.

Limitations, Failure Modes, and Professional Risks

RL can be data-hungry and computationally expensive. Learning may require many interactions, and the environment may change before a policy converges. Sparse rewards make credit assignment difficult: when success occurs after many actions, determining which action contributed is challenging. Delayed feedback and partial observability further complicate learning.

A policy can exploit flaws in the reward or simulator. This is called reward hacking or specification gaming. A system may achieve a formal target while violating the intended objective. Another danger is overfitting to historical data or simulated conditions. A policy that performs well in a familiar environment may fail under distribution shift, rare events, sensor degradation, or adversarial behavior.

Common technical mistakes include using an insufficient state representation, ignoring terminal-state handling, selecting an inappropriate discount factor, evaluating only average reward, and tuning on the same environment used for final testing. In deep RL, instability, high variance, sensitivity to random seeds, and misleading benchmark comparisons are frequent concerns. Reproducible evaluation should report multiple runs, confidence intervals where appropriate, baseline comparisons, and stress tests.

Safety requires more than a penalty in the reward function. Hard constraints, action shielding, safe exploration, control-theoretic backup policies, simulation testing, and human override may be required. In regulated settings, organizations must also preserve records explaining data sources, policy versions, approval decisions, incidents, and changes in operating conditions.

Ethically, RL systems can distribute benefits and harms unevenly. Dynamic pricing may disadvantage vulnerable customers; recommendation policies may amplify harmful material; automated employment or lending decisions may reinforce historical inequities. Designers should assess fairness, privacy, transparency, contestability, and accountability. User consent and data minimization remain relevant even when the system is framed as an optimization problem.

Emerging Directions and Best Practices

Current research increasingly emphasizes offline RL, safe and constrained RL, multi-agent learning, hierarchical policies, language-model agents, causal decision-making, and sim-to-real transfer. Multi-agent settings introduce strategic interaction, coordination, competition, and non-stationarity. Hierarchical RL decomposes long tasks into subgoals, potentially improving interpretability and learning efficiency. Causal approaches seek to distinguish correlation from the consequences of intervention.

A responsible professional workflow includes:

• Define the decision, time horizon, stakeholders, constraints, and failure costs before selecting an algorithm.
• Construct a state representation that includes relevant historical information and does not expose unnecessary personal data.
• Design rewards and constraints jointly, with domain experts and affected stakeholders.
• Establish a simple baseline and evaluate against it using operational metrics, not reward alone.
• Use simulation, offline validation, stress testing, and staged deployment before online exploration.
• Monitor drift, performance inequality, constraint violations, unusual actions, and feedback loops.
• Maintain a fallback policy and a clear human escalation process.
• Document assumptions, training data, evaluation environments, policy changes, and known limitations.

The central lesson is that reinforcement learning is a decision technology, not merely a neural-network technique. Its success depends on the quality of the decision formulation and on disciplined governance of the interaction between the learned policy and the real world.

Chapter Summary

Reinforcement learning addresses sequential decisions in which actions alter future states and rewards. Markov decision processes formalize states, actions, transition probabilities, rewards, and discounting. Policies determine behavior, while value and action-value functions measure expected future return. Bellman equations express the recursive structure of these values and support dynamic programming.

Model-free methods learn from experience. Monte Carlo methods wait for complete returns, whereas temporal-difference methods update from one-step predictions. SARSA is on-policy; Q-learning is off-policy and uses a greedy target. Large problems require function approximation, including deep value networks, policy gradients, and actor–critic architectures. Exploration must be balanced against safety, cost, uncertainty, and long-term value.

RL can support robotics, pricing, recommendations, operations, and autonomous systems, but deployment involves reward misspecification, distribution shift, sparse feedback, unsafe exploration, fairness concerns, and governance obligations. Effective practice combines strong problem formulation, constraints, conservative evaluation, monitoring, human oversight, and comparison with simpler alternatives.

Key Terms

Markov decision process: A formal model of sequential decisions defined by states, actions, transitions, rewards, and discounting.

Agent: The decision-making entity that observes the environment and selects actions.

Environment: The external system with which an agent interacts.

State: Information representing the situation relevant to future decisions.

Action: A choice available to the agent at a particular state.

Reward: A numerical signal indicating the immediate desirability of an outcome.

Return: The cumulative, often discounted, sequence of future rewards.

Discount factor: A parameter determining the relative importance of future rewards.

Policy: A rule or probability distribution for selecting actions in states.

Value function: Expected return from a state under a specified policy.

Action-value function: Expected return from taking an action in a state and then following a policy.

Bellman equation: A recursive equation relating current value to immediate reward and future value.

Temporal-difference learning: Learning that updates estimates using sampled transitions and bootstrapped predictions.

Q-learning: An off-policy algorithm that estimates optimal action values using a greedy target.

SARSA: An on-policy action-value algorithm using the sequence state, action, reward, next state, next action.

Exploration: Choosing uncertain actions to gain information.

Exploitation: Choosing actions currently believed to yield the best outcome.

Function approximation: Representing values or policies with parameterized models rather than tables.

Actor–critic: An architecture in which an actor learns the policy and a critic estimates values.

Reward hacking: Achieving a formal reward objective through behavior that violates the intended goal.

Review Questions

Short Answer Questions

1. What is the Markov property, and why is it useful in reinforcement learning?

2. Distinguish a reward from a return.

3. What role does the discount factor play in an MDP?

4. How does SARSA differ from Q-learning?

5. Define exploration and exploitation.

Long Answer Questions

1. Explain the components of an MDP and derive the Bellman optimality equation for an action-value function.

2. Compare Monte Carlo learning, temporal-difference learning, and dynamic programming.

3. Explain value-based, policy-based, and actor–critic methods, including their appropriate use cases.

4. Discuss the technical and organizational challenges of deploying RL in a real business process.

5. Explain why reward design, safety constraints, and human oversight are essential in autonomous decision systems.

Analytical / Application Questions

1. Design an MDP for dynamic pricing of a perishable product. Specify states, actions, rewards, constraints, and possible sources of partial observability.

2. An RL policy increases click-through rate but reduces long-term user retention and content diversity. Analyze the likely causes and propose an improved evaluation and reward framework.

3. A warehouse robot learns in simulation but collides with obstacles after deployment. Diagnose possible causes and propose a staged sim-to-real validation and safety strategy.

22. Multiple Choice Questions with Answers

Question 1

Which statement best describes the Markov property in a reinforcement-learning problem?

A. The agent must always choose a deterministic action.

B. The current state contains sufficient information for predicting the future transition distribution given the action.

C. Rewards must be positive and received immediately.

D. The environment must be fully known before learning begins.

Correct Answer: B. The current state contains sufficient information for predicting the future transition distribution given the action.

Question 2

An agent receives rewards of 2 immediately and 10 one step later, with γ = 0.5. Ignoring later rewards, what is the return at the first step?

A. 2

B. 5

C. 7

D. 12

Correct Answer: C. 7

Question 3

Which update makes Q-learning an off-policy method?

A. It uses the next action actually selected by the behavior policy.

B. It waits until the entire episode has ended.

C. It uses the maximum estimated next-state action value in its target.

D. It updates only deterministic policies.

Correct Answer: C. It uses the maximum estimated next-state action value in its target.

Question 4

A recommendation agent always chooses the item with the highest estimated click probability and never tests alternatives. What problem is most directly illustrated?

A. Over-exploration

B. Insufficient exploitation

C. Insufficient exploration

D. Violation of the Markov property by definition

Correct Answer: C. Insufficient exploration

Question 5

Which feature most clearly distinguishes temporal-difference learning from Monte Carlo learning?

A. TD learning requires a known transition model.

B. TD learning can update estimates before an episode ends by bootstrapping from current estimates.

C. TD learning cannot be used in continuing tasks.

D. TD learning never uses observed rewards.

Correct Answer: B. TD learning can update estimates before an episode ends by bootstrapping from current estimates.

Question 6

In an inventory-control RL system, which reward design is most likely to create unsafe or undesirable behavior?

A. Combining margin with holding, waste, and stockout costs.

B. Including service-level constraints and operational limits.

C. Rewarding rapid sales while ignoring stockouts and spoilage.

D. Evaluating the learned policy against a reorder-point baseline.

Correct Answer: C. Rewarding rapid sales while ignoring stockouts and spoilage.

Question 7

Why are actor–critic methods useful for many continuous-control problems?

A. They eliminate the need for rewards.

B. They combine a policy learner with a value estimator that supplies a learning signal.

C. They require a complete transition table for every state.

D. They guarantee globally optimal policies.

Correct Answer: B. They combine a policy learner with a value estimator that supplies a learning signal.

Question 8

A policy performs well on historical data but selects actions rarely represented in that data during deployment. What risk does this illustrate?

A. Distribution shift or out-of-distribution action selection

B. Corrective reward shaping

C. Excessive terminal-state handling

D. Guaranteed generalization

Correct Answer: A. Distribution shift or out-of-distribution action selection

Question 9

Which evaluation practice is most appropriate before deploying an RL policy in a safety-sensitive environment?

A. Deploy immediately with a high exploration rate.

B. Evaluate only the average training reward.

C. Use simulation, stress tests, baseline comparisons, staged deployment, and fallback controls.

D. Remove human oversight to avoid policy interference.

Correct Answer: C. Use simulation, stress tests, baseline comparisons, staged deployment, and fallback controls.

Question 10

A robot receives a large reward for moving quickly but only a small penalty for collisions. Which failure is most likely?

A. The policy may exploit reward misspecification by moving dangerously.

B. The policy will necessarily become purely exploratory.

C. The Markov property will automatically be restored.

D. The policy cannot learn from temporal differences.

Correct Answer: A. The policy may exploit reward misspecification by moving dangerously.