The earlier lectures learned values or policies directly from experience (model-free). This time we learn a model of the environment from experience, and plan with that model too (model-based). Then we fuse the two into one.
Lecture slides: PDF
Model-based reinforcement learning
The big picture is a loop. Real experience is used to learn a model, the model is used to plan for a value or a policy, and that policy acts to gather more experience.
The appeal of the model-based approach is that model learning is just supervised learning. Treat experience tuples $(s,a) \to (r, s')$ as a dataset: the reward $s,a \to r$ is a regression problem, and the transition $s,a \to s'$ is a density estimation problem. Without the difficulties peculiar to reinforcement learning (non-stationarity, bootstrapping), you can bring the full toolkit of regression and classification to bear. The model can be anything: table lookup, a linear model, a Gaussian process, a neural network. The downside is that the sources of error double. The model can be wrong, and the value solved on top of it can be wrong too.
The model generalizes experience: the AB example
Why is a model useful? The A, B example (also from Lecture 4) shows it from the other side. We have eight short experiences. Only one episode ever started at A, and it ended with reward 0. B came up several times and usually gave a reward.
Running MC on the real experience alone gives $V(A) = 0$: the one episode that visited A ended at 0. But build a table-lookup model from the experience, and “A leads to B” and “B usually gives a reward” get recorded separately. Draw imagined experience from this model and learn from it, and the two combine to give $V(A) \approx 0.75$. The model has stitched the scattered statistics together and generalized. This is the power of sample-based planning, which turns planning into a learning problem.
Inaccurate models
If the model is wrong, how bad can it get? The performance of model-based RL is bounded by the optimal policy of the approximate model. Learn the world wrong, and you settle for the right answer to a wrong world. There are two remedies: fall back to model-free when the model is untrustworthy, and plan while explicitly carrying the model’s uncertainty (Bayesian). Modern model-based methods using only short imagined rollouts to keep error from accumulating is an extension of the same concern.
Dyna
Dyna puts real experience to two uses. One is direct learning (a model-free update); the other is model learning. On top of that, it draws imagined experience from the learned model and updates further (Dyna-Q). In Silver’s maze experiment, garnishing each real step with 0, 5, or 50 imagined planning steps finds the path far faster from the same real experience. Imagination wrings the most out of real experience.
There is a trap here. What happens when the model goes stale? Silver’s two experiments answer. When a wall newly blocks the way and the path gets harder, Dyna-Q stumbles for a while but eventually fixes its model and adapts. But when a wall opens up and a shortcut appears, Dyna-Q settles into its stale model and rarely finds that shortcut. It fails to see a world that has improved. The fix is Dyna-Q+, which grants an exploration bonus to places not visited for a long time. It is also a preview of the exploration problem in the next lecture.
Simulation-based search
Planning need not be spread over every state. Take the current state as the root and solve only the sub-MDP from there. This is forward search, and it is far cheaper than solving the whole thing.
From the root, simulate several episodes to the end with the model and score each first action by its average result, and you have simple Monte-Carlo search. Put a tree on top of it and you have Monte-Carlo Tree Search (MCTS). One MCTS simulation splits into two parts. Inside the tree, it follows a tree policy that improves with the values seen so far; outside the tree, it runs a fixed random rollout (the default policy). Repeatedly updating the tree’s values from the result and improving the policy is, in fact, Monte-Carlo control over simulated experience. So the tree grows toward good moves and converges to the optimal action-value. Unlike simple MC search, which evaluates only the first action, MCTS lets the whole tree grow asymmetrically toward promising branches.
Go was the stage for this method. The bold idea of scoring a position’s value by the average win rate of random games started from that spot worked. Within a few years of MCTS arriving, computer Go leapt from amateur ranks to the doorstep of professional play. The strengths of MCTS are clear: it selects and digs deep along only the promising branches (best-first), evaluates positions on the fly, dodges the curse of dimensionality by sampling, works even on a black-box model as long as the rules can be run, produces an answer whenever you stop it, and parallelizes easily.
Use TD (bootstrapping) instead of MC on simulated experience and you have TD search. The logic that made TD more efficient than MC in the model-free setting repeats verbatim inside search. Finally, Dyna-2 combines two memories. It adds a long-term memory learned by TD from real experience (general knowledge) and a short-term memory learned by TD search from simulation of the current situation (knowledge of the present situation) to produce a value. AlphaGo’s later “pre-learned value network + real-time search” configuration is a direct descendant of exactly this idea (Lecture 10).