Markov decision processes

A Markov decision process is the mathematical scaffolding of sequential decision making under uncertainty. An agent lives in a world of states, chooses actions, receives rewards, and moves to new states, and it wants to maximize long run reward. Every reinforcement learning problem I have worked on, from tank battles to chess to Minecraft, is at bottom an MDP, and the reason the abstraction is worth learning carefully is that once a problem is written as one, the entire theoretical toolkit applies to it: recursive value equations, dynamic programming, convergence guarantees, and the sample based methods that come later.

The word Markov does the heavy lifting. It means the future depends on the past only through the present state. Whatever happened before is already baked into where you are now, so a decision only ever needs to look at the current state. That single assumption is what makes the recursion in the next note possible, and when it fails, most of the guarantees fail with it.

Formal definition

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

$\mathcal{S}$ , the state space, the set of all configurations the environment can be in.
$\mathcal{A}$ , the action space, the set of actions the agent may take. This may depend on the state, written $\mathcal{A}(s)$ .
$P(s' \mid s, a)$ , the transition kernel, the probability of landing in $s'$ after taking action $a$ in state $s$ . For each $(s, a)$ this is a probability distribution over $\mathcal{S}$ , so $\sum_{s'} P(s' \mid s, a) = 1$ .
$R(s, a)$ , the reward function, the expected immediate scalar reward for taking $a$ in $s$ . Some texts write $R(s, a, s')$ and let the reward depend on the landing state too; the two are interchangeable by taking $R(s, a) = \sum_{s'} P(s' \mid s, a) R(s, a, s')$ .
$\gamma \in [0, 1)$ , the discount factor, which controls how future reward is weighed against immediate reward.

Throughout this folder I take $\mathcal{S}$ and $\mathcal{A}$ finite and rewards bounded, $|R(s, a)| \le R_{\max}$ . Almost everything extends to countable or continuous spaces with measure theoretic care, but the finite case is where the proofs are cleanest and it already contains every idea.

The Markov property

The defining assumption is that the next state and reward depend on the history only through the current state and action:

\Pr(s_{t+1} = s', r_{t+1} = r \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0, a_0) = \Pr(s_{t+1} = s', r_{t+1} = r \mid s_t, a_t).

The state is a sufficient statistic for the future. If the thing you are calling the state does not satisfy this, you are really working with a partially observable MDP, and the honest fix is to augment the state until it does: include velocity if you only had position, include the last few frames if a single frame is ambiguous, include a memory if the environment has hidden structure. The theory below assumes the augmentation has been done.

Trajectories, returns, and policies

Interaction generates a trajectory

\tau = (s_0, a_0, r_1, s_1, a_1, r_2, s_2, \dots),

where $s_0$ is drawn from a start distribution $\rho_0$ , each action is chosen by the agent, and each $(r_{t+1}, s_{t+1})$ is drawn from the environment given $(s_t, a_t)$ .

The discounted return from time $t$ is

G_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots

The return satisfies a recursion that the whole subject is built on:

G_t = r_{t+1} + \gamma G_{t+1}.

A policy $\pi$ maps states to distributions over actions, $\pi(a \mid s)$ . A policy is deterministic if it puts all its mass on one action, in which case I write $\pi(s) = a$ . A policy is stationary if it does not depend on $t$ . For discounted infinite horizon problems, stationary policies are enough, which is one of the results below.

Why discount

The discount factor is usually introduced as a modeling choice, a preference for reward now over reward later, and it is that. But it is also doing mathematical work, and both roles matter.

Convergence. With bounded rewards and $\gamma < 1$ , the return is an absolutely convergent series:

|G_t| \le \sum_{k=0}^{\infty} \gamma^k R_{\max} = \frac{R_{\max}}{1 - \gamma}.

Without the discount, an infinite horizon sum of rewards need not converge at all, and comparing two policies whose returns are both infinite is meaningless. The bound $R_{\max} / (1 - \gamma)$ shows up constantly in the proofs in this folder; it is the reason value functions live in a bounded set.

Contraction. In Bellman equations the same $\gamma$ becomes the contraction constant of the Bellman operator. Every convergence rate in this folder is a power of $\gamma$ , and the closer $\gamma$ is to one, the slower everything converges. That is the real cost of a long effective horizon.

Effective horizon. A useful way to read $\gamma$ is that the agent effectively cares about roughly $1 / (1 - \gamma)$ steps into the future. At $\gamma = 0.99$ that is a hundred steps; at $\gamma = 0.9$ it is ten.

Value functions

The state value function of a policy $\pi$ is the expected return starting from $s$ and following $\pi$ :

V^{\pi}(s) = \mathbb{E}_{\pi}\bigl[G_t \mid s_t = s\bigr].

The action value function, or Q function, conditions on the first action as well:

Q^{\pi}(s, a) = \mathbb{E}_{\pi}\bigl[G_t \mid s_t = s, a_t = a\bigr].

The subscript $\pi$ on the expectation means that all actions after the conditioning are drawn from $\pi$ and all transitions from $P$ . Because the policy is stationary and the dynamics are Markov, neither quantity depends on $t$ , which is why I can write them as functions of $s$ alone.

The two are linked in both directions. Averaging $Q^\pi$ over the policy's action choice gives $V^\pi$ :

V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a).

Taking one step and then averaging $V^\pi$ over the landing state gives $Q^\pi$ :

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

This second identity is the seed of the Bellman equation. Substituting one into the other produces the recursion that the next note is about.

Both value functions inherit the bound from the return: $|V^\pi(s)| \le R_{\max} / (1 - \gamma)$ and likewise for $Q^\pi$ .

Matrix form of the value function

For a fixed policy on a finite state space, everything is linear algebra. Let $v_\pi \in \mathbb{R}^{|\mathcal{S}|}$ be the vector of state values, $r_\pi$ the vector of expected immediate rewards under the policy,

r_\pi(s) = \sum_a \pi(a \mid s) R(s, a),

and $P_\pi$ the policy induced transition matrix,

P_\pi(s, s') = \sum_a \pi(a \mid s) P(s' \mid s, a).

$P_\pi$ is row stochastic: every entry is nonnegative and every row sums to one. The value function satisfies

v_\pi = r_\pi + \gamma P_\pi v_\pi,

which is the Bellman expectation equation in matrix form, and it can be solved directly:

v_\pi = (I - \gamma P_\pi)^{-1} r_\pi.

Why the inverse exists. Since $P_\pi$ is row stochastic, $\|P_\pi\|_\infty = 1$ , so $\|\gamma P_\pi\|_\infty = \gamma < 1$ . The Neumann series then converges,

(I - \gamma P_\pi)^{-1} = \sum_{k=0}^{\infty} (\gamma P_\pi)^k,

and reading that series term by term gives back the definition of the value function: $(\gamma P_\pi)^k r_\pi$ is the discounted expected reward $k$ steps in the future. The matrix inverse and the infinite sum are the same object, which is a nice check that the algebra means what it should.

Optimality

The optimal value functions are the best achievable over all policies:

V^*(s) = \sup_\pi V^\pi(s), \qquad Q^*(s, a) = \sup_\pi Q^\pi(s, a).

A policy $\pi^*$ is optimal if $V^{\pi^*}(s) = V^*(s)$ for every state $s$ simultaneously. It is not obvious that such a policy exists. The supremum is taken state by state, and a priori the policy that is best from one state might be different from the policy that is best from another.

The foundational result is that for a finite discounted MDP an optimal policy does exist, and it can be taken deterministic and stationary. You never need randomness or memory to act optimally. The proof goes through the Bellman optimality equation and is given in Bellman equations: $V^*$ is the unique fixed point of the optimality operator, and any policy that is greedy with respect to $V^*$ achieves it in every state at once.

One consequence worth stating plainly: a partial order on policies, $\pi \ge \pi'$ if $V^\pi(s) \ge V^{\pi'}(s)$ for all $s$ , has a maximum element. That is unusual for a partial order and it is special to MDPs.

Variants

Finite horizon. The return runs to a fixed $T$ and the discount can be dropped. The optimal policy is generally not stationary, because the right action with three steps left differs from the right action with thirty, and the state has to be augmented with the time index to recover the Markov structure.
Average reward. With $\gamma = 1$ and an infinite horizon, the objective becomes the long run average reward per step. This needs ergodicity assumptions on the chain and its own theory.
Continuous state and action spaces. Sums become integrals, the transition kernel becomes a density or a measure, and the same equations hold. In the linear dynamics, quadratic cost case they reduce to the Riccati equation of LQR.
Partial observability. The agent sees an observation $o_t$ that is a noisy function of $s_t$ . The belief state, the posterior over $s_t$ given the history, is itself Markov, so a POMDP is an MDP over beliefs, but the belief space is continuous and high dimensional.

Where this breaks

The two assumptions that do the most work are the Markov property and bounded rewards with $\gamma < 1$ . In practice the first is usually violated slightly (the state you have is almost sufficient) and the theory degrades gracefully. The second is violated by any environment with unbounded reward or by the choice $\gamma = 1$ without a terminating episode, and there the value function may not exist at all.

The other thing to be honest about is that knowing $P$ and $R$ is a strong assumption. The next two notes assume it. Temporal difference learning is the point where it is dropped.

References

Sutton, Barto. Reinforcement Learning: An Introduction, 2nd ed. MIT Press, 2018, chapter 3.
Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994.
Bellman. Dynamic Programming. Princeton University Press, 1957.