Reinforcement Learning: An Introduction

Preface to the Second Edition......Page 13
Preface to the First Edition......Page 17
Summary of Notation......Page 19
Reinforcement Learning......Page 23
Examples......Page 26
Elements of Reinforcement Learning......Page 28
Limitations and Scope......Page 29
An Extended Example: Tic-Tac-Toe......Page 30
Early History of Reinforcement Learning......Page 35
I   Tabular Solution Methods......Page 44
A k-armed Bandit Problem......Page 47
Action-value Methods......Page 49
The 10-armed Testbed......Page 50
Incremental Implementation......Page 52
Tracking a Nonstationary Problem......Page 54
Optimistic Initial Values......Page 56
Upper-Confidence-Bound Action Selection......Page 57
Gradient Bandit Algorithms......Page 59
Associative Search (Contextual Bandits)......Page 63
Summary......Page 64
The Agent–Environment Interface......Page 69
Goals and Rewards......Page 75
Returns and Episodes......Page 76
Unified Notation for Episodic and Continuing Tasks......Page 79
Policies and Value Functions......Page 80
Optimal Policies and Optimal Value Functions......Page 84
Optimality and Approximation......Page 89
Summary......Page 90
Dynamic Programming......Page 95
Policy Evaluation (Prediction)......Page 96
Policy Improvement......Page 98
Policy Iteration......Page 102
Value Iteration......Page 104
Asynchronous Dynamic Programming......Page 107
Generalized Policy Iteration......Page 108
Efficiency of Dynamic Programming......Page 109
Summary......Page 110
Monte Carlo Methods......Page 113
Monte Carlo Prediction......Page 114
Monte Carlo Estimation of Action Values......Page 118
Monte Carlo Control......Page 119
Monte Carlo Control without Exploring Starts......Page 122
Off-policy Prediction via Importance Sampling......Page 125
Incremental Implementation......Page 131
Off-policy Monte Carlo Control......Page 132
*Discounting-aware Importance Sampling......Page 134
*Per-decision Importance Sampling......Page 136
Summary......Page 137
TD Prediction......Page 141
Advantages of TD Prediction Methods......Page 146
Optimality of TD(0)......Page 148
Sarsa: On-policy TD Control......Page 151
Q-learning: Off-policy TD Control......Page 153
Expected Sarsa......Page 155
Maximization Bias and Double Learning......Page 156
Games, Afterstates, and Other Special Cases......Page 158
Summary......Page 160
n-step Bootstrapping......Page 163
n-step TD Prediction......Page 164
n-step Sarsa......Page 167
n-step Off-policy Learning......Page 170
*Per-decision Methods with Control Variates......Page 172
Off-policy Learning Without Importance Sampling: The n-step Tree Backup Algorithm......Page 174
*A Unifying Algorithm: n-step Q()......Page 176
Summary......Page 179
Models and Planning......Page 181
Dyna: Integrated Planning, Acting, and Learning......Page 183
When the Model Is Wrong......Page 188
Prioritized Sweeping......Page 190
Expected vs. Sample Updates......Page 194
Trajectory Sampling......Page 196
Real-time Dynamic Programming......Page 199
Planning at Decision Time......Page 202
Heuristic Search......Page 203
Rollout Algorithms......Page 205
Monte Carlo Tree Search......Page 207
Summary of the Chapter......Page 210
Summary of Part I: Dimensions......Page 211
II   Approximate Solution Methods......Page 214
On-policy Prediction with Approximation......Page 219
Value-function Approximation......Page 220
The Prediction Objective (VE)......Page 221
Stochastic-gradient and Semi-gradient Methods......Page 222
Linear Methods......Page 226
Polynomials......Page 232
Fourier Basis......Page 233
Coarse Coding......Page 237
Tile Coding......Page 239
Radial Basis Functions......Page 243
Selecting Step-Size Parameters Manually......Page 244
[23pt][l]9.7Nonlinear Function Approximation: Artificial Neural Networks......Page 245
Least-Squares TD......Page 250
Memory-based Function Approximation......Page 252
Kernel-based Function Approximation......Page 254
Looking Deeper at On-policy Learning: Interest and Emphasis......Page 256
Summary......Page 258
Episodic Semi-gradient Control......Page 265
Semi-gradient n-step Sarsa......Page 269
Average Reward: A New Problem Setting for Continuing Tasks......Page 271
Deprecating the Discounted Setting......Page 275
Differential Semi-gradient n-step Sarsa......Page 277
Summary......Page 278
*Off-policy Methods with Approximation......Page 279
Semi-gradient Methods......Page 280
Examples of Off-policy Divergence......Page 282
The Deadly Triad......Page 286
Linear Value-function Geometry......Page 288
Gradient Descent in the Bellman Error......Page 291
The Bellman Error is Not Learnable......Page 296
Gradient-TD Methods......Page 300
Emphatic-TD Methods......Page 303
Reducing Variance......Page 305
Summary......Page 306
Eligibility Traces......Page 309
The -return......Page 310
TD()......Page 314
n-step Truncated -return Methods......Page 317
Redoing Updates: Online -return Algorithm......Page 319
True Online TD()......Page 321
*Dutch Traces in Monte Carlo Learning......Page 323
Sarsa()......Page 325
Variable  and ......Page 329
*Off-policy Traces with Control Variates......Page 331
Watkins's Q() to Tree-Backup()......Page 334
Stable Off-policy Methods with Traces......Page 336
Implementation Issues......Page 338
Conclusions......Page 339
Policy Gradient Methods......Page 343
Policy Approximation and its Advantages......Page 344
The Policy Gradient Theorem......Page 346
REINFORCE: Monte Carlo Policy Gradient......Page 348
REINFORCE with Baseline......Page 351
Actor–Critic Methods......Page 353
Policy Gradient for Continuing Problems......Page 355
Policy Parameterization for Continuous Actions......Page 357
III   Looking Deeper......Page 359
Psychology......Page 363
Prediction and Control......Page 364
Classical Conditioning......Page 365
Blocking and Higher-order Conditioning......Page 367
The Rescorla–Wagner Model......Page 368
The TD Model......Page 371
TD Model Simulations......Page 372
Instrumental Conditioning......Page 379
Delayed Reinforcement......Page 383
Cognitive Maps......Page 385
Habitual and Goal-directed Behavior......Page 386
Summary......Page 390
Neuroscience......Page 399
Neuroscience Basics......Page 400
Reward Signals, Reinforcement Signals, Values, and Prediction Errors......Page 402
The Reward Prediction Error Hypothesis......Page 403
Dopamine......Page 405
[23pt][l]15.5Experimental Support for the Reward Prediction Error Hypothesis......Page 409
TD Error/Dopamine Correspondence......Page 412
Neural Actor–Critic......Page 417
Actor and Critic Learning Rules......Page 420
Hedonistic Neurons......Page 424
Collective Reinforcement Learning......Page 426
Model-based Methods in the Brain......Page 429
Addiction......Page 431
Summary......Page 432
TD-Gammon......Page 443
Samuel's Checkers Player......Page 448
Watson's Daily-Double Wagering......Page 451
Optimizing Memory Control......Page 454
Human-level Video Game Play......Page 458
Mastering the Game of Go......Page 463
AlphaGo......Page 466
AlphaGo Zero......Page 469
Personalized Web Services......Page 472
Thermal Soaring......Page 475
General Value Functions and Auxiliary Tasks......Page 481
Temporal Abstraction via Options......Page 483
Observations and State......Page 486
Designing Reward Signals......Page 491
Remaining Issues......Page 494
The Future of Artificial Intelligence......Page 497
Index......Page 503