Unit 2: Markov Decision Process (MDP) & Dynamic
Programming
Comprehensive Exam Notes
Syllabus Covered: Markov property, MDPs, goals and rewards, returns and episodes,
optimality of value functions/policies, Bellman optimality equations. Overview of
Dynamic Programming (DP), principle of optimality, iterative policy evaluation, policy
improvement, policy iteration, value iteration, generalized policy iteration,
Asynchronous DP, Efficiency of DP.
Reference: Chapters 3 & 4 of Sutton & Barto.
1. The Markov Property
A state signal possesses the Markov Property if it contains all relevant information from
past interactions. In mathematical terms, the future is independent of the past given the
present state.
If a state S is Markov, then the probability of transitioning to the next state S
t t+1 and
receiving reward R
t+1 depends only on the current state St and action At, not on the entire
history.
2. Markov Decision Process (MDP)
A Markov Decision Process (MDP) is a classical formalization of sequential decision-
making, where actions influence not just immediate rewards, but also subsequent
situations, or states, and through those future rewards. It is formally defined by a tuple (S,
A, P, R, γ):
• S: A finite set of states.
• A: A finite set of actions.
• P: State transition probability matrix.
• R: Reward function.
• γ: Discount factor γ ∈ [0, 1].
1
Goals, Rewards, Returns, and Episodes
• Goals & Rewards: The agent's goal is formulated in terms of a special signal called the
reward. The goal is to maximize the cumulative reward.
• Return (G ): The function of future rewards that the agent seeks to maximize.
t
Gt = Rt+1 + γRt+2 + γ2Rt+3 + ... = ∑ γk Rt+k+1
• Episodes: In many tasks, the agent-environment interaction naturally breaks into
subsequences (e.g., plays of a game). Each sequence is called an episode.
3. Optimality and Bellman Optimality Equations
Solving a reinforcement learning task means finding a policy that achieves a lot of reward
over the long run.
• Optimal Policy (π ): A policy that is better than or equal to all other policies.
*
• Optimal State-Value Function (v (s)): The maximum expected return achievable from
*
state s under any policy.
Bellman Optimality Equation
It expresses the fact that the value of a state under an optimal policy must equal the
expected return for the best action from that state.
v*(s) = maxa 𝔼 [ Rt+1 + γ v*(St+1) | St=s, At=a ]
4. Dynamic Programming (DP)
The term Dynamic Programming (DP) refers to a collection of algorithms that can be used
to compute optimal policies given a perfect model of the environment as a Markov Decision
Process (MDP).
A. Iterative Policy Evaluation
The process of computing the state-value function v for an arbitrary policy π. We use the
π
Bellman equation as an update rule:
2
V(s) ← ∑a π(a|s) ∑s', r p(s', r | s, a) [r + γ V(s')]
B. Policy Improvement
Once we evaluate a policy, we can improve it by acting greedily with respect to the
evaluated value function. If a new action appears better than the current policy's action, we
update the policy to choose the new action.
C. Policy Iteration vs. Value Iteration
• Policy Iteration: Alternates between completely evaluating a policy (Policy Evaluation)
and strictly improving it (Policy Improvement) until the policy converges to the optimal
policy π .
*
• Value Iteration: Truncates the policy evaluation step to just one sweep (one update of
each state) to speed up the process. It merges evaluation and improvement into a single
update step using the Bellman Optimality Equation.
D. Generalized Policy Iteration (GPI)
GPI is the general idea of letting policy evaluation and policy improvement processes
interact, independent of the granularity and other details of the two processes. Almost all
RL methods are well described as GPI.
E. Asynchronous DP
Standard DP requires sweeping through the entire state set to do an update. Asynchronous
DP algorithms update states in any order, using whatever values of other states happen to
be available. This is highly efficient for MDPs with millions of states.
3
5. Code Example: Value Iteration
def value_iteration(env, gamma=0.9, theta=1e-8):
V = [Link]([Link]) # Initialize values to 0
while True:
delta = 0
for s in range([Link]):
v_old = V[s]
# Calculate action values
action_values = [Link]([Link])
for a in range([Link]):
for prob, next_state, reward, done in env.P[s][a]:
action_values[a] += prob * (reward + gamma * V[next_state])
V[s] = [Link](action_values) # Greedy update
delta = max(delta, [Link](v_old - V[s]))
if delta < theta: # Convergence check
break
# Extract optimal policy from V
policy = extract_policy(env, V, gamma)
return policy, V
📝 Exam Preparation Section
Short Answer Questions
1. What does the Markov Property imply?
Ans: It implies that the current state holds all necessary historical information. The
probability of future transitions depends only on the current state and action.
2. What is the difference between Policy Iteration and Value Iteration?
Ans: Policy Iteration fully evaluates a policy before improving it. Value iteration speeds
this up by doing only one sweep of evaluation before performing an improvement step
via the Bellman Optimality Equation.
4
Long Answer Questions
1. Explain the components of a Markov Decision Process (MDP).
Hint: Detail the tuple (S, A, P, R, γ). Define States, Actions, Transition Probabilities,
Rewards, and the Discount Factor with a real-life example (like a navigating robot).
2. What is Generalized Policy Iteration (GPI)? Explain its significance in DP.
Hint: Describe the interacting cycle between policy evaluation (making the value
function consistent with the current policy) and policy improvement (making the
policy greedy w.r.t the value function).
Multiple Choice Questions
Q1. In an MDP, the return G is defined as:
t
a) The immediate reward b) The discounted sum of future rewards
c) The average of past rewards d) The value of the initial state
Q2. Dynamic Programming requires which of the following?
a) A perfect model of the environment b) Trial and error learning
c) Continuous action spaces d) No discount factor
⚡ Quick Revision Cheat Sheet
• MDP Tuple: (S, A, P, R, γ). The mathematical framework for RL.
• Markov Property: The present dictates the future; the past is irrelevant.
• v (s) vs q (s,a): v is the value of a state. q is the value of taking an action in a
* * * *
state.
• DP Requirements: DP algorithms require a perfect model of the environment's
dynamics (transition probabilities and rewards).
• Policy Iteration: Evaluate → Improve → Evaluate → Improve until optimal.
• Value Iteration: Combines evaluation and improvement in a single step using
max(a).