Foundations — Policies and value functions

This page assumes you have seen nothing. Every letter, arrow, and squiggle that the parent note Policies and value functions throws at you is built here, in order, each one leaning on the one before it.

---

0. The stage: agent, world, and the loop of time

Before any symbol, picture the game that everything else describes.

An agent (the decision-maker — the cyan dot) sits inside an environment (the world — the blueprint grid). Time ticks in whole steps: $t=0,1,2,3,\dots$. At each tick the agent looks, acts, and the world responds. That loop is the whole subject. Introduced properly in 5.1.01-Introduction-to-RL.

Everything below names a piece of this picture.

---

1. $t$ — the time index (subscript)

Plain words: a counter that says which tick we are on. A subscript like $S_t$ just means "the state at time $t$".

The picture: the row of tick-marks along the bottom of the figure above. $S_t$ is the dot's position at that tick; $S_{t+1}$ is where it is one tick later.

Why we need it: rewards arrive over time, and "later" rewards will matter less than "sooner" ones. Without a clock we could not even say "later".

---

2. $S$, $s$, and $S_t$ — states

Plain words: a state is a complete description of "the situation right now" — everything the agent needs to decide.

• $S$ (capital, no subscript) = the set of all possible situations.
• $s$ (lowercase) = one specific situation, a name we plug in, like $s_1$.
• $S_t$ = the random situation the agent actually finds itself in at time $t$.

The picture: each blueprint grid-cell is one state $s$. The whole grid is $S$. The cyan dot marks the current $S_t$.

Why we need it: value functions ask "how good is this situation?" — you cannot ask that without a way to name situations. Formalised in 5.1.02-Markov-Decision-Processes.

---

3. $A$, $a$, and $A_t$ — actions

Plain words: an action is a move the agent can make.

• $A$ = the set of all possible moves.
• $a$ = one named move (e.g. RIGHT, BUY).
• $A_t$ = the move actually taken at time $t$.

The picture: the four amber arrows leaving a grid-cell (up / down / left / right) — each arrow is one action $a$.

Why we need it: the agent influences its future only through actions. Rewards depend on which action you pick, so actions are how you steer.

---

4. $R$, $r$, and $R_{t+1}$ — reward

Plain words: a reward is a single number the world hands you after each move, saying "that was good (+) or bad (−)".

• $R_{t+1}$ = the (random) reward received one tick after acting at time $t$.
• $r$ = a specific number-value the reward can take, used when we sum over possibilities.

The picture: a number floating over the arrow the agent just took: +1, +2, -5.

Why we need it: reward is the only signal telling the agent what "good" means. The entire goal — value functions — is built from reward.

---

5. $\pi$ — the policy (the first notebook)

Plain words: the policy $\pi$ is the agent's strategy — a rule that turns a state into an action.

Two flavours:

flavour	notation	meaning
deterministic	$a=\pi (s)$	"in state $s$, always do action $a$"
stochastic	$\pi (a\mid s)$	"in state $s$, do action $a$ with probability $\pi (a\mid s)$"

The picture: below — the policy is the arrow assignment painted onto every cell of the map.

Reading $\pi (a\mid s)$: the vertical bar $\mid$ reads "given". So $\pi (a\mid s)$ = "the probability of picking $a$, given we are in $s$". Because it is a probability, for every state its numbers over all actions add to $1$: ${\sum }_a\pi (a\mid s)=1.$

Why we need it: the policy is what the agent does. Value functions are always measured while following a specific $\pi$ — that is what the little superscript in $V^{\pi }$ will mean.

---

6. $\sum$ — the summation sign

Plain words: $\sum$ (capital Greek sigma) means "add up a list".

${\sum }_{a}f(a)=f(a_1)+f(a_2)+\dots$

The symbol under the $\sum$ says what to sweep through (here, every action $a$).

The picture: a checklist where you write a number next to each item, then total the column.

Why we need it: an uncertain future has many branches. To get the average outcome we weight each branch by its probability and add them all — that is a sum.

---

7. $P(\cdot )$ and $p(s^{\prime },r\mid s,a)$ — probability and the world's dynamics

Plain words: $P(\text{event})$ is a number in $[0,1]$ measuring how likely something is. $0$ = never, $1$ = certain, $0.5$ = coin-flip.

The dynamics of the world are packed into one object: $p(s^{\prime },r\mid s,a)=P(S_{t+1}=s^{\prime },R_{t+1}=r|S_t=s,A_t=a).$

Read it: "the probability that, after doing $a$ in $s$, the world lands you in $s^{\prime }$ and pays reward $r$." The prime mark ${}^{\prime }$ in $s^{\prime }$ just means "the next one" — $s^{\prime }$ is the state after $s$.

The picture:

One state, one action, but several possible outcomes, each on its own branch with a probability that all together sum to $1$.

Why we need it: the same action can lead to different next-states. This object is the world's rulebook, and it is what every value equation averages over.

---

8. $\mathbb{E}$ — expectation (the average future)

Plain words: $\mathbb{E}[X]$ is the average value of a random quantity $X$, where each possible value is weighted by how likely it is: $\mathbb{E}[X]={\sum }_{\text{outcomes}}P(\text{outcome})\times (\text{value on that outcome}).$

The subscript in ${\mathbb{E}}_{\pi }[\cdot ]$ says "average over the randomness produced by following policy $\pi$" (and the world's dynamics).

The picture: stand at the branching tree of section 7, multiply each leaf's value by its probability, and add — the balance point of all futures.

Why we need it: "how good is this state" has no single answer — the future is uncertain. Expectation collapses all possible futures into one honest number.

---

9. $\gamma$ — the discount factor

Plain words: $\gamma$ (Greek "gamma"), a number in $[0,1]$, is how much you shrink a reward for each tick you must wait.

• A reward now counts fully.
• A reward one step later counts $\gamma$ times as much.
• Two steps later: ${\gamma }^2$. And so on.

The three reasons the parent gives:

1. Uncertainty — far-off rewards may never arrive.
2. Convergence — with $\gamma <1$ an infinite stream of bounded rewards still adds to a finite number.
3. Impatience — models "sooner is better", like interest in economics.

Edge cases (cover them all):

• $\gamma =0$: agent is totally short-sighted — it cares only about the very next reward $R_{t+1}$.
• $\gamma =1$: no discounting — every future reward counts fully (safe only when the game is guaranteed to end).
• $0<\gamma <1$: the usual case; distant rewards fade smoothly to nothing.

The geometric-series fact (used in every worked example): if you receive a constant reward $c$ forever, $c+\gamma c+{\gamma }^{2}c+\cdots =\frac{c}{1-\gamma }.$ This is exactly why $V^{\pi }(s_2)=\frac{2}{1-0.9}=20$ in the parent's example.

Why we need it: without $\gamma$, an endless game would give infinite value everywhere and "better" would lose all meaning.

---

10. $G_t$ — the return

Plain words: the return $G_t$ is the whole discounted pile of future reward, added up from time $t$ onward: $G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots ={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}.$

Reading the compact form: $k$ is a counter starting at $0$; ${\gamma }^k$ is the shrink-factor at that distance; $R_{t+k+1}$ is the reward $k$ steps in the future. Sweep $k=0,1,2,\dots$ and add.

The one trick that unlocks everything — peel off the first term: $G_t=R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\dots )=R_{t+1}+\gamma G_{t+1}.$ "This return = next reward + $\gamma$ times the next return." This recursion is the seed of every Bellman equation in 5.1.04-Bellman-Equations.

Why we need it: $G_t$ is what value functions take the average of. It is a single random number summarising an entire future.

---

11. $V^{\pi }(s)$ — the state-value function (the second notebook)

Plain words: the average return you can expect starting in state $s$ and behaving according to $\pi$: $V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s].$

The picture: paint a number on every grid-cell — "how much total good flows out of here if I follow $\pi$."

Why we need it: it is the critic — the score that lets us compare states and, later, improve the policy.

---

12. $Q^{\pi }(s,a)$ — the action-value function

Plain words: the average return if you start in $s$, force action $a$ right now, then follow $\pi$: $Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t\mid S_t=s,A_t=a].$

How it relates to $V$: average $Q$ over the actions the policy would take: $V^{\pi }(s)={\sum }_a\pi (a\mid s)Q^{\pi }(s,a).$

Why we need it (vs $V$): $Q$ is per action, so you can literally compare moves and pick the best — the foundation of 5.3.01-Q-Learning.

---

13. $\max$, $\arg \max$, and the star ${}^{\ast }$

Plain words:

• ${\max }_{a}f(a)$ = the largest value in the list $f(a_1),f(a_2),\dots$
• $\arg {\max }_{a}f(a)$ = which $a$ achieves that largest value (the winner's name, not the score).
• The star, as in $V^{\ast }$ or ${\pi }^{\ast }$, marks the best possible — the optimum.

The picture: a bar chart of $Q$-values; $\max$ is the height of the tallest bar, $\arg \max$ is the label under it.

${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a)\text{— “in state }s\text{, do the best-scoring action.”}$

Why we need it: learning aims at the best strategy. $\max$ picks the best score; $\arg \max$ turns that score back into an action to actually take. These drive 5.2.01-Policy-Iteration and 5.2.02-Value-Iteration.

---

How the foundations feed the topic

Read top to bottom: raw pieces (time, states, actions, reward) combine into the two big ideas — the policy and, through return + discount + expectation, the value functions — which finally give the optimal quantities.

---

Equipment checklist

Cover the right side and answer out loud before revealing.