4 Policy Gradient Methods 33
4.1 The Policy Gradient Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.1 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 The Softmax Policy and Relative Entropy Regularization . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3 The Natural Policy Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.1 Global Convergence and the Softmax Policy Class . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.2 Function Approximation and a Connection to Transfer Learning . . . . . . . . . . . . . . . . 46
4.4 Related algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4.1 Trust Region Policy Optimization (TRPO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4.2 Proximal Policy Optimization (PPO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4.3 Conservative Policy Iteration (CPI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5 Bibliographic Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5 Value Function Approximation 53
5.1 Approximate Policy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2 Approximate Policy Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2.1 Greedy policy improvement with `
∞
approximation . . . . . . . . . . . . . . . . . . . . . . 59
5.2.2 Conservative Policy Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6 Strategic Exploration in RL with rich observations 65
6.1 Problem setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2 Value-function approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Bellman Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.4 Sample-efficient learning for CDPs with a small Bellman rank . . . . . . . . . . . . . . . . . . . . . 70
7 Behavioral Cloning and Apprenticeship Learning 73
7.1 Linear Programming Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.1.1 The Primal LP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.1.2 The Dual LP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.2 Behavioral Cloning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2.1 Behavioral Cloning via Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 76
7.2.2 Behavioral Cloning via Distribution Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.2.3 Sample Efficiency: comparing the approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4
