Chapter 2: Markov Decision Processes

An MDP is written as a tuple of states $\mathcal{S}$, actions $\mathcal{A}$, dynamics $p$, reward function $R$ and discount $\gamma$. The dynamics and reward are often folded together into a single distribution over next-state-and-reward pairs, since the environment produces both at once. The discount factor is part of the problem definition rather than a hyperparameter of the algorithm, and this is worth stating plainly because it is routinely treated as a tuning knob: changing $\gamma$ changes which policy is optimal, so an agent tuned at one value is solving a different problem from one tuned at another.

The discount factor weights a reward received $k$ steps in the future by $\gamma^k$, and it serves three purposes at once. It keeps the return finite in problems that never terminate, it encodes a genuine preference for sooner rewards, and it bounds how far the consequences of an action need to be tracked. A useful rule is that the effective horizon is roughly $1/(1-\gamma)$ steps, so $\gamma = 0.99$ behaves like planning about a hundred steps ahead. Small $\gamma$ produces myopic agents that converge quickly; $\gamma$ near one produces far-sighted agents whose estimates carry much higher variance and converge far more slowly.

Because $p$ is a proper probability distribution, it sums to one over all next-state-and-reward pairs for each state-action pair. Everything else about the environment is derived from it: the expected reward for a state-action pair comes from marginalizing out the next state, and the state-transition probabilities from marginalizing out the reward. The stochasticity is what makes RL an optimization over expectations rather than over fixed trajectories, and that distinction has teeth. A deterministic planner can commit to a single best sequence of actions; an agent facing stochastic dynamics must instead commit to a policy that responds to whatever actually happens.

If $p$ is available the problem is one of planning, and dynamic programming can compute the optimal policy without ever interacting with the environment. If $p$ is unknown the agent must estimate values from experience, which is the model-free setting covering Chapters 4 through 8. A third option is to learn an approximate model from data and plan inside it, which buys sample efficiency at the risk of compounding model error: a small inaccuracy in one-step predictions grows rapidly when rolled forward, so plans made in a learned model can be confidently wrong in ways that plans made in real experience are not.

The state-value function $v_\pi(s)$ is the expected return starting from $s$ and following $\pi$; the action-value function $q_\pi(s,a)$ is the same but commits to action $a$ first. Each satisfies a recursion that averages over two independent sources of randomness — the policy's action choice and the environment's response. The action-value form is the more useful one for control, because choosing the best action from $q$ requires no model at all, while doing the same from $v$ requires knowing the dynamics. That asymmetry is not a minor convenience; it determines which quantity every model-free algorithm in this course chooses to learn.

For a finite MDP with a fixed policy, the Bellman expectation equation is a system of linear equations — one per state, each linear in the unknown values — and can therefore be solved exactly by matrix inversion. This is rarely done in practice because the cost is cubic in the number of states, but it matters theoretically for three reasons: it proves the value function exists, proves it is unique, and identifies it as the fixed point that the iterative methods of Chapter 3 converge to. Knowing a unique fixed point exists is what makes successive approximation a sound strategy rather than a hopeful one.

The optimal value function $v_*$ satisfies a recursion in which the agent takes the best action rather than an average one. Because of the max operator the equations are nonlinear and cannot be solved by matrix inversion, but they still have a unique solution for $\gamma < 1$. Crucially, once $q_*$ is known the optimal policy is trivial to extract: act greedily, with no search and no model required. All of the difficulty lies in finding $q_*$ rather than in acting on it, which is a useful thing to keep in mind when an algorithm looks complicated — the complexity is nearly always in the estimation, not the decision.

A useful and slightly surprising theorem: every finite MDP admits an optimal policy that is deterministic and stationary, needing no randomness and no dependence on time. Stochastic policies remain essential during learning because they drive exploration, and they become genuinely necessary in partially observable or multi-agent settings where the theorem's assumptions fail. But for the MDPs in this chapter the optimum is always attainable without flipping a coin. The theorem is about what the final answer may look like, not about how you are permitted to search for it — a distinction worth holding onto when Chapter 7 introduces deliberately stochastic policies.