i
Reinforcement Learning:
An Introduction
Second edition, in progress
****Complete Draft****
November 5, 2017
Richard S. Sutton and Andrew G. Barto
c
2014, 2015, 2016, 2017
The text is now complete, except possibly for one more case study to be added to Chapter 16. The
references still need to be thoroughly checked, and an index still needs to be added. Please send any
errors to rich@richsutton.com and barto@cs.umass.edu. We are also very interested in correcting any
important omissions in the “Bibliographical and Historical Remarks” at the end of each chapter. If
you think of something that really should have been cited, please let us know and we can try to get it
corrected before the final version is printed.
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 xi
Summary of Notation xv
1 Introduction 1
1.1 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Elements of Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Limitations and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 An Extended Example: Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Early History of Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
I Tabular Solution Methods 18
2 Multi-armed Bandits 19
2.1 A k-armed Bandit Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Action-value Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 The 10-armed Testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Tracking a Nonstationary Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Optimistic Initial Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7 Upper-Confidence-Bound Action Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8 Gradient Bandit Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.9 Associative Search (Contextual Bandits) . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Finite Markov Decision Processes 37
3.1 The Agent–Environment Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
iii
iv CONTENTS
3.3 Returns and Episodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4 Unified Notation for Episodic and Continuing Tasks . . . . . . . . . . . . . . . . . . . . 45
3.5 Policies and Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6 Optimal Policies and Optimal Value Functions . . . . . . . . . . . . . . . . . . . . . . . 50
3.7 Optimality and Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4 Dynamic Programming 59
4.1 Policy Evaluation (Prediction) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Policy Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.4 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 Asynchronous Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.6 Generalized Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.7 Efficiency of Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5 Monte Carlo Methods 75
5.1 Monte Carlo Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2 Monte Carlo Estimation of Action Values . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.3 Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4 Monte Carlo Control without Exploring Starts . . . . . . . . . . . . . . . . . . . . . . . 82
5.5 Off-policy Prediction via Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . 84
5.6 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.7 Off-policy Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.8 *Discounting-aware Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.9 *Per-reward Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6 Temporal-Difference Learning 97
6.1 TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Advantages of TD Prediction Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3 Optimality of TD(0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.4 Sarsa: On-policy TD Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.5 Q-learning: Off-policy TD Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.6 Expected Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.7 Maximization Bias and Double Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.8 Games, Afterstates, and Other Special Cases . . . . . . . . . . . . . . . . . . . . . . . . 112
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7 n-step Bootstrapping 115
7.1 n-step TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
CONTENTS v
7.2 n-step Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.3 n-step Off-policy Learning by Importance Sampling . . . . . . . . . . . . . . . . . . . . 121
7.4 *Per-reward Off-policy Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.5 Off-policy Learning Without Importance Sampling:
The n-step Tree Backup Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.6 *A Unifying Algorithm: n-step Q(σ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8 Planning and Learning with Tabular Methods 131
8.1 Models and Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.2 Dyna: Integrating Planning, Acting, and Learning . . . . . . . . . . . . . . . . . . . . . 133
8.3 When the Model Is Wrong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.4 Prioritized Sweeping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.5 Expected vs. Sample Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
8.6 Trajectory Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
8.7 Real-time Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.8 Planning at Decision Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.9 Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
8.10 Rollout Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
8.11 Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.12 Summary of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.13 Summary of Part I: Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
II Approximate Solution Methods 160
9 On-policy Prediction with Approximation 161
9.1 Value-function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
9.2 The Prediction Objective (VE) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
9.3 Stochastic-gradient and Semi-gradient Methods . . . . . . . . . . . . . . . . . . . . . . . 164
9.4 Linear Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
9.5 Feature Construction for Linear Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 171
9.5.1 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
9.5.2 Fourier Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
9.5.3 Coarse Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.5.4 Tile Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
9.5.5 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
9.6 Nonlinear Function Approximation: Artificial Neural Networks . . . . . . . . . . . . . . 182
9.7 Least-Squares TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
9.8 Memory-based Function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
9.9 Kernel-based Function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
9.10 Looking Deeper at On-policy Learning: Interest and Emphasis . . . . . . . . . . . . . . 190
