Markov Decision Processes — Section 8: Decision Making Under Uncertainty

An MDP is a tuple $(S, A, P, R, \gamma)$ :

$S$ : states.
$A$ : actions.
$P(s' | s, a)$ : transition probabilities.
$R(s, a)$ or $R(s, a, s')$ : reward.
$\gamma \in [0, 1)$ : discount factor.

A policy $\pi: S \to A$ maps states to actions. The value of a policy at state $s$ is the expected discounted sum of rewards starting from $s$ and following $\pi$ :

V^\pi(s) = \mathbb{E}\left[\sum_{t=0}^\infty \gamma^t R(s_t, \pi(s_t)) \,\middle|\, s_0 = s\right]

Why discount?

Mathematical convenience: infinite sums converge when $\gamma < 1$ .
Models impatience: rewards now are worth more than rewards later.
Models uncertainty about the future: with each step, more probability of "the world ending" before you collect the reward.

For episodic tasks with guaranteed termination, $\gamma = 1$ is fine. For continuing tasks, $\gamma$ between 0.9 and 0.99 is standard.

Bellman equations

For value of a policy:

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

For the optimal value (Bellman optimality equation):

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

A policy $\pi^*$ is optimal iff $V^{\pi^*} = V^*$ .

Action-value (Q-) function

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

The optimal Q-function $Q^*(s, a)$ satisfies $V^*(s) = \max_a Q^*(s, a)$ . A greedy policy w.r.t. $Q^*$ is optimal — and importantly, you don't need to know the transition model to act optimally if you have $Q^*$ . That's what makes Q-learning model-free.

Partial observability (POMDPs)

Extend by adding observations $o$ and emission probabilities $P(o | s)$ . The agent doesn't see the state directly. Belief state — a distribution over states — replaces the state for policy purposes. POMDPs are dramatically harder to solve than MDPs; exact solution is undecidable in general.

When MDPs are the right model

The state transitions and rewards are well-defined.
The state is observable (or close enough).
You can iterate to compute the value function or learn a policy from experience.

When they're a bad fit: continuous state spaces without good function approximation, partially observable problems with complex belief updates, environments with rich language input. For these you need POMDPs, deep RL, or more bespoke frameworks.