Reverse curriculum hierarchical recursive learning

Master Thesis Reverse Curriculum Hierarchical Recursive Learning Author: Tair Tahar Supervisor: Mario Martin Mu˜noz, Department of Computer Science, UPC Master in Artificial Intelligence (MAI) Barcelona, June 2022 Abstract This work presents a study on Hierarchical Reinforcement Learning, where several different approaches for learning are researched, developed and tested. Specifically, the algorithm Reverse Curriculum Vicinity Learning (RCVL) resulted with an excellent performance in the tested environments. It is built on two level hierarchies, where the high hierarchy learns to suggest adequate subgoals to the lower level recursively, the latter learns the sequence of needed primitive actions to achieve the subgoals, and finally the ultimate goal. Currently it is designed only for discrete Reinforcement Learning environments. Hierarchical Learning allows to break a task into several smaller sub-tasks, which results with faster learning, since smaller tasks are easier to master. Each of the levels in the hierarchy has its own ”resolution” (i.e. different time scales) of the problem, while the low policy is the one to interact with the environment exclusively. In our problem the subgoals proposed by the high policy can be seen as milestones that break the big task into several shorter tasks. The proposed algorithm integrates the concept of Reverse Curriculum Learning. Its learning begins from states around the goal, and gradually expands to more difficult tasks from further states, until mastering the whole state space. With this curricular approach, the agent is able to learn faster: first it masters the easy tasks, and then challenged with harder tasks. In the proposed algorithm the high hierarchy stores neighbours from the vicinity of each goal (collected by low hierarchy interactions) such that the goal is reachable from them with a limited number of actions. In the meantime, the low policy learns simple actions to solve the mini-trajectories from the neighbours to the goal. Then with the accumulation of knowledge of both hierarchies, the high policy learns to draw a path from the goal to the state backwards recursively, suggesting the subgoals along the way. By long-term return estimation learning, the agent is able to decide which is the best subgoal for each given pair of state and goal (or subgoal). It is possible to make the learning even faster when allowing a preliminary phase of vicinity acquisition. In this configuration small and fast interactions of the low level with the environment are done first. Only afterwards the concurrent learning of both hierarchies is performed together. This allows a good starting point for learning during the main learning phase. More concepts are integrated in the algorithm to accelerate the learning and to allow sample efficiency. First, the algorithm is an off-policy algorithm, that is, the experience is accumulated, and is being used later to train a policy that is different from the policy acting while the experience was acquired. Secondly, the reward system is designed to exploit the maximum information when rolling-out the collected experience so that all possible ordered combinations are stored with a non-sparse reward. Finally, the algorithm uses Hindsight Experience Relabelling, allowing exploitation of the accumulated experience in a more efficient way. The proposed algorithm has shown outperformance over the State of the Art algorithms: DDQN [1], and DDQN combined with HER [2] in more complex tested environment. It has reached to a success rate of above 97%, while avoiding unfeasible subgoals suggestion, and constructing optimal paths. Finally, it has shown to be robust to most of hyperparameters changes. Keywords: AI ·Machine Learning ·Reinforcement Learning ·Hierarchical Learning · Curriculum Learning ·Actor Critic ·SAC ·DDQN ·HER ·Q-learning ·UVFA Acknowledgements I would like to use this opportunity to give my gratitude to important people who’s presence was essential along this journey: To my amazing parents, with their endless unconditional giving and caring, which is impossible to describe with words. Together with the rest of the family, you have given me the strength and calmness I needed. To my wonderful partner, Maria, for being my best friend, my family, my confidant. For being supportive and encouraging, and for making Barcelona a home. To my great friends from MAI, for the reciprocal teaching with patience and laughter, and for sharing with me beautiful moments in Catalunya. To my dearest long-life friends from Israel, that are always there for me. to ask, to listen, to be. It would have not be possible without them. To Varda, who always knew why. To the Barcelona Supercomputing Centre, for facilitating the computational challenges with kindness and efficiency. Finally and mostly, a greatest gratitude to Mario my dear supervisor, who has ignited my passion for Reinforcement Learning, and gave me generous guidance through this quest. Thank you for incredibly interesting conversations and fruitful shared thinking. Contents 1 Introduction 1 1.1 Motivation..................................... 1 1.2 Contribution.................................... 3 1.3 DocumentOverview ............................... 3 2 Background: Reinforcement Learning 4 2.1 InitialFormulation ................................ 4 2.2 ValueFunction .................................. 6 2.3 Stochastic Vs. Deterministic Policy . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Exploration Vs. Exploitation . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5 On-policy Learning Vs. Off-policy Learning . . . . . . . . . . . . . . . . . . 8 2.6 Modelfreealgorithms............................... 8 2.6.1 ValueIteration .............................. 9 2.6.2 Policy gradient algorithms . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6.3 Actor Critic Algorithms (AC) . . . . . . . . . . . . . . . . . . . . . . 14 3 Related Work 18 3.1 Universal Value Function Approximators (UVFA) . . . . . . . . . . . . . . . 18 3.2 ExperienceRelabeling .............................. 20 3.3 HierarchicalLearning............................... 20 3.4 CurriculumLearning ............................... 24 3.4.1 Reverse Curriculum Generation for Reinforcement Learning . . . . . 27 4 Algorithms 29 4.1 Motivation..................................... 29 4.2 Reverse Curriculum Learning: Adjustments to the Hierarchical framework . 30 4.3 Main common components for both suggested algorithms . . . . . . . . . . . 31 4.3.1 Lowpolicy................................. 31 4.3.2 is reachable set............................. 31 4.3.3 Highpolicy ................................ 32 4.4 Reverse Curriculum Recursive Learning (RCRL) . . . . . . . . . . . . . . . . 34 4.4.1 Theidea.................................. 34 4.4.2 Algorithmflow .............................. 34 4.5 Reverse Curriculum Vicinity Learning (RCVL) . . . . . . . . . . . . . . . . . 37 4.5.1 Theidea.................................. 37 4.5.2 Algorithmflow .............................. 38 4.5.3 Algorithm main components . . . . . . . . . . . . . . . . . . . . . . . 40 4.5.4 Learning Recursive Goal Proposal by value estimation . . . . . . . . 44 5 Experiments and Results 45 5.1 Environments................................... 45 5.1.1 Minigrid Empty room . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.1.2 Four Rooms MiniGrid . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.2 Studies During Development - configurations . . . . . . . . . . . . . . . . . . 47 5.2.1 Symmetry in the vicinity acquisition . . . . . . . . . . . . . . . . . . 47 5.2.2 Low Policy learning phase . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2.3 Flat acquisition Vs. round (back and forth) vicinity . . . . . . . . . . 50 5.3 Preliminary experiments - Hyperparameters search . . . . . . . . . . . . . . 51 5.3.1 Radius for states collection . . . . . . . . . . . . . . . . . . . . . . . . 51 5.3.2 Samples size in preliminary acquisition . . . . . . . . . . . . . . . . . 52 5.3.3 Back and forth while preliminary acquisition: number of repetitions . 55 5.3.4 Low level horizon effect . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.3.5 High level horizon effect . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.4 Comparison with State of the Art and baseline . . . . . . . . . . . . . . . . . 58 5.4.1 Minigrid empty room . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.4.2 Minigrid FourRooms environment . . . . . . . . . . . . . . . . . . . . 60 6 Conclusions and Future Work 64 6.1 Reverse Curriculum Recursive Learning (RCRL) . . . . . . . . . . . . . . . . 64 6.1.1 Discussion and conclusions . . . . . . . . . . . . . . . . . . . . . . . . 64 6.1.2 FutureWork................................ 65 6.2 Reverse Curriculum Vicinity Learning (RCVL) . . . . . . . . . . . . . . . . . 66 6.2.1 Discussion and conclusions . . . . . . . . . . . . . . . . . . . . . . . . 66 6.2.2 Futurework................................ 70 A Implementation Details 74 A.1 RCRL implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A.2 RCVL implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A.3 DDQNimplementation.............................. 75 A.4 SAC implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Chapter 2– Background: Reinforcement Learning Initial Formulation – 5 The general framework of RL, can be represented by figure 2.1 and it can be formalised by Markov Decision Process (MDP), as the tuple <S,A,R, P >. The current state of the agent is assigned as s, which is one state from the set of possible states S. By executing action aout of the set of possible actions A, the agent receives a reward r∈ R, while the state of the agent is updated to be s′∈ S. When the environment is not fully observable, then instead of state we have only observation o, which might not contain the complete knowledge about the real state. R(st, at, st+1) is the reward function, and P(st, at, st+1) is the transition probability function in time step t. Figure 2.1: RL Framework [6] The objective of the process is for the agent to learn an optimal behaviour (policy), which maximises its overall long term return. The reward function Rdetermines the immediate reward rtat each step of the learning rt=R(St): R(s, a) = E[rt+1|st=s, at=a] (2.1) Which can also be expressed in the following way: R(s, a) = X s′ P(s, a, s′)· R(s′) (2.2) The long-term reward in the case of a finite horizon Hcan be express in the following way: Rt=rt+1 +rt+2 +rt+3 +... = H X k=0 rt+1+k(2.3) For the infinite horizon case, we say the the summation continues until infinity (H → ∞). A discount factor γ∈(0,1] is usually introduced when calculating the long-term reward, which results with the following expression for the infinite horizon case: Rt=rt+1 +γrt+2 +γ2rt+3 +γ3rt+4... = ∞ X k=0 γkrt+1+k(2.4) When the value of γequals one, we get a far-sighted evaluation, while when it is close to zero, the significance of further steps decreases greatly. 5 Chapter 2– Background: Reinforcement Learning Value Function – 6 2.2 Value Function The Value Function is a prediction of future accumulated reward from a particular state, which depends on the agent’s policy. The idea is to have the cached knowledge in a single function Vπ(s) that represents the utility of any state sin achieving the agent’s overall goal or reward function. This knowledge allows the agent to immediately assess and compare the utility of states and/or actions [7]. The state-value function Vπ(s) is defined as the expected return, when the agents begins at state sand follows the policy π: Vπ(s) = E π[Rt|St=s] = E π(∞ X k=0 γkrt+k+1 St=s)(2.5) The action-value function Qπ(s, a) is the future expected return when the agents begins at state s, executes action aand the follows then policy π: Qπ(s, a) = E πRtst=s, at=a=E π(∞ X k=0 γkrt+k+1 st=s, at=a)(2.6) The Bellman expectation equation decomposes the value function and action-value function using the recurrence relation in following way: Vπ(s) = E π[Rt|st=s] = E πrt+1 +γV π(st+1)st=s(2.7) Qπ(s, a) = E π[Rt|st=s, at=a] = E πrt+1 +γV π(st+1)st=s, at=a(2.8) We can notice that Qπ(s, π(s)) = Vπ(s), which implies that the above can be also expressed in recursively with Qstate-action value: Qπ(s, a) = E πrt+1 +γQπ(st+1, π(st+1)) st=s, at=a(2.9) The optimal policy is a policy that means any action selection that is not following the policy will result in lower long-term return. The learning of the optimal policy can be achieved by either iterating the policy (PI) adding some exploration or iterating the value functions (VI), while some algorithms combine them both. In order to converge to the optimal policy, the agent faces the trade-off between exploration of new unknown state, to exploitation of the information it already obtained from the environment in past experience. It is possible to improve policy πif and only if there exist a state sin the state space Sand an action ain the action space A, such that Qπ(s, a)> Qπ(a, π(s)). If a policy πis improvable, it means it is not optimal when choosing action afrom state s. The optimal policy can be expressed in the following way based on value functions and transition function, showing is it a greedy policy: π(s) = argmax a∈A Qπ(s, a) = argmax a∈AX s′ Pa ss′[R(s′) + γV π(s′)] (2.10) 6 Chapter 2– Background: Reinforcement Learning Stochastic Vs. Deterministic Policy – 7 If the policy is the greedy policy that means that the value function is maximised: Vπ(s) = max a∈AQπ(s, a) = max a∈AX s′ Pa ss′[R(s′) + γV π(s′)] (2.11) 2.3 Stochastic Vs. Deterministic Policy A policy can be either stochastic or deterministic.Deterministic policy would like: a=πθ(s) (2.12) meaning that in state s, the agent will always choose action a.Stochastic policy would be expressed like: P(a|s) = πθ(a|s) (2.13) meaning that the probability for the agent to choose action afrom state sis according to the policy. Stochastic policies can be either categorical policies in discrete action space, or Gaussian policies for continuous action space. The good thing with stochastic policies is that they are smoother than greedy policies, so it is possible to use the gradients. For training stochastic policies we can sample actions from the policy, and we can compute the log likelihood of particular action logπθ(a|s). 2.4 Exploration Vs. Exploitation AGreedy Policy is the optimal one. That is the behaviour that has the highest possible benefit given a particular environment. It can not be further improved. A greedy action is the one that is selected by the policy. Under the assumption that the policy converges to the optimal one, a greedy action is simply the one that is suggested by the current policy. However, we know that the policy is not always optimal, so its selection of actions should be reconsidered during training. Mostly in the beginning of the training, where we start with a random policy, it is hard to believe that the action selected by the policy is the best one. Knowing the agent collects its experience, and in the meanwhile aims to improve its policy, we face the RL famous trade-off of exploration and exploitation. In order to get to know as much as possible about the environment, to be able to choose wisely, and converge to the optimal policy, we need to have the experience of the agent as wide as possible. That means we need to explore a lot, and let the agent not always go with its current policy, so new states are visited, and the knowledge on the environment gets more complete. On the other hand, we want to maximise the long-term expected return. We have the policy that is learnt, and that is expected to get closer and closer to optimal behaviour, and assumed to benefit the agent with higher rewards. That makes it appealing to use the existing policy, knowing that following it, the long-term return should be relatively high (higher as much as the training proceeds). With that, if we keep only following the current policy, we might get stuck in a local minimum, with suboptimal behaviour, because we haven’t got all the experience needed 7 Chapter 2– Background: Reinforcement Learning On-policy Learning Vs. Off-policy Learning – 8 to do the best actions. A useful compromise between those two is the ϵ-greedy (Epsilon Greedy) exploration. That method allows the agent to explore with probability of ϵ. Explore means to choose an action at random. The agent chooses the action according to the policy only with probability of 1 −ϵ. When ϵis high (close to 1) then we are more likely to explore, and the opposite when it is small. ϵcan be viewed as a hyperparameter, where the problem needs to be solved and the agent’s architecture should be considered for a wise choice. It is frequent to use a decaying epsilon, which means that in the beginning of the learning we explore more, and as we proceed we rely more on the policy, as the policy is closer to the optimal one, less random actions for exploration. There exist some other popular exploration methods such as Softmax Exploration, Gibb’s exploration, that adjust the exploration with more specific characteristics to bias the exploration to more promising actions, or other possible motivations. 2.5 On-policy Learning Vs. Off-policy Learning On-policy methods try to evaluate/improve the policy that is used for action selection, while Off-policy methods try to evaluate/improve a policy that is different from the one that is used for the data generation. In on-policy the agent grasps the optimal policy and uses the same policy to act and learn from it as the action is executed, right after the episode completion. On-policy training should be used when the value of the current exploring agent needs to be optimised. Off-policy training can be cost-effective when the deployment of the algorithm is in the real world. The updated policy is different from the policy used for experience accumulation. With that said, for the off-policy case, the evaluation becomes more challenging due to high randomness. 2.6 Model free algorithms RL problems can be solved using model-based methods or model-free methods. Modelbased methods allow inference on the environment [8]. Models are used for planning, deciding on actions by considering possible future situations. A model predicts the next state and the reward. In model-free solutions, we can not infer on the environment, and the information about the environment is captured only by the interaction of the agent with it: being in a particular state s, perform an action a, and observe the reward rand the next state s′. Changing the policy of value function from a specific state of a model-free agent, the agent must move to that state and act from it, possibly many times. Model-free algorithms are able to generalise to more environments. 8 Chapter 2– Background: Reinforcement Learning Model free algorithms – 9 In figure 2.2 it is possible to see the distribution to the two main groups, through the methods used and eventually specific algorithms that implement these ideas. The algorithms that will be presented in this work are model-free, which allows generalization to other possible environments. Figure 2.2: Taxonomy of RL algorithms[9]. In model free algorithms the agent gets to know more and more about the environment, as it collects experiences, while interacting with the environment. The experience is collected while the agent is going through different episodes or trials. Each episode has a starting state and a goal state. The observation of a sequence of states, actions and reward during the episode reveals information regarding the environment. Based on those experiences, it is possible to estimate the long term return from each state by averaging the collected rewards after these states in different episodes. In the following sections several important components of model free algorithms will be presented, as well as some useful methods we will use in this project. We will start by explaining VI and PI methods, and then we will see how those are merged into one algorithm with the two components. 2.6.1 Value Iteration One major drawback of PI (that will be elaborated in more details in section 2.6.2), is that each iteration involves policy iteration, which is another iterative process over the state space. Sutton et al. show in their book [3] that there is no need to iterate the value function more than a few times, to lean on it for policy evaluation, without losing the promise for convergence of the algorithm. An important special case is where value iteration is truncated after exactly one iteration, it is called Value Iteration, and it combines policy improvement and 9 Chapter 2– Background: Reinforcement Learning Model free algorithms – 10 truncated policy evaluation steps. In practice, VI can be seen as turning Bellman’s optimality equation into an update rule. Similar to PI this process should continue an infinite amount of times until convergence to the optimal value, however when the updates are small enough (below some threshold) the process is stopped in practice. 2.6.1.1 Monte Carlo Methods The Monte Carlo methods assume episodic tasks, meaning every episode terminates, with no dependency on the action selection. In those methods we average the complete return from the state until the end of the episode. The process is involved with computing the value functions Vπand Qπfor a fixed arbitrary policy π, then policy improvement, and finally generalised policy iteration. This idea is used also in Dynamic Programming (DP), which is amodel-based approach. In its simplest version, MC takes long term rewards collected from a state in different episodes and averages over them. For this case, it is necessary to complete all the episodes we want to base on in the calculation. In the version of Incremental MC it is possible to update the value function after every episode, following the update: Vn(st) = Vn−1(st) + 1 n(Rt−Vn−1(st)) (2.14) Where n is the number of visits to each state, which we should store. Instead of using that coefficient of 1 nusually a constant parameter αis used: V(st) = V(st) + α(Rt−V(st)) (2.15) It can be shown that: Vn(s) = α n−1 X i=0 (1 −α)iRn−1+ (1 −α)nR0(2.16) With this parameter αit is possible to control the proportion of old long-term return forgetting. It is useful since as the training proceeds, the policy is updated, so the new created experiences are more updated with it, and older ones are less important. Moreover, it is frequent to use a decaying alpha, meaning forgetting more. Observing equation 2.15, but bearing in mind the exploration - exploitation trade-off that is brought under section 2.4, the MC incremental update becomes: Q(s, a)←Q(s, a) + α(Rt−Q(s, a)) (2.17) MC is an on-policy method (further explanation on on-policy learning is under section 2.5). 10 Chapter 2– Background: Reinforcement Learning Model free algorithms – 11 2.6.1.2 Temporal Difference (TD) Methods: Q-Learning Another value iteration method that uses an idea that is similar to MC, but using Bellman’s equation in the place of Rt: Q(s, a)←Q(s, a) + α[rt+1 +γQ(s′, π(s′)) −Q(s, a)] (2.18) Q(s, a)←(1 −α)·Q(s, a) + α[rt+1 +γQ(s′, π(s′))] (2.19) This way of using Q-Value estimations of the next state to update the current one is called bootstrapping, and it allows the value to update every state and not only when the episode ends. That is a significant advantage of Q-Learning over MC. TD is an off-policy method (further explanation on off-policy learning is under section 2.5). 2.6.1.3 Deep Q-Netowrk Q-Learning that is performed via MC and TD is based on the tabular case of Q-function, which becomes very complex as the dimensionality grows. That is what gives the importance to Function approximators (FA). Its major advantages are that it can both generalise to unseen states, and in the meantime enabling to approximate a Q-value table without a dependency on the state/action dimensionality. The way to converge to optimality would be applying gradient descent where the loss function is the difference between the estimation and the actual real values from the collected experience, in a supervised manner. When the real value is unknown then bootstrapping is used. Having this approach alongside with online incremental learning, the experience samples are consequent and are not independent and identically distributed (i.i.d). This problem is resolved with batch gradient descent, which means that we sample randomly from past experiences. This of course can be done only with off-policy learning, using a Replay Buffer or Experience Replay ER. This buffer accumulates the collected experiences, and then when it is needed to update the approximator, a sample from this buffer is used. Experience is stored in the ER with the pattern of < s, a, r, s′>: state,action, reward and next state. In this way the samples are expected to be closer to be i.i.d and the learning gradient is more stable since it relies on computation over a batch of samples and not only a single one experience. Another problem that rises is the moving target problem. We calculate the loss based on the target that keeps on changing. The solution that is suggested is to handle two sets of approximators, θfor Q-Value, and the other, θ′for target Q-approximator. The target ones are only updated when an episode is finished, meaning it does not change during supervised regression. That solves the problem of the moving target to a large extent. In addition with ER, having the policy changing over the time, but continuing sampling from old experiences for approximator updates, might result in inappropriate updates for 11 Chapter 2– Background: Reinforcement Learning Model free algorithms – 12 irrelevancy purposes. That can be solved with either removing old samples from ER, or limit its size with FIFO (first in, first out) method cleaning. FIFO means that the first one to get into the ER is the first to also get erased from the memory. DQN algorithm is an important breakthrough [10] in Q-learning approximation development. It is a FA in the form of a deep Neural Network (NN) along with incremental learning mode. It uses a NN, parametrized by θfor Qθ(s, a) approximation, while for loss calculation, the ground truth that is used is bootstrapping for each experience (s, a, r, s′): Qθ(s, a) = r+γmax a′Qθ′(s′, a′) (2.20) The error can be then expressed by: error =Qθ(st, at)−rt+1 +γmax a′Qθ′(st+1, a′) (2.21) Based on the value FA the policy can be evaluated and improved. DQN has revealed a clear outperforming over the former existing methods, however one significant drawback is that it can be optimistic when estimating the Q-value. That happens given a random initialization of the networks. Observing equation 2.21, we notice that in the case where all of actions have a zero reward, the estimation should be exactly r, however with the random initialization it might get a positive result (this is a maximum operator). This overestimation propagates to other states. 2.6.1.4 Double Deep Q-Learning (DDQN) Double Deep Q-Learning [1] tackles the overestimation problem presented in the former section, using the two existing NNs for Q-value estimations that are parametrized by θand θ′. The NN Qθ′is udes for action selection while Qθis used for action evaluation. The equation for the error in 2.21 then becomes the following: error =Qθ(st, at)−rt+1 +γmax a′Qθ(st+1,argmax a′ Qθ′(st+1, a′)) (2.22) The resulting algorithm is shown in Algorithm 1. In this algorithm we minimise square error between Qθand Q∗, while Qθ′softly copies the parameters of Qθ, using Polyak averaging with τ, the averaging rate [11]. 2.6.2 Policy gradient algorithms In this family of algorithms there is an explicit representation of the policy πθ(a|s). The parameters θare learnt via optimising the objective function (loss). The general idea of PI is to initialise the policy randomly and then go through the iterative process where the action selected by the policy is updated in case it increases the long-term return. The optimal policy is expressed in 2.10. 12 Chapter 2– Background: Reinforcement Learning Model free algorithms – 13 Algorithm 1 DDQN: Deep Double Q-Learning (Hasslet et al., 2015) [1] 1: Initialize primary network Qθ, target network Qθ′, replay buffer D,τ << 1 2: for each iteration do 3: for each environment step do 4: Observe current state stand select action at∼π(st) 5: Execute and observe next state st+1 and reward rt=R(st, at) 6: Store experience (st, at, rt, st+1) in D 7: end for 8: for each update step do 9: Sample experience batch ∼D 10: Compute target Qvalue:Q∗(s, a)≈rt+γQθ(st+1,argmaxa′Qθ′(st+1, a′)) 11: Perform batch gradient descent step on the error (Q∗(s, a)−Qθ(s, a))2 12: Update target network parameters: θ′←τ·θ+ (1 −τ)·θ′ 13: end for 14: end for In the end of every iteration of training, or every several of them, the policy that is learnt should be evaluated, which means its value-function should be calculated. In theory the process should continue infinite times for convergence to the optimal policy. In practice, the iterations continue until the updates in the policy become very minor (below some threshold). Policy iteration has more promising probability for convergence than Q-value iteration. It is effective in high dimensional or continuous action spaces, and it can learn stochastic policies. However, it tends to converge in a sub-optimal solution (locally optimal), and it also tends to have a lot of variance and to sampling inefficiency. There are several approaches for policy iteration such as Cross Entropy Method and some Genetic Algorithms. We will elaborate more on Policy Gradient since it is the approach we implement in this project. The idea is to perform gradient ascent to find the policy that results with the maximum long term return, the value function. We define the the long-term reward from a trajectory τ= (s0, a0, r1, s1, a1, r2, ..., sT−1, aT−1, rT, sT) as the sum of the reward accumulated during the trajectory, which can also be discounted with γ: R(τ) = T X t=1 r(st) (2.23) We then note P(τ|θ) as the probability of the path τfollowing policy πθ. The policy value J(θ) can be expressed as in equation 2.24. We aim to maximise this term with respect to θ, which implies analytically compute ∇P(τ|θ). Assuming the policy is differentiable when it is not zero, we can use the log trick that allows us to replace this gradient with the derivative of its logarithm as shown in equation 2.25. Then we can derive ∇θlogP(τ|θ) using the stochastic policy to eventually get the gradient expression brought in 2.26 (His the horizon) 13 Chapter 2– Background: Reinforcement Learning Model free algorithms – 14 for a sample of mexperiences. J(θ) = E πθ [R(τ)] = X τ P(τ|θ)R(τ) (2.24) ∇θJ(θ) = X τ P(τ|θ)R(τ)∇θlogP (τ|θ) (2.25) ∇θJ(θ)≈1 m m X i=1 R(τ) H−1 X i=0 ∇θlogπθ(ai|si) (2.26) Second approach that aspire to optimise the expected return over state (2.27), having dπθ the probability of being in each state according to the policy (expected number of time steps the agent is in snormalised by the number trial time steps). Third and last, taking into consideration one immediate reward as brought in 2.28. J(θ) = X s dπθVπθ(s) = X s dπθX a πθ(a|s)Q(s, a) (2.27) J(θ) = X s dπθVπθ(s) = X s dπθX a πθ(a|s)r(s, a) (2.28) Policy Gradient theorem expresses the equation for the objective function gradient, as appear in 2.29, for each of the approaches proposed (2.24, 2.27, 2.28). ∇θJ(θ) = E πθ [∇θlogπθ(a|s)Qπθ(s|a)] (2.29) The classic algorithm to mention under policy gradient is Reinforce. It is a simple policy iteration where we generate an episode following the policy πθ, then rolling it out we calculate the long-term return from each time step Rt, and finally updating the parameters θwith a rate of αand according to: ∇θlogπθ(a|s)Rtbased on 2.29. This process is being iterated until convergence up to some threshold. One problem in Reinforce is that it has a lot of variance, which affect the convergence and solution. To overcome this, a baseline, which is an estimation of Vπθ(st) is introduced for the calculation of Rt. This approach is called Actor Critic algorithm. 2.6.3 Actor Critic Algorithms (AC) This is a family of algorithms that combines both Policy Iteration and Value Iteration concurrently. AC can be performed as on-policy (MC) or off-policy. It uses the estimation of Vπθ(st) as a baseline in the parameters update and explained in the former section. It has two main components: An Actor that implements the current policy, and a Critic that evaluates the current policy, and is being used for training. It holds two sets of parameters, one for each one of the components. For the Critic approximation is it possible to 14 Chapter 3– Related Work Hierarchical Learning – 21 Figure 3.2: HAC general concept for the associated policy using Bellman equation as target. It is expected to be easier for the agents to learn multiple shorter policies in parallel rather than one long policy. The subgoals that the Actor network needs to learn should be efficient (achieve its high level goal in as minimum amount of actions as possible), while suggesting goals that are achievable by the lower level actor in a limited number of steps (low level horizon). Those two objectives are contradicting, hence, a coordination between the higher level and lower level is needed. To address this need for coordination HAC proposes two measures: First, all experience transitions passed to the replay buffers of subgoal actor networks contain actions that were actually achieved by the consequent, lower level actor network within the number of actions limit. Secondly, HAC penalises when subgoals that are proposed were not achieved. If layer iproposed a subgoal that was not achieved, layer i receives a negative reward with no discount factor, making it not dependent on the Q-value of a different state. HAC shows good performance, however it also suffers from a problem of non-stationarity when different hierarchies learn in parallel, building on non-optimal estimations of lower levels. The paper [17] tries to tackle the non-stationarity problem. It suggests that RL can be used to learn all policies in parallel if each level above ground level has a way to simulate a transition function that uses the optimal versions of lower level policies. The suggested framework allows the user to simulate a transition function that uses an optimal lower level policy hierarchy. The algorithm is implemented basing on two concepts that express HER: 1. Hindsight Action transitions: As explained previously, when a layer i−1 is unsuccessful 21 Chapter 3– Related Work Hierarchical Learning – 22 over several attempts in achieving a subgoal giproposed by layer i, but it achieves instead another goal g′ i, than, layer ireceives a transition that includes g′ ias the action. That is in practice, assuming that the lower level i−1 policy is optimal. 2. Hindsight Goal transitions: One of the states reached in hindsight is used as the goal state in the transition instead of the original goal. The most significant drawback of that approach is that level ican only learn Q-values for subgoal proposals (its actions in practice) that are relatively close to its current state and will ignore the Q-values for all subgoal actions that require more than H(horizon) actions. Another problematic phenomenon is that subgoal hierarchy ignores the lower level abilities, and so the output subgoals created might be suboptimal. To overcome this disadvantage, an approach for subgoal testing transitions is proposed. That is to help a subgoal layer to learn whether the subgoal it proposed is reachable within the horizon H steps of the lower level with its current policy. If it not reachable, the transition will contain a penalty of −H. Another algorithm called HIRO suggested in [18] to tackle the problem of non-stationarity, by off-policy correction. The approach is to relabel gtfor past high level policy experiences in order to make the observed action sequence more likely with the current lower level policy. Having at:t+c−1∼πlo(st:t+c−1, gt:t+c−1), the goal that should be stored is ˜gt:t+c−1, the one that maximizes πlo(at:t+c−1|st:t+c−1,˜gt:t+c−1) with the current low policy πlo out of 10 candidates. That is approximated by 3.5. Eight candidates are sampled from a Gaussian around st+c−st, while one candidate is always st+c−st, which is equal to gtif the algorithm performs correctly, and trivially, gtitself is the tenth and last candidate. logπlo(st:t+c−1,˜gt:t+c−1)∝ −1 2 t+c−1 X i=t ||ai−πlo(si,˜gi)||2 2+constant (3.5) The paper [19] presented by Wang et al. also tries to tackle the problem of nonstationarity of high-level training for decision making - AGILE (Adversarially Guided Subgoal Hierarchical Generation). The proposed approach is to adversarially enforce the high-level policy to generate subgoals that are in accordance with the momentary instantiation of the low-level policy. That aims to enhance high-level policy’s knowledge of the low-level’s ability. The generator is the high level policy that learns to generate subgoals following a compatible distribution with the current low-level policy. A discriminator network is used to distinguish a generated subgoal that may not be reachable by the low level policy from a relabeled subgoal that is known to be reachable. The framework proposed has 2 hierarchies. The high-level modulates the behaviour of the low-level policy by intrinsic rewards for reaching the generated subgoals. The high-level policy aims to maximise the extrinsic reward rh kt that is defined in 3.6. The low-level policy aims to maximise the intrinsic reward provided by the high-level policy, that is measure by subgoal reaching performance: rl t=−||st+gt−st+1||2. The architecture used is of TD3 for each of the two hierarchies. One objective of the subgoal generator is to maximize the expected return induced by a deterministic policy in 3.7. 22 Chapter 3– Related Work Hierarchical Learning – 23 rh t= t+k−1 X i=t renv i, t = 0,1,2, ... (3.6) Jdpg =Es∼D[Qh(s, g)|g=G(s;θg)] (3.7) The subgoal generation network g=G(s;θg) maps from state space to subgoal space (not sampled from random noise as in vanilla GAN). Dis the replay buffer with the high level action relabeled: gtof the high-level transition (st, gt,Σt+k−1 i=trenv i, st+k) is relabeled with ˜gtto maximise the probability of the created low-level sequence of actions: πl(at:t+k−1|st:t+k−1,˜gt:t+k−1). This probability is approximated by maximising the log probability in 3.8. logπl(at:t+k−1|st:t+k−1,˜gt:t+k−1)∝ −1 2 t+k−1 X i=t ||ai−πl(si,˜gi)||2 2(3.8) A major difficulty in HL is that higher levels should suggest effective subgoals, without actually knowing if they are reachable or not, since this information can be collected only by the lower level after having sufficient exploration and training. The papers [20], [21] by Zhang et al. present the algorithm HRAC, which tries to tackle this problem. The term ”Shortest transition distance” refers to the minimum number of steps needed to reach a target state from a start state. It can be achieved by minimising the expected first hit time over all possible policies. The high-level action space can be restricted from the whole goal space to a k-step adjacent region centred at the current state. The algorithm requires an Adjacency network training from Adjacency table: explicitly memorise the adjacency information by constructing a binary k-step adjacency matrix of the explored states. The adjacency matrix has the same size as the number of explored states, and each element represents whether two states are k-step adjacent. The adjacency network learns a mapping from the goal space to an adjacency space, where the Euclidean distance between the state and the goal is consistent with their shortest transition distance. Another interesting paper by Kim et al. presents the algorithm called HIGL [22], which is similar to HRAC but it evaluates both the reachability of states, and their novelty. The novelty score is higher for novel states dissimilar to the ones the predictor network has been trained on. The adjacency Network discriminates whether two states are k-steps adjacent or not. It learns a mapping from goal space to an adjacency space, by minimising the contrastive-like loss. Then it is possible to approximate the shortest transition distance. The algorithm does Landmark sampling: coverage based sampling and novelty based sampling. Coverage based sampling means to sample farthest points from a wide range of visited states from the Experience Replay. The distance is measured in the goal space as norm2. As for novelty-based sampling, they introduce a priority queue of a fixed size ordered by novelty. The novelty of a state decreases constantly, meaning it should be updated all along. previously sampled similar states are discarded. After Landmark sampling comes Landmark selection to detect the urgency of the landmark since not all the landmarks are helpful. First, build a graph of landmarks, then run the shortest path planning to a goal in a graph. Nodes in the graph consist of current 23 Chapter 3– Related Work Curriculum Learning – 24 state, a goal, and landmarks. Each edge is weighted with the distance that is estimated by low-level goal conditioned value function. When the calculated distance is too big, the edge is being discarded, since distance estimation via value function is only locally accurate. Value iteration is used as shortest path planning, and the first landmark is selected to be the goal. 3.4 Curriculum Learning Curriculum Learning (CL) aims to address the sampling inefficiency for off-policy methods problem to accelerate RL training procedure and for some cases to improve the results, by performing the experience acquisition in heuristic systematic manner than the random. The inspiration of CL is the fact that animals and humans learn better when the experience they see is ordered in a meaningful manner, that gradually encompasses more concepts, with increased levels of complexity. Bengio et al. claims in [23] that curriculum strategy can act like a continuation method, which helps to find a better local minima, and points out that curriculum strategy operates like a regularizer, as reported in experiments. For convex criteria curriculum strategy can speed-up the convergence to the global minimum. In an older paper 1993, Elman presents the notion of starting small [24] and makes the statement that this strategy enabled humans to learn what might otherwise prove to be unlearnable. One difference between HL and CL is that HL is built such that both agents learn different resolution of solution to the problem, and eventually in test time, the higher policy is part of the solution. On the other hand, CL might involve two agents so the one aims only to accelerate the learning of the actual agent, and the first does not form part of the ultimate solution in test time. Also sometimes the implementation of curriculum does not imply another agent, but the goals that are suggested, are characterised by some heuristics so the learning is accelerated. The suggested algorithms in this work combine the two ideas, and let both the agents learn in a curricular way. While in first years the focus of CL was mainly on constructing manually a sequence of tasks of increasing difficulty, in more recent papers the focus is on the automatic curriculum generation. A practical (automatic) curriculum learning method addresses training examples ordering and sampling modification based on the order. A typical guideline of curriculum algorithm would be: 1. Curriculum design. 2. Evaluation metric design - how easy or difficult the current target is? 3. Sequentially Increasing difficulty level tasks (training). A classic paper in the field of CL is [25] Teacher and Student Curriculum Learning (TSCL), where a teacher agent chooses automatically which task to give to the student which allows the student agent to learn gradually more complex tasks. At each time step the 24 Chapter 3– Related Work Curriculum Learning – 25 teacher selects a task from a list of possible tasks, the student trains on the task and returns a score. The goal of the teacher for the student to succeed in achieving the ultimate task goal. A big challenge is for the teacher to estimate the level of the student, to pick tasks in the right level of difficulty and balance the exploration exploitation trade-off. The problem is that the only learning signal the teacher has is from the noisy scores of the student, which makes it harder to track the learning curve of the student. To overcome this, three approaches are presented and tested: Firstly, the naive approach, where an average over K times the students tries to solve the problem, then use the regression coefficient of the learning curve as a reward in a non-stationary bandit algorithm. Secondly, FIFO buffer over last k scores, then again linear regression to estimate the slope of the learning curve for each task, with respect to time steps. While those two options require exploration hyper parameters tuning, the third option takes inspiration from Thompson sampling, where k last rewards for each task is kept in a buffer, then to choose the next task, a recent reward is sampled for each task, and whichever yields the highest reward gets selected. Another paper [26] aims to investigate the effect of the task distribution as a hyperparameters in the Gradient-based Meta-Learning framework. When the distribution contains a large variety of tasks, most likely an underfitting problem will occur, since the agents are incapable to specialise in neither of the tasks reaching a good performance. On the other hand, low variety might lead to poor generalisation. The random sampling of tasks can also harm the ability to learn, in cases where qualitatively different tasks are chosen. The idea is to address the problem of meta-overfitting by explicit optimization for task distribution. The proposed method is called Meta-ADR (Active Domain Randomization) and it was proposed by Mehta et al.. The algorithm, as can be visualised in figure 3.3, helps the agent to learn a curriculum of tasks, instead of uniformly sampling the given tasks set. A discriminator that was trained over pre-adaptation and post-adaptation sequences, is used to learn task difficulty, via rewards, which are used for the particles training. Intuitively ADR is optimised to find environments where the same policy results with different behaviour. Another interesting paper [27] by Held et al. presents GoalGAN - Automatic Goal Generation for Reinforcement Learning Agents, an adversarial training approach for subgoals generation, which are always in the appropriate difficulty of the agent, producing a curriculum. The method includes a dynamic modification of the probability distribution from which goals are sampled, which assures that the difficulty level of the generated goals is appropriate. The algorithm formulation directly motivates the agent to train on tasks that challenge its capabilities, which reflects the concept of Intrinsic Motivation. In addition, the algorithm is based on Skill-learning, which is an approach where an agent can reuse skill, an improvement over learning from scratch. The third idea that the algorithm is based on is Curriculum Learning. The algorithm uses an indicator function, with a tolerance and a distance metric, such 25 Chapter 3– Related Work Curriculum Learning – 26 Figure 3.3: Meta-ADR that when reaching a certain distance from the target within the Ttime steps limitation (horizon), it counts as 1, otherwise 0. It applies to problems with binary and sparse reward, which resembles real world problems. The goal space is continuous. They define an objective of equation 3.9, named Coverage function, which should to be optimised. The first step of the algorithm is goal labelling as Goals of Intermediate Difficulty (GOIDi) or not. GOIDiare goals that during iteration i, yield a long term return within a certain range of Rmin and Rmax, as described in 3.10. Goal sampling during training is then uniform over the set of GOIDi. In this way, the agent is trained with goals that will result in some reward, but has not yet been mastered (not receiving the maximum reward it can get). Rmin and Rmax can be seen as the minimum and maximum probability of reaching a goal in Ttime steps. The algorithm suggests to first estimate the label yg∈ {0,1}that indicates whether g∈GOIDifor all goals gused in the previous training iteration, then use these label to train a generative model from where goals sampling for the next iteration is possible. The label estimation is done by calculating the fraction of success out of all trajectories that contain gin the previous iteration. Then the result can be passed through 3.10 threshold to be labelled as 1 or 0. π∗(at|st, g) = arg min π Eg∼Pg(·)Rg(π) (3.9) GOIDi:= {g:Rmin ≤Rg(πi)≤Rmax} ⊆ g(3.10) The second component of the algorithm is Adversarial Goal generation, using Goal GAN.Goal GAN is a Generative Adversarial Networks with a modification that allows training with both positive examples and negative examples (factuals and counterfactuals). Negative examples mean they were sampled from a distribution that does not share support with the desired one. GANs also allow scaling to high dimensional goal spaces (such as images). The Goal Generator G(z) is trained to uniformly output goals from noise vector z, that are in GOIDi, 26 Chapter 3– Related Work Curriculum Learning – 27 using Goal Discriminator D(g). The optimization is done similar to Least-Squares GAN (LSGAN), with the modification for negative examples. Let us emphasize the a main difference between AGILE (the hierarchical adversarial algorithm that was presented under 3.3), with the recently presented Goal-GAN:Goal-GAN does not have a condition on the observation, instead, its generator stands alone. The GAN and the policy are separated and sequentially trained. AGILE generator on the other hand, is a substitute of the actor network, and policy update is performed directly through the adversarial loss and policy loss concurrently. 3.4.1 Reverse Curriculum Generation for Reinforcement Learning One way of automatic curriculum for sparse environments is Reverse Curriculum [28]. The algorithm suggests a framework where a robot is trained in “reverse”, from the goal backwards. In practice it means to reach the goal from a set of starting states that are increasingly far from the goal. Those ”promising” starting states are located around the target (or states that are similar to the goal state), which means it is easier and more probable to reach the target from them. When the agents master the task of reaching the goal from ”good starts”, it is now possible to spread more, and learn how to reach from states that are close to the ”good starts”, to the promising state. That can be seen in a way where the ”promising state” becomes the new goal, for other ”promising states”. In this way, gradually the agents learn to reach different goals (or states). This way of training assures that the given goals are reachable with intermediate difficulty. Intermediate difficulty for most cases is defined to be tasks that the agent has not mastered yet, but has at least some success. Reverse Curriculum Learning is expected to accelerate the learning since the agents should reach the target relatively fast, which grants him with high reward. That is a strong learning signal which is beneficial for the learning. This paper suggests a discrete-time finite-horizon MDP by a tuple M= (S,A, P, r, ρ0,T). Most of those were already explained in section 2. ρ0:S → R+is a start state distribution, rand Tare the reward function and the horizon respectively. The starting state distribution ρichanges in every learning iteration i, while evaluation is done on the uniform distribution of the states, as in the original problem. The general problem that is considered then is reaching goal space Sg⊂S from any start state S0⊂S. Having the reward a binary one in case reaching a state the belongs in Sg, implies that the return associated with every start state s0is the probability of reaching the goal in the T horizon limit. The suggested algorithm relies on 3 assumptions: 1. It is possible to resent the agent into any start state s0∈Sat the beginning of all trajectories. 2. At least one state sgis provided such that sg∈Sg. 3. The Markov Chain induced by taking uniformly sampled random actions has a communicating class including all start states S0and the given goal state sg. 27 Chapter 3– Related Work Curriculum Learning – 28 To find those ”good starts”, a procedure called SampleNearby is performed concurrently during the learning. The agent performs T(horizon) random actions from the goal state, which bring it to new states, in the vicinity of the goal state. Several different series of actions are done, so those states which the probability of reaching the goal from them is high, are collected to the list of good starts. Then the distribution of those good starts is updated with the newly found states. All those states visited during the rollouts are guaranteed to be feasible and can then be used as start states. The ”good start” list in the beginning contains only the goal state sg. The curriculum is expressed by the fact that the suggested starting states are uniformly sampled from that list. The algorithm selects only states where the expected return from them is between Rmin and Rmax, which assures those are not yet mastered but also feasible - not too hard and not too easy [29]. In theory, to calculate the expected return from them, it is needed to perform some trajectories from each of them, however to avoid this inefficiency, they use the trajectories collected by the policy training trajectories. Gradually, this region of ”good starts” grows, and hopefully covers all possible starting states in the problem. They showed that Brownian Motion from that ”good starts” list, performed way better than the option of only uniformly sampling from the state space. 28 Chapter 4 Algorithms 4.1 Motivation Reinforcement learning algorithms still have a lot of drawbacks that prevent them being widely used, as explained in chapter 1. The idea in this master thesis was to create an effective and efficient algorithm that will be able to solve complex environment tasks. An important work that has been done last year (2021) by the colleague Rafel Palliser Sans, presented the algorithm Learning Recursive Goal Proposal,LRGP. This algorithm was also meant to solve RL complex environment problems with Hierarchical Learning using two policy levels - high and low. The high policy aims to suggest meaningful subgoals in the way from a given state to a goal, so the low policy only has to learn short sub-trajectories between the suggested subgoals. The low level is the one that interacts with the environment exclusively, performing (primitive) actions, which result in the agent’s state changes. The actions of the high hierarchy are in practice the goals of the low hierarchy, and they are added to the goal stack in every proposal in First In First Out (FIFO) technique. The high agent keeps suggesting subgoals recursively as long as the current subgoal is not reachable by the low agent, and the limit of allowed subgoals does not exceed the high agent’s horizon. The reachability of a goal/subgoal is verified with is reachable set that stores the possible movements of the agent within the limit of the low horizon from past experience. The task of the algorithm is to empty the goal stack, meaning the episode’s ultimate goal was achieved (it is the last one to be erased from the stack). For sample efficiency and learning acceleration algorithm uses HER. LRGP showed relatively high performance and was able to outperform some State of the Art algorithms in the presented environments. However it had some points for improvements. One of the challenges is the incomplete space of the environments: some states are not feasible in the sense that the agent is not able to be in those. For more details regarding the environment, please refer to section 5.1. The high level of LRGP suffers from impossible subgoal suggestions, since it does not learn the environment directly. The incomplete space is handled by storing a set of all visited states as allowed subgoals for proposals. When the high policy suggests a subgoal that does not appear in this list, it will be eliminated and another attempt of the high policy to suggest an appropriate subgoal is done, while adding some 29 Chapter 4– Algorithms Reverse Curriculum Learning: Adjustments to the Hierarchical framework – 30 noise. In practice, when a suggested subgoal is not allowed it leads to recursively suggesting locations that are close to the original proposal until an acceptable one is proposed, where frequently several suggestions are needed until an allowed state is proposed as a subgoal. Another issue is that the success rate by the end of the learning process keeps oscillating around 0.89 success rate, meaning there still exist a gap to improve. That is further worsen when expanding the goal state dimensions to 3 dimensions, to be identical to the state space. In that case the performance of LRGP seems to degrade. For these reasons we aspired to offer a Hierarchical algorithm, that integrates several common component with LRGP (such as goal stack and is reachable set), while basing on other different concepts, that will allow higher success rate, while also avoiding the unfeasible subgoals proposals. To tackle those objectives we offer algorithms that adjust the idea of Reverse Curriculum Learning to Hierarchical learning. In this chapter we will present the integration of the Reverse Curriculum Learning idea in the hierarchical learning framework in our context. Then we will present the two main developed algorithms in this thesis: Reverse Curriculum Recursive Learning (RCRL) and Reverse Curriculum Vicinity Learning (RCVL). 4.2 Reverse Curriculum Learning: Adjustments to the Hierarchical framework Under section 3.4.1 we went through the idea suggested by Carlos Florensa et al. in [28] in details. In the next subsections two algorithms that combine this idea of Reverse Curriculum Learning with the idea of Hierarchical Learning are presented. Florensa in his work [28] proposes to maintain a list of ”good starts” which are state with high potential for success. Those are collected by sampling states nearby the goal state. If those states are reachable from the goal state, meaning that the goal is reachable from them in reversible environment. The subgoals are uniformly sampled from this set of ”good starts”. The curriculum is expressed by the difficulty to reach the goal from them, which is estimated by the return from them over number of experiences. The average in the binary reward environment is equal to the probability of success. Those with 0 return are too hard, while those with 1 mean that they are mastered already, too easy. This can be visualised as if it was the area around the goal that is being learned by the agent, gradually it expands, until hopefully the whole state space has been visited by the agent in mastering level. Those ”good starts” are in practice milestones along the way from the state to the goal, that divide the episode path into several mini-trajectories that are expected to be shorter than the original path required. The hierarchical architecture facilitates the learning of the low agent, by making it only the mini-trajectories. Shorter sequences to learn are easier 30 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 37 Figure 4.1: Reverse Curriculum Recursive Learning starting states list along an example episode. 4.5 Reverse Curriculum Vicinity Learning (RCVL) 4.5.1 The idea The general idea is that the high policy suggests possible subgoals, from the episode goal and backwards recursively until the suggestion is reachable to the agent. An example is shown in section 4.5.4. Here, similarly to LRGP we use the goal stack with First In First Out (FIFO) technique. The ultimate episode goal is the last one to be popped out and that is when a successful episode is finished. Trying to tackle the problem of unfeasible subgoals suggestion in incomplete environments, we want to suggest subgoals from a visited set of states that are located in the vicinity of the current target. We will refer to this list of sets as goal list. We collect those states during the concurrent training of the higher policy and lower policy, and possibly in another separated step of vicinity acquisition that is performed before the concurrent learning as a preliminary step. In this way we get to know the state (goal) space such that it is possible to compose trajectories from each state to any other state passing through common states (intersections) between two or more neighbourhoods as expressed in figure 4.2. The more we sample and explore and state space, the more options are available for subgoal suggestion, which implies that it is possible to get closer to the optimal solution. 37 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 38 Figure 4.2: Learned neighbourhoods in the state space. Every circle is a neighbourhood around a goal. It is possible to construct a path from state sto goal gpassing the common neighbours on the way. The neighbourhoods that participate are the blue circles, and the green dots are the states that form the whole path. 4.5.2 Algorithm flow An overview of the algorithm is presented in algorithm 4. The first step is vicinity preliminary acquisition (line 1), however it is not a mandatory phase step. Then we iterate number of episodes we define, such that in every episode the algorithm first tries to create the path for the lower level, by high level sugoal suggestion, and then when the high level path is complete, and the last subgoal proposal is reachable from the current state, then the low level gets into action and goes though the constructed path by the high level. In each episode we start with assigning 0 to the number of subgoals proposed (line 3). We get state and goal for the episode in lines 4-5. We start accumulating the high level steps in solution (line 6) and we stack the goal into goal stack (line7). Then we get into the while loop that allows recursively subgoals suggestion and finally low level steps that will go through the mini-trajectories. If the current goal is reachable from the current state within low horizon steps, then reachable gets True value. In addition we explore with a probability of decaying ϵ. If it is an exploration sub-trajectory then reachable is assigned True (line 10). In the case that the current goal is not reachable then it is needed to verify the number of suggested subgoals. In the case where more than high horizon (Hh)subgoals were proposed we break the while loop and the episode is terminated without success (lines 12-13). Otherwise, a new subgoal is suggested by the high policy and is stacked into goal stack in case it is legal and the subgoal count grows by one (legal is when the subgoal location is different than current state and current goal) (lines 15-17). In the other case, where reachable is True, the low level performs its Hlsteps in the environment trying to get to the current goal (lines 19-29). During the run, we store every step done with -1 reward in the low level ER (line 23). If we happen to achieve the goal (line 22) we pop out the current goal from goal stack and break the low run (lines 25-28). After the low level run we save current state to the solution (high level steps) (line 30). If the goal stack is empty it means that the ultimate episode goal was achieved, the episode is finished with success (lines 31-33). After every episode we roll out the solution to the vicinity, and then we create the tran38 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 39 Algorithm 4 Reverse Curriculum Vicinity Learning (RCVL) Require: high agent,low agent,is reachable(s,g) function, Hllow horizon, Hhhigh horizon, r radius for collection. 1: preliminary goal acquisition() - algorithm 7 2: for episode=1:num episodes do 3: num subgoals = 0 4: s←initial episode state 5: g←environment goal 6: solution ←[s] 7: goal stack ←[g] 8: while True do 9: g←goal stack[-1] 10: reachable ←is reachable(s, g) or exploration 11: if not reachable then 12: if num subgoals > Hhthen 13: Break. episode ends. 14: end if 15: new ss ←high.subgoal suggestion(s, g) - algorithm 6 16: num subgoals += 1 17: goal stack.append(new ss) 18: else 19: for low steps = 1:Hldo 20: a←low.select action(s, g) 21: Apply action a and observe next state s’ 22: achieved = (s’ == g) 23: store in low.experience replay the tuple (s, a, achieved-1, s’) 24: s←s′ 25: if achieved then 26: Remove g from goal stack 27: Break for loop 28: end if 29: end for 30: solution.append(s) and high.store(first state and last state of low run). 31: if len(goal stack) == 0 then 32: episode is completed, break 33: end if 34: end if 35: end while 36: high.solution to vicinity(solution, r) - algorithm 5 37: HER on low policy and high policy 38: Every n episodes: Update networks 39: end for 39 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 40 sitions with HER. Every n episodes we update all the networks (lines 36-38). 4.5.3 Algorithm main components •Vicinity acquisition The vicinity acquisition is performed during the preliminary acquisition, if done, and during the concurrent learning of the high level and low level. For the vicinity acquisition during the concurrent learning we collect the ”high level steps” that are visited during the episode in solution list (lines 6 and 30 in the complete algorithm 4), and then we roll it out to store the data in goal list. More details regarding goal list structure are in appendix A. By ”high level steps” we refer to the states that are visited every completion of low horizon steps. When rolling out this solution (solution to vicinity() in line 36 in the complete algorithm 4, see algorithm 5), we have several settings to take into consideration. First, the Radius of vicinity: how distant the collected states from the sampled goal in terms of low horizons. It can vary between one low horizon, meaning the distance is feasible within one low horizon, to several horizons, when the maximum chosen was 6. Another decision that needed to be investigated was whether to store each trajectory in the order it was collected or symmetrically. For example if the agent went from state s1low horizon of steps till state s2, we store that s1is a possible subgoal on the way to s2, but should we also store that s2can be a possible subgoal on the way to s1. Algorithm 5 solution to vicinity Require: high agent, solution, r radius for collection, symmetry flag 1: solution.reverse() 2: for i = 1:len(solution) do 3: for j=i+1:i+r+1 do 4: index = convert 2 dimensional solution[i] to 1 dimensional index 5: high/goal list[index].add(solution[j]) 6: if symmetry flag then index = convert 2 dimensional solution[j] to 1 dimensional index 7: high/goal list[index].add(solution[i]) 8: end if 9: end for 10: end for •Subgoal suggestion When the high level suggests a goal (line 14, see algorithm 6), it uses the value function approximation to calculate the possible values of the different possible paths. Every path is composed of two parts: one is from current state to the current subgoal, and second is from the subgoal to the next subgoal/goal. To visualise an example of this 40 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 41 please refer to figure 4.3. We can see the steps how the algorithm finds the more rewarding path to go through. This example is for a simple case, where obstacles do not exist, and the distance goes with opposite relation with the reward: the shorter it is, the more rewarding it is. For example in 4.3(a) we have 5 optional subgoals from goal list for the current goal, and we calculate all of the following: –Q(path1) = Q(s, sg1, g) –Q(path2) = Q(s, sg2, g) –Q(path3) = Q(s, sg3, g) –Q(path4) = Q(s, sg4, g) –Q(path5) = Q(s, sg5, g) The suggested subgoal will be the one that draws the path with the maximum value estimation. In this case, if the value function is close to the real value, we expect the subgoal sg5to be selected. This process is done recursively until a suggested subgoal is reachable from the current state and the low agent starts to act. it should cross the way that is presented in 4.3(e). If in any of the intermediate subgoals, again one is not reachable, then another suggestion from the high level can be made in the same way, until the low subgoal is reachable from the current state. Algorithm 6 subgoal suggestion Require: high agent,gcurrent target, scurrent state. 1: index = convert 2 dimensional goal to 1 dimensional index 2: Possible actions ←high agent.goal list[index] 3: Broadcast sand gto dimensions of Possible actions 4: Calculate Q value(sbroadcast, P ossible actions, gbroadcast) 5: Choose the action that maximizes Q value •Preliminary vicinity acquisition. In the case where we perform the vicinity collection also as a separated step, see algorithm 7, in practice we perform some goal sampling before we start the concurrent learning. In this phase of the algorithm we uniformly sample the goal space (which is the same as the state space). For each sample we initialise the environment, receiving a state and a goal. We perform primitive steps using the ϵ-greedy low policy trying to reach from the state to the goal. We perform a low horizon of steps and then set the original goal to be the state. That means that we go approximately to the same direction we came from, but not exactly since we also explore with probability of ϵ, see figure 4.4 (this technique is compared to a flatten acquisition in section 5.2.3). We store the first state, and then we store the visited state every low horizon steps. That 41 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 42 (a) Step 1: Evaluate the benefit (value approximation) of passing from state s to goal gthrough the possible subgoals {sg1, sg2, sg3, sg4, sg5}. (b) Step 2: The path through subgoal sg5is the most rewarding, so it is now set as the goal, and the same process of evaluating the subgoals around it are done. (c) Step 3: Subgoal sg7is detected as the most rewarding subgoal among the possibilities. The same process is repeated for the vicinity of sg7. (d) Step 4: Subgoal sg8is detected as the most rewarding subgoal among the possibilities. The same process is repeated for the vicinity of sg8 (e) Step 5: Finally subgoal sg11 is reachable from the current state s, and we can see the revealed path that the algorithm suggested to cross the way from sto g. Figure 4.3: A simple example of subgoal suggestions from learned vicinity of each of the goals/subgoals. The path is expected to get better as the value function approximator gets closer to the real value function, and as the agent learns the neighborhoods better. 42 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 43 is the equal to a single ”step” of the high policy. That is the same as in the case of the concurrent learning phase acquisition. This phase also integrates low policy training, which was decided after experimenting the consequences of it on the algorithm learning. Details regarding the this experimentation is brought under section 5.2.2. Figure 4.4: Preliminary vicinity acquisition with ”back and forth” technique. (1) First we have state sand goal g, and the low agent tries to reach the goal applying ϵ-greedy policy. It ends a horizon of primitive actions in state s′. (2) Now the original state is set to be the goal g, while s′becomes s.gis no longer important, and we keep on sampling around the states that we are. Having ϵ-greedy policy, after a low horizon of primitive goals, the agent ends up in s′. (3) Again the process repeats itself, and we end up in a new but relatively close state. The vicinity has the following possible properties that need to be tuned and set, in addition to the radius of the vicinity and symmetrical acquisition explained above: 1. Sample size: How many times to initialise the environment and perform the process of acquisition. 2. Back and forward or flatten collection: The agents performs low horizon steps then the goal can be updated to be the initial one, so the agent is expected to back, however, not exactly, since we use the ϵ-greedy policy of the low agent. Another option, instead is to leave the goal the same for all the repetitions, so that we perform mini trajectories on the way to the same goal. For visualisation please refer to 4.4. 3. Number of repetitions: how many of the mini-trajectories described above (back and forth or ”flattened” path) the agent performs. 43 Chapter 4– Algorithms Reverse Curriculum Vicinity Learning (RCVL) – 44 Algorithm 7 preliminary vicinity acquisition Require: low agent,high agent n samples, n repetitions, flatten flag, Hl, r radius for collection 1: for i = 1:n samples do 2: s, g ←environment initialization solution.append(s) 3: for j=1:n repetitions do last state = run low steps(low agent, hl, s, g) 4: if Not flatten flag then: 5: g←last state 6: end if 7: s = last state 8: solution.append(s) 9: HER on low agent accumulated states. 10: end for 11: high agent.solution to vicinity(solution, r) - algorithm 5 12: end for 4.5.4 Learning Recursive Goal Proposal by value estimation We have also investigated the option of using the value approximations of the network to be stored in the ER as reward as explained in the second approach for long-term reward estimation in 4.3.3. The process of collecting and learning the neighbourhoods is done in a similar way to the other approach, and also in the way of suggesting subgoals. For suggesting subgoals (action selection of the high policy) the algorithm goes through all the possible states that are in the list corresponding to the current goal, and calculates which is the most rewarding path to go from state sto goal gthrough. The one that has the maximum value (or minimum cost) will be chosen as a subgoal, and will be suggested as the next goal for the low policy. The major difference of storing the estimations in the ER as explained in the seconds approach, makes the learning way more complicated, since there is nothing empirical that is fed into the reward estimations. In the beginning of the learning, the suggested subgoals are expected to be random, however with time, assuming the value estimators are converging to their true value, they are expected to be relevant. After several experiments, we reasoned that maybe there is no learning since the random initialization results with low estimation for the value. We decided then to test several different initializations of the last value NN layer bias that were expected to encourage learning. That also resulted in failure to learn. The possible reason for the failure is that we have combined three characteristics: Function approximation, bootstrapping and off-policy learning. Those three properties integrated together might lead to divergence of the algorithm. 44 Chapter 5 Experiments and Results The most relevant experiments performed in this work will be presented in this section. First the environments used will be presented, then some preliminary experiments, and finally performance comparison with State of the Art and Baseline. The preliminary studies that are documented are the ones that are related to the RCVL algorithm, the successful one. Similar studies for hyperparameters were done also with RCRL however when it did not demonstrate proper learning, it became redundant to document and conclude regarding it. Even though, in the final comparison, the performance of the two algorithms is presented and discussed. The implementation details for both algorithms appear in appendix A. The default values are as appears in the appendix, unless said otherwise. In the preliminary studies and experiments, the default values are used, and only a single variable, currently characterised parameter, changes. 5.1 Environments 5.1.1 Minigrid Empty room Minigrid empty room [31] is a mxn grid table, which is a simplified version of Gym MiniGrid [32] as appears in figure 5.1. The green arrow represents the agent while the black tile is the episode goal. When new starting states/subgoal is suggested they appear in different red - orange gradient as appears in figure 5.1(b). The state space contains all the position on the board plus a direction: (x,y,dir). The possible values for x are 0 to m-1 and for y are 0 to n-1 according to grid width and height. The possible values for the directions are 0-3: right, down left and up. The action space contains three actions: turn left (0), turn right (1), and move forward (2). The original goal space had only (x,y) location property. As explained in the previous chapter, the algorithm proposed also learns the directions for goal states. In that way the learning is more specific, and the state space,goal space are the same as the high policy action space. The mapping from state to goal is not longer needed. 45 Chapter 5– Experiments and Results Environments – 46 (a) Empty room, target and goal visualization (b) Empty room: state, target with subgoals Figure 5.1: Empty room example To allow implementing algorithm of the Hierarchical Reverse Curriculum Learning 4.4, the ability of positioning the agent in a desired location was needed to meet the first assumption that in that paper [28]. The reward function is sparse, meaning only when the agent reaches the episode goal, it receives 0, and otherwise it receives -1 for every step. Let up express the above formally: •S={0,1,2..., m −1}×{0,1,2..., n −1}× {Right,Down,Left,Up}. •G={0,1,2..., m −1}×{0,1,2..., n −1}× {Right, Down, Left, Up}. •A={turn left, turn right, step forward}. •R={−1,0} 5.1.2 Four Rooms MiniGrid The environment is built of mxn grid table, as in the empty room, but it is divided by walls into four rooms, and it is possible to move from one room to an adjacent room via one tile [32]. Each tile (state) in this grid world might be either free, meaning the agent can be in it, or it is a wall, meaning it is an impossible state for the agent. That means that the agent needs to learn to align to this ”key” tiles, and perform a ”forward” action to move to another room. An example of environment with 15x15 tiles can be visualised in Figure 5.2: 46 Chapter 5– Experiments and Results Preliminary experiments - Hyperparameters search – 53 preliminary acquisition phase, if done, and during the concurrent learning phase. Figure 5.8a presents the mean accumulated number of states in the vicinity along with the preliminary acquisition. It is possible to see that the accumulation is very fast in the beginning and becomes slower, however it stays relatively significant all along the acquisition. Then the effect of different amount of preliminary acquisitions (samples of goals) on the accumulation of vicinity size during the concurrent learning is presented in figure 5.8b. It is clearly seen that the more preliminary acquisition is done, the knowledge about the vicinity is larger (more states are collected for each goal). This is further emphasized in the mean final neighborhood size in table 5.3. The concurrent learning does not compensate for the vicinity size by the end of the concurrent learning. However the rhythm (mean derivative function of the accumulation function) of accumulation is greater as the preliminary learning is smaller: 0.035 and 0.015 respectively, which is 60% slower. That makes sense with same reason that the rhythm of accumulation during the preliminary acquisition gets smaller as more knowledge was already collected. The possible reason is that we accumulate already known neighbors, so they contribute less to enlarge the known neighborhood. In addition the lower level is more successful, and less explores, then the collected states are already known, not new. The effect of the sampling size during preliminary acquisition on the algorithm success rate is presented in 5.8c. We can see that asymptotically the different setups converge to similar success rate, although the preliminary acquisition shows its contribution in accelerating the learning, reaching to better success rates faster. For further inspection the low level success rate is presented in 5.8d. Having the low level more successful of course enables the performance of the algorithm as a whole. It does not assure the whole algorithm success, but without its success, it is impossible the algorithm as a whole will be successful. It is an essential condition, but not sufficient. Also, for the low level success, the different setups converge to similar success rates. Further discussion regarding the trends in low policy success rate for this algorithm will be discussed under section 6.2.1. 53 Chapter 5– Experiments and Results Preliminary experiments - Hyperparameters search – 54 (a) Vicinity size in preliminary acquisition. (b) Vicinity size during the concurrent learning, having different sampling size in preliminary acquisition. (c) Algorithm success rate according the sampling size in preliminary acquisition. (d) Low level success rate according the sampling size in preliminary acquisition. Figure 5.8: Minigrid FourRooms 15x15: Vicinity size (in terms of number of states) characterization along learning when setting different number of goals to sample during preliminary acquisition. Sampling Number in preliminary acquisition Final mean vicinity size [number of neighbors] Mean accumulation rhythm 078.7 0.035 1,000 79.7 0.0349 5,000 88.515 0.02 10,000 93.61 0.0199 20,000 96.77 0.015 Table 5.3: Neighbors accumulation with different preliminary acquisition sampling number. 54 Chapter 5– Experiments and Results Preliminary experiments - Hyperparameters search – 55 5.3.2.1 Runtime implication of preliminary acquisition The preliminary acquisition in is practice performing interaction with the environment, which might diverse in the time addition when changing its parameters such as low horizon, number of repetitions, number of goals to sample and so on. Calculating on sampling size of 20,000 in the preliminary acquisition with several different parameters, the addition time required for the preliminary acquisition ranges between 4% to 7% from the concurrent time learning, depending on the acquisition hyper parameters. This is not a big addition given that those are only short sampling rounds of mini-trajectories (not as in the concurrent learning, where we have in each episode high horizon of mini-trajectories), and there is no large complexity while doing that. 5.3.3 Back and forth while preliminary acquisition: number of repetitions When acquiring the samples of the vicinity, as explained, after the agents performs horizon primitive actions, we try to make the agent to repeat its steps back with the ϵ-greedy policy. The number of repetitions on that process might affect on both the learning phases of the low policy (assuming low policy training during goal acquisition and during concurrent learning). We have performed a study to characterize the effect of repetition number, executing the experiment with a reasonable sample size of 5,000 in the preliminary acquisition, and different number of repetitions ranging between 1 and 8. Representative results are shown in figure 5.9. The results are very similar for low policy. With one and only repetition low policy starts with lower success rate. In comparison, with 3 or 8 repetition it starts higher. However 8 repetitions do not seem to contribute much over 5 repetitions. As for the algorithm as a whole, 5 repetition contributed a bit, while 8 repetition results with similar success rate. A reasonable decision is then to stay with 5 repetitions of back and forth during the preliminary acquisition. 55 Chapter 5– Experiments and Results Preliminary experiments - Hyperparameters search – 56 (a) Algorithm success rate (b) Low level success rate Figure 5.9: Minigrid FourRooms 15x15: Back and forth repetitions during preliminary goal acquisition. 5.3.4 Low level horizon effect We have tested the effect of different low horizon on the training, and the results appear in figure 5.10. The most successful choice appears to be a horizon of 4. Horizon of 6 results with similar success rate as 4 for the algorithm as whole, but the low level success shows a clear advantage of 4 over 6. The low level success that increases very fast for the shorter low horizon, allows the high level to prosper accordingly. This is a very important parameter since as we see, the results do not converge to the same value even after 50,000 episodes. (a) Algorithm success rate (b) Low level success rate Figure 5.10: Minigrid FourRooms 15x15: Low horizon success rate effect on the learning 5.3.5 High level horizon effect Another important hyperparameter for final behavior is the maximum number of subgoals that are allowed to be proposed during an episode, that is the high level horizon. The char56 Chapter 5– Experiments and Results Preliminary experiments - Hyperparameters search – 57 acterization of its effect is presented in figure 5.11. The idea is to choose a minimal number of subgoals, as long as it does not harm the performance. The reason is simple: less subgoals with the same low horizon means less primitive steps. If we converge with an increasing amount of subgoals to the same success rate approximately, it means that there are redundant subogals. That is why the better choice would be the minimum subgoals with maximum success rate. Observing the results it is clear that horizon of 5 is too low. Similarly horizon of 8 also seems suboptimal. It is sufficient for most cases but it fails to be enough in some setup of state and goal. That is why it does not converge to the same as the others. On the other hand 15 and 20 behave very similar , which implies we might see redundant subgoals for 20, that makes the agents path longer. A good choice for the high horizon in that case would be then 15. (a) Algorithm success rate (b) Low level success rate Figure 5.11: Minigrid FourRooms 15x15: High horizon success rate effect on the learning 57 Chapter 5– Experiments and Results Comparison with State of the Art and baseline – 58 5.4 Comparison with State of the Art and baseline The following sections present the comparison of the proposed algorithms with the baselines. As for RCVL, all the presented results are without preliminary acquisition, meaning this is the ”worst” behavior with the algorithm. With the addition of preliminary acquisition the learning curves for RCVL are better. The rest of the parameters are brought in appendix A. 5.4.1 Minigrid empty room It is possible to visualize the learning process of the proposed algorithms: RCRL,RCVL in figure 5.12a, in comparison with LRGP (formerly proposed baseline) and State of the Art algorithms: DDQN and DDQN combined with HER. Observing the success rate of the different algorithms, we can see that RCVL performs similar to the LRGP and to DDQN with HER, reaching close to 1. RCRL fails to learn well the environment, reaching around 0.5 success rate. As for the low level success, figure 5.12b, the three algorithms compared show similar learning curves. To show the optimality of the paths drawn by the high level of RCVL, let us observe the average number of steps per episode. DDQN and its variation with HER learn the optimal behaviour (at least close to optimal) in the empty room (it was tested by observing it in action). Also, for the simpler environment we expect DDQN to master the tasks. That is, good performance of the tested algorithms will results with similar number of steps per episode. To evaluate this we ran 1,000 episodes with random initialization in the Minigrid Empty Room 15x15 environment, and calculated the average number of states across all of them for episode completion. Recall that the success rate of all the algorithms is close to 1, which makes the comparison valid. Otherwise unsuccessful episodes of one or another might bias the average, since the unsuccessful episodes are expected to be longer ones. Both scenarios of taking them into account or ignore them results with some bias. Please refer to table 5.4 to observe the results. We can see that the optimal (shortest) path is done by DDQN with an average of 12.72 steps. RCVL testing resulted in 13.76, which is 8.1% more. We can understand that on average RCVL results with a path that has one step that is redundant. This can be the result of hierarchical learning, which is not needed in such a simple environment. The fact that LRGP resulted with an even higher number of average steps (17.04 which are 34% more than DDQN), supports this reasoning. Overall it is safe to say that the solution of RCVL is close to optimal with 1 step difference. 58 Chapter 5– Experiments and Results Comparison with State of the Art and baseline – 59 (a) Algorithm success rate: learning process of the proposed algorithms compared to the baseline (LRGP) and the state of the art (DDQN and DDQN+HER). (b) Low level success rate: learning process of the proposed algorithms compared to the baseline LRGP. Figure 5.12: Minigrid Empty room 15x15: learning process of the proposed algorithms compared to the baseline LRGP and the state of the art: DDQN and DDQN+HER. 59 Chapter 5– Experiments and Results Comparison with State of the Art and baseline – 60 Algorithm Average steps per episode DDQN 12.72 DDQN + HER 12.86 LRGP 17.04 RCVL (ours) 13.76 Table 5.4: Minigrid Empty Room 15x15: Average number of subgoals per episode calculated across 1,000 episodes with random initialization. 5.4.2 Minigrid FourRooms environment 5.4.2.1 Success rates In figure 5.13 It is possible to visualize the comparison of the proposed algorithms to the baseline LRGP and State of the Art algorithms DDQN, DDQN combined with HER. Additionally, Some numerical results are presented in table 5.5. The presented mean success rates are calculated over 500 last episodes in the scope mentioned (last 500 episodes reaching to 25,000 episodes and so on). Then a 1,000 episodes with random initialization was performed, and the mean across all those 1,000 is presented in the table. RCVL outperformed the rest of the algorithms during learning and during test. It is possible to see that the baseline algorithms struggle a lot solving the problem, having DDQN reaching no more than 0.23 of success, and DDQN with HER succeed a bit more reaching up to 44%, while RCVL reaches close around 0.97 success rate.RCVL outperforms LRPG, having it around 0.8 success. Observing the low level performance during learning shown in figure 5.14, RCVL expresses similar learning to the baseline. Thirdly, as presented under section 5.3.2, addition of Preliminary Acquisition could accelerate the low level learning, leading to even faster convergence of the algorithm. 60 Chapter 5– Experiments and Results Comparison with State of the Art and baseline – 61 Figure 5.13: Minigrid Four rooms 15x15: Algorithm success rate comparison of the proposed algorithms with baseline LRGP and State of the Art: DDQN and DDQN+HER Figure 5.14: Minigrid Four rooms 15x15: Low policy success rate comparison of the proposed algorithms with baseline LRGP and State of the Art: DDQN and DDQN+HER 61 Chapter 5– Experiments and Results Comparison with State of the Art and baseline – 62 Algorithm Mean success rate after 25,000 episodes Mean success rate after 50,000 episodes success rate: Test over 1000 cases DDQN 0.1 0.22 0.23 DDQN + HER 0.22 0.44 0.44 LRGP 0.72 0.8 0.85 RCVL (ours) 0.96 0.97 0.98 Table 5.5: Minigrid FourRooms: Comparison of the suggested algorithm with baseline LRGP and State of the Art algorithms. 5.4.2.2 Subgoals proposals For further comparison it is possible to observe the number of subgoals suggested along learning, having equal low low horizon of 4 (otherwise the suggested subgoals would not be representative for anything). Figure 5.15 presents the results. It is easy to see the the number of subgoals proposed is lower and steadier (smaller amplitudes) for the proposed algorithm RCVL over the baseline LRGP. Figure 5.15: Minigrid FourRooms 15x15: Number of subogals proposal during learning for both algorithms LRGP, and RCVL (ours) 5.4.2.3 Path optimality In the following examples in figure 5.20 it is possible to visualize the path drawn by the high level. The paths seem to be very direct and do not express redundancy. 62 Chapter 6– Conclusions and Future Work Reverse Curriculum Vicinity Learning (RCVL) – 69 rest of parameters such as low horizon, high horizon, learning rate, network architecture, we end up trying to optimise in an overly expanded multi-dimensional space. Applying the algorithm in other environments will require this heavy experimentation. However, the algorithm demonstrates that in the long run with sufficient episodes, the preliminary acquisition parameters do not result in big differences. That means that the algorithm is robust to the parameters selection for the preliminary acquisition. The parameters that seem to have the major effect are the horizons of both low policy and high policy. The fact that the low horizon of 4 has shown the best performance proves that learning small tasks is helpful, expressing the exact purpose of the hierarchical learning. It shows that the algorithm benefits from the hierarchy. The is reachable set and the goal list are key players in the algorithm. The ”decision” of who is the next one to act - the high level or the low level, depends on the knowledge accumulated in is reachable exclusively. In addition, the goal list, should be diverse enough and to cover as much of the goal state as possible, since all the subgoal suggestions come from there (except the times where the current goal was never visited, and we ask the explicit policy representation for a suggestion). The fact that those two lists are needed for a good performance of the algorithm might harden the generalizability of the algorithm in more complex environments. With that said, thanks to the goal list we avoid the unfeasible states suggestion problem, which makes it very important component. In Minigrid Empty Room 15x15, the simpler environment tested, RCVL showed similar performance to the State of the Art algorithms of DDQN and DDQN combined with HER. In Minigrid FourRooms 15x15, which is the more complex environment (with obstacles) we aimed to solve, RCVL has shown superiority over DDQN,DDQN with HER and the baseline LRGP. It has shown faster learning, and efficient subgoals proposing converging to a success rate of approximately 0.975. The paths the algorithm chooses are close to optimal, verifying observing it in action. Recall that this thesis aimed to propose an algorithm for solving complex problems, which is why a minor path suboptimality below State of the Art (though same success rate) in the simple environment is acceptable, as long as in complex environments, it stands out with superior performance. One major drawback is that it will be hard to apply in continuous environments. The algorithm was built to solve discrete environments, but it will have a problem to generalise to the continuous case. It will require some kind of quantization of the state/action/goal space, or other metrics for distance evaluation. To conclude, the new suggested algorithm RCVL was able to outperform State of the Art methods and the baseline LRGP algorithm in the more complex environment. It manages to solve the problem of unfeasible subgoals suggestion, and reaches an incredibly high success rate. In addition, the paths drawn by the high level seem to be close to optimal when observing it in action. Furthermore, It has shown to have robustness to changes in a lot of the parameters, making it more reliable. 69 Chapter 6– Conclusions and Future Work Reverse Curriculum Vicinity Learning (RCVL) – 70 6.2.2 Future work First of all, the algorithm should be tested on new and more complex environments, to demonstrate its generalizability, to make sure the high performance is not for the specific problem we solve with the mini grid world. Secondly, to expand the algorithm to the continuous space. To apply the algorithm in acontinuous environment, one option is to discretize the state space. That raises the need to come up with a generalizable framework for environment discretization, with minimal harm to the problem resolution. It should be a modular addition, such that there is no need to change the environment itself. It seems like a complicated task, and hard to make in a generalizable manner, since it is most probable that each continuous environment will require different adaptations. Another option is to save the continuous states as we do with the discrete environment, but to use some metric to estimate the proximity to them when needed. That metric can also be learned/estimated. A possible suggestion to overcome the limitation of goal list and is reachable is to approximate those by a neural network, specifically GAN, having the generator generating states in the vicinity of a goal, while the discriminator learning to differentiate if a suggested state is in the vicinity or not and feasible or not. The collected experience can be divided into factuals and counterfactuals to train the discriminator. However to create the pool for factuals will be a lot easier than to create the counterfactuals pool in the aspect of reachability. We can only collect states that were visited, but we can’t collect those that are not feasible. We can try to collect the cases where the low level performs a forward step but stays in the same location. Then some kind of generalizable estimation of which is the state that we are trying to get but can’t, should be done, so we can use this state as a counterfactual for feasibility. To make the process even more curricular, instead of suggesting the lowest cost subgoal, it can be a state within thresholds (Qmin, Qmax), such that the suggested subgoals are always in intermediate level of difficulty, since they have not been mastered yet, however still result with more than a minimal value. That is more similar to the original suggestion of the Reverse Curriculum idea. The challenge in that case would be to set the thresholds for intermediate proficiency level of the lower level. 70 Bibliography [1] Hado Van Hasselt, Arthur Guez, and David Silver. “Deep reinforcement learning with double q-learning”. In: Proceedings of the AAAI conference on artificial intelligence. Vol. 30. 1. 2016. [2] Marcin Andrychowicz et al. “Hindsight experience replay”. In: arXiv preprint arXiv:1707.01495 (2017). [3] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. [4] Mario Martin. Lecture notes in Reinforcement Learning Course. Mar. 2020. url:https: //www.cs.upc.edu/~mmartin/ATCI-RL.html. [5] Shweta Bhatt. Reinforcement Learning 101 - Learn the essentials of Reinforcement Learning! url:https://towardsdatascience.com/reinforcement-learning-101e24b50e1d292. (accessed: 13.05.2022). [6] Ajitesh Kumar. Reinforcement Learning Real-world examples.url:https://vitalflux. com/reinforcement-learning-real-world-examples/. (accessed: 12.05.2022). [7] Tom Schaul et al. “Universal Value Function Approximators”. In: Proceedings of the 32nd International Conference on Machine Learning. Ed. by Francis Bach and David Blei. Vol. 37. Proceedings of Machine Learning Research. Lille, France: PMLR, July 2015, pp. 1312–1320. url:https://proceedings.mlr.press/v37/schaul15.html. [8] RAM SAGAR. What Is Model-Free Reinforcement Learning? url:https://analyticsindiamag. com/whatismodelfree - reinforcementlearning/#:~:text =%5C%E2%5C% 80%5C%9CModel%5C%2Dbased%5C%20methods%5C%20rely%5C%20on,methods%5C% 20primarily%5C%20rely%5C%20on%5C%20learning.%5C%E2%5C%80%5C%9D&text= In%5C%20the%5C%20context%5C%20of%5C%20reinforcement,be%5C%20made%5C% 20about%5C%20the%5C%20environment.. (accessed: 13.05.2022). [9] OpenAI. Spinning Up in Deep RL! url:https://spinningup.openai.com/en/ latest/spinningup/rl_intro.html. (accessed: 24.05.2022). [10] Volodymyr Mnih et al. “Human-level control through deep reinforcement learning”. In: nature 518.7540 (2015), pp. 529–533. [11] Chris Yoon. Towards Data Science: Double Deep Q Networks.url:https://towardsdatascience. com/double-deep-q-networks-905dd8325412. (accessed: 02.06.2022). [12] Timothy P Lillicrap et al. “Continuous control with deep reinforcement learning”. In: arXiv preprint arXiv:1509.02971 (2015). 71 Chapter 6– BIBLIOGRAPHY BIBLIOGRAPHY – 72 [13] Scott Fujimoto, Herke Hoof, and David Meger. “Addressing function approximation error in actor-critic methods”. In: International conference on machine learning. PMLR. 2018, pp. 1587–1596. [14] Tuomas Haarnoja et al. “Soft actor-critic algorithms and applications”. In: arXiv preprint arXiv:1812.05905 (2018). [15] OpenAI. OpenAI Spinning Up: Soft Actor Critic.url:https://spinningup.openai. com/en/latest/algorithms/sac.html. (accessed: 04.06.2022). [16] Andrew Levy, Robert Platt, and Kate Saenko. “Hierarchical actor-critic”. In: arXiv preprint arXiv:1712.00948 12 (2017). [17] Andrew Levy et al. “Learning multi-level hierarchies with hindsight”. In: arXiv preprint arXiv:1712.00948 (2017). [18] Ofir Nachum et al. “Data-Efficient Hierarchical Reinforcement Learning”. In: Advances in Neural Information Processing Systems. Ed. by S. Bengio et al. Vol. 31. Curran Associates, Inc., 2018. url:https://proceedings.neurips.cc/paper/2018/file/ e6384711491713d29bc63fc5eeb5ba4f-Paper.pdf. [19] Vivienne Huiling Wang et al. “Adversarially Guided Subgoal Generation for Hierarchical Reinforcement Learning”. In: arXiv preprint arXiv:2201.09635 (2022). [20] Tianren Zhang et al. Generating adjacency-constrained subgoals in hierarchical reinforcement learning. Tech. rep. 2020. arXiv: 2006.11485.url:https://github.com/ trzhang0116/HRAC.. [21] Tianren Zhang et al. “Adjacency constraint for efficient hierarchical reinforcement learning”. In: (2021). arXiv: 2111.00213.url:http://arxiv.org/abs/2111.00213. [22] Junsu Kim, Younggyo Seo, and Jinwoo Shin. “Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning”. In: NeurIPS (2021), pp. 1–14. arXiv: 2110. 13625.url:http://arxiv.org/abs/2110.13625. [23] Yoshua Bengio et al. “Curriculum learning”. In: Proceedings of the 26th annual international conference on machine learning. 2009, pp. 41–48. [24] Jeffrey L. Elman. “Learning and development in neural networks: the importance of starting small”. In: Cognition 48.1 (1993), pp. 71–99. issn: 0010-0277. doi:https: //doi.org/10.1016/0010-0277(93)90058-4.url:https://www.sciencedirect. com/science/article/pii/0010027793900584. [25] Tambet Matiisen et al. “Teacher–student curriculum learning”. In: IEEE transactions on neural networks and learning systems 31.9 (2019), pp. 3732–3740. [26] Bhairav Mehta et al. “Curriculum in gradient-based meta-reinforcement learning”. In: arXiv preprint arXiv:2002.07956 (2020). [27] David Held et al. “Automatic goal generation for reinforcement learning agents”. In: (2018). [28] Carlos Florensa et al. “Reverse Curriculum Generation for Reinforcement Learning”. In: CoRL (2017), pp. 1–14. arXiv: 1707.05300.url:http://arxiv.org/abs/1707. 05300. 72 Chapter – BIBLIOGRAPHY BIBLIOGRAPHY – 73 [29] Carlos Florensa. Reverse Curriculum Generation for Reinforcement Learning Agents. url:https: // bair. berkeley. edu/ blog/ 2017/ 12/ 20/ reversecurriculum/. (accessed: 20.05.2022). [30] Rafel Palliser Sans. Learning recursive goal proposal: a hierarchical reinforcement learning approach.url:https://upcommons.upc.edu/handle/2117/348422. (accessed: 10.06.2022). [31] Rafel Palliser Sans. gym-simple-minigrid.url:https://github.com/rafelps/gymsimple-minigrid. (accessed: 06.06.2022). [32] Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic Gridworld Environment for OpenAI Gym.https://github.com/maximecb/gym-minigrid. 2018. 73 Appendix A Implementation Details is reachable is stored as a set of tuples with the form of (s, g) where each of them has a 3 dimensional descriptor of (x,y,direction). In both proposed algorithms RCRL and RCVL we use the same structure of it. A.1 RCRL implementation details RCRL was implemented with the default parameters as appear in the table A.1. Hyperparameter Value High policy and Value estimation SAC A.4 Low policy ϵgreedy DDQN A.3 Low horizon 4 High horizon 15 Learning rate 3e-4 Batch size 256 Table A.1: RCRL default parameters used in studies and experiments A.2 RCVL implementation details RCVL was implemented with the default parameters as appear in the table A.2. In the preliminary studies some of the parameters were changes according the described in the specific study, while the rest of the parameters stay the same. 74 Chapter A– Implementation Details DDQN implementation – 75 Hyperparameter Value High policy and Value estimation SAC (A.4) Low policy ϵgreedy DDQN (A.3) Low horizon 4 High horizon 15 Learning rate 3e-4 Sample size in preliminary acquisition 0 Batch size 256 Radius for neighborhood 1 Symmetry neighborhood collection False Flatt or round acquisition (Pre.Acq) Round Back and forth repetitions (Pre.Acq) 5 Table A.2: RCVL default parameters used in studies and experiments The implementation of goal list includes a list in the size of m×n, having m board width and n board height. A function converts from location as (x,y) to a unidimensional indices list. In the case of the board with size of 15x15 we get a goal list with the length of 225. Each ”element” in this list is a set. That assures that there are no repetitions. This set contains the collected states in the vicinity of a goal, with their 3 dimensional descriptors: (x,y,direction). A.3 DDQN implementation DDQN was implemented according to [1] with the following hyper parameters: Hyperparameter Value Hidden dimension of NN (128, 128, 128, 128) Optimizer AdamW (default) ϵDecay 0.65 to 0.1 Learning rate 3e-4 Buffer size 5e5 Discount coefficient γ1 Soft-update parameter τ0.005 Table A.3: DDQN default parameters used in studies and experiments A.4 SAC implementation details SAC was implemented based on [14]. It was used for both RCLV and RCRL, while for the first uses it’s Q-value approximators, and the actor only for the case where the goal was 75 Chapter A– Implementation Details SAC implementation details – 76 never visited before so there are no possible suggestions in goal list. The hyperparameters for it are the following: Hyperparameter Value Hidden dimension of NN (128, 128, 128, 128) Optimizer AdamW (default) Learning rate 3e-4 Buffer size 1e6 Discount coefficient γ1 Soft-update parameter τ0.005 Entropy regularizer α1 Table A.4: SAC default parameters used in studies and experiments 76