Bellman equations

WHY they matter: In RL, an agent needs to know "how good is this state?" or "how good is this action?". The Bellman equations give us a way to compute these values by bootstrapping—using estimates of future values to improve current estimates. This is dynamic programming at its core.

WHAT they describe: The expected return (cumulative discounted reward) from any state or action pair, expressed in terms of immediate reward and the value of successor states.

HOW they work: By decomposing the infinite-horizon value into one-step reward + discounted future value, we turn an intractable sum into a recursive formula that can be solved iteratively.

Derivation from First Principles

$V^\pi(s) = \mathbb{E}_\pi\left[\sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0 = s\right]$

where $\gamma \in [0,1)$ is the discount factor, $R_{t+1}$ is the reward at time $t+1$, and the expectation is over trajectories generated by policy $\pi$.

WHY this definition? We care about long-term cumulative reward, but distant rewards matter less (discount factor). The expectation accounts for stochasticity in both the environment and policy.

Bellman Equation for $V^\pi$ (State Value)

Goal: Express $V^\pi(s)$ recursively.

Step 1: Expand the return sum: $V^\pi(s) = \mathbb{E}_\pi\left[R_1 + \gamma R_2 + \gamma^2 R_3 + \cdots \mid S_0 = s\right]$

Step 2: Factor out the first reward: $V^\pi(s) = \mathbb{E}_\pi\left[R_1 \mid S_0 = s\right] + \mathbb{E}_\pi\left[\gamma(R_2 + \gamma R_3 + \cdots) \mid S_0 = s\right]$

Why this step? We're separating the immediate reward (which happens now) from the future rewards (which depend on where we go next).

Step 3: Recognize that the second term is the discounted value of the next state $S_1$: $V^\pi(s) = \mathbb{E}_\pi[R_1 \mid S_0 = s] + \gamma \mathbb{E}_\pi[V^\pi(S_1) \mid S_0 = s]$

Step 4: Expand the expectation over actions and transitions: The policy gives us $\pi(a|s)$, the dynamics give us $p(s', r | s, a)$:

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

Interpretation: The value of state $s$ under policy $\pi$ equals the weighted average (over actions chosen by $\pi$) of the expected immediate reward plus discounted next-state value.

Bellman Equation for $Q^\pi$ (Action Value)

$Q^\pi(s, a) = \mathbb{E}_\pi\left[\sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0 = s, A_0 = a\right]$

WHY? Sometimes we need to evaluate specific actions (e.g., in Q-learning). $Q$ tells us "how good is action $a$ in state $s$?".

Derivation:

Step 1: Condition on taking action $a$ first: $Q^\pi(s, a) = \mathbb{E}\left[R_1 + \gamma V^\pi(S_1) \mid S_0 = s, A_0 = a\right]$

Why? After taking $a$, we transition to $S_1$ and then follow policy $\pi$, which gives us $V^\pi(S_1)$.

Step 2: Expand over environment dynamics: $Q^\pi(s, a) = \sum_{s', r} p(s', r | s, a) \left[r + \gamma V^\pi(s')\right]$

Step 3: Express $V^\pi(s')$ in terms of $Q^\pi$: $V^\pi(s') = \sum_{a'} \pi(a'|s') Q^\pi(s', a')$

Step 4: Substitute back:

Bellman Optimality Equations

GOAL: Find the best possible policy $\pi^*$ and its value functions $V^*(s)$ and $Q^*(s, a)$.

KEY INSIGHT: The optimal policy is greedy with respect to $V^*$ or $Q^*$: $\pi^*(s) = \arg\max_a Q^*(s, a)$

Derivation of Bellman Optimality for $V^*$:

Step 1: The optimal policy chooses the best action: $V^*(s) = \max_a Q^*(s, a)$

Step 2: Substitute the $Q^*$ definition: $V^*(s) = \max_a \sum_{s', r} p(s', r | s, a) \left[r + \gamma V^*(s')\right]$

Why the max? We're no longer following a fixed policy—we're choosing the action that maximizes value at each step.

Derivation of Bellman Optimality for $Q^*$:

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

Worked Examples

Compute $V^\pi(s_1)$ using the Bellman equation.

Step 1: Write the Bellman equation for $s_1$: $V^\pi(s_1) = \sum_a \pi(a|s_1) \sum_{s', r} p(s', r | s_1, a) \left[r + \gamma V^\pi(s')\right]$

Step 2: Assume $s_1$ can move right to $s_2$ or down to $s_3$, and hitting walls keeps you in place:

• Action "right": goes to $s_2$, reward $-1$
• Action "down": goes to $s_3$, reward $-1$
• Actions "left", "up": stay at $s_1$, reward $-1$

Step 3: Substitute: $V^\pi(s_1) = 0.25[(-1) + 0.9 V^\pi(s_2)] + 0.25[(-1) + 0.9 V^\pi(s_3)] + 0.25[(-1) + 0.9 V^\pi(s_1)] + 0.25[(-1) + 0.9 V^\pi(s_1)]$

Why this step? Each action has probability 0.25 under the uniform policy. We sum over all actions and their outcomes.

Step 4: Simplify (assuming symmetry $V^\pi(s_2) = V^\pi(s_3) = V$): $V^\pi(s_1) = -1 + 0.9[0.25V + 0.25V + 0.25V^\pi(s_1) + 0.25V^\pi(s_1)]$ $V^\pi(s_1) = -1 + 0.9[0.5V + 0.5V^\pi(s_1)]$ $V^\pi(s_1) = -1 + 0.45V + 0.45V^\pi(s_1)$ $0.55V^\pi(s_1) = -1 + 0.45V$

Result: This is a system of linear equations. Solving iteratively or exactly gives the value. The Bellman equation turned a sequential problem into an algebraic one.

Apply the Bellman optimality equation as an update:

Step 1: Bellman optimality says: $Q^*(s, a) = \mathbb{E}[r + \gamma \max_{a'} Q^*(s', a')]$

Step 2: We got a sample $(s, a, r, s')$ so the temporal difference target is: $\text{target} = r + \gamma \max_{a'} Q(s', a') = 5 + 0.9 \times 12 = 5 + 10.8 = 15.8$

Why? This is our bootstrapped estimate of the "true" $Q^*(s, a)$ based on this experience.

Step 3: Update $Q(s, a)$ toward the target (with learning rate $\alpha = 0.1$): $Q(s, a) \leftarrow Q(s, a) + \alpha[\text{target} - Q(s, a)]$ $Q(s, a) \leftarrow 10 + 0.1[15.8 - 10] = 10 + 0.58 = 10.58$

Interpretation: Our estimate of $Q(s, a)$ improved by moving toward the value predicted by the Bellman optimality equation.

Common Mistakes

Why it feels right: Seems simpler—just add rewards.

The problem: Without discounting, infinite-horizon returns diverge. If every state gives $r=1$, then $V(s) = \infty$. The discount $\gamma$ ensures convergence and prefers near-term rewards.

Fix: Always include $\gamma$ in the recursive term: $V(s) = r + \gamma V(s')$.

Why it feels right: Both involve actions and values—easy to mix up.

The problem:

• $V^\pi$ is tied to a fixed policy $\pi$, so we take the expectation over actions chosen by $\pi$.
• $V^*$ is the optimal value, so we take the max over all actions (choosing the best).

Fix:

• Bellman expectation (for $\pi$): $\sum_a \pi(a|s) \ldots$
• Bellman optimality (for $\pi^*$): $\max_a \ldots$

Why it feels right: In deterministic environments, there's only one $s'$ per $(s, a)$.

The problem: Most environments are stochastic. Multiple next states are possible with different probabilities $p(s' | s, a)$.

Fix: Always sum/integrate over possible next states: $V(s) = \sum_{s'} p(s' | s, a) [r(s, a, s') + \gamma V(s')]$

Active Recall Prompts

The Bellman equation says: Your total points = points you get right now + (slightly less valuable) points from the next level.

Why "slightly less valuable"? Because points later matter a bit less than points now (like getting ₹100 today is better than ₹100 next year—that's the discount factor).

So instead of adding up points from the entire game all at once (which is hard), you just think: "What do I get now, and what's the next level worth?" Then you use your guess of the next level's value to figure out this level's value. Keep doing this backward, and you figure out every level's value!

The "expectation" part means: if the game is random (sometimes you get a power-up, sometimes you don't), you average over all the possibilities.

Connections

• Dynamic Programming — Bellman equations enable DP methods (policy iteration, value iteration)
• Temporal Difference Learning — TD learning uses Bellman equations as update rules
• Q-Learning — Off-policy algorithm built directly on Bellman optimality for $Q^*$
• Policy Gradient Methods — Contrast: optimize policy directly without explicit value functions
• Markov Decision Process — Bellman equations formalize the value structure of MDPs
• Discount Factor — Controls the tradeoff between immediate and future rewards
• Bootstrapping — Key RL concept: using value estimates to update value estimates

#flashcards/ai-ml

What is the Bellman expectation equation for $V^\pi(s)$? :: $V^\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r | s, a) [r + \gamma V^\pi(s')]$ — the value of state $s$ under policy $\pi$ equals expected immediate reward plus discounted next-state value.

What is the recursive structure of the Bellman equation? :: $V(s) = \text{immediate reward} + \gamma \times \text{value of next state}$ — breaks infinite-horizon value into one-step reward + discounted future, enabling iterative solution.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)