i
Reinforcement Learning:
An Introduction
Second edition, in progress
****Draft****
Richard S. Sutton and Andrew G. Barto
c
2014, 2015, 2016, 2017
A Bradford Book
The MIT Press
Cambridge, Massachusetts
London, England
ii
In memory of A. Harry Klopf
Contents
Preface to the First Edition ix
Preface to the Second Edition xiii
Summary of Notation xvii
1 The Reinforcement Learning Problem 1
1.1 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Elements of Reinforcement Learning . . . . . . . . . . . . . . . . . . . 6
1.4 Limitations and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 An Extended Example: Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . 10
1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 History of Reinforcement Learning . . . . . . . . . . . . . . . . . . . . 15
I Tabular Solution Methods 25
2 Multi-arm Bandits 27
2.1 A k-Armed Bandit Problem . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Action-Value Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 The 10-armed Testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5 Tracking a Nonstationary Problem . . . . . . . . . . . . . . . . . . . . 34
2.6 Optimistic Initial Values . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.7 Upper-Confidence-Bound Action Selection . . . . . . . . . . . . . . . . 37
2.8 Gradient Bandit Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 39
2.9 Associative Search (Contextual Bandits) . . . . . . . . . . . . . . . . . 42
2.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
iii
iv CONTENTS
3 Finite Markov Decision Processes 49
3.1 The Agent–Environment Interface . . . . . . . . . . . . . . . . . . . . 49
3.2 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Returns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4 Unified Notation for Episodic and Continuing Tasks . . . . . . . . . . 57
3.5 *The Markov Property . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.6 Markov Decision Processes . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.7 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.8 Optimal Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.9 Optimality and Approximation . . . . . . . . . . . . . . . . . . . . . . 75
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4 Dynamic Programming 81
4.1 Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2 Policy Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.4 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.5 Asynchronous Dynamic Programming . . . . . . . . . . . . . . . . . . 93
4.6 Generalized Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . 95
4.7 Efficiency of Dynamic Programming . . . . . . . . . . . . . . . . . . . 96
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5 Monte Carlo Methods 101
5.1 Monte Carlo Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.2 Monte Carlo Estimation of Action Values . . . . . . . . . . . . . . . . 106
5.3 Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.4 Monte Carlo Control without Exploring Starts . . . . . . . . . . . . . 110
5.5 Off-policy Prediction via Importance Sampling . . . . . . . . . . . . . 113
5.6 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . 119
5.7 Off-Policy Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . 120
5.8 *Discounting-Aware Importance Sampling . . . . . . . . . . . . . . . . 122
5.9 *Per-Reward Importance Sampling . . . . . . . . . . . . . . . . . . . . 124
5.10 Off-policy Returns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
5.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6 Temporal-Difference Learning 129
6.1 TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.2 Advantages of TD Prediction Methods . . . . . . . . . . . . . . . . . . 133
CONTENTS v
6.3 Optimality of TD(0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.4 Sarsa: On-Policy TD Control . . . . . . . . . . . . . . . . . . . . . . . 139
6.5 Q-learning: Off-Policy TD Control . . . . . . . . . . . . . . . . . . . . 142
6.6 Expected Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.7 Maximization Bias and Double Learning . . . . . . . . . . . . . . . . . 145
6.8 Games, Afterstates, and Other Special Cases . . . . . . . . . . . . . . 147
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7 Multi-step Bootstrapping 153
7.1 n-step TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.2 n-step Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7.3 n-step Off-policy Learning by Importance Sampling . . . . . . . . . . 160
7.4 *Per-reward Off-policy Methods . . . . . . . . . . . . . . . . . . . . . . 162
7.5 Off-policy Learning Without Importance Sampling:
The n-step Tree Backup Algorithm . . . . . . . . . . . . . . . . . . . . 163
7.6 *A Unifying Algorithm: n-step Q(σ) . . . . . . . . . . . . . . . . . . . 166
7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8 Planning and Learning with Tabular Methods 173
8.1 Models and Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8.2 Dyna: Integrating Planning, Acting, and Learning . . . . . . . . . . . 176
8.3 When the Model Is Wrong . . . . . . . . . . . . . . . . . . . . . . . . . 180
8.4 Prioritized Sweeping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8.5 Full vs. Sample Backups . . . . . . . . . . . . . . . . . . . . . . . . . . 187
8.6 Trajectory Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
8.7 Real-Time Dynamic Programming . . . . . . . . . . . . . . . . . . . . 193
8.8 Planning at Decision Time . . . . . . . . . . . . . . . . . . . . . . . . . 197
8.9 Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
8.10 Rollout Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
8.11 Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . 202
8.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
II Approximate Solution Methods 208
9 On-policy Prediction with Approximation 211
9.1 Value-function Approximation . . . . . . . . . . . . . . . . . . . . . . . 211
9.2 The Prediction Objective (MSVE) . . . . . . . . . . . . . . . . . . . . 212
9.3 Stochastic-gradient and Semi-gradient Methods . . . . . . . . . . . . . 214