第1页 / 共455页
第2页 / 共455页
第3页 / 共455页
第4页 / 共455页
第5页 / 共455页
第6页 / 共455页
第7页 / 共455页
第8页 / 共455页
Reinforcement Learning: An Introduction，Richard S. Sutton and An....pdf
12chaper
5chaper
目录
i
Reinforcement Learning:
An Introduction
Second edition, in progress
****Draft****
Richard S. Sutton and Andrew G. Barto
c 2014, 2015, 2016
A Bradford Book
The MIT Press
Cambridge, Massachusetts
London, England
ii
In memory of A. Harry Klopf
Contents
Preface to the First Edition
Preface to the Second Edition
Summary of Notation
1 The Reinforcement Learning Problem
1.1 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Examples
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Elements of Reinforcement Learning . . . . . . . . . . . . . . . . . . .
1.4 Limitations and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . .
ix
xiii
xvii
1
1
4
6
7
1.5 An Extended Example: Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . 10
1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 History of Reinforcement Learning . . . . . . . . . . . . . . . . . . . . 15
1.8 Bibliographical Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . 23
I Tabular Solution Methods
2 Multi-arm Bandits
25
27
2.1 A k-Armed Bandit Problem . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Action-Value Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3
Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Tracking a Nonstationary Problem . . . . . . . . . . . . . . . . . . . . 34
2.5 Optimistic Initial Values . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6 Upper-Confidence-Bound Action Selection . . . . . . . . . . . . . . . . 37
2.7 Gradient Bandit Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 38
2.8 Associative Search (Contextual Bandits) . . . . . . . . . . . . . . . . . 42
2.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
iii
iv
3 Finite Markov Decision Processes
CONTENTS
47
3.1 The Agent–Environment Interface
. . . . . . . . . . . . . . . . . . . . 47
3.2 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3 Returns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
. . . . . . . . . . 54
3.4 Unified Notation for Episodic and Continuing Tasks
∗3.5 The Markov Property . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.6 Markov Decision Processes . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.7 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.8 Optimal Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.9 Optimality and Approximation . . . . . . . . . . . . . . . . . . . . . . 72
3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4 Dynamic Programming
79
4.1 Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.2 Policy Improvement
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.4 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.5 Asynchronous Dynamic Programming . . . . . . . . . . . . . . . . . . 91
4.6 Generalized Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . 93
4.7 Efficiency of Dynamic Programming . . . . . . . . . . . . . . . . . . . 94
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5 Monte Carlo Methods
99
5.1 Monte Carlo Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2 Monte Carlo Estimation of Action Values
. . . . . . . . . . . . . . . . 104
5.3 Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.4 Monte Carlo Control without Exploring Starts
. . . . . . . . . . . . . 108
5.5 Off-policy Prediction via Importance Sampling . . . . . . . . . . . . . 111
5.6
Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . 116
5.7 Off-Policy Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . 118
∗5.8 Return-Specific Importance Sampling . . . . . . . . . . . . . . . . . . 120
5.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6 Temporal-Difference Learning
127
6.1 TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.2 Advantages of TD Prediction Methods . . . . . . . . . . . . . . . . . . 131
6.3 Optimality of TD(0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.4 Sarsa: On-Policy TD Control
. . . . . . . . . . . . . . . . . . . . . . . 137
CONTENTS
v
6.5 Q-learning: Off-Policy TD Control
. . . . . . . . . . . . . . . . . . . . 140
6.6 Expected Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.7 Maximization Bias and Double Learning . . . . . . . . . . . . . . . . . 143
6.8 Games, Afterstates, and Other Special Cases
. . . . . . . . . . . . . . 145
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7 Multi-step Bootstrapping
151
7.1 n-step TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.2 n-step Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.3 n-step Off-policy Learning by Importance Sampling
. . . . . . . . . . 158
7.4 Off-policy Learning Without Importance Sampling:
The n-step Tree Backup Algorithm . . . . . . . . . . . . . . . . . . . . 160
∗7.5 A Unifying Algorithm: n-step Q(σ) . . . . . . . . . . . . . . . . . . . . 162
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8 Planning and Learning with Tabular Methods
167
8.1 Models and Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.2 Dyna: Integrating Planning, Acting, and Learning . . . . . . . . . . . 169
8.3 When the Model Is Wrong . . . . . . . . . . . . . . . . . . . . . . . . . 174
8.4 Prioritized Sweeping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.5 Planning as Part of Action Selection . . . . . . . . . . . . . . . . . . . 180
8.6 Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.7 Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
II Approximate Solution Methods
9 On-policy Prediction with Approximation
189
191
9.1 Value-function Approximation . . . . . . . . . . . . . . . . . . . . . . . 191
9.2 The Prediction Objective (MSVE)
. . . . . . . . . . . . . . . . . . . . 192
9.3 Stochastic-gradient and Semi-gradient Methods . . . . . . . . . . . . . 194
9.4 Linear Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
9.5 Feature Construction for Linear Methods
. . . . . . . . . . . . . . . . 203
9.5.1 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
9.5.2 Fourier Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
9.5.3 Coarse Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
9.5.4 Tile Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
9.5.5 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . 215
vi
CONTENTS
9.6 Nonlinear Function Approximation: Artificial Neural Networks . . . . 216
9.7 Least-Squares TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
9.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
10 On-policy Control with Approximation
229
10.1 Episodic Semi-gradient Control
. . . . . . . . . . . . . . . . . . . . . . 229
10.2 n-step Semi-gradient Sarsa
. . . . . . . . . . . . . . . . . . . . . . . . 232
10.3 Average Reward: A New Problem Setting for Continuing Tasks . . . . 234
10.4 Deprecating the Discounted Setting . . . . . . . . . . . . . . . . . . . . 238
10.5 n-step Differential Semi-gradient Sarsa . . . . . . . . . . . . . . . . . . 239
10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
11 Off-policy Methods with Approximation
243
11.1 Semi-gradient Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
11.2 Baird’s Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . 245
11.3 The Deadly Triad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
12 Eligibility Traces
251
12.1 The λ-return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
12.2 TD(λ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
12.3 An On-line Forward View . . . . . . . . . . . . . . . . . . . . . . . . . 259
12.4 True Online TD(λ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
12.5 Dutch Traces in Monte Carlo Learning . . . . . . . . . . . . . . . . . . 263
13 Policy Gradient Methods
265
13.1 Policy Approximation and its Advantages . . . . . . . . . . . . . . . . 266
13.2 The Policy Gradient Theorem . . . . . . . . . . . . . . . . . . . . . . . 268
13.3 REINFORCE: Monte Carlo Policy Gradient . . . . . . . . . . . . . . . 270
13.4 REINFORCE with Baseline . . . . . . . . . . . . . . . . . . . . . . . . 272
13.5 Actor-Critic Methods
. . . . . . . . . . . . . . . . . . . . . . . . . . . 273
13.6 Policy Gradient for Continuing Problems (Average Reward Rate) . . . 275
13.7 Policy Parameterization for Continuous Actions . . . . . . . . . . . . . 278
III Looking Deeper
14 Psychology
280
281
14.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
14.2 Prediction and Control . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
CONTENTS
vii
14.3 Classical Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
14.3.1 The Rescorla-Wagner Model
. . . . . . . . . . . . . . . . . . . 289
14.3.2 The TD Model
. . . . . . . . . . . . . . . . . . . . . . . . . . . 291
14.3.3 TD Model Simulations . . . . . . . . . . . . . . . . . . . . . . . 292
14.4 Instrumental Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . 301
14.5 Delayed Reinforcement . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
14.6 Cognitive Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
14.7 Habitual and Goal-Directed Behavior . . . . . . . . . . . . . . . . . . . 309
14.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
14.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
14.10Bibliographical and Historical Remarks
. . . . . . . . . . . . . . . . . 315
15 Neuroscience
319
15.1 Neuroscience Basics
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
15.2 Reward Signals, Reinforcement Signals, Values, and Prediction Errors 322
15.3 The Reward Prediction Error Hypothesis
. . . . . . . . . . . . . . . . 324
15.4 Dopamine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
15.5 Experimental Support for the Reward Prediction Error Hypothesis . . 329
15.6 TD Error/Dopamine Correspondence . . . . . . . . . . . . . . . . . . . 332
15.7 Neural Actor-Critic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
15.8 Actor and Critic Learning Rules
. . . . . . . . . . . . . . . . . . . . . 342
15.9 Hedonistic Neurons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
15.10Collective Reinforcement Learning . . . . . . . . . . . . . . . . . . . . 348
15.11Model-Based Methods in the Brain . . . . . . . . . . . . . . . . . . . . 351
15.12Addiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
15.13Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
15.14Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
15.15Bibliographical and Historical Remarks
. . . . . . . . . . . . . . . . . 357
16 Applications and Case Studies
365
16.1 TD-Gammon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
16.2 Samuel’s Checkers Player
. . . . . . . . . . . . . . . . . . . . . . . . . 370
16.3 The Acrobot
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
16.4 Watson’s Daily-Double Wagering . . . . . . . . . . . . . . . . . . . . 376
16.5 Optimizing Memory Control . . . . . . . . . . . . . . . . . . . . . . . . 379
16.6 Human-Level Video Game Play . . . . . . . . . . . . . . . . . . . . . . 384
16.7 Mastering the Game of Go . . . . . . . . . . . . . . . . . . . . . . . . . 389
viii
CONTENTS
16.8 Personalized Web Services . . . . . . . . . . . . . . . . . . . . . . . . . 396
16.9 Thermal Soaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
17 Frontiers
403
17.1 The Unified View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
References
407
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
