Return, value and the Bellman equation
A reward tells you how good one step was. To choose well you need to know how good a situation is in the long run. That number is the value, and the Bellman equation says how to compute it from the next step's value.
Kind: not an agent: the toolkit behind value iteration and Q-learning.
Week: 4 (slides 17 to 24).
Book: Wooldridge 2.6, utility over runs and expected utility (pp. 38 to 41). The Bellman equation isn’t in the book: Sutton and Barto 3.3 to 3.6.
Techniques on this page: the discounted return, choosing γ, state and action values, the Bellman equation, the Bellman optimality equation.
The problem it solves
In the gridworld, the safe route and the risky route both cost −0.04 a step. Nothing in the immediate reward tells them apart: the difference is a 1-in-10 chance of falling into the −1 later (slide 17).
So the agent needs a number for “how good is it to be here, counting everything that might follow”. That’s the value. And the trick that makes it computable is that the value of a state can be written in terms of the values of the states one step away.
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| return \(G_t\) | the total (discounted) reward from time \(t\) onwards, along one run |
| discount factor \(\gamma\) | a reward \(k\) steps away counts \(\gamma^k\) as much as one now |
| myopic / far-sighted | \(\gamma\) near 0 / \(\gamma\) near 1 |
| episodic task | every run ends in a terminal state |
| \(V^\pi(s)\) | the average return from \(s\) if you follow policy \(\pi\) |
| \(Q^\pi(s, a)\) | the average return if you do \(a\) in \(s\), then follow \(\pi\) |
| \(V^*\), \(Q^*\) | the same, for the best possible policy |
| \(\mathbb E\) | “the average over everything that could happen” |
| \(\arg\max_a\) | the action that gives the biggest value (not the value itself) |
Technique 1: the discounted return
Problem it solves: one number for a whole run of rewards.
\[G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty}\gamma^k r_{t+k+1}\]
The crucial identity: \(G_t = r_{t+1} + \gamma G_{t+1}\). “Reward now, plus the discounted return from the next step.” You can compute a return backwards from the end.
Worked example (slide 20). The top route from \(s_{1,1}\) with no slips: rewards −0.04, −0.04, −0.04, −0.04, +1.
\(\gamma = 1\): \(G_0 = 4(-0.04) + 1 = 0.84\).
\(\gamma = 0.9\), backwards: \(G_4 = 1\), \(G_3 = -0.04 + 0.9 = 0.86\), \(G_2 = -0.04 + 0.774 = 0.734\), \(G_1 = -0.04 + 0.6606 = 0.6206\), \(G_0 = -0.04 + 0.5585 = 0.5185 \approx 0.52\).
This lucky run (no slip in 5 moves) has probability \(0.8^5 \approx 0.33\). Other runs give other returns, which is why value is an average.
Technique 2: choosing γ
Problem it solves: keeps the return finite, and sets how patient the agent is.
With rewards no bigger than \(r_{max}\), \(|G_t| \le r_{max}/(1-\gamma)\). A constant reward \(r\) forever is worth exactly \(r/(1-\gamma)\): −0.04 forever with \(\gamma = 0.9\) is −0.4. So \(\gamma < 1\) is needed when runs can go on for ever (slide 7 says \(\gamma \in [0, 1)\)).
\(\gamma = 1\) is fine for episodic tasks: the sum has finitely many terms. That’s why slide 20 can use it.
γ is a value judgement (slide 19). Agents differing only in \(\gamma\) can act oppositely in the same state. In the gridworld, \(\gamma = 1\) sends the bottom row the safe way round; \(\gamma = 0.9\) makes the agent impatient enough to go past the −1. Who sets an AI system’s patience is an ethical question, not just a tuning one.
Technique 3: state value and action value
Problem it solves: “how good is it here?” and “how good is it to do this here?”.
\[V^\pi(s) = \mathbb E_\pi[G_t \mid s_t = s], \qquad Q^\pi(s, a) = \mathbb E_\pi[G_t \mid s_t = s, a_t = a]\]
The average is over every run that could happen, weighted by its probability. This is Wooldridge’s expected utility (book p. 40, equation 2.1), starting from a particular state. And \(V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a)\).
Technique 4: the Bellman equation
Problem it solves: computes values without listing every possible run.
Average the identity \(G_t = r_{t+1} + \gamma G_{t+1}\):
\[V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a)\,\big[R(s, a, s') + \gamma V^\pi(s')\big]\]
Inside out: reward for landing in \(s'\) plus the discounted value from there; averaged over where you might land; averaged over what the policy might do. “Reward now + value of what comes next.” One equation per state; for a fixed policy they’re ordinary simultaneous equations.
Worked example (the corridor). \(s_1 \leftrightarrow s_2 \to s_3\) (goal, value 0). Moves are certain; West from \(s_1\) stays put. −0.1 per step, \(R(s_2, E, s_3) = 0.9\), \(\gamma = 0.9\).
Always East: \(V(s_2) = 0.9\); \(V(s_1) = -0.1 + 0.9(0.9) = 0.71\).
East or West at random (0.5 each): \(V(s_1) = -0.1 + 0.45V(s_2) + 0.45V(s_1)\) and \(V(s_2) = 0.4 + 0.45V(s_1)\). Substitute: \(0.55V(s_1) = 0.08 + 0.2025V(s_1)\), so \(V(s_1) = 0.08/0.3475 = 0.230\) and \(V(s_2) = 0.504\). Dithering costs a lot.
Technique 5: the Bellman optimality equation
Problem it solves: describes the best values, and from them the best policy.
Replace the average over actions by the best action:
\[V^*(s) = \max_a \sum_{s'} P(s' \mid s, a)\,\big[R(s, a, s') + \gamma V^*(s')\big]\] \[Q^*(s, a) = \sum_{s'} P(s' \mid s, a)\,\big[R(s, a, s') + \gamma \max_{a'} Q^*(s', a')\big]\]
Then \(V^*(s) = \max_a Q^*(s, a)\) and \(\pi^*(s) = \arg\max_a Q^*(s, a)\). With \(Q^*\) in hand, choosing the best action is a table lookup that needs no model, which is exactly what Q-learning exploits. The max makes the equations non-linear, so you solve them by iterating. No proofs in this course (slide 23).
Worked example. \(Q^*(s, \cdot) = \{N: 0.3,\ S: -0.2,\ E: 0.8,\ W: 0.5\}\). Then \(V^*(s) = \max = 0.8\) and \(\pi^*(s) = \arg\max = E\).
What to read
| Source | Read? | Why |
|---|---|---|
| Wooldridge 2.6 “Utility functions”, Tileworld (pp. 38 to 40) | Read | utility over runs; the return is one |
| Wooldridge 2.6 “Maximizing expected utility” (p. 40) | Read | equation 2.1, the optimal agent; it “does not give us any clues about how to implement” it, which is what Bellman supplies |
| Sutton and Barto 3.3 to 3.6 | Optional | returns, discounting, value functions, Bellman equations |
Page numbers are the book’s; in the scanned PDF add 21.
Practice prompt
I'm studying CS5940 Intelligent Agents, week 4 (MDPs and reinforcement learning). I want practice on RETURN, VALUE AND THE BELLMAN EQUATIONS:
- computing discounted returns G_t for short reward sequences and different gamma, forwards and backwards with G_t = r_{t+1} + gamma G_{t+1}
- the r/(1 - gamma) formula, why gamma < 1 is needed in general and when gamma = 1 is fine
- V^pi(s) and Q^pi(s, a) in words and symbols, and how they relate to expected utility
- evaluating a fixed policy on a tiny corridor MDP by writing and solving the Bellman equations
- the Bellman optimality equations for V* and Q*, max vs argmax, and reading off the optimal policy from Q*
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.