Model-Free Reinforcement Learning

Reinforcement Learning (RL) is concerned with the problem of an agent trying to maximize a scalar reward signal through interaction within its environment [1]. During the process no supervision is being provided i.e., the agent is never directly informed about the best action at a given moment in time. Based on advances in Deep Learning, the field has celebrated success in complex tasks i.e., solving various video games [2] and board games like chess and go [3]. The Deep Q-Network used by [1] is considered a model-free RL algorithm i.e., no explicit function for modeling the dynamics of the system is being approximated. On the other hand, model-based methods learn a dynamics model of the environment from observed data. While these model-based methods are arguably considered to be more sample efficient, they suffer from model bias, i.e., they inherently assume that the learned dynamics model sufficiently accurately resembles the real environment [4]. Model bias is especially an issue when only a few samples and no informative prior knowledge about the task to be learned are available. Therefore, methods like [5] that use probabilistic function approximators like Gaussian Processes [6], which can incorporate uncertainty into model approximation, can cope with bias to allow for more robust long term planning. Alternatives to GP function approximators which incorporate uncertainty but scale better with the number of available data points are Bayesian Neural Networks [7]. Nonetheless, uncertainty estimation becomes difficult or even unfeasible under harder system dynamics like complex locomotion or grasping. For harder dynamics, model-free algorithms offer the alternative to directly and therefore only learning the quantity of interest i.e., (the parameters of) a policy for optimal behavior within the environment. A real-world sports analogy is baseball where the performance of a pitcher\footnote{In baseball, a pitcher is a person that tries to throw the ball to the catcher while retiring the batter who is placed in between.} is judged by the actual throw of the ball rather than his reasoning over the physical dynamics of the ball throw. The methods presented in the following are policy gradient methods [8,9], a subclass of model-free RL algorithms. Policy gradient methods rely upon gradient descent optimization of parametrized policies with respect to the expected return or long term cumulative reward. Mathematically formalized, the RL scenario is given as a Markov Decision Process $\mathcal{M}=(\mathcal{S},\mathcal{A},D,R)$ where $\mathcal{S}$ and $\mathcal{A}$ are the state and action spaces and $D:\mathcal{S}\times \mathcal{A}\to \mathcal{S}$ is the dynamics function of the system and $R:\mathcal{S}\times \mathcal{A}\to \mathbb{R}$ is the scalar reward signal, and the optimization problem which seeks to find the optimal policy ${\pi }_{\theta \theta }:\mathcal{S}\to \mathcal{A}$ is formalized as $$\begin{array}{}\text{(1)}& \theta \theta =\arg \underset{\theta \theta }{max}\mathbb{E}\left[\sum _{t=0}^{\mathrm{\infty }}{r}_t\right]\end{array}$$ where $r_t=R({\mathbf{s}}_t,{\mathbf{a}}_t={\pi }_{\theta \theta }({\mathbf{s}}_t))$ with $\mathbf{s}\in \mathcal{S}$ and $\mathbf{a}\in \mathcal{A}$ being the state and the agent’s action respectively. The policy gradient methods try to solve the problem formulated in Equation $\text{1}$ above through estimation of the gradient $g:={\mathrm{\nabla }}_{\theta \theta }\mathbb{E}\left[\sum _{t=0}^{\mathrm{\infty }}{r}_t\right]$. The policy gradient methods to be presented in this section can formally be generalized to a policy gradient $g$ that satisfies $$\begin{array}{}\text{(2)}& g=\mathbb{E}[\sum _{t=0}^{\mathrm{\infty }}{\varphi }_t{\mathrm{\nabla }}_{\theta \theta }\log {\pi }_{\theta \theta }({\mathbf{a}}_{\mathbf{t}}\mid {\mathbf{s}}_{\mathbf{t}}\mathbf{)}]\end{array}$$ where in abuse of notation ${\pi }_{\theta \theta }({\mathbf{a}}_t\mid {\mathbf{s}}_t)$ refers to the probability¹ of taking action ${\mathbf{a}}_{\mathbf{t}}$ from state ${\mathbf{s}}_{\mathbf{t}}$ during timestep $t\in \mathbb{N}$, and ${\varphi }_t$ can take on various forms e.g., ${\varphi }_t=\mathbb{E}\left[\sum _{t=0}^{\mathrm{\infty }}{r}_t\right]$ corresponds to vanilla policy gradients i.e., REINFORCE [8]. The vanilla policy gradient is arguably the simplest form of a policy gradient method and the main disadvantage of the algorithm stems from the variance during estimation. Therefore, subsequently developed methods based on the policy gradient theorem have introduced mathematical structures that can help in controlling this variance. In the following, arguably state-of-the-art policy gradient methods, which will be used for the systematic experimentation phase presented in the following chapter, are being introduced in more detail. Trust Region Policy Optimization [10] improves the training stability by restricting the possible change of the policy during update phase at each step. This optimization constraint is enforced by the introduction of a trust region constraint formalized using a Kullback-Leibler divergence between the previous policy and the new candidate policy. I.e., Equation $\text{1}$ is adapted and extended to $$\begin{array}{}\text{(3)}& \theta \theta =\arg \underset{\theta \theta }{max}{J}_{\theta {\theta }_{old}}(\theta \theta )\text{subject to}{D}_{\text{KL}}(\theta {\theta }_{old},\theta \theta )\le \delta \end{array}$$ where $\delta \in \mathbb{R}$ and $J:=\mathbb{E}[{\psi }_t(\theta \theta )A_t]$ where $A_t$ is an advantage function² estimate and $$\begin{array}{}\text{(4)}& {\psi }_t(\theta \theta )=\frac{{\pi }_{\theta \theta }({\mathbf{a}}_t\mid {\mathbf{s}}_t)}{{\pi }_{\theta {\theta }_{old}}({\mathbf{a}}_t\mid {\mathbf{s}}_t)}\end{array}$$ being a weight ratio for an action ${\mathbf{a}}_{\mathbf{t}}$ under the two considered policies, and thus $J$ represents the (surrogate) objective function (e.g. as previously the expected return solely). The authors further generally prove the monotonic improvement for an algorithm that repeatedly optimizes a local approximation to the expected return of the policy with a KL divergence penalty, and that their methodic approximation to this principle through incorporation of a KL divergence constraint achieves good empirical results. Proximal Policy Optimization [11] simplifies the notion introduced by TRPO by simply reformulating the objective to control the range of values the function $\psi$ can take on i.e., $$\begin{array}{}\text{(5)}& J(\theta \theta )=\mathbb{E}[\text{min}({\psi }_t(\theta \theta )A_t,c_{ϵ}({\psi }_t(\theta \theta )))]\end{array}$$ where $c_{ϵ}:\mathbb{R}\to [1-ϵ,1+ϵ]$ is a clipping function with $ϵ\in \mathbb{R}$. Empirically PPO is arguably more sample efficient than TRPO, while also being a method of greater simplicity. TRPO and PPO belong to the same family of policy gradient algorithms and both implement stochastic policies i.e., the policy is a function which outputs the specification $\mu \mu$ and $\mathrm{\Sigma }\mathrm{\Sigma }$ of a Gaussian distribution (i.e., $\mathbf{a}\sim \mathcal{N}\mathbf{(}\mu \mu \mathbf{,}\mathbf{\Sigma }\mathbf{\Sigma }\mathbf{)}$). Thus, actions are being sampled from that distribution at runtime (or alternatively the mean of the distribution is simply being considered). Another family of policy gradient methods makes use of deterministic policies [12]. Deterministic policies can be seen as a special case of the more general stochastic setting. Stochasticity is useful or even crucial to exploration during training. Therefore, deterministic policies need additional investment to compensate for adequate exploration. However, their simpler form allows for higher computational efficiency. The Deep Deterministic Policy Gradient [13] method belongs to this family of algorithms. The algorithm combines concepts from deterministic policy gradients with DQN [2] which helps in stabilizing training through target network updates and experience replay. Intuitively, the mechanism of experience replay corresponds to a task memory or history of the agent’s actions from which it samples during learning. Improving the experience replay procedure i.e., changing the way information is being stored and accessed, can significantly change the task performance of the agent, as has been shown by [14]. Another method belonging to the family of deterministic policy gradients which tries to improve upon concepts from DDPG is Twin Delayed DDPG [15]. The authors argue that the overestimation of the value function, which guides the learning of optimal policies, leads to sub-optimal policies. Given that they further conclude that this issue is identifiable within training procedures, they introduce improvements via clipping of target values, less frequent updates of the policy compared to the value function and smoothing or regularization of the target policy. Another actor-critic method Soft Actor Critic [16] alters the original objective by introducing a maximum entropy regularization. I.e., the Equation $\text{5}$ would be changed to $$\begin{array}{}\text{(6)}& J(\theta \theta )=\mathbb{E}[r_t+\alpha H({\pi }_{\theta \theta }(\cdot \mid s{s}_t)]\end{array}$$ where $H$ is the entropy measure with free parameter $\alpha$ often referred to as temperature. The introduction of the entropy term leads to higher exploration. SAC is an off-policy algorithm like DDPG or TD3 i.e., it does not estimate the value function using actions generated from the current but a separate policy, but uses stochastic policies like the on-policy methods TRPO and PPO. The six algorithms presented in this section have been widely applied and benchmarked to various RL tasks [17], including robotics [18]. Open-source implementations of these methods exist and are being provided by the Python libraries ChainerRL [19] and garage [20] (which is the successor to the rllab framework). As has been observed, the mentioned state of the art arguably differs only partially to any other competitive method belonging to the same algorithmic class i.e., the methodological variance within the family of policy gradient methods is arguably low. Therefore, a method can benefit from a combination of additional techniques that have been empirically shown to be supportive of learning (e.g. entropy regularization) or improve computational efficiency (e.g. clipping). The work in [21] performs an ablation study on various factors that improve upon baseline versions of the policy gradient class of model-free algorithms.

References

• R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT press, 2018.
• V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.
• D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al., “A general reinforcement learning algorithm that masters chess, shogi, and go through self-play,” Science, vol. 362, no. 6419, pp. 1140–1144, 2018.
• J. G. Schneider, “Exploiting model uncertainty estimates for safe dynamic control learning,” in Advances in neural information processing systems, pp. 1047–1053, 1997.
• M. Deisenroth and C. E. Rasmussen, “Pilco: A model-based and data-efficient approach to policy search,” in Proceedings of the 28th International Conference on machine learning (ICML-11), pp. 465–472, 2011.
• C. E. Rasmussen, “Gaussian processes in machine learning,” in Summer School on Machine Learning, pp. 63–71, Springer, 2003.
• C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra, “Weight uncertainty in neural networks,” arXiv preprint arXiv:1505.05424, 2015.
• R. J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning,” Machine learning, vol. 8, no. 3-4, pp. 229–256, 1992.
• J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, “High-dimensional continuous control using generalized advantage estimation,” arXiv preprint arXiv:1506.02438, 2015.
• J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, “Trust region policy optimization,” in International conference on machine learning, pp. 1889–1897, 2015.
• J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv preprint arXiv:1707.06347, 2017.
• D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller, “Deterministic policy gradient algorithms,” 2014.
• T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” arXiv preprint arXiv:1509.02971, 2015.
• M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, O. P. Abbeel, and W. Zaremba, “Hindsight experience replay,” in Advances in neural information processing systems, pp. 5048–5058, 2017.
• S. Fujimoto, H. Van Hoof, and D. Meger, “Addressing function approximation error in actor-critic methods,” arXiv preprint arXiv:1802.09477, 2018.
• T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine, “Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor,” arXiv preprint arXiv:1801.01290, 2018.
• Y. Duan, X. Chen, R. Houthooft, J. Schulman, and P. Abbeel, “Benchmarking deep reinforcement learning for continuous control,” in International Conference on Machine Learning, pp. 1329–1338, 2016.
• J. Hwangbo, J. Lee, A. Dosovitskiy, D. Bellicoso, V. Tsounis, V. Koltun, and M. Hutter, “Learning agile and dynamic motor skills for legged robots,” Science Robotics, vol. 4, no. 26, p. eaau5872, 2019.
• Y. Fujita, T. Kataoka, P. Nagarajan, and T. Ishikawa, “Chainerrl: A deep reinforcement learning library,” arXiv preprint arXiv:1912.03905, 2019.
• T. garage contributors, “Garage: A toolkit for reproducible reinforcement learning research.” , 2019.
• M. Hessel, J. Modayil, H. Van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver, “Rainbow: Combining improvements in deep reinforcement learning,” in Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

Footnotes