Markov Decision Processes (MDP)

What is an MDP?

Why these components?

States: Where can the agent be? (positions, configurations, observations)
Actions: What choices does the agent have? (moves, controls, decisions)
Transitions: What happens when I act? (physics, rules, uncertainty)
Rewards: What's good/bad? (goals encoded as numbers)
Discount: Future rewards are worth less (impatience, uncertainty, mathematical convenience)

Deriving the Value Function from First Principles

The Goal: Find a policy $\pi: S \to A$ (a strategy mapping states to actions) that maximizes total reward.

Step 1: Total Return

Starting from state $s_0$ , if we follow policy $\pi$ , we get a sequence: $s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_1} s_2 \xrightarrow{a_2} \cdots$

The return $G_t$ from time $t$ is the sum of all future rewards: $G_t = R_{t+1} + R_{t+2} + R_{t+3} + \cdots$

Problem: This sum can be infinite and doesn't distinguish near vs. far rewards.

Step 2: Discounted Return

Why discount? Three reasons:

Uncertainty: Future is less certain, so worth less
Impatience: Prefer reward now over later (economic time-preference)
Mathematical convergence: Ensures finite sums for infinite horizons

Discounted return: $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

Why this works: If $|\gamma| < 1$ and rewards are bounded by $R_{\max}$ , then: $G_t \leq \sum_{k=0}^{\infty} \gamma^k R_{\max} = \frac{R_{\max}}{1-\gamma}$ The geometric series converges!

Step 3: State-Value Function

The state-value function $V^\pi(s)$ is the expected return starting from state $s$ and following policy $\pi$ :

$V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$

Why expectation? Transitions are stochastic ( $P(s'|s,a)$ ), so we average over all possible futures.

Expanding: $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]$

Key insight: $G_{t+1}$ is itself a return from $S_{t+1}$ , so $\mathbb{E}[G_{t+1}|S_{t+1}=s'] = V^\pi(s')$ .

Step 4: Bellman Equation Derivation

$V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s]$

Under policy $\pi$ , we take action $a = \pi(s)$ deterministically (or sample from $\pi(a|s)$ for stochastic policies). For deterministic $\pi$ :

$V^\pi(s) = \sum_{s'} P(s'|s,\pi(s)) \left[ R(s,\pi(s),s') + \gamma V^\pi(s') \right]$

Breaking it down:

We're in state $s$ , policy says take action $\pi(s)$
Environment randomly picks next state $s'$ with probability $P(s'|s,\pi(s))$
We get immediate reward $R(s,\pi(s),s')$
Then we get discounted future value $\gamma V^\pi(s')$ from the new state

Step 5: Action-Value Function (Q-function)

Sometimes we want to know: "How good is taking action $a$ in state $s$ (and then following $\pi$ afterward)?"

Action-value function: $Q^\pi(s,a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a]$

Derivation: $Q^\pi(s,a) = \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^\pi(s') \right]$

Relationship to $V$ : $V^\pi(s) = Q^\pi(s, \pi(s))$

Optimal Policy and Bellman Optimality

Goal: Find the optimal policy $\pi^*$ that maximizes value for all states: $\pi^* = \arg\max_\pi V^\pi(s), \quad \forall s \in S$

Define optimal value functions: $V^*(s) = \max_\pi V^\pi(s)$ $Q^*(s,a) = \max_\pi Q^\pi(s,a)$

Deriving Bellman Optimality Equation

If $V^*(s)$ is the best possible value, then: $V^*(s) = \max_{a \in A} Q^*(s,a)$

Why? The optimal policy must pick the action with highest Q-value.

Substituting the Q-function expansion: $V^*(s) = \max_{a \in A} \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma V^*(s') \right]$

For Q-function: $Q^*(s,a) = \sum_{s'} P(s'|s,a) \left[ R(s,a,s') + \gamma \max_{a'} Q^*(s',a') \right]$

Optimal policy extraction: Once we have $V^*$ or $Q^*$ : $\pi^*(s) = \arg\max_a Q^*(s,a)$

Worked Examples

Worked example Example 1: Simple Grid World

Setup:

$S = \{s_1, s_2, s_3\}$ (3 states in a line)
$A = \{\text{left}, \text{right}\}$
Deterministic transitions: left moves left (unless at boundary), right moves right
$R(s_3, \text{any}, s_3) = +10$ (goal state), all other rewards = 0
$\gamma = 0.9$
Policy $\pi$ : always go right

Compute $V^\pi(s_1)$ : Step 1: Write Bellman equations for each state.

$s_1$ : Taking right → lands in $s_2$ with probability 1 $V^\pi(s_1) = 0 + 0.9 \cdot V^\pi(s_2)$

$s_2$ : Taking right → lands in $s_3$ with probability 1 $V^\pi(s_2) = 0 + 0.9 \cdot V^\pi(s_3)$ $s_3$ : Terminal state (self-loop with reward +10) $V^\pi(s_3) = 10 + 0.9 \cdot V^\pi(s_3)$

Step 2: Solve for $V^\pi(s_3)$ : $V^\pi(s_3) = 10 + 0.9 V^\pi(s_3)$ $0.1 V^\pi(s_3) = 10$ $V^\pi(s_3) = 100$

Why this step? Rearranging to isolate $V^\pi(s_3)$ on one side. The $1/(1-\gamma)$ term emerges from infinite geometric series of rewards at goal.

Step 3: Back-substitute: $V^\pi(s_2) = 0.9 \times 100 = 90$ $V^\pi(s_1) = 0.9 \times 90 = 81$

Intuition: From $s_1$ , we're 2 steps away from the goal, so value is discounted twice: $\gamma^2 \times V^\pi(s_3) = 0.81 \times 100 = 81$ .

Worked example Example 2: Stochastic Transitions

Setup: Same grid, but:

Taking "right" succeds 80% of time, stays in place 20%
$\gamma = 0.9$ Compute $V^\pi(s_2)$ with stochastic policy: From $s_2$ , action "right":
80% chance → $s_3$ (reward 0, then enter goal)
20% chance → $s_2$ (reward 0, stay put)

$V^\pi(s_2) = 0.8[0 + 0.9 V^\pi(s_3)] + 0.2[0 + 0.9 V^\pi(s_2)]$ We know $V^\pi(s_3) = 100$ (same as before): $V^\pi(s_2) = 0.8 \times 90 + 0.2 \times 0.9 V^\pi(s_2)$ $V^\pi(s_2) = 72 + 0.18 V^\pi(s_2)$ $0.82 V^\pi(s_2) = 72$ $V^\pi(s_2) = 87.8$

Why lower? Uncertainty means we might get stuck, so expected value decreases.

Worked example Example 3: Optimal Policy Selection

Setup:

State $s_1$ , two actions: $a_1$ (safe), $a_2$ (risky)
$a_1$ : deterministically reach $s_2$ with reward +5
$a_2$ : 50% reach $s_3$ (reward +20), 50% reach $s_4$ (reward -10)
Assume $V^*(s_2) = 50, V^*(s_3) = 80, V^*(s_4) = 30$
$\gamma = 1$ (no discount for simplicity)

Which action is optimal? $Q^*(s_1, a_1) = 5 + 1 \times 50 = 55$ $Q^*(s_1, a_2) = 0.5 \times (20 + 80) + 0.5 \times (-10 + 30)$ $= 0.5 \times 100 + 0.5 \times 20 = 50 + 10 = 60$

Answer: $a_2$ is optimal because $Q^*(s_1, a_2) = 60 > 55$ .

Why this step? We compute expected value under uncertainty: weight each outcome by its probability, sum immediate reward and future value.

Common Mistakes and Fixes

Memory Aids

Recall Feynman Explain-to-a-12-Year-Old

Imagine you're playing a board game. At each turn, you're on some square (that's the state). You pick a move (that's your action). The game has some randomness—maybe you roll a dice to see where you land (that's the transition probability). When you land, you get points or lose points (that's the reward).

Now, the Markov property says: only your current square matters for deciding your next move and where you'll land. You don't need to remember every square you visited before—just look at where you are now.

Your policy is your strategy: "When I'm on square X, I'll choose move Y." The value of a square is: "If I start here and play smartly, how many points will I get in total?" The discount factor is like saying "I care about points I'll get soon more than points far in the future."

The Bellman equation is just math for: "The value of my current square = points I get right now + (discounted) value of where I'll land next."

Finding the best strategy means: for every square, pick the move that leads to the highest total points. That's the optimal policy!

Connections

5.1.01-Reinforcement-Learning-Problem-Formulation - MDPs formalize theRL problem
5.1.03-Policy-and-Value-Functions - Deep dive into policies and values
5.1.04-Bellman-Equations - Detailed treatment of Bellman equations
5.2.01-Dynamic-Programming-inRL - Solving MDPs with DP methods
5.3.01-Monte-Carlo-Methods - Model-free estimation of $V$ and $Q$
5.3.02-Temporal-Difference-Learning - TD learning uses Bellman equation for online updates
5.4.01-Q-Learning - Uses Bellman optimality equation for Q-values
Markov-Chains - MDPs extend Markov chains by adding actions and rewards
Dynamic-Programming - MDP solution methods are DP algorithms

#flashcards/ai-ml

What is the Markov Property in an MDP? :: The probability of the next state depends only on the current state and action, not on the history: $P(s_{t+1}|s_t,a_t,s_{t-1},...) = P(s_{t+1}|s_t,a_t)$

What are the five components of an MDP?

States (S), Actions (A), transition Probability (P), Rewards (R), and discount factor (gamma)

What is the discount factor

\gamma

and why is it needed?

A value in [0,1) that makes future rewards worth less than immediate rewards. Needed for mathematical convergence (ensures finite sums), models uncertainty about the future, and controls howarsighted the agent is.

What is the state-value function

V^\pi(s)

The expected return (cumulative discounted reward) starting from state

s

and following policy

\pi

V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]

What is the action-value function

Q^\pi(s,a)

The expected return starting from state

s

, taking action

a

, then following policy

\pi

Q^\pi(s,a) = \mathbb{E}_\pi[G_t | S_t=s, A_t=a]

State the Bellman Expectation Equation for

V^\pi

V^\pi(s) = \sum_{s'} P(s'|s,\pi(s)) [R(s,\pi(s),s') + \gamma V^\pi(s')]

— value equals immediate reward plus discounted future value

State the Bellman Optimality Equation for

V^*

V^*(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V^*(s')]

— optimal value equals the maximum over actions of expected reward + discounted optimal future

How do you extract the optimal policy from

Q^*(s,a)

\pi^*(s) = \arg\max_a Q^*(s,a)

— pick the action with the highest Q-value in each state

What is the relationship between

V^\pi(s)

and

Q^\pi(s,a)

V^\pi(s) = Q^\pi(s, \pi(s))

— the value of a state equals the Q-value of the action the policy takes in that state

What is a policy in an MDP?

A mapping from states to actions

\pi: S \to A

(deterministic) or a probability distribution

\pi(a|s)

(stochastic) that defines the agent's behavior

\gamma = 0.9

and you're in a state 3 steps from a terminal reward of 100, what's the undiscounted contribution?

\gamma^3 \times 100 = 0.9^3 \times 100 = 0.729 \times 100 = 72.9

Why can't we use

\gamma = 1

in continuing tasks?

Because the infinite sum of rewards would diverge (infinite value), making the problem mathematically intractable unless all rewards are zero

What's the effective planning horizon for

\gamma = 0.95

Approximately

1/(1-\gamma) = 1/0.05 = 20

steps — that's how far into the future the agent effectively considers

True or False: The Markov property means the policy cannot use historical information :: False. The policy can use history if encoded in the state. The Markov property applies to environment dynamics, not policy design.

What's the difference between model-based and model-free RL in the context of MDPs?

Model-based knows

P(s'|s,a)

and

R(s,a,s')

(the MDP model) and can use planning. Model-free doesn't know these and must learn from experience.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Chalo, is concept ko simple tareeke se samajhte hain. MDP ka core idea yeh hai ki jab bhi tum koi decision lete ho—jaise video game khelte waqt—tumhare liye sirf abhi ki current situation matter karti hai, poori purani history nahi. Iss "memoryless" property ko hi Markov property kehte hain. Iska matlab: agar tum jaante ho abhi kahan ho (current state), toh next best move decide karne ke liye tumhe yeh yaad rakhne ki zarurat nahi ki tum yahan tak kaise pahunche. Yeh property complex problems ko manageable bana deti hai, kyunki hume infinite history track nahi karni padti—bas "yahan best action kya hai?" pe focus karo.

Ab MDP ek tuple hai $(S, A, P, R, \gamma)$ jismein states (kahan ho sakte ho), actions (kya choices hain), transition probability (action lene par kahan pahunchoge, thoda uncertainty ke saath), reward (kya achha ya bura hai, numbers mein) aur discount factor $\gamma$ (future rewards ki value aaj se kam) hote hain. Discount factor bahut important hai—yeh isliye lagate hain kyunki future uncertain hai, hum abhi ke reward ko zyada prefer karte hain, aur mathematically yeh infinite sum ko converge kara deta hai. Iske baad hum Value Function banate hain jo batati hai ki kisi state se start karke, ek policy follow karte hue, average mein kitna total reward milega.

Yeh matter kyun karta hai? Kyunki self-driving cars, game-playing AI (jaise AlphaGo), robotics, aur recommendation systems—yeh sab MDP framework pe hi chalte hain. Bellman equation jo humne derive ki— $V^\pi(s) =$ immediate reward $+$ discounted future value—yeh ek recursive relationship hai jo poore Reinforcement Learning ki neev hai. Ek baar tumne yeh intuition pakad li ki "aaj ki value = abhi ka reward + kal ki value ka discounted version," toh aage ke saare RL algorithms (Q-learning, policy gradients, sab) tumhe naturally samajh aane lagenge. Isliye yeh foundation rock-solid banana zaruri hai!

What is an MDP?

Deriving the Value Function from First Principles

Step 1: Total Return

Step 2: Discounted Return

Step 3: State-Value Function

Step 4: Bellman Equation Derivation

Step 5: Action-Value Function (Q-function)

Optimal Policy and Bellman Optimality

Deriving Bellman Optimality Equation

Worked Examples

Common Mistakes and Fixes

Memory Aids

Connections

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Reinforcement Learning Foundations

Connections