Reinforcement Learning: Theory and Python Implementation

Preface....5 Synopsis....5 Features....6 Errata, Codes, and Exercise Answers....6 Acknowledgements....7 Contents....8 Notations....17 Introduction of Reinforcement Learning (RL)....21 What is RL?....21 Applications of RL....23 Agent–Environment Interface....25 Taxonomy of RL....27 Task-based Taxonomy....27 Algorithm-based Taxonomy....30 Performance Metrics....31 Case Study: Agent–Environment Interface in Gym....32 Install Gym....33 Use Gym....34 Example: MountainCar....36 Summary....40 Exercises....41 Multiple Choices....41 Programming....42 Mock Interview....42 MDP: Markov Decision Process....43 MDP Model....44 DTMDP: Discrete-Time MDP....44 Environment and Dynamics....48 Policy....52 Discounted Return....55 Value....57 Definition of Value....57 Properties of Value....58 Calculate Value....62 Calculate Initial Expected Returns using Values....67 Partial Order of Policy and Policy Improvement....67 Visitation Frequency....70 Definition of Visitation Frequency....71 Properties of Visitation Frequency....73 Calculate Visitation Frequency....76 Equivalence between Visitation Frequency and Policy....78 Expectation over Visitation Frequency....79 Optimal Policy and Optimal Value....81 From Optimal Policy to Optimal Value....81 Existence and Uniqueness of Optimal Policy....82 Properties of Optimal Values....83 Calculate Optimal Values....86 Use Optimal Values to Find Optimal Strategy....91 Case Study: CliffWalking....92 Use Environment....93 Policy Evaluation....93 Solve Optimal Values....95 Solve Optimal Policy....96 Summary....96 Exercises....99 Multiple Choices....99 Programming....100 Mock Interview....100 Model-Based Numerical Iteration....101 Bellman Operators and Its Properties....101 Model-Based Policy Iteration....107 Policy Evaluation....108 Policy Iteration....111 VI: Value Iteration....112 Bootstrapping and Dynamic Programming....114 Case Study: FrozenLake....116 Use Environment....117 Use Model-Based Policy Iteration....119 Use VI....121 Summary....122 Exercises....123 Multiple Choices....123 Programming....123 Mock Interview....123 MC: Monte Carlo Learning....125 On-Policy MC Learning....126 On-Policy MC Policy Evaluation....126 MC Learning with Exploration Start....132 MC Learning on Soft Policy....135 Off-Policy MC Learning....138 Importance Sampling....138 Off-Policy MC Policy Evaluation....141 Off-Policy MC Policy Optimization....142 Case Study: Blackjack....143 Use Environment....144 On-Policy Policy Evaluation....146 On-Policy Policy Optimization....147 Off-Policy Policy Evaluation....151 Off-Policy Policy Optimization....151 Summary....152 Exercises....153 Multiple Choices....153 Programming....154 Mock Interview....154 TD: Temporal Difference Learning....155 TD return....156 On-Policy TD Learning....158 TD Policy Evaluation....158 SARSA....164 Expected SARSA....167 Off-Policy TD Learning....169 Off-Policy Algorithm based on Importance Sampling....169 Q Learning....171 Double Q Learning....173 Eligibility Trace....175 Return....175 TD()....177 Case Study: Taxi....180 Use Environment....180 On-Policy TD....182 Off-Policy TD....185 Eligibility Trace....186 Summary....188 Exercises....189 Multiple Choices....189 Programming....189 Mock Interview....190 Function Approximation....191 Basic of Function Approximation....192 Parameter Update using Gradient....195 SGD: Stochastic Gradient Descent....195 Semi-Gradient Descent....198 Semi-Gradient Descent with Eligibility Trace....200 Convergence of Function Approximation....202 Condition of Convergence....202 Baird's Counterexample....203 DQN: Deep Q Network....206 Experience Replay....207 Deep Q Learning with Target Network....210 Double DQN....212 Dueling DQN....213 Case Study: MountainCar....214 Use Environment....215 Linear Approximation....216 DQN and its Variants....221 Summary....230 Exercises....230 Multiple Choices....230 Programming....231 Mock Interview....231 PG: Policy Gradient....232 Theory of PG....232 Function Approximation for Policy....233 PG Theorem....234 Relationship between PG and Maximum Likelihood Estimate....238 On-Policy PG....239 VPG: Vanilla Policy Gradient....239 PG with Baseline....240 Off-Policy PG....242 Case Study: CartPole....243 On-Policy PG....244 Off-Policy PG....249 Summary....254 Exercises....254 Multiple Choices....254 Programming....255 Mock Interview....255 AC: Actor–Critic....256 Intuition of AC....256 On-Policy AC....257 Action-Value AC....257 Advantage AC....258 Eligibility Trace AC....260 On-Policy AC with Surrogate Objective....261 Performance Difference Lemma....261 Surrogate Advantage....262 PPO: Proximal Policy Optimization....264 Natural PG and Trust Region Algorithm....266 Kullback–Leibler Divergence and Fisher Information Matrix....267 Trust Region of Surrogate Objective....270 NPG: Natural Policy Gradient....271 TRPO: Trust Region Policy Optimization....275 Importance Sampling Off-Policy AC....276 Case Study: Acrobot....277 On-Policy AC....279 On-Policy AC with Surrogate Objective....287 NPG and TRPO....291 Importance Sampling Off-Policy AC....302 Summary....304 Exercises....305 Multiple Choices....305 Programming....306 Mock Interview....306 DPG: Deterministic Policy Gradient....307 DPG Theorem....307 On-Policy DPG....310 Off-Policy DPG....311 OPDAC: Off-Policy Deterministic Actor–Critic....311 DDPG: Deep Deterministic Policy Gradient....313 TD3: Twin Delay Deep Deterministic Policy Gradient....314 Exploration Process....316 Case Study: Pendulum....317 DDPG....319 TD3....323 Summary....327 Exercises....328 Multiple Choices....328 Programming....328 Mock Interview....328 Maximum-Entropy RL....330 Maximum-Entropy RL and Soft RL....330 Reward Engineering and Reward with Entropy....330 Soft Values....332 Soft Policy Improvement Theorem and Numeric Iterative Algorithm....334 Optimal Values....337 Soft Policy Gradient Theorem....338 Soft RL Algorithms....342 SQL: Soft Q Learning....342 SAC: Soft Actor–Critic....344 Automatic Entropy Adjustment....347 Case Study: Lunar Lander....349 Install Environment....350 Use Environment....350 Use SQL to Solve LunarLander....352 Use SAC to Solve LunarLander....355 Use Automatic Entropy Adjustment to Solve LunarLander....359 Solve LunarLanderContinuous....364 Summary....369 Exercises....370 Multiple Choices....370 Programming....370 Mock Interview....370 Policy-Based Gradient-Free Algorithms....372 Gradient-Free Algorithms....372 ES: Evolution Strategy....372 ARS: Augmented Random Search....374 Compare Gradient-Free Algorithms and Policy Gradient Algorithms....375 Case Study: BipedalWalker....376 Reward Shaping and Reward Clipping....378 ES....379 ARS....380 Summary....381 Exercises....382 Multiple Choices....382 Programming....383 Mock Interview....383 Distributional RL....384 Value Distribution and its Properties....384 Maximum Utility RL....388 Probability-Based Algorithm....391 C51: Categorical DQN....392 Categorical DQN with Utility....395 Quantile Based RL....397 QR-DQN: Quantile Regression Deep Q Network....398 IQN: Implicit Quantile Networks....401 QR Algorithms with Utility....403 Compare Categorical DQN and QR Algorithms....405 Case Study: Atari Game Pong....406 Atari Game Environment....406 The Game Pong....408 Wrapper Class of Atari Environment....410 Use Categorical DQN to Solve Pong....410 Use QR-DQN to Solve Pong....415 Use IQN to Solve Pong....419 Summary....425 Exercises....425 Multiple Choices....425 Programming....426 Mock Interview....426 Minimize Regret....427 Regret....427 MAB: Multi-Arm Bandit....429 MAB Problem....429 -Greedy Algorithm....430 UCB: Upper Confidence Bound....431 Bayesian UCB....436 Thompson Sampling....438 UCBVI: Upper Confidence Bound Value Iteration....439 Case Study: Bernoulli-Reward MAB....441 Create Custom Environment....441 -Greedy Solver....442 UCB1 Solver....444 Bayesian UCB Solver....444 Thompson Sampling Solver....445 Summary....446 Exercises....447 Multiple Choices....447 Programming....447 Mock Interview....448 Tree Search....449 MCTS: Monte Carlo Tree Search....450 Select....452 Expand and Evaluate....454 Backup....455 Decide....456 Train Networks in MCTS....456 Application in Board Game....459 Board Games....460 Self-Play....465 Neural Networks for Board Games....467 From AlphaGo to MuZero....469 Case Study: Tic-Tac-Toe....472 boardgame2: Board Game Environment....472 Exhaustive Search....477 Heuristic Search....479 Summary....486 Exercises....487 Multiple Choices....487 Programming....488 Mock Interview....488 More Agent–Environment Interfaces....489 Average Reward DTMDP....490 Average Reward....490 Differential Values....494 Optimal Policy....498 CTMDP: Continuous-Time MDP....502 Non-Homogenous MDP....506 Representation of Non-Stationary States....506 Bounded Time Index....507 Unbounded Time Index....508 SMDP: Semi-MDP....510 SMDP and its Values....510 Find Optimal Policy....513 HRL: Hierarchical Reinforcement Learning....514 POMDP: Partially Observable Markov Decision Process....515 DTPOMDP: Discrete-Time POMDP....515 Belief....516 Belief MDP....521 Belief Values....524 Belief Values for Finite POMDP....527 Use Memory....530 Case Study: Tiger....531 Compare Discounted Return Expectation and Average Reward....531 Belief MDP....533 Non-Stationary Belief State Values....534 Summary....536 Exercises....538 Multiple Choices....538 Programming....539 Mock Interview....539 Learn from Feedback and Imitation Learning....540 Learn from Feedback....540 Reward Model....541 PbRL: Preference-based RL....542 RLHF: Reinforcement Learning with Human Feedback....543 IL: Imitation Learning....546 f-Divergences and their Properties....547 BC: Behavior Cloning....554 GAIL: Generative Adversarial Imitation Learning....556 Application In Training GPT....559 Case Study: Humanoid....560 Use PyBullet....561 Use BC to IL....564 Use GAIL to IL....566 Summary....572 Exercises....573 Multiple Choices....573 Programming....574 Mock Interview....574