9. Reinforcement Learning and Sequential Decision Systems

Introduction and Context

Many artificial intelligence problems cannot be solved by predicting a single label or estimating a fixed numerical quantity. An autonomous vehicle must repeatedly choose acceleration, braking, and steering actions; a recommender system must decide which item to display while considering long-term user engagement; an industrial controller must regulate a process under uncertainty; and a clinical decision-support system may recommend a sequence of interventions rather than one isolated action. These are sequential decision problems. The quality of an action depends not only on its immediate consequence but also on how it changes future possibilities.

Reinforcement learning (RL) provides a mathematical and computational framework for learning through interaction. An agent observes a state, selects an action, receives a reward, and moves to another state. Through repeated experience, it learns a policy intended to maximize cumulative return. Unlike supervised learning, RL does not require a target action for every observation. Unlike unsupervised learning, it is organized around goals and consequences. Its central difficulty is that feedback may be delayed, noisy, incomplete, and affected by the agent's own behavior.

At doctoral level, reinforcement learning should be understood not merely as a collection of algorithms but as a field connecting stochastic control, dynamic programming, statistics, optimization, game theory, causal reasoning, and decision-making under uncertainty. This chapter develops that perspective, beginning with Markov decision processes and progressing through value-based, policy-based, model-based, offline, multi-agent, and safe learning systems.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Formulate sequential decision problems as Markov decision processes and explain their assumptions.

2. Derive and interpret value functions, Bellman equations, and dynamic-programming algorithms.

3. Distinguish Monte Carlo, temporal-difference, value-based, policy-gradient, actor–critic, and model-based methods.

4. Analyze exploration, exploitation, credit assignment, distribution shift, partial observability, and non-stationarity.

5. Select suitable methods for bandits, online control, offline learning, and multi-agent environments.

6. Design reward, safety, governance, and evaluation strategies for real-world deployments.

7. Critically assess current research directions and limitations in reinforcement learning.

The Decision Process: States, Actions, and Consequences

A finite Markov decision process (MDP) is commonly represented by the tuple \(M=(S,A,P,R,\gamma)\). Here, \(S\) is the state space, \(A\) the action space, \(P(s'|s,a)\) the transition probability, \(R(s,a,s')\) the reward, and \(\gamma\in[0,1)\) the discount factor. At time \(t\), the agent observes state \(S_t\), selects action \(A_t\) according to policy \(\pi(a|s)\), receives reward \(R_{t+1}\), and transitions to \(S_{t+1}\).

The Markov property states that the conditional distribution of the future depends on the past only through the current state and action:

\[P(S_{t+1}|S_t,A_t,S_{t-1},A_{t-1},...) = P(S_{t+1}|S_t,A_t).\]

This is a modeling assumption, not a universal property of the physical world. If the observation omits relevant information, the problem is better described as a partially observable MDP (POMDP). The agent then maintains a belief state, history representation, or recurrent memory to infer hidden conditions.

The discounted return from time \(t\) is

\[G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+... .\]

Discounting represents time preference, uncertainty about distant outcomes, or a mathematical device for ensuring finite returns. In continuing tasks, average-reward formulations may be more appropriate than discounted objectives, especially where long-run rates matter more than immediate utility.

A policy specifies behavior. A deterministic policy maps states to actions, while a stochastic policy assigns probabilities. The state-value function under policy \(\pi\) is

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

and the action-value function is

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

The optimal value functions, \(V^(s)\) and \(Q^(s,a)\), correspond to the best achievable expected return. A policy is optimal if it selects actions that maximize the relevant optimal value.

Bellman Reasoning and Dynamic Programming

The key structural idea in RL is the Bellman decomposition: the value of a state equals immediate reward plus the discounted value of the next state. For a fixed policy,

\[V^\pi(s)=\sum_a\pi(a|s)\sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma V^\pi(s')].\]

The optimality equation is

\[V^(s)=\max_a\sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma V^(s')].\]

These equations support dynamic programming when the transition and reward models are known. Policy evaluation repeatedly applies the expectation under a fixed policy. Policy improvement makes the policy greedy with respect to the current value estimate. Policy iteration alternates these procedures until stability. Value iteration combines partial evaluation and improvement by repeatedly applying the optimal Bellman operator.

Dynamic programming is conceptually important because it clarifies what RL algorithms are approximating. Its practical limitation is the need to enumerate states and actions and to know the environment model. Large or continuous problems require approximation, sampling, or learning from experience.

The Bellman equation also reveals a fundamental source of difficulty: an error in estimating one state's value can propagate through future backups. Function approximation may therefore produce unstable feedback loops, particularly when bootstrapping, off-policy learning, and nonlinear approximation occur together. This combination is often called the “deadly triad.”

Learning from Experience: Monte Carlo and Temporal Differences

Monte Carlo methods estimate returns from complete episodes. After an episode ends, the observed return is used to update value estimates. They are conceptually simple and do not require a model, but they can have high variance and may be unsuitable for continuing tasks.

Temporal-difference (TD) learning updates an estimate before an episode ends. The TD(0) error is

\[\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t),\]

and a basic update is

\[V(S_t)\leftarrow V(S_t)+\alpha\delta_t.\]

TD methods trade some bias for lower variance and can learn online. Eligibility traces, such as TD(\lambda), interpolate between one-step TD and Monte Carlo learning by assigning credit across multiple preceding states.

For action values, SARSA is on-policy: it updates using the action actually selected next,

\[Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)].\]

Q-learning is off-policy and uses the greedy next action in its target:

\[Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\max_aQ(S_{t+1},a)-Q(S_t,A_t)].\]

The distinction matters. SARSA evaluates the behavior policy, including its exploration; Q-learning seeks the greedy target policy even when behavior is exploratory. In stochastic or risky environments, this can produce different safety profiles.

Exploration, Bandits, and Information Acquisition

An agent must balance exploitation of actions currently believed to be valuable with exploration of uncertain actions. In a multi-armed bandit, each action produces a reward but does not change a persistent state. Bandits isolate the exploration problem from long-horizon credit assignment.

An \(\epsilon\)-greedy strategy chooses the estimated best action with probability \(1-\epsilon\) and explores randomly with probability \(\epsilon\). Upper confidence bound methods select actions using both estimated value and uncertainty. Bayesian approaches, such as Thompson sampling, sample plausible action values from a posterior distribution. Contextual bandits incorporate observed user or environmental context while still focusing on immediate reward.

The bandit framing is useful for advertising, recommendation, clinical experimentation, and resource allocation. However, treating a sequential problem as a bandit can be dangerous when actions influence future states, user preferences, safety, or delayed outcomes. Exploration itself can cause harm, so practical systems often use constrained experimentation, safe action sets, or human approval.

Value-Based, Policy-Based, and Actor–Critic Learning

Value-based methods learn a value function and derive a policy from it, commonly by selecting the action with maximum estimated value. Deep Q-networks extend Q-learning using neural networks. Experience replay reduces temporal correlation by training on stored transitions, while target networks slow the movement of bootstrap targets. These mechanisms improve optimization but do not eliminate approximation error or distributional bias.

Policy-based methods directly optimize a parameterized policy \(\pi_\theta\). The policy-gradient identity is commonly expressed as

\[\nabla_\theta J(\theta)=E[\nabla_\theta\log\pi_\theta(A_t|S_t)G_t].\]

The identity permits optimization in continuous action spaces and naturally represents stochastic behavior. Its weakness is high gradient variance. Baselines and advantage functions reduce variance without changing the expected gradient. An advantage function is \(A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)\).

Actor–critic methods combine a policy (actor) with a value estimator (critic). The critic supplies a learned evaluation signal, often a TD error, while the actor updates the policy. Modern policy-optimization methods frequently constrain the size of policy updates to improve stability. Nevertheless, apparent training improvement may reflect reward exploitation, simulator artifacts, or overfitting to a narrow set of environments.

Model-Based Reinforcement Learning

A model-based agent learns or uses transition and reward models, then plans with them. Planning may use dynamic programming, tree search, trajectory optimization, or model-predictive control. The agent can be more sample efficient because each real transition supports many simulated planning computations.

Model error is the central risk. Small inaccuracies may compound over long imagined trajectories, leading to a policy that performs well in the learned model but poorly in reality. Short-horizon planning, uncertainty-aware ensembles, conservative model use, and frequent replanning can reduce this problem. Model-based methods are especially attractive where data collection is expensive or dangerous, such as robotics and industrial control.

A useful distinction is between epistemic uncertainty, arising from limited knowledge and potentially reducible through data, and aleatoric uncertainty, arising from inherent environmental randomness. A planner that ignores this distinction may explore unreliable regions or become excessively conservative.

Offline Reinforcement Learning and the Data-Distribution Problem

Offline RL learns from a fixed dataset of previously collected interactions without further online experimentation. This is valuable when exploration is unsafe, expensive, regulated, or impossible. Examples include historical medical records, industrial logs, customer interactions, and robotic demonstrations.

The central challenge is extrapolation error. A learned policy may select actions rarely or never represented in the dataset. The value estimator must then evaluate out-of-distribution actions using weak evidence, and bootstrap errors can be amplified. Offline methods therefore often constrain the learned policy toward the behavior policy, use conservative value estimates, or model uncertainty explicitly.

A dataset's quality is not determined only by its size. Coverage of relevant states and actions, accurate logging, consistent reward definitions, censoring mechanisms, missingness, and selection bias are crucial. Historical data may reflect earlier policies and institutional inequities. High offline return estimates are not evidence of causal improvement unless evaluation accounts for confounding and distribution shift.

Multi-Agent Sequential Decision Systems

In multi-agent environments, each agent's outcome depends on the actions of others. Cooperative systems may share a team reward; competitive systems may have opposing objectives; mixed settings combine collaboration and conflict. The environment is non-stationary from any individual agent's perspective because other agents are learning simultaneously.

Game-theoretic concepts such as Nash equilibrium, correlated equilibrium, and mechanism design help characterize strategic behavior. Centralized training with decentralized execution allows agents to use joint information during learning while acting on local observations at deployment. Communication, credit assignment, coordination, and partial observability remain major challenges.

A policy that is optimal against one population of agents may fail against another. Robust evaluation should therefore test behavioral diversity, adaptation, collusion risks, and worst-case responses rather than relying on a single fixed opponent or simulator.

Reward Design and the Problem of Specification

The reward function translates organizational or societal objectives into an optimization signal. It should represent the intended outcome, not merely a convenient proxy. Reward shaping can accelerate learning by adding informative intermediate feedback, but poorly designed shaping may alter the optimal policy or encourage loopholes. Potential-based shaping offers a principled way to preserve optimal policies under certain assumptions.

Common failures include reward hacking, where the agent maximizes the formal reward while violating the underlying intention; omission of externalities; excessive focus on short-term metrics; and unintended incentives created by aggregation. Multi-objective settings require explicit treatment of trade-offs, for example through constrained optimization, lexicographic priorities, scalarization, or Pareto analysis.

Human preferences can be incorporated through demonstrations, comparisons, feedback, or inverse reinforcement learning. Such methods do not remove normative judgment: annotator disagreement, power relationships, cultural variation, and strategic feedback must be documented and governed.

Safe Sequential Control and Governance

Safety cannot be reduced to a penalty added after training. A safe system may require hard action constraints, runtime shields, fallback controllers, formal verification of restricted properties, uncertainty thresholds, human override, and incident monitoring. Constrained MDPs represent safety through conditions such as \(E[\sum_t\gamma^t C_t]\leq d\), where \(C_t\) is a cost and \(d\) an acceptable limit.

Important questions include: Which failures are unacceptable? How is risk measured under distribution shift? Who may authorize exploration? Can the system explain an action sufficiently for audit? Are reward and performance metrics aligned with legal and professional duties? In high-impact domains, governance should include access control, versioned policies, reproducible training records, independent validation, red-team testing, privacy protection, and post-deployment monitoring.

Fairness is sequential rather than purely static. A policy can change future exposure, opportunity, health, or creditworthiness. Evaluation should therefore examine cumulative effects, subgroup trajectories, delayed harms, and feedback loops. Privacy-preserving data practices are also essential because trajectories may reveal sensitive behavior even when individual records appear anonymized.

An Illustrative Case: Warehouse Robot Fleet Control

Background

Consider a fictional logistics company operating a fleet of autonomous mobile robots in a fulfillment warehouse. Each robot transports items between storage locations and packing stations. The company seeks to reduce average order completion time while avoiding collisions, battery depletion, congestion, and unequal allocation of difficult tasks.

Situation and Problem

An initial prototype uses a reward equal to negative travel time. In simulation, it learns routes that are fast under light traffic. During pilot operation, robots cluster around popular packing stations, battery levels fall below safe thresholds, and emergency stopping increases. The problem is not simply an inadequate neural network. The objective, state representation, training distribution, and deployment constraints are all incomplete.

Analysis

The system can be modeled as a multi-agent, partially observable, constrained MDP. A robot's local sensors do not reveal the complete warehouse state, while other robots alter transition probabilities. Historical logs contain mostly conservative human-designed routes, so unrestricted offline policy optimization would evaluate many unsupported actions. Reward based only on travel time omits collision risk, congestion externalities, battery management, and fairness in workload.

Approach

The company first defines a layered objective: collision avoidance and battery safety are hard constraints; throughput and travel time are optimization objectives. A centralized simulator is calibrated against logged trajectories, with uncertainty estimates for poorly observed areas. Offline learning is restricted toward the behavior distribution, and candidate policies are evaluated in held-out traffic patterns. A model-predictive safety layer can override an unsafe action, while a learned policy selects among feasible routes.

Training uses curriculum scenarios that gradually increase traffic and introduce blocked aisles. Evaluation includes throughput, collision and near-miss rates, battery reserve violations, queue lengths, recovery after sensor failure, and performance by robot subgroup and warehouse zone. Human supervisors retain a stop function and review incidents. Deployment begins with a limited fleet and progressively expands only when safety evidence meets predefined thresholds.

Outcome

In this illustrative case, the main improvement comes from aligning the decision architecture with the operational problem rather than from selecting a more complex algorithm. Hard constraints prevent catastrophic behavior; uncertainty-aware model use reduces unsafe extrapolation; and multi-agent evaluation exposes congestion effects hidden by single-robot tests.

Learning Points

The case demonstrates five principles: sequential objectives must include future consequences; reward is not a substitute for safety engineering; offline data constrain what can be learned reliably; multi-agent interaction changes the environment; and evaluation must measure operational risk, not only average reward.

Challenges, Limitations, and Research Issues

RL performance is sensitive to reward scale, discounting, exploration schedules, random seeds, termination conventions, and hyperparameters. Reproducibility is weakened when studies report only the best run or evaluate on a narrow benchmark. Statistical uncertainty and confidence intervals should accompany performance claims.

Sample inefficiency remains a central limitation, particularly in physical systems. Simulators may be inaccurate, and sim-to-real transfer can fail because of visual, physical, or behavioral discrepancies. Partial observability can make apparently simple tasks require memory and belief-state reasoning. Long-horizon credit assignment remains difficult when rewards are sparse.

Deep RL systems can be brittle under adversarial or naturally occurring distribution shifts. Reward maximization may create undesirable strategies that are difficult to anticipate. Offline systems face confounding and coverage limits, while multi-agent systems face equilibrium selection and strategic manipulation. These limitations motivate hybrid methods combining learning with planning, demonstrations, formal constraints, causal models, and domain expertise.

Current Developments and Best Practices

Contemporary research is exploring offline-to-online adaptation, uncertainty-aware exploration, world models, hierarchical and goal-conditioned RL, preference-based learning, foundation models for decision support, and scalable multi-agent coordination. Hierarchical methods decompose long tasks into temporally extended skills; world models learn compact predictive representations; and generalist agents attempt to transfer policies across tasks.

Responsible practice should follow a disciplined sequence:

• Define the decision, stakeholders, horizon, constraints, and failure costs before choosing an algorithm.
• Establish simple baselines, including rules, optimization methods, and human or historical policies.
• Verify state and action semantics, logging quality, reward definitions, and termination conditions.
• Separate training, validation, stress testing, and deployment evaluation.
• Measure return together with safety, fairness, robustness, calibration, sample efficiency, and operational cost.
• Use conservative exploration and human oversight when real-world consequences are material.
• Monitor policy drift, data drift, incidents, and changes in the surrounding population after deployment.

Chapter Summary

Reinforcement learning addresses sequential decisions in which actions alter future states and rewards. Markov decision processes formalize this setting through states, actions, transitions, rewards, and discounting. Bellman equations provide the foundation for dynamic programming and motivate value estimation, temporal-difference learning, and policy optimization. Monte Carlo and TD methods differ in when they use observed returns; SARSA and Q-learning differ in their treatment of behavior and target policies.

Bandits isolate exploration, while model-based methods exploit learned or known dynamics for planning. Value-based, policy-based, and actor–critic methods offer different trade-offs in action spaces, variance, stability, and sample efficiency. Offline RL addresses settings where online experimentation is unsafe but must manage distribution shift and extrapolation error. Multi-agent systems introduce strategic interaction and non-stationarity. Reward design, safety constraints, uncertainty, governance, and evaluation are as important as algorithm selection. Effective sequential decision systems therefore combine statistical learning with control theory, domain knowledge, monitoring, and institutional accountability.

Key Terms

Markov Decision Process: A formal model of sequential decision-making with states, actions, transitions, rewards, and a discount factor.

Policy: A rule, possibly stochastic, specifying actions given states or observations.

Return: The cumulative, usually discounted, reward from a time step onward.

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 relationship expressing value as immediate reward plus future value.

Dynamic Programming: Planning by repeatedly applying known transition and reward models.

Temporal-Difference Learning: Learning from the discrepancy between successive value predictions.

TD Error: The difference between a bootstrapped target and the current value estimate.

On-Policy Learning: Learning about the same policy used to generate behavior.

Off-Policy Learning: Learning a target policy from data generated by another policy.

Exploration–Exploitation Trade-off: The conflict between trying uncertain actions and using actions believed to be best.

Contextual Bandit: A bandit problem in which action choice depends on observed context.

Policy Gradient: An optimization method that directly adjusts parameters of a policy.

Actor–Critic: An architecture combining a policy learner with a value estimator.

Model-Based Reinforcement Learning: RL that uses a transition or reward model for prediction and planning.

Offline Reinforcement Learning: Learning a policy exclusively from a fixed interaction dataset.

Constrained MDP: An MDP that includes limits on cumulative costs or risks.

Reward Hacking: Achieving the specified reward through behavior that violates the intended objective.

Partial Observability: A condition in which observations do not fully reveal the underlying state.

Review Questions

Short Answer Questions

1. What is the Markov property, and why can it fail in practical systems?

2. Distinguish a state-value function from an action-value function.

3. How does Q-learning differ from SARSA?

4. What is the purpose of experience replay in deep value-based learning?

5. Why is offline reinforcement learning vulnerable to extrapolation error?

Long Answer Questions

1. Explain the Bellman optimality equation and show how it supports value iteration and policy iteration.

2. Compare Monte Carlo, temporal-difference, and policy-gradient methods in terms of targets, variance, and applicability.

3. Discuss the exploration–exploitation problem using epsilon-greedy, confidence-bound, and Bayesian approaches.

4. Analyze the principal challenges of applying reinforcement learning to multi-agent environments.

5. Explain how reward design, constrained MDPs, runtime safeguards, and governance contribute to safe sequential control.

Analytical / Application Questions

1. A hospital has historical treatment records but cannot safely experiment with new treatment policies. Formulate the problem as offline RL and identify the dataset, distribution-shift, ethical, and evaluation issues that must be addressed.

2. Design an evaluation framework for an autonomous warehouse robot policy. Specify performance, safety, robustness, fairness, and deployment-monitoring measures.

3. An agent achieves high training reward but causes congestion and battery failures after deployment. Diagnose possible failures in state representation, reward design, model generalization, and multi-agent evaluation, and propose corrective actions.

22. Multiple Choice Questions with Answers

Question 1

Which expression best represents the Markov property in an MDP?

A. The next state depends only on the complete history of rewards.

B. The future distribution depends on the current state and action, not additional past history.

C. The reward must be identical for every action.

D. The policy must always be deterministic.

Correct Answer: B. The future distribution depends on the current state and action, not additional past history.

Question 2

What is the principal distinction between SARSA and Q-learning?

A. SARSA requires a known transition model, whereas Q-learning does not.

B. SARSA uses a Monte Carlo target, whereas Q-learning uses no target.

C. SARSA uses the next action actually taken, whereas Q-learning uses the greedy target action.

D. SARSA applies only to continuous actions, whereas Q-learning applies only to discrete states.

Correct Answer: C. SARSA uses the next action actually taken, whereas Q-learning uses the greedy target action.

Question 3

Why can offline reinforcement learning suffer from extrapolation error?

A. The dataset contains too many rewards.

B. The learned policy may select actions insufficiently represented in the dataset.

C. Offline methods cannot use value functions.

D. The environment becomes more stochastic when data are stored.

Correct Answer: B. The learned policy may select actions insufficiently represented in the dataset.

Question 4

A bandit formulation is inappropriate when an action primarily matters because it changes future states and long-term opportunities. Which issue does this illustrate?

A. Bandits do not model persistent state transitions.

B. Bandits cannot represent immediate rewards.

C. Bandits always require a transition model.

D. Bandits prohibit stochastic policies.

Correct Answer: A. Bandits do not model persistent state transitions.

Question 5

Which combination is associated with the deadly triad in value-function learning?

A. Planning, imitation, and Bayesian inference

B. Bootstrapping, off-policy learning, and function approximation

C. Reward shaping, exploration, and eligibility traces

D. Partial observability, communication, and game theory

Correct Answer: B. Bootstrapping, off-policy learning, and function approximation

Question 6

What is a major advantage of model-based reinforcement learning?

A. It guarantees a perfect model of the environment.

B. It can improve sample efficiency by planning with a learned or known model.

C. It eliminates all distribution shift.

D. It requires no reward definition.

Correct Answer: B. It can improve sample efficiency by planning with a learned or known model.

Question 7

Which reward-design failure occurs when an agent maximizes a formal proxy while violating the intended objective?

A. Policy evaluation

B. Reward hacking

C. Eligibility tracing

D. Belief-state filtering

Correct Answer: B. Reward hacking

Question 8

In a constrained MDP, a constraint such as expected cumulative cost being below a threshold primarily represents what?

A. A safety or resource limit in addition to reward maximization

B. A requirement that all policies be deterministic

C. A guarantee that the environment is fully observable

D. A replacement for the transition model

Correct Answer: A. A safety or resource limit in addition to reward maximization

Question 9

Why is a multi-agent environment often non-stationary from one agent's perspective?

A. The reward function is necessarily constant.

B. Other agents change their policies while the focal agent learns.

C. All agents observe exactly the same state.

D. The environment contains no actions.

Correct Answer: B. Other agents change their policies while the focal agent learns.

Question 10

A warehouse robot policy performs well in simulation but violates battery constraints in deployment. Which response is most consistent with safe sequential control?

A. Increase the discount factor without further evaluation.

B. Remove battery information from the state.

C. Add hard safety constraints, uncertainty testing, runtime safeguards, and staged deployment.

D. Evaluate only average reward because safety is not an optimization metric.

Correct Answer: C. Add hard safety constraints, uncertainty testing, runtime safeguards, and staged deployment.