State-value and action-value functions

Overview

The state-value function and action-value function are the core tools for quantifying "how good" a state or action is under a given policy. They convert the abstract goal of "maximize future rewards" into concrete numbers we can compute and optimize.

[!intuition] Why do we need value functions?

An agent in state $s$ wants to know: "Should I stay or should I go?" But the answer depends on:

• Immediate reward from actions available now
• Future rewards from states we'll visit later
• The policy we're following (which actions we tend to take)

Value functions compress the infinite future into a single number: the expected cumulative reward from this point forward. This lets us compare states and actions numerically.

The key insight: Instead of simulating thousands of possible futures every time, we learn a function $V(s)$ or $Q(s,a)$ that memorizes "how good is this situation?"

[!definition] State-value function $V^\pi(s)$

The state-value function $V^\pi(s)$ is the expected return when starting in state $s$ and following policy $\pi$ thereafter:

$V^\pi(s) = \mathbb{E}_\pi\left[ G_t \mid S_t = s \right]$

where $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$ is the discounted return.

Breaking it down:

• $\mathbb{E}_\pi$: expectation over trajectories sampled by following policy $\pi$
• $G_t$: sum of future rewards, discounted by $\gamma \in [0,1]$
• $S_t = s$: we condition on starting in state $s$

What this tells us: $V^\pi(s)$ answers "If I'm in state $s$ and keep following my current policy $\pi$, what's my expected total reward?"

[!definition] Action-value function $Q^\pi(s,a)$

The action-value function (or Q-function) $Q^\pi(s,a)$ is the expected return when starting in state $s$, taking action $a$, and then following policy $\pi$:

$Q^\pi(s,a) = \mathbb{E}_\pi\left[ G_t \mid S_t = s, A_t = a \right]$

The difference from $V^\pi(s)$:

• $V^\pi(s)$: "How good is this state under policy $\pi$?"
• $Q^\pi(s,a)$: "How good is taking action $a$ in state $s$, then following $\pi$?"

$Q$ gives us action-level granularity. We can compare different actions in the same state.

[!formula] Relationship between $V$ and $Q$

Deriving $V$ from $Q$

If we know $Q^\pi(s,a)$ for all actions, we can compute $V^\pi(s)$ by averaging over the policy's action distribution:

$V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \, Q^\pi(s,a)$

Why this works:

1. $V^\pi(s)$ is the expected return when following $\pi$ from state $s$
2. Policy $\pi$ gives us a probability distribution over actions: $\pi(a|s)$
3. For each action $a$, the return is $Q^\pi(s,a)$
4. Expected value over actions: weight each $Q$ by its probability

Intuition: $V$ is the weighted average of all action-values, where weights are the policy's action probabilities.

Deriving $Q$ from $V$

We can express $Q$ in terms of $V$ using the one-step dynamics:

$Q^\pi(s,a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma V^\pi(s') \right]$

where $p(s', r | s, a)$ is the environment's transition probability.

Derivation from first principles:

Start with the definition: $Q^\pi(s,a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a]$

Expand the return $G_t$: $Q^\pi(s,a) = \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]$

Separate immediate and future rewards: $Q^\pi(s,a) = \mathbb{E}[R_{t+1} | S_t = s, A_t = a] + \gamma \mathbb{E}_\pi[G_{t+1} | S_t = s, A_t = a]$

The immediate reward depends only on $(s,a,',r)$ from the environment: $\mathbb{E}[R_{t+1} | S_t = s, A_t = a] = \sum_{s',r} p(s',r|s,a) \cdot r$

The future return $\mathbb{E}_\pi[G_{t+1} | S_t = s, A_t = a]$ depends on where we land. Condition on $s'$: $\mathbb{E}_\pi[G_{t+1} | S_t = s, A_t = a] = \sum_{s',r} p(s',r|s,a) \cdot \mathbb{E}_\pi[G_{t+1} | S_{t+1} = s']$

But $\mathbb{E}_\pi[G_{t+1} | S_{t+1} = s'] = V^\pi(s')$ by definition!

Combine: $Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^\pi(s') \right]$

Why this step? We're using the law of iterated expectation and the Markov property: the future return from $s'$ depends only on $s'$, not on how we got there.

[!formula] Bellman expectation equations

These are recursive consistency conditions that value functions must satisfy.

Bellman equation for $V^\pi$

$V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V^\pi(s') \right]$

Derivation:

1. Start with $V^\pi(s) = \sum_a \pi(a|s) Q^\pi(s,a)$ (averaging over actions)
2. Substitute $Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a)[r + \gamma V^\pi(s')]$
3. Result: $V^\pi(s)$ expressed in terms of $V^\pi(s')$ for successor states

Intuition: The value of state $s$ equals the immediate reward plus the discounted value of wherever you land next, averaged over your policy's action choices.

Bellman equation for $Q^\pi$

$Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a) \left[ r + \gamma \sum_{a'} \pi(a'|s') Q^\pi(s',a') \right]$

Derivation:

1. Start with $Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a)[r + \gamma V^\pi(s')]$
2. Substitute $V^\pi(s') = \sum_{a'} \pi(a'|s') Q^\pi(s',a')$
3. Result: $Q^\pi(s,a)$ in terms of $Q^\pi(s',a')$

Why recursive? Both equations express value functions in terms of themselves at successor states. This is the bootstrapping principle: we can solve for value functions iteratively.

[!example] Example 1: Gridworld state values

Consider a $3 \times 3$ gridworld. Agent starts anywhere, goal is top-right corner $(0,2)$. Actions: up, down, left, right. Deterministic. Reward: $-1$ per step, $+10$ at goal. $\gamma = 0.9$. Policy $\pi$: move right if possible, else move up.

Let's compute $V^\pi(s)$ for state $s = (1,1)$ (center).

Step-by-step:

1. Identify policy action: From $(1,1)$, $\pi$ says go right with probability 1.

2. Next state: $(1,2)$ (one step from goal)

3. Immediate reward: $r = -1$

4. Bellman equation: $V^\pi(1,1) = 1.0 \cdot [-1 + 0.9 \cdot V^\pi(1,2)]$

5. Compute $V^\pi(1,2)$: From $(1,2)$, policy goes up to $(0,2)$ (goal). $V^\pi(1,2) = 1.0 \cdot [-1 + 0.9 \cdot V^\pi(0,2)]$

6. At goal: $V^\pi(0,2) = 0$ (terminal state, no future rewards)

7. Back-substitute: $V^\pi(1,2) = -1 + 0.9 \cdot 0 = -1$ $V^\pi(1,1) = -1 + 0.9 \cdot (-1) = -1 - 0.9 = -1.9$

Why this step? Each application of the Bellman equation propagates value backward from the goal. The negative values reflect the cost of reaching the goal (each step incurs $-1$).

[!example] Example 2: Action values in a two-action state

State $s$, two actions: $a_1$ (safe), $a_2$ (risky). Stochastic outcomes.

$a_1$ (safe):

• 100% chance: next state $s'$, reward $r=1$

$a_2$ (risky):

• 70% chance: next state $s''$, reward $r=5$
• 30% chance: next state $s'''$, reward $r=-3$

Assume $V^\pi(s') = 10$, $V^\pi(s'') = 15$, $V^\pi(s'') = 2$. $\gamma = 1.0$ (undiscounted).

Compute $Q^\pi(s, a_1)$:

$Q^\pi(s, a_1) = .0 \cdot [1 + 1.0 \cdot 10] = 11$

Why? Deterministic transition, so the sum colapses to a single term.

Compute $Q^\pi(s, a_2)$:

$Q^\pi(s, a_2) = 0.7 \cdot [5 + 1.0 \cdot 15] + 0.3 \cdot [-3 + 1.0 \cdot 2]$ $= 0.7 \cdot 20 + 0.3 \cdot (-1) = 14 - 0.3 = 13.7$

Why this step? We weight each outcome by its probability. The risky action has higher expected value despite the negative outcome possibility.

Comparison: $Q^\pi(s, a_2) = 13.7 > Q^\pi(s, a_1) = 11$. If we're trying to improve the policy, we'd prefer $a_2$ in state $s$.

[!example] Example 3: Computing $V$ from $Q$ with a stochastic policy

State $s$, actions{a_1, a_2, a_3}$. Known Q-values:

• $Q^\pi(s, a_1) = 5$
• $Q^\pi(s, a_2) = 8$
• $Q^\pi(s, a_3) = 3$

Policy $\pi$:

• $\pi(a_1|s) = 0.5$
• $\pi(a_2|s) = 0.3$
• $\pi(a_3|s) = 0.2$

Compute $V^\pi(s)$:

$V^\pi(s) = \sum_a \pi(a|s) Q^\pi(s,a)$ $= 0.5 \cdot 5 + 0.3 \cdot 8 + 0.2 \cdot 3$ $= 2.5 + 2.4 + 0.6 = 5.5$

Why this step? The policy is stochastic, so we take a weighted average. $a_2$ has the highest Q-value but only 30% probability, so it contributes $0.3 \times 8 = 2.4$ to the overall value.

Insight: Even though $a_2$ is best, $V^\pi(s) = 5.5$ is less than $Q^\pi(s, a_2) = 8$ because the policy sometimes choses suboptimal actions.

[!mistake] Common mistake: Confusing $V$ and $Q$ in policy improvement

Wrong reasoning: "I'll compute $V^\pi(s)$ for all states, then pick the action that leads to the state with highest $V$."

Why it feels right: We want to go to valuable states, so picking the action that takes us to the highest-value next state seems logical.

Why it's wrong:

1. $V^\pi(s)$ already averages over the policy's action distribution. It doesn't tell you which action is best.
2. An action might lead to a high-value state but have a low immediate reward, making it worse overall.
3. The transition might be stochastic—you can't just "choose" the next state.

The fix: Use $Q^\pi(s,a)$ for action selection! Compute: $Q^\pi(s,a) = \sum_{s',r} p(s',r|s,a)[r + \gamma V^\pi(s')]$ for each action, then pick $\arg\max_a Q^\pi(s,a)$.

Why this works: $Q$ already accounts for:

• Immediate reward $r$
• Stochastic transitions via the sum over $s'$
• Future value via $V^\pi(s')$

Steel-man the mistake: The confusion arises because in deterministic environments with zero immediate reward, $V$ and $Q$ collapse to similar meanings. But in general, they're distinct!

[!mistake] Common mistake: Ignoring the policy in value function notation

Wrong statement: "The value function $V(s) = 10$."

Why it's wrong: Value functions are policy-dependent! Different policies lead to different values for the same state.

The fix: Always write $V^\pi(s)$ or specify which policy you mean. For the optimal policy $\pi^*$, write $V^*(s)$.

Example:

• Random policy $\pi_{\text{random}}$: $V^{\pi_{\text{random}}}(s) = 2$
• Optimal policy $\pi^*$: $V^*(s) = 10$

Same state, different values!

Why this matters: In policy evaluation, we compute $V^\pi$ for a fixed $\pi$. In policy optimization, we search for the $\pi$ that maximizes $V^\pi$.

[!recall]- Explain to a 12-year-old

Imagine you're playing a video game. You're at certain level (state). You want to know: "How good is my situation right now?"

$V(s)$ is like a score for your current level. It tells you, "If you keep playing the way you normally play, here's how many total points you'll probably get from now until the game ends." It's a single number that sums up your future.

$Q(s,a)$ is like a score for each possible move. It says, "If you press the jump button right now, here's how many points you'll get." Then, "If you press the shoot button, here's how many points you'll get." It helps you compare different moves.

The key difference: $V$ tells you how good your position is if you keep doing what you usually do. $Q$ tells you how good each specific choice is, so you can pick the best one!

Why we need both: Sometimes you want to know "Am I in a good spot overall?" (use $V$). Other times you want to know "Which button should I press?" (use $Q$).

[!mnemonic] Remember V vs Q

V = "Value of a Vacation spot"

• You're in Hawaii $(s)$. How good is being here overall? That's $V(s)$.
• Depends on your plans (policy): if you like beaches, Hawaii is great. If you hate sun, not so much!

Q = "Quality of a Quest"

• You're in Hawaii and deciding: swim, hike, or surf? Each choice has a quality score: $Q(s, \text{swim})$, $Q(s, \text{hike})$, $Q(s, \text{surf})$.
• Pick the highest $Q$ for the best experience.

V is where you are. Q is what you do.

Connections

• 5.1.03-Returns-and-episodes: Value functions compute the expected return $G_t$
• 5.1.05-Optimal-policiesand-optimal-value-functions: Optimal $V^*$ and $Q^*$ are value functions for the best policy
• 5.2.01-Dynamic-programming-policy-evaluation: Iterative algorithms solve Bellman equations for $V^\pi$
• 5.2.02-Policy-iteration: Uses $V^\pi$ and $Q^\pi$ to improve policies
• 5.3.01-Monte-Carlo-prediction: Estimates $V^\pi$ from sampled episodes
• 5.4.01-Temporal-difference-learning: Updates $V$ and $Q$ using bootstrapping from Bellman equations

#flashcards/ai-ml

What is the state-value function $V^\pi(s)$? :: The expected return (cumulative discounted reward) starting from state $s$ and following policy $\pi$ thereafter: $V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$

Concept Map

Hinglish (regional understanding)