Markov Decision Processes — Mathematics Knowledge System

Overview

A Markov Decision Process (MDP) is a mathematical framework for sequential decision-making under uncertainty. An agent observes the current state, takes an action, receives a reward, and transitions to a new state according to a Markov transition kernel that depends on the action. The goal is to find a policy (state-to-action mapping) that maximizes expected cumulative reward. MDPs underlie reinforcement learning, optimal control, operations research, and robotics.

Intuition

Think of an MDP as a game: at each step you observe where you are (state), choose a move (action), receive points (reward), and end up in a new position (next state). The rules only depend on where you are now and what you do (Markov property). A good strategy (policy) maps each state to a good action. The Bellman equation says: 'the value of a state = the immediate reward + the discounted value of where you end up.'

Formal Definition

Definition

An MDP is a tuple (S, A, P, R, gamma) where S is the state space, A is the action space, P(s'|s,a) is the transition kernel, R(s,a) is the expected reward, and gamma in [0,1) is the discount factor. A policy pi: S -> A (deterministic) or pi: S -> Delta(A) (stochastic) induces a Markov chain. The goal is to find pi* maximizing the expected discounted return.

V^\pi(s) = \mathbb{E}^\pi\!\left[\sum_{t=0}^\infty \gamma^t R(S_t, A_t) \,\Big|\, S_0 = s\right]

Value function under policy pi

V^*(s) = \max_\pi V^\pi(s)

Optimal value function

V^*(s) = \max_{a \in A}\left[R(s,a) + \gamma \sum_{s'} P(s'|s,a)V^*(s')\right]

Bellman optimality equation

Q^*(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a)\max_{a'} Q^*(s',a')

Q-value Bellman equation

\pi^*(s) = \operatorname*{arg\,max}_{a} Q^*(s,a)

Optimal policy from Q*

Notation

Notation	Meaning
$V^*(s)$	Optimal value function: maximum expected discounted return from state s
$Q^*(s,a)$	Optimal Q-function: expected return for taking action a in state s, then acting optimally
$\pi^*$	Optimal policy: arg max_a Q*(s,a)
$\gamma$	Discount factor in [0,1): weights future rewards

Theorems

Theorem 1: Theorem 1 (Bellman Optimality)

\text{The optimal value function } V^* \text{ is the unique fixed point of the Bellman operator } (TV)(s) = \max_a [R(s,a) + \gamma \sum_{s'} P(s'|s,a)V(s')]. \text{ Value iteration } V_{k+1} = TV_k \text{ converges to } V^* \text{ geometrically at rate } \gamma.

Theorem 2: Theorem 2 (Policy Improvement)

\text{Given a policy } \pi, \text{ define } \pi' \text{ by } \pi'(s) = \arg\max_a Q^\pi(s,a). \text{ Then } V^{\pi'}(s) \ge V^\pi(s) \text{ for all } s. \text{ Policy iteration (evaluate then improve) converges to } \pi^* \text{ in finitely many steps.}

Worked Examples

1
Consider the policy 'always stay'. Value equation: V(L) = 1 + 0.9 * V(L) => 0.1 V(L) = 1 => V(L) = 10. V(R) = 2 + 0.9 * V(R) => V(R) = 20.
$V^{\pi_{\text{stay}}}(L) = 10, \quad V^{\pi_{\text{stay}}}(R) = 20$
2
Check if moving is ever better. From L, move gives 0 + 0.9 * V(R) = 0.9 * 20 = 18 > 10. So it is better to move from L!
$Q(L, \text{move}) = 0 + 0.9 \cdot 20 = 18 > 10 = Q(L, \text{stay})$
3
Revised optimal policy: move from L (go to R), stay at R. Recompute: V(R) = 2 + 0.9 * V(R) => V(R) = 20. V(L) = 0 + 0.9 * V(R) = 18.
$\pi^*(L) = \text{move}, \quad \pi^*(R) = \text{stay}; \quad V^*(L) = 18, \quad V^*(R) = 20$

✓ Answer

Optimal policy: move from L, stay at R. V*(L) = 18, V*(R) = 20.

Practice Problems

Mediumfree response

Write the Bellman equation for V*(s) and explain each term.

Mediumfree response

Explain why policy iteration converges faster than value iteration in practice, even though both find the optimal policy.

Common Mistakes

Common Mistake

Confusing V(s) with Q(s,a)

V*(s) = max_a Q*(s,a). V is the value of being in state s (acting optimally), while Q*(s,a) is the value of being in state s and taking action a specifically.

Common Mistake

Assuming gamma = 1 always works

With gamma = 1, the infinite-horizon sum may diverge. gamma < 1 ensures convergence. For finite-horizon problems, gamma = 1 is fine, but the equations change.

Quiz

Summary

An MDP is (S, A, P, R, gamma): states, actions, transitions, rewards, discount.
Value function V*(s) = max_a [R(s,a) + gamma sum P(s'|s,a) V*(s')] (Bellman equation).
Algorithms: value iteration (gamma-contraction) and policy iteration (exact evaluation + greedy improvement).
Optimal policy: pi*(s) = arg max_a Q*(s,a).
MDPs are the foundation of reinforcement learning.

References

BookPuterman, M. L. -- Markov Decision Processes: Discrete Stochastic Dynamic Programming
BookSutton, R. S. and Barto, A. G. -- Reinforcement Learning: An Introduction
WebsiteWikipedia -- Markov decision process