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

**Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications.** 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 when interacting with a complex, uncertain environment. In __Reinforcement Learning__, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability. The book is divided into three parts. Part I defines the reinforcement learning problem in terms of Markov decision processes. Part II provides basic solution methods: dynamic programming, Monte Carlo methods, and temporal-difference learning. Part III presents a unified view of the solution methods and incorporates artificial neural networks, eligibility traces, and planning; the two final chapters present case studies and consider the future of reinforcement learning. Cover 1 Endorsements for Sutton & Barto Book: Reinforcement Learning: An Introduction 6 Code for Sutton & Barto Book: Reinforcement Learning: An Introduction 7 code/utilities.lisp 9 code/TTT.lisp 17 code/testbed.lisp 20 code/softmax.lisp 22 code/banditsAB.lisp 24 code/constant-alpha.lisp 26 code/optimistic.lisp 28 code/RC1.lisp 30 code/RC2.lisp 32 code/RC3.lisp 34 code/pursuit.lisp 36 code/pole.c 38 code/gridworld5x5.lisp 45 code/gridworld4x4.lisp 47 code/jacks.lisp 51 code/gambler.lisp 53 code/blackjack1.lisp 54 code/blackjack2.lisp 56 code/walk.lisp 59 code/walk-batch.lisp 62 code/queuing.lisp 65 code/queuing.c 67 code/nstep-walk-online.lisp 71 code/nstep-walk-offline.lisp 73 code/generalization.lisp 75 code/Baird.lisp 77 code/sampling2.lisp 99 code/acrobot.lisp 102 Figures for Sutton & Barto Book: Reinforcement Learning: An Introduction 113 Errata and Notes for Sutton & Barto Book: Reinforcement Learning: An Introduction 117 Presentation Slides for Teaching from Sutton & Barto's Book: Reinforcement Learning: An Introduction 119 Preface 121 1 Introduction 125 1.1 Reinforcement Learning 127 1.2 Examples 130 1.3 Elements of Reinforcement Learning 132 1.4 An Extended Example: Tic-Tac-Toe 135 1.5 Summary 141 1.6 History of Reinforcement Learning 142 1.7 Bibliographical Remarks 150 2 Evaluative Feedback 151 2.1 An n-armed Bandit Problem 153 2.2 Action-Value Methods 155 2.3 Softmax Action Selection 159 2.4 Evaluation versus Instruction 161 2.5 Incremental Implementation 166 2.6 Tracking a Nonstationary Problem 169 2.7 Optimistic Initial Values 172 2.8 Reinforcement Comparison 175 2.9 Pursuit Methods 178 2.10 Associative Search 181 2.11 Conclusion 183 2.12 Bibliographical and Historical Remarks 186 Footnotes 189 3 The Reinforcement Learning Problem 193 3.1 The Agent-Environment Interface 195 3.2 Goals and Rewards 200 3.3 Returns 202 3.4 A Unified Notation for Episodic and Continual Tasks 205 3.5 The Markov Property 207 3.6 Markov Decision Processes 212 3.7 Value Functions 216 3.8 Optimal Value Functions 223 3/node10.html 230 3/node11.html 232 3/node12.html 234 3/footnode.html 238 Part II: Elementary Solution Methods 247 4 Dynamic Programming 248 4.1 Policy Evaluation 251 4/node3.html 257 4.3 Policy Iteration 261 4.4 Value Iteration 265 4.5 Asynchronous Dynamic Programming 269 4.6 Generalized Policy Iteration 271 4.7 Efficiency of Dynamic Programming 274 4.8 Summary 276 4.9 Historical and Bibliographical Remarks 278 Footnotes 280 5 Monte Carlo Methods 282 5.1 Monte Carlo Policy Evaluation 284 5.2 Monte Carlo Estimation of Action Values 290 5.3 Monte Carlo Control 292 5.4 On-Policy Monte Carlo Control 297 5.5 Evaluating One Policy While Following Another 300 5.6 Off-Policy Monte Carlo Control 302 5.7 Incremental Implementation 305 5.8 Summary 307 5.9 Historical and Bibliographical Remarks 309 6 Temporal Difference Learning 311 6.1 TD Prediction 313 6.2 Advantages of TD Prediction Methods 318 6.3 Optimality of TD(0) 322 6.4 Sarsa: On-Policy TD Control 326 6.5 Q-learning: Off-Policy TD Control 330 6.6 Actor-Critic Methods (*) 333 6.7 R-Learning for Undiscounted Continual Tasks (*) 336 6.8 Games, After States, and other Special Cases 340 6.9 Conclusions 343 6.10 Historical and Bibliographical Remarks 345 Footnotes 348 Part III: A Unified View 350 7 Eligibility Traces 351 7.1 n-step TD Prediction 353 7.2 The Forward View of TD() 358 7.3 The Backward View of TD() 363 7.4 Equivalence of the Forward and Backward Views 367 7.5 Sarsa() 372 7.6 Q() 375 7.7 Eligibility Traces for Actor-Critic Methods (*) 379 7.8 Replacing Traces 381 7/node10.html 384 7.10 Variable (*) 386 7.11 Conclusions 388 7.12 Bibliographical and Historical Remarks 390 8 Generalization and Function Approximation 393 8/node1.html 393 8/node2.html 395 8/node3.html 400 8/node4.html 405 8.3.1 Coarse Coding 408 8.3.2 Tile Coding 411 8.3.3 Radial Basis Functions 415 8.3.4 Kanerva Coding 417 8.4 Control with Function Approximation 420 8.5 Off-Policy Bootstrapping 426 8.6 Should We Bootstrap? 430 8.7 Summary 432 8.8 Bibliographical and Historical Remarks 434 9 Planning and Learning 439 9.1 Models and Planning 441 9.2 Integrating Planning, Acting, and Learning 444 9.3 When the Model is Wrong 449 9.4 Prioritized Sweeping 453 9.5 Full vs. Sample Backups 457 9.6 Trajectory Sampling 462 9.7 Heuristic Search 466 9.8 Summary 470 9.9 Historical and Bibliographical Remarks 472 Footnotes 474 10 Dimensions 476 10.1 The Unified View 477 10.2 Other Frontier Dimensions 481 11 Case Studies 484 11.1 TD-Gammon 485 11.2 Samuel's Checkers Player 490 11.3 The Acrobot 494 11.4 Elevator Dispatching 498 11.5 Dynamic Channel Allocation 502 11.6 Job-Shop Scheduling 507 References 513 Summary of Notation 548 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. 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 when interacting with a complex, uncertain environment. In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning. Their discussion ranges from the history of the field's intellectual foundations to the most recent developments and applications. The only necessary mathematical background is familiarity with elementary concepts of probability.The book is divided into three parts. Part I defines the reinforcement learning problem in terms of Markov decision problems. Part II provides basic solution methods: dynamic programming, Monte Carlo simulation, and temporal-difference learning. Part III presents a unified view of the solution methods and incorporates artificial neural networks, eligibility traces, and planning; the two final chapters present case studies and consider the future of reinforcement learning. In Reinforcement Learning, Richard Sutton And Andrew Barto Provide A Clear And Simple Account Of The Key Ideas And Algorithms Of Reinforcement Learning. Their Discussion Ranges From The History Of The Field's Intellectual Foundations To The Most Recent Developments And Applications. The Only Necessary Mathematical Background Is Familiarity With Elementary Concepts Of Probability.--book Jacket. Contents -- Series Foreword -- Preface -- I. The Problem -- 1. Introduction -- 2. Evaluative Feedback -- 3. The Reinforcement Learning Problem -- Ii. Elementary Solution Methods -- 4. Dynamic Programming -- 5. Monte Carlo Methods -- 6. Temporal-difference Learning -- Iii. A Unified View -- 7. Eligibility Traces -- 8. Generalization And Function Approximation -- 9. Planning And Learning -- 10. Dimensions Of Reinforcement Learning -- 11. Case Studies -- References -- Summary Of Notation -- Index. Richard S. Sutton And Andrew G. Barto. Includes Bibliographical References (p. [291]-312) And Index. Reinforcement learning is a computational approach to learning whereby an agent tries to maximize the total amount of reward it receives when interacting with its environment. This book explains the main ideas and algorithms of reinforcement learning. The book is thorough in its coverage. Part I defines the reinforcement learning problem in terms of Markov decision processes. Part II provides basic solution methods: dynamic programming, Monte Carlo methods, and temporal-difference learning. Part III presents a unified view of the solution methods and incorporates artificial neural networks, eligibility traces, and planning; the two final chapters present case studies and consider the future of reinforcement learning. Presents the book "Reinforcement Learning: An Introduction," written by Richard S. Sutton and Andrew G. Barto and published by the Massachusetts Institute of Technology (MIT) Press in 1998. The book is a textbook targeted toward engineers and scientists in artificial intelligence, operations research, neural networks, and control systems. Examines a computation approach to learning from interaction with environment