i
Reinforcement Learning:
An Introduction
Second edition, in progress
Richard S. Sutton and Andrew G. Barto
c
2012
A Bradford Book
The MIT Press
Cambridge, Massachusetts
London, England
ii
In memory of A. Harry Klopf
Contents
Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
Series Forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
Summary of Notation . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
I The Problem 1
1 Introduction 3
1.1 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . 4
1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Elements of Reinforcement Learning . . . . . . . . . . . . . . 7
1.4 An Extended Example: Tic-Tac-Toe . . . . . . . . . . . . . . 10
1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 History of Reinforcement Learning . . . . . . . . . . . . . . . 16
1.7 Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . 23
2 Bandit Problems 25
2.1 An n-Armed Bandit Problem . . . . . . . . . . . . . . . . . . 26
2.2 Action-Value Methods . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Softmax Action Selection . . . . . . . . . . . . . . . . . . . . . 30
2.4 Incremental Implementation . . . . . . . . . . . . . . . . . . . 32
2.5 Tracking a Nonstationary Problem . . . . . . . . . . . . . . . 33
2.6 Optimistic Initial Values . . . . . . . . . . . . . . . . . . . . . 35
2.7 Associative Search (Contextual Bandits) . . . . . . . . . . . . 37
iii
iv CONTENTS
2.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.9 Bibliographical and Historical Remarks . . . . . . . . . . . . . 40
3 The Reinforcement Learning Problem 43
3.1 The Agent–Environment Interface . . . . . . . . . . . . . . . . 43
3.2 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Returns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Unified Notation for Episodic and Continuing Tasks . . . . . . 52
∗
3.5 The Markov Property . . . . . . . . . . . . . . . . . . . . . . . 53
3.6 Markov Decision Processes . . . . . . . . . . . . . . . . . . . . 58
3.7 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.8 Optimal Value Functions . . . . . . . . . . . . . . . . . . . . . 66
3.9 Optimality and Approximation . . . . . . . . . . . . . . . . . 71
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.11 Bibliographical and Historical Remarks . . . . . . . . . . . . . 74
II Tabular Action-Value Methods 79
4 Dynamic Programming 83
4.1 Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.2 Policy Improvement . . . . . . . . . . . . . . . . . . . . . . . . 87
4.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.5 Asynchronous Dynamic Programming . . . . . . . . . . . . . . 98
4.6 Generalized Policy Iteration . . . . . . . . . . . . . . . . . . . 99
4.7 Efficiency of Dynamic Programming . . . . . . . . . . . . . . . 101
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.9 Bibliographical and Historical Remarks . . . . . . . . . . . . . 103
5 Monte Carlo Methods 107
5.1 Monte Carlo Policy Evaluation . . . . . . . . . . . . . . . . . 108
CONTENTS v
5.2 Monte Carlo Estimation of Action Values . . . . . . . . . . . . 112
5.3 Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . . 114
5.4 On-Policy Monte Carlo Control . . . . . . . . . . . . . . . . . 118
∗
5.5 Evaluating One Policy While Following Another (Off-policy Pol-
icy Evaluation) . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.6 Off-Policy Monte Carlo Control . . . . . . . . . . . . . . . . . 122
5.7 Incremental Implementation . . . . . . . . . . . . . . . . . . . 124
5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.9 Bibliographical and Historical Remarks . . . . . . . . . . . . . 127
6 Temporal-Difference Learning 129
6.1 TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.2 Advantages of TD Prediction Methods . . . . . . . . . . . . . 134
6.3 Optimality of TD(0) . . . . . . . . . . . . . . . . . . . . . . . 137
6.4 Sarsa: On-Policy TD Control . . . . . . . . . . . . . . . . . . 141
6.5 Q-Learning: Off-Policy TD Control . . . . . . . . . . . . . . . 144
6.6 Games, Afterstates, and Other Special Cases . . . . . . . . . . 147
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.8 Bibliographical and Historical Remarks . . . . . . . . . . . . . 149
7 Eligibility Traces 153
7.1 n-Step TD Prediction . . . . . . . . . . . . . . . . . . . . . . . 154
7.2 The Forward View of TD(λ) . . . . . . . . . . . . . . . . . . . 159
7.3 The Backward View of TD(λ) . . . . . . . . . . . . . . . . . . 163
7.4 Equivalence of Forward and Backward Views . . . . . . . . . . 166
7.5 Sarsa(λ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
7.6 Q(λ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
7.7 Replacing Traces . . . . . . . . . . . . . . . . . . . . . . . . . 175
7.8 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . 178
∗
7.9 Variable λ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
