1 Introduction of Reinforcement Learning (RL) . . . . . . . . . . . . . . . . . . . . . 1
1.1 What is RL? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Applications of RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Agent–Environment Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Taxonomy of RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Task-based Taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Algorithm-based Taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6 Case Study: Agent–Environment Interface in Gym . . . . . . . . . . . . . . . 12
1.6.1 Install Gym . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6.2 Use Gym . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6.3 Example: MountainCar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.8.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 MDP: Markov Decision Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1 MDP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.1 DTMDP: Discrete-Time MDP . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.2 Environment and Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.3 Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.1.4 Discounted Return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.1 Definition of Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.2 Properties of Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.3 Calculate Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.4 Calculate Initial Expected Returns using Values . . . . . . . . . . . 47
2.2.5 Partial Order of Policy and Policy Improvement . . . . . . . . . . . 47
2.3 Visitation Frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.3.1 Definition of Visitation Frequency . . . . . . . . . . . . . . . . . . . . . . 51
2.3.2 Properties of Visitation Frequency . . . . . . . . . . . . . . . . . . . . . . 53
2.3.3 Calculate Visitation Frequency . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.3.4 Equivalence between Visitation Frequency and Policy . . . . . 58
2.3.5 Expectation over Visitation Frequency . . . . . . . . . . . . . . . . . . 59
2.4 Optimal Policy and Optimal Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.4.1 From Optimal Policy to Optimal Value . . . . . . . . . . . . . . . . . . 61
2.4.2 Existence and Uniqueness of Optimal Policy . . . . . . . . . . . . . 62
2.4.3 Properties of Optimal Values . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.4.4 Calculate Optimal Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.4.5 Use Optimal Values to Find Optimal Strategy . . . . . . . . . . . . 71
2.5 Case Study: CliffWalking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.5.1 Use Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.5.2 Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.5.3 Solve Optimal Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.5.4 Solve Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.7.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.7.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.7.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3 Model-Based Numerical Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.1 Bellman Operators and Its Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2 Model-Based Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2.1 Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.2.2 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.3 VI: Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.4 Bootstrapping and Dynamic Programming . . . . . . . . . . . . . . . . . . . . . 94
3.5 Case Study: FrozenLake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.5.1 Use Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.5.2 Use Model-Based Policy Iteration . . . . . . . . . . . . . . . . . . . . . . 99
3.5.3 Use VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.7.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.7.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.7.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4 MC: Monte Carlo Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.1 On-Policy MC Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.1.1 On-Policy MC Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . 106
4.1.2 MC Learning with Exploration Start . . . . . . . . . . . . . . . . . . . . 112
4.1.3 MC Learning on Soft Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2 Off-Policy MC Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.1 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2.2 Off-Policy MC Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . 121
4.2.3 Off-Policy MC Policy Optimization . . . . . . . . . . . . . . . . . . . . . 122
4.3 Case Study: Blackjack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.3.1 Use Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.3.2 On-Policy Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.3.3 On-Policy Policy Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.3.4 Off-Policy Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.3.5 Off-Policy Policy Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 131
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.5.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.5.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.5.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5 TD: Temporal Difference Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.1 TD return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.2 On-Policy TD Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.2.1 TD Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.2.2 SARSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.2.3 Expected SARSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.3 Off-Policy TD Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
5.3.1 Off-Policy Algorithm based on Importance Sampling . . . . . . 149
5.3.2 Q Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.3.3 Double Q Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.4 Eligibility Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.4.1 𝜆 Return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.4.2 TD(𝜆) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.5 Case Study: Taxi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.5.1 Use Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.5.2 On-Policy TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
5.5.3 Off-Policy TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
5.5.4 Eligibility Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.7.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.7.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.7.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6 Function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.1 Basic of Function Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
6.2 Parameter Update using Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6.2.1 SGD: Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . . 175
6.2.2 Semi-Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
6.2.3 Semi-Gradient Descent with Eligibility Trace . . . . . . . . . . . . . 180
6.3 Convergence of Function Approximation . . . . . . . . . . . . . . . . . . . . . . . 182
6.3.1 Condition of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
6.3.2 Baird’s Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
6.4 DQN: Deep Q Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6.4.1 Experience Replay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
6.4.2 Deep Q Learning with Target Network . . . . . . . . . . . . . . . . . . 190
6.4.3 Double DQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
6.4.4 Dueling DQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
6.5 Case Study: MountainCar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
6.5.1 Use Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
6.5.2 Linear Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
6.5.3 DQN and its Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.7.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.7.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
6.7.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7 PG: Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.1 Theory of PG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.1.1 Function Approximation for Policy . . . . . . . . . . . . . . . . . . . . . 214
7.1.2 PG Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
7.1.3 Relationship between PG and Maximum Likelihood Estimate . 219
7.2 On-Policy PG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
7.2.1 VPG: Vanilla Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . 220
7.2.2 PG with Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
7.3 Off-Policy PG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
7.4 Case Study: CartPole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
7.4.1 On-Policy PG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.4.2 Off-Policy PG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.6.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.6.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.6.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
8 AC: Actor–Critic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
8.1 Intuition of AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
8.2 On-Policy AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.2.1 Action-Value AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.2.2 Advantage AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
8.2.3 Eligibility Trace AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
8.3 On-Policy AC with Surrogate Objective . . . . . . . . . . . . . . . . . . . . . . . . 242
8.3.1 Performance Difference Lemma . . . . . . . . . . . . . . . . . . . . . . . . 242
8.3.2 Surrogate Advantage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.3.3 PPO: Proximal Policy Optimization . . . . . . . . . . . . . . . . . . . . . 245
8.4 Natural PG and Trust Region Algorithm . . . . . . . . . . . . . . . . . . . . . . . 247
8.4.1 Kullback–Leibler Divergence and Fisher Information Matrix . 248
8.4.2 Trust Region of Surrogate Objective . . . . . . . . . . . . . . . . . . . . 251
8.4.3 NPG: Natural Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . 252
8.4.4 TRPO: Trust Region Policy Optimization . . . . . . . . . . . . . . . . 256
8.5 Importance Sampling Off-Policy AC . . . . . . . . . . . . . . . . . . . . . . . . . . 257
8.6 Case Study: Acrobot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
8.6.1 On-Policy AC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
8.6.2 On-Policy AC with Surrogate Objective . . . . . . . . . . . . . . . . . 268
8.6.3 NPG and TRPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8.6.4 Importance Sampling Off-Policy AC . . . . . . . . . . . . . . . . . . . . 283
8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
8.8.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
8.8.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
8.8.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
9 DPG: Deterministic Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
9.1 DPG Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
9.2 On-Policy DPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
9.3 Off-Policy DPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
9.3.1 OPDAC: Off-Policy Deterministic Actor–Critic . . . . . . . . . . . 293
9.3.2 DDPG: Deep Deterministic Policy Gradient . . . . . . . . . . . . . . 295
9.3.3 TD3: Twin Delay Deep Deterministic Policy Gradient . . . . . 296
9.4 Exploration Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
9.5 Case Study: Pendulum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
9.5.1 DDPG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
9.5.2 TD3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
9.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.7.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.7.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.7.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
10 Maximum-Entropy RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.1 Maximum-Entropy RL and Soft RL . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.1.1 Reward Engineering and Reward with Entropy . . . . . . . . . . . . 313
10.1.2 Soft Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
10.1.3 Soft Policy Improvement Theorem and Numeric Iterative
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
10.1.4 Optimal Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
10.1.5 Soft Policy Gradient Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 321
10.2 Soft RL Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
10.2.1 SQL: Soft Q Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
10.2.2 SAC: Soft Actor–Critic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
10.3 Automatic Entropy Adjustment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
10.4 Case Study: Lunar Lander . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
10.4.1 Install Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
10.4.2 Use Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
10.4.3 Use SQL to Solve LunarLander . . . . . . . . . . . . . . . . . . . . . . . . 335
10.4.4 Use SAC to Solve LunarLander . . . . . . . . . . . . . . . . . . . . . . . . 338
10.4.5 Use Automatic Entropy Adjustment to Solve LunarLander . . 342
10.4.6 Solve LunarLanderContinuous . . . . . . . . . . . . . . . . . . . . . . . . . 347
10.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
10.6.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
10.6.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
10.6.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
11 Policy-Based Gradient-Free Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 355
11.1 Gradient-Free Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
11.1.1 ES: Evolution Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
11.1.2 ARS: Augmented Random Search . . . . . . . . . . . . . . . . . . . . . . 357
11.2 Compare Gradient-Free Algorithms and Policy Gradient Algorithms .
11.3 Case Study: BipedalWalker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
11.3.1 Reward Shaping and Reward Clipping . . . . . . . . . . . . . . . . . . . 361
11.3.2 ES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
11.3.3 ARS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
11.5.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
11.5.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
11.5.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
12 Distributional RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
12.1 Value Distribution and its Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
12.2 Maximum Utility RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
12.3 Probability-Based Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
12.3.1 C51: Categorical DQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
12.3.2 Categorical DQN with Utility . . . . . . . . . . . . . . . . . . . . . . . . . . 378
12.4 Quantile Based RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
12.4.1 QR-DQN: Quantile Regression Deep Q Network . . . . . . . . . . 381
12.4.2 IQN: Implicit Quantile Networks . . . . . . . . . . . . . . . . . . . . . . . 384
12.4.3 QR Algorithms with Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
12.5 Compare Categorical DQN and QR Algorithms . . . . . . . . . . . . . . . . . 388
12.6 Case Study: Atari Game Pong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
12.6.1 Atari Game Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
12.6.2 The Game Pong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
12.6.3 Wrapper Class of Atari Environment . . . . . . . . . . . . . . . . . . . . 393
12.6.4 Use Categorical DQN to Solve Pong . . . . . . . . . . . . . . . . . . . . 393
12.6.5 Use QR-DQN to Solve Pong . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
12.6.6 Use IQN to Solve Pong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
12.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
12.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
12.8.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
12.8.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
12.8.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
13 Minimize Regret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
13.1 Regret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
13.2 MAB: Multi-Arm Bandit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
13.2.1 MAB Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
13.2.2 𝜀-Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
13.2.3 UCB: Upper Confidence Bound . . . . . . . . . . . . . . . . . . . . . . . . 415
13.2.4 Bayesian UCB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
13.2.5 Thompson Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
13.3 UCBVI: Upper Confidence Bound Value Iteration . . . . . . . . . . . . . . . 423
13.4 Case Study: Bernoulli-Reward MAB . . . . . . . . . . . . . . . . . . . . . . . . . . 425
13.4.1 Create Custom Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
13.4.2 𝜀-Greedy Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
13.4.3 UCB1 Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
13.4.4 Bayesian UCB Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
13.4.5 Thompson Sampling Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
13.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
13.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
13.6.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
13.6.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
13.6.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
14 Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
14.1 MCTS: Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
14.1.1 Select . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
14.1.2 Expand and Evaluate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
14.1.3 Backup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
14.1.4 Decide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
14.1.5 Train Networks in MCTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
14.2 Application in Board Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
14.2.1 Board Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
14.2.2 Self-Play . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
14.2.3 Neural Networks for Board Games . . . . . . . . . . . . . . . . . . . . . . 451
14.2.4 From AlphaGo to MuZero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
14.3 Case Study: Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
14.3.1 boardgame2: Board Game Environment . . . . . . . . . . . . . . . . . 456
14.3.2 Exhaustive Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
14.3.3 Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
14.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
14.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
14.5.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
14.5.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
14.5.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
15 More Agent–Environment Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
15.1 Average Reward DTMDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
15.1.1 Average Reward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
15.1.2 Differential Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
15.1.3 Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
15.2 CTMDP: Continuous-Time MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
15.3 Non-Homogenous MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
15.3.1 Representation of Non-Stationary States . . . . . . . . . . . . . . . . . 490
15.3.2 Bounded Time Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
15.3.3 Unbounded Time Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
15.4 SMDP: Semi-MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
15.4.1 SMDP and its Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
15.4.2 Find Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
15.4.3 HRL: Hierarchical Reinforcement Learning . . . . . . . . . . . . . . 498
15.5 POMDP: Partially Observable Markov Decision Process . . . . . . . . . . 499
15.5.1 DTPOMDP: Discrete-Time POMDP . . . . . . . . . . . . . . . . . . . . 499
15.5.2 Belief . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
15.5.3 Belief MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
15.5.4 Belief Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
15.5.5 Belief Values for Finite POMDP . . . . . . . . . . . . . . . . . . . . . . . 511
15.5.6 Use Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
15.6 Case Study: Tiger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
15.6.1 Compare Discounted Return Expectation and Average
Reward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
15.6.2 Belief MDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
15.6.3 Non-Stationary Belief State Values . . . . . . . . . . . . . . . . . . . . . 518
15.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
15.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
15.8.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
15.8.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
15.8.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
16 Learn from Feedback and Imitation Learning . . . . . . . . . . . . . . . . . . . . . 525
16.1 Learn from Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
16.1.1 Reward Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526
16.1.2 PbRL: Preference-based RL . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
16.1.3 RLHF: Reinforcement Learning with Human Feedback . . . . 528
16.2 IL: Imitation Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
16.2.1 𝑓 -Divergences and their Properties . . . . . . . . . . . . . . . . . . . . . 532
16.2.2 BC: Behavior Cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
16.2.3 GAIL: Generative Adversarial Imitation Learning . . . . . . . . . 541
16.3 Application In Training GPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
16.4 Case Study: Humanoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
16.4.1 Use PyBullet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
16.4.2 Use BC to IL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
16.4.3 Use GAIL to IL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
16.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
16.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
16.6.1 Multiple Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
16.6.2 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
16.6.3 Mock Interview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559

 Reinforcement Learning: Theory and Python Implementation is a tutorial book on reinforcement learning, with explanations of both theory and applications. Starting from a uniform mathematical framework, this book derives the theory of modern reinforcement learning systematically and introduces all mainstream reinforcement learning algorithms such as PPO, SAC, and MuZero. It also covers key technologies of GPT training such as RLHF, IRL, and PbRL. Every chapter is accompanied by high-quality implementations, and all implementations of deep reinforcement learning algorithms are with both TensorFlow and PyTorch. Codes can be found on GitHub along with their results and are runnable on a conventional laptop with either Windows, macOS, or Linux.

 This book is intended for readers who want to learn reinforcement learning systematically and apply reinforcement learning to practical applications. It is also ideal to academical researchers who seek theoretical foundation or algorithm enhancement in their cutting-edge AI research.