MDP - RL Foundation

What is an MDP?

A Markov Decision Process (MDP) provides the mathematical framework for modeling sequential decision-making under uncertainty. It formalizes environments where an agent takes actions, transitions between states stochastically, and receives rewards. Every reinforcement learning algorithm implicitly or explicitly operates on an MDP.

The "Markov" property means the future depends only on the current state, not on the history of how we got there. This memoryless property makes computation tractable—we only need to know where we are, not where we've been.

Formal Definition

An MDP is defined by the tuple (S, A, P, R, γ):

S	Set of states (state space)
Examples	grid positions, game boards, robot configurations
A	Set of actions (action space)
Examples	{up, down, left, right}, {buy, sell, hold}
P	Transition function P(s'\|s, a)
R	Reward function R(s, a, s')
γ	Discount factor ∈ [0, 1]
γ=0	only care about next reward (myopic)
γ=1	all future rewards equally important (far-sighted)
γ=0.9	typical choice (balance)

Worked Example: Grid World MDP

States	11 non-terminal cells
Actions	{Up, Down, Left, Right}
Transition	Stochastic!
80% chance	move in intended direction
10% chance	move perpendicular (left of intended)
10% chance	move perpendicular (right of intended)
If hits wall	stay in place
Rewards	-0.04 per step (motivates efficiency)
Discount	γ = 0.9

Policy, Value Function, and Optimality

Policy π(s)

A policy maps states to actions—it's the agent's strategy:

π(s) = action to take in state s

Deterministic: π(s) = Up (always go up from state s)

Stochastic: π(a|s) = P(action=a | state=s)

Value Function V^π(s)

Expected cumulative discounted reward from state s following policy π:

V^π(s) = E[R₁ + γR₂ + γ²R₃ + ... | s₀=s, policy=π]

For Grid World with optimal policy:

V*(goal_adjacent) ≈ 0.85 (close to reward)

V*(start) ≈ 0.44 (many steps away, discounted)

V*(pit_adjacent) ≈ -0.1 (danger nearby)

Bellman Equation

The fundamental recursive relationship:

V^π(s) = Σ_a π(a|s) × Σ_s' P(s'|s,a) × [R(s,a,s') + γ × V^π(s')]

For optimal policy:

V*(s) = max_a Σ_s' P(s'|s,a) × [R(s,a,s') + γ × V*(s')]

"The value of a state equals the best action's expected

immediate reward plus discounted future value"

Q-Function (Action-Value)

Q*(s,a) = Σ_s' P(s'|s,a) × [R(s,a,s') + γ × V*(s')]

Relationship: V*(s) = max_a Q*(s,a)

Optimal policy: π*(s) = argmax_a Q*(s,a)

Solving MDPs

Value Iteration

Iteratively apply Bellman optimality equation

Initialize V(s) = 0 for all states

Repeat until convergence

for each state s:

V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')]

Convergence: |V_new(s) - V_old(s)| < ε for all s

Value Iteration Trace (Simplified)

Iteration 1	(only terminal rewards visible)
Iteration 2	(rewards propagate one step further)
Iteration 10	Values converge, optimal policy emerges

Policy Iteration

2. Policy Evaluation	Compute V^π exactly (solve linear system)
3. Policy Improvement	For each s, set π(s) = argmax_a Q^π(s,a)
4. If policy unchanged	optimal! Else → go to step 2

Properties of MDPs

Optimal policy exists	For finite MDPs with discount < 1,
Stationary policy suffices	The optimal policy doesn't depend
Policy uniqueness	Optimal value function is unique,

Extensions of Basic MDPs

Partially Observable MDP (POMDP)

Agent can't directly observe state

Instead gets observations O with P(o|s)

Must maintain belief state: probability distribution over states

Much harder to solve (PSPACE-complete)

Continuous MDPs

Infinite/continuous state and/or action spaces

Can't enumerate states—use function approximation

Neural networks approximate V(s) or Q(s,a)

Multi-Agent MDPs

Multiple agents with shared or competing goals

Game theory meets sequential decision making

Nash equilibrium in sequential games

Interview Questions

Q: What is the Markov property and why does it matter? A: The Markov property states that the future is independent of the past given the present: P(s_{t+1}|s_t, s_{t-1}, ...) = P(s_{t+1}|s_t). This makes MDPs tractable—we only need the current state for optimal decisions, not the entire history. Without this property, the state space becomes history-dependent and exponentially larger.

Q: What does the discount factor γ control? A: γ controls the planning horizon. γ close to 0 makes the agent myopic (only immediate rewards matter). γ close to 1 makes the agent far-sighted (future rewards nearly as important as immediate). Mathematically, γ ensures the infinite sum of rewards converges: Σγ^t R_t ≤ R_max/(1-γ).

Q: When is value iteration preferred over policy iteration? A: Value iteration is simpler and uses less memory per iteration (just stores V(s)). Policy iteration converges in fewer iterations but each requires solving a linear system (O(|S|³)). For large state spaces where the linear system is impractical, value iteration (or its RL approximations) is preferred.

What is an MDP?

Formal Definition

An MDP is defined by the tuple (S, A, P, R, γ):

S	Set of states (state space)
Examples	grid positions, game boards, robot configurations
A	Set of actions (action space)
Examples	{up, down, left, right}, {buy, sell, hold}
P	Transition function P(s'\|s, a)
R	Reward function R(s, a, s')
γ	Discount factor ∈ [0, 1]
γ=0	only care about next reward (myopic)
γ=1	all future rewards equally important (far-sighted)
γ=0.9	typical choice (balance)

Worked Example: Grid World MDP

States	11 non-terminal cells
Actions	{Up, Down, Left, Right}
Transition	Stochastic!
80% chance	move in intended direction
10% chance	move perpendicular (left of intended)
10% chance	move perpendicular (right of intended)
If hits wall	stay in place
Rewards	-0.04 per step (motivates efficiency)
Discount	γ = 0.9

Policy, Value Function, and Optimality

Policy π(s)

A policy maps states to actions—it's the agent's strategy:

π(s) = action to take in state s

Deterministic: π(s) = Up (always go up from state s)

Stochastic: π(a|s) = P(action=a | state=s)

Value Function V^π(s)

Expected cumulative discounted reward from state s following policy π:

V^π(s) = E[R₁ + γR₂ + γ²R₃ + ... | s₀=s, policy=π]

For Grid World with optimal policy:

V*(goal_adjacent) ≈ 0.85 (close to reward)

V*(start) ≈ 0.44 (many steps away, discounted)

V*(pit_adjacent) ≈ -0.1 (danger nearby)

Bellman Equation

The fundamental recursive relationship:

V^π(s) = Σ_a π(a|s) × Σ_s' P(s'|s,a) × [R(s,a,s') + γ × V^π(s')]

For optimal policy:

V*(s) = max_a Σ_s' P(s'|s,a) × [R(s,a,s') + γ × V*(s')]

"The value of a state equals the best action's expected

immediate reward plus discounted future value"

Q-Function (Action-Value)

Q*(s,a) = Σ_s' P(s'|s,a) × [R(s,a,s') + γ × V*(s')]

Relationship: V*(s) = max_a Q*(s,a)

Optimal policy: π*(s) = argmax_a Q*(s,a)

Solving MDPs

Value Iteration

Iteratively apply Bellman optimality equation

Initialize V(s) = 0 for all states

Repeat until convergence

for each state s:

V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')]

Convergence: |V_new(s) - V_old(s)| < ε for all s

Value Iteration Trace (Simplified)

Iteration 1	(only terminal rewards visible)
Iteration 2	(rewards propagate one step further)
Iteration 10	Values converge, optimal policy emerges

Policy Iteration

2. Policy Evaluation	Compute V^π exactly (solve linear system)
3. Policy Improvement	For each s, set π(s) = argmax_a Q^π(s,a)
4. If policy unchanged	optimal! Else → go to step 2

Properties of MDPs

Optimal policy exists	For finite MDPs with discount < 1,
Stationary policy suffices	The optimal policy doesn't depend
Policy uniqueness	Optimal value function is unique,

Extensions of Basic MDPs

Partially Observable MDP (POMDP)

Agent can't directly observe state

Instead gets observations O with P(o|s)

Must maintain belief state: probability distribution over states

Much harder to solve (PSPACE-complete)

Continuous MDPs

Infinite/continuous state and/or action spaces

Can't enumerate states—use function approximation

Neural networks approximate V(s) or Q(s,a)

Multi-Agent MDPs

Multiple agents with shared or competing goals

Game theory meets sequential decision making

Nash equilibrium in sequential games

What is an MDP?

Formal Definition

Worked Example: Grid World MDP

Policy, Value Function, and Optimality

Policy π(s)

Value Function V^π(s)

Bellman Equation

Q-Function (Action-Value)

Solving MDPs

Value Iteration

Iteratively apply Bellman optimality equation

Repeat until convergence

Value Iteration Trace (Simplified)

Policy Iteration

Properties of MDPs

Extensions of Basic MDPs

Partially Observable MDP (POMDP)

Continuous MDPs

Multi-Agent MDPs

Interview Questions

Continue learning this concept

What is an MDP?

Formal Definition

Worked Example: Grid World MDP

Policy, Value Function, and Optimality

Policy π(s)

Value Function V^π(s)

Bellman Equation

Q-Function (Action-Value)

Solving MDPs

Value Iteration

Iteratively apply Bellman optimality equation

Repeat until convergence

Value Iteration Trace (Simplified)

Policy Iteration

Properties of MDPs

Extensions of Basic MDPs

Partially Observable MDP (POMDP)

Continuous MDPs

Multi-Agent MDPs

Interview Questions

Continue learning this concept