Reinforcement Learning and Sequential Decision-Making

Introduction

Many machine-learning problems involve a fixed dataset in which examples are treated as independent observations. Reinforcement learning (RL) addresses a different class of problem: an agent repeatedly interacts with an environment, chooses actions, receives rewards, and learns a strategy for making better decisions over time. The consequences of an action may be delayed, uncertain, and dependent on later decisions.

RL therefore provides a formal language for problems such as robot control, inventory management, recommendation, dynamic pricing, energy storage, autonomous navigation, network routing, and adaptive resource allocation. Its central challenge is not merely predicting an outcome, but learning which action should be taken now when the value of that action depends on future states and future choices.

This chapter develops the foundations of sequential decision-making, beginning with Markov decision processes (MDPs). It then explains policies, returns, value functions, Bellman equations, dynamic programming, Monte Carlo estimation, temporal-difference learning, Q-learning, SARSA, policy-gradient methods, exploration, reward design, simulation, and operational deployment.

Learning Objectives

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

1. Formulate a sequential decision problem as a Markov decision process.
2. Distinguish states, actions, rewards, transitions, policies, returns, and value functions.
3. Derive and interpret Bellman expectation and optimality equations.
4. Explain dynamic programming, Monte Carlo learning, and temporal-difference learning.
5. Compare Q-learning, SARSA, actor–critic, and policy-gradient approaches.
6. Analyse exploration, reward specification, off-policy learning, and sample efficiency.
7. Design a simulation-based RL workflow and evaluate operational risks.
8. Assess ethical, safety, governance, and deployment considerations.

1. Sequential Decision-Making as an MDP

A finite Markov decision process is commonly represented by the tuple (S, A, P, R, γ), where:

• S is the set of states;
• A is the set of actions;
• P(s'|s,a) is the transition probability of reaching state s' after taking action a in state s;
• R(s,a,s') is the immediate reward; and
• γ ∈ [0,1) is the discount factor.

The Markov property states that, conditional on the current state and action, the future does not depend on the full history:

This property is a modelling assumption, not a universal fact. If the current observation omits relevant information—for example, the velocity of a vehicle or the hidden health condition of a machine—the observed process may not be Markov. Such problems may require state augmentation, recurrent models, or a partially observable MDP.

At time t, the agent observes state S_t, selects action A_t, receives reward R_t+1, and transitions to S_t+1. A policy specifies how actions are selected. A stochastic policy is written π(a|s), where π(a|s) = P(A_t=a|S_t=s). A deterministic policy is written a = π(s).

The episode may terminate at a terminal state, such as a completed delivery or failed mission. In continuing tasks, discounting is especially useful because it makes the infinite-horizon return finite under bounded rewards. The discount factor expresses both mathematical preference for earlier rewards and, in some applications, economic time preference.

2. Returns and Value Functions

The discounted return from time t is

Here G_t is the cumulative future reward, R_t+k+1 is the reward received k+1 steps after time t, and γ is the discount factor. For an episodic task, the sum ends at termination. If rewards are bounded by |R_t| ≤ R_max and γ<1, then the absolute return is bounded by R_max/(1−γ).

The state-value function for policy π is

It measures the expected return from state s when the agent follows π. The action-value function is

It measures the expected return after taking action a initially and subsequently following π. The optimal value functions are

and

They satisfy the relationship

Value functions are not probabilities and need not lie between zero and one. Their units are reward units, although discounting may give rewards received at different times unequal effective weight.

3. Bellman Equations

The return can be decomposed into its first reward and the remaining return:

Taking conditional expectations gives the Bellman expectation equation for a fixed policy:

For continuous state or reward spaces, sums are replaced by integrals or expectations. The corresponding action-value equation is

The Bellman optimality equation is

and its action-value form is

These equations assume an MDP model and an additive discounted reward objective. They are central because they express a long-horizon decision problem recursively: the value of a choice equals its immediate reward plus the discounted value of the next state.

Worked example: one-step value calculation

Suppose an action from state s leads to state s₁ with probability 0.7 and to s₂ with probability 0.3. The immediate reward is 4 in either case, V(s₁)=10, V(s₂)=2, and γ=0.9. The expected backed-up value is

4 + 0.9(0.7×10 + 0.3×2) = 4 + 0.9(7.6) = 10.84.

This is the value estimate for that action under the stated successor values. It is not necessarily the globally optimal value unless the successor values and action choice satisfy the optimality conditions.

4. Planning and Learning Methods

Dynamic programming

If P and R are known, dynamic programming can compute values through iterative updates. Value iteration uses

Under standard finite-MDP conditions and γ<1, repeated application converges to V* from bounded initial values. A greedy policy is then selected using the maximizing action. Policy iteration alternates policy evaluation with policy improvement. Dynamic programming can be computationally expensive when the state space is large, but it provides an important theoretical benchmark.

Monte Carlo methods

Monte Carlo (MC) methods estimate values from complete episodes. If an occurrence of state s is followed by return G_t, the value estimate can be updated by

where α∈(0,1] is a learning rate. MC methods do not require a transition model and use actual returns, but they must generally wait until the episode ends. They can therefore have high variance and may be unsuitable for very long or continuing tasks.

Temporal-difference learning

Temporal-difference (TD) learning combines sampling with bootstrapping. The TD(0) target and error are

with update

For a terminal next state, the continuation term is conventionally set to zero. TD learning updates after each transition, usually has lower variance than MC estimation, and can learn before an episode terminates. It is biased because its target uses an estimated value, but often has favourable practical speed.

The distinction can be summarized as follows:

5. Q-Learning and SARSA

For discrete actions, a tabular action-value method can learn directly which actions are useful. Q-learning uses the target

and update

The terminal-state continuation term is zero. Q-learning is off-policy: the behaviour policy may explore, while the target evaluates the greedy action in the next state. Under finite-state, finite-action conditions, sufficient exploration, suitable learning-rate conditions, and a stationary environment, tabular Q-learning has strong convergence results. Function approximation, non-stationarity, partial observability, and inadequate exploration weaken these guarantees.

SARSA updates using the action actually selected next:

SARSA is on-policy because its target reflects the behaviour policy. This distinction can matter in risky environments. If exploratory actions may lead to severe penalties, SARSA may learn a safer policy than Q-learning because it accounts for the consequences of continued exploration.

Worked Q-learning update

Assume Q(s,a)=5, reward r=2, γ=0.8, and the next-state action values are 6 and 3. With α=0.25, the target is 2+0.8×6=6.8. Therefore,

Q_new = 5 + 0.25(6.8−5) = 5.45.

The update moves the estimate toward the greedy one-step target; it does not replace the estimate completely unless α=1.

6. Exploration and Exploitation

An agent must exploit actions currently believed to be valuable while exploring actions whose value is uncertain. Pure exploitation can lock the agent into a poor policy; unrestricted exploration can be costly or unsafe.

A common strategy is ε-greedy action selection. With probability 1−ε, the agent selects a greedy action; with probability ε, it selects an exploratory action, often uniformly among available actions. Ties among greedy actions should be handled consistently, preferably with random tie-breaking to avoid artificial bias.

Other approaches include:

• Decaying ε: exploration decreases as learning progresses, although it should not disappear prematurely when uncertainty remains.
• Softmax selection: actions are sampled according to probabilities proportional to exp(Q(s,a)/τ), where temperature τ>0 controls randomness.
• Upper-confidence methods: estimated value is augmented by an uncertainty bonus.
• Optimistic initialization: initially high values encourage trying actions.
• Count-based or posterior exploration: actions or states with greater uncertainty receive priority.
• Safe exploration: constraints, risk limits, human approval, or a trusted baseline restrict dangerous actions.

Exploration must be evaluated against operational cost. In an online advertising system, a poor exploratory recommendation may reduce engagement; in a chemical plant, it may create a safety hazard. Exploration in simulation does not automatically make real-world exploration safe because the simulator may omit rare failures or distribution shifts.

7. Policy-Gradient and Actor–Critic Methods

Value-based methods are convenient for small discrete action sets. For continuous actions or highly structured policies, direct policy optimization is often more appropriate. Let π_θ(a|s) be a differentiable policy parameterized by θ. The objective is

where τ denotes a trajectory generated by the policy. The policy-gradient theorem gives, under standard regularity conditions,

A policy-gradient update is approximately

where β is a policy learning rate and Â_t is an estimate of the action advantage or return. Subtracting a state-dependent baseline from the return can reduce variance without changing the expected gradient when the baseline does not depend on the action.

Actor–critic methods maintain an actor, representing the policy, and a critic, estimating a value function. A common advantage estimate is

The critic supplies a lower-variance learning signal to the actor. Modern deep RL systems often combine neural networks, replay buffers, target networks, entropy regularization, and carefully designed stabilisation methods. These techniques can solve complex tasks but introduce sensitivity to architecture, data distribution, random seeds, reward scaling, and hyperparameters.

8. Reward Design and Objective Specification

The reward function operationalizes what the system is encouraged to do. It is therefore a specification of an objective, not merely a technical detail. Poor reward design can produce reward hacking: behaviour that maximizes the numerical reward while violating the intended purpose.

A reward should be:

• aligned with the actual organizational or social objective;
• measurable with acceptable latency and noise;
• resistant to manipulation;
• explicit about safety, fairness, and constraints; and
• tested against foreseeable unintended strategies.

Reward shaping can accelerate learning by adding informative intermediate feedback. Potential-based shaping has a useful policy-preservation property. If Φ(s) is a potential function, define

and add F to the original reward. Under the usual discounted-MDP assumptions and consistent terminal treatment, this form preserves the optimal policy while changing learning signals. Arbitrary reward shaping does not have this guarantee.

In safety-critical systems, constraints should not be hidden solely inside a weighted reward. A constrained formulation may maximize expected return subject to a cost limit:

where J_R is expected task reward, J_C is expected safety cost, and d is an acceptable limit. Multi-objective problems require explicit discussion of trade-offs rather than assuming that one scalar reward captures every stakeholder value.

9. Simulation, Evaluation, and Deployment

Simulation is often essential because real-world data collection may be slow, expensive, or dangerous. A credible simulation workflow includes:

1. defining the state, action, transition, reward, and termination rules;
2. validating the simulator against historical or experimental data;
3. modelling uncertainty, delays, constraints, and rare events;
4. training under multiple seeds and scenarios;
5. testing on held-out conditions and stress cases; and
6. transferring cautiously through monitoring and staged deployment.

Offline RL learns from previously collected trajectories without freely interacting with the environment. It is useful when online experimentation is unsafe, but it faces distribution shift: the learned policy may select actions poorly represented in the dataset. Conservative methods, uncertainty estimation, behaviour constraints, and rigorous off-policy evaluation are therefore important.

Evaluation should not rely solely on mean episode return. Relevant measures may include:

• cumulative reward and discounted return;
• success rate and completion time;
• variance and lower-tail performance;
• constraint violations and near misses;
• robustness under changed conditions;
• sample efficiency and computational cost;
• fairness across users or subpopulations; and
• comparison with a strong baseline or existing operational policy.

For stochastic policies, confidence intervals and repeated trials are preferable to reporting a single run. A policy that has a slightly lower mean reward but far fewer catastrophic outcomes may be preferable in practice.

10. Applied Case: Warehouse Robot Replenishment

The following is an illustrative case, not a report of a particular company.

Background and problem

A warehouse operates mobile robots that transport inventory from storage locations to picking stations. The system must decide which request to serve next and which route to follow. Delays reduce throughput, while congestion and battery depletion create operational failures.

MDP formulation

A state may contain robot location, battery level, outstanding requests, aisle congestion, time of day, and station queues. Actions may include selecting a request, moving to an adjacent location, waiting, or visiting a charging station. The transition model captures travel time, congestion, battery consumption, and stochastic equipment events.

A possible reward is a throughput benefit minus delay, energy, congestion, and safety costs. However, a single weighted reward can create undesirable behaviour—for example, aggressively pursuing throughput while approaching unsafe battery levels. A safer design adds explicit action constraints, such as prohibiting dispatch when predicted battery reserve is below a validated threshold.

Approach

The team first builds a discrete-event simulator calibrated with historical travel times and queue data. A heuristic dispatch policy provides a baseline. A constrained actor–critic agent is trained in simulation using randomized demand, blocked-aisle events, and sensor noise. Training uses several random seeds and evaluates both average throughput and worst-case congestion.

Before deployment, the learned policy operates in shadow mode: it recommends actions while the existing system remains in control. Recommendations are reviewed for constraint violations, unexpected routing patterns, and performance under peak demand. A staged rollout then limits the number of robots controlled by the policy. A rule-based fallback remains available, and intervention logs are retained for audit.

Outcome and interpretation

Suppose simulation shows a 9% improvement in throughput and a 14% reduction in average delay, but a small increase in energy consumption. The result is not automatically a success. Managers must compare the improvement with electricity cost, battery replacement, safety margins, service-level commitments, and failure-tail behaviour. If gains disappear under unseen congestion patterns, the policy is not robust enough for unrestricted deployment.

Learning points

The case illustrates that RL is a socio-technical decision system. Good performance depends on state representation, reward and constraint design, simulator fidelity, baseline comparison, safe exploration, monitoring, and accountability—not merely on selecting a sophisticated algorithm.

11. Limitations, Governance, and Contemporary Directions

RL remains difficult in high-dimensional, partially observable, and non-stationary environments. The curse of dimensionality makes tabular representation impractical. Neural function approximation can generalize, but it may also extrapolate unpredictably. Long-horizon credit assignment makes it difficult to determine which earlier action caused a later outcome. Sparse rewards can lead to very slow learning.

Other limitations include instability from bootstrapping with approximation, overestimation of action values, sensitivity to reward scaling, and reproducibility problems. Reported improvements may depend on tuning budgets or favourable random seeds. Researchers should disclose environments, preprocessing, evaluation protocols, seeds, baselines, and computational resources.

Governance is particularly important when RL affects people. Systems should have defined authority boundaries, human override, incident response, access controls, privacy protection, and change-management procedures. Decisions that allocate healthcare, credit, employment opportunities, or public resources require fairness analysis and legal review. A reward function should never be treated as a complete substitute for policy, law, or professional judgment.

Contemporary research includes model-based RL, offline and batch RL, multi-agent learning, hierarchical policies, world models, safe and constrained RL, distributional value estimation, causal decision-making, and combinations of RL with foundation models. These directions expand capability but do not remove the need for valid assumptions, reliable evaluation, and operational controls.

Best-Practice Checklist

Before approving an RL system, ask:

1. Is the state sufficiently Markov, or is important information hidden?
2. Are rewards, costs, constraints, and terminal conditions specified clearly?
3. Is there a strong non-RL baseline?
4. Are exploration and failure modes safe?
5. Has the simulator been validated and stress-tested?
6. Has performance been assessed across seeds, subgroups, and distribution shifts?
7. Are offline-data coverage and extrapolation risks understood?
8. Are human oversight, rollback, monitoring, and audit mechanisms defined?
9. Does the deployment objective reflect stakeholder and regulatory requirements?
10. Can the organization explain why an action was selected and detect degradation?

Chapter Summary

Reinforcement learning studies how an agent learns sequential decisions through interaction with an environment. The Markov decision process formalizes states, actions, transitions, rewards, and discounting. Policies determine action selection, while state-value and action-value functions quantify expected future return. Bellman equations express the recursive structure of these values.

Dynamic programming assumes a known model; Monte Carlo methods learn from complete returns; temporal-difference methods update from sampled transitions and bootstrap from current estimates. Q-learning is an off-policy action-value method, whereas SARSA is on-policy. Policy-gradient and actor–critic methods directly optimize parameterized policies and are especially useful for continuous or complex action spaces.

Effective RL requires careful management of exploration, reward design, constraints, simulation fidelity, evaluation, and deployment risk. Reward hacking, partial observability, distribution shift, approximation error, and unsafe exploration remain serious challenges. In operational applications, technical performance must be considered alongside safety, fairness, accountability, privacy, and governance.

Key Terms

Markov decision process: A mathematical framework for modelling sequential decisions under uncertainty.

State: Information representing the agent’s relevant situation at a decision time.

Action: A choice available to the agent.

Transition probability: The probability of moving to a successor state after an action.

Reward: Immediate scalar feedback associated with a transition or action.

Policy: A rule or probability distribution for selecting actions.

Return: The cumulative, often discounted, future reward.

Discount factor: A parameter controlling the weight assigned to 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 equation relating current value to immediate reward and future value.

Dynamic programming: Model-based planning through recursive value computation.

Monte Carlo learning: Estimation from complete sampled episodes.

Temporal-difference learning: Learning from sampled rewards and bootstrapped estimates.

Q-learning: Off-policy learning of optimal action values.

SARSA: On-policy temporal-difference action-value learning.

Exploration: Trying actions to obtain information.

Reward shaping: Modifying rewards to provide more useful learning feedback.

Policy gradient: A method that optimizes parameters of a stochastic policy.

Actor–critic: An architecture combining a policy learner and a value estimator.

Review Questions

Short Answer Questions

1. What is the Markov property, and why can an inadequate state representation violate it?
2. Distinguish a policy, a state-value function, and an action-value function.
3. Why is Q-learning described as an off-policy method?
4. State one advantage and one limitation of temporal-difference learning.
5. What is reward hacking?

Long Answer Questions

1. Derive the Bellman expectation equation for a fixed policy and explain each term.
2. Compare dynamic programming, Monte Carlo learning, and temporal-difference learning.
3. Explain the differences between Q-learning and SARSA and discuss when each may be preferable.
4. Describe how reward design and explicit constraints should be handled in a safety-critical RL system.
5. Develop a simulation and deployment plan for an RL system used in logistics or energy management.

Analytical / Application Questions

1. An agent has Q(s,a)=5, receives reward 2, uses γ=0.8, observes next-state action values 6 and 3, and uses α=0.25. Calculate the Q-learning update and interpret it.
2. Design an MDP for dynamic pricing. Identify states, actions, transitions, rewards, constraints, and at least two possible reward-hacking behaviours.
3. A policy improves average reward but increases the frequency of rare catastrophic failures. Propose an evaluation framework and a deployment decision, explaining which metrics and safeguards you would require.

Multiple Choice Questions with Answers

Question 1

Which property defines a Markov decision process?

A. The next state depends only on the complete historical sequence

B. The future is conditionally independent of history given the current state and action

C. All rewards must be positive

D. The agent must use a deterministic policy

Correct Answer: B. The future is conditionally independent of history given the current state and action

Question 2

If the discount factor is zero, which objective is optimized?

A. Only the immediate next reward

B. The undiscounted infinite-horizon return

C. Only the final terminal reward

D. The variance of future rewards

Correct Answer: A. Only the immediate next reward

Question 3

Which equation represents the TD(0) value update?

A. V(S_t) ← V(S_t) + α[R_{t+1} + γV(S_{t+1}) − V(S_t)]

B. V(S_t) ← V(S_t) + α[R_{t+1} − γV(S_{t+1})]

C. V(S_t) ← max_a V(S_t)

D. V(S_t) ← R_{t+1}/γ

Correct Answer: A. V(S_t) ← V(S_t) + α[R_{t+1} + γV(S_{t+1}) − V(S_t)]

Question 4

Why is Q-learning off-policy?

A. It cannot use rewards

B. Its target evaluates a greedy next action even when behaviour explores

C. It requires a known transition model

D. It updates only after an episode ends

Correct Answer: B. Its target evaluates a greedy next action even when behaviour explores

Question 5

In the worked Q-learning example, what is the updated value when Q=5, reward=2, γ=0.8, max next Q=6, and α=0.25?

A. 5.20

B. 5.45

C. 6.80

D. 7.25

Correct Answer: B. 5.45

Question 6

What is the principal trade-off addressed by ε-greedy action selection?

A. Bias versus dimensionality

B. Exploration versus exploitation

C. Reward versus transition modelling

D. Variance versus observability

Correct Answer: B. Exploration versus exploitation

Question 7

Which reward-shaping form is associated with preserving the optimal policy under standard assumptions?

A. Φ(s)+Φ(s')

B. γΦ(s')−Φ(s)

C. γΦ(s)+Φ(s')

D. Φ(s)/γ

Correct Answer: B. γΦ(s')−Φ(s)

Question 8

What does SARSA use in its temporal-difference target?

A. The maximum possible next action value only

B. The action actually selected under the behaviour policy

C. The initial state value

D. A model-derived expectation over all complete episodes

Correct Answer: B. The action actually selected under the behaviour policy

Question 9

Which problem is especially associated with offline reinforcement learning?

A. The absence of any historical data

B. Distribution shift when the learned policy selects poorly represented actions

C. The impossibility of using constraints

D. The requirement that all actions be continuous

Correct Answer: B. Distribution shift when the learned policy selects poorly represented actions

Question 10

Why should an RL deployment be evaluated beyond mean episode reward?

A. Mean reward is always mathematically invalid

B. Operational safety, fairness, robustness, and rare failures may not be reflected by the mean

C. Episode reward cannot be measured in simulation

D. Value functions never use rewards

Correct Answer: B. Operational safety, fairness, robustness, and rare failures may not be reflected by the mean