Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning series)

The significantly expanded and updated new edition of a widely used text on reinforcement learning, one of the most active research areas in artificial intelligence. Reinforcement learning, one of the most active research areas in artificial intelligence, is a computational approach to learning whereby an agent tries to maximize the total amount of reward it receives while interacting with a complex, uncertain environment. In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the field's key ideas and algorithms. This second edition has been significantly expanded and updated, presenting new topics and updating coverage of other topics. Like the first edition, this second edition focuses on core online learning algorithms, with the more mathematical material set off in shaded boxes. Part I covers as much of reinforcement learning as possible without going beyond the tabular case for which exact solutions can be found. Many algorithms presented in this part are new to the second edition, including UCB, Expected Sarsa, and Double Learning. Part II extends these ideas to function approximation, with new sections on such topics as artificial neural networks and the Fourier basis, and offers expanded treatment of off-policy learning and policy-gradient methods. Part III has new chapters on reinforcement learning's relationships to psychology and neuroscience, as well as an updated case-studies chapter including AlphaGo and AlphaGo Zero, Atari game playing, and IBM Watson's wagering strategy. The final chapter discusses the future societal impacts of reinforcement learning. 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 Reinforcement learning is the learning of a mapping from situations to actions so as to maximize a scalar reward or reinforcement signal. The learner is not told which action to take, as in most forms of machine learning, but instead must discover which actions yield the highest reward by trying them. In the most interesting and challenging cases, actions may affect not only the immediate reward, but also the next situation, and through that all subsequent rewards. These two characteristics -- trial-and-error search and delayed reward -- are the most important distinguishing features of reinforcement learning. Reinforcement learning is both a new and a very old topic in AI. The term appears to have been coined by Minsk (1961), and independently in control theory by Walz and Fu (1965). The earliest machine learning research now viewed as directly relevant was Samuel's (1959) checker player, which used temporal-difference learning to manage delayed reward much as it is used today. Of course learning and reinforcement have been studied in psychology for almost a century, and that work has had a very strong impact on the AI/engineering work. One could in fact consider all of reinforcement learning to be simply the reverse engineering of certain psychological learning processes (e.g. operant conditioning and secondary reinforcement). Reinforcement Learning is an edited volume of original research, comprising seven invited contributions by leading researchers.