Reinforcement Learning - An Introduction

Cover......Page 1
Endorsements for Sutton & Barto Book: Reinforcement Learning: An Introduction......Page 6
Code for Sutton & Barto Book: Reinforcement Learning: An Introduction......Page 7
code/utilities.lisp......Page 9
code/TTT.lisp......Page 17
code/testbed.lisp......Page 20
code/softmax.lisp......Page 22
code/banditsAB.lisp......Page 24
code/constant-alpha.lisp......Page 26
code/optimistic.lisp......Page 28
code/RC1.lisp......Page 30
code/RC2.lisp......Page 32
code/RC3.lisp......Page 34
code/pursuit.lisp......Page 36
code/pole.c......Page 38
code/gridworld5x5.lisp......Page 45
code/gridworld4x4.lisp......Page 47
code/jacks.lisp......Page 51
code/gambler.lisp......Page 53
code/blackjack1.lisp......Page 54
code/blackjack2.lisp......Page 56
code/walk.lisp......Page 59
code/walk-batch.lisp......Page 62
code/queuing.lisp......Page 65
code/queuing.c......Page 67
code/nstep-walk-online.lisp......Page 71
code/nstep-walk-offline.lisp......Page 73
code/generalization.lisp......Page 75
code/Baird.lisp......Page 77
code/sampling2.lisp......Page 99
code/acrobot.lisp......Page 102
Figures for Sutton & Barto Book: Reinforcement Learning: An Introduction......Page 113
Errata and Notes for Sutton & Barto Book: Reinforcement Learning: An Introduction......Page 117
Presentation Slides for Teaching from Sutton & Barto's Book: Reinforcement Learning: An Introduction......Page 119
Preface......Page 121
1 Introduction......Page 125
1.1 Reinforcement Learning......Page 127
1.2 Examples......Page 130
1.3 Elements of Reinforcement Learning......Page 132
1.4 An Extended Example: Tic-Tac-Toe......Page 135
1.5 Summary......Page 141
1.6 History of Reinforcement Learning......Page 142
1.7 Bibliographical Remarks......Page 150
2 Evaluative Feedback......Page 151
2.1 An n-armed Bandit Problem......Page 153
2.2 Action-Value Methods......Page 155
2.3 Softmax Action Selection......Page 159
2.4 Evaluation versus Instruction......Page 161
2.5 Incremental Implementation......Page 166
2.6 Tracking a Nonstationary Problem......Page 169
2.7 Optimistic Initial Values......Page 172
2.8 Reinforcement Comparison......Page 175
2.9 Pursuit Methods......Page 178
2.10 Associative Search......Page 181
2.11 Conclusion......Page 183
2.12 Bibliographical and Historical Remarks......Page 186
Footnotes......Page 189
3 The Reinforcement Learning Problem......Page 193
3.1 The Agent-Environment Interface......Page 195
3.2 Goals and Rewards......Page 200
3.3 Returns......Page 202
3.4 A Unified Notation for Episodic and Continual Tasks......Page 205
3.5 The Markov Property......Page 207
3.6 Markov Decision Processes......Page 212
3.7 Value Functions......Page 216
3.8 Optimal Value Functions......Page 223
3/node10.html......Page 230
3/node11.html......Page 232
3/node12.html......Page 234
3/footnode.html......Page 238
Part II: Elementary Solution Methods......Page 247
4 Dynamic Programming......Page 248
4.1 Policy Evaluation......Page 251
4/node3.html......Page 257
4.3 Policy Iteration......Page 261
4.4 Value Iteration......Page 265
4.5 Asynchronous Dynamic Programming......Page 269
4.6 Generalized Policy Iteration......Page 271
4.7 Efficiency of Dynamic Programming......Page 274
4.8 Summary......Page 276
4.9 Historical and Bibliographical Remarks......Page 278
Footnotes......Page 280
5 Monte Carlo Methods......Page 282
5.1 Monte Carlo Policy Evaluation......Page 284
5.2 Monte Carlo Estimation of Action Values......Page 290
5.3 Monte Carlo Control......Page 292
5.4 On-Policy Monte Carlo Control......Page 297
5.5 Evaluating One Policy While Following Another......Page 300
5.6 Off-Policy Monte Carlo Control......Page 302
5.7 Incremental Implementation......Page 305
5.8 Summary......Page 307
5.9 Historical and Bibliographical Remarks......Page 309
6 Temporal Difference Learning......Page 311
6.1 TD Prediction......Page 313
6.2 Advantages of TD Prediction Methods......Page 318
6.3 Optimality of TD(0)......Page 322
6.4 Sarsa: On-Policy TD Control......Page 326
6.5 Q-learning: Off-Policy TD Control......Page 330
6.6 Actor-Critic Methods (*)......Page 333
6.7 R-Learning for Undiscounted Continual Tasks (*)......Page 336
6.8 Games, After States, and other Special Cases......Page 340
6.9 Conclusions......Page 343
6.10 Historical and Bibliographical Remarks......Page 345
Footnotes......Page 348
Part III: A Unified View......Page 350
7 Eligibility Traces......Page 351
7.1 n-step TD Prediction......Page 353
7.2 The Forward View of TD()......Page 358
7.3 The Backward View of TD()......Page 363
7.4 Equivalence of the Forward and Backward Views......Page 367
7.5 Sarsa()......Page 372
7.6 Q()......Page 375
7.7 Eligibility Traces for Actor-Critic Methods (*)......Page 379
7.8 Replacing Traces......Page 381
7/node10.html......Page 384
7.10 Variable (*)......Page 386
7.11 Conclusions......Page 388
7.12 Bibliographical and Historical Remarks......Page 390
8/node1.html......Page 393
8/node2.html......Page 395
8/node3.html......Page 400
8/node4.html......Page 405
8.3.1 Coarse Coding......Page 408
8.3.2 Tile Coding......Page 411
8.3.3 Radial Basis Functions......Page 415
8.3.4 Kanerva Coding......Page 417
8.4 Control with Function Approximation......Page 420
8.5 Off-Policy Bootstrapping......Page 426
8.6 Should We Bootstrap?......Page 430
8.7 Summary......Page 432
8.8 Bibliographical and Historical Remarks......Page 434
9 Planning and Learning......Page 439
9.1 Models and Planning......Page 441
9.2 Integrating Planning, Acting, and Learning......Page 444
9.3 When the Model is Wrong......Page 449
9.4 Prioritized Sweeping......Page 453
9.5 Full vs. Sample Backups......Page 457
9.6 Trajectory Sampling......Page 462
9.7 Heuristic Search......Page 466
9.8 Summary......Page 470
9.9 Historical and Bibliographical Remarks......Page 472
Footnotes......Page 474
10 Dimensions......Page 476
10.1 The Unified View......Page 477
10.2 Other Frontier Dimensions......Page 481
11 Case Studies......Page 484
11.1 TD-Gammon......Page 485
11.2 Samuel's Checkers Player......Page 490
11.3 The Acrobot......Page 494
11.4 Elevator Dispatching......Page 498
11.5 Dynamic Channel Allocation......Page 502
11.6 Job-Shop Scheduling......Page 507
References......Page 513
Summary of Notation......Page 548
20071204 128......Page 128