Reinforcement Learning and Sequential Decision-Making

Introduction and Context

Reinforcement learning (RL) studies how an agent learns to make decisions through interaction with an environment. At each time step, the agent observes a situation, selects an action, receives a reward, and moves to a new situation. Unlike supervised learning, the correct action is usually not supplied. The agent must discover a strategy that maximizes long-term performance.

RL is therefore particularly suitable for sequential decision problems in which:

• actions influence both immediate rewards and future opportunities;
• information may be incomplete or noisy;
• decisions must balance exploration and exploitation; and
• performance depends on a sequence of actions rather than one prediction.

Applications include robotics, recommender systems, industrial control, traffic management, energy optimization, healthcare planning, finance, and resource allocation. However, an RL system can make costly or unsafe decisions during learning. Consequently, practical RL requires not only algorithms but also careful reward design, simulation, monitoring, constraints, and human governance.

Learning Objectives

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

1. formulate a sequential decision problem as a Markov decision process;
2. distinguish policies, value functions, rewards, returns, and transition dynamics;
3. derive and apply Bellman expectation and optimality equations;
4. explain value-based, policy-based, and actor–critic methods;
5. compare exploration strategies and identify their limitations;
6. design rewards while avoiding proxy failure and reward hacking;
7. evaluate RL systems using statistically meaningful and operationally relevant measures; and
8. incorporate safety, constraints, uncertainty, and deployment requirements.

1. Sequential Decision-Making and the Markov Property

A sequential decision problem consists of repeated decisions whose consequences extend into the future. A delivery vehicle, for example, may choose a route that saves time now but creates congestion later. A production controller may increase output immediately while increasing the probability of equipment failure.

The Markov property states that the current state contains all information needed to predict the distribution of the next state and reward, given the current action. Formally:

Here, S_t is the state at time t, A_t is the action, S_t+1 is the next state, and R_t+1 is the reward received after acting. The equation is a modelling assumption, not a claim that real environments are always perfectly Markovian. If relevant information is hidden, the agent may need a history, belief state, recurrent model, or partially observable formulation.

A state should be sufficiently informative without being unnecessarily large. Including too little information causes ambiguity; including irrelevant detail increases computational and statistical difficulty.

2. The Markov Decision Process

A finite Markov decision process (MDP) is commonly represented by the tuple:

where:

For episodic tasks, an episode terminates at a terminal state. The discount factor expresses how strongly future rewards are valued. If rewards are measured in utility points, discounted returns remain in utility points; γ is dimensionless.

A policy specifies how actions are selected. A stochastic policy is:

A deterministic policy is written a = π(s). The objective is to find a policy maximizing expected return. The return from time t is:

For a finite episode ending after T steps:

The sum assumes rewards are bounded or otherwise well behaved. For infinite-horizon tasks, γ < 1 commonly ensures convergence when rewards are bounded.

3. Value Functions and Bellman Equations

The state-value function under policy π is:

The action-value function is:

The state value measures the expected long-term return from a state when following π. The action value measures the expected return after selecting action a and then following π.

The Bellman expectation equation decomposes a value into immediate reward and discounted future value:

For deterministic transitions and a deterministic immediate reward, this simplifies to:

The optimal value function is:

Its Bellman optimality equation is:

Similarly:

These equations are foundational: dynamic programming, temporal-difference learning, Q-learning, and many deep RL algorithms are different ways of approximating or solving them.

Worked Example: Discounted Return

Suppose an agent receives rewards 5, 10, and 20 over three future steps, with γ = 0.8. The return is:

The third reward contributes less because it is further in the future. A larger discount factor would make delayed outcomes more important.

4. Dynamic Programming and Value-Based Learning

When the full transition model is known, policy evaluation estimates V^π, while policy improvement chooses actions that appear better according to current values. Repeated alternation is called policy iteration. Value iteration instead repeatedly applies the Bellman optimality backup:

For finite discounted MDPs, the Bellman optimality operator is a contraction under the maximum norm, supporting convergence to the unique optimal value function under standard bounded-reward assumptions.

In model-free learning, the agent does not require P or R in advance. Temporal-difference (TD) learning updates an estimate using the difference between a target and a current estimate. The general TD error is:

A one-step state-value update is:

where α is a learning rate, normally satisfying 0 < α ≤ 1. The update is online and bootstraps from an estimate of the next state.

SARSA

SARSA is an on-policy action-value method. Its update is:

It learns the value of the policy actually being followed, including its exploration behaviour.

Q-Learning

Q-learning is traditionally off-policy. Its target uses the best estimated next action, even if the behaviour policy explores:

The distinction matters. SARSA may learn a safer policy when exploratory actions carry risk, whereas Q-learning targets the greedy policy represented by its current estimates.

Function Approximation and Deep Q-Networks

Tabular methods become impractical when states are numerous or continuous. Function approximation represents Q(s,a) using parameters θ, often a neural network. A deep Q-network (DQN) commonly uses:

• a replay buffer containing past transitions;
• random minibatches to reduce temporal correlation;
• a target network updated less frequently to stabilize targets; and
• an exploration policy such as ε-greedy.

The squared temporal-difference loss for a sampled transition is often:

where, for a terminal transition, y = r, and otherwise y = r + γ max_a'Q(s',a';θ⁻). The symbol θ⁻ denotes target-network parameters. This loss is an engineering objective, not a guarantee that the learned policy is optimal.

5. Policy-Based and Actor–Critic Methods

Value methods select actions indirectly through estimated values. Policy-based methods parameterize the policy directly as π_θ(a|s). They are useful for continuous actions, stochastic policies, and objectives that cannot be represented conveniently by a maximum over discrete actions.

The policy-gradient identity, under standard differentiability and regularity assumptions, is:

Here, J(θ) is expected performance and θ contains policy parameters. The update increases the probability of actions associated with high returns. Monte Carlo estimates can have high variance.

A baseline that does not depend on the selected action can reduce variance without changing the expected gradient. Using a state-value baseline gives the advantage estimate:

The actor updates the policy, while the critic estimates value. A one-step advantage estimate is often:

where w are critic parameters. The actor may use Â_t in its gradient estimate, and the critic minimizes a value-estimation error. This division of labour produces the actor–critic architecture.

Modern methods such as proximal policy optimization (PPO), soft actor–critic (SAC), and deterministic policy-gradient algorithms improve sample efficiency or stability in particular settings. Their practical success depends on normalization, clipping or entropy regularization, network architecture, batch construction, and careful hyperparameter selection. No algorithm is universally best.

6. Exploration and Exploitation

Exploitation selects actions currently believed to be good. Exploration gathers information about uncertain actions. Excessive exploitation can lock an agent into a poor policy; excessive exploration can waste resources or cause unsafe behaviour.

Common strategies include:

An exploration schedule may reduce ε over time, but the schedule should reflect changing risk and learning needs. In safety-critical environments, exploration should occur primarily in simulation, through constrained actions, or under human supervision.

7. Reward Design and the Specification Problem

The reward function is a formal specification of what the agent optimizes. It is not automatically identical to the organization’s real objective. A reward such as “maximize clicks” can encourage sensational content; “minimize waiting time” can disadvantage vulnerable users if fairness is omitted.

A shaped reward may combine objectives:

The weights w₁,w₂,w₃ must be dimensionally and operationally meaningful. If component rewards have different scales, normalization may be necessary. However, arbitrary weighting can conceal value judgments and create undesirable trade-offs.

Potential failures include:

• reward hacking, in which the agent exploits a loophole;
• side effects, where achieving the target damages other objectives;
• sparse rewards, which make credit assignment difficult;
• misspecified proxies, where a measurable indicator diverges from the true goal; and
• distributional shift, where a reward works in training but fails after deployment.

Good practice includes testing adversarial and unusual behaviours, reviewing rewards with domain experts, logging reward components separately, and evaluating outcomes with independent safety and fairness measures.

8. Constraints, Safety, and Governance

An unconstrained expected-return objective is unsuitable when violations have severe consequences. A constrained formulation can be written:

Here, J_R is expected reward, J_Ci is expected cumulative cost for constraint i, and d_i is an acceptable limit. Costs may represent collision probability, energy use, privacy exposure, financial loss, or regulatory risk.

Practical safeguards include:

1. action masking to remove invalid actions;
2. safety layers or control-barrier mechanisms that override unsafe commands;
3. conservative policies that penalize uncertainty;
4. offline training from approved historical data;
5. simulation and digital-twin testing;
6. human approval for high-impact actions;
7. emergency shutdown and rollback procedures; and
8. continuous monitoring after deployment.

Governance should address accountability, data provenance, privacy, discrimination, auditability, cybersecurity, and the authority to stop the system. A reward constraint does not replace legal compliance or professional responsibility.

9. Evaluation and Operational Deployment

Average episode return is useful but insufficient. Evaluation should include:

• mean and distribution of return;
• success rate and constraint-violation rate;
• worst-case or tail outcomes;
• sample efficiency;
• robustness to changed conditions;
• calibration of uncertainty;
• fairness across relevant groups; and
• latency, cost, energy use, and system availability.

Results should be reported across multiple random seeds and, where possible, confidence intervals or uncertainty estimates. Comparing two agents on one training run is not reliable evidence of superiority.

Deployment commonly follows a staged path: offline analysis, simulation, shadow mode, restricted pilot, monitored release, and periodic review. The policy version, training data, reward definition, environment version, and safety overrides should be recorded for reproducibility.

10. Illustrative Case: Warehouse Robot Routing

Background

Consider a fictional warehouse in which autonomous robots deliver inventory bins to human pickers. The robot must choose movements at intersections while avoiding collisions and reducing delivery time.

Problem

A reward based only on speed causes robots to pass too close to people and to block narrow aisles. A reward based only on safety produces excessively cautious behaviour and poor throughput.

Analysis

The state may include robot position, velocity, local obstacle map, destination, aisle occupancy, and uncertainty about moving pedestrians. The action may be a discrete movement command or a continuous velocity vector. Because pedestrian intentions are only partly observable, a simple MDP may be inadequate; a belief state or recurrent policy may be required.

The team defines a primary service reward, energy and delay costs, and a severe collision cost. Hard action constraints prohibit entering occupied safety zones. Training occurs in a randomized simulator with varied layouts and pedestrian patterns. The learned policy is first evaluated in simulation, then in shadow mode, where it proposes actions but does not control robots.

Approach and Solution

A constrained actor–critic policy is used for continuous velocity commands. A safety supervisor checks each proposed command and replaces it with a verified safe action when necessary. Exploration is limited to simulation and low-speed pilot trials. Metrics include delivery time, near-miss rate, emergency stops, energy use, and performance across warehouse layouts.

Outcome

In this illustrative scenario, the pilot is approved only after the policy meets a predefined near-miss threshold and maintains acceptable throughput. Logs record the proposed action, supervisor intervention, observed state, and outcome. Human operators retain authority to pause all robots.

Learning Points

The case demonstrates that RL is a socio-technical system rather than merely a neural network. State representation, reward design, uncertainty, hard constraints, evaluation, and operational authority are all essential.

11. Challenges and Contemporary Directions

RL remains difficult because data can be expensive, feedback can be delayed, environments can change, and small modelling errors can produce large long-term consequences. Deep networks may be unstable, overestimate values, or fail outside the training distribution. Offline RL can reduce dangerous exploration but must handle distributional mismatch: actions rarely represented in the dataset may receive unreliable value estimates.

Current research directions include offline and batch RL, multi-agent learning, hierarchical policies, world models, risk-sensitive and distributional RL, preference-based reward learning, safe exploration, and foundation-model agents. These developments do not eliminate the need for domain knowledge. In high-impact systems, interpretability, uncertainty, verification, and institutional controls remain as important as raw benchmark performance.

Best-Practice Checklist

Before deploying an RL system, ask:

• Is the state sufficiently Markovian for the intended decision?
• Are reward components explicit, scaled, and reviewed by domain experts?
• What behaviours would count as reward hacking?
• Where can exploration occur safely?
• Which constraints are hard rather than merely penalized?
• Has performance been tested under distribution shift and adversarial conditions?
• Are human override, logging, rollback, and incident procedures available?
• Are fairness, privacy, security, and regulatory obligations addressed?
• Are results reproducible across seeds, scenarios, and policy versions?

Chapter Summary

Reinforcement learning formulates decision-making as repeated interaction between an agent and an environment. The MDP provides the central mathematical framework through states, actions, transition probabilities, rewards, and discounting. Policies specify behaviour; value functions estimate expected long-term return; and Bellman equations express the recursive structure of sequential decisions.

Value-based methods such as SARSA and Q-learning learn action values, while policy-gradient methods optimize policies directly. Actor–critic methods combine these approaches by using a critic to estimate values or advantages for an updating actor. Exploration is necessary for learning but must be controlled when actions have operational consequences.

Reward design is a specification problem. Poorly chosen proxies can produce reward hacking, unsafe side effects, and unfair outcomes. Constrained optimization, safety supervisors, simulation, human oversight, monitoring, and rigorous evaluation are therefore essential. Effective RL deployment requires alignment between mathematical objectives, engineering constraints, organizational goals, and public responsibility.

Key Terms

Markov property: The assumption that the current state contains sufficient information for predicting future transitions and rewards.

Markov decision process: A formal model consisting of states, actions, transitions, rewards, and discounting.

State: A representation of the situation relevant to decision-making.

Action: A choice made by the agent.

Policy: A rule or probability distribution for selecting actions.

Reward: Immediate feedback following an action or transition.

Return: Discounted cumulative future reward.

Discount factor: A parameter controlling the importance of future rewards.

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

Action-value function: Expected return from a state–action pair.

Bellman equation: A recursive relationship expressing value through immediate and future value.

Temporal-difference learning: Learning from the difference between successive predictions.

Q-learning: An off-policy method that targets the greedy next action.

SARSA: An on-policy method using the action actually selected next.

Policy gradient: A method that directly optimizes policy parameters.

Actor–critic: An architecture with a policy-learning actor and value-estimating critic.

Exploration: Trying actions to obtain information.

Exploitation: Choosing actions currently believed to be effective.

Reward hacking: Achieving a formal reward through unintended or harmful behaviour.

Safe RL: Reinforcement learning that explicitly manages constraints, risk, and operational safety.

Review Questions

Short Answer Questions

1. What is the Markov property, and why is it important in an MDP?
2. Distinguish a policy from a value function.
3. What is the purpose of the discount factor?
4. How does Q-learning differ from SARSA?
5. Define reward hacking and give one example.

Long Answer Questions

1. Explain the components of an MDP and derive the Bellman expectation equation.
2. Compare value-based, policy-based, and actor–critic methods, including suitable applications for each.
3. Discuss exploration–exploitation trade-offs and explain why random exploration may be inappropriate in safety-critical systems.
4. Explain how reward misspecification can cause unintended behaviour and propose a systematic reward-design process.
5. Describe a responsible deployment lifecycle for an RL system used in an operational environment.

Analytical / Application Questions

1. An agent receives rewards 4, 6, and 10 with γ = 0.9. Calculate its discounted return and explain how the result changes if γ = 0.5.
2. Design an MDP for elevator dispatching. Specify states, actions, rewards, at least one constraint, and one likely source of partial observability.
3. A robot policy achieves high average reward but occasionally causes severe collisions. Explain why average return is inadequate and recommend an evaluation and safety strategy.

Multiple Choice Questions with Answers

Question 1

Which condition is represented by the Markov property?

A. The next state depends only on the complete history

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

C. All actions have identical rewards

D. The environment is always deterministic

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

Question 2

What does the discount factor primarily control?

A. The number of available actions

B. The size of the state space

C. The relative importance of future rewards

D. The learning-rate schedule

Correct Answer: C. The relative importance of future rewards

Question 3

Which method is traditionally off-policy?

A. SARSA

B. Monte Carlo policy evaluation

C. Q-learning

D. Behaviour cloning

Correct Answer: C. Q-learning

Question 4

For rewards 5 and 10 with discount factor 0.8, what is the two-step return?

A. 8.0

B. 13.0

C. 13.8

D. 15.0

Correct Answer: C. 13.8

Question 5

What is the principal role of the critic in an actor–critic method?

A. To encode raw sensor data only

B. To estimate values or advantages that guide policy updates

C. To remove all exploration

D. To define the legal constraints of a system

Correct Answer: B. To estimate values or advantages that guide policy updates

Question 6

Which strategy selects a random action with probability ε and a greedy action otherwise?

A. ε-greedy exploration

B. Policy evaluation

C. Action masking

D. Reward normalization

Correct Answer: A. ε-greedy exploration

Question 7

Why can reward hacking occur?

A. The agent ignores all numerical feedback

B. The formal reward is only an imperfect proxy for the intended objective

C. The discount factor is always zero

D. The state space contains no terminal states

Correct Answer: B. The formal reward is only an imperfect proxy for the intended objective

Question 8

Which formulation explicitly represents a performance objective subject to cost limits?

A. Unconstrained supervised learning

B. Constrained reinforcement learning

C. Random search without feedback

D. Nearest-neighbour classification

Correct Answer: B. Constrained reinforcement learning

Question 9

Why are replay buffers used in deep Q-learning?

A. To guarantee optimality

B. To store and randomly sample past transitions for training

C. To eliminate the need for rewards

D. To make every environment deterministic

Correct Answer: B. To store and randomly sample past transitions for training

Question 10

Which evaluation measure is especially important when rare failures are severe?

A. Only average training loss

B. Only the number of neural-network layers

C. Constraint-violation and tail-risk measures

D. The initial random seed alone

Correct Answer: C. Constraint-violation and tail-risk measures