Markov and Partially Observable Decision Processes › The Markov Decision Process

This section defines the MDP formally, states the Markov assumption, and explains discounting and horizons. Everything later in the book, from Kalman filters to large-scale world models, is best read as a variation on this template.

Each element answers a distinct question, and it helps to read the tuple that way. The state space $\mathcal{S}$ and initial distribution $\rho_0$ describe where the story can begin. The action set $\mathcal{A}$ describes what the agent can influence. The transition kernel $P$ describes how the world responds, capturing both physics and noise in a single conditional distribution. The reward function $R$ describes what matters, translating each transition into a score. Finally, the discount factor $\gamma$ describes how patient the agent is, a quantity whose full meaning emerges below. If you can locate all six pieces for a concrete problem, you have turned an informal description into a solvable decision problem.

The transition kernel is the world model in miniature: it answers the predictive question "if we do $a$ here, where do we end up?" The reward function answers the evaluative question "how much did that outcome help?" Notice the deliberate division of labor between the two: prediction is descriptive, evaluation is normative, and neither substitutes for the other. A fully specified MDP is therefore a complete decision problem, and much of this book is about learning or approximating its pieces from data. Later chapters differ mainly in which piece they learn and how they plan against the learned version, while the skeleton of the problem stays exactly as written above.

The adjective Markov refers to one assumption that does an enormous amount of work.

Why does this matter so much? Because it collapses an ever-growing history into a fixed-size summary. Without it, every quantity of interest would be indexed by a history $h_t$. At a fixed finite horizon, the history set is finite but grows exponentially whenever actions or observations branch. With an unbounded horizon, individual histories also grow without bound, so there is no fixed finite history table or fixed-size per-state recursion. Under the Markov property, by contrast, a policy only needs the current state, transition probabilities only need the current state and action, and the mathematics of planning becomes recursive rather than historical. Every efficient algorithm in this book, from value iteration to Kalman filtering to latent dynamics models, exploits some version of this compression.

It is worth being precise about what the Markov property does not claim. It does not claim the world is deterministic, nor that it is noiseless, nor even that the state is small. Stochasticity survives fully intact inside $P(s' \mid s, a)$; the property constrains what the probabilities condition on, not how random they are. Nor does it claim the agent's chosen representation is automatically adequate. It claims only that the chosen state representation is predictively sufficient: no information relevant to the future is missing from it. Whether a given representation satisfies this is an empirical property of the environment paired with the representation, and Section "When the Markov Assumption Fails" examines what happens when it does not hold.

There is also a constructive reading worth internalizing: the Markov property is something you can often engineer. If position alone fails to predict next position, include velocity; if velocity fails, include acceleration; if battery charge matters, measure it. Each enrichment costs dimensionality, so practical modeling is a negotiation between sufficiency and tractability. That negotiation recurs throughout this book wherever learned latent representations stand in for engineered features.

The agent does not care about individual rewards so much as about their accumulated total. The quantity of interest is the return $G_t$, the total discounted reward from time $t$ onward:

For episodic tasks that terminate, such as our delivery robot finishing its route, the sum simply stops at the terminal time step. For continuing tasks that never end, the discount factor $\gamma$ serves two purposes at once, and understanding both prevents a lot of confusion.

First, $\gamma$ is an economic preference for earlier reward. With $\gamma = 0.9$, a reward arriving ten steps from now counts about $0.9^{10} \approx 0.35$ as much as the same reward today. This mirrors interest rates and time preferences in economics, and in many applications it encodes the fact that sooner is better: energy spent today cannot be reclaimed by reward promised tomorrow. Second, and more technically, $\gamma$ guarantees that the infinite sum stays finite and that the optimization problem is well posed. As long as rewards are bounded and $\gamma < 1$, the return is bounded by $r_{\max}/(1-\gamma)$. Without this guarantee, summing rewards forever could diverge, and two infinite quantities could not be compared; with it, every policy receives a finite score and there is always a well-defined best one to seek.

The quantity $1/(1-\gamma)$ is called the effective horizon: it measures how many future steps materially influence decisions. With $\gamma = 0.9$ the effective horizon is 10 steps; with $\gamma = 0.99$ it is 100. Choosing $\gamma$ is therefore not a numerical detail but a modeling statement about how far ahead the agent should reason. Set it too low and a greedy agent will happily sprint toward a pit because tomorrow's catastrophe is discounted away; set it too high and planning becomes computationally expensive and statistically fragile, since values then depend on chains of many uncertain predictions. We will see in the value iteration experiments that $\gamma$ bounds the worst-case contraction rate of Bellman backups, while the transition structure can make actual convergence substantially faster. It therefore sits at the junction of modeling intent and algorithmic cost.

The abstract discussion of discounting becomes much clearer when drawn. The next figure shows how much a unit of reward is worth as a function of how far in the future it arrives, for several values of $\gamma$.