Foundations — State-value and action-value functions

This page assumes you have seen NONE of the notation in the parent note. We build every symbol from the ground up, in the order they depend on each other. Nothing is used before it is drawn.

Parent topic: State-value and action-value functions · Hinglish version: 5.1.04 State-value and action-value functions (Hinglish)

---

The picture everything lives in: an agent walking through states

Before any symbol, here is the world we are describing.

An agent (the little dot) sits in a situation. It picks a move. The world responds: it hands the agent a small reward (a number) and drops it into a new situation. Then it repeats — until the game reaches an ending (a terminal state) or, in some games, forever.

Everything in this topic is just careful bookkeeping of that loop. Let us name each part.

---

Symbol 0 — random variables (the idea behind every capital letter)

Before naming anything, one background idea that everything rests on.

The picture: a die mid-roll. While it tumbles it is the random variable $X$; the moment it lands showing a $4$, that landed value is $x=4$.

Why the topic needs it: in reinforcement learning, states, actions, and rewards are all decided partly by chance. So each gets a capital-letter random variable ($S_t$, $A_t$, $R_t$) for "not yet decided" and a lowercase version ($s$, $a$, $r$) for "a specific value it might take".

---

Symbol 1 — the state $s$ and the state space $\mathcal{S}$

The picture: figure s01's grid. One highlighted square is a state $s$. The whole grid of squares together is the state space $\mathcal{S}$; every $s$ is one member, written $s\in \mathcal{S}$ ("$s$ is in $\mathcal{S}$").

Why the topic needs it: value functions grade each state, so we need (a) a symbol for "this spot" ($s$) and (b) a symbol for "the collection of all spots" ($\mathcal{S}$), because a value function is really a rule assigning a number to every member of $\mathcal{S}$.

• Lowercase $s$ ::: a particular, named state (like the center square)
• Uppercase $S_t$ ::: a random variable — the state you end up in at step $t$
• Curly $\mathcal{S}$ ::: the set of all possible states; $s\in \mathcal{S}$

---

Symbol 2 — time steps $t$ and the subscript notation

The picture: frames of a filmstrip. Frame $t$, frame $t+1$, frame $t+2$, laid left to right.

Why: rewards arrive at different times, and we will treat "now" and "later" differently. We need a clock to tell them apart.

---

Symbol 3 — the action $a$ and the action set $\mathcal{A}$

The picture: four arrows leaving the agent's square. Each arrow is one element of $\mathcal{A}$.

Why: an action-value function grades moves, so we need a name for a move.

---

Symbol 4 — the reward $R$ and the discount $\gamma$

Why a discount at all — why this tool and not just adding rewards up? Two reasons, both in figure s02:

1. Infinity. If the game never ends and you just sum rewards, the total can blow up to infinity — then "which state is better" becomes meaningless. Multiplying by ${\gamma }^k$ (with $\gamma <1$) makes even an infinite sum settle to a finite number, because ${\gamma }^0+{\gamma }^1+{\gamma }^2+\dots$ converges.
2. Impatience. A reward now is worth more than the same reward in a hundred steps. $\gamma$ encodes exactly how patient the agent is.

• $\gamma =0$ ::: totally short-sighted — only the very next reward matters
• $\gamma \to 1$ ::: far-sighted — a reward 50 steps away counts almost fully
• Why $\gamma <1$ keeps infinite sums finite ::: geometric series $\sum {\gamma }^k=\frac{1}{1-\gamma }$ converges only for $\gamma <1$
• When is $\gamma =1$ allowed? ::: only when the game always terminates, so the sum has finitely many terms

---

Symbol 5 — terminal states and episodes

Before we add rewards up, we must know when the adding stops.

The picture: figure s01 — the goal square (top-right) is terminal; the little dot's whole path from start to that square is one episode. In an absorbing state, all arrows loop back to itself with reward $0$, so it "absorbs" the agent.

How this fixes $G_t$ at the ending: once you reach a terminal state at some tick $T$, every reward $R_{T+1},R_{T+2},\dots$ is $0$. So the infinite sum in $G_t$ automatically truncates to a finite number of nonzero rewards. That is exactly why $\gamma =1$ is safe for episodic (terminating) games.

• What is a terminal state's value? ::: $0$ — there is no future reward left to collect
• What is an episode? ::: one full run from a start state to a terminal state
• Why can episodic games use $\gamma =1$? ::: the reward stream ends, so the sum has finitely many terms

---

Symbol 6 — the return $G_t$

Now we stack the discounted rewards into one grand total.

Reading the symbols one at a time:

• ${\sum }_{k=0}^{\infty }$ — "add up the following for $k=0,1,2,\dots$". The big $\Sigma$ is Greek "S" for Sum. In an episode the sum stops naturally once you hit a terminal state (all later rewards are $0$).
• ${\gamma }^k$ — the shrink factor for a reward $k$ steps into the future.
• $R_{t+k+1}$ — the reward received $k+1$ ticks after now.

The picture: figure s02's staircase — each future reward is a bar, each bar squashed shorter than the last by the ${\gamma }^k$ ladder, then all bars added.

Why the topic needs it: $G_t$ is the actual number we care about — total (discounted) reward from here on. But $G_t$ depends on the specific dice rolls of one episode. To get a stable grade for a state we must average many episodes — which is the next symbol.

---

Symbol 7 — the policy $\pi$

The picture: figure s03 — from one square, arrows of different thickness leave; thickness = probability. A thick "right" arrow and a thin "up" arrow means "I usually go right".

Why the vertical bar $\mid$? It reads "given". $\pi (a\mid s)$ = "chance of $a$, given you're in $s$". The bar always separates what we're asking about (left) from what we already know (right).

• A deterministic policy ::: one action gets probability $1$, all others $0$
• A stochastic policy ::: probabilities split across several actions, summing to $1$

---

Symbol 8 — trajectories and expectation $\mathbb{E}$

First, the object we will average over.

Tiny example (this is the whole idea): flip for $10 with 70% chance, lose $1 with 30% chance. $\mathbb{E}=0.7\times 10+0.3\times (-1)=6.7$ You never actually get 6.7 — it's the long-run average.

Why the subscript ${\mathbb{E}}_{\pi }$? The averaging is taken over trajectories the agent produces while following policy $\pi$. Change the policy → the trajectories change → the average changes. The subscript reminds us "these trajectories were generated by strategy $\pi$".

Why this exact tool and not just $G_t$? $G_t$ is one lucky (or unlucky) trajectory. ${\mathbb{E}}_{\pi }[G_t]$ smooths over all trajectories to give one trustworthy grade. Value functions are defined as expectations for precisely this reason.

---

Putting the symbols together — the two value functions

Now every ingredient exists, we can read the parent's headline definitions with zero mystery.

The only difference: $Q$ pins down the first action too; $V$ lets the policy pick it. Everything after step one is identical.

• Superscript $\pi$ ::: "graded while following policy $\pi$" — a different policy gives a different grade
• Condition $\mid S_t=s$ ::: "given we start in $s$"
• Extra condition $,A_t=a$ ::: "and given the first move is forced to be $a$"

---

How the foundations feed the topic

Each arrow means "you must understand the source before the target makes sense". Notice value functions sit near the bottom because they need all the earlier pieces. Once you have them, the optimal value functions and the algorithms that estimate them — dynamic programming, Monte-Carlo prediction, and temporal-difference learning — become reachable.

---

A 30-second sanity check with all symbols live

Say from state $s$ the policy is "go right for sure": $\pi (\text{right}\mid s)=1$. That move pays $R_{t+1}=-1$ and lands you in $s^{\prime }$ where $V^{\pi }(s^{\prime })=-1$, with $\gamma =0.9$.

$V^{\pi }(s)=\underset{\pi (\text{right}\mid s)}{\underbrace{1.0}}\times [\underset{R_{t+1}}{\underbrace{-1}}+\underset{\gamma }{\underbrace{0.9}}\times \underset{V^{\pi }(s^{\prime })}{\underbrace{(-1)}}]=-1.9$

Every symbol on this page appears here. If you can read that line, you are ready for the parent note.

---

Equipment checklist

Cover the right side and see if you can state each from memory.

• What is a random variable, and how is it written? ::: a quantity not yet decided by chance; written as a capital letter, its realised value lowercase
• What does a state $s$ represent? ::: a full snapshot of your current situation — all you need to choose a move
• What is the state space $\mathcal{S}$? ::: the set of all possible states; $s\in \mathcal{S}$
• Capital $S_t$ vs lowercase $s$? ::: $S_t$ is the random state-at-time-$t$; $s$ is one specific named state
• What is an action $a$, and what is $\mathcal{A}$? ::: a chosen move; $\mathcal{A}$ is the full menu of legal moves
• What is a terminal state and its value? ::: an ending square where the game stops; its value is $0$
• What is an episode? ::: one full run from a start state to a terminal state
• When is $\gamma =1$ allowed, and when must $\gamma <1$? ::: $\gamma =1$ only if the game always terminates; otherwise $\gamma <1$ to keep the infinite sum finite
• What does the subscript on $R_{t+1}$ tell you? ::: the reward for acting at tick $t$ is paid on the next tick, $t+1$
• Why do we multiply future rewards by ${\gamma }^k$? ::: to keep infinite sums finite and to make the agent value sooner rewards more
• Write the return $G_t$ from memory. ::: $G_t={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$
• What is a trajectory? ::: the recorded sequence of states, actions, and rewards in one episode
• What does $\pi (a\mid s)$ mean? ::: probability of choosing action $a$ given you are in state $s$
• What does the vertical bar $\mid$ read as? ::: "given" — separates what we ask about from what we already know
• What does ${\mathbb{E}}_{\pi }[\cdot ]$ compute? ::: the probability-weighted average over trajectories produced by policy $\pi$
• In one sentence, what is $V^{\pi }(s)$? ::: expected total discounted reward from $s$ while following $\pi$
• How does $Q^{\pi }(s,a)$ differ from $V^{\pi }(s)$? ::: $Q$ forces the first action to be $a$; $V$ lets $\pi$ pick it