Intrinsic Motivation mechanisms for a better sample efficiency in deep reinforcement learning applied to scenarios with sparse rewards

University of the Basque Country UPV/EHU Doctoral Thesis Intrinsic Motivation Mechanisms for a Better Sample Efficiency in Deep Reinforcement Learning applied to Scenarios with Sparse Rewards Author: Alain Andres Fernandez Supervisors: Dr. Esther Villar-Rodriguez Prof. Dr. Javier Del Ser A Thesis submitted in fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Communications Engineering June 28, 2023 (cc)2023 ALAIN ANDRES FERNANDEZ (cc by-sa 4.0) iii “We tend to overestimate the effect of a technology in the short run and underestimate the effect in the long run.” Roy Amara “Most people overestimate what they can achieve in a year and underestimate what they can achieve in ten years” Bill Gates “The complex line that delimits the short-sighted and long-term decisions for happiness. The 𝛾parameter that governs and rules our lives. The motivations behind each decision. The uncertainty of the environment that surrounds us. There is no “optimal” path to follow; the answer for a worth living life is unique and subjective for each human being.” Alain Andres, myself. UNIVERSITY OF THE BASQUE COUNTRY UPV/EHU Abstract Engineering School of Bilbao Department of Communications Engineering Doctoral Degree Intrinsic Motivation Mechanisms for a Better Sample Efficiency in Deep Reinforcement Learning applied to Scenarios with Sparse Rewards by Alain Andres Fernandez Driven by the quest to create intelligent systems that can autonomously learn to make optimal decisions, Reinforcement Learning has emerged as a powerful branch of Machine Learning. Reinforcement Learning agents interact with their environment, learning from trial and error, guided by feedback signals shaped in the form of rewards. However, the application of Reinforcement Learning is often hampered by the complexity associated with the design of such rewards. Creating a dense reward function, where the agent receives immediate and frequent feedback from its actions, is often a challenging task. This challenge arises from the difficulty of specifying the correct behavior for every possible state-action pair. This issue parallels the challenges faced in human learning where educators often grapple with identifying the best way to teach a certain skill or subject, given that learning styles can vary dramatically among individuals. As a consequence, it is common to formulate the problems with sparse rewards, where the agent is only rewarded when it accomplishes a significant task or achieves the final goal, thus aligning more directly with the objective of the problem. The sparse reward formulation does not require the anticipation of every possible scenario or state, making it more tractable for complex environments and real-world scenarios, where feedback is often delayed and not immediately available. However, sparse reward settings also introduce their own challenges, most notably, the issue of exploration. In the absence of frequent rewards, an agent can struggle to identify beneficial actions, making learning slow and inefficient. This is where mechanisms such as Intrinsic Motivation come into play, encouraging more effective exploration and improving sample efficiency, despite the sparsity of extrinsic rewards. In this context, the overall contribution of this Thesis is to delve into how Intrinsic Motivation can boost the performance of Deep Reinforcement Learning approaches in environments with sparse rewards, aiming vi to enhance their sample efficiency. To this end, we first stress on its application with concurrent heterogeneous agents, aiming to establish a collaborative framework to make them explore more efficiently and accelerate their learning process. Furthermore, an entire chapter is devoted to analyzing and discussing the impact of certain design choices and parameter settings on the generation of the Intrinsic Motivation bonuses. Last but not least, the Thesis proposes to combine these explorative techniques with Self-Imitation Learning, demonstrating that they can be used jointly towards achieving faster convergence and optimal policies. All the analyzed scenarios suggest that Intrinsic Motivation can significantly speed up learning, reducing the number of interactions an agent needs to perform, and ultimately, leading to more rapid and efficient problem-solving in complex environments characterized by sparse rewards. vii Acknowledgements It seems like yesterday when I was doing my Master’s and began my internship at the Aula Tecnalia in San Mames. Although my research at the time was oriented towards cybersecurity due to its relation to my studies, I had always been curious about the potential of Artificial Intelligence and its possibilities to create solutions that lead us, humans, to a better environment. Unbeknownst to me, I was working alongside a group of high-quality researchers in AI (JRL group)... and one day, I approached them and expressed my interest in their work, not knowing that it would be the first step that propelled me into the world of research. This journey would not have been possible without Javier Del Ser, a.k.a el señor mayor or deidad del ser... my professor, director, and supervisor throughout this long and challenging journey. I remember the first time we met during a class, but it wasn’t until some time later that I realized how research-aholic you were(are) when I discovered you held, not one, but two PhDs! I will always be grateful for the time you took to answer my inquiries and explain what doing research is, introduce me to the entire research group, and encourage me to pursue my PhD despite my fears and not being familiar with the field. You provided guidance when I felt lost and demotivated, offering invaluable tips that have shaped my research career up to this point. Without your support, I definitely would not have embarked on this path. I am also indebted to Tecnalia, which was initially the research partner of the Bikaintek funding program that granted my PhD. Despite the fact that other employer was involved (with more weight and more interest in what respects to my research), when the latter decided to withdraw from the project, Tecnalia took a step forward, assumed the proportional financial aspects of my grant, and continued to support the project and myself, recognizing its value. I want to thank my superiors at that time: Isidoro Cirion, Iñigo Arizaga, Elena Urrutia and Joseba Laka. However, I must emphasize the critical role played by both my directors during this period when we had no results, papers or indicators guaranteeing the viability of such an investment. We had to shift our focus away from the problem we were addressing and start from scratch again (due to the other partner leaving), which posed a real challenge for us. Even in that circumstance, both of you convinced everyone, solely with your words, to continue trusting in me and put yourselves in a complex position. I am at a loss for words to express my gratitude.. I can not forget the most significant pillar during these years, my other director, Esther. Even at this point, I struggle to find the right words to express myself adequately. I could highlight different (numerous, various, multiple...) technical aspects that commend such a brilliant brain which have been crucial for the successful development of this thesis. However, without intending to diminish these professional attributes, I want to use my words to emphasize your humanity. We have discussed, argued and conversed about various topics for hours, much like a child does with their mother (I think that is one of the reasons behind some co-workers saying viii that you were my figurative mom). You have always listened to me, not only during our work hours but also outside of work, offering your perspective and advice in whatever the problem was. I can not enumerate how many calls we have had, and how thankful I felt to have your support, specially in those situations were I was unmotivated due to several reasons that are not relevant at this moment. I can not forget when you said something like: "It is about the person and its values, not just the work or the results. You should be proud of what you are; any team would undoubtedly be lucky to have you". I have repeated those words to myself and use them as a compass during this journey. This thesis and the person I have become, both professionally and personally, owe a great deal to you. Thank you. Last but not least, I have to thank my friends, but more importantly, my family – both my parents, Txomin and Marijo, and my sister Goretti – who have always support me unconditionally, not only during these past 4 years, but throughout my entire life. I would not be who I am without you, without your patience, without your efforts, without the values you have instilled in me, and without all the trust you placed in me even when I lost myself. I hope I can return everything I got, and to be, at some point in time, for other people, what you have been for me. ix Contents Abstract v Acknowledgements vii 1 Introduction 1 1.1 Motivation ........................... 2 1.2 Outline and Contributions of the Thesis ........... 5 1.3 Reading this Thesis ....................... 6 2 Background 9 2.1 Fundamentals of Reinforcement Learning .......... 10 2.1.1 Markov Decision Process ............... 10 2.1.2 Sequence Boundaries: Episode & Rollout ...... 12 2.1.3 Rewards and Returns ................. 12 2.1.4 Policy and Value Function ............... 15 2.1.5 On-policy VS Off-policy ................ 17 2.1.6 Value-based VS Policy-based ............. 17 2.1.6.1 Policy Gradient methods .......... 20 2.1.7 Deep Reinforcement Learning ............. 25 2.2 Environments .......................... 26 2.2.1 Procedurally-Generated Environments ........ 27 2.3 Exploration Strategies ..................... 28 2.3.1 Intrinsic Motivation .................. 30 2.3.2 Imitation Learning ................... 34 3 Collaborative Training of Heterogeneous Agents 37 3.1 Related Work .......................... 39 3.1.1 Contribution Beyond the State of the Art ...... 41 3.2 Problem Statement ....................... 42 3.3 Proposed Collaborative Framework .............. 44 3.3.1 Centralized Learning with Decentralized Execution . 45 3.3.1.1 Decentralized Actors ............. 46 3.3.1.2 Centralized Critic Module .......... 47 3.3.2 Centralized Intrinsic Curiosity Module ........ 49 3.3.2.1 Action-based Curiosity Module ....... 51 3.3.2.2 Tree Filtering ................ 52 3.3.3 Summary of the Proposed Modules .......... 53 3.4 Experimental Setup ...................... 54 3.4.1 Case Study 1 ...................... 55 3.4.2 Case Study 2 ...................... 57 xvii List of Tables 2.1 Popular 𝜓estimator choices. .................. 20 3.1 Details of both the actor and critic neural network architectures. .............................. 60 3.2 Summary of the configuration ablations within the collaborative framework. ........................ 63 3.3 Sample-efficiency and quality of resulting policies for different evaluated configurations in Setup 3. ........... 74 4.1 Various IM methods based on different design choices. . . . 82 4.2 Results of different IM strategies over MiniGrid scenarios, addressing RQ1. ........................ 93 4.3 Results of different IM strategies over MiniGrid scenarios, addressing RQ2. ........................ 95 4.4 Comparison of number of parameters and required forward and backward passes across different IM modules. ...... 97 4.5 Results of different IM strategies over MiniGrid scenarios, addressing RQ3. ........................ 98 5.1 On-policy versus off-policy ratios (𝜉) in each environment, with the off-policy update executed upon episode completion.114 xix List of Abbreviations General SOTA State OfThe Art ANN Artificial Neural Network DL Deep Learning SL Supervised Learning UL Unsupervised Learning RL Reinforcement Learning DRL Deep Reinforcement Learning MDP Markov Decision Process POMDP Partially Observable Markov Decision Process MARL Multi-Agent RL CLDE Centralized Learning with Decentralized Execution IM Intrinsic Motivation IL Imitation Learning self-IL Self Imitation Learning (generic) LfD Learning from Demonstrations IRL Inverse Reinforcement Learning PCG Procedurally Content Generator KL Kullback-Leibler SR Success Rate LSTM Long Short-Term Memory Reinforcement Learning SState space AAction space RReward space PTransition probability function GReturn OObservation function ΩObservation space 𝛾Discount factor 𝜋Policy VValue function QAction-Value function TD Temporal Difference xx Algorithmic approaches EA Evolutionary Algorithms UCB Upper Confidence Bound SARSA State-Action-Reward-StateActionDQN Deep Q-Network PPO Proximal Policy Optimization TRPO Trust Region Policy Optimization GAE Generealized Advantage Estimator A3C Asynchronous Advantage Actor-Critic IMPALA Importance Weighted Actor-Learner Architecture DPG Deterministic Policy Gradient DDPG Deep Deterministic Policy Gradient TD3 Twin Delayed DDPG SAC Soft Actor-Critic NGU Never Give Up PER Prioritized Experience Replay ICM Intrinsic Curiosity Module RND Random Network Distillation RIDE Rewarding Impact Driven Eexploration RAPID Rank the Episodes BeBold Beyond the Boundary of ExploredRegions MADE Exploration via Maximizing Deviation from Explored Regions BeBold Beyond the Boundary of ExploredRegions NovelD Novelty Difference FaSo Fast and Slow intrinsic curiosity AGAC Adversarially Guided Actor-Critic DoWhaM Don’t Do What Doesn’t Matter D&E Divide-and-Explore SIL Self-Imitation Learning DTSIL Diverse Trajectory-conditioned Self-Imitation Learning UVFA Universal Value Function Approximator BC Behavior Cloning DAGGER Dataset Aggregation 1 Chapter 1 Introduction Artificial Intelligence (AI) is one of those topics in everyone’s lips in these days. Although multiple definitions can be found in the literature laid out by how a system should think and act taking into account both the rational and human aspects, a wide and more generalist definition was set in (Russell & Norvig, 2022), which characterized AI as: “The study of agents that receive percepts from the environment and perform actions”. AI’s popularity has raised with the irruption of Industry 4.0 (and the upcoming and more sustainable Industry 5.0) where it has been considered one of the main Key Enabling Technologies, being in the own words of the European Commission a game-changer due to its potential to increase the efficiency and productivity across multiple sectors1. More concretely, Machine Learning (ML) has drawn the attention due its potential to make a computer-system learn from examples (data) without explicit supervision of a human-being, getting the necessary information by analyzing patterns. By resorting to ML to automate tasks, people can spend time carrying out other duties (productivity) and also rely on the solutions provided by systems with better performance that overcome natural human limitations (efficiency/optimality), ultimately improving overall people’s welfare. Regarding ML, three subgroups can be distinguished: •Supervised learning (SL): learns from labeled data in order to generalize the knowledge to upcoming new inputs. •Unsupervised learning (UL): learns from unlabeled data so that the information can be compressed and accordingly segmented into classes. •Reinforcement learning (RL): learns through the interaction (trial and error) with an environment where the aim is to solve a defined task. This thesis gravitates around RL and, although its fundamentals are going to be more deeply explained in Chapter 2, it is important to notice the 1https://research-and-innovation.ec.europa.eu/knowledge-publications-tools-and-d ata/publications/all-publications/ai-research-and-innovation-europe-paving-its-own -way_en. 2Chapter 1. Introduction differences with respect to the other two categories, specially between RL and SL, which are similar and often confused with each other. On the one hand, SL assumes the data to be independent and identically distributed (i.i.d) and requires a priori knowledge about the ground truth (also referred to as true label or annotation) of the training data. Contrarily, in RL previous decisions influence future inputs (i.e., data are not independent, it is a sequential paradigm) whereas the ground truth answer is not known (correct actions/labels are not provided). Instead, the reward is used as an estimator to guide the learning. Although the RL field has been under study since the 20th century, it did not come to the fore until the last decade due to advances in Deep Learning (DL) and computational capabilities that ease their application. DL involves using non-linear function approximators – typically Artificial Neural Networks (ANN) – so that ML algorithms can ingest unstructured data and automate the feature extraction process. Regarding computational capabilities, the processing units have experienced significant advances in efficiency enabling the deployment of larger and more complex models while exponentially decreasing the time devoted to train them. By the virtue of this progress, RL can leverage ANNs to handle more complicate and diverse problems unapproachable in the past, which gives name to the field where this dissertation is contextualized, Deep Reinforcement Learning (DRL), Figure 1.1. UL SL RL Artificial Intelligence Machine Learning Deep Learning : Pure Deep RL : Deep RL + SL Figure 1.1: Artificial Intelligence taxonomy: Supervised Learning (SL), Unsupervised Learning (UL) and Reinforcement Learning (RL). This dissertation is focused on the areas highlighted in orange, Pure DRL, and pink, DRL+SL. 1.1 Motivation Despite the premises stated above, state-of-the-art (SOTA) ML methods are not mature enough to solve the vast majority of the problems without human presence. Behind the very basic idea of learning from a reward, 1.1. Motivation 3 RL has to deal with multiple challenges derived from its demanding setup requirements (Dulac-Arnold et al., 2021) (e.g., lack of an available-good simulator, delayed feedback signals, learning from poorly specified reward functions) as well as other difficulties inherent to these techniques(Osband et al., 2020) (e.g., exploration-exploitation dilemma, credit assignment problem, generalization to unseen experiences). However, this has not been an obstacle to begin applying RL to real-world problems when possible(Li, 2019) and see outstanding results in fields like: •Industry/robotics (supply chain, manufacturing)(Ibarz et al., 2021; Nian et al., 2020) •Healthcare (treatment recommendation)(Gottesman et al., 2019) •Energy (power consumption)(Fu et al., 2022) •Finance (portfolio management)(Filos, 2019) •Communications and Networking Systems (network access and security, adaptive rate control)(Luong et al., 2019) Motivated by the exciting journey of RL in those fields, the researchdriven interest have been oriented towards narrowing the gap between realworld problem requirements and experimental RL setups, so that more problems become tractable. With all this in mind, multiple high level challenges can be identified (Dulac-Arnold et al., 2021): •Sparse rewards: in RL a feedback signal (reward) is needed to guide the learning so that the agent can distinguish whether the decisions made were actually good/bad. Informative rewards are not necessary right after every single interaction as long as the credit of each action can be deduced. Nevertheless, determining if a decision is better/worse than another, without considering a whole sequence of events, is complex – even when having access to the whole state information and the objective to attain – as there are a large amount of possible sequential combinations that exponentially grow with the extension of the action space and the required number of steps up to the goal, which can lead to very different outcomes. Thus, sparse rewards can be used to evaluate a sequence of decisions. In fact, sparse feedback signals are one of the main challenges present in real-world setups: system delays and difficulties in modeling reward functions in complex problems. However, the more sparse the rewards, the more arduous becomes to determine which actions are useful. Furthermore, the exploration becomes more troublesome. Therefore, sparsity remains as one of the main concerns to be solved in realworld RL problems. •Partial observability: the RL-framework is commonly formalised as a Markov Decision Process (MDP), where a state must contain all the necessary information to make a decision. In practice, this rarely holds true due to the lack of critical information needed in each 4Chapter 1. Introduction time step. Hence, it is common that the agent gets an observation rather than a state, which obviously limits the comprehension of the environment that surrounds it. That context is formally referred to as a Partially Observable Markov Decision Process (POMDP) and exposes difficulties regarding generalization, credit assignment and long-term consequences2, being a challenge present in large number of real-world scenarios. •High dimensional continuous states spaces: among the different possibilities to model a problem, one of the big issues is how to represent the state (or observation) in such a way that the agent can learn. This implies selecting the type of data and the dimensions to be used as input, where an inappropriate criteria can downgrade dramatically the expected results. This may cause that the agent is unable to model the correlation between the input features, the selected action and their utility. Thank to advances in DL and assuming an agent can understand/infer the world similarly to how humans do, it has become popular to model problems taking into account, for example, images, as input. Therefore, high dimensional inputs are related to generalization issues which are also present in real-world problems. •Evolution-Adaptation to action space modifications: the modification and the consequence adaptation of the agent to either state and/or action spaces can bring new behaviors. Instead of re-training from scratch, the previous knowledge can be reused with techniques like Transfer Learning or by the virtue of using Expert Demonstrations. In such context, how heterogeneous agents should be trained is not clear, as they are supposed to learn different policies. The challenge resides in how to exploit the knowledge gained by other agents. •Real-time inference: in order to deploy any ML-based solution into a production system, the algorithm has to be designed according to the system’s capabilities and constraints. While large and complex artificial neural network (ANN) architectures have achieved remarkably good results in various applications, their high computational costs often hinder their adoption in real-world systems. Therefore, striking a balance between performance and costs becomes a practical criterion. Sometimes, achieving high performance can be accomplished by reducing the complexity of the network while introducing complementary, yet lighter, procedures from algorithmic development into an extended ML pipeline. 2As the agent only manages to understand the impact of the decisions that modify parts of state that are measurable in its observation, the credit of each action is usually hard to determine (credit assignment). This problem can be minored if such effects can be correlated within a narrow sequence of interactions (long-term consequences), which could ultimately affect the capacity to act in new or similar observations (generalization capacity). 1.2. Outline and Contributions of the Thesis 5 The Thesis aims to develop novel strategies to cope proficiently with all these aspects, which are the facets that most faithfully reproduce realistic scenarios. 1.2 Outline and Contributions of the Thesis In light of the aforementioned objectives, the core problem to be addressed can be entitled as sample-efficiency in POMDPs with sparse rewards, covering exploration-exploitation dilemma in multiple scenarios while attempting to use the minimum samples to get an optimal policy. Therefore, the Thesis is structured in chapters with different use-cases. A brief summary of each chapter is introduced below. Chapter 2 This chapter – Background – aims to introduce and condense all the needed information to understand the technical contributions. Besides the fundamentals of RL and the benchmarks/environments that can be found into the literature, the reasons why sparse reward problems have become popular are highlighted. At the same time, the incoming challenges of adopting such sparse paradigm are explained altogether with the most popular techniques adopted to face the major drawbacks. Along this section a wide review of related research works are presented in order to provide the reader with the fundamental concepts, which are indeed transversal for the following chapters. Chapter 3 In this chapter – Collaborative training between hetereogeneously skilled agents in environments with sparse rewards – we focus on how to carry out a collaborative learning framework between heterogeneous agents with different action spaces yielding different optimal policies. Unlike multi-agent systems, in which agents operate in the same scenario and are typically evaluated based on a team-reward function, we analyze how to learn more efficiently when agents’ rewards are independent and each of them interact with distinct instances of the environment. This is also known as the concurrent learning paradigm, which lies somewhere between singleand multiagent problems. Besides the heterogeneity, this chapter also delves into the challenges of POMPDs,sparse rewards and high-dimensional state spaces by learning how to navigate directly from pixels. Chapter 4 Motivated by the great success and advances of Intrinsic Motivation (IM) techniques, Chapter 4 – An Evaluation Study of Intrinsic Motivation Techniques applied to Reinforcement Learning over Hard Exploration Environments – presents an empirical study to assess and 12 Chapter 2. Background 2.1.2 Sequence Boundaries: Episode & Rollout The sequence or number of interactions between the agent and the environment can be broken into subsequences which can be referred as trajectory, rollout and/or episode, being their meaning slightly different depending on the boundaries. In this Thesis, we adopt the following taxonomy which is widely used in the literature: •Trajectory is the less restrictive concept and can be used to refer to any of the next two terms. •An episode ends when a maximum number of steps are taken or when the agents achieves the goal (the number of steps required to finish an episode in any of those cases is parameterized by T). As a result, the environment is reset and the agent is brought back to a initial state2in order to solve the environment again. Despite the fact that the large majority of problems are of this nature, commonly referred as episodic tasks, others are categorized as continuous tasks when the goal is never achieved (𝑇=∞) because the task is endless. •On the contrary, a rollout (𝜏) is not subject to the termination of the episode and is composed by a predetermined number of steps. Consequently, a rollout could contain less experiences than an episode, or even a multiple amount of them, being the number of such experiences (T) a parameter defined by the user (independently of the environment). For the sake of clarity, we provide an example in Figure 2.2 where interactions of two different complete episodes can be distinguished. If we considered a rollout of size 15 (𝑇=15), then the rollout would fence the two different episode’s information in; on the opposite, if it was set to 5 (𝑇=5), then the rollout will cover less information (e.g., half of an episode in the first example). Note that an episode’s length (number of experiences) depends not only on the environment, but also on the quality of the policy that selects the actions, since an expert agent will be able to accomplish the task with the optimal, i.e. smallest, number of steps3. Thus, the defined rollout size (𝑇) ends up containing a variable number of episodes during the training process, which is important in order to balance the bias and variance of the updates generated upon those experiences. 2.1.3 Rewards and Returns In RL, a reward is a scalar value that an agent receives from the environment after taking an action to guide its learning. The reward indicates how well the agent performed relative to the objective. More importantly, 2The agent can be reset either in a fixed starting state (𝑠0) or within a distribution of possible states (𝜌0). Thus, 𝑠0∼𝜌0with a variable number of initial states. 3In the interactions of the two episodes presented in Figure 2.2 the optimal trajectories are considered. 2.1. Fundamentals of Reinforcement Learning 13 Episode 1 10 steps Episode 2 11 steps Figure 2.2: Example of two different episodes’ interactions. The agent is the red arrow and the environment the maze and all the objects that surround it. The state is the visual perception of the environment, the actions are the set of permitted navigation movements and the set of object manipulation operations, and, the reward, is always zero except when arriving to the green square (the goal). The above two rows represent a single episode, while the remaining rows represent a different episode. the agent’s primary goal is to make decisions that maximize the rewards obtained from the environment, which is referred to as the return. Therefore, designing a reward function that provides adequate feedback signals is of utmost importance. In the following, extended definitions of rewards and returns are provide. Rewards The reward has to reinforce good decisions and discourage useless or wrong actions in order to make the agent achieve what we desire from it. This means that the agent´s success pivots on how well the feedback signals are coherent with the goal of the task. Some conceptualizations of reward functions, and subsequently, the rewards in each interaction, can be exemplified as follows: Example 1, Robot. Goal: make a robot run as fast as possible not falling. The reward could be inversely proportional to the required number of steps to arrive to a given destination without falling. 14 Chapter 2. Background Example 2, Chess. Goal: make an agent learn how to play chess. The intuitively rewards could be +1 for winning, -1 for losing and 0 for drawing. In such examples, the agent is guided to complete the task with sparse signals that evaluate the whole sequence of actions that leads to a given outcome. Nevertheless, a reward function’s success is also subject to how the progress in reaching the objective is evaluated. For instance, sparsity can be circumvented by means of establishing easier subgoals or providing intermediate rewards (i.e., dense) that ease the credit assignment problem: Example 1, Robot. The reward function can be designed to promote the forward motion at each step. Example 2, Chess. Intermediate rewards can be considered when taking opponent’s pieces out. Nonetheless, this strategy could mislead the agent into a greedy search of subgoals achievement instead of focusing on the main goal. Example 2, Chess. The agent could find difficulties to beat the opponent becoming greedy into taking the others pieces out rather than developing a winning strategy. It is important to remark that, even by designing a good reward function, the success and quality of the results might not be as expected due to other important aspects (e.g., model weights initialization, algorithmic limitations, bias-variance trade-off)4. Thus, opting for a naive and easy reward function (over a more complex one) is sometimes suggested. For these reasons, its design is not trivial and sparse formulations are preferable at the expense of exploration challenges. We will refer later on this Chapter (Section 2.3) to methods to address the explorationexploitation dilemma more efficiently although this is tangential to the main subject of this dissertation. Return Note that the main goal of the agent is to maximize the sum of rewards, which can be formalized with the return,𝐺𝑡: 𝐺𝑡=𝑟𝑡+1+𝑟𝑡+2+𝑟𝑡+3+... +𝑟𝑇(2.2) where 𝑡and 𝑇stand for the current and final time steps in an episode, respectively. This calculation gives the same importance to all the decisions regardless of their temporal component. What is more, this formulation complicates the calculation of the return in continuous tasks, when there is no episodic boundaries and the return becomes a sum of infinite series. In light of this limitation, the discount concept was introduced by 𝛾∈ [0,1], 4This can be seen in humans clearly: for the same stimuli, environment, and objective, people require different time to converge to a solution. Moreover, multiple behaviors could lead to what is considered an optimal policy (even for the same reward function). 2.1. Fundamentals of Reinforcement Learning 15 turning such operation in a finite calculation5. This discount factor allows also modulating the importance of immediate and distant rewards. This new return formulation is commonly referred to as discounted return: 𝐺𝑡=𝑟𝑡+1+𝛾𝑟𝑡+2+𝛾2𝑟𝑡+3+... = ∞ ∑︁ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘+1(2.3) This implies that a reward to be received after 𝑘steps in the future will be worth 𝛾𝑘−1times less than one obtained immediately. Accordingly, •𝛾 < 1is used to adjust the weights of future rewards. •𝛾=0is known as "myopic-view" and only maximizes immediate rewards, 𝐺𝑡=𝑟𝑡+1+0·𝑟𝑡+2+0·𝑟𝑡+3+... =𝑟𝑡+1. •𝛾=1corresponds to the formal definition of return without discount, homogenizing the value of future and immediate rewards, 𝐺𝑡=𝑟𝑡+1+ 1·𝑟𝑡+2+1·𝑟𝑡+3+... =𝑟𝑡+1+𝑟𝑡+2+𝑟𝑡+3... In summary, the 𝛾value regulates the effect of maximizing short-term or long-term behaviors, being 0.9< 𝛾 < 1mostly selected to give credit to future actions and avoid the reward importance vanishing. As a consequence, a fifth (and seventh) element must be attached to the previously introduced MDP (POMDP) tuple: {S,A,P,R, 𝛾} ({S,A,P,R, 𝛾, O,Ω}). 2.1.4 Policy and Value Function Previously, it has been explained how the agent interacts with the environment through actions. A policy, 𝜋:S −→ A, is a function that maps the current state of an agent to an action to be taken, 𝑎∼𝜋(𝑠)and it can be either deterministic or stochastic. A deterministic policy maps each state to a single action, whereas a stochastic policy maps each state to a probability distribution over the possible actions that the agent can take. The value function is a function that estimates the long-term reward that an agent can expect to receive in a given state or state-action pair, under a specific policy 𝜋. The state value function,𝑉𝜋(𝑠), is responsible for estimating the expected return starting from a state 𝑠and following the policy 𝜋thereafter, i.e., 𝑉𝜋(𝑠𝑡)=E𝜋[𝐺𝑡|𝑠𝑡=𝑠]=E𝜋"∞ ∑︁ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘+1|𝑠𝑡=𝑠#(2.4) where E[·] denotes expected value. Similarly, the action value function, 𝑄𝜋(𝑠, 𝑎), estimates the expected return starting from not only a state 𝑠, 5After a big number of steps, any future reward’s effect can be considered insignificant. Furthermore, this only holds true as long as 𝛾∈ [0,1)because when 𝛾=1all the rewards are considered equally important. 16 Chapter 2. Background but also executing an action 𝑎, and following the policy 𝜋thereafter, i.e., 𝑄𝜋(𝑠𝑡, 𝑎𝑡)=E𝜋[𝐺𝑡|𝑠𝑡=𝑠, 𝑎𝑡=𝑎]=E𝜋"∞ ∑︁ 𝑘=0 𝛾𝑘𝑟𝑡+𝑘+1|𝑠𝑡=𝑠, 𝑎𝑡=𝑎#.(2.5) Interestingly, one property that applies over value functions is the recursive relationship involving the calculation of returns: 𝐺𝑡=𝑟𝑡+1+𝛾(𝑟𝑡+2+𝛾𝑟𝑡+3+𝛾2𝑟𝑡+4+...) =𝑟𝑡+1+𝛾𝐺𝑡+1 (2.6) with the consequent reformulation of Equation (2.4): 𝑉𝜋(𝑠𝑡)=E𝜋[𝐺𝑡|𝑠𝑡=𝑠] =E𝜋[𝑟𝑡+1+𝛾𝑟𝑡+2+𝛾2𝑟𝑡+3+...|𝑠𝑡=𝑠] =E𝜋[𝑟𝑡+1+𝛾𝐺𝑡+1|𝑠𝑡=𝑠] (2.7) being the rewards those that are obtained by following 𝜋actions in each of the encountered states from 𝑠onwards. Note that both 𝑉𝜋and 𝑄𝜋are connected through the next equations: 𝑉𝜋(𝑠𝑡)=E𝜋[𝑄𝜋(𝑠𝑡, 𝑎𝑡)|𝑠𝑡=𝑠, 𝑎𝑡=𝑎∼𝜋(𝑠)] (2.8) 𝑄𝜋(𝑠𝑡, 𝑎𝑡)=E𝜋[𝑟𝑡+1+𝛾𝑉𝜋(𝑠𝑡+1)|𝑠𝑡=𝑠, 𝑎𝑡=𝑎](2.9) where the key difference lies in the fact that 𝑄𝜋calculates the expected return assuming that the immediate action will be 𝑎𝑡, determining the next state 𝑠𝑡+1∼ P(𝑠𝑡, 𝑎𝑡)and the associated reward 𝑟𝑡+1=R(𝑠𝑡, 𝑎𝑡, 𝑠𝑡+1); whereas 𝑉𝜋does not presume any action in its return estimation, being this selection dependent on the current behavior of the policy 𝜋. In addition to these two value estimators, a new function can be considered: the advantage function, 𝐴𝜋(𝑠, 𝑎). This function quantifies how much is a certain action 𝑎taken in state 𝑠a good or bad decision in relation to the expected value 𝑉𝜋(𝑠)in that state, i.e., 𝐴𝜋(𝑠𝑡, 𝑎𝑡)=𝑄𝜋(𝑠𝑡, 𝑎𝑡|𝑠𝑡=𝑠, 𝑎𝑡=𝑎) − 𝑉𝜋(𝑠𝑡|𝑠𝑡=𝑠)(2.10) Last but not least, a policy 𝜋is considered to be better than another policy 𝜋′if the expected return is greater, that is, 𝜋≥𝜋′iff (if and only if )𝑉𝜋(𝑠) ≥ 𝑉𝜋′(𝑠). In this regard, there is always going to be a policy that is equal or better to the rest of policies, named the optimal policy 𝜋∗. Analogously, there will be optimal value functions representing the actual best returns that would be expected from each state 𝑠when following the optimal policy 𝜋∗thereafter, i.e., 𝑉∗(𝑠𝑡)=𝑚𝑎𝑥𝜋𝑉𝜋(𝑠𝑡|𝑠𝑡=𝑠) 𝑄∗(𝑠𝑡, 𝑎𝑡)=𝑚𝑎𝑥𝜋𝑄𝜋(𝑠𝑡, 𝑎𝑡|𝑠𝑡=𝑠, 𝑎𝑡=𝑎)(2.11) 2.1. Fundamentals of Reinforcement Learning 17 2.1.5 On-policy VS Off-policy In RL, a wide range of algorithms can be found. One of the criteria to opt for one schema is the strategy about how to use the data in the training, commonly categorised as on-policy or off-policy strategies. On-policy techniques attempt to improve the policy that is being used to interact with the environment. Because of that, they can only use data that are representative of the current policy, 𝜋𝑡, which precludes the use of any data gathered with a different policy, including any previous policy state 𝜋𝑡−1, 𝜋𝑡−2, ... Hence, they are prone to be less sample efficient yet more stable in the learning process. Within this group we can find SARSA(Rummery & Niranjan, 1994), REINFORCE and Trust Region Policy Optimization (TRPO) (Schulman, Levine, et al., 2017), among others. On the other hand, off-policy methods learn a target policy with data generated by a different policy, known as behavior policy. In that case, the learning is said to be carried out from experiences "off" the target policy. Consequently, these algorithms exhibit better sample-efficiency, but are prone to overestimation and instabilities during training time. The most common off-policy algorithms are Q-learning (Watkins & Dayan, 1992) and its extended DL approach, DQN(Mnih et al., 2015); and other approaches that were built on top of DQN like Double DQN (van Hasselt et al., 2015), Dueling DQN(Z. Wang et al., 2016) and C51(Bellemare et al., 2017). Nevertheless, other popular and effective algorithms unrelated to DQN have also been proposed, such as Deterministic Policy Gradients (DPG)(Silver et al., 2014), Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al., 2015), Twin Delayed DDPG (TD3)(Fujimoto et al., 2018) and Soft Actor-Critic (SAC) (Haarnoja et al., 2018). 2.1.6 Value-based VS Policy-based Regarding the procedure to obtain the policy, RL algorithms can be divided into value-based or policy-based methods. The first group, i.e. value-based methods, aims to learn a value function that evaluates the utility of each state (i.e., 𝑉𝜋(𝑠)) and/or stateaction pairs (i.e., 𝑄𝜋(𝑠, 𝑎)). For this purpose, the objective is to minimize the difference between the predicted return of each state (𝑉𝜋(𝑠𝑡)or 𝑄𝜋(𝑠𝑡, 𝑎𝑡)) and the actual target return (𝐺𝑡). Note that the actual return calculation is subject to the experiences gathered by the agent (e.g., 𝜏={𝑠𝑡, 𝑎𝑡, 𝑟𝑡+1, 𝑠𝑡+1, 𝑎𝑡+1, 𝑟𝑡+2, ...}), which might well not represent the optimal return and will result in the learning of value functions according to these suboptimal target values. More importantly, the trajectories collected for this purpose will be very diverse due to the 𝜋’s evolution dependence during training. Thus, the target return calculation will exhibit large variance and induce instabilities in the respective estimator function learning. To mitigate the possible variance (and bias)-related issues, any of the following proposed estimators can be adopted: 18 Chapter 2. Background •Monte Carlo. All the rewards from the current state to the terminal state are included, 𝐺𝑡=𝑟𝑡+1+𝛾𝑟𝑡+2+𝛾2𝑟𝑡+3+.... It has no bias but exhibits variance problems. •Temporal Difference error (TD-error). Only the current reward is considered and then the rest is bootstrapped by using the value of the next state as an estimate of all the rewards to go, 𝐺𝑡=𝑟𝑡+1+ 𝛾𝑉 (𝑠𝑡+1). It copes well with the variance problem, but introduces a higher bias. •n-step. It is the generalization of the TD-error (𝑛=1) for greater values of 𝑛. This means bootstrapping from a specific time step (𝑛) to the terminal state: 𝐺𝑡:𝑡+𝑛=𝑟𝑡+1+𝛾𝑟𝑡+2+.. +𝛾𝑛−1𝑟𝑡+𝑛+𝛾𝑛𝑉(𝑠𝑡+𝑛). The larger the 𝑛, the less bias and more variance; the lower the value of 𝑛, the higher bias but the less variance. •TD(𝜆)can be explained as a way to average over the above mentioned n-step updates. Therefore, it requires the calculation of all the 𝑛-step returns to, afterwards, assign them more/less weight: 𝐺𝜆 𝑡=(1−𝜆)Í∞ 𝑛=1𝜆𝑛−1𝐺𝑡:𝑡+𝑛. The TD-error is also known as TD(0) as it equals the case 𝜆=0with just 1-step return. For the sake of clarity, Figure 2.3 summarizes the strategies of 𝑛-step and TD(𝜆). Once the value function has been obtained, value-based methods distill their knowledge with some defined rules to build a policy. One approach is to learn an action-value function 𝑄(𝑠, 𝑎)that closely approximates, if not exactly, the optimal action-value function 𝑄∗(𝑠, 𝑎). Then, the agent can greedily choose the action that maximizes the return in each state: 𝑎𝑡=arg max 𝑎 𝑄∗(𝑠𝑡, 𝑎)(2.12) This methodology is known as greedy and is used to exploit and evaluate the knowledge. However, using such strategy during the training (prior to obtaining 𝑄∗(𝑠, 𝑎)) could lead to policies with suboptimal behaviors due to insufficient exploration. This is the reason why other mechanisms that influence in the action selection are adopted (e.g., 𝜖-greedy6). Here we can find algorithms like Q-learning (Watkins & Dayan, 1992), SARSA (Rummery & Niranjan, 1994) and DQN-family among others (Bellemare et al., 2017; Mnih et al., 2015; van Hasselt et al., 2015; Z. Wang et al., 2016). On the opposite, policy-based methods parameterize and optimize the policy directly without the necessity of having a value function. Policies can be learnt by either derivative free methods such as genetic algorithms (Mirjalili, 2019) (recently compared with RL solutions (Martinez et al., 2021)) or policy gradient schemes. In all these methods, the objective is 6Refers to a strategy where the agent selects with probability 𝜖−→ [0,1]a random action and with 1−𝜖the greedy action, balancing exploration-exploitation through 𝜖 parameter. 2.1. Fundamentals of Reinforcement Learning 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1−λ (1 −λ)λ (1 −λ)λ2 λT−t−1 2-step TD 3-step TD Monte Carlo T D(λ) st at st+1 st+2 at+1 at+2 aT−1 st+3 State Action P= 1 1-step TD Terminal State Figure 2.3: (Left) Spectrum of possible TD estimators from 1-step up to Monte Carlo (until termination of episode); in between, n-step calculation are placed. The return estimator is calculated with the real nrewards and then the estimated value of the nth next state. (Right) TD(𝜆) diagram used to weight the n-step returns (when being adopted). 𝜆=0corresponds to just using the 1-step TD, whereas 𝜆=1considers only the Monte Carlo update. to maximize the performance via a fitness score (used for evaluation) or by maximizing directly the return, 𝐽(𝜃)=E𝜋[𝐺𝑡]7. Additionally, policy gradient algorithms can handle both discrete and continuous actions spaces. Continuous actions can be more difficult to work with because it is not feasible to explicitly represent every possible action’s value, as there are an infinite number of them. As a consequence, they are parameterized by either discretizing the range of possible action values in a discrete number of values, or using statistical distributions (e.g., Gaussian) from which the agent can sample specific values. Overall, any value-based or policy-based method can result in deterministic or stochastic policies. Indeed, in value-based methods the agent learns the value of each action. Then, it usually selects the action with higher outcome leading to a deterministic policy. However, this can be bypassed by means of methods that perturb the action selection process (e.g., 𝜖-greedy strategy) or by parameterizing the output values with 7𝜃is used to refer to the parameters that compose the policy 𝜋. 20 Chapter 2. Background a soft-max function to generate a distribution, resulting in a stochastic policy8: 𝜋(𝑎|𝑠)=exp(𝑠,𝑎) Í𝑘exp(𝑠,𝑘)(2.13) being 𝑘the total number of possible actions in A𝑘where the total sum of probabilities of selecting an action is equal to 1, Í𝑘𝜋(𝑎𝑘|𝑠)=1. On the other hand, in policy-based methods the agent learns a probability distribution over the actions composing a discrete action space (or a distribution per action in continuous action spaces), and then samples from that distribution to select an action. 2.1.6.1 Policy Gradient methods Policy gradient methods maximize the expected total reward by estimating the gradient, which can be obtained by differentiating the following objective: 𝐿𝑃𝐺 (𝜃)=b E𝑡[𝜓𝑡log 𝜋𝜃(𝑎𝑡|𝑠𝑡)] (2.14) that results in the popular formalization of the gradient as: b𝑔=b E𝑡"∞ ∑︁ 𝑡=0 𝜓𝑡∇𝜃𝑙𝑜𝑔𝜋𝜃(𝑎𝑡|𝑠𝑡)#(2.15) where 𝜓can be estimated in various ways (Schulman et al., 2015) –see Table 2.1– similar to the estimators previously mentioned for value-based methods. Table 2.1: Different 𝜓estimators (Schulman et al., 2015) that can be used to compute the gradient in policy gradient methods as exposed in Equation (2.15). 𝜓Description Í𝑇 𝑡=0𝛾𝑡𝑟𝑡+1Total reward of the trajectory from the initial state (𝑠𝑡|𝑡=0), Equation (2.3) Í𝑇 𝑡=𝑡𝑖𝛾𝑡𝑟𝑡+1The total reward from a time step (𝑡𝑖) onward, "reward-to-go", Equation (2.3) Í𝑇 𝑡=𝑡𝑖𝛾𝑡𝑟𝑡+1−𝑏(𝑠𝑡𝑖)A baseline (i.e. an average return over trajectories or a parallel 𝑉𝜋) 𝑄𝜋(𝑠𝑡, 𝑎𝑡)State-action value function, Equation (2.5) 𝐴𝜋(𝑠𝑡, 𝑎𝑡)Advantage function, Equation (2.10) 𝑟𝑡+1+𝑉𝜋(𝑠𝑡+1) − 𝑉𝜋(𝑠𝑡)TD-residual At this point it is important to highlight that b𝑔is calculated based on experiences belonging to a trajectory, whose probability depends not only on the initial state (𝑠0) and the transition probability function (P), but 8Note that by the virtue of generating a distribution, an agent will sample different values even for the same state due to the randomness in the sampling distribution. Nonetheless, the outcome can be set to be deterministic by selecting the action with the highest selection probability (Sutton & Barto, 2018). 2.1. Fundamentals of Reinforcement Learning 21 also on the current policy (𝜋𝑡) and the subsequent action probabilities: 𝑝(𝜏|𝜋𝑡)=𝑝(𝑠0) · 𝜋𝑡(𝑎0|𝑠0) · P(𝑠1|𝑠0, 𝑎0) · 𝜋𝑡(𝑎1|𝑠1) · P(𝑠2|𝑠1, 𝑎1) · 𝜋𝑡(𝑎2|𝑠2) ... · P(𝑠𝑇|𝑠𝑇−1, 𝑎𝑇−1) · 𝜋𝑡(𝑎𝑇|𝑠𝑇) (2.16) Therefore, once the policy is updated (𝜋𝑡≠𝜋𝑡+1) the probability of sampling the same 𝜏also changes, which leads to very different experiences, and consequently, to highly variant returns. In fact, some approaches (Espeholt et al., 2018; Horgan et al., 2018; Mnih et al., 2016; Stooke & Abbeel, 2019) use multiple parallel agents to calculate expectations on more diverse batches of experiences that end up stabilizing the variance over the gradient updates: b𝑔=b E𝑡"∑︁ 𝜏∈ D𝑤 ∞ ∑︁ 𝑡=0 𝜓𝑡∇𝜃𝑙𝑜𝑔𝜋𝜃(𝑎𝑡|𝑠𝑡)#(2.17) being 𝑤the number of parallel agents and D𝑤the set of all the trajectories collected by all these agents. The most basic approach is called REINFORCE (Williams, 1992) and resorts to 𝜓=Í𝑇 𝑡=0𝛾𝑡𝑟𝑡+1for the policy update. Posterior works, coined REINFORCE with baseline or Vanilla Policy Gradient (VPG), introduced 𝜓=Í𝑇 𝑡=𝑡𝑖𝛾𝑡𝑟𝑡+1−𝑏(𝑠𝑡𝑖), where a baseline 𝑏𝑡(𝑠𝑡) ≈ 𝑉𝜋(𝑠𝑡)was used in order to mitigate high variance gradient updates. Nevertheless, the most adopted 𝜓since its publication has been the Generalized Advantage Estimation (GAE) (Schulman et al., 2015), being also the one employed in this Thesis. Generalized Advantage Estimation Analogously to TD(𝜆), GAE is defined as an exponentially-weighted estimator of the advantage function (instead of the value function in TD(𝜆)). In that context, the TD-residual of the value-function is defined as 𝛿𝑉 𝑡=𝑟𝑡+1+𝛾𝑉 (𝑠𝑡+1) − 𝑉(𝑠𝑡), which can be considered as an estimate of the advantage when executing an action 𝑎𝑡that provides a reward 𝑟𝑡and a new state 𝑠𝑡+1. Similarly to the n-step target estimator, now we can calculate multiple advantage estimators by taking into account k-steps of the returns minus 28 Chapter 2. Background been released such as Sonic (Nichol et al., 2018), MiniGrid (ChevalierBoisvert et al., 2018), Obstacle Tower Challenge(Juliani et al., 2019), NetHack (Küttler et al., 2020), Procgen(Cobbe, Hesse, et al., 2020) and XLand (Team et al., 2021) among others. Besides generalization, in the same way as singleton benchmarks, each PCG environment poses its own particular challenges too, such as sparse rewards to analyze the sampleefficiency mentioned in the previous chapter. Throughout this Thesis some hard-exploration mazes from MiniGrid (Chevalier-Boisvert et al., 2018) are employed, where the agent has a partial egocentric view (POMDP) of the environment and its objective is to reach a given destination, being each level’s configuration different despite the task is kept fixed. See some examples in Figure 2.7. The employed tasks in this Thesis are deemed sparse rewards problems because the agent only gets a non-zero reward when accomplishing the goal, i.e., R(𝑠𝑡, 𝑎𝑡, 𝑠𝑡+1)=(1−0.9·𝑡 𝑡𝑚𝑎𝑥 ,if 𝑡 < 𝑡𝑚𝑎𝑥 and 𝑠𝑡+1is terminal 0,otherwise (2.23) being 𝑡𝑚𝑎𝑥 the maximum number of steps per episode in each problem/task. Remark that the probability of achieving the goal by randomness is too small to learn a valid policy with any state-of-the-art (SOTA) RL-algorithm. Further details can be found later in this manuscript when those environments are employed as benchmark. 2.3 Exploration Strategies When should the agents explore? It is a relevant question still unsolved and apparently highly problem dependant (Pîslar et al., 2022). The explorationexploitation dilemma becomes fundamental in sparse reward formulations where the probability of getting a valuable feedback from the environment is close to zero in almost all the cases, 𝑝(𝐺𝑡=𝑟𝑡+1+𝛾𝑟𝑡+2+... ≠0) ≈ 0, which leads to a huge amount of uninformative interactions. In this context, acting greedily – exploiting the information that the agent already knows – is synonym of failure or very poor performance. Hence, the exploration becomes essential. Along the literature two main exploration strategies can be listed(Thrun, 1992): Undirected exploration and Directed Exploration. The undirected exploration strategies focus on injecting randomness into the action selection to promote the discovery of new states without taking into account the information of the environment. Typically, they tend to be simple and have good results in small state spaces and dense reward formulations, albeit struggle and inefficient in the opposite situations. In this category, algorithms random-walks (Anderson, 1986; Nguyen & Widrow, 1989), 𝜖-greedy (Sutton, 1995; Watkins & Dayan, 2.3. Exploration Strategies 29 Figure 2.7: Rendering of PCG MiniGrid’s MultiRoom-N7-S8 ≡MN7S8 (top row), KeyCorridor-S3-R3 ≡KS3R3 (middle row) and ObstructedMaze-2Dl ≡O2Dl (bottom row) environments across three different levels. Each episode is generated with a different seed so that the configuration of objects and the initial spawn position (and orientation) of the agent are different. As a consequence, a huge number of diverse levels for the same tasks can be generated. 1992; Whitehead & Ballard, 1991) and Boltzmann distribution strategies (Cesa-Bianchi et al., 2017; L.-J. Lin, 1992; Sutton, 1990) are included11. Contrarily, directed exploration techniques memorize exploration specific knowledge to guide the future agent’s behavior. The Upper Confidence Bound (UCB) (Auer et al., 2002) was one of the first approaches to implement this by estimating the expected return along with a measure of 11These methods always use some kind of parameter – 𝜖(in 𝜖-greedy) or 𝜏(Boltzmann) to define the probability/frequency of selecting the greedy action or a random one. Just to clarify, the Boltzmann (or Gibs) distribution can be seen as a soft-max distribution (Equation (2.13)) over the possible 𝑄(𝑠𝑡,·)-values/probabilities given by 𝜋(·|𝑠𝑡)where the distribution is subject to a energy/temperature factor,𝜏: exp 𝑄(𝑠,𝑎) 𝜏/Í𝑘exp 𝑄(𝑠,𝑘) 𝜏. 30 Chapter 2. Background the uncertainty for each action: 𝑎𝑡=arg max 𝑎"𝑄(𝑠𝑡, 𝑎𝑡) + 𝑐√︄ln(𝑡) 𝑁𝑡(𝑎)#(2.24) where the first term, 𝑄(𝑠𝑡, 𝑎𝑡), stands for the expected return, whereas the second term, √︃𝑙𝑛(𝑡) 𝑁𝑡(𝑎), specifies the uncertainty of selecting an action (𝑎) considering the number of times (𝑁𝑡) that action was taken until that time step (𝑡). That is, the first component aims to select the action that leads to the highest return (exploitation), whereas the second promotes the selection of actions inversely proportional to the number of times that they have been selected (exploration). Such exploration-exploitation trade-off is ultimately controlled by the hyperparameter 𝑐≥0. This idea fostered the proposal of Intrinsic Motivation (IM) methods, recently centered on generating intrinsic rewards to explore and discover new behaviors more efficiently, which is of utmost importance in sparse rewards settings to learn the optimal policy with the minimum amount of agent-environment interactions. Below some of the most popular IM approaches that are going to be discussed in the following Chapters are detailed. Thereafter, Imitation Learning (IL) is also explained, and further discussed in Chapter 5, as an alternative approach when counting on expert demonstrations. 2.3.1 Intrinsic Motivation By letting the agent explore the environment for its inherent satisfaction rather than for other exogenous stimuli, new behaviors emerge. In fact, this is related to psychology and how the babies can learn different skills in the early stages of their human life without additional feedback from the world (Grigorescu, 2020; Oudeyer et al., 2016; Ryan & Deci, 2000). IM methods, also referred to as curiosity or novelty, endow the agent with the ability of learning behaviors that are separate from their main task (Aubret et al., 2019) (task-agnostic exploration/behavior). This property becomes particularly interesting in the absence of explicit feedback from the primary task, as the agent is encouraged to learn a secondary goal (intrinsic-goal) that will eventually drive it to achieve the main objective (extrinsic-goal). This idea is formalized in an intrinsic reward (𝑟𝑖 𝑡) that is combined with the extrinsic reward provided by the environment (𝑟𝑒 𝑡) at each time step 𝑡through a weighting factor 𝛽: 𝑟𝑡=𝑟𝑒 𝑡+𝛽𝑟𝑖 𝑡.(2.25) In this context, several approaches can be found in the literature to generate the exploration bonuses. 2.3. Exploration Strategies 31 Count-based methods One mechanism to generate the aforementioned intrinsic rewards is by adopting a visitation count strategy, also known as count-based methods. Similar to UCB’s exploration component (Equation (2.24)), the rationale is that the agent should be less curious in those states with less novelty. That is, the exploration bonus is inversely proportional to the number of times (𝑁(𝑠𝑡)) a given state (𝑠) has been visited. The most common approach is to define 𝑟𝑡 𝑐𝑜𝑢𝑛𝑡𝑠 =1/𝑁(𝑠𝑡)1/2=1/√︁𝑁(𝑠𝑡)(Strehl & Littman, 2008), although other alternatives without the square root (Kolter & Ng, 2009) or other exponential magnitudes to get the desired bonus decay (i.e., how smoothly the magnitude decreases, see Figure 2.8) can also be utilized. Figure 2.8: Visitation count bonus decay for different square values 𝛽 𝑁(𝑠𝑡)𝑒𝑥 𝑝_𝑣𝑎𝑙𝑢𝑒 for 1000 consecutive visits. The magnitude parameter is proportional to the selected numerator value, usually weighted with a parameter 𝛽. The particular case of 𝛽=1is illustrated. This is a simple, yet effective, solution to quantify the degree to which a state is unknown for the agent. However, this is only possible when dealing with discrete state spaces. Contrarily, when having more complex domains with continuous state spaces other solutions are needed. One option is to discretize it by creating tiles/bins to embed multiple values at once. Other alternatives have been fruitfully: density models to measure the uncertainty and henceforth compute the bonus (Bellemare et al., 2016; Ostrovski et al., 2017), hashes to encode the states in a discrete manner 32 Chapter 2. Background (Tang et al., 2017) or successor representations to leverage similarities for the exploration bonus generation (Machado et al., 2019). Prediction-error methods On the other hand, the intrinsic reward can be computed as the predictionerror when predicting the consequence of an agent’s action in the environment; that is, measuring the predictability of the changes in the environment. The intuition in these methods is clear: the better the prediction, the more often might that situation has been encountered and the lower the novelty bonus should be. Intrinsic Curiosity Module (ICM) (Pathak et al., 2017) was a game changer and distinct itself from other previous prediction approaches (Houthooft et al., 2017; Stadie et al., 2015) because it focuses on a smaller feature space to compute the expected changes that affect the prediction. Such a feature space is built to model the transitions between consecutive steps that were controlled by the agent or that directly affect it; while ignoring the rest. This was accomplished by using an inverse dynamics model in a self-supervised manner to predict the agent’s action (b𝑎𝑡) given the current (𝜙(𝑠𝑡)) and next state (𝜙(𝑠𝑡+1)) embeddings, so that only things affecting to the agent were modeled to obtain the desired feature space. At the same time, that embedding space (𝜙(𝑠𝑡)) altogether with the actual action (𝑎𝑡) is used to train a forward dynamic model (Stadie et al., 2015) that predicts the feature representation in the next state (b 𝜙(𝑠𝑡+1)), which in last instance is compared against the latent representation of the next state in the previously modeled feature space (𝜙(𝑠𝑡+1)) to compute the intrinsic reward (𝑟𝑖 𝑡), see Figure 2.9. ϕ(st) ϕ(st+1) b ϕ(st+1) st st+1 bat at ri t ICM Features Features Forward model Inverse model − Figure 2.9: Intrinsic Curiosity Module (ICM)(Pathak et al., 2017), where the generation of the intrinsic reward 𝑟𝑖 𝑡is illustrated. The intrinsic reward is computed as the prediction error in the feature space of the next state, that is, the difference between b 𝜙(𝑠𝑡+1)and 𝜙(𝑠𝑡+1)given 𝑠𝑡, 𝑠𝑡+1and 𝑎𝑡. 2.3. Exploration Strategies 33 Later on, (Burda, Edwards, Pathak, et al., 2018) conducted a largescale study based on these prediction errors over 54 environments without any extrinsic reward –purely guided by intrinsic behaviors– in which they analyzed the efficacy of using various feature learning methods. In other words, they investigated the effect of using different feature spaces – 𝜙(·)– such as relying on pixels, random features, variational audoencoders (Kingma & Welling, 2014) and the previously introduced inverse model (Pathak et al., 2017). One important remark is that they brought up the noisy-TV problem on this kind of algorithms: the agents tend to be attracted by stochastic dynamics of the environment which was clearly exemplified by introducing a TV into the environment that changed the channels randomly independently of the agent’s actions. In order to solve this issue, (Pathak et al., 2019) proposed the use of an ensemble of forward dynamics models so that the reward was computed taking into account the variance with respect to their next state prediction; hence, they are not sensitive to agent’s impact on the environment changes but to the parts of the environment that have been largely/shortly explored (the more a state has been visited, the less the disagreement between the outcome of all the forward models and the less variance even in a stochastic situation). Another idea is to use an episodic memory so that the distance/proximity –referred to as reachability in the paper– of past instances in reference to the current state can be measured (Savinov et al., 2019); in other words, how many steps away is the agent from experiencing those situations again. The episodic novelty module idea was extended and combined with a lifelong novelty module so that curiosity across the episode and the whole training was modulated yielding new SOTA results in some benchmarks (Badia, Sprechmann, et al., 2020). Special mention deserves Random Network Distillation (RND) (Burda, Edwards, Storkey, et al., 2018), which became popular due to its simplicity and good performance. Thi is the reason why it was picked over other prediction-error methods for this Thesis. In this strategy, two neural networks are required: a target 𝜙(·), and a predictor b 𝜙(·). Both of them are initialized randomly and the target’s parameters are frozen thereafter. The predictor’s goal is to mimic the target network’s output, so that the outcomes are as close as possible. Therefore, the intrinsic reward measures the closeness through: || b 𝜙(𝑠𝑡+1) − 𝜙(𝑠𝑡+1)||. As the predictor keeps learning to imitate the target, the intrinsic reward is supposed to be smaller and smaller as a reflection of the number of cumulative state visits, so that the curiosity concept about exploring novel states is satisfied. The authors identify three main factors to be relevant source of prediction errors: •Factor 1. Prediction error is high when the predictor fails to generalize from previously seen data. •Factor 2. Prediction error is high because the target is stochastic. •Factor 3. Prediction error is high because necessary information for the predictor is not given (or the model capacity is too limited to accurately predict the target). 34 Chapter 2. Background The last 2 factors can induce the aforementioned noisy-TV problem. Hence, RND was designed to overcome those undesired properties by fixing the prediction problem with a deterministic target and having two replicates of the same ANN architecture, so that the prediction error is not limited by the model capacity or architecture. Last but not least, it is important to emphasize that when using intrinsic rewards the problem becomes bi-objective and the agent is accordingly going to optimize both goals12. Nevertheless, unexpected behaviors can arise in these settings due to an excessive exploration that hinders the exploitation of the main task (Badia, Sprechmann, et al., 2020; Rosser & Abed, 2021; Taïga et al., 2020). Most of the approaches neither control nor balance the importance of the extrinsic and intrinsic components during training. This is based on the following assumptions: •The scale of both rewards is very different: very low intrinsic values in comparison to the extrinsic ones. As a result, possible goal-deviation occurs mainly in the absence of extrinsic rewards. •Intrinsic rewards are non-stationary in nature. Their magnitude, regardless of 𝛽, decreases on average throughout the training as the state space is explored, resulting in an even larger difference between the two types of rewards/goals. However, these assumptions sometimes are not enough and other solutions are required. Among those examples, there are meta-learning approaches where the functions that parameterize the intrinsic rewards are influenced by the direction of the extrinsic gradient(Dai et al., 2022; Du et al., 2019; Z. Zheng et al., 2018) (ensuring that the main extrinsic objective is aligned with the exploration component too), while other frameworks propose to directly decouple the two goals into different agents (E. Z. Liu et al., 2021; Schäfer et al., 2022). 2.3.2 Imitation Learning Another solution to overcome exploration problems is the use of expert demonstrations, which is also known as Imitation Learning (IL) and/or Learning from Demonstrations (LfD)(Hester et al., 2017; Vecerik et al., 2018). Within this framework, good (optimal or suboptimal) trajectories are assumed to be provided, 𝜏∗={(𝑠0, 𝑎0, 𝑟0, 𝑠1),(𝑠1, 𝑎1, 𝑟1, 𝑠2), ...}, so that the agent can use those tuples to pre-train or even master a policy in an online fashion that prevents the agent from getting stuck in the early phases of the training (where no expertise is still developed). Nevertheless, key aspects such as different embodiment and observability between the expert and the learner make challenging its success application (Osa et al., 2018). Depending on how the demonstrations are used to distill the knowledge, two ways of learning can be found: Behaviour Cloning (BC) and Inverse Reinforcement Learning (IRL). 12Recall that the agent maximizes the return (Equation (2.3)) in which the considered reward has now a new explorative component (Equation (2.25)). 2.3. Exploration Strategies 35 On the one hand BC (Bain & Sammut, 2001; Pomerleau, 1988; Torabi et al., 2018) seeks to learn a policy through a mapping strategy where a given input is associated to an action; this is, it just requires stateaction tuples, 𝜏∗={(𝑠0, 𝑎0),(𝑠1, 𝑎1,), ...}. Standard supervised learning methods such as the log loss function (which can be embedded within a Cross Entropy loss (Gneiting & Raftery, 2007)) are used to map the probability of selecting an action to the specified input, which augments its future probability preference: 𝐿𝐵𝐶 =−1 |𝐷|∑︁ (𝑠,𝑎) ∈𝐷 ln(𝜋(𝑎|𝑠)) (2.26) where 𝐷refers to a pool of data where the demonstrations are contained and from the tuples are sampled. Nevertheless, these approaches suffer from compounding errors (Ross & Bagnell, 2010) derived from the fact that the policy to be updated exhibits different probabilities of collecting experiences with the assumed expert policy that provides samples. This is, a distribution shift exists in the sampling probability of trajectories (recall Equation (2.16)) between the policy that gathered the demonstrations and the policy that is being learned. Consequently, the future test data are influenced by the policy that is being learned, breaking the main assumption of most SL methods that assume the data to be independent and identically distributed (recall Chapter 1when we explained the differences between RL and SL). Therefore, one of the most popular BC algorithms up to date – Dataset Aggregation (DAGGER) (Ross et al., 2011)– proposed to aggregate additional online data to the dataset used for training (D), with the particularity that the visited states are subject to the learned policy distributions (𝜋(𝑎𝑡|𝑠𝑡) −→ 𝑠𝑡+1) but the stored action in each state is the expert’s (𝑎∗ 𝑡+1∼𝜋∗(𝑠𝑡+1)), so that 𝐷∪ {𝑠𝑡+1, 𝑎∗ 𝑡+1}. Alternatively, IRL(Finn et al., 2016) aims to learn the hidden reward function from the provided experiences under the assumption of being optimal (or very close to optimal) demonstrations. To do so, it uses that function to obtain rewards from which the agent’s policy is learned, 𝜏0, 𝜏1, ... −→ Rℎ≈ R;b𝑟𝑡∼ Rℎ(𝑠, 𝑎)13. These methods are highly sensitive to how good the reward function represents the desired (optimal) behavior. Within this taxonomy, adversarial IL methods can be taken into account too (Ho & Ermon, 2016; Ho et al., 2016), where the policy parameterizes a generative model that "creates" new experiences and the cost function (i.e., reward function) serves as an adversary. In summary, the selection of one or another approach will depend on whether the BC’s learned policy represents a valid mapping from states to actions or if IRL’s distilled reward function is valid to learn a suitable policy for the desired behavior. Furthermore, the criteria is also subject to the availability of a model that makes possible the use of dynamics information of the environment (Osa et al., 2018). 13For simplicity, the calculated reward function is shown to be dependant on the state and action, although it can also be subject to the next state. 37 Chapter 3 Collaborative training between Heterogeneously skilled Agents in Environments with Sparse Rewards Designing a reward function is one of the most challenging steps when formulating a problem that is meant to be solved with RL. As we have previously highlighted in Section 1.1, one way to overcome this cumbersome design is by using a single (sparse) reward signal that determines whether a RL task has been solved. In this context, the problem becomes more complex due to the lack of dense feedback signals that guide the learning process, ultimately hindering the correlation between successfully solving the task and the successive actions that lead to that outcome. To address this issue, a solution is to generate an exploration bonus (intrinsic reward) that promotes the novelty (motivate the agent) within the environment. This approach encourages diverse behaviors and enables the discovery of valid solutions through exploration, thereby fostering goal achievement. The family of algorithms that can generate these bonuses are known as Intrinsic Motivation (IM) techniques, which have been introduced previously in Section 2.3.1 of Chapter 2. Their utility can be better understood from the intuition gained from the following real-world example: A bike rider wants to descend a given mountain across the shortest path and as fast as possible. However, the rider does not know the mountain, and the unique feedback signal will be received at the end of the route. Thus, the rider does not know whether the decision in a bifurcation is right, if they get stacked close to the final line, or even if they spend too much time when compared to other bikers. Due to so much uncertainty without feedback signals, the agent (bike rider) should drive their decisions based on their own motivation and curiosity. A first question arises when examining this real-world example: what 44 Chapter 3. Collaborative Training of Heterogeneous Agents search space. This implies a two-sided competition where the non-skilled agent drives the skilled one into a longer path solution, whereas the skilledagent pushes the former to take the shortcut that is not reproducible for it. Consequently, negative transfer problems may well arise. This situation can be observed from their value estimate difference which, as shown in Figure 3.1.b, differ remarkably from each other at critical points (near the corridor). These issues can be understood even clearer if the problem is represented as a MDP tree (Figure 3.2), in which the agents will have a share-view of the environment as long as they can reproduce the same trajectories. Nonetheless, some states will only be visited by one agent due to special capacities of its action space, generating an independent view of the problem for that particular agent. S0 S1 a0 a1 a2 a0 a1 a2 a0 a1 a1 S3 S4≡S7(terminal state) : Independent view (skilled agent) : Shared view (both agents) S4 S5 S2 a0 S6 S7 a1 {a0, a1, a2}∈Askilled {a0, a1}∈Anon−skilled Figure 3.2: Example of a MDP as a tree where states are represented with nodes and the edges denote actions. Some states (e.g., 𝑆3) can be reached by being in a specific state and executing a certain action (e.g., 𝑆1 𝑎2 −−→ 𝑆3). This results in parts accessible and shared between agents (shared-view) and others that are restricted to the capacities of the agents (independent-view). These problems are not limited to the example shown in the above plot, but also to any scenario with heterogeneous agents. The contribution of this chapter is to expose this problem, and to sketch effective collaborative learning strategies under such circumstances. 3.3 Proposed Collaborative Framework The design of the framework proposed in this chapter roots in the fact that there can be observations where the policy distributions of heterogeneous agents can be very similar to each other. In some cases, both agents can push each other towards the same direction, i.e., 𝜋𝑠𝑘𝑖𝑙𝑙𝑒𝑑 ≡𝜋𝑛𝑜𝑛𝑠𝑘𝑖𝑙𝑙𝑒𝑑. However, in other cases those distributions can differ from each other because each agent pushes in a different direction based on their optimal solution learned at that time. In this situation, we aim to strengthen the shared knowledge between both of them, yet at the same time, to avoid negative transfer in places where the optimal solutions of each agents are in conflict. Consequently, the goal of the framework is to learn a sharedknowledge view while respecting those subspaces in the environment where the interest of the agents are not the same. 3.3. Proposed Collaborative Framework 45 As already explained in previous sections, in problems characterized by sparse rewards the main issue to deal with is an efficient exploration of the environment. The application of IM and on-policy techniques does not permit to interfere in the action-sampling process directly, as the training experiences have to be representative of the current policy, i.e., 𝑎∼𝜋(𝑠). Hence, the use of past experiences or even samples collected by other policies is not tractable3. In this case, the policy is optimized as per Expression 2.14 where, aside from the inherent mechanism of the algorithm itself, the advantage estimator b 𝐴𝑡is the main factor that eases and pushes the learning process4. The latter advantage estimator can be estimated in different ways, but almost all of them are correlated to the reward 𝑟𝑡+1 and the value function 𝑉(𝑠𝑡)through the TD-error: 𝛿=𝑟𝑡+1+𝛾𝑉 (𝑠𝑡+1) − 𝑉(𝑠𝑡)(3.1) whose value changes iteratively as soon as 𝑉(𝑠𝑡)gets updated. This process can be said to converge when 𝑉(𝑠𝑡)=𝑉∗(𝑠𝑡). The framework described in what follows aims at accelerating the learning process focusing on the exploration part, more concretely in how to generate better advantages. For that purpose, we propose a framework driven by two different design objectives (DO): •DO1: How to generate more accurate and faster state value estimates 𝑉(𝑠). •DO2: How to modify the intrinsic reward generation process to be tackled more efficiently when dealing with heterogeneous action spaces. Next, multiple methods are proposed to address these objectives within a collaborative framework (see Figure 3.3), so that the ongoing ablation studies in Section 3.5 can inform about the best options among the postulated methods. For simplicity, hereinafter we consider only 2 heterogeneous agents, skilled and non-skilled, although the approaches could be extended to work with more agents. 3.3.1 Centralized Learning with Decentralized Execution Our framework adopts an actor-critic policy gradient architecture with two separated networks: •An actor whose policy (one for each agent) is fed just with its local observations. •A critic with two output heads related to the extrinsic (𝑉𝑒) and intrinsic (𝑉𝑖) signals that is trained with the observations gathered by all the agents. 3Not tractable at least theoretically without any type of correction, such as importance sampling (Christianos et al., 2020; Schäfer et al., 2022). 4We assume 𝜓=𝐴𝑡. 46 Chapter 3. Collaborative Training of Heterogeneous Agents at ACT ORID Ve t Vi t b Ae(st, at) b Ai(st, at) b Atotal = b Ae(st, at) + β b Ai(st, at) Ge t Gi t O(st, at) = ot+1 ri t INTRINSIC MOTIVATION MODULE ENVIRONMENT re t PPO loss GAE Observation MSE loss CRITIC ACTOR Figure 3.3: Flowchart of the collaborative framework, where we highlight in blue those modules that are usually performed independently for each agent, and that can be shared in our framework. The core idea is to have a unique and centralized critic, so that its capabilities can be augmented with additional information corresponding to the different agents solely during the training phase. This strategy is also known in the literature as the centralized learning with decentralized execution (CLDE) paradigm (Foerster et al., 2017; Lowe et al., 2017). With this design, we aim to expedite the critic’s learning process so as to generate more accurate and faster value estimates, contributing to DO1. Moreover, it gives rise to a scalable architecture which can easily take into account more agents with little additional complexity. 3.3.1.1 Decentralized Actors In spite of using centralized learning strategy, the behavior of each agent can be very similar yet not equal. As a consequence, each agent is parameterized by an independent actor5. As above explained, the benefit of CLDE relies on learning faster and more accurate 𝑉(𝑠), which subsequently has a positive effect on 𝐴(𝑠, 𝑎), ultimately leading to an improved overall learning. However, the speed at which this is achieved depends on multiple factors. All this coupled with the fact of transient intrinsic rewards (𝑟𝑖 𝑡) and sparse extrinsic feedback (𝑟𝑒 𝑡), increased the importance of introducing Monte Carlo updates to latch on to these signals rapidly (Bellemare et al., 2016; Ostrovski et al., 2017). In our framework, this is instead circumvented by using GAE (Schulman et al., 2015) and calculating two independent advantages for the extrinsic and intrinsic streams, 𝐴𝑒(𝑠, 𝑎)and 𝐴𝑖(𝑠, 𝑎), which are then blended as 5For practical purposes, their learning works in the same way as when being done independently. That is, the actor is trained only with data captured by itself as it would do in a single agent scheme. 3.3. Proposed Collaborative Framework 47 follows: 𝐴(𝑠, 𝑎)=𝐴𝑒(𝑠, 𝑎) + 𝛽𝐴𝑖(𝑠, 𝑎)(3.2) This implies having extrinsic (𝑉𝑒) and intrinsic (𝑉𝑖) streams with their respective independent returns, which allows for a higher flexibility to combine episodic and non-episodic returns. It also enables the use of different discount factors (i.e., 𝛾𝑒and 𝛾𝑖). Moreover, it is intuitively more suitable to separate both streams that are indeed stationary (𝑉𝑒) and nonstationary (𝑉𝑖) in nature. The extrinsic reward in a singleton environment has an associated 𝑉𝑒∗because the extrinsic reward function does not change throughout the learning process6. On the contrary, 𝑉𝑖∗will vary as the training evolves because the generated intrinsic rewards depend on a novelty measure that changes right after every interaction. Note that combining in this way the extrinsic and intrinsic streams is just another strategy (Burda, Edwards, Storkey, et al., 2018) that substitutes the naive idea of mixing both objectives in a weighted reward as in Equation (2.25). 3.3.1.2 Centralized Critic Module When conceived within collaborative learning, a problem that requires attention is that the value function estimates, 𝑉(𝑠), can be different among agents for the same state, although it might be equal or very similar at many other states of the same scenario (recall Figure 3.1). Based on this intuition, the value of a state should depend not only on the state itself, but also on the possible actions of the agents. Henceforth, we propose to use a centralized action-value function, 𝑄(𝑠, 𝑎)which, as shown in Figure 3.4, is fed with the observations of all agents, producing the value estimate of selecting an action 𝑎𝑡when being at state 𝑠𝑡. This is, instead of producing an estimation for the state value 𝑉(𝑠), the centralized module elicits all 𝑄(𝑠, 𝑎)possible values for 𝑎∈ A𝑠𝑘𝑖𝑙𝑙𝑒𝑑 ∪ A𝑛𝑜𝑛−𝑠𝑘𝑖𝑙𝑙𝑒𝑑, regardless of the agent collecting the observation. Centralized Critic Module oskilled t onon−skilled t . . . aN a2 a1 . . . . . . {a0, a1, . . . , aN}=Askilled ∪ Anon−skilled πnon−skilled Q(ot, an) Environment Anon−skilled πskilled Vt=PA aπ(a|ot)·Q(ot, a) Askilled being π and A or Figure 3.4: Centralized critic module based on 𝑄(𝑠, 𝑎)(instead of 𝑉(𝑠)) for 2 agents with different action spaces (A𝑠𝑘𝑖𝑙𝑙𝑒𝑑,A𝑛𝑜𝑛−𝑠𝑘𝑖𝑙𝑙𝑒𝑑). In the image, how 𝑉𝑡(𝑠)is calculated for each case is shown. This architectural change of the critic module implies several considerations. To begin with, 𝐴(𝑠, 𝑎), which is one of the key components for 6We are not considering environment with stochastic transitions. 48 Chapter 3. Collaborative Training of Heterogeneous Agents the calculation of the the actor’s loss, commonly requires a value estimate –𝑉(𝑠)(not 𝑄(𝑠, 𝑎))– to reduce its variance (Schulman et al., 2015). Therefore, we calculate different state values 𝑉𝑥(𝑠)for each agent by taking into account their action spaces, as follows: 𝑉𝑥(𝑠)=∑︁ 𝑎∈A𝑥 𝜋𝑥(𝑎|𝑠) · 𝑄(𝑠, 𝑎)(3.3) where 𝑥∈ {𝑠𝑘𝑖𝑙𝑙𝑒𝑑, 𝑛𝑜𝑛 −𝑠𝑘𝑖𝑙𝑙𝑒𝑑}and 𝜋𝑥(𝑎|𝑠)denotes the probability of each agent 𝑥performing action 𝑎∈ A𝑥in state 𝑠. Thus, an agent not capable of executing a given action will have a zero probability for that given option. This can be also regarded as a way of masking possible outcomes. Additionally, the critic loss is slightly modified to accommodate the multiple action-wise outputs as opposed to the unique output neuron usually set when critic estimates directly the value of the state itself. Namely: L𝑐𝑟𝑖𝑡𝑖𝑐 =1 𝑇 𝑇 ∑︁ 𝑡=0𝑄(𝑠𝑡, 𝑎𝑡) − b 𝑄𝑡2 ,(3.4) where 𝑎𝑡is the action taken by the agent at time step 𝑡, and b 𝑄𝑡is a discounted return estimate of the 𝑇-length rollout over which the optimization step is performed. Last but not least, the critic is updated with the tuples gathered by each agent individually, and executes an optimization step per collected batch of experiences: B𝑠𝑘𝑖𝑙𝑙𝑒𝑑 ={(𝑠𝑡, 𝑎𝑡, 𝑟𝑡),(𝑠𝑡+1, 𝑎𝑡+1, 𝑟𝑡+1). . . , (𝑠𝑇−1, 𝑎𝑇−1, 𝑟𝑇−1)} ∼ 𝜋𝑠𝑘𝑖𝑙𝑙𝑒𝑑 B𝑛𝑜𝑛−𝑠𝑘𝑖𝑙𝑙𝑒𝑑 ={(𝑠𝑡, 𝑎𝑡, 𝑟𝑡),(𝑠𝑡+1, 𝑎𝑡+1, 𝑟𝑡+1). . . , (𝑠𝑇-1, 𝑎𝑇-1, 𝑟𝑇-1)} ∼ 𝜋𝑛𝑜𝑛-𝑠𝑘𝑖𝑙𝑙𝑒𝑑 As a consequence, the critic will take as many optimization steps in every training step as the number of agents at hand (in the considered case, 2 updates with B𝑠𝑘𝑖𝑙𝑙𝑒𝑑 and B𝑛𝑜𝑛−𝑠𝑘𝑖𝑙𝑙𝑒𝑑). Universal Value Function Approximator An alternative to the previous proposed centralized critic is to adopt a so-called Universal Value Function Approximator (UVFA) design (Schaul et al., 2015), where the ANN will be conditioned to additional parameters (i.e., to a determined goal 𝑉(𝑠, 𝑔)). Actually, in the proposed framework the value estimation is subject to the agent’s capabilities: 𝑉(𝑠) −→ 𝑉(𝑠, 𝑎𝑐𝑡𝑜𝑟𝑖𝑑)(3.5) Indeed, with the previously mentioned action-value architecture modification, it will be 𝑄(𝑠, 𝑎, 𝑎𝑐𝑡𝑜𝑟𝑖𝑑 )as shown in Figure 3.5. Analogously to the procedure followed for the other critic architecture, advantages will be 3.3. Proposed Collaborative Framework 49 calculated with value estimates that will be obtained as in Expression 3.3. {at,actorid} ht ht−1 ot CNN FLATTEN Qi(ot, at) Qe(ot, at) FC Recurrence FC module FC FC Figure 3.5: UVFA based centralized critic, where the convolutional (and the following FC) layers extract common features to both type of agents. The rest of the network is parameterized subject to the skills of each agent. The design is inspired by the idea that the feature extraction of an observation can be linked to an agent but not to the additional information that can be inferred from a sequence. In this latter case, it could be inconsistent due to the agent’s different capabilities to generate their own divergent trajectories that might well not be reproducible by other agents. In order to address this inconsistency during the training stage, and to aid the network in gaining insights about what knowledge must be shared and what must be preserved for individual use, information about the skills is provided to the network as an input (𝑎𝑐𝑡𝑜𝑟𝑖𝑑)7. In addition, the action in every time step 𝑎𝑡is also fed as an input, which can be useful to learn better temporal representations within the recurrent module. Other parameters such as the trade-off between intrinsic-extrinsic streams (i.e., 𝛽coefficient) or the collected rewards (i.e., 𝑟𝑒 𝑡and 𝑟𝑖 𝑡) could also be advantageous (Badia, Sprechmann, et al., 2020). Nevertheless, the study is limited to the aforementioned parameters in order to avoid over-parameterized critic architectures. Overall, with the design of a centralized critic we aim to have a more robust and stable learning, where the shared-view value estimates of the environment should be easier to obtain, while not hindering the calculation and learning of the independent-view value estimates when the optimal solutions of the agents diverge. This closely aligns with the design objective DO1 established previously. 3.3.2 Centralized Intrinsic Curiosity Module The most straightforward strategy to make the exploration of one agent depend on the exploration performed by others is to combine them by using a centralized module, which is directly related to the intrinsic reward generation (DO2). This idea relies on the principle of divide and conquer, where an observation should be discouraged to be visited if the other agent 7The information is encoded as a one-hot vector distinguishing between agents with different action domains, i.e., 𝑎𝑐𝑡𝑜𝑟𝑖𝑑 𝑠𝑘𝑖𝑙𝑙𝑒𝑑 −−−−−−→ [1,0]or 𝑎𝑐𝑡𝑜𝑟𝑖𝑑 𝑛𝑜𝑛−𝑠𝑘𝑖𝑙𝑙𝑒𝑑 −−−−−−−−−−→ [0,1]. 50 Chapter 3. Collaborative Training of Heterogeneous Agents Start Door Goal (a) (b) (c) (d) (e) Figure 3.6: Evolution of the intrinsic rewards in a simplistic RL environment after 10 executions according to the number of visits (i.e. 𝑟𝑖=1/√︁𝑁(𝑠)). The agent is initialized at the bottom-left corner and its goal is to arrive to the destination located at the bottom right. Going straight, in the middle is a door that obstructs the path, which can be only be opened by a skilled agent. (a) Intrinsic rewards heatmap of a skilled agent able to traverse the corridor through the door and go straight. (b) Intrinsic reward heatmap of a non-skilled agent not capable of opening the door, hence arriving at the target through the larger path. (c) Resulting intrinsic reward heatmap when combining both type of agents’ visits for a total of 10 executions per agent (20 in total). (d) Relative difference of rewards using the centralized novelty (as in subfigure (c)) with respect to using two skilled agents (subfigure a) for the same amount of interactions. (e) Relative difference of rewards using the centralized novelty (subfigure (c)) with respect to using two non-skilled agents (subfigure b) for the same amount of interactions. In (a,b,c) darker colors mean higher reward; brighter the opposite. In (d,e) red means that the centralization with heterogeneous agents encourages visiting those locations more often with respect to using homogeneous agents, yielding higher intrinsic rewards in that location by virtue of having heterogeneous actions (blue the opposite). has already been there, promoting the exploration of uncharted areas. The problem of this assumption is that if agents have different knowledge and/or capabilities, one agent may get discouraged to explore areas that are indeed crucial for finding its own optimal solution and enforced to visit unpromising areas instead. In practice, by using a centralized curiosity approach with multiple heterogeneous agents, the experienced novelty is affected. Let’s see the expected modifications following the example illustrated in Figure 3.6. Firstly, the intrinsic bonuses for those states that can be reached by both agents will be smaller(Figure 3.6.c, yellow areas). By the same token, intrinsic returns should be higher along those trajectories in which the agent visits more novel states. This behavior is exacerbated in those states that are only accessible by one of the agents (i.e., skilled agent, Figure 3.6.a, corridor colored in purple), as they can only be visited by them 3.3. Proposed Collaborative Framework 51 and its novelty decreases at a slower pace when compared to the rest of possible states (Figure 3.6.d, red). Therefore, the skilled agent will end up becoming more encouraged to visit restricted areas – namely, states that are only possible to be accessed by the use of the action that make them to be different – when compared to the behavior in the decentralized intrinsic module approach. In regard to the non-skilled agent, using a centralized curiosity with an additional more skilled agent has little impact in its exploration procedure, as the novelty distribution will undergo no changes for it. Indeed, the parts that are critical for the skilled agent –the door and the corridor– do not influence the exploration of the non-skilled (Figure 3.6.e, corridor). The remaining state space will be similarly visited for both agents. However, if we assume that the skilled agent will be encouraged to visit more times those experiences leading the corridor, inversely the non-skilled agent will be discouraged to go over those same locations. Eventually, the nonskilled agent will be pushed towards exploring other alternatives. This can be observed in Figure 3.6.e, in which the non-skilled agent will be more encouraged to explore through the larger path (as told by the higher rewards colored in red) when combining its rewards with a skilled-agent with respect to doing it independently. In conclusion, adopting a centralized curiosity module can be beneficial when heterogeneous agents are involved. On the one hand, actions yielding observations that can only be achieved by the one of the agents (i.e., open the door and access the corridor) will have larger intrinsic rewards, and hence, higher returns, fostering the exploration of that state space. At the same time, it discourages the agent who is not capable of executing such actions of exploring the state space that guides such non-reproducible situations (i.e., corridor), being advantageous to focus on exploring other promising zones. 3.3.2.1 Action-based Curiosity Module Manifold means of calculating the novelty of a given state have been proposed in the literature. Mechanisms to deal with novelty are based on using either 𝑠𝑡(Bellemare et al., 2016), 𝑠𝑡+1(Burda, Edwards, Storkey, et al., 2018) or even the information related to the transition between successive states {𝑠𝑡, 𝑠𝑡+1}(Pathak et al., 2017)8. In this vein, when having multiple agents using this module in a centralized manner, they update it more frequently with the experiences sampled by their own independent action distributions, leading to different visitation strategies as those depicted in Figure 3.6. Notice that the agent will be discouraged to visit states already inspected regardless the actions taken before. This implies that the agent will have the same curiosity to visit a state and execute an action frequently selected (at that state) as selecting another action that has been barely chosen. Previous works have reported 8The intrinsic reward is generated just with 𝑠𝑡+1, but the update of the whole ICM framework requires 𝑎𝑡,𝑠𝑡and 𝑠𝑡+1. 52 Chapter 3. Collaborative Training of Heterogeneous Agents that no difference arises from considering the action (Tang et al., 2017), speculating that the policy itself was sufficiently random (i.e., had sufficient entropy) to entrust the exploration at each state. This hypothesis, however, was validated over RL environments with single agents whose individual exploration does not interfere with the interaction and learning of other agents. By contrast, when heterogeneous agents are involved, the action selection and its consequent exploration becomes more sensitive. Therefore, we modify those intrinsic related approaches in order to account for the action as well, so that the generated intrinsic rewards become more informative for the critic (DO2). In fact, a strategy that takes into account both the action and the state when computing the novelty will encourage a more homogeneous action selection and a deeper exploration (Raileanu & Rocktäschel, 2020). This difference may not hinder convergence in single-agent RL problems, but can be problematic when having agents with different action spaces. In this latter case, actions that can only be executed by just one agent will become more affected, as shown previously in Figure 3.6. 3.3.2.2 Tree Filtering Previous exploration strategies aim at sharing as much information as possible between the agents. Nevertheless, there might be states embedded in a trajectory that are not accessible by some agents where specific chunks of the trajectory might, in turn, be reproducible. On the one hand, a trajectory can be thought to be shareable for both agents if the actions taken by the agent responsible for gathering the experiences belong to the mutual action space9. On the other hand, let us consider a trajectory gathered by the skilled agent that is not fully reproducible by the non-skilled agent. Can that information be used in some way by the non-skilled agent (rather than being discarded)? This is what tree-filtering is all about. In order to explain it and for the sake of clarity, consider the trajectory shown in Figure 3.7, where we can distinguish two main chunks of experiences: •{(𝑠49, 𝑎2),(𝑠50, 𝑎3), . . .}: From 𝑠49 onward, the whole trajectory is assumed to be reproducible by the non-skilled agent too. In spite of the non-skilled not being responsible of collecting such experiences, the curiosity of both agents at them is updated (i.e., decreased). As a consequence, future returns, and subsequently, their critic estimates, will reflect it10. 9This also applies when selecting an action out of that mutual action space which has no effect on the environment, or which is interchangeable by one of the actions of the mutual action space. 10If the non-skilled agent is not capable of reproducing some of those states, the novelty update, from the perspective of that agent, will be insignificant, as it would never be able to explore that situation; on the contrary, it would assume that an agent with at least the same capabilities would have previously explored them (pretending that the non-skilled agent itself gathered them). 3.3. Proposed Collaborative Framework 53 •{. . . (𝑠45, 𝑎1),(𝑠46, 𝑎1),(𝑠47, 𝑎2),(𝑠48, 𝑎4)}: At state 𝑠48, the skilled agent executed an action that does not belong to the mutual action space, 𝑎4, which is not reproducible by the other agent. Should we then decrease the novelty of the non-skilled agent for all those {𝑠, 𝑎}tuples? If so, that novelty reduction will be noticed when the non-skilled agent collects a trajectory containing any of those experiences and updates the critic. Let us examine the consequences: –Regarding (𝑠48, 𝑎4), no impact will be caused, since this tuple is indeed impossible to be experienced in any trajectory performed by the non-skilled agent. –Nonetheless, for the rest of feasible tuples: {. . . (𝑠45, 𝑎1),(𝑠46, 𝑎1),(𝑠47, 𝑎2)}, the intrinsic reward signal will be lowered, discouraging the nonskilled agent from developing its own exploration strategy on account of an external update of the skilled-agent not playing the role of an equally skilled agent. In order to encourage the non-skilled agent to create its own personal experience, the novelty update of the tuples from 𝑠48 back to the initial state are not performed on the non-skilled agent, allowing it to keep on working on its independent individual view. As a result of this filtering process, we propose to consider novelty along sequences rather than novelty as attractiveness on isolated step-on states11. This is, we aim to minimize the error between the globally generated novelty estimation of paths taking into account the intrinsic rewards generated at each experience and also their reproducibility, thus polishing the intrinsic reward recollection by allowing room for independent views on the environment (DO2). Ideally, the novelty through a path would be handled by a intrinsic curiosity module that takes into account sequences rather than single experiences. However, as we will further elaborate in Section 3.7, the design of such a novelty reward function is not trivial at all. 3.3.3 Summary of the Proposed Modules To sum up, the proposed collaborative framework is composed of a centralized critic and modified intelligent exploration strategies, where: •The use of a centralized critic enhances the learning process by ensuring more diverse experiences. At the same time, a robust knowledge 11In practice, the novelty of a sequence is calculated as the discounted intrinsic return for each the experiences belonging to that trajectory, which is a sum of independent intrinsic bonus as in Expression (2.3). 60 Chapter 3. Collaborative Training of Heterogeneous Agents Table 3.1: Conv2D(A1,A2,B,C,D,E): Convolutional layer with A1 input channels and A2 output channels, B kernel size B, stride C, padding D and activation function E (ELU: Exponential Linear Unit) Network Architecture Training Parameters Actor Conv2D(4,32,3,2,1,ELU)+ Conv2D(32,32,3,2,1,ELU)+ Conv2D(32,32,3,2,1,ELU)+ Conv2D(32,32,3,2,1,ELU)+ Dense(256,ELU)+ Dense(# actions, softmax) Orthogonal initialization Adam optimizer PPO loss Critic Conv2D(4,32,3,2,1,ELU)+ Conv2D(32,32,3,2,1,ELU)+ Conv2D(32,32,3,2,1,ELU)+ Conv2D(32,32,3,2,1,ELU)+ Dense(256,ELU)+LSTM(128)+ Dense(256,ELU)+. . .+ Dense(5) [extrinsic] & Dense(5) [intrinsic] Orthogonal initialization Adam optimizer MSE loss in both critic heads intrinsic returns in order to mitigate issues derive from the reward scale (Burda, Edwards, Storkey, et al., 2018), i.e., : 𝑟𝑖 𝑡=𝑟𝑖 𝑡 𝜎(𝐺𝑖 𝑡(𝜏)) (3.6) Moreover, a crucial matter when using ANN is normalizing the input to prevent several problems. Therefore, it also happens with IM methods that use ANN for the reward generation, but it becomes crucial when using RND13. Hence, the input to the RND modules is standardized and clipped within values between -5 and 5 as follows: 𝑜𝑐𝑙𝑖 𝑝 𝑝𝑒𝑑 =max h−5,min h𝑜−𝜇 𝜎,5ii (3.7) Recall that the latter is only applied when using RND, i.e., only at Setups 1 and 2. More information regarding how RND performs in ViZDooM and why we decided not to use it at Setup 3 can be found at Appendix A). 3.4.4 Evaluation Metrics In general, the main goal of knowledge reuse in RL is to accelerate the learning process. In order to analyze the benefits of using knowledge transfer, different metrics can be used (Taylor & Stone, 2009). However, a 13The target network has its parameters fixed (frozen) and cannot adjust its values according to the train data. Consequently, the obtained embeddings might not convey enough meaningful information and could result in high variance outcomes. 3.4. Experimental Setup 61 framework could report similar performance metrics to other possible options, but could still remain of interest due to other factors related to the training procedure, such as the number of required samples, the training time for a given computational power, and model complexity/size, among other factors. Consequently, discussions on the experimental results later held in this chapter consider two performance scores: •Average extrinsic result (also referred to as Success Rate, SR), which is calculated as the average extrinsic score obtained through a window of the last 100 episodes. •Number of steps to achieve the goal, measured from the starting point of the scenario until the agent reaches the target. The reason for considering these two scores is that, by only inspecting the SR metric, the discussion only regards whether agents have reached the goal, disregarding the required number of steps (which represent the quality of the learned policy). Other works using this environment assume that no rewards are given except when arriving to the goal, when they actually give a small penalization referred to as living reward, equal to −0.0001 for each step. This small modification yields an optimal average extrinsic return of 0.97 approximately for 270 steps; this is, they have a reward function that parameterizes the optimality of the results subject to the number of steps. We instead fix a null living reward, and give a reward equal to 1 when achieving the goal (independent of the number of steps). In this way, we stand strict in regards to the sparse reward problem formulation. Moreover, the environment itself is slightly different depending on the action space of each agent. Hence, in this case the skilled agent has different possibilities to achieve the target, being optimal the one that involves going through the corridor (labeled in what follows as _OPT). Therefore, we trace not only whether every agent reaches the target, but also if they navigate through their optimal paths. Summary On the one hand, Case Study 1 analyzes the impact of a standard centralized critic approach while using either an independent or a centralized RND-based curiosity module. Setup 1 and Setup 2 establish a corridor in different places (Figure 3.8) while allowing the agent to spawn at various locations based on the selected setting. More importantly, the agents’ policies differ due to the presence of a crouch and move forward action in the policy of the skilled agent. On the other hand, Case Study 2 examines a more sophisticated centralized critic design (with an UVFA architecture and LSTM layers). Instead of using RND, visitation counts are used to compute the curiosity and to assess the impact of making the latter independent, centralized and subject to the action space. In addition, it adopts a more challenging setup 62 Chapter 3. Collaborative Training of Heterogeneous Agents (Setup 3, Figure 3.10), where agents differ due to the existence of an open action for the skilled agent to open a gate and access the corridor. As a result of the above case studies, different algorithmic configurations are considered (summarized in Table 3.2): •Full Independent PPO (PPO): the baseline PPO algorithm. •Independent Curiosity (IC_IC): the PPO algorithm with independent curiosity (IC) and independent critics (IC). –Independent Curiosity (IC_IC_3r): Uses 3 parallel environments/runners to collect experiences. –Independent Curiosity (IC_IC_6r): Uses 6 parallel environments/runners to collect experiences. •Independent Critic + Centralized Curiosity (IC_CC): both agents share a unique/centralized curiosity module yet they have independent critics. •Centralized Critic + Independent Curiosity (CC_IC): both agents share a unique/centralized critic, but they remain independent in what refers to the generation of their intrinsic rewards. •Centralized Critic + Centralized Curiosity (CC_CC ≡CC_CC_sh): both agents share all parameters of both the critic and the curiosity modules to generate the intrinsic rewards. By default, solely the state is considered as input. –Centralized Critic + Centralized-Action-based Curiosity (CC_CC_sh_ action): In this case, the intrinsic bonus is made dependent on the state and the action, instead of just uniquely on the state. –Centralized Critic + Centralized-Action Curiosity + Tree Filtering (CC_CC_sh_action_filter): this scheme is equal to the previous one, but during the generation of the rewards it prunes those rollouts whose experiences are not reproducible by the non-skilled agent (see Section 3.3.2.2)14. 3.5 Results and Analysis Results produced after the experiments held over the aforementioned setup are discussed in this section. For the sake of clarity in the discussion, results are commented based on the following research questions (RQ): •RQ1: Does a centralized critic provide any gain when compared to completely independent agents? 14We assume an oracle that informs whether the action executed by the skilled-agent is is reproducible by the non-skilled agent. 3.5. Results and Analysis 63 Table 3.2: Summary of algorithmic configurations of critic and curiosity modules. Besides the setups, the case studies also differ in the use of a (1) standard or UVFA centralized critic and (2) a RND or visitation counts based curiosity module as explained in Sections 3.4.1 and 3.4.2.*: sh and sh_action are used to distinguish the input for the centralized curiosity module. Critic Curiosity Module Case Study Configuration Independent Centralized Independent (state) Centralized (state) Centralized (state-action) 1 PPO ✓ IC_IC ✓ ✓ IC_CC ✓ ✓ CC_CC ✓ ✓ 2 IC_IC_3r ✓ ✓ IC_IC_6r ✓ ✓ CC_IC ✓ ✓ CC_CC_sh* ✓ ✓ CC_CC_sh_action* ✓Naive CC_CC_sh_action_filter ✓Filter •RQ2: Does a centralized curiosity yield better performance levels than maintaining the curiosity locally at every agent? •RQ3: Should we compute curiosity incentives based on the (state,action) pair rather than only the state itself? •RQ4: Should agents have their intrinsic rewards updated only by experiences that are reproducible as per their action spaces? We now analyze experimental results aiming to obtain informed responses to the above questions, using to this end the different configurations of the proposed collaborative framework that are represented in Table 3.2. Results are reported over 3 independent runs in order to account for their statistical variability. Unless otherwise stated, curves shown in the plots correspond to the average extrinsic return/success ratio (y-axis) obtained after a given number of train episodes (x-axis). RQ1: Does a centralized critic provide any gain when compared to completely independent agents? We begin our discussion by examining whether a centralized critic performs better than completely independent agents in the RL scenario under consideration. Responses to this question can be found in Figure 3.11, Figure 3.12 and Figure 3.13, which evince that a centralized critic (CC_XC) reaches better performance levels with respect to using independent critics (IC_XC). With a centralized critic, both agents manage to solve the task consistently in all the considered setups and settings, while reaching the target through their optimal path in most of the attempts (as shown in the previously referred Figures with _OPT). By contrast, agents featuring individual critic modules (IC_XC) are more unstable and require a larger amount of episodes than those considered during training. 64 Chapter 3. Collaborative Training of Heterogeneous Agents PPO IC IC IC CC CC CC Non-skilled agent Skilled agent Skilled agent (_OPT) Episodes Figure 3.11: Average extrinsic return achieved in Setup 1 for different settings (i.e., agent’s spawn initialization, each represented in a different row). The last column represents the score obtained by the skilled agent when going through its shortest path (i.e., corridor). PPO IC IC IC CC CC CC Non-skilled agent Skilled agent Skilled agent (_OPT) Episodes Figure 3.12: Same interpretation as in Figure 3.11, but for Setup 2. Intuitively one can postulate that the advantage of using a centralized critic is that, for the same/unique ANN, more number of experiences are collected (and used). Thus, as we compute the gradients with larger amount of data (gathered by two agents instead of just one), benefits in terms of variance are expected. If this is the case, we can just increase the number of collected experiences by each worker by doubling the number of runners, which ensures each agent to have the same amount of experiences as they would have had when using a centralized critic. This hypothesis can be answered from Figure 3.13, where we observe that IC_IC_6r is not only unable to perform as CC_IC, but also performs worse than IC_IC_3r. 3.5. Results and Analysis 65 Additionally to less variance, another key difference relies on the fact that CC_IC is updated almost twice faster, as it executes an optimization step per trajectories collected by each worker. On the contrary, in IC_IC_3r and IC_IC_6r each worker has its own critic module, which is updated once for the experiences collected by their respective actor. Nevertheless, if the number of optimization steps was the key factor to perform better, then with twice as many number of episodes, any individual approach should achieve similar performance levels than those by a centralized critic. However, this is not the case either, thereby arriving at the conclusion that a centralized critic performs better than individual critic modules. IC IC 3r IC IC 6r CC CC Non-skilled agent Skilled agent 3 runners 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 6 runners 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 Episodes Figure 3.13: Average extrinsic return achieved in Setup 3 using independent curiosity for encouraging the exploration when using independent critics (IC_CC) and a single centralized critic for both agents (CC_CC). We show the curves when using either 3 (upper row) or 6 (bottom row) parallel agent runners for the independent critic case; whereas the centralized critic approach uses 3 parallel agents. Dashed lines with markers are used to plot skilled agent’s _OPT curves. RQ2: Does a centralized curiosity yield better performance levels than maintaining the curiosity locally at every agent? Before delving into this second RQ, it is important to highlight that the addition of a curiosity module is undeniably necessary with respect to not using it, as PPO on its own is not able to outperform the behavior of a 66 Chapter 3. Collaborative Training of Heterogeneous Agents random agent (included as a dashed horizontal line in each plot of Figures 3.11 and 3.12). By using independent critics, results obtained by using either an individual (IC_IC) or a centralized (IC_CC) curiosity module elicit a better performance when using everything in an independent fashion. This statement is supported by the differences observed in Figures 3.11 and 3.12 for Setups 1 and 2, where IC_IC (green) exhibits higher success rates with a better sample efficiency. Besides, these differences are more notorious for the skilled agent, which undergoes more difficulties to go through the corridor when sharing the curiosity module, CC_CC (red), as seen in the _OPT curves. On the other hand, when using a centralized critic, the adoption of a centralized curiosity strategy (CC_CC_sh) is slightly better with respect to the independent curiosity counterpart (CC_IC), which can be confirmed by the results obtained in Figure 3.1415. By zooming into these results, for the skilled agent the CC_CC_sh approach achieves a 90% of SR with 1309 episodes on average, whereas CC_IC requires 1522 (an improvement of 14%). This can be also observed when the skilled agent achieves the destination through the corridor over 80% of the total episodes. At this point of the learning process, the fully centralized approach requires 6% less episodes. In the case of a non-skilled agent, differences are visually negligible, but they represent an improvement of 8%. Furthermore, CC_IC finishes with a slightly better policy that requires less steps to achieve the goal. Interestingly, the results obtained in Setups 1 and 2 with independent critics go against the intuition explained in Section 3.3.2 about centralizing the curiosity module (IC_IC >IC_CC), although the outcomes in Setups 1, 2 and 3 when using a centralized critic enforces this idea (CC_CC > IC_IC). We hypothesize that this occurs because the curiosity decreases for both agents when being shared, yet that knowledge is not persisted into their critic modules (when they have independent critics), estimating wrongly the intrinsic value of the state 𝑉𝑖(𝑠𝑡). This is effectively avoided when using a centralized critic. Therefore, results suggest that sharing the curiosity without sharing the critic as well is not actually beneficial. However, sharing both modules give rise to consistently better results. RQ3: Should we compute curiosity incentives based on the (state,action) pair rather than only the state itself? Previously, we have concluded that sharing curiosity information between agents yields advantages in terms of success rate and number of steps to reach the target as long as the critic is also shared. 15Indeed, the need for having a large number of episodes to actually see that the skilled agent is capable of traversing the corridor conceals any improvements that could arise from the experiments. 3.5. Results and Analysis 67 CC CC CC CC sh Non-skilled agent Skilled agent Extrinsic return 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 Number of steps 0 1000 2000 3000 4000 5000 6000 0 200 400 600 800 1000 1200 1400 0 1000 2000 3000 4000 5000 6000 0 200 400 600 800 1000 1200 1400 Episodes Figure 3.14: Average extrinsic return (top row) and number of steps (bottom rom) achieved in Setup 3 using a centralized critic while using either an independent curiosity(CC_IC) or a centralized approach (CC_CC_sh). Dashed lines with markers are used to plot skilled agent’s _OPT curves. Now we turn the focus on evaluating whether the intrinsic reward should be made dependent on both the state and action rather than just the state. In the past, the work in (Tang et al., 2017) showed no empirical differences between both approaches. However, in the cases under study they were not dealing with heterogeneous agents, where the novelty may be influenced by the actions available at each agent. Thus, as foretold in Section 3.3.2, our hypothesis is that by making the curiosity subject to the {𝑠, 𝑎}tuple, CC_CC_sh_action, different exploration behaviors can be induced into the agents, making it easier for the skilled agent to go through the corridor (as a consequence of inducing a larger curiosity for that special action). In light of the results depicted in Figure 3.15, it is fair to claim that our hypothesis holds, where the skilled agent exhibits a convergence improvement of its success rate of almost 1000 episodes when considering success as traversing the corridor to reach the target. This enhancement can be attributed to a smoother exploration bonus, which is representative on how the required steps decay more abruptly after finding out that path. On the other side, once that the path is discovered, it gets stacked with a policy that is slightly worse than the two approaches analyzed previously. That is, it requires greater number of steps to achieve the goal. We hypothesize that the reason for this effect is the same that leads the agent to 68 Chapter 3. Collaborative Training of Heterogeneous Agents find the path faster: the exploration component (intrinsic reward) is high when compared to the extrinsic bonuses, which makes the agent undergo noise in its learning process (higher entropy). The same behavior is also distilled into the policy learned by the non-skilled agent, whose scores are worse despite converging faster. CC CC sh CC CC sh action Non-skilled agent Skilled agent Extrinsic return 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 Number of steps 0 1000 2000 3000 4000 5000 6000 0 200 400 600 800 1000 1200 1400 0 1000 2000 3000 4000 5000 6000 0 200 400 600 800 1000 1200 1400 Episodes Figure 3.15: Average extrinsic return (top row) and number of steps (bottom rom) achieved in Setup 3 using a centralized and curiosity approach, yet making the curiosity to be subject to only the state (CC_CC_sh) or the state-action pair (CC_CC_sh_action). Dashed lines with markers are used to plot skilled agent’s _OPT curves. RQ4: Should agents have their intrinsic rewards updated rewards only by experiences that are reproducible as per their action spaces? Finally, we evaluate the proposed collaborative framework configured with a centralized critic and a centralized action-based curiosity, but filtering according to the idea explained in Section 3.3.2.2,CC_CC_sh_action_filter. Differences should appear mainly for the non-skilled agent, so that its learning process changes by deleting those experiences that modify its curiosity inappropriately. Plots nested in Figure 3.16 validate this hypothesis. A narrow performance gap arises between the two compared approaches CC_CC_sh_action _filter and CC_CC_sh_action. Both workers converge to a SR of 90% faster when compared to any of the previously analyzed configurations of 3.5. Results and Analysis 69 the framework, attaining an improvement of 7.7% (skilled agent) and 15% (non-skilled agent) in comparison to the second-best solution. CC CC sh action CC CC sh action filter Non-skilled agent Skilled agent Extrinsic return 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 0 1000 2000 3000 4000 5000 6000 0.0 0.2 0.4 0.6 0.8 1.0 Number of steps 0 1000 2000 3000 4000 5000 6000 0 200 400 600 800 1000 1200 1400 0 1000 2000 3000 4000 5000 6000 0 200 400 600 800 1000 1200 1400 Episodes Figure 3.16: Average extrinsic return (top row) and number of steps (bottom rom) achieved in Setup 3 using a centralized critic and a centralized curiosity subject to both the state-action, and with (CC_CC_sh_action_filter) and without (CC_CC_sh_action) filtering the episodes in which the special action has been used (e.g., open). Dashed lines with markers are used to plot skilled agent’s _OPT curves. 3.5.1 Exploration versus Exploitation: When? One of the major issues arising from the analysis of the results is that the number of steps of the optimal policy is far from the number of steps taken by executing the minimum number of actions16. The reason is that, even at the final stages of the training process, the learned policy is too stochastic and still features significant variability. Depending on the problem, this might be a good result as it allows the agent to adapt to changes more easily (Haarnoja et al., 2017). However, if the aim is to learn to perform the task as efficiently as possible, the optimal policy should be the one that converges with the minimum required steps towards the target. The challenge lies in the absence of a specific objective incorporated into the reward function that guides the problem-solving process with the fewest possible steps. In fact, the policy’s enhancement relies on precise value estimates, denoted as 𝑉(𝑠), based on the discounted return. 16Experiments have considered a frame skip equal to 4, hence the optimal solution with 1 frame per step should require less interactions of the agent with the environment. 76 Chapter 3. Collaborative Training of Heterogeneous Agents preventing from getting an optimal policy (remains too stochastic). This aligns with other works where, once a certain degree of knowledge has been obtained and the exploration is already considered sufficient, the fact of continuing to use it results to be counterproductive for the learning process (Rosser & Abed, 2021; Taïga et al., 2020). 3.7 Lessons Learned & Future Work Grounded on the insights extracted from the experiments and the analysis of the results, in this section we sketch learned lessons and interesting directions for future research. Some of the reflections offered in what follows relate to the heterogeneity between agents, whereas others relate to issues that lie at the conjunction of both RL and IM. 3.7.1 When to Explore? Exploration-Exploitation Dilemma with Heterogeneous Agents A well-known challenge in RL is about deciding when to explore and when to exploit in single agent scenarios. Besides the strong dependence on the characteristics of the environment, there are different types of exploration strategies that can be followed with diverse results (Pîslar et al., 2022). Even in the simpler single-agent scenario, it is not clear how to make the agent explore efficiently. In other words, when should a given agent explore? This question, often regarded as the exploration-exploitation dilemma, is yet unsolved, as it is not straightforward to determine when the agent (or even a human) has explored enough when learning to solve a task. This problem is exacerbated in settings with sparse rewards, specially when the completion of the task can require long-term training horizons. It has been seen in this chapter that one way to deal with exploration is to use IM techniques, with which the agent can explore the environment more smartly. However, this approach introduces a non-stationary novelty bonus, yielding a bi-objective problem with conflicting objectives: the main task’s extrinsic goal and the exploration-related intrinsic goal. As consequence, a misalignment between these objectives can emerge, potentially leading to worse results that not using the aforementioned intrinsic streams whatsoever (Taïga et al., 2020). In the considered concurrent learning problem the heterogeneous agents do not share anything (by default) as opposed to the assumptions made in multi-agent RL problems, where they share at least a team reward or the environment where they are deployed. Should we impose a collaborative strategy when none of the actions executed by an agent influence in the other agents behavior? It is complex to give an answer, and particularly if we do not know when an agent (independently of other agents) has explored enough on a given task, 3.7. Lessons Learned & Future Work 77 as depicted in the previous paragraphs. Therefore, in the current chapter, we have assumed some kind of latent knowledge between agents and tasks17 that have been formalized in terms of sharing the critic and curiosity module. We further assumed that both agents understand and perceive the environment in similar ways, which can be translated into developing congruent representations and exploration patterns, which, ultimately, can help bootstrapping the learning of the involved agents. Unfortunately, this might not be realistic in other RL scenarios. 3.7.2 Detachment-Derailment Problem Solutions that rely on IM techniques exhibit the so-called detachmentderailment problem. This issue arises when an agent has explored the environment correctly, becoming close to discovering an interesting state space or to achieving the goal. At some point, however, the agent’s learning gets stuck and the episode finishes. When the next episode is started, all decisions that the agent made to reach those spots are now regarded with less novelty (even being close to finding out promising locations). Consequently, the agent will be stimulated to examine other alternatives, even if it was in the right direction to discover novel states, degrading the effectiveness of the exploration. In this chapter, we realized that the detachment-derailment problem gets worse when the time horizon required to achieve any meaningful feedback signal increases. Recently, it has been shown that an effective way to address this issue is by clustering representations, and by reinitializating the agent smartly in the environment (Ecoffet et al., 2021; Ugadiarov et al., 2021). However, these approaches require the environment to be reset-free18. In the scenario with heterogeneous agents tackled in this chapter, a similarity-based clustering of the state space might be suitable to identify promising states where the agent can be reset (Ecoffet et al., 2021; Ugadiarov et al., 2021). Unfortunately, it is difficult to make these techniques work in POMDPs with first-person-view observations due to (1) the dimensionality reduction of the state space, and (2) the generation of clusters and the determination on where (i.e., in which cluster of states) to reinitialize each agent considering that they might have different stimuli and optimal paths for the same goal. In spite of the difficulty of implementing adequate mechanisms to deal with this phenomena is high, analysing and developing procedures to keep track of previous not-fully explored, albeit promising, routes, could complement IM techniques and make them efficient even in extraordinary complex circumstances 17Akin to the hypothesis behind Transfer Learning approaches. 18An environment in which the agent position and/or state perception can be manually selected without any constraints. This property grants flexibility to select new/desired start positions arbitrarily. 78 Chapter 3. Collaborative Training of Heterogeneous Agents 3.7.3 Potential of Recurrent Rewards Another issue encountered during this research springs from the fact that intrinsic bonuses are generated from a given experience tuple rather than a sequence of tuples. This issue affects not only the scenario tackled in this chapter, but also other RL environments that generate intrinsic rewards based on single experiences. This mainly occurs when having a POMDP as changes in the environment cannot be directly reflected even if those changes have a clear impact in the environment. Next, we expose this problem by briefly discussing on two hypothetical environments. Button Unlock when pressed Door Agent location (observation) Button Unlock when pressed Door 2 1 State visited twice (a) (b) Figure 3.20: Hypothesized case studies to discuss on how to deal with longterm dependencies within sparse POMDP problems. In the environments shown in Figure 3.20, the agent can unlock the colored passage by pushing the button that is located at a different location, relatively far from the entrance to the corridor. For this purpose, an action namely open is available by the agent but is useless anywhere else except in front of the door. In these environments a first-person-view observation hinders the agent from understanding the correlation between pushing the button and opening the door. What is more, the value of reaching the location where the button is located (and all the subsequent states to the destination) will differ depending whether: •The button is pushed and the agent goes through the corridor. •The button is pushed and the agent does not go through the corridor. •The button is not pushed. This issue, combined with long horizon returns and an agent that does not know how to interact and solve the problem correctly, leads to noisy updates and hampers the discovery of the correlation existing between the 3.7. Lessons Learned & Future Work 79 button and the door. This is even more complex in scenarios as the one in Figure 3.20.b, where a given observation (e.g., the one marked with an X) must be visited twice: 1when searching for the button that opens the passage, and another 2to go through the passage itself19. Due to these inconsistencies, we believe that novelty needs to be redefined in one of the following two ways: •As the intrinsic reward for a given experience tuple, aiming to quantify how novel the experience is on its own. •As the discounted expected return within a given trajectory,considering the calculated intrinsic bonus or the experiences that make up that specific trajectory, answering which degree of novelty this experience injects into future steps of the episode. The first definition relies solely on the experience itself to measure novelty. It is more practical and widely adopted in the research community. Nevertheless, this requires the temporal dependencies among the experiences to be modeled manually (e.g., stacking multiple instance frames, using memory mechanisms) or incorporating recurrent (and/or attention) modules at the actor, the critic or both (Hausknecht & Stone, 2015; Oh et al., 2016; Vaswani et al., 2017). In fact, in the architectures discussed in the experiments of this chapter, one of the algorithmic configurations adopted a LSTM-based neural architecture in the critic. However, there are no guarantees that this type of architecture retains the gathered knowledge at long-term horizons, nor is the novelty score used to compute the return stationary (it decreases over time). This instability in the expectation term over time ultimately hampers the long-term modeling capabilities of the recurrent/attention modules within ANN. Alternatively, a solution could be to generate intrinsic rewards based not only on the current time step, but also on past experiences (i.e. a sequence of experiences, second definition). This is, designing a reward function that handles the temporal dependencies and provides a different reward value, so that an experience is determined to be novel taking into account a full episode or path with its inherent consequences. This problem has also been recently showcased in relation to goals in (Colas et al., 2022), opening a debate around how to address this problem in an online fashion with no previous knowledge about the environment. This discussion finds in the action heterogeneity of agents studied in this chapter another twist of its screw. 19Recall the agent is only provided by a first-person-view input; therefore, the same observation can receive different values estimates depending whether the button was previously pushed or not. 81 Chapter 4 An Evaluation Study of Intrinsic Motivation Techniques applied to Reinforcement Learning over Hard Exploration Environments The claimed effectiveness of IM techniques in environments with sparse rewards has been proven in the previous chapter, when applied either collaboratively or independently in multiand singleagent problems. Experiments performed in the previous chapter, which considered RND and count-based strategies to compute the intrinsic rewards, showcased the large amount of IM approaches that can be adopted to foster the exploration by combining the produced intrinsic signal with its extrinsic counterpart (e.g. as in Expression (2.25) or Expression (3.2)). In this context, modern IM solutions (Badia, Sprechmann, et al., 2020; Raileanu & Rocktäschel, 2020; Seurin et al., 2021; T. Zhang et al., 2020) solutions propose not only their own method to calculate the exploration bonus, but also introduce other operations to weight and scale the magnitude of their generated intrinsic rewards. Table 4.1 lists several of such IM methods, building upon the early studies focused on the generation of curiosity information (Bellemare et al., 2016; Burda, Edwards, Storkey, et al., 2018; Pathak et al., 2017). Unfortunately, as per the current literature it remains unclear whether the research race towards superior IM methods is mainly driven by the proposed reward generation approach or instead, biased by other design choices, such as different base RL algorithms, decay of the exploration bonus, episodic scaling techniques adoption, neural network architectures and benchmarks for the evaluation of results. Analogously to other studies in the field of RL (Andrychowicz et al., 2021a; Andrychowicz et al., 2021b; Henderson et al., 2019; Orsini et al., 82 Chapter 4. Empirical Study of Intrinsic Motivation Techniques Table 4.1: Classification of various IM methods based on different design choices. We provide the parameters with which those approaches have been evaluated in the MiniGrid benchmark, except for NGU (Atari). Ref RL-algorithm Vary 𝛽𝑖Scale 𝑟𝑖ANN architecture ICM (Pathak et al., 2017) IMPALA ✗ ✗ Shared AC [3CNN,256LSTM,FC] RND (Burda, Edwards, Storkey, et al., 2018) IMPALA ✗ ✗ Shared AC, [3CNN,256LSTM,FC] RIDE (Raileanu & Rocktäschel, 2020) IMPALA ✗ ✓ Shared AC, [3CNN,256LSTM,FC] BeBold (T. Zhang et al., 2020) IMPALA ✗ ✓ Shared AC, [3CNN,256LSTM,FC] DoWhaM (Seurin et al., 2021) IMPALA ✗ ✓ Shared AC, [3CNN,1024LSTM,1024FC] RAPID (Zha, Ma, et al., 2021) PPO ✗ ✗ Independent AC, [2FC64] AGAC (Flet-Berliac et al., 2021) PPO ✗ ✓ Independent AC, [3CNN,512FC] D&E (Jing et al., 2021) PPO ✓ ✓ Independent AC, [3CNN,512FC] NGU (Badia, Sprechmann, et al., 2020) R2D2 ✓ ✓ Single Q(s,a,𝛽), [4CNN,512LSTM,512FC] 2021), a fundamental matter is to distinguish which design criteria are actually important and their impact on the performance of the agent. This is specially relevant in hard exploration environments, since it is known that under such circumstances, the proficiency of the agent is very sensitive w.r.t. the configuration of its compounding modules. For this reason, the goal of this chapter is to perform a fair evaluation of IM-based solutions present in the literature, aiming to decouple the contribution of the IM approach to the overall performance of the agent from the impact of additional design choices. As a result, insights will be given about which design choices matter when designing IM mechanisms, so that these approaches can be adapted and used in new RL problems thoughtfully. 4.1 Related Work Before digging into the contribution of this chapter chapter, we first briefly review the concepts in which some IM solutions support their curiosity mechanisms. Intrinsic Motivation As we have already explained in Section 2.3.1 of Chapter 2, two main groups of IM algorithms can be found in the literature: count-based and prediction-error methods. The firsts calculate the reward inversely proportional to the number of times 𝑁(𝑠𝑡)a given state (𝑠𝑡) has been visited: 𝑟𝑐𝑜𝑢𝑛𝑡𝑠 𝑡=1 √︁𝑁(𝑠𝑡)(4.1) This idea can be also extended to other visitation count approaches that are suitable for high-dimensional state domains (Bellemare et al., 2016; Machado et al., 2019; Ostrovski et al., 2017; Tang et al., 2017). On the other hand, prediction-error methods generate the exploration bonus taking into account the ability of the method to reliably predict changes in the environment. In order to accomplish it, ICM (Pathak et al., 2017) proposed a framework to calculate the difference between the actual next state (𝑠𝑡+1) and a prediction of the next state taking into account the 4.1. Related Work 83 current state and action, b𝑠𝑡+1=𝑓(𝑠𝑡, 𝑎𝑡), being 𝑓the function that will learn the dynamics of the environment. Even more importantly, instead of calculating the error directly with the raw input state, in ICM a latent representation 𝜙(·) is learned to capture only the information that affects or is affected by the agent (preventing irrelevant features of the state space from biasing the prediction): 𝑟𝐼𝐶𝑀 𝑡=|| b 𝜙(𝑠𝑡+1) − 𝜙(𝑠𝑡+1)||2(4.2) where || · ||2stands for the 𝐿2(Euclidean) norm and b 𝜙(𝑠𝑡+1)represents the prediction of the 𝑠𝑡+1taking into account 𝜙(𝑠𝑡)and the actual action 𝑎𝑡as input; that is, b 𝜙(𝑠𝑡+1)=𝑓(𝜙(𝑠𝑡), 𝑎𝑡). Please refer to Figure 2.9 for better clarity. Upon the idea of how state embeddings are learned, RIDE (Raileanu & Rocktäschel, 2020) proposed to calculate the exploration bonus by the difference between two consecutive states in their latent space: 𝑟𝑅𝐼𝐷𝐸 𝑡=||𝜙(𝑠𝑡+1) − 𝜙(𝑠𝑡)||2(4.3) With this change, RIDE encourages the agent to perform actions that have an impact on the environment. The modification with respect to ICM can be seen in Figure 4.11. φ(st) φ(st+1) b φ(st+1) st st+1 bat at LF W RIDE Features Features Forward model Inverse model LIN V − rRIDE t Figure 4.1: RIDE framework (Raileanu & Rocktäschel, 2020) to generate the intrinsic reward. What is more, to ensure that the agent does not go back and forth between a sequence of states in order to get intrinsic rewards, the reward is discounted by the episodic state visitation counts: 𝑟𝑅𝐼𝐷𝐸 𝑡=||𝜙(𝑠𝑡+1) − 𝜙(𝑠𝑡)||2 √︁𝑁𝑒𝑝 (𝑠𝑡+1)(4.4) 1Note that the forward model is now just used to build a better approximation of the feature space in the same way as the inverse model does. 84 Chapter 4. Empirical Study of Intrinsic Motivation Techniques so that the bonus now is calculated by combining experimentand episodelevel exploration (Pîslar et al., 2022; Stanton & Clune, 2018). Similar but more aggressively, in BeBold/NovelD (T. Zhang et al., 2020,2022) the reward was restricted so that only the first time the agent visits a given state in an episode was valid: 𝑟𝐵𝑒𝐵𝑜𝑙𝑑 𝑡=max 1 𝑁(𝑠𝑡+1)−1 𝑁(𝑠𝑡),0·I[𝑁𝑒(𝑠𝑡+1)=1](4.5) where 𝑁𝑒(·) stands for the episodic state count that is reset every episode, and I[·] is an indicator function taking value 1 if its argument is true (0 otherwise). Following the idea of combining various degrees of exploration, NGU (Badia, Sprechmann, et al., 2020) calculated the intrinsic reward as the combination of two sub-rewards: 𝑟𝑖 𝑡=𝑟𝑒𝑝𝑖𝑠𝑜𝑑𝑖𝑐𝑖 𝑡·min{max{𝑟𝑙𝑖 𝑓 𝑒𝑙𝑜𝑛𝑔𝑖 𝑡,1},5}(4.6) being 𝑟𝑒𝑝𝑖𝑠𝑜𝑑𝑖𝑐𝑖 𝑡calculated through an episodic memory (Pritzel et al., 2017) and 𝑟𝑙𝑖 𝑓 𝑒𝑙𝑜𝑛𝑔𝑖 𝑡computed across the whole training. In addition, NGU adopted an UVFA (Schaul et al., 2015) framework so that the employed action-value function was subject to different 𝛽coefficients, 𝑄(𝑠𝑡, 𝑎𝑡, 𝛽), which allows learning policies with different explorative behaviors using a single network. Last but not least, FaSo (Bougie & Ichise, 2021) combined local and global exploration by generating two different intrinsic rewards, depending on the quality of the reconstruction of two contexts built from the same state. Aside from the method to calculate the exploration bonus itself, new IM solutions are shown to yield better results in their respective publications, yet using additional components which were not used when compared to the selected baselines. Thus, rather than proposing a new intrinsic generation module, in this chapter we carry out an evaluation study to gauge the impact of such modifications (Table 4.1) and to ascertain the contribution of the IM reward generation to the overall performance of the agent. Reinforcement Learning Studies Other benchmarks/studies have been done in recent times surrounding RL: to begin with, (Taïga et al., 2020) evaluates the performance of different exploration bonuses (pseudo-counts, ICM, RND and noisy networks) in the whole Atari 2600 suite with Rainbow (Hessel et al., 2017). By contrast, (Burda, Edwards, Pathak, et al., 2018) carried out a large-scale study based exclusively on prediction error bonuses over 54 environments, where they investigated the efficacy of using different feature learning methods with PPO (Schulman, Wolski, et al., 2017). This chapter also connects with (Andrychowicz et al., 2021a; Andrychowicz et al., 2021b; Henderson et al., 2019; Orsini et al., 2021), a series of evaluation studies aimed to understand what choices among highand low-level algorithmic options affect 4.2. Methodology of the Study 85 the learning process. As such, the studies in (Andrychowicz et al., 2021a; Andrychowicz et al., 2021b) focus on on-policy deep actor-critic methods (examining different policy losses, architectures and advantage estimators). On the other hand, (Orsini et al., 2021) addresses adversarial IM related decisions (multiple reward functions and observation normalization methods), whereas (Henderson et al., 2019) investigates reproducibility issues using different random seeds, activation functions, codebases, and reward scales, among other experimental choices. Contribution To the best of knowledge, there is no prior work that exhaustively evaluates different choices for the implementation of intrinsic motivation strategies. The study presented in this chapter of the Thesis takes a step further by analyzing different weight and scale strategies for the combination of intrinsic and extrinsic rewards, as well as the impact of adopting different neural networks architectures and its dimensions. The design choices here evaluated are applicable to any intrinsic curiosity generation module, so that conclusions about which ones are the most suitable given a task and an environment with sparse rewards can be drawn. 4.2 Methodology of the Study After reviewing different solutions proposed in the literature to cope with hard exploration issues with IM techniques, we now proceed by describing the methodology adopted in this chapter to gauge the advantages and drawbacks of design choices that are present in some of them, giving an informed hint of their utility when extrapolated to the rest of IM solutions. The methodology is driven by the pursuit of responses to three research questions (RQ): •RQ1: Does the use of a static, parametric or adaptive decaying intrinsic coefficient weight 𝛽affect the agent’s training process? •RQ2: Which is the impact of using episodic counts to scale the intrinsic bonus? Is it better to use episodic counts than to just consider the first time a given state is visited by the agent? •RQ3: Is the choice of the neural network architecture crucial for the agent’s performance and learning efficiency? Departing from these questions, the following methodology has been devised: 4.2.1 RQ1: Varying the Weight of the Intrinsic Reward Coefficient 𝛽 In general, it is not advisable to combine raw extrinsic and intrinsic reward signals directly due to their potentially diverging value scales. Moreover, 92 Chapter 4. Empirical Study of Intrinsic Motivation Techniques filters with kernel 3×3, stride equal to 2, and padding 1) and a FC256 layer. Originally in (Raileanu & Rocktäschel, 2020) they used an LSTM of 256 units instead of a FC-256. We analyze the results with no recurrence despite being in an POMDP setting, which will also allow the comparison whether if it is actually necessary the use of recurrence modules in these environments. What is more, even if (Raileanu & Rocktäschel, 2020) defined the previously mentioned architecture design, in their GitHub implementation they seem to use larger networks (https://github.com/facebookresearch/impact-driven-exploration). This is the reason why in Table 4.1 we do not specify the FC units. This last architecture will be labeled as the default architecture to endow the agent with more learning capabilities and to ensure that it is not limited by a restricted network. CNN 1 CNN 2 CNN 3 FC 256 V(s) π(a|s) (7 values, distribution) (1 value) 32 filters, 3 ×3 kernel, 2×2 stride, padding 1 FC 7 FC 64 FC 64 π(a|s) (7 values, distribution) FC 7 FC 64 FC 64 FC 1 V(s) (1 value) Actor: Critic: (a) (b) FC 1 . . . Figure 4.4: (a) Sophisticated/default and (b) lightweight network architectures. 4.4 Results and Analysis In this section experimental results are presented and discussed towards answering the research questions posed in Section 4.2. Scripts and results have been made available in a public GitHub repository (https://github .com/aklein1995/intrinsic_motivation_techniques_study) to foster reproducibility and stimulate follow-up studies. For all the experiments described in this section we provide the mean and standard deviation of the average return computed over the past 100 episodes, performing 3 different runs (each with a different seed) to account for the statistical variability of the results. 4.4.1 RQ1: Does the use of a static, parametric or adaptive decaying intrinsic coefficient weight 𝛽 affect the agent’s training process? Our first set of results compares the multiple weighting strategies introduced in Section 4.2.1, which differently tune the importance granted to the intrinsic rewards with respect to extrinsic signals coming from the environment. The results are shown in Table 4.2. It is straightforward to note that RIDE outperforms COUNTS and RND. At this point we remind that 4.4. Results and Analysis 93 Table 4.2: Results of different IM strategies over several MiniGrid scenarios with static (_𝑠), multiple static (_𝑛𝑔𝑢) (as in NGU Badia, Sprechmann, et al., 2020), a parametric (_𝑝𝑑) or adaptive decay (_𝑎𝑑) weight 𝛽to modulate the importance of the intrinsic bonus in the computation of the reward. Cell values denote the training steps/frames (1𝑒6scale) at which the optimal average extrinsic return is achieved; between parentheses, steps at which 95% of the optimal average extrinsic return is reached. The best results for every (IM strategy, scenario) combination are highlighted in bold. MN7S4 MN10S4 MN7S8 KS3R3 O2Dlh COUNTS_𝑠0.93 (0.86) 1.87 (1.78) >30 >30 >50 COUNTS_𝑛𝑔𝑢 1.17 (1.11) 2.67 (2.35) >30 >30 >50 COUNTS_𝑝𝑑 0.96 (0.83) 2.27 (1.67) >30 22.91 (22.49) >50 COUNTS_𝑎𝑑 1.03 (0.92) 1.81 (1.65) 24.23 (24.10) >30 >50 COUNTS_𝑎𝑑1000 1.03 (0.92) 1.81 (1.65) 23.63 (23.56) >30 >50 RND_𝑠3.83 (3.78) 7.84 (7.79) >30 10.83 (9.72) >50 RND_𝑛𝑔𝑢 2.69 (2.62) 5.78 (5.75) >30 8.12 (7.50) >50 RND_𝑝𝑑 4.04 (3.94) 6.02 (5.99) >30 9.24 (8.07) >50 RND_𝑎𝑑 2.02 (1.39) 3.21 (2.65) >30 6.02 (5.43) >50 RND_𝑎𝑑1000 3.62 (1.42) 3.59 (3.50) >30 7.47 (6.66) >50 RIDE_𝑠2.49 (1.82) 2.27 (2.14) 4.00 (3.68) 6.63 (4.39) 30.88 (25.87) RIDE_𝑛𝑔𝑢 3.85 (2.40) 2.59 (1.26) >30 7.18 (3.91) 36.07 (29.96) RIDE_𝑝𝑑 5.20 (2.14) 5.01 (1.96) 3.73 (3.49) 6.42 (3.87) 29.27 (20.84) RIDE_𝑎𝑑 2.89 (0.91) 1.60 (0.99) >30 5.93 (2.99) 27.65 (20.91) RIDE_𝑎𝑑1000 2.54 (0.91) 1.60 (0.99) 3.88 (3.70) 4.70 (3.00) 28.00 (23.01) RIDE is configured with episodic count scaling, in accordance with the final solution proposed in (Raileanu & Rocktäschel, 2020). Count-based generated rewards seem to be the best solution when facing easy exploration scenarios (MN7S4 and MN10S4), but its performance degrades when facing scenarios that require more sophisticated exploration strategies. A similar pattern can be observed when analyzing the results of RND, which is unable to solve MN7S8 and O2Dlh with any kind of weighting strategy. Contrarily, RIDE manages to solve all the tasks by its naïve implementation, although it achieves better results when using more sophisticated weighting exploration strategies. We now focus the discussion on gaps arising from the use of different weighting strategies. The static (default) weighting strategy (indicated with a suffix _𝑠appended to each approach) is surpassed by any of the other proposed weighting approaches in the majority of the cases. When using multiple static values (_𝑛𝑔𝑢), the only approach that takes advantage of such a strategy is RND, yielding worse results for both COUNTS and RIDE in all the cases. This might happen due to the slow pace at which the intrinsic rewards values decay in RND in reference to the other strategies6. On the other hand, the use of parametric decay (_𝑝𝑑), which 6The error output by RND has higher amplitude values than those of RIDE, thereby RND is a better candidate to get benefit of applying the _𝑛𝑔𝑢 strategy by the use of agents with smaller intrinsic coefficient weights (avoiding over-exploration issues in the case of RND and oppositely having under-exploration issues with RIDE). 94 Chapter 4. Empirical Study of Intrinsic Motivation Techniques decreases the weight of the intrinsic reward as the training evolves to favor exploration, provides significant gains in almost all simulated scenarios. This approach is similar to _𝑛𝑔𝑢. However, instead of using multiple agents with different static intrinsic coefficients, the parametric decay strategy modulates a single value during the course of training. When employing the _𝑝𝑑 strategy, COUNTS is able to get a valid solution in KS3R3, RND improves all its scores and RIDE improves its behavior in the most challenging scenarios MN7S8,KS3R3 and O2Dlh. Nevertheless, _𝑛𝑔𝑢 and _𝑝𝑑 highly depend on the intrinsic coefficients given to each agent and the evolution of a single intrinsic coefficient during training, respectively. This strongly impacts on the agent’s performance for a given scenario and dictates when those approaches might be better. Indeed, it can be seen as a tuning parameter like 𝜖in 𝜖-greedy strategies. Finally, the use of adaptive decay (_𝑎𝑑)produces better results in COUNTS and RND when compared to the static case (_𝑠). For RIDE, however, this statement does not strictly hold true, as its performance degrades in MN7S4 and MN7S8 (the agent does not even solve the task in the latter case). We hypothesize that this is due to the fact that the initial intrinsic returns are too high. Hence, calculating the historical average intrinsic returns biases the computation of the decay factor. As outlined in Section 4.2.1, a workaround to overcome this issue is to calculate returns with a moving average over a window of 𝜔steps/rollouts. We hence include in the benchmark an adaptive decay with a window size of 𝜔=1000 rollouts (_𝑎𝑑1000). With this modification, RIDE improves its behavior in all the complex scenarios. Nevertheless, _𝑎𝑑1000 performs slightly worse than _𝑎𝑑 in RND, but never worse than its static counterpart _𝑠. In general, _𝑎𝑑1000 promotes higher intrinsic coefficient values than _𝑎𝑑, as the calculated average return is a better fit to the actual return values. This leads to a lower decay value and a higher intrinsic coefficient, forcing the agent to explore more intensely than with _𝑎𝑑 (but less than with _𝑠). 4.4.2 RQ2: Which is the impact of using episodic counts to scale the intrinsic bonus? Is it better to use episodic counts than to just consider the first time a given state is visited by the agent? Answers to this second question can be drawn from the results of Table 4.3. A first glance at this table reveals that the use of episodic counts or first-time visitation strategies for scaling the generated intrinsic rewards leads to better results. In the most challenging environments (MNS78, KS3R3 and O2Dlh), these differences are even wider, as they require a more intense and efficient exploration by the agent. In fact, when the training stage is extended to cope with a more complex task, intrinsic rewards also decrease, inducing a lower explorative behaviour in the agent the longer the training period is extended. Hence, the agent does not seek as much novelty as it should, what might explain why the baseline 4.4. Results and Analysis 95 implementation of intrinsic motivation (_𝑛𝑜𝑒𝑝) fails in those scenarios as opposed to when using the scaling strategies (e.g., COUNTS and RND in O2Dlh). By contrast, in environments requiring less exploration (MN7S4 and MN10S4), differences are narrower when using episode-level exploration and may be even counterproductive in some cases (i.e. COUNTS at MN10S4 with _1𝑠𝑡). Table 4.3: Comparison of different IM strategies when using no scaling (_𝑛𝑜𝑒𝑝), episodic (_𝑒𝑝) or first-time visit (_1𝑠𝑡) to scale the generated intrinsic reward and combine two types of exploration degrees. Interpretation as in Table 4.2. MN7S4 MN10S4 MN7S8 KS3R3 O2Dlh COUNTS_𝑛𝑜𝑒𝑝 0.93 (0.86) 1.87 (1.78) >30 >30 >50 COUNTS_𝑒𝑝 0.76 (0.56) 1.55 (1.47) 2.77 (2.56) 3.99 (2.00) 33.17 (29.79) COUNTS_1𝑠𝑡 0.85 (0.48) >20 1.64 (1.42) 1.97 (1.19) 45.26 (37.29) RND_𝑛𝑜𝑒𝑝 3.83 (3.78) 7.84 (7.79) >30 10.83 (9.72) >50 RND_𝑒𝑝 1.41 (0.96) 1.72 (1.34) 3.60 (3.30) 4.31 (2.63) 18.54 (14.07) RND_1𝑠𝑡 1.18 (0.59) 1.36 (0.78) 1.97 (1.72) 4.78 (2.29) 21.19 (9.88) RIDE_𝑛𝑜𝑒𝑝 4.71 (4.54) 5.29 (5.20) >30 11.44 (9.63) 39.68 (35.15) RIDE_𝑒𝑝 2.49 (1.82) 2.27 (2.14) 4.00 (3.68) 6.63 (4.39) 30.88 (25.87) RIDE_1𝑠𝑡 3.17 (1.34) 3.27 (2.33) 1.95 (1.83) 5.13 (2.26) 32.14 (28.03) ICM_𝑛𝑜𝑒𝑝 2.67 (2.55) >20 >30 8.02 (6.75) 34.04 (26.78) ICM_𝑒𝑝 3.25 (1.26) 1.68 (1.59) >30 5.32 (3.14) 19.05 (13.87) ICM_1𝑠𝑡 1.56 (0.87) 1.90 (1.07) 2.11 (1.77) 4.72 (4.23) 20.74 (10.09) To better understand the superiority of RIDE over ICM as shown in (Raileanu & Rocktäschel, 2020), we also evaluate the performance of both approaches under equal conditions, with (_𝑒𝑝, _1𝑠𝑡) and without (_𝑛𝑜𝑒𝑝) scaling strategies. In this way, we can examine the actual improvement between the two types of exploration bonus strategies. Surprisingly, ICM gives better results in almost all the cases for the analyzed scenarios, yet exhibiting a larger variance in several environments that lead to failure (MN10S4 and MN7S8). The reason might reside in how RIDE encourages the agent to perform actions that affect the environment, forcing the agent to assess all possible actions, so that the entropy in the policy distribution decays slowly. This hypothesis is buttressed by the results obtained in MN7S4 and MN10S4: we recall that there are 3 useless actions in these scenarios (pick up,drop and done), and RIDE performs clearly worse (except for the _𝑒𝑝 case in MN7S4). In more complex scenarios, when those actions are relevant for the task, performance gaps between RIDE and ICM become narrower. For the sake of completeness of the results discussed for RQ1 and RQ2, Figure 4.5 shows the training convergence plots of COUNTS, RND and RIDE for different weighting and scaling strategies. 96 Chapter 4. Empirical Study of Intrinsic Motivation Techniques static ngu pd ad ad 1000 ep 1st 0.25 0.50 1.00 1.50 2.00 ×107 0.25 0.50 0.77 1.00 MN7S4 COUNTS 0.25 0.50 1.00 1.50 2.00 ×107 0.0 0.2 0.4 0.6 0.8 1.0RND 0.25 0.50 1.00 1.50 2.00 ×107 0.0 0.2 0.4 0.6 0.8 1.0RIDE 0.25 0.50 1.00 1.50 2.00 ×107 0.25 0.50 0.76 1.00 MN10S4 0.25 0.50 1.00 1.50 2.00 ×107 0.0 0.2 0.4 0.6 0.8 1.0 0.25 0.50 1.00 1.50 2.00 ×107 0.0 0.2 0.4 0.6 0.8 1.0 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.25 0.50 0.65 1.00 MN7S8 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.0 0.2 0.4 0.6 0.8 1.0 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.0 0.2 0.4 0.6 0.8 1.0 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.25 0.50 0.90 1.00 KS3R3 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.0 0.2 0.4 0.6 0.8 1.0 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.0 0.2 0.4 0.6 0.8 1.0 12345 ×107 0.25 0.50 0.95 1.00 O2Dlh 12345 ×107 0.0 0.2 0.4 0.6 0.8 1.0 12345 ×107 0.0 0.2 0.4 0.6 0.8 1.0 Figure 4.5: Convergence plots of the schemes reported in Tables 4.2 and 4.3. Each column represents a Intrinsic Motivation type (COUNTS, RND and RIDE from left to right); each row represents the different scenarios (MN7S4,MN10S4, MN7S8,KS3R3 and O2Dlh, from top to bottom). All figures depict the average extrinsic return as a function of the number of training steps/frames (in a scale of 1𝑒7). For each scenario, optimal and suboptimal scores are highlighted with horizontal black and brown lines, respectively. 4.4.3 RQ3: Is the choice of the neural network architecture crucial for the agent’s performance and learning efficiency? One of the most tedious parts when implementing an algorithm is to determine which network architectures to use. First of all, when using an actor-critic RL framework it is necessary to establish whether a single but two-headed network or two different (and independent) networks will be adopted for the actor and the critic modules. In addition, some IM approaches are based on neural networks to generate the intrinsic rewards. 4.4. Results and Analysis 97 Herein we evaluate two of those solutions: RND and RIDE, evaluating the contribution of different neural network architectures to the overall performance of the agent. We use similar architectures to the ones used in RIDE and RAPID7: (a) a two-headed shared actor-critic network built upon convolutional and dense layers and (b) two independent MLP networks for the actor and the critic, respectively (Figure 4.4). Moreover, we fix the RL algorithm (PPO) and detail the number of parameters and time taken for the forward and backward passes in each network for an informed comparison. Table 4.4: Comparison of number of parameters and required forward and backward passes between the ANN architectures described in Section 4.2.3 when being used with different IM modules. Lightweight (lw) Default Parameters Time (ms) Parameters Time (ms) Actor 14,087 - - Critic 13,697 - - Actor+Critic 27,784 - 29,896 - Dictionary - 83.66 - 95.11 Total COUNTS 27,784 724.25 29,896 937.37 Embedding 13,632 - 19,392 - RND 27,264 336.39 38,784 721.64 Total RND 55,048 986.13 68,937 1,408.42 Inverse 12,871 - 18,439 - Forward 12,928 - 18,464 - Embedding 13,632 - 19,392 - RIDE 39,431 388.84 56,295 844.43 Total RIDE 67,215 1,177.75 86,191 1,791.70 First of all, Table 4.4 informs about these details of the neural architectures in use for COUNTS, RND and RIDE. It reports the differences in terms of the number of parameters of each network, and the latency taken by the sum of both forward and backward passes through those IM modules (we note that COUNTS uses a dictionary and not a neural network for the reward generation). In addition, we summarize the total number of parameters depending on the implemented IM module, together with the actor-critic parameters. Referred to the total elapsed time, we report the total amount of time required for a rollout collection. This elapsed time takes into account both the forward and backward passes in the IM modules, and just the forward pass across the actor-critic, among other operations executed when collecting samples. Times are calculated when executing the experiments over an Intel(R) Xeon(R) CPU E3-1505M v6 processor running at 3.00GHz. 7Even with different neural architectures and base RL algorithms, they successfully solve the same tasks in MiniGrid with different sample-efficiency. 98 Chapter 4. Empirical Study of Intrinsic Motivation Techniques On the other hand, Table 4.5 shows the performance of the agent when configured with such different network configurations. It can be seen that when reducing the number of parameters in both the actor-critic and the IM modules (_𝑙𝑤_𝑡𝑜𝑡), the agent’s behavior degrades critically. This occurs even with COUNTS, where the modification should have had less impact as the generation of intrinsic rewards does not depend on a neural network, but on a dictionary. When inspecting the performance of RIDE, its performance gets worse in all cases except for MN7S4, where the exploration requirements are the lowest among all the analyzed scenarios. As for RND, the full lightweight configuration of the networks makes the tasks not solvable by the agent. Table 4.5: Performance obtained with COUNTS, RND and RIDE when 1) using the default network configurations, 2) a lightweight architecture for the IM modules and keeping actor-critic with a default configuration (_𝑙𝑤_𝑖𝑚), and 3) when both the IM and the actor-critic modules are implemented with the lightweight networks (_𝑙𝑤_𝑡𝑜𝑡). Values in the cells represent the training steps/frames (in a scale of 1𝑒6) when the optimal average extrinsic return is achieved. Within brackets, the training steps when a suboptimal behavior is accomplished. MN7S4 MN10S4 MN7S8 KS3R3 O2Dlh COUNTS 0.93 (0.86) 1.87 (1.78) >30 >30 >50 COUNTS_𝑙𝑤_𝑖𝑚 0.93 (0.86) 1.87 (1.78) >30 >30 >50 COUNTS_𝑙𝑤_𝑡𝑜𝑡 1.64 (1.48) 2.52 (2.36) >30 (29.96) >30 >50 RND 3.86 (3.79) 7.84 (7.79) >30 10.84 (9.72) >50 RND_𝑙𝑤_𝑖𝑚 5.66 (5.44) 6.68 (6.61) >30 10.97 (9.45) >50 RND_𝑙𝑤_𝑡𝑜𝑡 > 20 >20 >30 >30 >50 RIDE 2.49 (1.82) 2.27 (2.14) 4.01 (3.38) 6.63 (4.39) 30.88 (25.87) RIDE_𝑙𝑤_𝑖𝑚 1.63 (1.31) 1.75 (1.53) >30 9.44 (5.08) >50 RIDE_𝑙𝑤_𝑡𝑜𝑡 1.42 (1.05) >20 >30 8.00 (5.69) >50 Going back again to Table 4.4, it can be seen that the number of parameters to be learned is mostly dependent on the IM networks under consideration, whereas joining the actor and the critic into a single two-headed network barely increases the dimensionality requirements8. Nevertheless, the time required to perform a forward pass increases in approximately 25% when an unique actor-critic network is employed. Moreover, by using a single network, part of the parameters of the network are shared between the actor and the critic, which can induce more instabilities but also a faster learning since the model may share features between the actor and the critic and require less samples to learn a given task. With this in mind, we carry out an additional ablation study considering only the reduction of parameters at IM modules, and maintaining the actor-critic as a single two-head network. Such results are provided in the second row of every group of results in Table 4.5 (_𝑙𝑤_𝑖𝑚). These outcomes evince that when using 8We note that the number of parameters is slightly increased, but they also differ in the type of layers that are used in each network (the two-headed network uses CNNs while the independent actor-critic only uses dense layers. 4.5. Conclusions 99 RND_𝑙𝑤_𝑖𝑚, slightly worse results are achieved with respect to RND with the default network setup. However, its performance does not degrade dramatically down to failure as with RND_𝑙𝑤_𝑡𝑜𝑡. Hence, using parameter sharing in a single actor-critic network yields a faster learning process and positively contributes for this case, inferring also that the dimensionality reduction in IM modules is not that critical in RND. Regarding RIDE_𝑙𝑤_𝑖𝑚, in some cases (MN7S4 and MN10S4) it attains better results, whereas in MN7S8 and KS3R3 it suffers from a notorious performance degradation (MN7S8 is not solved). It can also be observed that the use of the single actor-critic network might be beneficial when reducing the complexity of the IM network (_𝑙𝑤_𝑖𝑚), as it mitigates the performance degradation in 3 out of 5 scenarios (still, MN7S8 and O2Dlh are not solved). This clashes with the results for separated actor-critic networks (_𝑙𝑤_𝑡𝑜𝑡), which fail to solve MN7S8,O2Dlh and MN10S4). 0.0 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.0 0.2 0.4 0.6 0.8 1.0RIDE at MN7S8 012345 ×107 0.0 0.2 0.4 0.6 0.8 1.0RIDE at O2Dlh 0.0 0.5 1.0 1.5 2.0 2.5 3.0 ×107 0.0 0.2 0.4 0.6 0.8 1.0COUNTS at MN7S8 Figure 4.6: Convergence plots of COUNTS and RIDE for some scenarios when using the default network (blue), _𝑙𝑤_𝑖𝑚(green) and _𝑙𝑤_𝑡𝑜𝑡(red). All the figures depict the average extrinsic return as a function of the number of training frames. Finally, we include Figure 4.6 in order to help the reader extract further conclusions and gain insight about the behavior of the learning process. This figure reveals that, in the two cases in which RIDE_𝑙𝑤_𝑖𝑚 failed (namely, MN7S8 and O2Dlh), the agent learned to solve the task in two out of the three experiments that were run (seeds). This underscores the impact of using different actor-critic architectures. Moreover, with the default actor-critic architecture and using the COUNTS approach, the agent is also capable of solving the MN7S8 task in 2 out of the 3 runs. When using COUNTS_𝑙𝑤_𝑡𝑜𝑡, the agent reaches suboptimal performance and almost the optimal one within the frame budget. 4.5 Conclusions In this chapter we have studied the actual impact of different design choices when implementing RL agents augmented with IM mechanisms. More concretely, we have evaluated multiple weighting strategies to grant different importance when combining the intrinsic and extrinsic rewards (i.e., the 𝛽coefficient). Moreover, we have analyzed the effect of applying distinct degrees of exploration (to scale generated intrinsic rewards, 𝑟𝑖) along with the influence of the complexity of the network architectures on the performance of both actor-critic and IM modules. To conduct the study we have 100 Chapter 4. Empirical Study of Intrinsic Motivation Techniques utilized environments belonging to the MiniGrid benchmark, so as to test the quality of the considered schemes in a variety of tasks characterized by a hard to very-hard demand of an exploratory behavior of the agent. On one hand, we have shown that using a static intrinsic coefficient might not be the best strategy if focusing on sample efficiency. Adaptive decay strategies have proven to be promising, although they require a good parameterization of the sliding window. The parameter decay approach, in turn, has performed competently. However, the parameter values of the decay function are more dependent on the task at hand than the previous scheme, making this strategy more sensitive to the environment and the task. This resounds what occurs with 𝜖-greedy strategies in some valuebased algorithms. The use of multiple agents (as in NGU), each featuring a different exploration-exploitation balance, also suffers from the need for a good parameterization, but it reports worse results. On the other hand, the use of episode-level exploration along with experiment-level strategies seem to be preferable when having environments with hard exploration requirements. It is not a clear winner nor a preference between episodic counts and first visitation strategies, as their performance is subject to the environment and the selected IM strategy. However, both achieve significant performance gains. The adoption of any of these strategies can be advised in future IM-related studies. We have also analyzed the impact of the neural network architecture on both the actor-critic and IM modules. Results have shown that reducing the number of parameters in the IM modules deteriorates the performance of the agent, making it fail in some challenging scenarios which are feasible for the complex neural configuration. What is more, when reducing the dimensions of the IM network, it is preferable to use a shared twoheaded actor-critic as it provides better results, although it is not clear whether those results are due to the use of a single neural network (and the underlying parameter sharing and common feature space for the actor and the critic), or instead to the adoption of different neural processing architectures (e.g. CNNs). Further research is necessary in this direction. All in all, the evaluation study presented in this chapter can serve as a reference for the community in the implementation of intrinsic motivation strategies to address (1) tasks with sparse rewards; or (2) hard exploration scenarios where classic exploration techniques do not suffice. 101 Chapter 5 Towards Improving Exploration in Self-Imitation Learning using Intrinsic Motivation The previous chapter has analyzed the impact of using different design factors over rewards generated with IM techniques. We have evaluated those algorithms not in singleton but in procedurally generated environments, where the generalization capabilities of the agent are essential for it to exhibit an overall good performance. Continuing with the idea of improving the sample efficiency over hard exploration PCG environments, in this chapter we further examine the use of Imitation Learning (IL) for this purpose. Over years the use of IL and Transfer Learning has been widely adopted to accelerate the learning process and to reduce the amount of required training data (Hua et al., 2021; Nair et al., 2021; Wu et al., 2022). The strategy of using expert demonstrations has been also adopted to tackle exploration issues in hard exploration scenarios with sparse rewards, by either initializing a buffer with good behavior trajectories (Hester et al., 2017; Vecerik et al., 2018) or by generating a curriculum-style learning and re-initializing the agent smartly (Aytar et al., 2018; Salimans & Chen, 2018). Unfortunately, such expert demonstrations are not always available in practice. This motivated the idea of storing trajectories – self-collected by the agent– featuring good exploration properties for a later replay, forging what is now known as self-Imitation Learning (self-IL1). Despite its effectiveness to alleviate the need for expert demonstrations, self-IL methods are highly sensitive to the early discovery of sufficiently good trajectories, which can be challenging in hard exploration scenarios. 1There is an approach named directly as SIL. Thus, for the sake of clarity, in this chapter we refer as self-IL to the family of algorithm in which the agent collects the experiences by itself for augmenting its sample efficiency, whereas SIL will denote the specific approach presented in (Oh et al., 2018). 108 Chapter 5. Self-Imitation Learning with Intrinsic Motivation As in previous chapters, we report the mean and standard deviation of the average return computed over the past 100 episodes for each experiment, performing 3 different runs (with different seeds) to account for the statistical variability of the results. For transparency and reproducibility of the experiments later discussed, the code is available in a public GitHub repository: https://github.com/aklein1995/exploration_sil_im. 5.3.1 Environments We evaluate our proposed approach over MiniGrid (Chevalier-Boisvert et al., 2018), as explained in Chapter 4(Section 4.3.1). Specifically, we evaluate the framework over the following scenarios (for further information about the environments and their tasks, please refer to Chevalier-Boisvert et al., 2018): MultiRoom (MN7S8 and MN12S10), KeyCorridor (KS4R3) and ObstructedMaze (O2Dlh). The criterion to select these environments relies on their difficulty as verified in (Zha, Ma, et al., 2021), where MN12S10 and KS4R3 were identified as the most difficult scenarios under analysis: the first was solved by RAPID and RIDE, while the latter remained unsolved for the given train steps by any of the baselines under consideration. In the case of (Ning et al., 2021), where the performance of SIL+BeBold was analyzed in MiniGrid, the most difficult environments were KS3R3 and MN6S, which are more easily solvable than KS4R3 and MN12S10 (they use smaller rooms and less number of rooms respectively). Additionally, we include another very hard exploration scenario, not considered in the aforementioned works, which possesses different characteristics and requirements than the previous environments: O2Dlh. 5.3.2 Baselines and Hyperparameters We select RAPID (Zha, Ma, et al., 2021) and SIL (Oh et al., 2018) as self-IL baseline methods, and BeBold (T. Zhang et al., 2020) as the IM. All strategies use PPO as their core RL algorithm, which uses a number of steps equal to 128 and 4minibatches of size 32 for training (one unique agent). Each train step comprises 4epochs, where optimization updates are carried out with a learning rate of 10−4, a clipping factor of 𝜖=0.2, 𝛾=0.99 and 𝜆=0.95 for the advantages calculation with GAE as per Expression (2.18). Furthermore, the loss function (recall Expression (2.22)) is weighted by a entropy coefficient of 𝑐2=0.01 and a value coefficient of 𝑐1=0.5. Moreover, we employ 2 independent fully-connected layers for the actor and the critic – each with 64 neurons – for all the experiments and baselines. Specific parameters of RAPID are configured as in its original implementation reported in the paper where it was first presented: a buffer size of D=104experiences, batch size of 256 and 5off-policy updates after every episode completion. Moreover, the weights to rank the replay buffer episodes – Expression (5.1) – are set to 𝑤0=1,𝑤1=0.1and 𝑤2=0.001 according to the sensitivity analysis shown in the original approach (Zha, Ma, et al., 2021). 5.4. Results and Analysis 109 In the case of SIL, for the sake of fairness with respect to RAPID the same replay buffer size (D=104) and the same off-policy update ratio (5) are used. Moreover, a SIL loss weight of 0.1and a SIL value loss weight of 𝛽𝑠𝑖𝑙 =0.01 are set. Regarding PER (Schaul et al., 2016), we select a prioritization exponent 𝛼𝑃𝐸𝑅 =0.6and a bias correction factor 𝛽𝑃𝐸𝑅 =0.1. All these parameter values were chosen according to the supplementary material provided in (Oh et al., 2018)2, and taking into account that we aim to solve hard exploration environments. On the other hand, the intrinsic reward when using BeBold is computed as described in Section 5.2.2, calculating the novelty with visitations counts (taking advantage of the discrete state space) and using an intrinsic coefficient of 𝛽=0.005. The value of this coefficient (together with that of the entropy coefficient, 𝑐2) was tailored based on the results of a grid search carried out over scenario MN7S8 – whose results are shown in Figure 5.3 – while keeping the values for other parameters fixed (e.g. the RAPID weight values above referred, namely, 𝑤0,𝑤1and 𝑤2). Figure 5.3: Results of a grid search over the MN7S8 scenario to determine 𝛽(intrinsic motivation coefficient) and 𝑐2(entropy coefficient). (Left) Returns obtained after 3·106training steps; (Right) Number of steps (in scale of millions, 106) required for the agent to achieve an optimal average return (≈0.65) for the first time. 5.4 Results and Analysis This section presents the results of the proposed approach in PCG environments, examining them in depth from different angles: 5.4.1 Performance of self-IL and IM Techniques: Independent versus Combined To begin with, Figure 5.4 analyzes the actual impact on the performance of the agent when using IM and self-IL techniques, either independently or jointly. We observe that BeBold (light blue curve) shows a good behavior only in 2 out of the 4 environments under consideration (namely, MN7S8 and KS4R3). However, it completely fails when dealing with the challenging 2http://proceedings.mlr.press/v80/oh18b/oh18b-supp.pdf 110 Chapter 5. Self-Imitation Learning with Intrinsic Motivation scenarios of MultiRoom and ObstructedMaze series (i.e., MN12S10 and O2Dlh). When using just SIL (green curve), it performs poorly in all scenarios. We here recall what we stated at the beginning of this chapter: other works (e.g., (Ning et al., 2021)) have analyzed the complementarity of SIL and IM, but over problems with sparse rewards that are not so complex as the ones considered in this chapter. When it comes to RAPID, it is capable of solving MultiRoom environments, but struggles over KS4R3 and O2Dlh (as expected). This latter environments are assumed to have larger state spaces and an increasing difficulty from the perspective of exploration. On top of the self-IL approaches, BeBold fosters the exploration and, consequently, renders some actionable learning when using SIL (pink curve). However, results are worse than those obtained when using BeBold in isolation (light blue). This suggests that the SIL prioritization mechanisms are not working properly. Contrarily, results are outstanding when combined with RAPID (light green curve), reducing drastically the number of samples to achieve the same performance level, and attaining a better overall learning when compared to using RAPID in its naive version (blue plot). Besides these improvements, it is interesting to notice that the benefits of using IM remain even when the latter is not enough to learn in isolation: BeBold does not capture any knowledge over MN12S10 and O2Dlh, but it augments the capabilities of RAPID when used in those scenarios. 5.4.2 Evaluation of RAPID with Various IM Strategies A key aspect to study empirically is the capacity of IM to enhance the agent’s exploration while learning. Therefore, it is of utmost importance to assess the sensitivity of the proposed self-IL+IM combination with respect to the selection of the IM approach. With that in mind, and considering that the current implementation is based on BeBold’s tabular version (see Section 5.2.2), we now evaluate the agent’s performance with other two visitation counts strategies: counts (i.e. 𝑟𝑖 𝑡=1/√︁𝑁(𝑠𝑡+1)) and counts1st, which is the same as counts but with episodic restriction. This second set of experiments allows comparing very similar IM strategies that have proven to yield different results due to their intrinsic reward generation scheme (Andres et al., 2022; T. Zhang et al., 2020). The results provided in Figure 5.5 suggest that there is a high relationship between what the agent can learn with IM (without self-IL) and what it actually does by combining them altogether. This can be regarded as a measure of the effectiveness of IM methods when implemented in isolation, where their base functionality of exploring is not wide-spread with the self-IL counterpart. At this point, by just inspecting the results reported in (Andres et al., 2022; T. Zhang et al., 2020), it is clear that counts is the worst method, followed by counts1st and BeBold, 𝑐𝑜𝑢𝑛𝑡𝑠 < 𝑐𝑜𝑢𝑛𝑡𝑠1𝑠𝑡 < 𝐵𝑒𝐵𝑜𝑙𝑑. Differences between counts1st and BeBold are unclear: most of the contribution seems to be related to the 5.4. Results and Analysis 111 BeBold RAPID RAPID+BeBold SIL SIL+BeBold 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN7S8 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN12S10 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return KS4R3 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return O2Dlh Figure 5.4: Results over multiple procedurally generated hard exploration environments in MiniGrid. Both RAPID and SIL always achieve better results when combined with BeBold. episodic restriction part. However, going beyond the boundaries of already explored regions seems to be promising as well, as it yields better results when compared to RND with episodic restriction (T. Zhang et al., 2020). The same comparative performance between IM methods holds when combining them with the ranking replay strategy, where RAPID+counts (red curve) performs slightly better or equal to RAPID in isolation (blue plot), yet being the worst out of the three IM options. Moreover, the choice of one IM strategy over another can actually deteriorate the performance of the agent, as observed in KS4R3. In this particular case, the aforementioned RAPID+counts(red curve) is worse than using RAPID without IM (blue curve). Nevertheless, when selecting demonstrably good IM strategies, the agent combining self-IL+IM – both RAPID+counts1st (yellow curve) and RAPID+BeBold (light green curve) – improves its performance even when it was not able to do it with just the IM strategy. 112 Chapter 5. Self-Imitation Learning with Intrinsic Motivation RAPID RAPID+BeBold RAPID+Counts RAPID+Counts+1st 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN7S8 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN12S10 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return KS4R3 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return O2Dlh Figure 5.5: Performance comparison of RAPID when combined with different IM methods, namely, counts,counts1st and BeBold. 5.4.3 Exploration-exploitation Parameters Evolution in self-IL+IM By introducing IM into the on-policy loss, the agent has to deal with multiple objectives (exploration-exploitation) in various stages: 1) on-policy, by balancing the extrinsic and intrinsic rewards; and 2) off-policy, by keeping in the buffer the most promising experiences parameterized by the extrinsic, local and global scores. In this regard, Figure 5.6 depicts the evolution of some representative values concerning how the exploration is carried out during an experiment. Initially 𝐺𝑖> 𝐺𝑒(i.e., the episodic discounted intrinsic and extrinsic returns calculated as described in Expression 2.3), which evinces that the agent learning process is guided by IM in the absence of extrinsic signals from the environment. Eventually, extrinsic feedback is obtained and gains more importance for the agent’s ability to complete the task. Similarly, the impact of the extrinsic score in Expression (5.1) – 𝑤0·𝑆𝑒𝑥𝑡 , which promotes the exploitation of highly extrinsic rewarded episodes – quickly increases, so that those potential trajectories are more often replayed. However, the selection criterion is also subject to the local score –𝑤1·𝑆𝑙𝑜𝑐𝑎𝑙, which aims to maximize the diversity of observations inside the episode – that also increases until reaching its maximum value of 0.1 5.4. Results and Analysis 113 Gext Gint w0 w1 w2 on-policy off-policy 0.00 0.25 0.50 0.75 1.00 Avg Ext Return MN7S8 0.0 0.2 0.4 Gext VS Gint 0.00 0.25 0.50 0.75 1.00 Impact w0/w1/w2 0.64 3.84 7.04 10.24 13.44 16.64 19.84 Frames/steps (1e6) 0 10 20 Number of updates 0.00 0.25 0.50 0.75 1.00 Avg Ext Return MN12S10 0.0 0.1 0.2 Gext VS Gint 0.00 0.25 0.50 0.75 1.00 Impact w0/w1/w2 0.64 3.84 7.04 10.24 13.44 16.64 19.84 Frames/steps (1e6) 0 5 10 Number of updates 0.00 0.25 0.50 0.75 1.00 Avg Ext Return KS4R3 0.0 0.2 0.4 0.6 Gext VS Gint 0.00 0.25 0.50 0.75 1.00 Impact w0/w1/w2 1.28 7.68 14.08 20.48 26.88 33.28 39.68 Frames/steps (1e6) 0 10 20 Number of updates 0.00 0.25 0.50 0.75 1.00 Avg Ext Return O2Dlh 0.0 0.2 0.4 Gext VS Gint 0.00 0.25 0.50 0.75 1.00 Impact w0/w1/w2 1.28 7.68 14.08 20.48 26.88 33.28 39.68 Frames/steps (1e6) 0 5 10 Number of updates Figure 5.6: Summary of the evolution of different critical values that impact the learning for a given seed in all the scenarios, using RAPID+BeBold. Plots in the first row denote the average extrinsic reward. Plots in the second row depict the difference between the discounted extrinsic (𝐺𝑒𝑥𝑡 ≡𝐺𝑒) and intrinsic (𝐺𝑖𝑛𝑡 ≡𝐺𝑖) returns used in the on-policy update (RL-loss). Figures in the third row show the influence of each component/score of the ranking buffer (𝑤0,𝑤1 and 𝑤2) when sampling from its collected experiences. Finally, plots in the last row indicate the average number of off-policy updates per 10 on-policy updates (ratio of updates, 𝜉). All depicted data correspond to the average value in the given time slots. (which is subject to 𝑚𝑎𝑥(𝑆𝑙𝑜𝑐𝑎𝑙)=1and 𝑤1=0.1). To a lower extent, the global score (𝑤2·𝑆𝑔𝑙𝑜𝑏𝑎𝑙) also plays its role in the selection criterion, which can be helpful during the initial learning stages, when there are no success episodes to complete the task, and also to untie when two episodes require the same amount of steps for the completion of the task. However, its relative importance is lower in comparison to the other scores due to the selected value of the 𝑤2parameter (0.001)3. Frequency of Updates We now proceed by exposing how the ratio 𝜉between the number of onpolicy and off-policy updates changes over the curse of training. In what follows 𝜉is represented as on-policy:off-policy ratio: a 𝜉value of 1:2 will thus imply that the off-policy updates are executed 2 times more frequently than the on-policy ones. 3Recall that the criteria to select such weight values (𝑤0, 𝑤1, 𝑤2) is due to reported results in (Zha, Ma, et al., 2021). 114 Chapter 5. Self-Imitation Learning with Intrinsic Motivation As was explained in Section 2.1.2, an episode can be larger or shorter than a trajectory. On-policy optimization steps are executed once a trajectory4has been finished, and it remains fixed during the whole training. By contrast, off-policy updates are applied once an episode finishes, which varies depending on the maximum steps per episode configured for each environment, and also on the optimality of the agent’s policy at that moment. The decision to execute off-policy updates at the end of the episode was taken from the original paper where RAPID was proposed (Zha, Ma, et al., 2021). Such ratio 𝜉can change from 1:1 to 1:3 in MultiRoom environments, and more dramatically in other scenarios like KS4R3, which initially implies a ratio of 4:1 and can evolve up to a 4:13 relation. In words, the off-policy loss can undergo a modification in its schedule that makes it update more than 10×at its initial frequency (Table 5.1). Such a balance has a critical importance in the agent’s learning process, as it would turn to optimize what is stored in the buffer rather than what is actually experiencing (or vice versa). This generates in turn a big difference between both methods. In fact, in IL this ratio is usually balanced by either using a weight when combining both losses or by carefully tailoring the frequency update (Hester et al., 2017; Sovrano, 2019). Table 5.1: On-policy versus off-policy ratios that can be achieved in each scenario when the supervised loss is backpropagated to when the episode finishes. Each scenario has a different maximum number of steps (row 2) and also different expected number of optimal steps (row 3) (we include an estimation of the optimal steps as it differs from seed to seed). We show the expected initial ratios (𝜉) when the agent cannot solve the task (rows 4 & 6) and when it accomplishes the task via an estimated optimal policy (rows 5 & 7). We also report those values when the rollout size is 𝑇=128 (rows 4-5) and 𝑇=2048 (rows 6-7). MN7S8 MN12S10 KS4R3 O2Dlh Max steps per episode 140 240 480 576 Expected optimum steps 50 105 37 32 𝑇=128 Initial 1:1 2:1 4:1 5:1 Final 1:3 2:2 4:13 5:18 𝑇=2048 Initial 1:14 2:17 4:17 5:18 Final 1:40 2:40 4:216 5:320 5.4.4 Scheduling self-IL Updates To shed further light on the importance of the aforementioned ratio 𝜉, we now fix the off-policy loss to be constant and subject directly to the onpolicy updates. We then analyze how the performance varies under several 4Here we refer as a trajectory to the experiences collected on-policy with a fixed amount of interactions, whereas an episode’s length might vary depending the environment and the learned policy. 5.4. Results and Analysis 115 values for this ratio. Figure 5.7 summarizes the results obtained for this study. In the family of MultiRoom scenarios, the agent is very sensitive to a reduction of the frequency of the off-policy updates, which can eventually make the agent fail when increasing their complexity (e.g. 10:1 in MN12S10). Contrarily, in KS4R3 the original adopted schema (blue curve) with a ratio of 4:1 performs much better than a more frequent update (green plot) of the off-policy part (1:1). This fact is also observed when using a more conservative ratio of 10:1 (red result), suggesting that, although a higher off-policy update frequency can be beneficial at initial stages to bootstrap the learning process in hard exploration tasks, it can eventually degrade the learned knowledge in the long term. These conclusions can also be inferred when using BeBold, but with a better sample-efficiency and optimal solutions. Similar conclusions hold when analyzing O2Dlh. RAPID RAPID+BeBold RAPID 1:1 ratio RAPID+BeBold 1:1 ratio RAPID 10:1 ratio RAPID+BeBold 10:1 ratio 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN7S8 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN12S10 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return KS4R3 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return O2Dlh Figure 5.7: Results over multiple procedurally generated MiniGrid hard exploration environments using different ratios 𝜉between on-policy (PPO) and off-policy (RAPID) updates. The default RAPID approach has a dynamic update ratio, by which it executes an optimization step every time an episode finishes (see Table 5.1). 116 Chapter 5. Self-Imitation Learning with Intrinsic Motivation 5.4.5 Addressing Inter-episode Variance So far, the selected value of the ratio 𝜉seems to be decisive for the success and sample efficiency of the training process. However, the obtained outcomes are very noisy and barely close to optimal results. We hypothesize that this can be due to one of the two losses being unstable. While the seminal work presenting RAPID used PPO with a rollout size5of 𝑇=128, other similar works considering the same environment use a larger time horizon equal to 𝑇=2048, with better and more stable results (Andres et al., 2022; Flet-Berliac et al., 2021). In PCG environments each level is configured differently depending on the selected seed. Consequently, by training the agent with less episodes in a single update, it might get biased to learn specific features present in that subset of episodes, rather than getting the required high-level skills to solve the desired task in the whole possible episode/level distribution. Hence, the increase of the rollout size implies that the agent will be trained – in the on-policy update – with a larger set of episodes (see Table 5.1 to check episode lengths). This forces the algorithm to extract generalizable knowledge in this wider set of slightly different environments, avoiding a by-heart learning. Furthermore, this also reduces the variance of the on-policy updates through the ANN, as the minibatch size will be larger. However, the agent will perform less optimization steps during the training process for the same amount of steps/frames. On this basis, the following question arises: How does the use of larger rollout size impact on the on-policy update regarding the performance and the stabilization of the learned knowledge? The answer can be found by analyzing Figure 5.8. The on-policy update is substantially improved, as can be told from the performance of BeBold (light blue) without being corrupted by off-policy updates. Indeed, this IM approach is able to solve all the environments with the expected optimal steps, obtaining the best result in both KS4R3 and O2Dlh. On the contrary, RAPID (blue) performs worse, and its contribution when combined with BeBold (light green) is also not as good as it has been observed in the previous analysis. The reason for these bad results also connects to what we have previously highlighted: the ratio 𝜉. By increasing the rollout size (𝑇) and by making the off-policy updates be subject to the episode completion, the relevance of the off-policy loss in the agent’s learning process grows up to be 14×,8×,4×and 4× more frequent than the on-policy counterpart in MN7S8,MN12S10,KS4R3 and O2Dlh, respectively, just at the start of the training process (Table 5.1). As we have already observed in Figure 5.7, these ratios do not necessarily guarantee a better learning process. Thus, when adjusting the 5The rollout size is directly related with the number and minibatch size. The increase of the first implies that the minibatch size is also augmented (for the same number of minibatches). For instance, using 𝑇=1024 and 4 minibatches means to have 256-sized minibatches, whereas with 𝑇=128 and using the same number of minibatches this size decreases to 32 units. 5.4. Results and Analysis 117 BeBold (T=2048) RAPID (T=2048) RAPID+BeBold (T=2048) 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN7S8 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return MN12S10 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return KS4R3 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 Timesteps ×107 0.0 0.2 0.4 0.6 0.8 1.0 Avg Extrinsic Return O2Dlh Figure 5.8: Results on multiple hard exploration procedurally-generated environments in MiniGrid when increasing the time horizon up to 2048 in on-policy (RL-loss) updates. Off-policy (supervised/imitation) updates remain with fixed batch size of 256. ratio again with the new rollout size, the performance of both RAPID and RAPID+BeBold drastically changes, as informed in Figure 5.9. A better sample-efficiency can be noted when using a more conservative ratio (1:1, green and pink curves) in both KS4R3 and O2Dlh with respect to the default episode termination setting (blue and light green results). This also occurs when decreasing the off-policy updates down to a 10:1 ratio (red and yellow curves). In this case, the convergence speed can be affected, although it manages to achieve the optimal policy in less steps (the 1:1 ratio struggles more to finally achieve it). In contrast, when applying those updates at the end of the episode, which corresponds with approximately a 1:4 ratio initially in KS4R3 and O2Dlh (Table 5.1), results get worse, just surpassed by the BeBold approach. Concerning MultiRoom environments, increasing the number of off-policy updates seems to be a good strategy, which is difficult to be outperformed by any state-of-the-art solution. In fact, decreasing the frequency of the replayed experiences has a negative impact that can make the agent not learn in the absence of intrinsic rewards. The above discussed behaviors strengthen the claim posed in this chapter: 124 Chapter 6. Concluding Remarks systematically evaluated by means of an ablation study. The conclusion drawn from this work can be summarised as follows: •A centralized critic has greater stability and also leads to faster convergence of optimal policy. As long as the critic is centralized, centralizing also the curiosity module brings advantages that are most noticeable when considering the action to generate the exploration bonus. •The use of IM converts the problem into a bi-objective function in which the explorative side may induce noise into the attainment of the main task objective, ultimately slowing down the learning. One way to address these issues might be through decoupling the exploration and the exploitation behaviours by two different agents (Schäfer et al., 2022) or transforming the problem into a multi-objective approach (Hayes et al., 2021). An interesting avenue would be also reformulate our heterogeneous agent proposal into off-policy strategies (e.g., DQN) where the agents could share their replay buffers and benefit directly from episodes representing how others undertook the same task from different perspectives (Christianos et al., 2020). Additionally, tailoring techniques to leverage expert demonstrations so as to cope with the heterogeneity of the action spaces would be interesting to analyze (e.g., using IL techniques that only rely on observations and do not strictly depend on the actions (Torabi et al., 2018)). •Chapter 4.Analysing fairly the contribution to performance of the state-of-the-art IM algorithms. IM techniques have been shown to be effective for promoting the exploration in RL. Nevertheless, it is not always clear if the proposals are superior due to the presence of novel rewardrelated procedures or to peripheral or additional design choices. On this ground, we conducted a study to try to detach both components and the conclusions were as follows: •Using an adaptive intrinsic coefficient 𝛽based on the return of previous rollouts outperforms strategies relying on a fixed parameter. •The inclusion of episode-level (e.g., episodic visitation counts) for the generation of intrinsic rewards are beneficial in comparison with disregarding episode-level information. •Adopting different neural network architectures is critical to guarantee the success. Indeed, when reducing the number of parameters of the IM modules the performance is deteriorated, which gets even worse if the actor-critic parameters are also decreased. In future extensions, the study of more environments (e.g., Procgen, with high-dimensional observations (Cobbe, Hesse, et al., 2020)) and more IM algorithms to solve efficiently hard exploration environments would be of great interest. •Chapter 5.How to collect good trajectories to improve self-IM algorithms performance Attracted by the idea of replaying not only good 6.1. List of Publications 125 trajectories in terms of performance but also novel trajectories, we proposed the use of IM to promote exploration and discover episodes with interesting properties for the agent’s learning. We evinced that: •As long as the selected IM approach and fitting is appropriate, the benefits are clear. •The method is sensitive to the diversity of the replayed trajectories and the rollout size, i.e. when to execute the updates of the agent’s policy. These are decisive to make the agent generalize well to the whole level distribution of the task. We firmly believe that the results can be improved even more if the diversity of the trajectories is guaranteed; this is, if the demonstrations are not biased and represent the whole level distribution. In addition, more effective ways to manage the scheduling of losses (or even the combination of them in a single loss function (Rajeswaran et al., 2018)) should be studied as well. 6.1 List of Publications As a result of the research conducted during the development of this PhD Thesis, several contributions were published in conferences and journals related to the areas of reinforcement learning and neural networks: •Journal publications: – Alain Andres, Esther Villar-Rodriguez and Javier Del Ser, “Collaborative training of heterogeneous reinforcement learning agents in environments with sparse rewards: what and when to share?” Neural Computing & Applications, published on-line, 2022. https: //doi.org/10.1007/s00521-022-07774-5 (IF: 5.102, Q2, 45/145 ARTIFICIAL INTELLIGENCE). •Conference contributions: – Alain Andres, Esther Villar-Rodriguez, Aritz D. Martinez and Javier Del Ser, “Collaborative Exploration and Reinforcement Learning between Heterogeneously Skilled Agents in Environments with Sparse Rewards,” 2021 International Joint Conference on Neural Networks (IJCNN), Shenzhen, China, pp. 1-10, 2021. https://doi.org/10.110 9/IJCNN52387.2021.9534146. – Alain Andres, Esther Villar-Rodriguez and Javier Del Ser, “An Evaluation Study of Intrinsic Motivation Techniques Applied to Reinforcement Learning over Hard Exploration Environments,” in: A. Holzinger, P. Kieseberg, A. M. Tjoa, E. Weippl (eds). Machine Learning and Knowledge Extraction (CD-MAKE 2022), Lecture Notes in Computer Science, vol 13480, Springer, 2022. https://doi.org/10.100 7/978-3-031-14463-9_13 126 Chapter 6. Concluding Remarks – Alain Andres, Esther Villar-Rodriguez and Javier Del Ser, “Towards Improving Exploration in Self-Imitation Learning using Intrinsic Motivation,” IEEE Symposium Series on Computational Intelligence (SSCI), Singapore, pp. 890-899, 2022. https://doi.org/10.110 9/SSCI51031.2022.10022199 – Alain Andres, Lukas Schäfer, Esther Villar-Rodriguez, Stefano V. Albrecht and Javier Del Ser, “Using Offline Data to Speed-up Reinforcement Learning in Procedurally Generated Environments,” Adaptive and Learning Agents (ALA) Workshop at the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), accepted, London, UK, 2023. 6.2 Future Research Lines This Thesis concludes by outlining future research lines that have been identified as interesting directions during the PhD Thesis: As we have highlighted during this document, sample-efficiency is crucial in RL because despite simulators provide unlimited number of interactions with a good throughput rate, in real-world the systems are actually slow, fragile and expensive to operate, preventing the adoption of RL solutions. This is translated in having a high cost in terms of agentenvironment interactions. One way to overcome it is using offline data to speed up the learning. Imitation Learning approaches have shown an incredible potential as long as demonstrations are available, although their success is usually highly dependant to the quality, quantity and also the diversity of the trajectories. Indeed, we analyzed this issue in PCG environments in a paper that is currently under review –"Using Offline Data to Speed-up Reinforcement Learning in Procedurally Generated Environments"– where IL could overfit the model towards the provided examples. As explained in Section 2.3.2, the most broadly used IL technique is BC due its simplicity and good results. However, better results can be expected when using more advanced techniques such as adversarial IL (Ho & Ermon, 2016; Orsini et al., 2021), curriculum strategies that prioritize demonstrations over others (Bajaj et al., 2022) and even using approaches that take into account temporal dependencies (Paine et al., 2019). Akin to Imitation Learning, Offline RL focus on how to learn in the absence of online interactions. This subfield of RL has shown promising results when having data that do not resemble a demonstration but random data or when being trained with suboptimal and noisy data (Kumar et al., 2022). However, this kind of algorithms exhibit challenges regarding the distribution shift between the offline data and the actual problem distribution, reason why some approaches constrain the policy to not deviate too far from the behavior policy (Kostrikov et al., 2021; Kumar et al., 2020); whereas others focus on prioritizing the usage of experiences to maximize the data coverage or the discovery of skills (H. Liu & Abbeel, 2021a,2021b), ultimately learning a good representation and a versatile policy (Yang & Nachum, 2021). In 6.2. Future Research Lines 127 view of the necessities and potential of these techniques, using offline data envisages an exciting path. Another fascinating branch is the one related to Representation Learning and few-shot learning, which are closely related when generalization is pursued. The ability to understand and discover automatically the key features that govern a task is indeed a game-changer, as it brings the policy with the capacity to quickly adapt when changes in the environment are made (e.g., goal modification, state domain variation), minimizing the total number of online interactions with the environment within the RL domain (X. Chen et al., 2021). Nevertheless, how learn a valid representation is not trivial, requiring sometimes to have different representations between the actor’s policy and the critic (Cobbe, Hilton, et al., 2020; Raileanu & Fergus, 2021). In fact, value-based methods might have some issues when it becomes to generalization capabilities (Ehrenberg et al., 2022; Lyle et al., 2022), which can explain why the large majority of off-policy solutions (that tend to be more sample-efficient than their on-policy counterparts) struggle in PCG environments (Ehrenberg et al., 2022; Mohanty et al., 2021). Last but not least, we feature world models (Ha & Schmidhuber, 2018; Wu et al., 2022) and unsupervised environment design (Dennis et al., 2020; Parker-Holder et al., 2022) as a proxy to avoid the large costs of real-world environment interactions by the virtue of using techniques (e.g. generative models) to generate new instances of the problem without the necessity of explicitly having access to the environment itself. 129 Appendix A Random Network Distillation - Limitations One of the critical aspects when using any prediction error method is how the scale of rewards can vary, not only between environments, but also at points in time in the same scene, making it difficult the selection of hyperparameters. Additionally, if such IM approach uses DL, the normalization of inputs is important for an appropriate prediction. Nonetheless, the latter, is crucial when using RND, as the target network’s parameters are frozen and hence can not adjust the scale of the upcoming observations. According to the recommendations (Burda, Edwards, Storkey, et al., 2018), we normalized the observations as in Expression (3.7). Unexpectedly, we find out that the reward scale was biased towards the features of each room in ViZDooM environment. In order to account for that issue, we proceed as follows: •First, we select observations gather by the agent at different points of the Setup 3 shown in Figure 3.10, which results in the visualizations shown in Figure A.1. •Afterwards, we train the predictor network, ˆ 𝜙(·), during 100 consecutive randomly sampled episodes, and we store both the frozen –𝜙(·)– and trained predictor networks parameters. •Finally, we evaluate which would have been the the obtained intrinsic reward at the selected checkpoints after each episode’s updates. The evolution of the intrinsic rewards considering different changes are shown in Figure A.2. Overall, it can be seen that there is a trend in all the checkpoints to decrease the intrinsic reward over time. However, it is not consistent with the novelty we are pursuing, as the points that rarely might have been visited –the ones that are far from the start position and are very difficult to be experienced without knowledge (e.g., 49 and 50) – have lower bonus respect to others that are closer to the spawn location and that are more often observed (e.g., 0 or 14). In fact, the largest values are given always for observations at rooms 22 and 24. We also experiment if the issue was related to how the input was processed by either providing higher dimensions and using RGB images instead of the default grayscale 130 Appendix A. Random Network Distillation - Limitations configuration (Figure A.2, middle), or by the adopted ANN architecture (Figure A.2, bottom). Nevertheless, there was no significant changes except the amplitude of the novelty signal. Therefore, we conclude that RND presents unforeseen difficulty to capture the actual curiosity and should be taken into account when being used in ViZDooM. Appendix A. Random Network Distillation - Limitations 131 (0) Initial spawn position (14) At room 13 looking forward looking forward (22) At corridor 16 (23) At room 17 oriented to the door in front of the door (40) At room 22 (41) At room 22 oriented to the wall partially oriented to the next corridor (46) At room 24 (47) At room 24 oriented to the wall partially oriented to the next corridor (49) At corridor 25 (50) At room 26 oriented to goal/vest oriented to the goal/vest Figure A.1: Observations (grayscale,120x160) at 10 different checkpoints of VizDoom’s My way home environment. 132 Appendix A. Random Network Distillation - Limitations 0 20 40 60 80 100 episode 0 50 100 150 200 250 300 350 400 0 14 22 23 40 41 46 47 49 50 Default with 42x42 grayscale images and 512 output neurons ANN 0 20 40 60 80 100 episode 0 50 100 150 200 250 300 350 400 42x42 Color 160x120 grayscale Input Processing 0 20 40 60 80 100 episode 0 20 40 60 80 0 20 40 60 80 100 episode 0 5 10 15 20 25 30 100 output neurons 10 output neurons ANN modification 0 20 40 60 80 100 episode 0 20 40 60 80 0 20 40 60 80 100 episode 0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 Figure A.2: Intrinsic rewards evolution throughout 100 randomly sampled episodes at different checkpoints explained in Figure A.1. Cold colors represent locations that are close to the spawn position and farther from the goal/vest. At the top row the default performance with 42x42 grayscale images and the adopted ANN architecture is shown; the middle row shows the impact when varying the input image by either using 42x42 colored images (left) or 160x120 images; the bottom row results illustrate how changes in the ANN architecture affect when using 100 output neurons (left) or just 10 output neurons (right). 133 Bibliography Abbeel, P., & Ng, A. Y. (2004). Apprenticeship learning via inverse reinforcement learning. 21st International Conference on Machine Learning (ICML), 1. Abolafia, D. A., Norouzi, M., Shen, J., Zhao, R., & Le, Q. V. (2018). Neural Program Synthesis with Priority Queue Training [arXiv:1801.03526]. Anderson, C. W. (1986). Learning and Problem-Solving with Multilayer Connectionist Systems (Adaptive Strategy Leraning, Neural Networks, Reinforcement Learning). Doctoral Dissertation, 1–260. Andres, A., Villar-Rodriguez, E., & Del Ser, J. (2022). An Evaluation Study of Intrinsic Motivation Techniques Applied to Reinforcement Learning over Hard Exploration Environments. In A. Holzinger, P. Kieseberg, A. M. Tjoa, & E. Weippl (Eds.), Machine Learning and Knowledge Extraction (pp. 201–220). Springer International Publishing. Andrychowicz, M., Raichuk, A., Stańczyk, P., Orsini, M., Girgin, S., Marinier, R., Hussenot, L., Geist, M., Pietquin, O., Michalski, M., Gelly, S., & Bachem, O. (2021a). What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study [arXiv:2006.05990]. Andrychowicz, M., Raichuk, A., Stańczyk, P., Orsini, M., Girgin, S., Marinier, R., Hussenot, L., Geist, M., Pietquin, O., Michalski, M., Gelly, S., & Bachem, O. (2021b). What Matters for On-Policy Deep ActorCritic Methods? A Large-Scale Study. 9th International Conference on Learning Representations (ICLR). Aubret, A., Matignon, L., & Hassas, S. (2019). A survey on intrinsic motivation in reinforcement learning [arXiv:1908.06976]. Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning,47(2), 235– 256. Aytar, Y., Pfaff, T., Budden, D., Paine, T., & Wang, Z. (2018). Playing hard exploration games by watching YouTube. Advances in Neural Information Processing Systems (NeurIPS), 12. Badia, A. P., Piot, B., Kapturowski, S., Sprechmann, P., Vitvitskyi, A., Guo, D., & Blundell, C. (2020). Agent57: Outperforming the Atari Human Benchmark. 37th International Conference on Machine Learning (ICML),119. Badia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., & Blundell, C. (2020). Never Give Up: Learning Directed Exploration Strategies. International Conference on Learning Representations (ICLR).