Foundations — Markov Decision Processes (MDP)

Before you touch value functions or Bellman equations, you must be able to read every squiggle the parent note writes without pausing. This page builds each one from nothing, in an order where every symbol is earned before it is used. Nothing here contradicts the parent — it is the ground floor under it.

0. The world as dots and arrows

Everything in an MDP can be drawn as dots connected by labelled arrows. Keep this picture in your head for the whole page.

• A dot = a situation the agent can be in.
• An arrow = "if you do this action, you might end up over there."
• Each arrow carries a chance (how likely) and a payoff (how much reward).

That is the entire object. The rest is naming the parts. Once we have named all five parts, we bundle them together and call the bundle an MDP:

1. The set $S$ — states

Plain words. A state is "the current screen of the video game."

The picture. Each dot in the figure above is one state. $S$ is the whole bag of dots.

Why the topic needs it. Without a fixed idea of "where am I," there is nothing to attach a decision to. States are the nouns of the problem.

Notation you'll meet:

• $s$ — a generic state (a single dot).
• $s^{\prime }$ (read "s-prime") — the next state, the dot an arrow points to. The little tick mark just means "the new one."
• $s_t$ — the state at time step $t$ (see §7). So $s_0,s_1,s_2,\dots$ is the agent's actual trip through the dots.

2. The set $A$ — actions

Plain words. In a maze: move up, down, left, right. Those four choices are $A$.

The picture. From one dot, each action is a bundle of arrows leaving that dot. In our line-world, action right is one arrow group, left is another.

Why the topic needs it. Actions are the only thing the agent controls. They are the verbs. The whole point of the topic is to choose them well.

Notation: $a$ = a generic action; $a_t$ = the action taken at time $t$.

3. Probability, and the symbol $P(s^{\prime }\mid s,a)$

Before we can read the transition symbol, we must be sure about the word probability and the bar $\mid$.

Now the transition symbol reads itself:

Why not just one arrow per action? Because the world can be random. In the figure, taking right from $s_2$ has an $0.8$ arrow to $s_3$ and a $0.2$ arrow back to $s_2$. This is exactly the stochastic Example 2 in the parent. $P$ is the tool that encodes "acting doesn't guarantee an outcome."

Sanity check on $P$: for any fixed $s$ and $a$, adding the chances of all next states gives ${\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)=1$ — from every dot, something must happen.

4. The reward function $R(s,a,s^{\prime })$

The picture. The reward is the label on the arrow — the little "+10" or "0" written on it in the figure.

Why the topic needs it. Rewards are how a goal becomes math. "Reach the exit" turns into "give $+10$ on the arrow into the exit dot." The agent has no idea what you want except through these numbers.

5. The Greek letter $\gamma$ — discount factor

The picture. Think of every future reward as a coin that fades a little each step. A reward $k$ steps away is worth only ${\gamma }^k$ of its face value.

Why the topic needs it. Three reasons (all in the parent):

1. The far future is uncertain, so it should count less.
2. Impatience — a reward now beats the same reward later.
3. Convergence — an endless sum of rewards would blow up; multiplying by ${\gamma }^k$ tames it.

Why $\gamma <1$ makes infinite sums finite. This is the one bit of algebra you must own. A geometric series is a sum where each term is the previous one times a fixed ratio: $1+\gamma +{\gamma }^2+{\gamma }^3+\cdots =\frac{1}{1-\gamma }(\text{valid when }0\le \gamma <1).$

That $\frac{1}{1-\gamma }$ is why the parent's Example 1 gets $V(s_3)=\frac{10}{1-0.9}=100$: an infinite stream of $+10$ each shrunk by $\gamma$ sums to a finite $100$. Whenever you see $\frac{1}{1-\gamma }$ later, this is the picture it came from.

6. Summation $\sum$ and expectation $\mathbb{E}$

Two symbols do the heavy lifting in every Bellman equation. Meet them now.

Why the topic needs both. Because transitions are random ($P$), the return is a random quantity. We cannot report a single guaranteed number, so we report the average over all possible futures — that is $\mathbb{E}$, and it is computed by summing $P\times (\text{value})$ over next states. Every Bellman equation is literally an expectation written out as a sum.

Tiny concrete example (matches parent Example 3's risky action): $\mathbb{E}[\text{reward}]=0.5\times (20)+0.5\times (-10)=10-5=5.$ Half a chance of $+20$, half of $-10$, average $+5$.

${\mathbb{E}}_{\pi }[\cdot ]$ with a little $\pi$ underneath just means "the average, assuming actions are chosen by policy $\pi$" (next section).

7. Time steps $t$ and the return $G_t$

The picture. A row of stopwatch ticks. The convention that reward for the step from $t$ has subscript $t+1$ is just bookkeeping: "the payoff arrives with the next state."

Now we can name the quantity the whole topic is trying to maximise — the return.

Why the topic needs it. $G_t$ is the score the agent chases. It is random (the rewards depend on random transitions), which is exactly why the value functions in 5.1.03-Policy-and-Value-Functions take its expectation $\mathbb{E}[G_t]$. Every symbol on this page exists to make this single sum well-defined and finite: $t$ says where to start counting, $R$ supplies the terms, and $\gamma$ guarantees it converges.

8. The Markov property (the reason it's an MDP)

The picture. Cross out the whole tail of past dots — the branching probabilities from the current dot don't change one bit.

Why the topic needs it. This is the assumption that makes everything solvable. Because the next step depends only on now, we can talk about "the value of a state" as a single well-defined quantity, instead of "the value of this entire 4000-step history." It shrinks an infinite bookkeeping problem to one number per dot. This idea is the same one behind Markov-Chains; an MDP is a Markov chain with choices and rewards bolted on.

9. Policy $\pi$ — the strategy

The picture. Paint one chosen out-arrow at every dot; that colouring is a deterministic policy. Follow the paint and you get a path.

Why the topic needs it. The policy is the answer the whole topic is searching for. Actions ($A$) are what's possible; the policy is what's decided. Value functions (built in 5.1.03-Policy-and-Value-Functions) always measure "how good is this policy." The best one is ${\pi }^{\ast }$ (§10). Details live in 5.1.03-Policy-and-Value-Functions.

10. The star $\ast$ and $\arg \max$

Two final marks close the alphabet.

Why the topic needs them. Optimal control = "pick the action that leads to the best future." That sentence is exactly ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)$. The $\max$ inside the Bellman optimality equation is where "just averaging" becomes "actively choosing the best." These power 5.1.04-Bellman-Equations and the algorithms in 5.2.01-Dynamic-Programming-inRL, 5.4.01-Q-Learning.

How the foundations feed the topic

Everything on the left is a symbol built on this page; everything on the right is what the parent note does with them.

Equipment checklist

Cover the right side and try to answer aloud.