Learning recursive goal proposal: a hierarchical reinforcement learning approach

Final Master’s Degree Thesis Learning Recursive Goal Proposal A Hierarchical Reinforcement Learning approach Master’s Degree in Artificial Intelligence Author: Rafel Palliser Sans Supervisor: Mario Martin Mu˜ noz April 2021 Rafel Palliser Sans: Learning Recursive Goal Proposal. A Hierarchical Reinforcement Learning approach ©, April 2021. A Final Master’s Degree Thesis submitted to the Facultat d’Inform`atica de Barcelona (FIB) - Universitat Polit`ecnica de Catalunya (UPC) - Barcelona Tech, Facultat de Matem`atiques de Barcelona - Universitat de Barcelona (UB) and Escola T`ecnica Superior d’Enginyeria - Universitat Rovira Virgili (URV) in partial fulfillment of the requirements for the Master’s Degree in Artificial Intelligence. Thesis produced at the Facultat d’Inform`atica de Barcelona under the supervision of Prof. Mario Martin. Author: Rafel Palliser Sans Supervisor: Mario Martin Mu˜noz Location: Menorca, Spain What we want is a machine that can learn from experience. — Alan Turing 4 Abstract Reinforcement Learning’s unique way of learning has led to remarkable successes like Alpha Zero [29] or Alpha Go [28], mastering the games of Chess and Go, and being able to beat the respective World Champions. Notwithstanding, Reinforcement Learning algorithms are underused in real-world applications compared to other techniques such as Supervised or Unsupervised learning. One of the most significant problems that could limit the applicability of Reinforcement Learning in other areas is its sample inefficiency, i.e., its need for vast amounts of interactions to obtain good behaviors. Off-policy algorithms, those that can learn a different policy than the one they use for exploration, take advantage of Replay Buffers to store the gathered knowledge and reuse it, already making a step into sample efficiency. However, in complex tasks, they still need lots of interactions with the environment to explore and learn good policies. This master thesis presents Learning Recursive Goal Proposal (LRGP), a new hierarchical algorithm based on two levels in which the higher one serves as a goal proposal for the lower one, which interacts with the environment following the proposed goals. The main idea of this novel method is to break a task into two parts, speeding and easing the learning process. In addition to this, LRGP implements a new reward system that takes advantage of non-sparse rewards to increase its sample efficiency by generating more transitions per episode, which are stored and reused thanks to Experience Replay. LRGP, which has the flexibility to be used with a wide variety of Reinforcement Learning algorithms in environments of different nature, obtains State-of-the- Art results both in performance and efficiency when compared to methods such as Double DQN [14] or Soft Actor Critic (SAC) [12,13] in Simple MiniGrid and Pendulum environments. KeyWords: Reinforcement Learning · Hierarchical RL · Sample Efficiency · Recursivity · Subgoal Proposal · Actor Critic · LRGP · DDQN · HER · SAC · UMDP · UVFA · AI. 5 6 Acknowledgments First of all, I would like to show my greatest gratitude to my thesis supervisor Professor Mario Martin. The interest and enthusiasm he demonstrated for the project were crucial for developing this new algorithm. Thanks for our uncountable meetings and endless fruitful discussion that made our first idea see the light in this project. Moreover, I also need to thank the Barcelona Supercomputing Center (BSC) for providing me with the necessary computational resources for the project presented in this thesis. I also wish to thank my MAI friends, who, aside from exchanging ideas for our research, have motivated and supported me during this project and the whole master’s. Finally, I would like to thank my family and friends here in Menorca for being my main support and providing laughs and distraction when needed during all these last months. 7 8 Contents 1 Introduction 13 1.1 Motivation ....................................... 13 1.2 Contribution ...................................... 14 1.3 Overview ........................................ 14 2 Reinforcement Learning 15 2.1 ReinforcementLearning ................................ 15 2.2 Model-free Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 Value-based algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Policy gradient algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.3 Actor Critic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Universal Markov Decision Processes (UMDP) . . . . . . . . . . . . . . . . . . . 26 2.3.1 Universal Value Function Approximators (UVFA) . . . . . . . . . . . . . 27 2.3.2 Hindsight Experience Replay (HER) . . . . . . . . . . . . . . . . . . . . . 27 3 Meta Reinforcement Learning and Multi-Task Learning 31 3.1 Theconcept....................................... 31 3.2 RelatedWork...................................... 32 4 Learning Recursive Goal Proposal 35 4.1 Ideaandmotivation .................................. 35 4.2 AlgorithmOverview .................................. 35 4.3 Maincomponents.................................... 36 4.3.1 Thelowhierarchy ............................... 36 4.3.2 Thehighhierarchy............................... 37 4.3.3 Is reachable function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.4 Incomplete goal spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 Experiments and Results 45 5.1 Environments...................................... 45 5.1.1 SimpleMiniGrid ................................ 45 5.1.2 Pendulum.................................... 47 5.2 Preliminarystudies................................... 48 5.3 MainResults ...................................... 54 6 Conclusions 59 Bibliography 61 Appendix A Implementation Details 65 9 16 CHAPTER 2. REINFORCEMENT LEARNING Formal Definition More formally, the RL problem can be formulated as a Markov Decision Process (MDP), this is, a tuple <S,A,R,P>, in which: •Sdenotes a finite set of states •Aa finite set of actions •R(s,a,s0) = E[rt+1|st=s, at=a, st+1 =s0] is a reward function •P(s,a,s0) = Pr{st+1 = s0|st = s, at = a} is a transition probability function in which the Markovian Property holds, this is, the probability of a next state st+1 = s0 only depends on the actual state st=sbut not older ones. With this formulation, we can now define a policy π : S −→ A as a mapping from states to actions, and the goal becomes choosing that actions that obtain the maximum long-term reward, defined as the sum of immediate rewards. From a certain time-step t , the long-term reward Rt would be defined as Rt=rt+1 +rt+2 +rt+3 +. . . =X k=0 rt+1+k(2.1) Note that if long-term reward does not have a horizon, this sum is unbounded. For this reason, a discount factor γ∈[0,1] is often introduced for future rewards. Rt=rt+1 +γrt+2 +γ2rt+3 +. . . =X k=0 γkrt+k+1 (2.2) In this project we will use finite horizons H , so there is no need in introducing a discount. Our long-term reward will be calculated as Rt=rt+1 +rt+2 +rt+3 +. . . = H X k=0 rt+1+k(2.3) Value Functions Value functions are introduced to evaluate states’ goodness by estimating the long-term reward that an agent would receive from a specific state if following a particular policy. Concretely, the state-value function (also called V-Value Function) Vπ ( s ) from state s following policy πis defined as Vπ(s) = Eπ[Rt|st=s] = Eπ"X k=0 γkrt+k+1 st=s#(2.4) Besides, the action-value function (also called Q-Value Function) estimates the long-term reward from a state staking action aand then following the policy π, and is defined as Qπ(s, a) = Eπ[Rt|st=s, at=a] = Eπ"X k=0 γkrt+k+1 st=s, at=a#(2.5) 2.1. REINFORCEMENT LEARNING 17 Bellman Equations The Bellman’s equation for the V-Value Function can be easily obtained by decomposing Equation 2.4 and regrouping as seen in Equation 2.6. It can be seen that the V-Value of a certain state is formed by two parts: the immediate reward rt+1 , and the discounted value for the next state, obtained following the policy π . Additionally, we can recursively decompose any V-Value into further time-steps, which will be crucial to learn optimal policies. Vπ(s) = Eπ[Rt|st=s] =Eπ[rt+1 +γrt+2 +γ2rt+3 +. . . |st=s] =Eπ[rt+1 +γ(rt+2 +γrt+3 +. . .)|st=s] =Eπ[rt+1 +γRt+1|st=s] =Eπ[rt+1 +γV π(St+1)|st=s] (2.6) Similarly, one can obtain the Bellman’s equation for the Q-Value Function as Qπ(s, a) = Eπ[Rt|st=s, at=a] =Eπ[rt+1 +γrt+2 +γ2rt+3 +. . . |st=s, at=a] =Eπ[rt+1 +γ(rt+2 +γrt+3 +. . .)|st=s, at=a] =Eπ[rt+1 +γRt+1|st=s, at=a] =Eπ[rt+1 +γV π(St+1)|st=s, at=a] (2.7) Note that the immediate reward rt+1 is affected by the taken action at = a , but the rest depends on the policy π , which is the reason why we can convert the second part of the equation into a V-Value. Also, taking into account that the difference between a V-Value and a Q-Value stands only on the first action, if that action is in fact the one followed by the policy, both value functions match: Qπ ( s, π ( s )) = Vπ ( s ). Therefore, we can rewrite Equation 2.7 as follows, making it recursive too. Qπ(s, a) = Eπ[rt+1 +γQπ(St+1, π(St+1))|st=s, at=a] (2.8) Optimal policies An optimal policy π∗ is a policy that, when followed, obtains a better value for each possible state of the environment than the value that could have been obtained with any other policy. Formally, Vπ∗(s)≥Vπ(s)∀s∈ S (2.9) From another point of view, an optimal policy must be capable of selecting the best action to take from any state to maximize the long-term reward. Otherwise, another policy could exist that took a better action in the mentioned state while behaving identically in the others, being more optimal. π∗(s) = arg max a∈A Eπ∗[Rt+1] = arg max a∈A Qπ∗(s, a)∀s∈ S (2.10) This idea of idea of improving a policy by taking a better action in a certain state is often called “greedification” , and it’s the idea of the most basic algorithms to find optimal policies: Policy Iteration (PI) and Value Iteration (VI) . The former iteratively evaluates a policy by computing the value of all states to then update the policy by making it greedy. The latter, instead, directly uses the Bellman equations to update the values to obtain a greedy policy once the values have converged. Both these algorithms are proved to converge at the optimal policy. However, these only work under critical assumptions that come from the fact that they are defined beneath a Markov Decision Process (MDP). As explained, an MDP is constituted from a 4-tuple, which includes a 18 CHAPTER 2. REINFORCEMENT LEARNING state space, an action space, the reward function, and the transition function between states. Therefore, to apply these algorithms one must know the complete dynamics of the environment as well as the rewards for each state and action beforehand. This type of Reinforcement Learning is called Model-based RL , and needs a model of the environment (its dynamics) in order to then learn value functions or optimal policies. On the other side, Model-free RL are another group of algorithms in which the agent explores to gather information at the same time that improves its policy. This project is based in Model-free algorithms. 2.2 Model-free Reinforcement Learning The family of Model-free RL algorithms is at the same time divided in several groups of algorithms, which will be explained during this section as Learning Recursive Goal Proposal uses several of them. 2.2.1 Value-based algorithms This sub-family of methods relies on the computation of value functions as an estimation of long-term rewards. If we had a model of the world, an MDP, we could calculate the V-Values or Q-Values using the reward function and the transition probability function by computing the expected long-term reward as in Equation 2.4 or Equation 2.5. However, as this information is not available in Model-free RL, these estimations are computed through an average of the empiric long-term reward received from each state. In Model-free RL the agent interacts with the environment generating episodes or trials τ = ( s0, a0, s1, r1, a1, s2, r2, . . . ) following its current policy. From any time-step we can calculate the empiric long-term reward Rt as in Equations 2.1 to 2.3. Finally, we can average all long-term rewards obtained from a certain state sand taking action ato estimate Q(s, a). Monte Carlo policy learning, one of the most-known Model-free Value-based algorithms takes this idea but applies a clever approximation of the averaging part that does not need to store millions of trials before being able to compute an average, at the same time that permits updating the policy to gather new information. To do so, they initialize the values of Q ( s, a ) randomly, and anytime the agent visits state s and takes action a applies the following updating rule: Q(s, a)←− Q(s, a) + α(Rt(s)−Q(s, a)) (2.11) Note that instead of having to store all empirical Rt , they only need an entry for each Q ( s, a ), which is softly updated depending on the parameter α . When doing this iteratively, Q ( s, a ) will converge to approximating Rt. Q-learning , another well-known method uses the same idea but substitutes Rt using the Bellman’s equation Q(s, a)←− Q(s, a) + α[rt+1 +γQ(s0, π(s0)) −Q(s, a)] Q(s, a)←− (1 −α)·Q(s, a) + α[rt+1 +γQ(s0, π(s0))] (2.12) Q-learning is also known a Temporal Differences (TD) , as uses the Q-Values of the next state to update the current one. This process of using value estimates for learning other value estimates is called bootstrapping. The differences between Monte Carlo and Q-learning are the fact that the former uses long-term reward while the latter uses immediate rewards and bootstrapping, which permits it to update the Q-Values each step and not each trial (MC needs to end the trial to compute Rt ). 2.2. MODEL-FREE REINFORCEMENT LEARNING 19 Note, nevertheless, that these algorithms have a problem. As we mentioned in the previous section in Equation 2.10, the optimal policy takes the greedy action, the one with highest Q-Value. Therefore, it could happen that after few iterations the agent took always the same actions, looking for the largest reward preventing it to explore possibly even better behaviors. For this reason, whenever generating new trials the agent uses an exploratory policy. One of the most used methods to solve this Exploitation vs Exploration problem is the -greedy exploration policy, which takes a random action with probability , and the optimal one otherwise. At this point it’s worth mentioning that Model-free methods can also be classified in two families: On-policy algorithms and Off-policy ones. The former optimize the policy they are using to generate the trials while the latter ones are able to learn a different policy that the one used to explore. Monte Carlo is an on-policy method because all the information used to update the Q-Values, Rt , is obtained empirically. Therefore, the policy gets updated with information gathered with the same policy. On the other hand, Q-learning is an off-policy method because it gathers information using an exploratory policy like  -greedy, but in the updating rule seen in Equation 2.12 also uses information about policy π which is purely greedy and different from the one used to explore. Although on-policy methods tend to be more stable and converge faster, off-policy algorithms can take advantage of learning a different policy than the one used to explore, as we will see following. Deep Q-learning All the methods presented up to this point have some significant drawbacks. On the one hand, they work in a tabular manner, only applicable for discrete state and action spaces. This problem could be solved by discretizing continuous environments, but there is a more critical shortcoming: the curse of dimensionality. The number of combinations of states and actions grows exponentially with their spaces’ dimensionality. Therefore, it can be drastic to store huge Q-Value tables for each state and action. Nonetheless, it can even be worse to obtain a reasonably good estimate for each of them, which implies visiting each state and taking each action from it several times. For this reason, the use of function approximators is crucial, methods that can approximate a full Q-table in limited amount of parameters, independently of the dimensionality of state and action spaces, apart from having the ability to generalize to unseen states. In order to update the parameters, gradient descent is used alongside with an error function that compares the estimation with the “true” value in a supervised way. As there is no known true value, bootstrapping is often used. However, the use of gradient descent in the online incremental learning scheme (where we generate trials in an online basis) comes with convergence problems due to data not being i.i.d., as there is high correlation among consecutive states. In addition to this, it would be inefficient to compute the gradient for each data point. To solve this, gradient batch methods are introduced. Gradient batch methods take advantage of off-policy algorithms to learn using data from another policy, and instead of training their function approximators on online data (just gathered from experience), it creates a dataset D of past experiences coded as tuples ( s, a, r, s0 ). Using this idea, they can decouple the exploration step, in which the dataset is being filled from the learning stage, also called Experience Replay , in which batches of transitions are sampled from D . Using batches breaks the i.i.d. problem, as transitions in a batch are selected randomly, and equally important, it brings the possibility of using Stochastic Gradient Descent. 20 CHAPTER 2. REINFORCEMENT LEARNING Moreover, the use of a dataset provides the option to reuse data, thus being much more sample efficient. The first method to appear and one of the most known is Deep Q-Network (DQN) [20], presented in 2015 by Mnih et al. Their algorithm was one of the first in using Neural Networks (NN) as function approximators for Q-Values, introducing Deep Learning in the field of Reinforcement Learning, a combination known as Deep Reinforcement Learning (DRL) . Additionally, DQN uses the Bellman’s equation and takes advantage of batch computing and off-policy algorithms. More specifically, the mentioned algorithm uses a NN with parameters θ to approximate Qθ ( s, a ), and for each batch of samples ( s, a, r, s0 ), computes the “true” value Q ( s, a ) by bootstrapping: Q(s, a) = r+γmax a0Qθ0(s0, a0) (2.13) Note that according to the Bellman’s equation (see Equation 2.8), we should select an action a0 = π ( s0 ). Taking into account that this is a Value-based method whose goal is to estimate the Q-Values, the policy is then obtained by “greedification” over these estimations. Therefore, following the idea in Equation 2.10, the “true” value is computed with the action the optimal policy would select, the greedy one. Also note that if the “true” value was calculated with the same parameters θ that are being update each iteration, DQN would suffer from a problem called moving target , in which the value that we are trying to estimate, the “true” one, changes over time. To solve this, Mnih et al. use the trick of using a target network, another NN parametrized with θ0 , which is updated at a much lower pace, helping in the convergence of the algorithm. Once we have calculated this “true” or target value, we can compute the loss, also called TD error , by comparing it with the current estimate. Afterwards, the gradient of this loss w.r.t the parameters θcan be computed to update them using SGD. TD −error = Qθ(s, a)−Q(s, a) = Qθ(s, a)−[r+γmax a0Qθ0(s0, a0)] (2.14) This updating rule, however, had an inconvenience. When using a random initialization of Q, we can be overestimating the real Q-Values by iteratively applying r + γmaxa0Qθ0 ( s0, a0 ) on the same network, propagating this overestimation to other states and making the problem even worse. Hasselt et al. recognized this problem and presented Double Q-learning [14], also called Double DQN (DDQN). In this algorithm, they introduced the idea of having a set of two different networks A and B to estimate Q ( s, a ). Using one to estimate the values of the other should compensate mistakes as networks would be independent. Nonetheless, taking into account that DQN already used two networks (the value network to estimate and the target network to compute the target values), they proposed the idea of using the former to select the best action and the latter to evaluate it calculating the “true” or target value as Q(s, a) = r+γQθ0s0,arg max a0 Qθ(s0, a0)(2.15) Note that a0 is selected using Qθ , the value network, but the estimation of Q ( s0, a0 ) is taken from Qθ0 , the target network. As the target network is updated asynchronously, both networks will have different values and overestimates will mutually mitigate each other. The complete DDQN method is shown in Algorithm 2.1. 2.2. MODEL-FREE REINFORCEMENT LEARNING 21 Apart from DDQN, the literature contains various publications that make incremental contributions to DQN improving its performance. Prioritized Experience Replay [26], presented by Schaul et al., implements a method to sample transitions from the buffer more cleverly. Dueling Network Architectures [31], published by Wang et al., include new NNs to the algorithm to compute a new value function called Advantage that improves convergence. Finally, Hessel et al. presented Rainbow [15], which merged all these ideas into the same algorithm to obtain State-of-the-Art results, back in 2017. Algorithm 2.1 DDQN [14] 1: Initialize weights θfor the value network 2: Initialize target network as θ0←θ 3: Initialize a buffer D 4: s←initial state 5: repeat 6: Choose afrom susing an exploratory policy derived from Qθ 7: Execute action a, observe r, s0and add (s, a, r, s0) to dataset D 8: Sample a mini-batch Bfrom D 9: Update parameters θusing θ←θ−αPt∈B ∂ ∂θ Qθ(st, at)−rt+1 +γQθ0st+1,arg max a0 Qθ(st+1, a0) 10: if iteration mod Nthen 11: Update target network θ0←θ 12: end if 13: until max iterations 14: return πbased on greedy evaluation of Qθ 2.2.2 Policy gradient algorithms The idea of Policy gradient methods is to use a function approximator to directly learn a policy πθ with parameters θ without having to estimate value functions. The explanation behind this approach is that Value-based algorithms use greedy updates, and this can potentially make the learning process unstable due to large policy jumps (argmax is not smooth). Using a function approximation to directly estimate a policy with certain parameters makes it possible to compute gradient updates (which are soft and stable) directly on the policy. Moreover, as there is no need on estimating an explicit Q-Value for all states and actions, Policy gradient methods can be used in high dimensional spaces or even continuous action spaces, in which Value-based algorithms need a discretization step. To have a soft policy which can be differentiated, these algorithms use stochastic policies. Thus, π ( a|s ) is a conditional probability distribution over A , indicating the probability of taking each action a∈ A from state s. Two more steps are needed for these methods to work: a function that defines the goodness of a policy, and a way to compute its gradient. The first part is solved by defining some value functions. One option would be computing the value of the starting state of an episode, following the policy (see Equation 2.16). An alternative would be computing the average value over states as in Equation 2.17. Note that dπθ is a stationary distribution of Markov Chain for πθ , indicating the probability of being in each state if following the policy. Finally, a third way of measuring the quality of a policy could be computing an average over state values, but taking into account 22 CHAPTER 2. REINFORCEMENT LEARNING the immediate rewards that the agent receives in that state depending on the action it takes. This idea is presented in Equation 2.18, under the function JavR. J1(θ) = Vπθ(s1) (2.16) Jav(θ) = X s dπθ(s)Vπθ(s) (2.17) JavR(θ) = X s dπθ(s)X a πθ(a|s)r(s, a) (2.18) On the other side, Sutton and Barto in their Reinforcement Learning book [30], proved the Policy gradient theorem, presented in Equation 2.19, which shows how to compute the gradient of any of the defined objective functions J1, Jav, JavR. ∇θJ(θ) = Eπθ[∇θlog πθ(a|s)Qπθ(s, a)] (2.19) Knowing that Rt is an unbiased sample of the estimator Qπθ , REINFORCE—also called Monte Carlo Policy Gradient—uses the theorem to build an online Policy Gradient method, which is shown in Algorithm 2.2. Algorithm 2.2 REINFORCE 1: Initialize weights θfor the policy network 2: repeat 3: Generate episode τ= (s1, a1, r2, s2, a2, . . .) following πθ 4: for all tdo 5: Rt←long-term return from step t 6: Update parameters θ←θ+α∇θlog πθ(at|st)Rt 7: end for 8: until convergence 2.2.3 Actor Critic Methods Actor Critic Methods appear as an improvement over REINFORCE. Monte Carlo-based algorithms, the ones that use empirical long-term rewards Rt , tend to have high variance due to the implicit variance of Rt , which is the result of taking several actions in the environment. In order to reduce this variance, a baseline is added to Rt to obtain the value ( Rt−b ( st )). Choosing a clever estimation for the baseline such as b ( st ) = Vπθ ( st ) reduces the variance of the algorithm, making it more stable. However, a new set of parameters have to be introduced to estimate the V-Values. The resulting algorithm is called REINFORCE with Baseline or Monte Carlo Actor Critic. Actor Critic Methods (AC) are formed by an Actor , which selects actions and it is trained following the idea of Policy Gradient algorithms; and by a Critic , which estimates a Value function which originally was introduced as a baseline to reduce the variance. Therefore, AC algorithms merge the two worlds of Value-based and Policy Gradient methods. Similarly with Monte Carlo and Q-learning, there is a version of REINFORCE with Baseline that uses bootstrapping on the Bellman’s equation to train the critic. Additionally, the same TD error, which is a difference between two values makes the functions of the baseline and serves to train the policy using the Policy Gradient Theorem. Figure 2.2 shows the general structure of this method called One step AC (QAC). 2.2. MODEL-FREE REINFORCEMENT LEARNING 23 Actor (Policy) Critic (Value Function) Environment Reward r State s Action a TD error Figure 2.2: Actor Critic general architecture. DDPG In 2016, Lillicrap et al. presented Deep Deterministic Policy Gradient (DDPG) [17], a method that combines ideas both from DQN and One step Actor Critic (QAC). On the one hand, DDPG is an AC algorithm because it uses both policy gradient and value networks, which allows it to be use under continuous action spaces . On the other hand, as an off-policy method, it takes advantage from Experience Replay , being much more sample efficient . In addition to this, DDPG uses the Bellman’s equation and bootstrapping, which are common features among DQN and QAC. Moreover, DDPG comes with some novel features. Firstly, it uses deterministic policies as opposed to the already mentioned AC algorithms; and second, it proposes a new exploration method based in the addition of Gaussian noise to the action selected by the policy instead of using other techniques such as  -greedy exploration, which selects a completely random action with probability . Algorithm 2.3 shows the main pipeline of DDPG. Note in first place that it uses target networks both for the actor and the critic to improve convergence. Furthermore, line 8 shows the addition of Gaussian noise, with standard deviation σ , which is usually reduced during training, and set to 0 when testing. It should be also remarked that DDPG uses soft updates for its target networks. In this technique, instead of directly copying the parameters of the trained networks each N iterations, the target networks are updated every iteration using small steps (a common value is τ≈ 0 . 005). This usually improves stability compared to delayed hard updates. TD3 Two years later, in 2018, Twin Delayed DDPG (TD3) [10] was presented by Fujimoto et al. proposing four incremental contributions to DDPG. Firstly, the authors noted a small problem in the noise addition. Due to the Gaussian distribution, there is a low—but not zero—probability of sampling extreme values, which can imply large and unstable updates. For this reason, they clipped the noise before introducing it in the exploratory action improving stability. The second contribution was to also add noise when updating the critic, and not only when exploring. Therefore, when computing the target Q-Value (see line 11 in Algorithm 2.3), instead of selecting a0=πθ0 a(s0), they add Gaussian noise like in the exploratory action. 24 CHAPTER 2. REINFORCEMENT LEARNING Algorithm 2.3 DDPG [17] 1: Initialize weights θcfor the critic network Qθc(s, a) 2: Initialize weights θafor the actor network πθa(s) 3: Initialize target networks as θ0 c←θc, θ0 a←θa 4: Initialize a buffer D 5: s←initial state 6: repeat 7: Select action a=πθa(s) 8: Add noise a←a+N(0, σ) 9: Execute action a, observe r, s0and add (s, a, r, s0) to dataset D 10: Sample a mini-batch Bfrom D 11: Compute the target Q-Value using the Bellman’s equation and target networks: Q(s, a) = r+γQθ0 cs0, πθ0 a(s0) 12: Update critic using MSE Loss on the target Q-Values: θc←θc−αcPt∈B ∂ ∂θc(Qθc(st, at)−Q(st, at))2 13: Update actor using critic’s valuation of the actions it selects: θa←θa+αaPt∈B ∂ ∂θaQθc(st, πθa(st)) 14: Soft-update target networks: θ0 c←(1 −τ)θ0 c+τθc θ0 a←(1 −τ)θ0 a+τθa 15: until max iterations The third improvement is a reminiscence of DDQN. To fight against possible overestimation, TD3 introduces two sets of critics, and uses the most pessimistic one to build the target Q-Values from which to calculate the loss or error. Finally, the last contribution is to delay the updates of the actor several iterations. In other words, updating the critic more frequently than the policy network brings better convergence. All in all, TD3 is one of the State-of-the-Art Reinforcement Learning algorithms nowadays. SAC Also in 2018, Haarnoja et al. presented Soft Actor Critic (SAC) [12], which is an Actor Critic method that works with Entropy-regularized policies. The idea behind this project is that if a stochastic policy has maximum entropy, the probability of taking each action becomes closer, so it automatically explores. Therefore, when learning a maximum entropy policy, there is no need to add noise or other exploration techniques. The entropy of a stochastic policy can be defined as H(π(·|s)) = E a∼π(s)[−log π(a|s)] (2.20) And using this definition, now the goal is not to maximize the long-term reward, but to maximize a combination of the reward and the entropy of the policy using the following new value functions: Vπ(s) = E τ∼π(s)"X k=0 γk(rt+k+1 +αH(π(·|st+k))) st=s#(2.21) Qπ(s, a) = E τ∼π(s)"X k=0 γkrt+k+1 +αX k=1 γkH(π(·|st+k)) st=s, at=a#(2.22) 2.2. MODEL-FREE REINFORCEMENT LEARNING 25 Note that the entropy does not play in the first time-step for the Q-value, as the immediate reward is directly used. Also, the parameter α controls the trade-off between exploiting the rewards or providing more importance to the entropy, thus to exploration. This parameter is usually decreased during training, and set to 0 when testing. Nonetheless, in a newer work [13], Haarnoja et al. provide a method to automatically and dynamically tune this parameter during the training stage. With these entropy-aware definitions of the value functions, we can rewrite the Bellman equations as Vπ(s) = E τ∼π(s)[Qπ(s, a) + αH(π(·|s))] (2.23) Qπ(s, a) = E τ∼π(s)r+γQπ(s0, a0) + αH(π(·|s0))=E τ∼π(s)r+γV π(s0)(2.24) Taking into account that in both Bellman equations appear V-Values and Q-Values, SAC uses the following seven function approximators: •Twin Q-networks (like in TD3) with their respective target networks •A V-network and its target one •A policy network for the actor Both Q-networks are trained using the MSE loss against a target Q-Value calculated as in Equation 2.24, which is computed using the target V-network. On the other side, the V-network is also trained using an MSE loss against a target V-Value computed as in Equation 2.23, using the most pessimistic target Q-network. Finally, the objective function for the policy network is to maximize the V-value of taken states, this is max π E τ∼π(s)[Qπ(s, a)−αlog π(s, a)] (2.25) Following the same methodology used in the different networks, we would like to calculate the gradient of it to optimize using gradient ascent. However, this is not possible for this objective function as gradients cannot be computed for π when the expectation operator works for its own stochasticity. For this reason, and taking advantage of π being stochastic, the authors apply the Reparametrization trick . Firstly, they define the policy as Gaussian, so given a state s there is a Gaussian probability distribution over the action space A . From this point, instead of computing the outcome directly, they calculate the mean and standard deviation for such probability distribution. Using a new independent variable ξ , they can sample a value from the distribution in the following way: aθ=µθ+σθξ(2.26) being θ the parameters of the policy network, and ξ∼ N (0 , 1). Now note that, as the stochasticity has fallen into ξ ( µ and σ are two variables but do not “decide” on the action taken), the expectation depends on ξ , not on the parameters θ from which we need to compute the gradient. Alongside with TD3, SAC obtains State-of-the-Art results in almost all Reinforcement Learning tasks nowadays. 32 CHAPTER 3. META REINFORCEMENT LEARNING starts by presenting easy goals, and once the learner knows how to achieve them, it increases the difficulty until the agent can solve the whole task. Instead of leaving the agent to discover all the state space, the meta-learner guides it through the learning process. Curriculum Learning follows the idea of “Learning to Learn”, which is a colloquial definition for Meta-Learning. Third, Hierarchical methods tackle the same problem with a different philosophy. Opposite to Curriculum Learning techniques, which work at training time guiding the learning process, Hierarchical methods help the base agents accomplish each episode by guiding it through intermediate states (or goals) that are more easily achievable. These methods use “Divide and Conquer”’s idea by splitting the task’s complexity into several parts, each of them to be solved by a different agent more efficiently. Commonly, the low hierarchy, or base learner, has to learn the environment’s basic actions while trying to achieve the subgoals proposed by higher agents while these learn how to propose intermediate subgoals to make the whole process easier and faster. Finally, there is also a group of methods that focus on exploring the environment in an unsupervised way to be then able to solve any task using the gathered knowledge. 3.2 Related Work Gradient-based algorithms Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks (MAML) [7], presented by Finn et al. in 2017, is a generic Meta-Learning approach that works for any task and model that uses gradient descent as optimization technique. Its goal is to obtain a generic model that can directly solve a group of tasks or, at least, that can do it after a very short fine-tuning on each of them. To accomplish this, given a set of parameters θ for the learner (the policy in RL), MAML computes K updates for each task independently (from the same initial parameters θ ). Each of these updated models is then evaluated using test data belonging to the respective task, computing a loss or error. Finally, all per-task losses are combined, and a gradient step is made from the original parameters θ using this final loss. This methodology ensures that the gradient step goes in a direction where most tasks are improved, obtaining a general model able to solve several tasks. Moreover, this pipeline ensures that the parameters are set so that the model can be easily fine-tuned for each specific task with very few steps. Although it is quite an impressive theoretical idea and well funded mathematically, it is pretty inefficient in practice. On the one hand, the whole pipeline requires creating a copy of the model for each task, every iteration. On the other hand, it is a second-order method as it has to compute the gradients over already-computed per-task gradients, which is costly computationally. Additionally, the RL-adapted version (the original algorithm is generic, not RL based) uses the empirical long-term reward Rt as estimator, similar to Monte Carlo methods, thus being on-policy and sample-inefficient. Proximal Meta-Policy Search (ProMP) [24], published in 2018 by Rothfuss et al., and later, Curriculum in Gradient-Based Meta-Reinforcement Learning (Meta-ADR) [19] by Mehta et al. proposed some incremental contributions over MAML by improving its sample efficiency and its performance over unseen tasks, respectively. 3.2. RELATED WORK 33 Curriculum Learning With a completely different idea, Florensa et al. presented, in 2018, Automatic Goal Generation for Reinforcement Learning Agents (AGG) [8], a Curriculum Learning algorithm for RL tasks. In this work, they propose the concept “GOID: Goals of Intermediate Difficulty”, and define a goal g to have this property if it was achieved between a minimum and a maximum percentages in the previous iteration. Using this information, they train a Generative Adversarial Network (GAN) [11] to propose goals that are of intermediate difficulty with the current agent’s knowledge and ability. They show that using this technique, the agent is always “motivated” to learn because their goals are not too difficult, at the same time it is “challenged” as they are not too easy, being able to efficiently learn to solve any goal from a given initial state in an organized way. Note that this algorithm runs at training time, providing a way of learning the whole environment. However, for an specific task, not all possible goals are required to be learned. In this cases AGG can be too costly. All in all, it is a quite clever way of exploring and learning. Exploration-based algorithms Following with exploration approaches, Diversity Is All You Need (DIAYN) [5], presented in 2019 by Eysenbach et al., proposes an unsupervised methodology to explore all the space by learning skills, which can be interpreted—simplifying—as goal regions. Therefore, their purpose is to learn diverse and distinguishable skills that cover all the space. Their implementation is based on a discriminator that uses information theory to ensure that the learned skills are as different and variate as possible. After discovering skills in an environment during the pre-training stage, they apply fine-tuning to several downstream tasks. The method’s idea is to obtain a deep knowledge of the environment before learning any possible task with zero or few iterations. This is pretty useful when extreme multi-task knowledge is needed. However, exploring all the space can be hugely inefficient if valid states’ subspace is not the entire state space, or in cases where the task’s goal space is much lower than the space of states. A year later, Sekar et al. presented Planning to Explore via Self-Supervised World Models (Plan2Explore) [27], another exploration technique whose goal is to obtain a world model to later learn new tasks efficiently by zero-shot or few-show fine-tuning using Model-based sample-efficient algorithms on the model. Again, a rather interesting alternative if massive multi-tasking is required. Latent task representations Back to purely multi-task approaches, although not gradientbased, Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables (PEARL) [23] was published in 2019 by Rakelly et al. In their work, they propose an alternative to solve multi-task environments without the use of UMDPs and explicit definition of goals. Instead, for each episode, they gather information of the environment by collecting tuples ( s, a, r, s0 ), and use an Inference Neural Network to estimate a probabilistic latent representation zfor the task using that data. Afterwards, taking inspiration on goal-conditioned policies, they condition the policy on the obtained task latent representation z . They prove that this idea, which is directly designed for Reinforcement Learning outperforms methods such MAML [7] or ProMP [24] both in performance and sample efficiency, which is expected as PEARL is an off-policy method that uses Experience Replay. 34 CHAPTER 3. META REINFORCEMENT LEARNING Hierarchical methods On the hierarchical methods field, we find Learning Multi-Level Hierarchies with Hindsight (HAC) [16], which Levi et al. presented in 2017. HAC builds a structure of two or more hierarchies, where the lowest one interacts with the environment, and the rest work as goal proposers. More specifically, each hierarchy is an independent agent, with its own learning algorithm and UMDP. The highest level receives the environment goal and has to propose a subgoal for the immediately lower hierarchy. The last agent, the lowest one, is a base learner who interacts with the environment, but instead of following the environment’s goals, it receives proposals for the agent just on top of it, which are easier to achieve. With this idea, the base learner does not need to learn the whole space but only those goals proposed by the hierarchical parent. Similarly, the highest level does not need to know how to interact with the environment but to propose goals that ease the solve of tasks. To implement this concept, HAC uses DDPG [17], HER [1], and UVFA’s [25] “concatenate” strategy for each agent. Note that while the lowest hierarchy’s action space matches the environment’s one, the other levels have to propose goals, so their action space is actually the environment’s goal space. Following this structure, the highest level starts proposing a goal for the immediately lower one, which from the same state and new goal, proposes a new goal to the following one. The last agent, the base learner, has a limited horizon of time-steps to try to achieve the goal it has received, and after reaching the goal or the time horizon H , it sends its final state to the agent immediately on top which recognizes it as its own next state. After all agents have used their time horizons or the environment’s goal has been achieved, each agent updates its own policy using its replay buffer to learn better proposals or actions and eventually easing the learning process by dividing it into several smaller problems. HAC is an astonishingly interesting idea that can be applied as a complement of HER to make learning more efficient. However, the introduction of new agents make the algorithm more costly computationally. Finally, Meta Goal-generation for Hierarchical Reinforcement Learning (MGHRL) [9] presented by Fu et al. in 2020 combines a two-level hierarchy similar to the one in HAC [16] with latent representations of tasks like in PEARL [23] to build an algorithm that is both efficient at learning and flexible to adapt to new tasks, two of the main purposes of Meta Reinforcement Learning. 4. Learning Recursive Goal Proposal 4.1 Idea and motivation As exposed in Chapter 3, Reinforcement Learning has some weak points that make it less efficient, and therefore less usable in the real world. Taking this under consideration, this project’s intention has been to design a new algorithm that is evenly powerful to solve complex environments than efficient in all of its definitions. First, sample efficiency is vital in RL as it brings the ability to learn a task with fewer interactions with the environment. Another quality of an algorithm that can reduce the number of interactions is the ability to learn faster and easier, lowering the required training time and amount of iterations needed. Finally, the design of the algorithm itself also has an impact on the computational cost. With all these concepts in mind, our idea has been to build a two-level hierarchical method. The high level would work as a subgoal proposal , while the low one would only interact with the environments following easy goals proposed by the higher hierarchy. As explained in the past chapter, this allows the lower agent to learn faster by having a smaller search space, while the high hierarchy only needs to learn how to propose goals, not how to act in the environment. Opposite to HAC [16], which uses several goal-proposing agents to obtain better and more refined proposals with each of them, our design decision has been to encapsulate all these different policies into a single one. By using recursivity on the high level , we can ask for closer and more reachable goal proposals without having to use multiple agents, thus being more computationally efficient. This idea has been inspired by how shortest paths can be found after applying Dijkstra’s algorithm [4]. The algorithm—applied to a set of nodes in a graph—stores, for each target node, the node that should be visited just before it when traveling optimally from a source node. Therefore, if the source and target nodes are not directly connected, recursive calls have to be made to recover the shortest path. 4.2 Algorithm Overview Learning Recursive Goal Proposal is formed by a goal stack , an infinite loop and two differentiated parts, one for each hierarchy level. An overview of the method is shown in Algorithm 4.1. As it can be seen, each episode starts with an initial state and goal drawn from the environment. Additionally, a stack is used to store all goals and subgoals, which the low agent will have to achieve in last in first out strict order. The final objective is to empty the stack of goals, which would imply that the first inserted item, the episode’s goal, is accomplished. 35 36 CHAPTER 4. LEARNING RECURSIVE GOAL PROPOSAL Algorithm 4.1 LRGP Require: high agent, low agent, is reachable(s, g) function, low horizon Hl 1: s←initial state 2: g←episode goal 3: goal stack ←[g].Initialize stack with goal g 4: while True do 5: g←goal stack.top() 6: reachable ←is reachable(s, g) .Boolean 7: if not reachable then .High hierarchy section 8: g0←high.propose goal(s, g) 9: Add g0to goal stack 10: else .Low hierarchy section 11: for low step = 1:Hldo 12: a←low.select action(s, g) 13: Apply action aand observe next state s0 14: s←s0 15: if s0achieves gthen 16: Remove gfrom goal stack and break for loop 17: end if 18: end for 19: if goal stack.is empty() then 20: Episode is completed. Break. 21: end if 22: end if 23: end while After the initialization, the algorithm contains a loop in which the last goal introduced in the stack is selected. If that goal is not reachable by the low agent in Hl or fewer steps, the goal proposer—the higher hierarchy—is asked to generate a new goal taking into account the current state-goal pair. If otherwise the last goal introduced in the stack is reachable by the low agent within its step horizon Hl , a maximum of Hl steps are taken in the environment guided by the low level’s policy. If during these interactions the agent reaches the goal that it is pursuing, that goal is removed from the stack and the following one us used for the next iteration. Coming sections refer to how the two hierarchies are implemented, as well as the is reachable function, that estimates when a goal is reachable from a state in no more than Hlsteps. 4.3 Main components 4.3.1 The low hierarchy The low hierarchy can be seen as a UMDP (see Section 2.3) whose state space S , action space A , and transition probability function P are the environment’s original ones. The goal space G is also the environment’s one, with the main difference that goals do not come directly from it, but from the high hierarchy. Therefore, although the space G is identical, the low agent will receive fewer state and goal combinations, so the perceived space to explore becomes smaller. Regarding the reward function R , goal environments tend to use binary sparse rewards with a positive or negative value depending on whether the agent’s state has achieved the episode’s 4.3. MAIN COMPONENTS 37 goal. In our hierarchical algorithm, we overwrite the environment’s rewards for another sparse and binary reward function that acts on the goal that is currently pursued, the one on top of the goal stack (which in the general case is different from the episode’s goal, the one in the bottom of the stack). More specifically we use a value of − 1 if a goals is not achieved, and 0 otherwise. As long-term reward is upper-bounded at 0, there is no need on using a discounted version of the long-term return, therefore we use γ= 1. In order to be more sample efficient and learn faster under sparse rewards, we use HER [1] with “future” strategy, presented in Section 2.3.2 and Algorithm 2.4. Additionally, it’s worth mentioning that Learning Recursive Goal Proposal (LRGP) is defined for any type of environment , with no restriction on the nature of the state or action spaces. Moreover, it is also flexible to use any Value-based or Actor Critic algorithm as base learner. For our experiments we have tested DDQN [14] for discrete environments and DDPG [17], TD3 [10] and SAC [12,13] for continuous ones. 4.3.2 The high hierarchy The high hierarchy task can also be defined as a UMDP in which the state space S and the goal space G are the environment’s original ones. However, this time the action space A becomes the environment’s goal space, as the high agent will work as goal proposer . Therefore, its output, actions, become goals. Regarding the probability transition function P, it now depends on the low-level policy because it is the only agent able to change the state of the environment. In fact, the states perceived by the high hierarchy are only the first and last states of each run of maximum Hl steps by the lower one. In other words, how the lower agent has moved from one state to the other is a black box for the high level. Concerning the reward function, we have used a non-sparse definition that lets us be more sample efficient and speed up the learning process. Moreover, we have studied two different estimation techniques that will be explained following. Both methodologies can be implemented into any off-policy learning algorithm that uses Q-Values: either Value-based methods or Actor Critic learners. In this work, we have experimented with DDQN [14] to propose goals from a discrete space and DDPG [17], TD3 [10], and SAC [12,13] for continuous goal spaces. Furthermore, we have proved that the continuous methods also work for discrete goal spaces by first proposing a continuous goal and then discretizing it. This idea leads to an improvement on the generalization power and a more quickly convergence. Reward function The task of proposing subgoals to help the base learner reach a final goal g from a current state s can be seen as a planning algorithm in which the objective is to find a sequence of intermediate milestones that the base learner can easily achieve. In our context, a goal is easily achievable if it can be reached with no more than Hl environment steps, which we will call a run. Taking this idea into account, we define the short-term reward to be − 1 for each required goal proposal. Therefore, it is trivial to see that the long-term reward will be the negative of the number of subgoals that have been required to solve an episode. 38 CHAPTER 4. LEARNING RECURSIVE GOAL PROPOSAL From the definition of Q-Value functions in UMDPs (see Equation 2.29), the Q-Value for a state s , subgoal proposal a and goal g , Q ( s, a, g ), will be the negative of the expected number of subgoals required to reach g from s after having proposed a . Thus, the optimal policy will have to learn which subgoal proposal a to choose in order to minimize the expected number of proposals that will be required from sto g. Note that minimizing the number of subgoal proposals implies minimizing the number of low hierarchy runs, which at the same time implies minimizing the number of steps the agent performs in the environment (as each run is bounded by Hl ). If subgoal proposals are too close to the actual state, the episode will require more proposals, being suboptimal. On the other hand, if subgoal proposals are too far, the low agent will not be able to reach them in Hl steps, and an extra proposal will be required by the algorithm thus becoming suboptimal again. Therefore, this reward function definition ensures both a minimum use of the high hierarchy and solving the episodes as fast as possible. Similarly to the low agent’s reward, this long-term reward is also upper-bounded by 0. Therefore, we use γ= 1 for the higher hierarchy too. Long-term reward estimation To estimate the number of subgoal proposals or runs required from a state s to a goal g we propose two alternatives. The first one would be inspired on Bellman’s equation and the use of the short-term reward, while the second one is based on Monte Carlo ’s idea of using the long-term empirical reward as estimation. However, in both cases, we take advantage of the reward function’s definition to increase our sample efficiency by generating more transitions per episode. To illustrate how we generate these transitions we will make use of the diagram shown in Figure 4.1, which represents a sequence of 3 runs with their initial and final states A, B, C, D . Note that arrows represent runs ,i.e., sequences of at most Hl environment steps. Therefore, A−→ B could have two compositions: either Hl steps towards a goal that was not achieved by the low agent before reaching its horizon; or any number of steps ( ≤Hl ) towards B until achieving it. One or the other, it is a black box for the high hierarchy and only the initial and final states Aand Bare needed. To compute transitions, we use the idea of Hindsight Action Transitions (HAT) presented in HAC [1], in which transitions for the higher hierarchies are computed as if lower ones already had an optimal policy. This is key to stabilize the learning process of the high hierarchy because it depends on the low’s policy, which changes over time when learning simultaneously. We know that when the low agent acts optimally, it always achieves the last goal in the stack if reachable. Therefore, to mimic an optimal behavior we will force the final step of each run to accomplish the goal in the transition. Following HAT’s idea, we will use hindsight goals ,i.e., we will use the empirical final state of each run—mapped into the goal space G —instead of the goal that was truly proposed, independently of the accomplishment of it. Therefore, to create transitions we do not need the goals that were actually proposed, but the sequence of initial and final states for each episode run. Following with the example in Figure 4.1, both states and goals belong to R2 . As they have the same exact representation, the state-goal mapper becomes g = sgm ( s ) = s . For this reason, in this example, we will refer to nodes A, B, C, D as either states or goals. 4.3. MAIN COMPONENTS 39 A B C D Figure 4.1: Diagram to illustrate high hierarchy transition generation. Our Bellman’s based way of estimating the long-term reward makes use of the Bellman’s equation to generate transitions of the form: Q(s, a, g) = r+ max a0Q(s0, a0, g) (4.1) This should be read as “the cost of going from s to g through the intermediate milestone or subgoal a is: r , which encapsulates the cost of going from s to sgm( s0 ), plus the cost of going from s0 to g in the most optimal way”. Following this idea, we could generate the following transitions for the diagram: •Q ( A, B, B ) = − 1 + 0. The cost of going from A to B is − 1 (one run). The second part of the equation would be the cost of going from B to B which is obviously 0. •Similarly, Q(B, C, C) = −1 + 0, and Q(C, D, D) = −1 + 0. •Q ( A, B, C ) = − 1 + maxa0Q ( B, a0, C ). The cost of going from A to C proposing B is the cost of going from Ato B(−1) plus the best cost from Bto Cin the most efficient way. • Similarly, Q ( B, C, D ) = − 1+ maxa0Q ( C, a0, D ), and Q ( A, B, D ) = − 1+ maxa0Q ( B, a0, D ). • Finally, we can also skip time-steps by doing Q ( A, C, D ) = − 2 + maxa0Q ( C, a0, D ). In this case we are encapsulating the cost from A to C in the short-term reward, which now becomes −2 as two runs or proposals are needed to reach Cunder this trial A, B, C, D. Note that thanks to the definition of the reward function we are able to generate more transitions that the ones that would be created under sparse rewards. In this toy example the episode contains three runs, but instead, we generated 7 transitions or samples. Every one of these data points would be stored in the replay buffer in the form ( s, a, r, s0, g ) and then sampled applying Equation 4.1 to compute the target values for the learners as exposed in Chapter 2. Moreover, it can easily be seen that the number of computed transitions increases rapidly with the number of runs the episode contains, becoming even more sample efficient. On the other hand, we propose another technique inspired on Monte Carlo estimation . In this case, we use the observed long-term return R , which includes the number of proposals required from a certain state sto goal gusing the empirical trial. Using this idea, read as “from s to g through a , R proposals or runs were required”, we can generate the following transitions: •Q ( A, B, B ) = − 1. The cost of going from A to B through B is − 1. One proposal ( B ) or run was required. 40 CHAPTER 4. LEARNING RECURSIVE GOAL PROPOSAL •Similarly, Q(B, C, C) = −1, and Q(C, D, D) = −1 •Q ( A, B, C ) = − 2. The cost of going from A to C through B was − 2 as it required 2 runs. •Similarly, Q(B, C, D) = −2 • Following the same idea and extending the span of the transitions, Q ( A, B, D ) = − 3, and Q(A, C, D) = −3. Note that using these transitions we always use the observed information, what happened during the episode. Under this technique, we would store tuples like ( s, a, g, R ), and then we would ask the Q-Value network or critic to predict Q(s, a, g) = R. Comparison between our two approaches To better see which is the difference between our two methodologies we will focus on the estimation of Q(A, B, D). Additionally, we will use the concept of the triangular inequation . This inequation expresses that between three states B−C−D, the following relation holds: d(B, D)≤d(B, C) + d(C, D) (4.2) If we make a generalization into Q-Values, we obtain: max a0Q(B, a0, D)≥max a00 Q(B, a00, C) + max a000 Q(C, a000, D) (4.3) Note how the inequality sign changes sides because the original definition is in terms of distance (which usually has to be minimized), while Q-Values are to be maximized. In this case, the inequality expresses that when introducing intermediate milestones (e.g. C ), the Q-Value can not go any better. In our Bellman’s approach we use Q ( A, B, D ) = − 1 + maxa0Q ( B, a0, D ), therefore we are using an optimistic view of the triangular inequation, as we are using the minimum cost from Bto D, using the left side of the Q-Value inequation (see Equation 4.3). On the other side, when using Monte Carlo’s approach we obtain Q ( A, B, D ) = − 3, which implies a cost from B to D of exactly − 2. We call this an empirical view of the triangular inequation as opposed to our first method, as it does not uses the best case but the observed one. Special Cases In order to improve the stability, robustness and convergence of our learning stage, we introduce some penalizations in the following cases: • When the policy proposes g0 = g , being g the goal that was being accomplished. If g could not be reached and another closer goal was required, it makes no sense to propose the same one. • When the policy proposes a goal g0 that is directly achieved by the current state s . In this case the proposed goal does not help the agent reach its final objective. During the training stage we introduce a maximum number of goal proposals Hh for each episode, to avoid getting stuck in some environments. Taking this into account, a correctly completed episode can have a sequence of maximum Hh runs, therefore the values for R can get down to −Hh in a completed episode. To make the punishment work, we use Q ( s, a, g ) = −(Hh+ 1) in the mentioned cases, for both our strategies of long-term reward estimation. 4.3. MAIN COMPONENTS 41 4.3.3 Is reachable function The is reachable function is the third main component of our algorithm, and its goal is to predict if a goal g is reachable from a state s to decide whether to ask for a closer subgoal, or attempt a run towards g. Multiple alternatives exist to implement it. Data gathering To train this predictor we have to first gather data and store it in a Reply Buffer . It is important to note that the gathered information will be changing over time during the training phase in which the agents’ policies are being optimized. Imagine a low hierarchy agent with Hl = 3 that performs the following run of 3 steps over environment states A, B, C, D , as seen in Figure 4.2. Thanks to the triangular inequation we can ensure that if the agent has been able to move from A to D using Hl steps, B and C are also reachable from A . In fact, we can generate all the following state-goal pairs: reachable ={(A, sgm(B)),(A, sgm(C)),(A, sgm(D)),(B, sgm(C)),(B, sgm(D)),(C, sgm(D))}. On the contrary, if the goal was to reach G , we can only affirm that G is not reachable from A using this policy. As the triangular inequation is in fact an inequation, we can not extract any information about B , C or D . Additionally, note that with an optimal policy, G might be reachable from A , opposite to the “positive” transitions, which are true independently of the policy’s optimality. A B C D G Figure 4.2: Diagram to illustrate is reachable data gathering. Possible Implementations In this work we have tested two different implementations for the is reachable function. The first idea is to use a basic Neural Network such as a Multi Layer Perceptron (MLP) , trained on the positive and negative gathered data as a binary classifier. After each episode, some mini-batches of the buffer’s data would be sampled and used to update the network’s parameters. This concept has some advantages and drawbacks. Firstly, as a function approximator it is able to generalize over states and goals, learning faster. This, however, could also be a drawback because in a hard-boundary problem like this one, two consecutive states can have completely different outcomes. Moreover, there is a notorious class imbalance in the data, as we are only able to obtain one “negative” example for each non-achieved run, while multiple “positive” samples are generated. This fact could hinder the learning process. Finally, taking into account that the error tends to be larger in the first epochs, the most important gradient steps would be computed using transitory data gathered in the first episodes where the agents do not act close to optimal, with the possibility of moving the parameters far from the real optimum. The second approach to implement this function is a tabular method . Using this system, a certain state-goal pair is tagged as reachable if it has been visited before during training. 48 CHAPTER 5. EXPERIMENTS AND RESULTS Figure 5.3: Pendulum Environment. The goal proposals ask the agent to first move left (orange subgoal) in order to gain velocity to then move to the right sector towards the red milestone. g= sgm(s) = sgm (cos(θ), sin(θ),˙ θ)=atan2 (sin(θ),cos(θ)) ,˙ θ= (θ, ˙ θ) (5.1) With this definition, the goal of the environment becomes (θ= 0,˙ θ= 0). Finally, we have modified this environment to use a sparse reward of − 1 whenever the episode’s goal is not achieved, or 0 otherwise. To consider a goal achieved, we use the following definition where (θs,˙ θs) = sgm(s) and g= (θg,˙ θg): achieved(s, g) =    True if |normalize(θs-θg)|< θ∧ | ˙ θs−˙ θg|<  ˙ θ False otherwise (5.2) Note that θ and ˙ θ are two tolerances for the angle and the angular velocity respectively, and the normalize function maps any angle into [−π, π). 5.2 Preliminary studies This section contains several experiments and studies that were performed with the main objective of obtaining a better understanding on our new algorithm, its components and how each of them can affect its performance and convergence. Base learner comparison Learning Recursive Goal Proposal (LRGP) is able to work with any Value-based or Actor Critic Reinforcement Learning algorithm. In this experiment, performed on a 15x15 version of our Simple MiniGrid Empty environment, we have compared the performance of DDQN [14], DDPG [17], TD3 [10] and SAC [12,13] when used in our high hierarchy. Note that the Simple MiniGrid environment has an action set of three discrete actions. To match the nature of that space we use DDQN as it specifically designed for discrete action spaces. Regarding the goal space, which becomes the action space of our high hierarchy, it is also discrete. Therefore, the straightforward implementation would be using DDQN, treating each position of the grid independently. 5.2. PRELIMINARY STUDIES 49 Nonetheless, there is a correlation among those actions or goals, as they are spatially distributed in a two-dimensional grid. For this reason, we have implemented a discretization step in order to be able to use algorithms that are defined for continuous action spaces, therefore capable of generalizing over them. To be more specific, we use two-dimensional continuous actions, and divide the output range of each dimension into 15 equal bins (width and height of the environment), which are used to discretize and obtain the x and y coordinates of a goal proposal. Figure 5.4 shows the learning curves for these experiments, expressed as the success ratio achieved when testing the learned policy. The most remarkable result is that DDQN hugely underperforms the other methods. This is expected because it treats each grid position independently, thus being unable to generalize.                   Figure 5.4: Algorithm comparison for the high hierarchy. Among the other algorithms, TD3 performs similarly to DDPG, while SAC slightly outperforms all of them while learning faster and achieving a 100% success ratio more consistently. To conclude the analysis, we should say that Learning Recursive Goal Proposal’s flexibility to use different learners, enables the possibility to choose the most appropriate algorithm depending on the task. Moreover, this experiment showed that when having correlated discrete actions, it is better to use continuous-defined algorithms as generalization speeds up the learning process. Estimation technique comparison In this experiment we compare our two long-term reward estimation techniques introduced in Section 4.3.2. We refer to them as Monte Carlo for the version that uses long-term empirical returns; and Bellman for the version that is based on the Bellman’s recursive equation. Figure 5.5 shows the learning curves for the best configuration of our agents—using DDQN [14] for the low hierarchy and SAC [12,13] for the higher one—when using one or the other estimation techniques. 50 CHAPTER 5. EXPERIMENTS AND RESULTS                 Figure 5.5: Comparison between Monte Carlo-inspired and Bellman-based estimation techniques. Note how although both should converge to the same policy theoretically, the Monte Carlo inspired version clearly outperforms the Bellman-based one. A possible explanation for these results is the fact that Bellman’s version—opposite to Monte Carlo’s—relies on target networks to compute the “target” or “true” values used to train the Q-networks or critics. These target networks are updated at a significantly slower pace than the value ones, in order to overcome the moving target problem. This could hinder the learning speed of the high level agent, which at the same time could snowball into worse learning dynamics for the low one. All the following experiments have been made using the Monte Carlo version of long-term return estimation. Study on the sample efficiency In Section 4.3.2 we showed that our way of generating transitions for the high hierarchy was quite sample efficient because it created more samples than the number of runs that the episode contained. The main objective of this study is to illustrate how much sample efficient is our system in comparison with different methodologies. Figure 5.6 shows this comparison by presenting the number of transitions that are created as a function of the number of runs an episode has had. Without any special technique, a “plain” or common agent that interacts with the environment obtaining sparse rewards would create one data point per interaction. By making use of HER [1], this ratio would increase as Hindsight Experience Replay adds additional transitions to the buffer. The most used ratio for HER is one-to-one, therefore creating a hindsight transition for each original one, leading to a total of two transitions per interaction. Some algorithms may use higher HER ratios like two-to-one, which we also included. However, much higher ratios usually lead to instability and convergence problems. 5.2. PRELIMINARY STUDIES 51 Finally, the number of transitions generated by our method grows much faster than linear. In fact, it can be seen that for four runs we have less than 4 2 = 16 transitions, but for six runs we have more than 62= 36. Therefore, the growth of this function becomes more than quadratic. To conclude, it must be said that the reward function definition and the methodology used to generate transitions for our high hierarchy is one of the key points of this project, leading to incredible sample efficiency.                      Figure 5.6: Study on the sample efficiency. Solution to incomplete goal spaces The intention of this study is to analyze the ability of our solution to solve the problem of incomplete goal spaces presented in Section 4.3.4. To test our method we now use a 15x15 version of our Simple MiniGrid FourRooms environment, which as already mentioned, includes some inner walls or obstacles. These are placed in “valid” positions regarding the goal space. However, these positions are not reachable by the agent, which can never stand on walls. Therefore, if the high hierarchy proposes a goal located on a wall, which is in between the bounds or range of its output, the lower agent will never be able to reach it and that episode will never be achieved. Figure 5.7 shows a comparison between the learning processes of our algorithm when using our solution to this problem and without any treatment of these forbidden goals. It can easily be seen that without handling the problem, the algorithm is not able to solve the environment (at least in 25000 training episodes), while when using our solution the agent learns much faster and it achieves a better success ratio from the very beginning of the training stage. 52 CHAPTER 5. EXPERIMENTS AND RESULTS On the one hand, this analysis proves the importance of detecting this problem and on the other, the validity of our solution, which improves both the performance in the environment and the learning speed.                 Figure 5.7: Analysis of our solution to incomplete goal spaces. Analysis of the learning process Training multiple agents simultaneously is not a straightforward matter, as the interactions between their suboptimal policies can lead to instabilities and convergence problems. The goal of this study is to analyze how the whole algorithm, including the two agents and the is reachable function, learn simultaneously. In order to provide more insight on this process, Figure 5.8 shows different metrics of our algorithm learning to solve a 15x15 Simple MiniGrid Empty environment with low horizons of Hl= 4 and Hl= 8. Figure 5.8a presents the number of subgoals that were asked during the testing episodes inserted in between the training process, which has a direct implication on the convergence of the high policy. Note how it starts at 15, which is a hard limit that we established in order to avoid getting stuck when agents act far from optimal. In the following episodes the curves go down close to 4, to later converge to approximately 3. When using a shorter low horizon Hl , more goal proposals are needed, as expected. Figure 5.8c shows the success rate of the low agent. In other words, it presents the ratio of runs in which it could achieve its goal in no more than Hl steps. It can be seen that when the low agent starts learning how to achieve “reachable” goals, the high hierarchy starts to converge. Therefore, both learning processes are connected. Note how larger horizons need slightly more time to converge, which is expected because in that case the agent receives more state-goal combinations to learn. 5.2. PRELIMINARY STUDIES 53                  (a) Subgoal proposals.                  (b) High hierarchy buffer occupancy.                 (c) Low agent success rate.                (d) Low hierarchy buffer occupancy.                 (e) Success rate.                 (f) is reachable buffer occupancy Figure 5.8: LRGP’s learning process. Putting all together, Figure 5.8e shows the environment’s success rate. It can easily be seen that the whole algorithm’s convergence is strictly related to each of the agent’s. On the other side, Figure 5.8b shows the number of transitions inserted in the high hierarchy replay buffer, which has a size of 10 6 . Note how it’s occupancy grows faster in the first episodes. The reason behind this fact is the larger sample efficiency that we have in episodes with larger number of runs or goal proposals. Furthermore, with larger low horizon Hl , the number of subgoal proposals decreases and the buffer is filled slower. 54 CHAPTER 5. EXPERIMENTS AND RESULTS Figure 5.8d shows the same information for the low-level replay buffer. In this case, however, it grows at a slower pace because the low agent uses HER [1], which is less sample efficient. Moreover, note how both curves look the same because the total number of environment steps is independent on how many subgoal proposals are being used (if the proposals are meaningful). Finally, Figure 5.8f shows the number of unique transitions inserted in the buffer used for the tabular implementation of is reachable. It is important to see that its convergence is strongly related with the agent’s. Additionally, lower horizons Hl converge to lower values because there exist less reachable state-goal combinations (note that we only store “positive” reachable pairs). To conclude, it can clearly be seen that the convergence of the algorithm is strongly correlated with the convergence of each of its three main components: the high hierarchy, the low agent and the is reachable function. Therefore, it is crucial to find good hyperparameters for each of them, as a delay on one’s convergence has a huge impact on the learning speed of the whole algorithm. 5.3 Main Results In this section we are presenting the best results achieved by Learning Recursive Goal Proposal (LRGP) in each environment, along with a comparison to other non-hierarchical State-of-the-Art algorithms. For all experiments, the hyperparameters have been kept constant across all algorithms in order to provide the fairest analysis. Appendix A shows detailed information about them. Simple MiniGrid Empty Environment Figure 5.9 presents the learning curves for DDQN [14] , DDQN with HER [1,17], and Learning Recursive Goal Proposal (LRGP) with the best configuration obtained in the preliminary studies (see Section 5.2). It can be seen that although being a quite easy environment, a “plain” agent has problems to learn under sparse rewards, requiring almost 5000 episodes to obtain a perfect success ratio. With the addition of HER, DDQN is already able to learn quite faster thanks to the hindsight positive rewards. Regarding LRGP, the plot shows the learning curve for a configuration in which the goal proposer uses SAC [12,13]. Note that the success rate starts growing slightly before than DDQN + HER, which is expected as the low agent uses in fact DDQN + HER, but it has the advantage that it does not need to learn the whole state-goal space but only the goals proposed by the high hierarchy. As seen in the preliminary studies, the high hierarchy requires a couple more episodes to converge and stabilize close to 100% success rate. To conclude, in the empty version of the Simple MiniGrid environment, Learning Recursive Goal Proposals obtains comparable results to the current State-of-the-Art, with the added difficulty of training two agents simultaneously. 5.3. MAIN RESULTS 55                  Figure 5.9: State-of-the-Art comparison in Simple MiniGrid Empty 15x15 environment. Simple MiniGrid FourRooms Environment Although being quite similar visually, the FourRooms version of the Simple MiniGrid environment is significantly different in difficulty. In fact, the first thing that can be seen in Figure 5.10, which presents the learning curves of different algorithms in this environment, is that they need, at least, 10 times more episodes to reach good performances. If we start analyzing DDQN, we can see that this well-known algorithm is not able to solve the environment within 25000 episodes. In particular, it does not reach a 25% success rate in all the training stage. The addition of HER helps DDQN to obtain between 30% and 40% success rate between episodes 1000 and 20000. During this stage it seems that DDQN + HER is consistently capable of solving some environments, but it can not achieve many others. A possible reason might be the inability of crossing doors and changing rooms, which require high exploration. In fact, approximately episode 20000 seems to be critical because DDQN + HER increases its success rate rapidly. Finally, LRGP is able to obtain similar success rates already in episode 10000, learning more than twice as faster as non-hierarchical solutions. In this environment, where learning a good goal-conditioned policy that can guide the agent from any state to any goal is quite complex, our hierarchical solution shines by proving its sample efficiency and the advantages of dividing the search space in different agents. Opposite to the empty environment, which was quite easy, the FourRooms environment presents a favorable trade-off between the complexity of training two agents simultaneously and the benefits of having such hierarchy. 56 CHAPTER 5. EXPERIMENTS AND RESULTS                  Figure 5.10: State-of-the-Art comparison in Simple MiniGrid FourRooms 15x15 environment. Pendulum Environment As mentioned in Section 5.1.2, Pendulum [22] is an environment that uses both continuous state and action spaces. For this reason, in this experiment we have compared our algorithm to two State-of-the-Art methods for environments of this nature: Soft Actor Critic (SAC) [12,13], and SAC + HER, which improves learning in sparse reward schemes. Moreover, we have used SAC both for our low hierarchy which has to perform a continuous action, and for the high hierarchy which has to propose a continuous goal. Figure 5.11 shows the results for this experiment, in which all algorithms work quite similarly. Firstly, it is worth mentioning that all the methods have a 0% success rate during some episodes. The reason behind this is that in the Pendulum environment, the final goal is always to reach an upwards position with zero velocity. Therefore, it is almost impossible to complete an episode with a suboptimal policy, as opposed to MiniGrid environments in which some easy generations with close initial state and goal were possible. Second, note how SAC is able to solve the environment on its own quite efficiently, and the addition of HER does not make a huge difference. This could be due to the fact that SAC’s implicit exploration is enough to solve the task, and learning a goal-conditioned policy is not required as the goal is always the same. On the other side, it can be seen that LRGP is also able to solve the task with approximately the same amount of episodes. This proves that the algorithm can work with environments of any nature, as well as with different base learners for each of its hierarchy levels. To conclude, Pendulum has been a good environment to prove the ability to work on continuous tasks, but it may be too easy to show the power of the hierarchy because a nonhierarchical State-of-the-Art method is already able to solve it straightforwardly. Regardless, LRGP has proved that can obtain, at least comparable results to State-of-the-Art methods while training two agents simultaneously. 5.3. MAIN RESULTS 57                  Figure 5.11: State-of-the-Art comparison in Pendulum Environment. 64 BIBLIOGRAPHY Appendix A. Implementation Details Simple MiniGrid Environments The non-hierarchical agents have been implemented using DDQN [14] with the hyperparameters shown in Table A.1. Furthermore, the low hierarchy has also been implemented with DDQN and the same parameters. Hyperparameter Value Discount factor γ1 Soft-update parameter τ0.005 Hidden dimensions (128, 128, 128, 128) Optimizer AdamW with default parameters Learning rate 3e-4 Buffer size 5e5 Table A.1: DDQN default hyperparameters for Simple MiniGrid environments. Regarding the high hierarchy of Learning Recursive Goal Proposal, it has been implemented using SAC [12,13] and the hyperparameters presented in Table A.2. Furthermore, the selected continuous action has been discretized using the floor function to obtain a discrete coordinate. Hyperparameter Value Discount factor γ1 Soft-update parameter τ0.005 Entropy weight α1 Hidden dimensions (for all networks) (128, 128, 128, 128) Optimizer (for all networks) AdamW with default parameters Learning rate (for all networks) 3e-4 Buffer size 1e6 Table A.2: SAC default hyperparameters for Simple MiniGrid environments. The is reachable function has been implemented with a 1e5 buffer and an exact look-up call; and for the FourRooms environment, we have implemented our solution to the incomplete goal space problem using a buffer of 200 dimensions (which is exactly the number of non-forbidden states in the 15x15 version of the environment). Finally, we have used the learning parameters shown in Table A.3 to train all our policies. 65 66 APPENDIX A. IMPLEMENTATION DETAILS The length of the training stage has been 5000 episodes for the Empty version of the environment and 25000 for the FourRooms variant. Hyperparameter Value LRGP’s low horizon Hl4 LRGP’s limit of subgoal proposals Hh15 Network updates per episode 5 Batch size 256 -greedy (DDQN and is reachable) as in Figure A.1 Table A.3: Learning parameters for Simple MiniGrid environments.                Figure A.1: -greedy exploration. 67 Pendulum Environment In the Pendulum Environment we have used SAC for all our experiments, using the hyperparameters shown in Table A.4. Hyperparameter Value Discount factor γ0.2 Soft-update parameter τ0.005 Entropy weight α1 Hidden dimensions (for all networks) (128, 128, 128, 128) Optimizer (for all networks) AdamW with default parameters Learning rate (for all networks) 3e-4 Buffer size (non-hierarchical and low) 5e5 Buffer size (high) 1e6 Table A.4: SAC default hyperparameters for the Pendulum environment. Additionally, we have used the learning parameters presented in Table A.5. Hyperparameter Value Episodes 10000 LRGP’s low horizon Hl15 LRGP’s limit of subgoal proposals Hh15 Tolerance on the angle θ0.15 rad Tolerance on the angular velocity ˙ θ1 rad/s Network updates per episode 5 Batch size 256 -greedy (is reachable) as in Figure A.1 Table A.5: Learning parameters for the Pendulum environment. Finally, the is reachable function has been implemented using a buffer of capacity 1e5, and a look-up call that checks if there is any state-goal pair in the buffer such that both the state and the goal are close to the query. To implement this comparison, let ( θsq,˙ θsq, θgq,˙ θgq ) be the state-goal queried pair (the state has already been converted into the goal space), and ( θsi,˙ θsi, θgi,˙ θgi ) the i th component in the buffer. Therefore, using a normalization function that maps any angle to the range [ −π, π ), the is reachable is defined as in Equation A.1, using the tolerances presented in Table A.5. is reachable =        True if ∃i s.t. |normalize(θsq-θsi)|< θ∧ | ˙ θsq −˙ θsi|<  ˙ θ∧ |normalize(θgq-θgi)|< θ∧ | ˙ θgq −˙ θgi|<  ˙ θ False otherwise (A.1)