ReinforcementLearning:AnIntroduction(2018年1月）资源-CSDN文库

Introduction

需积分: 9 103 浏览量 2018-01-05 16:37:11 上传评论 1 收藏 12.14MB PDF 举报

资源推荐

资源详情

资源评论

Reinforcement Learning:

An Introduction

Second edition, in progress

****Complete Draft****

January 1, 2018

Richard S. Sutton and Andrew G. Barto

 2014, 2015, 2016, 2017, 2018

The text is now complete, except possibly for one more case study to be added to Chapter 16. An

index still needs to be added. Please send any errors to rich@richsutton.com and barto@cs.umass.edu.

We are also very interested in correcting any important omissions in the “Bibliographical and Historical

Remarks” at the end of each chapter. If you think of something that really should have been cited,

please let us know and we can try to get it corrected before the ﬁnal version is printed.

A Bradford Book

The MIT Press

Cambridge, Massachusetts

London, England

Contents

Preface to the Second Edition ix

Preface to the First Edition xiii

Summary of Notation xv

1 Introduction 1

1.1 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Elements of Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Limitations and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 An Extended Example: Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.7 Early History of Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

I Tabular Solution Methods 18

2 Multi-armed Bandits 19

2.1 A k -armed Bandit Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Action-value Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 The 10-armed Testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5 Tracking a Nonstationary Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.6 Optimistic Initial Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.7 Upper-Conﬁdence-Bound Action Selection . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.8 Gradient Bandit Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.9 Associative Search (Contextual Bandits) . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3 Finite Markov Decision Processes 37

3.1 The Agent–Environment Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

iii

iv CONTENTS

3.3 Returns and Episodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.4 Uniﬁed Notation for Episodic and Continuing Tasks . . . . . . . . . . . . . . . . . . . . 44

3.5 Policies and Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.6 Optimal Policies and Optimal Value Functions . . . . . . . . . . . . . . . . . . . . . . . 49

3.7 Optimality and Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4 Dynamic Programming 57

4.1 Policy Evaluation (Prediction) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.2 Policy Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.4 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.5 Asynchronous Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.6 Generalized Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.7 Eﬃciency of Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5 Monte Carlo Methods 73

5.1 Monte Carlo Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.2 Monte Carlo Estimation of Action Values . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.3 Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.4 Monte Carlo Control without Exploring Starts . . . . . . . . . . . . . . . . . . . . . . . 80

5.5 Oﬀ-policy Prediction via Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . 82

5.6 Incremental Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.7 Oﬀ-policy Monte Carlo Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

5.8 *Discounting-aware Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 90

5.9 *Per-decision Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6 Temporal-Diﬀerence Learning 95

6.1 TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6.2 Advantages of TD Prediction Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.3 Optimality of TD(0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.4 Sarsa: On-policy TD Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

6.5 Q-learning: Oﬀ-policy TD Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

6.6 Expected Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6.7 Maximization Bias and Double Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6.8 Games, Afterstates, and Other Special Cases . . . . . . . . . . . . . . . . . . . . . . . . 110

6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

7 n-step Bootstrapping 113

7.1 n-step TD Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

CONTENTS v

7.2 n-step Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

7.3 n-step Oﬀ-policy Learning by Importance Sampling . . . . . . . . . . . . . . . . . . . . 119

7.4 *Per-decision Oﬀ-policy Methods with Control Variates . . . . . . . . . . . . . . . . . . 120

7.5 Oﬀ-policy Learning Without Importance Sampling:

The n-step Tree Backup Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

7.6 *A Unifying Algorithm: n-step Q(σ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

8 Planning and Learning with Tabular Methods 129

8.1 Models and Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

8.2 Dyna: Integrating Planning, Acting, and Learning . . . . . . . . . . . . . . . . . . . . . 131

8.3 When the Model Is Wrong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

8.4 Prioritized Sweeping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

8.5 Expected vs. Sample Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

8.6 Trajectory Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

8.7 Real-time Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

8.8 Planning at Decision Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

8.9 Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

8.10 Rollout Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

8.11 Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

8.12 Summary of the Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

8.13 Summary of Part I: Dimensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

II Approximate Solution Methods 158

9 On-policy Prediction with Approximation 159

9.1 Value-function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

9.2 The Prediction Objective (VE) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

9.3 Stochastic-gradient and Semi-gradient Methods . . . . . . . . . . . . . . . . . . . . . . . 162

9.4 Linear Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

9.5 Feature Construction for Linear Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 169

9.5.1 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

9.5.2 Fourier Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

9.5.3 Coarse Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

9.5.4 Tile Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

9.5.5 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

9.6 Selecting Step-Size Parameters Manually . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

9.7 Nonlinear Function Approximation: Artiﬁcial Neural Networks . . . . . . . . . . . . . . 181

9.8 Least-Squares TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

9.9 Memory-based Function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

9.10 Kernel-based Function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

剩余443页未读，继续阅读

评论收藏

内容反馈

dzm_neu

粉丝: 2
资源: 11

Reinforcement Learning: An Introduction (2018年1月）

最新资源

Reinforcement Learning: An Introduction (2018年1月）

Reinforcement Learning-An introduction

reinforcement learning ：an introduction 2018最新版book pdf格式

Reinforcement Learning: An Introduction（最新版书籍+代码，February 28, 2018）

Reinforcement Learning_An Introduction多版本合集

Reinforcement Learning: An Introduction second edition

增强学习导论（Reinforcement Learning An Introduction_Sutton）

Reinforcement Learning An Introduction(2nd)2018.pdf

Reinforcement Learning：An Introduction

An Introduction to Reinforcement Learning

Reinforcement Learning - An Introduction

Reinforcement Learning: An Introduction

Reinforcement Learning: An Introduction 2018年 第二版和之前2015中文翻译版

Reinforcement Learning：An Introduction.pdf

Reinforcement Learning: An Introduction 自学代码（第二章）

Reinforcement Learning: An Introduction 2nd solutions （第二版 答案）

Reinforcement Learning An Introduction.pdf

Reinforcement learning an introduction中文pdf

Reinforcement Learning - An Introduction 2nd 2017 6月版

Reinforcement Learning An Introduction second edition

Reinforcement Learning: An Introduction最新版习题解答（第一版本）

Reinforcement Learning: An Introduction 第二版

最新资源

Reinforcement Learning: An Introduction 2018年第二版和之前2015中文翻译版

Reinforcement Learning: An Introduction 2nd solutions （第二版答案）