Year: 2021

Abstract:
A central question in reinforcement learning (RL) is how to leverage prior knowledge to accelerate learning in new tasks. We propose a Bayesian exploration method for lifelong reinforcement learning (BLRL) that aims to learn a Bayesian posterior that distills the common structure shared across different tasks. We further derive a sample complexity analysis of BLRL in the finite MDP setting. To scale our approach, we propose a variational Bayesian Lifelong Learning (VBLRL) algorithm that is based on Bayesian neural networks, can be combined with recent model-based RL methods, and exhibits backward transfer. Experimental results on three challenging domains show that our algorithms adapt to new tasks faster than state-of-the-art lifelong RL methods.

heading: 1 INTRODUCTION
text: Reinforcement-learning (RL) methods (Sutton & Barto, 1998; Kaelbling et al., 1996) have been successfully applied to solve challenging individual tasks such as learning robotic control (Duan et al., 2016) and playing expert-level Go (Silver et al., 2017). However, in the real world, a robot usually experiences a collection of distinct tasks that arrive sequentially throughout its operational lifetime; learning each new task from scratch is infeasible, but treating them all as a single task will fail. Therefore, recent research has focused on algorithms that enable agents to learn across multiple, sequentially posed tasks, leveraging past knowledge from previous tasks to accelerate the learning of new tasks. This problem setting is known as lifelong reinforcement learning (Brunskill & Li, 2014; Wilson et al., 2007b; Isele et al., 2016b). The key questions in lifelong RL research are: How can an algorithm exploit knowledge gained from past tasks to improve performance in new tasks (forward transfer), and how can data from new tasks help the agent to perform better on previously learned tasks (backward transfer)?
To answer these two questions, first consider a simple problem, which is to find different items in different houses. Here, a single task corresponds to finding items in a specific house. Although items may be stored in different locations in different houses, there still exists some shared information that connects all houses. For instance, a toothbrush is more likely to be found in a bathroom than a kitchen, and a room without a window is more likely to be a bathroom than a living room. Such information can significantly accelerate the search for items in newly encountered houses. We propose that extracting the common structure existing in previously encountered tasks can help the agent quickly learn the dynamics of the new tasks. Specifically, this paper considers lifelong RL problems that can be modeled as hidden-parameter MDPs or HiP-MDPs (Doshi-Velez & Konidaris, 2016; Killian et al., 2017), where variations among the true task dynamics can be described by a set of hidden parameters. We model two main categories of learning across multiple tasks: the world-model distribution, which describes the probability distribution over tasks, and the task-specific model, that defines the (stochastic) dynamics within a single task. To enable more accurate sequential knowledge transfer, we separate the learning process for these two quantities and maintain a hierarchical Bayesian posterior to approximate them. The world-model posterior is designed to manage the uncertainty in the world-model distribution, while the task-specific posterior handles the uncertainty from the data collected from only the current task.
We propose a Bayesian exploration method for lifelong RL (BLRL) that learns a Bayesian worldmodel posterior that distills the common structure of previous tasks, and then uses it as a prior to learn a task-specific model in each subsequent task. For the discrete case, we derive an explicit
performance bound that shows that the task-specific model requires fewer samples to become accurate as the world-model posterior approaches the true underlying world-model distribution. We further develop VBLRL, a more scalable version of BLRL that uses variational inference to approximate the world-model distribution and leverages Bayesian Neural Networks (BNNs) to build the hierarchical Bayesian posterior. Our experimental results on a set of challenging domains show that our algorithms achieve better forward and backward transfer performance than state-of-the-art lifelong RL algorithms within limited samples for each task.

heading: 2 BACKGROUND
text: RL is the problem of maximizing the long-term expected reward of an agent interacting with an environment (Sutton & Barto, 1998). We usually model the environment as a Markov Decision Process or MDP (Puterman, 1994), described by a five tuple: 〈S,A,R, T, γ〉, where S is a finite set of states; A is a finite set of actions; R : S ×A 7→ [0, 1] is a reward function, with a lower and upper bound 0 and 1; T : S ×A 7→ Pr(S) is a transition function, with T (s′|s, a) denoting the probability of arriving in state s′ ∈ S after executing action a ∈ A in state s; and γ ∈ [0, 1) is a discount factor, expressing the agent’s preference for delayed over immediate rewards.
An MDP is a suitable model for the task facing a single agent. In the lifelong RL setting, the agent instead faces a series of tasks τ1, ..., τn, each of which can be modeled as an MDP: 〈S(i), A(i), R(i), T (i), γ(i)〉. A key question is how these task MDPs are related; we model the collection of tasks as a HiP-MDP (Doshi-Velez & Konidaris, 2016; Killian et al., 2017), where a family of tasks is generated by varying a latent task parameter ω drawn for each task according to the world-model distribution PΩ. Each setting of ω specifies a unique MDP, but the agent neither observes ω nor has access to the function that generates the task family. Formally, then, the dynamics T (s′|s, a;ωi) and reward function R(r|s, a;ωi) for task i depend on ωi ∈ Ω, which is fixed for the duration of the task. For lifelong RL problems, the performance of a specific algorithm is usually evaluated based on both forward transfer and backward transfer results (Lopez-Paz & Ranzato, 2017):
• Forward transfer: the influence that learning task t has on the performance in future task k t.
• Backward transfer: the influence that learning task t has on the performance in earlier tasks k ≺ t.
3 BAYESIAN EXPLORATION FOR LIFELONG REINFORCEMENT LEARNING
𝜔𝑖 Ψ
𝑚𝑖
𝜏𝑗
𝑖 = 1 ⋯ 𝐾
𝑗 = 1 ⋯ 𝑅
Figure 1 shows our generative model in plate notation. Ψ is the parameter set that represents distribution PΩ. It functions as the world-model posterior that aims to capture the common structure across different tasks. The resulting MDP mi is created based on ωi, which is one hidden parameter sampled from Ψ. We can sample from our approximation of Ψ to create and solve possible MDPs.
The proposed BLRL approach is formalized in Algorithm 3 in the appendix. Initially, before any MDPs are experienced, the world-model posterior qe(·|st, at) is initialized to an uniformed prior. For each new task mi, we first initialize the task-specific posterior qmiθ (·|st, at) with the parameter values from the current world-model posterior, and then, for each timestep, select actions using a Bayesian exploration algorithm based on sampling from this posterior (Thompson, 1933; Asmuth et al., 2009). A set of sampled MDPs drawn from qmiθ is a concrete representation of the uncertainty within the current task. BLRL samples K models from the task-specific posterior whenever the number of transitions from a state–action pair has reached threshold B. Analogously to RMAX (Brafman & Tennenholtz, 2003) and BOSS (Asmuth et al., 2009), we call a state–action pair known whenever it has been observed Nst,at = B times. For each state–action pair, if it is known, we use the taskspecific posterior to sample the model. If it is unknown, we instead sample from the world-model posterior. These models are combined into a merged MDP m#i and BLRL solves m # i to get a policy π∗ m#i
. This approach is adopted from BOSS (best of sampled set) to create optimism in the face of uncertainty, and thereby drive exploration. The new policy π∗
m#i will be used to interact
with the environment until a new state–action pair reaches the sampling threshold. The collected transitions from this task will be used to update the task-specific posterior immediately, while the world-model posterior will be updated using transitions from all the previous tasks at a slower pace. For simple finite MDP problems in practice, we use the Dirichlet distribution (the conjugate for the multinomial) to represent the Bayesian posterior. Thus, the updating process for the posterior is straightforward to compute. Intuitively, BLRL is able to rapidly adapt to new tasks as long as the prior of the task-specific model (that is, the world-model posterior) is close to the true underlying model and captures the uncertainty of the common structure of a set of tasks.

heading: 3.1 SAMPLE COMPLEXITY ANALYSIS
text: We now provide a simple theoretical analysis of BLRL. First, we use the setting and results of Zhang (2006) to describe the properties of the Bayesian prior and how it relates to the sample complexity for the concentration of the Bayesian posterior.
Lemma 1. Let π(ω) denote the prior distribution on the parameter space Γ. We consider a set of transition-probability densities p(·|ω) indexed by ω, and the true underlying density q. Define the prior-mass radius of the transition-probability densities as:
dπ = inf{d : d ≥ − lnπ({p ∈ Γ : DKL(q||p) ≤ d})}. (1)
Intuitively, this quantity measures the distance between the Bayesian prior we use to initialize the posterior and the true underlying distribution. Then, ∀ρ ∈ (0, 1) and η ≥ 1, let
εn = (1 + 1
n )ηdπ + (η − ρ)εupper,n((η − 1)/(η − ρ)), (2)
where εupper,n is the critical upper-bracketing radius (Zhang, 2006). The decay rate of εupper,n controls the consistency of the Bayesian posterior distribution (Asmuth et al., 2009). Let ρ = 12 , we have for all t ≥ 0 and δ ∈ (0, 1), with probability at least 1− δ,
πn ({ p ∈ Γ : ||p− q||21/2 ≥
2εn + (4η − 2)t δ/4 }∣∣∣X) ≤ 1 1 + ent . (3)
Proof (sketch). The proof is similar to that of Corollary 5.2 of Zhang (2006) (see Appendix A.5). Instead of using the critical prior-mass radius επ,n to describe certain characteristics of the Bayesian prior, we define and use the prior-mass radius dπ, which is independent of the sample size n and measures the distance between the prior and true distribution.
Similar to BOSS, for a new MDP m ∼M with hidden parameters ωm, we can define the Bayesian concentration sample complexity for the task-specific posterior: f(s, a, 0, δ0, ρ0), as the minimum number c such that, if c IID transitions from (s, a) are observed, then, with probability at least 1− δ0,
Prm∼posterior(||Tm(s, a, ωm)− Tm∗(s, a, ωm)||1 < 0) ≥ 1− ρ0. (4)
Lemma 2. Assume the posterior is consistent (that is, εupper,n = o(1)) and set η = 2, then the Bayesian concentration sample complexity for the task-specific posterior f(s, a, , δ, ρ) =
O ( dπ+ln 1 ρ
2δ−dπ
) .
Proof (sketch). This bound can be derived by directly combining Lemma 1 and Equation 4.
The above lemma suggests an upper bound of the Bayesian concentration sample complexity using the prior-mass radius. We can further combine this result with PAC-MDP theory (Strehl et al., 2006) and derive the sample complexity of the algorithm for each new task.
Theorem 1. For each new task, set the sample size K = Θ(S 2A δ ln SA δ ) and the parameters 0 =
(1− γ)2, δ0 = δSA , ρ0 = δ S2A2K , then, with probability at least 1− 4δ, V At(st) ≥ V ∗(st)− 4 0
in all but Õ( S 2A2dπ
δ 3(1−γ)6 ) steps, where Õ(·) suppresses logarithmic dependence.
Proof (sketch). The proof is based on the PAC-MDP theorem (Strehl et al., 2009) combined with the new bound for the Bayesian concentration sample complexity we derived in Lemma 2. In general, we use the same process in BOSS to verify the three required properties of PAC-MDP: optimism, accuracy and learning complexity. For each new task, the main difference between BLRL and BOSS is that we use the world-model posterior to initialize the task-specific posterior, which results in a new sample complexity bound based on the prior-mass radius.
The result formalizes the intuition that, if we put a larger prior mass at a density that is close to the true q such that dπ is small, the sample complexity of our algorithm will be lower. In the meantime, the sample complexity is bounded by polynomial functions of the relevant quantities, showing that our training strategy preserves the properties required by PAC-MDP algorithms (Strehl et al., 2009).

heading: 4 SCALING UP: VARIATIONAL BAYESIAN LIFELONG RL
text: Directly computing the exact posterior is typically not possible for large scale problems. Instead, we propose a practical approximate algorithm, VBLRL, that uses neural networks and variational inference (Hinton & van Camp, 1993a). We model the posterior via the transition dynamics using p(st+1, rt|st, at; θ), θ ∈ Θ. The posterior, given a new state–action pair, can be rewritten via Bayes’ rule:
p(θ|Dt, at, st+1, rt) = p(θ|Dt)p(st+1, rt|Dt, at; θ)
p(st+1, rt|Dt, at) , (5)
where Dt is the agent’s history with all the experienced tasks up until time step t. As representing the posterior p(θ|D) is intractable, we approximate it through an alternative distribution q(θ;φ) by minimizing DKL[q(θ;φ)||p(θ|D)], leveraging variational lower bounds (Hinton & van Camp, 1993b; Houthooft et al., 2016).
We choose Bayesian neural networks (BNN) to approximate the posterior. The intuition is that, in the context of stochastic outputs, BNNs naturally approximate the hierarchical Bayesian model since they also maintain a learnable distribution over their weights and biases (Graves, 2011; Houthooft et al., 2016). We expect the uncertainty embedded in the weights and biases of networks can capture the epistemic uncertainty introduced by hidden parameters of different tasks, while we also set the outputs of the neural networks to be stochastic to capture the aleatoric uncertainty within each specific task. In our case, the BNN weights and biases distribution q(θ;φ) can be modeled as fully factorized Gaussian distributions (Blundell et al., 2015):
q(θ;φ) = |Θ|∏ i=1 N (θi|µi, σ2i ), (6)
where φ = {µ, σ}, and µ is the Gaussian’s mean vector while σ is the covariance matrix diagonal. Then, the posterior distribution over the model parameters can be computed through:
φt = arg min φ
[ DKL[q(θ;φ)||p(θ)]− Eθ∼q(·;φ)[log p(st+1, rt|Dt, at; θ)] ] , (7)
where p(θ) represents the fixed prior distribution of θ. The second term on the right hand side can be approximated through 1N ∑N i=1 log p(st+1, rt|Dt, at; θi) with N samples from θi ∼ q(φ). This optimization can be performed in parallel for each s, keeping φt−1 fixed.
We provide the intuition of how our design capture the uncertainties of lifelong RL in Figure 2 and summarize the method in Algorithm 1. The left side of the figure shows the process of how transitions are generated from the environment’s true distribution, while the other parts show how our models generate transition predictions and how they separately estimate different uncertainties generating from approximating the true underlying distribution. We employ our posterior knowledge models in the context of a model-based RL method. When encountering a new task, VBLRL first uses the model parameters (that is, {µ, σ} of weights and biases of BNN) from the general knowledge model to initialize the task-specific posterior network. The task-specific model outputs the predicted next state and reward given a state–action pair. Then, we use model-predictive control (Garcia et al., 1989) to select actions based on the generated transitions.
For planning, at each step, we begin by creating P particles from the current state spτ=t = st∀p. Then we sample N candidate action sequences at:t+T from a learnable distribution. We propagate the state-action pairs using the learned task-specific model pmi(·|s, a) (BNN) and use the cross entropy method (Botev et al., 2013) to update the sampling distribution to make the sampled action sequences close to previous action sequences that achieved high reward. We further calculate the cumulative reward estimated (via the learned model) for previously sampled sequences and use the mean of that distribution to select the current action.
The task-specific posterior is updated using the data collected from only the current task. The world-model posterior is updated after a few more steps with the collected transitions from all the visited tasks. The intuition is to guide the two posteriors to separately learn two categories of uncertainty within lifelong learning tasks. Note that other CEM-based model-based RL algorithms like PETS (Chua et al., 2018) usually maintain a set of neural networks using the same training data, and sample action sequences from each of the neural nets to achieve randomness in transitions. Besides the problem of requiring special training tricks, it is unrealistic to maintain (≥ 30) models for each task in lifelong RL settings. Our usage of BNNs avoids such problems as we only have to train one neural network using the same data for each task, and we can sample an unlimited number of different action sequences to cover more possibilities as needed. In PETS, the epistemic uncertainty
is estimated via the variance of the output mean of different neural networks, while in VBLRL, it is estimated via the variance of the weights and biases distribution of BNN during training. This is implied as the objective function we use to update φt is from minimizing DKL[q(θ;φ)||p(θ|D)].
Algorithm 1: Variational Bayesian Lifelong RL Initialize general knowledge model pwm(·|s, a; θwm), replay buffer Dm1 , · · · , DmM for each task mi from i = 1, 2, 3, · · · ,M do
Initialize task-specific model pmi(·|s, a; θmi) with general knowledge model pwm for each episode do
for Time t = 0 to TaskHorizon do Sample Actions at:t+T ∼ CEM(·) Propagate state particles spτ with pmi(s
′|s, a) Evaluate actions as ∑t+T τ=t 1 P ∑P p=1 pmi(r|s, a) Update CEM(·) distribution. Execute optimal actions a∗t:t+T
end Add transitions to replay buffer Dmi Update task-specific model according to Equation (7) given Dmi Update general knowledge model according to Equation (7) given {Dm1 , · · · , Dmi}
end end

heading: 4.1 BACKWARD TRANSFER OF VARIATIONAL BAYESIAN LIFELONG RL
text: In our lifelong RL setting, the agent interacts with each task for only a limited number of episodes and the task-specific model stops learning when the next task is initiated. As a result, there may exist portions of the transition dynamics in which model uncertainty remains high. However, as the world-model posterior continues to train on new tasks, it gathers more experience in the whole state space and can provide improvements in its guesses concerning the “unknown” transition dynamics, even for previously encountered tasks.
Intuitively, the performance of an agent on one task has the potential to be further improved (positive backward transfer) if there exists a sufficiently large set of state–action transition pairs of which the task-specific model’s predictions are not confident due to lack of data. This type of model uncertainty is sometimes called epistemic uncertainty (Kiureghian & Ditlevsen, 2009; Ciosek et al., 2020). In our algorithm, the aleatory variability (irreducible chance in the outcome) is measured by the output variance of the prediction {σrpτ , σspτ }, and the epistemic uncertainty (due to lack of experience) corresponds to the uncertainty of the output mean and variance (see Definition 1 below). Thus, a straightforward method to improve a previously learned task-specific model is to find the predictions it needs to make that have high epistemic uncertainty, and replace them with the predictions from the world-model posterior, which has lower epistemic uncertainty. If we only consider reward prediction, the conditions for measuring whether a task-specific model is sufficiently confident are as follows. Definition 1. Assume there exist known constants δµr , δσr . For a given state–action pair (s, a), the task-specific model (reward) is proclaimed confident when the following conditions are satisfied:∑P
p=1(µrpτ − µrpτ ) 2
P − 1 < δµr ,
∑P p=1(σrpτ − σrpτ )2
P − 1 < δσr ,
(8)
where P is the number of particles. Similar definition applies to the task-specific model’s next-state prediction. Intuitively, δµr and δσr function as the threshold to judge whether the uncertainty of the output mean or variance for each dynamic prediction is too high to be called as a confident prediction.
The detailed backward transfer testing algorithm can be found in the appendix. In practice, it is often hard to find specific confidence thresholds (δµs , δµr , δσs , δσr ) that are effective. Instead, we implement a simpler approach: During planning, for each prediction, we compare the uncertainty of the output mean and variance of the world model and the task-specific model, and then choose the one with lower values, which indicates higher confidence level.

heading: 5 EXPERIMENTS

heading: 5.1 GRID-WORLD ITEM SEARCHING
text: We first evaluate BLRL in a simple Grid-World domain. Our testbed consists of a collection of houses, each of which has four rooms. The goal of each task is to find a specific object (blue, green or purple) in the current house. The type of each room is sampled based on an underlying distribution given by the environment. Each room type has a corresponding probability distribution of which kind of objects can be found in rooms of this type. Different tasks/houses vary in terms of which rooms are which types and precisely where objects are located in the room (the task’s hidden parameters).
To simplify the problem, instead of modeling the whole MDP distribution, we use BLRL to model the object distribution as the Bayesian posterior and sample MDPs from the distribution. We use BOSS with a fixed prior (no intertask transfer) as our baseline. The average training performance of all 300 tasks are shown in Figure 3 top right. Each task consists of 10 epochs, with 21 sample steps for each epoch. Within the limited steps allotted for each task, BLRL is able to discover and transfer the common knowledge and helps the agent quickly adapt to new tasks as the training goes on. In comparison, running BOSS with a fixed prior is able to find the optimal policy eventually but needs more sample steps and learns more slowly than BLRL.

heading: 5.2 BOX-JUMPING TASK
text: We use a simplified version of the jumping task (des Combes et al., 2018) as a testbed for the proposed algorithm VBLRL. As shown in Figure 3 bottom left, the goal of the agent is to reach the right side of the screen by jumping over the obstacle. The agent can only choose from two actions: jump and right. It will hit the obstacle unless the jump action is chosen at precisely the right time. We set different obstacle positions as different tasks, constituting the HiP-MDP hidden parameters. The 4-element state vector describes the (x, y) coordinates of the agent’s current position, and its velocity in the x and y directions.
Figure 3 bottom right presents the average performance during training across all 300 tasks. Each task is run for 30 episodes. We compare VBLRL against state-of-the-art lifelong RL methods LPGFTW (Mendez et al., 2020) from the multi-model category, EWC (Kirkpatrick et al., 2016) from the single-model category, singel-task model-base RL baseline (using the same BNN structure and planning procedures) as well as a HiP-MDP baseline (Killian et al., 2017). For a fair comparison, we further replace the DDQN algorithm (van Hasselt et al., 2016) used in Killian et al.’s paper with CEM planning, and let the transition model also predict the reward for each state–action pair. This modified
baseline is similar to the single-model version of VBLRL (i.e., only using the world-model posterior). VBLRL clearly learns faster than the HiP-MDP baseline and reaches better final performance. Thus, in the lifelong RL setting, separating the updating processes of the world-model posterior and the task-specific posterior can lead to better learning efficiency.

heading: 5.3 OPENAI GYM MUJOCO DOMAINS
text: We evaluate the performance of VBLRL on HiP-MDP versions of several continuous control tasks from the Mujoco physics simulator (Todorov et al., 2012), HalfCheetah-gravity, HalfCheetahbodyparts, Hopper-gravity, Hopper-bodyparts, Walker-gravity, Walker-bodyparts, all of which are lifelong-RL benchmarks used in prior work1 (Mendez et al., 2020). For each of six different domains, the task-specific hidden parameters correspond to different gravity values or different sizes and masses of the simulated body parts. More details can be found in the appendix. Compared with prior work, we substantially reduced the number of iterations that the agent can sample and train on (100 iterations for each task and a horizon of 100/200 for each iteration). We used such settings to increase the difficulty of lifelong learning and ensure that no learning-from-scratch algorithm could obtain a good policy in the available training time.
The results are shown in Table 1. We compare our algorithm against the three algorithms described in Section 5.2. For all six domains, we report the average performance of all the tasks at the beginning of training (Start) and after all training for each new task (Train), as well as the average performance for all previous tasks after training for a given number of tasks, which is the backward transfer test (Back). As shown in the results, our method VBLRL shows better performance on all three test stages of the HalfCheetah domain and Walker domain, as well as better backward transfer performance on Hopper-gravity and Hopper-bodyparts than the other three algorithms. LPG-FTW exhibits better forward training performance in the Hopper domain, but still shows some signs of catastrophic forgetting as there is a huge gap between its training performance and backward performance. EWC fails in most of the tasks as the tasks are diverse and we set very limited sample steps for each task, which means it is hard to directly learn a single shared policy that achieves good performance. The HiP-MDP baseline shows good results on some of the tasks because it is more sample-efficient to learn a shared model across all the tasks and easier to capture the world-model uncertainty. However, it cannot achieve as good performance as VBLRL as it is hard to model the task-specific uncertainty using only one model across all tasks, which also leads to the negative backward transfer performance on Cheetah-Gravity. Comparing VBLRL’s performance on the Train stage and Back stage, we also find that it shows positive backward transfer results on most of the tasks, without showing patterns of catastrophic forgetting. Overall, VBLRL’s world-model posterior contributes to better forward
1We changed the environment settings for Hopper and Walker to make them amenable to model-based RL following Wang et al. (2019).
transfer performance (Start), the learning of task-specific posterior contributes to better forward transfer training for each new task (Train), and the combination of these two posteriors guides the agent to achieve better backward transfer performance (Back).

heading: 6 RELATED WORK
text: HiP-MDPs (Doshi-Velez & Konidaris, 2016) provide a framework for studying lifelong RL. Published HiP-MDP methods use Gaussian Processes (Doshi-Velez & Konidaris, 2016) or Bayesian neural networks (Killian et al., 2017) to find a single model that works for all tasks, which may trigger catastrophic forgetting. Other single-model lifelong RL algorithms encourage transfer across tasks by modifying objective functions. EWC (Kirkpatrick et al., 2016) imposes a quadratic penalty that pulls each weight back towards its old values by an amount proportional to its importance for performance on previously-learned tasks to avoid forgetting. There are several extensions of this work based on the core idea of modifying the form of the penalty (Li & Hoiem, 2017; Zenke et al., 2017; Nguyen et al., 2018). Another category of lifelong RL methods uses multiple models with shared parameters and task-specific parameters to avoid or alleviate the catastrophic problem (Bou-Ammar et al., 2014; Isele et al., 2016a; Mendez et al., 2020). The drawback of this method is that it is hard to incorporate the knowledge learned from previous tasks during initial training on a new task (Mendez et al., 2020).Nagabandi et al. (2019) introduce a model-based continual learning framework based on MAML, but they focus on discovering when new tasks were encountered without access to task indicators.
Research in Meta-RL (Wang et al., 2016; Finn et al., 2017) and multi-task RL (Parisotto et al., 2016; Teh et al., 2017) settings also attempts to find ways to accelerate learning by transferring knowledge from different tasks. Some work employs the MAML framework with Bayesian methods to learn a stochastic distribution over initial parameter (Yoon et al., 2018; Grant et al., 2018; Finn et al., 2018). Other work uses the collected trajectories to infer the hidden parameter, which is taken as an additional input when computing the policy (Rakelly et al., 2019; Zintgraf et al., 2020; Fu et al., 2021). Our method, however, focuses on problems where the tasks arrive sequentially instead of having a large number of tasks available at the beginning of training. This sequential setting makes it hard to accurately infer the hidden parameters, but opens the door for algorithms that support backward transfer. Further, our method approximates the true HiP-MDP model by learning the Bayesian posterior over past tasks and uses it to initialize a model for each new task, encouraging the agent to explore places where the epistemic uncertainty of the world model is high.
Some prior work uses Bayesian methods in RL to quantify uncertainty over initial MDP models (Ghavamzadeh et al., 2015; Asmuth & Littman, 2011; Guez et al., 2012). Several algorithms start from the idea of sampling from a posterior over MDPs for Bayesian RL, maintaining Bayesian posteriors and sampling one complete MDP (Strens, 2000; Wilson et al., 2007a) or multiple MDPs from this distribution (Asmuth et al., 2009). Instead of focusing on single-task RL, our algorithm aims to find a posterior over the common structure among multiple tasks. Wilson et al. (2007a) uses a hierarchical Bayesian infinite mixture model to learn a strong prior that allows the agent to rapidly infer the characteristics of new environment based on previous tasks. However, it only infers the category label of a new MDP and uses that information to find parameter values. Moreover, their method only works in discrete settings and cannot be applied to the kind of continuous problems we included in our evaluation. Lifelong learning has also been widely studied within the supervised learning domain with explicit performance bounds (Baxter, 2000; Pentina & Lampert, 2014). Our work is one of the first papers to give explicit sample complexity bounds for lifelong reinforcement learning algorithm, where data efficiency is essentially important.

heading: 7 CONCLUSION
text: To address the lifelong RL problems, our work proposed to distill the shared knowledge from similar MDPs and maintain a Bayesian posterior to approximate the distribution derived from that knowledge. We gave a sample complexity analysis of the algorithm in the finite MDP setting. Then, we extended our method to use variational inference, which scales better and supports both backward and forward transfer. Our experimental results show that the proposed algorithms enables faster training on new tasks through collecting and transferring the knowledge learned from preceding tasks.

heading: A APPENDIX

heading: A.1 BACKWARD TRANSFER
text: We take backward transfer to be the influence of subsequent learning on the agent’s performance of a previous task. Negative backward transfer, which is also known as catastrophic forgetting, describes the scenario in which the agent’s progress on a task is erased after learning new tasks (French, 1993; Carpenter & Grossberg, 1988; Robins, 1995). Our algorithm avoids catastrophic forgetting as it maintains a separate task-specific model for each task. In the mean time, there are circumstances in which VBLRL exhibits positive backwards transfer as introduced in the main text.
Algorithm 2: Variational Bayesian Lifelong RL (Backward transfer) input :Test task mi, model uncertainty thresholds δµs , δµr , δσs , δσr for Time t = 0 to TaskHorizon do
for Trial k = 1 to K do Sample Actions at:t+T ∼ CEM(·) for each action do
Propagate state particles spτ and reward r p τ with Tmi(s ′, r|s, a) if Tmi(s′, r|s, a) is not confident (Definition 1) then
Repropagate state particles spτ and reward r p τ with Te(s ′, r|s, a) end
end Evaluate actions as ∑t+T τ=t 1 P ∑P p=1 Tmi(r|s, a)
Update CEM(·) distribution. end Execute optimal actions a∗t:t+T
end
The difference between the backward transfer version and the forward training version is that, when we do predictions for the state particles, each time we will also calculate the confidence level (Definition 1) of the task-specific model for this particular transition. If the task-specific model is not confident enough for this state–action pair, we will use the world-model instead and recalculate the prediction value.
In practice, it is often hard to find specific confidence thresholds (δµs , δµr , δσs , δσr ) that are effective. Instead, we implement a simpler approach: During planning, for each prediction, we compare the uncertainty of the output mean and variance of the world model and the task-specific model, and then choose the one with lower values, which indicates higher confidence level. Here is a link to the learned behaviors of VBLRL https://youtu.be/I7RAT6g9v5w. The video shows the agent trained by our algorithm learns some meaningful behaviors at the current setting within limited steps, and performs better compared with the behaviors learned by other baseline algorithms.

heading: A.2 BNN MODEL
text: As we model the transition models as Gaussian distributions:
T (·|s, a) = N (fµθ (s, a), f σ θ (s, a)) (9)
The function fθ represented as a Bayesian neural network parameterized by θ, which is further modeled as the posterior distribution parameterized by φ, predicts the mean µs, µr and variance σs, σr given current state and action s, a. To make it clearer, we can view the BNN model in VBLRL as an infinite neural network ensemble by integrating out its parameters:
T (s′, r|s, a) = ∫
Θ
T (s′, r|s, a; θ)q(θ;φ)dθ (10)
Compared to previous model-based algorithms that use finite number of neural network ensembles (e.g. PETS), our choice of BNN is more suitable for lifelong RL as we only need to maintain one neural network for each task, and we can sample an unlimited number of predictions from it which better estimates the uncertainty and is essential in our setting where both dynamic function and reward function are not given unlike prior model-based RL methods.

heading: A.3 BLRL ALGORITHM
text: Algorithm 3: Lifelong Bayesian Sampling Approach Algorithm input :K, B initialize MDP set, the world-model posterior qe(st+1, rt|st, at); for each MDP mi do
Ns,a ← 0,∀s, a do sample← TRUE ; initialize the task-specific posterior qmiθ (st+1, rt|st, at)← qe(st+1, rt|st, at); for all timesteps t = 1, 2, 3, ... do
if do sample then Sample K models mi1 , mi2 ,···,miK from the task-specific posterior qmiθ (st+1, rt|st, at).;
Merge the models into the mixed MDP m#i ; Solve m#i to obtain π
∗ m#i ; do sample← FALSE
end Use π∗
m#i for action selection: at ← πm#i (st) and observe reward rt and next state st+1 ;
Nst,at ← Nst,at + 1; Update the task-specific posterior distribution qmiθ (st+1, rt|st, at) for the current MDP; if Nst,at = B then
Update the world-model posterior distribution qe(st+1, rt|st, at) with the collected transitions; do sample← TRUE
end end
end

heading: A.4 EXPERIMENTAL SETTING

heading: A.4.1 GRID-WORLD ITEM SEARCHING
text: Our testbed consists of a collection of houses, each of which has four rooms. The goal of each task is to find a specific object (blue, green or purple) in the current house. The type of each room is sampled based on an underlying distribution given by the environment. Each room type has a corresponding probability distribution of which kind of objects can be found in rooms of this type. Different tasks/houses vary in terms of which rooms are which types and precisely where objects are located in the room (the task’s hidden parameters). Room types are sampled from a joint distribution.

heading: A.4.2 BOX-JUMPING TASK
text: We use a simplified version of jumping task (des Combes et al., 2018) as a simple testbed for the proposed algorithm VBLRL. We select a random position of obstacle between 15 ∼ 33 for each task. The 4-element state vector describes the (x, y) coordinates of the agent’s current position, and its velocity in the x and y directions. The agent can choose from two actions: jump and right. The reward function for this box-jumping task is: Rt = I{st reach the right wall}− I{st+1 hit the obstacle}+ ẋt · I{st+1 not hit the obstacle} (11)

heading: A.4.3 OPENAI GYM MUJOCO DOMAINS
text: Similar to (Mendez et al., 2020), we evaluated on the HalfCheetah, Hopper, and Walker-2D environments. For the gravity domain, we select a random gravity value between 0.5g and 1.5g for each task. For the body-parts domain, we set the size and mass of each of the four parts of the body (head, torso, thigh, and leg) to a random value between 0.5× and 1.5× its nominal value. As shown in Appendix C of (Mendez et al., 2020), these changes lead to highly diverse tasks for lifelong RL. Further, as required by model-based deep RL methods, we change the environment settings for Hopper and Walker following (Wang et al., 2019). When implementing VBLRL, we found that in the first few
episodes of each new tasks, the agent hasn’t collected enough samples of the new task, which results in overfitting problems when training the task-specific. Thus, we use the world-model posterior instead to do the first few rounds of predictions and let the task-specific model begin training after collecting enough samples. The world-model has lower possibility of overfitting as its training data comes from all the previous tasks and has much larger quantity. We list the other implementation details below. The planning horizons are selected from values suggested by previous model-based RL papers (Chua et al., 2018; Wang et al., 2019).
For LPG-FTW and EWC, we use the original source code2 with parameters and model architectures suggested in the original paper. Specifically, we select step size from {0.005, 0.05, 0.5}. For LPGFTW, e use λ = 1e − 5, µ = 1e − 5 and select k from 3,5,10. For EWC, we select λ from {1e − 6, 1e − 7, 1e − 4}. For HiP-MDP baseline, we modify the original algorithm for a fair comparison. We replace the DDQN algorithm used in Killian et al.’s paper with the exact same CEM planning method we used in VBLRL as well as the same parameters. And we use the same model architecture of Bayesian Neural network by modifying the baseline algorithm to also predict reward for each state-action pair (the original method only considers next-state prediction).
2https://github.com/Lifelong-ML/LPG-FTW
For BOSS and BLRL, we set the number of sampled models K = 5, and γ = 0.95,∆ = 0.01 for value iteration.

heading: A.5 DETAILED PROOF FOR LEMMA 1
text: Following the same settings introduced in section 5 of (Zhang, 2006), we define the resolvability of standard Bayesian posterior as:
rn(q) = inf ω
[Eπω(θ)DKL(q||p(·|θ)) + 1
n DKL(ωdπ||dπ)]
= − 1 n
lnEπe−nDKL(q||p(·|θ)). (12)
We refer the readers to Zhang’s paper for further explanation of the denotations. Intuitively, the Bayesian resolvability controls the complexity of the density estimation process. Based on this definition and our previous definitions of dπ, we can derive a simple and intuitive estimate of the standard Bayesian resolvability. Lemma 3. The resolvability of standard Bayesian posterior defined in (12) can be bounded as
rn(q) ≤ n+ 1
n dπ
proof. For all d > 0, we have
rn(q) = − 1
n lnEπe−nDKL(q||p(·|θ)) ≤ −
1 n ln[e−ndπ(p ∈ Γ : DKL(q||p) ≤ d)]
= d+ 1
n × [− lnπ(p ∈ Γ : DKL(q||p) ≤ d)] ≤
n+ 1
n dπ
This bound links the Bayesian resolvability to the number of samples n and prior-mass radius dπ which is a fixed property of the density given a specific prior and the true underlying density. Intuitively, the Bayesian posterior is better behaved when the Bayesian prior is closer to the true distribution (dπ is smaller) and more samples are used (n is larger).
Now we can prove the main theorem of Lemma 1. Let ρ = 12 , t = 2εn+(4η−2)t
δ/4 , define Γ1 = {p ∈ Γ : DReρ (q||p) < t} and Γ2 = {p ∈: DReρ (q||p) ≥ t}. We let a = e−nt and define π′(θ) = aπ(θ)C when θ ∈ Γ1 and π′(θ)C when θ ∈ Γ2, where the normalization constant C = (aπ(Γ1) + π(Γ2)) −1 ∈ [1, 1/a]. Firstly,
EXπ′(Γ2|X) t ≤ EXEπ′π′(θ|X) 1
2 ||p− q||21 ≤ EXEπ′π′(θ|X)DKL(q||p)
according to the Markov inequality (with probability at least 1− δ) and Pinsker’s inequality. Then according to Theorem 5.2 and Proposition 5.2 in Zhang’s paper,
EXEπ′π′(θ|X)DKL(q||p) ≤ η lnEπ′e−nDKL(q||p(·|ω))
ρ(ρ− 1)n
+ η − ρ
ρ(1− ρ)n inf {Γj} ln ∑ j π′(Γj) (η−1)/(η−ρ)(1 + rub(Γj)) n
≤ ηt− (η/n) lnEπe −nDKL(q||p(·|ω))
ρ(1− ρ) + η − ρ ρ(1− ρ) [ (η − 1)t η − ρ + εupper,n (η − 1 η − ρ )] =
(2η − 1)t ρ(1− ρ) + −(η/n) lnEπe−nDKL(q||p(·|ω)) + (η − ρ)εupper,n((η − 1)/(η − ρ)) ρ(1− ρ)
Then, using the definitions of dπ , we further obtain
EXπ′(Γ2|X) t
≤ (2η − 1)t ρ(1− ρ) + η infd>0[d− 1n lnπ({p ∈ Γ : DKL(q||p) ≤ d})] + (η − ρ)εupper,n((η − 1)/(η − ρ)) ρ(1− ρ)
≤ (2η − 1)t ρ(1− ρ) + η(1 + 1n )dπ + (η − ρ)εupper,n((η − 1)/(η − ρ)) ρ(1− ρ)
= (2η − 1)t+ εn ρ(1− ρ)
We use η instead of γ which is used in the original paper to avoid confusion with the discount factor. Then we further divide both sides by t and obtain π′(Γ|X) ≤ 0.5. Then by definition,
π(Γ2|X) = aπ′(Γ2|X)/(1− (1− a)π′(Γ|X))
≤ a a+ 1 = 1 1 + ent
Thus, we get the desired bound.

heading: A.6 DETAILED PROOF FOR THEOREM 1
text: Theorem 2. (Full version of the bound in Theorem 1) For each new task, set the sample size K = Θ(S
2A δ ln SA δ ) and the parameters 0 = (1 − γ) 2, δ0 = δ SA , ρ0 = δ S2A2K , then, with
probability at least 1− 4δ, V At(st) ≥ V ∗(st)− 4 in all but O( S2A2(dπ+ln S2A2K δ ) δ 3(1−γ)6 ln 1 δ ln 1 (1−γ) ) steps.
First, we would like to introduce two lemma from BOSS (Asmuth et al., 2009):
Lemma 4. The sample size K = Θ(S 2A δ ln SA δ ) suffices to guarantee V ∗ m(s) ≥ V ∗(s) for all s during the entire learning process with probability at least 1− δ. Lemma 5. If the knownness parameter B = maxs,af(s, a, , δSA , ρ S2A2K ), then the transition function of all the sampled models are -close (in the l1 sense) to the true transition function for all the known state-action pairs during the entire learning process with probability at least 1− δ − ρ.
proof. Given discrete state and action spaces, the proof that BLRL on each new task is PAC-MDP depends on three main assumptions, following a general PAC-MDP theorem from (Strehl et al., 2006):
1. Learning complexity condition. In our settings, a state-action pair is claimed to be known after being visited for B times. In the meantime, there are SA unknown state-action pairs in total at the beginning of each task, so the bounded discoveries condition is guaranteed.
2. Optimism. This is guaranteed by Lemma 3. We construct a new hyper-model each time a discovery event occurs. The values for each unknown state in every hyper-model are optimistic.
3. Accuracy. For each new task, since the prior π has bounded sample complexity of B for δ0 and 0, a known state-action pair will be locally 0-accurate with probability at least 1− δ0. Given the definition of Bayesian concentration sample complexity and Lemma 4, 0 = (1− γ)2 translates into an error bound in the value function (Asmuth et al., 2009).
Finally, given Lemma 2, we know f(s, a, 0, δ0, ρ0) = O ( dπ+ln 1 ρ0
20δ0−dπ
) , let 0 = (1 − γ)2, δ0 =
δ SA , ρ0 = δ S2A2K , we can get f(s, a, 0, δ0, ρ0) = O
( SA(dπ+ln S2A2K δ )
δ 2(1−γ)4
) . We can get the final form
of the bound by replacing B with these quantities.

heading: A.7 ADDITIONAL EXPLANATION OF THE ALGORITHM
text: Here we first provide an example to help the readers better understand our plate notation. In our Gridworld Item Searching case, Ψ represents the parameters of PΩ, which is the room-type and object distribution. For each task, the environment samples a hidden parameter ω, which is the actual room and object layout of this house, from this distribution PΩ. The sampled ω then will result in an MDP m and let the agent interact with it.

heading: A.7.1 PLANNING ALGORITHM
text: With the transition dynamics and reward functions, a planning algorithm like CEM is not the only way to solve the MDP to get an optimal policy. Another option would be using other Deep RL algorithms like Soft actor-critic (Haarnoja et al., 2018) with data generated from the model. However, in this case, incorporating a deep RL algorithm means that we need to introduce additional neural networks (that is, policy/value networks) for each task. The update signal from the RL loss is usually stochastic and weak, which is even worse in this case when our model is still far from accurate. So, here we assume applying a planning algorithm is a better way to get the policy.

heading: A.8 COIN EXAMPLE
text: Consider a coin-flipping environment. We want to find the sample complexity of the unbiased coin (i.e. How many times we need to flip this coin such that our posterior samples are accurate.). Consider a Dirichlet prior, α0 = (n1, n2) and θ0 = (12 , 1 2 ). We want to find sample complexity B such that the posterior likelihood for a coin with heads likelihood in [0.5− , 0.5 + ] is at least 1− δ. Note that the Dirichlet distribution on the two-dimensional simplex is the Beta distribution. The Multinomial distribution with two outcomes is the Binomial distribution. That is, given the process
H ∼ Bin(H|ρ = 0.5, B), (13)
ρ̂ ∼ Beta(ρ̂|α = H + n1, β = B −H + n2), (14) choose a value B such that
P (0.5− ≤ ρ̂ ≤ 0.5 + ) ≥ 1− δ, (15)
B∑ H=0 Bin(H|ρ = 0.5, B) · ∫ 0.5+ ρ̂=0.5− Beta(ρ̂|α = H + n1, β = B −H + n2) ≥ 1− δ. (16)
Here, n1 and n2 capture the prior. The smallest B that satisfies Equation 16 can be found numerically.
We set = 0.1 and δ = 0.3. Here are the results of sample complexity B given different values of n1, n2:
We fix the sum of (n1, n2) as 10. As shown in the results, the value of sample complexity B becomes lower as we use a more accurate prior (from (10, 0) to (5, 5)).
(n1, n2) lowest B (0,10) 78 (1,9) 68 (2,8) 58 (3,7) 49 (4,6) 42 (5,5) 40 (6,4) 42 (7,3) 48 (8,2) 58 (9,1) 68 (10,0) 78
In general, for the task-specific posterior, we can relate B, and δ with the following equation:∫ P0 Dir(P0|ΦTrue) [ ∑ N:||N||1=B Mult(N |P0, B) [ ∫ P :||P (Φ)−P0(Φ)||≤ Dir(P |Φold+N)dP ]] dP0 ≥ 1−δ (17) For the world model posterior:∑
N:||N||1=Bw
Mult(N |Pw0 , Bw) [ ∫
P :||Pw(Φ)−Pw0 (Φ)||≤ Dir(Pw|Φwold + N)dPw
] ≥ 1− δ (18)
For each task, first we pick a true model P0 according to the true distribution and initialize the task-specific prior Φold = Φw. Then, we make some observations from the world. Once we have the true model and the observations, we can calculate how many models are -close to the true model, weighted according to their posterior likelihood.

Review summaries:
The paper deals with the problem of lifelong RL, also referred to as meat-RL, where an agent attempts to solve a sequence of tasks in order to facilitate the solution of a novel task. The framework follows that of Baxter 2000 (albeit that paper deals with supervised learning), and has been widely studied in recent years.  The basic assumption is that the tasks are drawn from an underlying task-distribution, and each task (an MDP) is stochastically selected from  a task-specific distribution. The authors work with a Bayesian framework, assuming a hierarchical distribution of the two levels, and learn the two levels separately. This framework has the advantage of providing both estimates and uncertainty estimates. For the discrete case they present a sample complexity analysis, and suggest a variational approach to practical learning. Finally, experiments are provided supporting the utility of the approach.   The formal framework is that of hidden-parameter MDPs (HiP-MDPs) from Doshi-Velez 2016, and each MDP is modeled based on a transition and a reward model based on a hidden parameter. As more tasks are encountered the posterior over world models sharpens, and, being used to learn new tasks, is expected to facilitate learning. The learning of each new task is as in BOSS, and takes place by sampling from the learned MDP distribution, creating a mixed MDP, and using standard model-based approaches to solve these. 

The authors proposes a Hierarchical Bayesian approach for lifelong RL. The global world-model posterior models the world model shared across tasks and the task-specific model learns the dynamics within a specific task. The task-specific model achieves forward transfer by initializing from the global world model. The authors use mean-field variational approximation to scale the proposed model. Also, the authors introduce sample complexity analysis. The method is evaluated on two toy tasks (grid-world and box jumping) and one on MuJoCo simulator and showed superior performance to the previous works. 

This submission presents an approach for Bayesian model-based exploration in a lifelong RL setting, building upon existing approaches for Bayesian exploration (BOSS) and Bayesian multi-task modeling (HiP-MDPs). The approach keeps separate models for sampling transitions and rewards for each task, and each task model is drawn from a shared prior that models the distribution over tasks. The method continually updates the shared model with data from all observed tasks and the task-specific model with data from the current task. To achieve backward transfer, the approach replaces the task model with the shared model whenever the task model has not been sufficiently trained on a particular state-action pair.