\( \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

RL01.6 · Bellman equations

A free, illustrated module of 4 lessons and one interactive in RL01 RL Foundations: Value now is reward plus value next; The Bellman expectation equation; The Bellman optimality equation; Bellman backups as operators.

RL01.6 L2 · Intermediate 4 lessons · about 115 min Live · in review

Part of RL01 RL Foundations in the Reinforcement Learning track.

The value of a state is tied to the values of the states that can follow it: value now is reward plus discounted value next. These four lessons derive that recursion from the definition of the return, turn it into the Bellman expectation equation for a given policy and the Bellman optimality equation for the best one, solve both by hand on a two-state lake, and then show why simply repeating the equations as an update converges whenever the discount is below 1.

What you need first. Markov decision processes: states, actions, rewards and the dynamics p(s’, r | s, a) (RL01.4), and returns, discounting and value functions (RL01.5). Expectations and weighted averages, sums, and solving two linear equations in two unknowns. Matrix notation helps in two places but is not required.

Lessons

1. Value now is reward plus value next RL01.6.1 25 min

   The discounted return hides a copy of itself: the return from now is the first reward plus the discount times the return from the next step. Derive that recursion, use it to work backwards along a chain of rewards, and meet the one-step look-ahead that every Bellman equation is built on.

2. The Bellman expectation equation RL01.6.2 30 min

   For a fixed policy, the value of every state is tied to the values of the states that can follow it. Derive that tie, the Bellman expectation equation, line by line from the definition of value, read it off a backup diagram, and solve it as a small system of linear equations by hand and with NumPy.

3. The Bellman optimality equation RL01.6.3 30 min

   Replace the average over actions by a maximum and the Bellman equation describes the best possible behaviour instead of a given one. Meet the optimal value functions, see why acting greedily on them is optimal, and find the best policy of a small problem by checking every candidate.

4. Bellman backups as operators RL01.6.4 30 min

   Treat the right-hand side of a Bellman equation as a machine that turns any table of values into a new one. Prove that both machines pull any two tables closer by the discount factor, and see why repeating a backup converges to the right values from any starting guess.

The interactive

RL01.6-X1 · Bellman backup gridworld. Apply Bellman backups to a small gridworld one sweep at a time. Switch between the average over a random policy and the max, change the discount, the slip probability and the step reward, and open any cell to see its backup written out with the current numbers. It lives in Bellman backups as operators.