Markov Decision Processes and Bellman Theory

Introduction

Reinforcement learning (RL) studies how an agent learns to make sequential 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 behavior that produces desirable long-term consequences.

The mathematical foundation for this interaction is the Markov decision process (MDP). MDPs formalize states, actions, transition dynamics, rewards, and objectives. Bellman theory then provides recursive equations for evaluating policies and finding optimal decisions. These ideas support dynamic programming, temporal-difference learning, Q-learning, policy-gradient methods, and many modern AI systems.

This chapter develops MDPs from Markov chains, explains finite- and infinite-horizon objectives, introduces occupancy measures, derives Bellman equations, and examines practical limitations and governance concerns.

Learning Objectives

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

1. Explain the Markov property and distinguish Markov chains from MDPs.

2. Define states, actions, transition probabilities, rewards, policies, and returns.

3. Formulate finite- and infinite-horizon decision problems.

4. Derive and interpret Bellman expectation and optimality equations.

5. Calculate values and action values for small MDPs.

6. Explain occupancy measures and their use in evaluating policies.

7. Apply MDP reasoning to an AI-enabled decision problem.

8. Identify modeling assumptions, limitations, and ethical risks.

1. Sequential Decision Making and the Markov Property

A stochastic process is a sequence of random variables, such as \(S_0,S_1,S_2,\ldots\), representing system states over time. A process is Markov if the distribution of the next state depends on the past only through the current state:

\[

P(S_{t+1}=s'\mid S_t=s,S_{t-1},\ldots,S_0)=P(S_{t+1}=s'\mid S_t=s).

\]

The equation assumes that the chosen state representation contains all information needed to predict the next state. This is the Markov property. It does not claim that the environment is deterministic; transitions may remain stochastic.

A Markov chain consists of a state space \(\mathcal S\), an initial-state distribution, and transition probabilities \(P(s'\mid s)\). It has no decisions: the transition mechanism is fixed. For example, a machine may be operating, degraded, or failed, with probabilities governing movement among these conditions.

An MDP extends a Markov chain by adding actions and rewards. The agent influences transitions by selecting actions. Formally, a finite MDP is commonly represented as

\[

(\mathcal S,\mathcal A,P,R,\gamma),

\]

where:

• \(\mathcal S\) is the state space;
• \(\mathcal A\) is the action space;
• \(P(s'\mid s,a)\) is the probability of reaching \(s'\) after action \(a\) in state \(s\);
• \(R(s,a,s')\) is the reward associated with a transition; and
• \(\gamma\in[0,1)\) is a discount factor for continuing tasks.

Some texts use an expected immediate reward \(r(s,a)\) instead of a transition-dependent reward. These are related by

\[

r(s,a)=\sum_{s'}P(s'\mid s,a)R(s,a,s').

\]

The transition probabilities satisfy \(P(s'\mid s,a)\ge 0\) and \(\sum_{s'}P(s'\mid s,a)=1\) for every state-action pair.

State representation and the Markov assumption

The Markov property is a modeling decision. In a robot navigation task, the current position alone may be insufficient if velocity affects future motion. A better state might include position, velocity, battery level, and nearby obstacles. If relevant history is omitted, the observed process may be non-Markovian, causing value estimates and policies to be systematically unreliable.

In partially observable environments, the agent observes \(O_t\) rather than the true state \(S_t\). Such problems are often modeled as partially observable MDPs (POMDPs). A belief state—a probability distribution over possible states—can sometimes restore the Markov property, but increases computational complexity.

2. Policies, Rewards, and Returns

At time \(t\), the agent selects an action \(A_t\), receives reward \(R_{t+1}\), and observes \(S_{t+1}\). A policy specifies how actions are selected. A stationary stochastic policy is

\[

\pi(a\mid s)=P(A_t=a\mid S_t=s),

\]

with \(\sum_a\pi(a\mid s)=1\). A deterministic policy chooses one action, written \(a=\pi(s)\). Stochastic policies are useful when exploration, uncertainty, randomization, or robustness is important.

The immediate reward measures short-term consequence. The return is the cumulative reward from a specified time onward. For a finite horizon of \(H\) steps, the undiscounted return is

\[

G_t=\sum_{k=0}^{H-t-1}R_{t+k+1}.

\]

For a discounted continuing task,

\[

G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots

=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}.

\]

Here, \(0\le\gamma<1\). If rewards are bounded by \(|R_t|\le R_{\max}\), the infinite sum is finite because \(|G_t|\le R_{\max}/(1-\gamma)\). Discounting can represent time preference, uncertainty about distant outcomes, or a mathematical device ensuring convergence. It should not be treated as a neutral technical setting: a high discount factor gives more weight to delayed consequences.

A terminal episodic task may use \(\gamma=1\) when the episode ends in finite time and returns are bounded. For continuing tasks, undiscounted objectives require additional conditions, such as average-reward formulations.

3. Value Functions and Occupancy Measures

The state-value function of policy \(\pi\) is the expected return starting from state \(s\):

\[

V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s].

\]

The action-value function is

\[

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

\]

The first action is fixed at \(a\); thereafter the policy \(\pi\) is followed. Their relationship is

\[

V^\pi(s)=\sum_a\pi(a\mid s)Q^\pi(s,a).

\]

The optimal value functions are

\[

V^(s)=\max_\pi V^\pi(s),\qquad Q^(s,a)=\max_\pi Q^\pi(s,a).

\]

An optimal policy can select an action maximizing \(Q^*(s,a)\).

State and state-action occupancy

For an initial distribution \(\mu\), the discounted state occupancy measure under policy \(\pi\) is

\[

d^\pi_\mu(s)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^tP_\pi(S_t=s\mid S_0\sim\mu).

\]

The factor \((1-\gamma)\) normalizes the measure so that \(\sum_s d^\pi_\mu(s)=1\) in a finite state space. The state-action occupancy is

\[

d^\pi_\mu(s,a)=d^\pi_\mu(s)\pi(a\mid s).

\]

Occupancy measures describe how often a policy visits states and takes actions, with earlier visits weighted more heavily. They are useful for policy evaluation, imitation learning, inverse reinforcement learning, offline RL, and constrained optimization. For example, the normalized expected discounted return from \(\mu\) can be written as

\[

J(\pi)=\mathbb E_{S_0\sim\mu}[V^\pi(S_0)]

=\frac{1}{1-\gamma}\sum_{s,a}d^\pi_\mu(s,a)r(s,a).

\]

This identity assumes the reward is the expected immediate reward \(r(s,a)\) and the discounted occupancy is defined as above.

4. Bellman Expectation Equations

The key insight of Bellman theory is that a return can be decomposed into its immediate reward plus the discounted return from the next state:

\[

G_t=R_{t+1}+\gamma G_{t+1}.

\]

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

\[

V^\pi(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a)

\left[R(s,a,s')+\gamma V^\pi(s')\right].

\]

Using expected reward \(r(s,a)\), this becomes

\[

V^\pi(s)=\sum_a\pi(a\mid s)\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s')\right].

\]

The corresponding action-value equation is

\[

Q^\pi(s,a)=\sum_{s'}P(s'\mid s,a)\left[R(s,a,s')+

\gamma\sum_{a'}\pi(a'\mid s')Q^\pi(s',a')\right].

\]

For a finite MDP, these equations form a linear system. Define the policy-induced transition matrix \(P_\pi(s,s')=\sum_a\pi(a\mid s)P(s'\mid s,a)\), and expected policy reward \(r_\pi(s)=\sum_a\pi(a\mid s)r(s,a)\). In vector notation,

\[

V^\pi=r_\pi+\gamma P_\pi V^\pi.

\]

When \(\gamma<1\),

\[

V^\pi=(I-\gamma P_\pi)^{-1}r_\pi,

\]

provided the inverse exists, which it does for a finite stochastic transition matrix and \(0\le\gamma<1\). Direct matrix solution is useful for small problems, while iterative methods are preferable for large state spaces.

Worked example: policy evaluation

Consider two nonterminal states, \(A\) and \(B\), and a fixed policy. Under the policy, state \(A\) gives expected immediate reward 2 and transitions to \(B\) with probability 1. State \(B\) gives expected immediate reward 1 and transitions to \(A\) with probability 1. Let \(\gamma=0.5\). Then

\[

V(A)=2+0.5V(B),\qquad V(B)=1+0.5V(A).

\]

Substituting the second equation into the first:

\[

V(A)=2+0.5(1+0.5V(A))=2.5+0.25V(A).

\]

Thus \(0.75V(A)=2.5\), so \(V(A)=10/3\approx3.333\). Therefore,

\[

V(B)=1+0.5(10/3)=8/3\approx2.667.

\]

These values are expected discounted returns, not guaranteed rewards.

5. Bellman Optimality Equations and Dynamic Programming

For optimal control, the agent chooses the action that maximizes expected return. The Bellman optimality equation is

\[

V^*(s)=\max_a\sum_{s'}P(s'\mid s,a)

\left[R(s,a,s')+\gamma V^*(s')\right].

\]

Equivalently,

\[

Q^*(s,a)=\sum_{s'}P(s'\mid s,a)\left[R(s,a,s')+

\gamma\max_{a'}Q^*(s',a')\right].

\]

The principle of optimality states that an optimal policy has the property that, whatever the initial state and first decision, the remaining decisions must form an optimal policy for the state resulting from that decision. This principle depends on an appropriate Markov state representation and an additive return objective.

Policy evaluation

Given \(\pi\), policy evaluation computes \(V^\pi\), either by solving the linear system or by iterative updates:

\[

V_{k+1}(s)=\sum_a\pi(a\mid s)\sum_{s'}P(s'\mid s,a)

[R(s,a,s')+\gamma V_k(s')].

\]

For finite states and \(\gamma<1\), these updates converge to \(V^\pi\) under standard bounded-reward assumptions.

Policy improvement

Given \(V^\pi\), define a greedy policy by choosing

\[

\pi'(s)\in\arg\max_a\sum_{s'}P(s'\mid s,a)

[R(s,a,s')+\gamma V^\pi(s')].

\]

The policy improvement theorem states that this policy is at least as good as \(\pi\) in every state. Repeated policy evaluation and improvement produces policy iteration.

Value iteration

Value iteration combines optimality backups directly:

\[

V_{k+1}(s)=\max_a\sum_{s'}P(s'\mid s,a)

[R(s,a,s')+\gamma V_k(s')].

\]

For discounted finite MDPs, the Bellman optimality operator is a contraction in the sup norm with modulus \(\gamma\). Consequently, value iteration converges to the unique fixed point \(V^*\). A practical stopping rule is to stop when

\[

\max_s|V_{k+1}(s)-V_k(s)|<\varepsilon.

\]

The resulting value error is bounded by approximately \(\gamma\varepsilon/(1-\gamma)\) if the stopping difference is interpreted in the usual contraction-based manner; implementations should state precisely which bound and stopping convention they use.

6. Finite-Horizon and Infinite-Horizon Formulations

Finite horizon

A finite-horizon problem has a known number of remaining decisions. Values depend on time because the value of an opportunity changes as the deadline approaches. Let \(V_t(s)\) be the optimal expected reward from time \(t\) through terminal time \(H\), with terminal value \(V_H(s)=0\). Backward induction gives

\[

V_t(s)=\max_a\sum_{s'}P(s'\mid s,a)

[R_t(s,a,s')+V_{t+1}(s')].

\]

A time-dependent optimal policy \(\pi_t^*\) may be necessary. If discounting is included, replace the continuation term by \(\gamma V_{t+1}(s')\). Finite-horizon models are appropriate for inventory planning over a month, portfolio decisions over a fixed project, or robot missions with a deadline.

Infinite horizon

In an infinite-horizon discounted MDP, the same decision problem repeats without a fixed endpoint. Stationary optimal policies exist under common assumptions, including finite state and action spaces and bounded rewards. Discounting ensures that distant rewards have diminishing influence and supports contraction-based convergence.

An alternative for continuing tasks is the average-reward objective:

\[

\rho^\pi=\lim_{T\to\infty}\frac{1}{T}\mathbb E_\pi\left[\sum_{t=0}^{T-1}R_{t+1}\right],

\]

when the limit exists. Average-reward methods focus on long-run performance rather than time preference, but require different theory and may have multiple recurrent classes or nonunique bias values.

7. Illustrative Case: Predictive Maintenance for a Production Line

This is a fictional illustrative case designed to demonstrate MDP modeling.

Background and problem

A manufacturer operates a machine whose condition is observed daily as Healthy, Degraded, or Failed. The firm can either continue operation or perform preventive maintenance. Maintenance costs money and temporarily reduces production, but may prevent a costly failure. The objective is to maximize discounted expected profit over an ongoing planning horizon.

Model formulation

The state space is

\[

\mathcal S=\{H,D,F\}.

\]

Actions in states \(H\) and \(D\) are Continue and Maintain. In state \(F\), repair is mandatory. A state should include information such as age, workload, and sensor-derived condition if these variables affect future transitions.

Suppose the reward for continuing in \(H\) is 10, while continuing in \(D\) gives 6. Maintenance costs 3 but returns the machine to \(H\) on the next day. Failure imposes a large negative reward and requires repair. Transition probabilities are estimated from historical maintenance records and engineering simulations.

Analysis and solution

For each state-action pair, the organization estimates

\[

Q(s,a)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s').

\]

Value iteration compares Continue and Maintain in each state. A typical result is that Continue is optimal in Healthy states, while Maintain becomes optimal in Degraded states when failure risk is sufficiently high. The exact threshold depends on maintenance cost, failure penalty, transition probabilities, discount factor, and the reliability of estimates.

Outcome and learning points

The MDP makes trade-offs explicit rather than relying on a simple “repair after a fixed number of days” rule. It can support what-if analysis: managers can examine how the policy changes if maintenance costs rise, sensors become more accurate, or the penalty for downtime increases.

However, deployment requires more than maximizing estimated profit. Sensor errors, unequal safety impacts, unmodeled breakdown modes, and changing production conditions can invalidate the model. A safe system should include human override, conservative action constraints, monitoring for distribution shift, and periodic validation. Preventive maintenance policies also affect workers, production schedules, and environmental waste; these impacts belong in the decision analysis.

8. Practical Implementation Considerations

A sound MDP implementation begins with the decision question, not with an algorithm. Designers should identify the decision frequency, available actions, relevant state variables, reward timing, terminal conditions, and constraints. Rewards should represent the actual objective and avoid hidden incentives that encourage unsafe shortcuts.

Transition models may be known, estimated from data, or learned online. Empirical estimates should report uncertainty, sample coverage, and whether data were collected under policies different from the proposed policy. Offline RL is especially sensitive to distribution shift: a learned policy may select actions rarely or never observed in the historical data.

For continuous or very large spaces, exact tabular dynamic programming is infeasible. Function approximation, simulation, model-based planning, or state abstraction may be needed. These methods introduce approximation error and potential instability. Validation should use held-out scenarios, stress tests, uncertainty analysis, and domain-expert review.

9. Challenges, Limitations, and Governance

Reward misspecification occurs when the numerical reward omits important objectives or creates undesirable incentives. A recommendation system rewarded only for immediate clicks may reduce user well-being or promote sensational content. Multi-objective settings may require constrained MDPs, vector rewards, or explicit stakeholder-defined trade-offs.

State aliasing occurs when distinct situations are represented by the same state even though their future consequences differ. This violates the effective Markov assumption. Memory, belief states, or richer observations may be required.

Model uncertainty is unavoidable in real environments. Confidence intervals, robust MDPs, Bayesian models, and risk-sensitive objectives can represent uncertainty more honestly than a single point estimate.

Safety and fairness are central when actions affect people. A policy should be tested for disparate impacts, unsafe edge cases, privacy risks, and the possibility that exploration imposes harm. High-stakes applications may require hard constraints, approval workflows, audit logs, explainability, and compliance with sector-specific regulation.

Discounting and intergenerational effects raise normative questions. A low weight on distant rewards can encourage short-term gains at the expense of sustainability. Discount factors should therefore be justified in relation to the application rather than selected solely for computational convenience.

Best Practices

1. Define a state that is sufficiently predictive while remaining measurable and operationally available.

2. Separate state, action, reward, and next-state timing explicitly.

3. Document transition and reward assumptions, including uncertainty.

4. Choose finite, discounted, or average-reward objectives to match the real decision problem.

5. Test policies under perturbations, rare events, and distribution shift.

6. Use constraints and human oversight in safety-critical settings.

7. Monitor outcomes after deployment and revise the MDP when the environment changes.

8. Evaluate stakeholder and ethical consequences, not merely numerical return.

Chapter Summary

Markov chains describe stochastic state evolution without decisions; MDPs add actions and rewards. The Markov property states that the current state contains the information needed for predicting future dynamics, although constructing such a state is a substantive modeling task. Policies map states to actions, returns aggregate rewards, and discounting controls the importance of delayed outcomes.

State-value and action-value functions quantify expected returns under a policy. Discounted occupancy measures describe how frequently states and actions are visited and connect policy performance to reward averages. Bellman expectation equations evaluate a fixed policy, while Bellman optimality equations characterize the best achievable value. Policy iteration alternates evaluation and improvement, whereas value iteration applies optimality backups directly. Finite-horizon problems use backward induction and may require time-dependent policies; infinite-horizon discounted problems often admit stationary optimal policies.

MDPs are practical tools for maintenance, robotics, recommendation, resource allocation, and other sequential decisions. Their reliability depends on state representation, transition estimates, reward design, uncertainty treatment, and responsible governance. A mathematically optimal policy is not necessarily socially desirable or safe unless these broader considerations are included.

Key Terms

Markov property: The condition that the next-state distribution depends on history only through the current state.

Markov chain: A stochastic state process with fixed transition dynamics and no agent-controlled actions.

Markov decision process: A model consisting of states, actions, transitions, rewards, and usually a discount factor.

State: A representation of the situation relevant to future decisions and dynamics.

Action: A choice made by the agent.

Transition probability: The probability of reaching a next state given a current state and action.

Reward: Numerical feedback associated with an action or transition.

Policy: A rule specifying action selection.

Return: Cumulative future reward from a time step.

Discount factor: A number governing 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 under a policy.

Occupancy measure: A discounted or long-run distribution describing visits to states or state-action pairs.

Bellman expectation equation: A recursive equation evaluating a specified policy.

Bellman optimality equation: A recursive equation defining the best achievable value.

Principle of optimality: The idea that the remaining part of an optimal plan is optimal for the resulting state.

Policy iteration: Repeated policy evaluation and policy improvement.

Value iteration: Iterative application of Bellman optimality backups.

Finite-horizon MDP: An MDP with a specified final decision time.

Average reward: Long-run reward per time step in a continuing task.

Review Questions

Short Answer Questions

1. What is the Markov property, and why is state representation important?

2. How does an MDP differ from a Markov chain?

3. Define a policy, a return, and a discount factor.

4. Distinguish the state-value function from the action-value function.

5. What is the purpose of an occupancy measure?

Long Answer Questions

1. Derive the Bellman expectation equation for a fixed stochastic policy and explain each term.

2. Compare policy iteration and value iteration, including their update rules and convergence setting.

3. Explain how finite-horizon and infinite-horizon MDPs differ in objectives and policy structure.

4. Discuss how reward misspecification and state aliasing can produce harmful policies.

5. Explain how a predictive-maintenance problem can be formulated as an MDP.

Analytical / Application Questions

1. A two-state MDP has rewards \(r(A)=2\) and \(r(B)=1\), alternates deterministically between states, and uses \(\gamma=0.5\). Calculate the values of both states under the fixed policy.

2. Design an MDP for allocating jobs between two cloud servers. Specify states, actions, transitions, rewards, discounting, and at least one operational constraint.

3. A historical dataset contains no examples of an RL policy taking a particular high-risk action. Analyze why offline evaluation of that action is unreliable and propose safeguards.

Multiple Choice Questions with Answers

Question 1

Which statement best defines the Markov property?

A. Rewards are always deterministic

B. The next-state distribution depends on the past only through the current state

C. Every state has exactly two available actions

D. The agent must know the transition probabilities

Correct Answer: B. The next-state distribution depends on the past only through the current state

Question 2

What additional elements does an MDP add to a Markov chain?

A. Actions and rewards

B. Only terminal states

C. Only a discount factor

D. A requirement that transitions be deterministic

Correct Answer: A. Actions and rewards

Question 3

For a discounted continuing task with bounded rewards, which condition commonly ensures a finite return?

A. Gamma is greater than 2

B. Gamma equals negative one

C. Gamma is between 0 inclusive and 1 exclusive

D. Rewards must all be zero

Correct Answer: C. Gamma is between 0 inclusive and 1 exclusive

Question 4

Which equation evaluates a fixed policy?

A. The Bellman expectation equation

B. The Bellman optimality equation only

C. The softmax equation

D. The central limit equation

Correct Answer: A. The Bellman expectation equation

Question 5

What operation appears in the Bellman optimality equation for a value function?

A. Minimum over rewards only

B. Maximum over available actions

C. Random permutation of states

D. Division by the number of states

Correct Answer: B. Maximum over available actions

Question 6

In the worked two-state example, with V(A)=2+0.5V(B) and V(B)=1+0.5V(A), what is V(A)?

A. 2.5

B. 3.333 approximately

C. 4.0

D. 5.0

Correct Answer: B. 3.333 approximately

Question 7

What is the main purpose of policy improvement?

A. To choose actions that are greedy with respect to the current value estimate

B. To remove all rewards from the MDP

C. To make transitions deterministic

D. To force every state to be visited equally often

Correct Answer: A. To choose actions that are greedy with respect to the current value estimate

Question 8

Which method applies Bellman optimality backups directly?

A. Policy iteration

B. Value iteration

C. Ordinary least squares only

D. Random search without values

Correct Answer: B. Value iteration

Question 9

Why can a finite-horizon optimal policy depend on time?

A. The available state space always changes

B. The value of future opportunities changes as the deadline approaches

C. Discounting is impossible in finite horizons

D. Finite-horizon transitions cannot be stochastic

Correct Answer: B. The value of future opportunities changes as the deadline approaches

Question 10

What does a discounted occupancy measure describe?

A. The frequency of visiting states or state-action pairs, weighted toward earlier times

B. The maximum reward possible in one step

C. The number of parameters in a neural network

D. Only the probability of terminal failure

Correct Answer: A. The frequency of visiting states or state-action pairs, weighted toward earlier times