Contents

1. Exact Dynamic Programming

1.1. DeterministicDynamicProgramming . . . . . . . . . . . p. 2

1.1.1. DeterministicProblems . . . . . . . . . . . . . . p. 2

1.1.2. TheDynamicProgrammingAlgorithm . . . . . . . . p. 7

1.1.3. Approximation inValue Space . . . . . . . . . . . p. 12

1.2. StochasticDynamicProgramming . . . . . . . . . . . . . p. 14

1.3. Examples,Variations, and Simplifications . . . . . . . . . p. 18

1.3.1. Deterministic ShortestPathProblems . . . . . . . . p. 19

1.3.2. DiscreteDeterministicOptimization . . . . . . . . . p. 21

1.3.3. Problemswith aTermination State . . . . . . . . . p. 25

1.3.4. Forecasts . . . . . . . . . . . . . . . . . . . . . p. 26

1.3.5. Problems with Uncontrollable State Components . . . p. 29

1.3.6. PartialState Information andBelief States . . . . . . p. 34

1.3.7. LinearQuadraticOptimalControl . . . . . . . . . . p. 38

1.3.8. SystemswithUnknownParameters -Adaptive . . . . . .

Control . . . . . . . . . . . . . . . . . . . . . p. 40

1.4. ReinforcementLearning andOptimalControl - Some . . . . . .

Terminology . . . . . . . . . . . . . . . . . . . . . . p. 43

1.5. Notes and Sources . . . . . . . . . . . . . . . . . . . p. 45

2. Approximation in Value Space

2.1. ApproximationApproaches inReinforcementLearning . . . . p. 50

2.1.1. General Issues ofApproximation inValue Space . . . . p. 54

2.1.2. Off-Line andOn-LineMethods . . . . . . . . . . . p. 56

2.1.3. Model-Based Simplification of the Lookahead . . . . . .

Minimization . . . . . . . . . . . . . . . . . . . p. 57

2.1.4. Model-Free off-Line Q-Factor Approximation . . . . p. 58

2.1.5. Approximation inPolicy Space onTop of . . . . . . . .

ApproximationinValue Space . . . . . . . . . . . p. 61

2.1.6. When is Approximation in Value Space Effective? . . . p. 62

2.2. Multistep Lookahead . . . . . . . . . . . . . . . . . . p. 64

??ii

viii Contents

2.2.1. Multistep Lookahead and Rolling Horizon . . . . . . p. 65

2.2.2. Multistep Lookahead and Deterministic Problems . . . p. 67

2.3. Problem Approximation . . . . . . . . . . . . . . . . . p. 69

2.3.1. Enforced Decomposition . . . . . . . . . . . . . . p. 69

2.3.2. Probabilistic Approximation - Certainty Equivalent . . . .

Control . . . . . . . . . . . . . . . . . . . . . p. 76

2.4. Rollout and the Policy Improvement Principle . . . . . . . p. 83

2.4.1. On-Line Rollout for Deterministic Discrete . . . . . . . .

Optimization . . . . . . . . . . . . . . . . . . . p. 84

2.4.2. Stochastic Rollout and Monte Carlo Tree Search . . . p. 95

2.4.3. Rollout with an Expert . . . . . . . . . . . . . p. 104

2.5. On-Line Rollout for Deterministic Infinite-Spaces Problems - . . .

Optimization Heuristics . . . . . . . . . . . . . . . . p. 106

2.5.1. Model Predictive Control . . . . . . . . . . . . . p. 108

2.5.2. Target Tubes and the Constrained Controllability . . . . .

Condition . . . . . . . . . . . . . . . . . . . p. 115

2.5.3. Variants of Model Predictive Control . . . . . . . p. 118

2.6. Notes and Sources . . . . . . . . . . . . . . . . . . p. 120

3. Parametric Approximation

3.1. Approximation Architectures . . . . . . . . . . . . . . p. 126

3.1.1. Linear and Nonlinear Feature-Based Architectures . . p. 126

3.1.2. Training of Linear and Nonlinear Architectures . . . p. 134

3.1.3. Incremental Gradient and Newton Methods . . . . . p. 135

3.2. Neural Networks . . . . . . . . . . . . . . . . . . . p. 149

3.2.1. Training of Neural Networks . . . . . . . . . . . p. 153

3.2.2. Multilayer and Deep Neural Networks . . . . . . . p. 157

3.3. Sequential Dynamic Programming Approximation . . . . . p. 161

3.4. Q-Factor Parametric Approximation . . . . . . . . . . . p. 162

3.5. Parametric Approximation in Policy Space by . . . . . . . . .

Classification . . . . . . . . . . . . . . . . . . . . . p. 165

3.6. Notes and Sources . . . . . . . . . . . . . . . . . . p. 171

4. Infinite Horizon Dynamic Programming

4.1. An Overview of Infinite Horizon Problems . . . . . . . . p. 174

4.2. Stochastic Shortest Path Problems . . . . . . . . . . . p. 177

4.3. Discounted Problems . . . . . . . . . . . . . . . . . p. 187

4.4. Semi-Markov Discounted Problems . . . . . . . . . . . p. 192

4.5. Asynchronous Distributed Value Iteration . . . . . . . . p. 197

4.6. Policy Iteration . . . . . . . . . . . . . . . . . . . p. 200

4.6.1. Exact Policy Iteration . . . . . . . . . . . . . . p. 200

4.6.2. Optimistic and Multistep Lookahead Policy . . . . . . .

Iteration . . . . . . . . . . . . . . . . . . . . p. 205

4.6.3. Policy Iteration for Q-factors . . . . . . . . . . . p. 208

Contents i??

4.7. Notes and Sources . . . . . . . . . . . . . . . . . . p. 209

4.8. Appendix: MathematicalAnalysis . . . . . . . . . . . p. 211

4.8.1. Proofs for Stochastic ShortestPathProblems . . . . p. 212

4.8.2. Proofs forDiscountedProblems . . . . . . . . . . p. 217

4.8.3. ConvergenceofExact andOptimistic . . . . . . . . . .

Policy Iteration . . . . . . . . . . . . . . . . p. 218

5. Infinite Horizon Reinforcement Learning

5.1. Approximation in Value Space - Performance Bounds . . . p. 222

5.1.1. LimitedLookahead . . . . . . . . . . . . . . . p. 224

5.1.2. Rollout and Approximate Policy Improvement . . . p. 227

5.1.3. ApproximatePolicy Iteration . . . . . . . . . . . p. 232

5.2. FittedValue Iteration . . . . . . . . . . . . . . . . . p. 235

5.3. Simulation-BasedPolicy IterationwithParametric . . . . . . .

Approximation . . . . . . . . . . . . . . . . . . . . p. 239

5.3.1. Self-Learning andActor-CriticMethods . . . . . . p. 239

5.3.2. Model-Based Variant of a Critic-Only Method . . . p. 241

5.3.3. Model-FreeVariant of aCritic-OnlyMethod . . . . p. 243

5.3.4. Implementation Issues ofParametricPolicy . . . . . . .

Iteration . . . . . . . . . . . . . . . . . . . . p. 246

5.3.5. Convergence Issues ofParametricPolicy Iteration - . . . .

Oscillations . . . . . . . . . . . . . . . . . . . p. 249

5.4. Q-Learning . . . . . . . . . . . . . . . . . . . . . p. 253

5.4.1. Optimistic Policy Iteration with Parametric Q-Factor . . .

Approximation- SARSAandDQN . . . . . . . . p. 255

5.5. AdditionalMethods -TemporalDifferences . . . . . . . p. 256

5.6. Exact andApproximateLinearProgramming . . . . . . p. 267

5.7. Approximation inPolicy Space . . . . . . . . . . . . . p. 270

5.7.1. Training byCostOptimization -PolicyGradient, . . . . .

Cross-Entropy,andRandomSearchMethods . . . . p. 276

5.7.2. Expert-BasedSupervisedLearning . . . . . . . . p. 286

5.7.3. ApproximatePolicy Iteration,Rollout, and . . . . . . .

ApproximationinPolicySpace . . . . . . . . . . p. 288

5.8. Notes and Sources . . . . . . . . . . . . . . . . . . p. 293

5.9. Appendix: MathematicalAnalysis . . . . . . . . . . . p. 298

5.9.1. Performance Bounds for Multistep Lookahead . . . . p. 299

5.9.2. Performance Bounds for Rollout . . . . . . . . . . p. 301

5.9.3. Performance Bounds for Approximate Policy . . . . . . .

Iteration . . . . . . . . . . . . . . . . . . . . p. 304

6. Aggregation

6.1. AggregationwithRepresentativeStates . . . . . . . . . p. 308

6.1.1. Continuous State and Control Space Discretization . p. 314

6.1.2. Continuous State Space - POMDP Discretization . . p. 315

?? Contents

6.2. AggregationwithRepresentativeFeatures . . . . . . . . p. 317

6.2.1. Hard Aggregation and Error Bounds . . . . . . . . p. 320

6.2.2. AggregationUsingFeatures . . . . . . . . . . . . p. 322

6.3. Methods for Solving theAggregateProblem . . . . . . . p. 328

6.3.1. Simulation-BasedPolicy Iteration . . . . . . . . . p. 328

6.3.2. Simulation-Based Value Iteration . . . . . . . . . p. 331

6.4. Feature-BasedAggregationwith aNeuralNetwork . . . . p. 332

6.5. BiasedAggregation . . . . . . . . . . . . . . . . . . p. 334

6.6. Notes and Sources . . . . . . . . . . . . . . . . . . p. 337

6.7. Appendix: MathematicalAnalysis . . . . . . . . . . . p. 340

References . . . . . . . . . . . . . . . . . . . . . . . p. 345

Index . . . . . . . . . . . . . . . . . . . . . . . . . . p. 369