Year: 2021

Abstract:
Curriculum value-based reinforcement learning (RL) solves a complex target task by reusing action-values across a tailored sequence of related tasks of increasing difficulty. However, finding an exact way of reusing action-values in this setting is still a poorly understood problem. In this paper, we introduce the concept of boosting to curriculum value-based RL, by approximating the action-value function as a sum of residuals trained on each task. This approach, which we refer to as boosted curriculum reinforcement learning (BCRL), has the benefit of naturally increasing the representativeness of the functional space by adding a new residual each time a new task is presented. This procedure allows reusing previous action-values while promoting expressiveness of the action-value function. We theoretically study BCRL as an approximate value iteration algorithm, proving its advantages over regular curriculum RL in terms of approximation accuracy and convergence to the optimal action-value function. Finally, we provide detailed empirical evidence of the benefits of BCRL in problems requiring curricula for accurate action-value estimation and targeted exploration.

heading: 1 INTRODUCTION
text: The combination of reinforcement learning (RL) (Sutton & Barto, 2018) algorithms with powerful function approximators, i.e., deep RL (François-Lavet et al., 2018; Mnih et al., 2015), is a major breakthrough towards solving complex decision making and control problems that were impractical for previous shallow RL methods. However, the outstanding performance of deep RL techniques is obtained at the cost of a massive amount of data needed from the interaction with the environment, hindering the practicality of deep RL methods. Curriculum RL is a biologically inspired approach that frames the problem of learning a complex target task into learning a sequence of simplified, increasingly difficult, versions of it (Florensa et al., 2017; Shao et al., 2018; Ivanovic et al., 2019; Narvekar et al., 2020). Commonly, establishing the complexity of a task in RL is not trivial, as an indisputable notion of complexity is still missing. However, from a practical point of view, we can consider a task complex if it requires targeted exploration in the environment or complex policies to be solved. In curriculum RL, the notion of task complexity is key, and it is assumed that tailored tasks in a sequence of increasing complexity are presented to the learning agent. Such an appropriate design is, however, a difficult problem, requiring either human expertise (Narvekar et al., 2020) or solutions to automatize the selection of tasks following the learning of the agent (Jiang et al., 2015; Svetlik et al., 2017; Klink et al., 2020). Regardless of using a handcrafted or an automatically generated curriculum, a common approach adopted by most value-based curriculum RL methods is to use the same function approximator throughout all the tasks (Narvekar et al., 2020): given a task, an approximation of the action-value function is learned, and used as an initialization for learning the action-value function of the next task in the curriculum. For the success of this procedure, the function approximator needs to be powerful enough to handle the complexity of the target task. However, this requirement raises the key issue of adequately designing the function approximator. A complex function approximator is prone to overfitting, and sensitive to hyper-parameters, being detrimental for learning simple tasks in the curriculum; conversely, using an overly simple function approximator can hinder the learning of the target task. Moreover, choosing an adequate function approximator a-priori is not trivial, as the target task is only visited at the end, and it is commonly unsolvable by non-curriculum RL methods.
In this paper, we introduce a novel approach that models the action-value function of a task as a sum of residuals learned on the previous tasks in the curriculum. Our method increases the representativeness of the function approximator as new tasks are presented to the agent, leading to a procedure
that increases the size of the functional space as the curriculum proceeds. This results in a learning procedure that increases the power of the function approximator according to the complexity of the task at hand, using small models in simple problems to avoid overfitting, and using large models (resulting from the sum of small ones) to handle the dimensionality of complex problems. Notably, if the curriculum is sufficiently fine-grained, the residuals become smoother functions, close to zero, that are easy to learn, even if the respective tasks are harder than the previous ones. We call our method boosted curriculum reinforcement learning (BCRL), for its resemblance with the boosting technique in supervised learning (Freund, 1995). We provide a theoretical analysis of our approach under the lens of the approximate value iteration (AVI) framework (Farahmand, 2011). In AVI, an estimate of the optimal action-value function is obtained as an iterative process that starts from an arbitrary estimate and applies the optimal Bellman operator until convergence. It is shown that two sources of error exist in AVI: (i) computation of the optimal Bellman operator, (ii) representation of the action-value function (Farahmand, 2011). While the former is due to the need of using samples to approximate the unknown optimal Bellman operator, the latter depends on the representativeness of the functional space chosen to approximate the action-value function. In this work, we formalize the curriculum RL problem in the AVI setting to show that the representation of the action-value function obtained by BCRL results in a tighter bound on the approximation error compared to regular curriculum RL, consequently reducing the performance loss. We complement this analysis with an empirical evaluation of BCRL in AVI and RL settings, resorting to the fitted Q-iteration algorithm (Ernst et al., 2005), least-squares policy iteration (Lagoudakis & Parr, 2003) and deep Q-networks (Mnih et al., 2015), confirming the advantages of BCRL over regular curriculum RL.

heading: 2 RELATED WORK
text: Learning under a dynamic set of training experience has been investigated in different fields throughout decades (Saul, 1941; Elman, 1993; Asada et al., 1996; Krueger & Dayan, 2009). A recent paper by Bengio et al. (2009) has established the term curriculum learning for the concept of organizing training data of a neural network in a beneficial way for performance and generalization. This term carried over to the domain of RL, where curricula over training tasks have been shown to stabilize the highly challenging optimization problem of RL (Narvekar et al., 2020). While a large body of research in the domain of curriculum reinforcement learning investigates the interesting problem of optimally selecting and scheduling the training tasks for an RL agent to optimize performance on a set of target tasks (Florensa et al., 2017; Ivanovic et al., 2019; Shao et al., 2018; Klink et al., 2020), the architecture of the learning agent is often assumed fixed and the transfer of agent behavior between subsequent tasks in the curriculum is realized by this shared fixed architecture. However, aside from investigations into the benefit of an adequately chosen evolution of training experience, investigations of an optimal learning architecture (Elsken et al., 2019) and the evolution of this architecture during learning (Aoki & Siekevitz, 1988; Rumelhart et al., 1988; Ash, 1989; Fahlman, 1990; Lahnajärvi et al., 2002; Nitanda & Suzuki, 2018) have been conducted in supervised learning scenarios. The adaptation of these methods to the setting of RL has been limited to on-policy temporal-difference learning (Rivest & Precup, 2003; Vamplew & Ollington, 2005b;a) and it has not been further pursued in recent years. Our work aims to improve the information transfer between subsequent tasks in curriculum value-based reinforcement learning via a boosting procedure (Freund, 1995). The benefit of the boosting framework is that it is well understood from a theoretical perspective (Tosatto et al., 2017), allowing for the derivation of error bounds, as also presented in this paper. Further, it is agnostic to any value-based RL algorithm, avoiding the need to adjust the RL algorithm of choice to be suited for the evolution of the function approximator (Rivest & Precup, 2003; Vamplew & Ollington, 2005a;b). Aside from improving knowledge transfer via the learning architecture of the agent, the field of transfer learning investigates various approaches for transferring knowledge, which we shortly review in Appendix A.

heading: 3 PRELIMINARIES

heading: 3.1 DEFINITIONS AND NOTATION
text: We recall the notions about Markov Decision Processes (MDPs) (Puterman, 1990), and the notation used for approximate value iteration (AVI) (Farahmand, 2011), that are relevant to our work.
For a space Σ, we defineM(Σ) the set of probability measures over the σ-algebra σΣ. We denote B(Σ, B) as the space of bounded measurable functions w.r.t. σΣ with bound 0<B<∞. A finiteaction discounted MDP is defined as a tuple T = 〈S,A,P,R, γ〉, where S is a measurable state space, A is a finite set of actions, P : S × A →M(S) is a transition kernel, R : S × A × S → R is a reward function, and γ ∈ [0, 1) is a discount factor. A policy π is a mapping from the state space S to a probability distribution over the action spaceA. A policy induces an action-value function Qπ(s, a) , E [Σ∞t=0γtRt|S0=s,A0=a], corresponding to the expected cumulative discounted reward obtained performing action a in state s and following the policy π thereafter. RL aims at solving an MDP by finding an optimal policy π∗ which induces an optimal action-value function Q∗(s, a) = supπ Q
π(s, a). For immediate rewards uniformly bounded by Rmax, the action-value function is bounded by Qmax = Rmax/1−γ. For a probability measure µ ∈ M(S × A), we define the Lp(µ)-norm of a measurable function Q ∈ B(S × A) as ‖Q‖p,µ , [ ∫ S×A |Q(s, a)|
pdµ(s, a)]1/p. Given a sequence of values x1:n=(x1, . . . , xn) for some space X , the empirical Lp-norm of a function f : X → R is ‖f‖p,x1:n , 1n ∑n i=1 |f(xi)|p. Conveniently, when Xi ∼ µ, we have E [‖f‖p,x1:n ] = ‖f‖p,µ. From now on, we consider the L2-norm when the subscript p is omitted. Operators. We define the operator Pπ as (PπQ)(s, a) , ∫ S P(ds ′|s, a) ∑ a′∈A π(a
′|s′)Q(s′, a′), for any given policy π. Then, the Bellman operator Tπ : B(S ×A)→ B(S ×A) is (TπQ)(s, a) , r(s, a) + γ(PπQ)(s, a). The optimal Bellman operator T ∗ : B(S × A) → B(S × A) is (T ∗Q)(s, a) , r(s, a) + γ ∫ S maxa′ P(ds
′|s, a)Q(s′, a′)). Finally, the fixed point of the Bellman operator is (TπQπ) = Qπ , and the fixed point of the optimal Bellman operator is (T ∗Q∗) = Q∗. As in Györfi et al. (2006), we define the truncation operator βB : B(S × A) → B(S × A, B) such that, given a function f ∈ B(S ×A), we have βBf(s, a) ∈ [−B,B],∀(s, a) ∈ S ×A.

heading: 3.2 APPROXIMATE VALUE ITERATION
text: The family of approximate value iteration (AVI) algorithms (Sutton & Barto, 2018; Farahmand, 2011; Munos, 2005) aims at approximating the solution of RL problems with large state space where finding an optimal solution is impractical or impossible. Starting from an arbitrary estimate Q0, AVI algorithms iteratively approximate the application of the optimal Bellman operator in a suitable functional space, i.e., Qk+1 ≈ T ∗Qk. Intuitively, the approximation error at each iteration plays a central role in terms of convergence to the fixed point Q∗. The approximation error results from two key aspects: (i) the unknown optimal Bellman operator, and (ii) the representation of the action-value function in a suitable functional space F via the application of a nonlinear operator S : B(S × A)→ F defined as Sy = arg inff∈F‖f − y‖2µ for any y ∈ B(S × A). Then, we define Qk+1 = S(T ∗Qk), and the resulting approximation error by
εk , T ∗Qk −Qk+1. (1)
The role of the approximation error in AVI is evinced by the following theorem that bounds the performance loss, w.r.t. the optimal performance, at iteration K1.
Theorem 1. (Theorem 3.4 of Farahmand (2011)). Let K be a positive integer, ρ an initial state distribution, and Qmax ≤ Rmax1−γ . Then, for any sequence (Qk) K k=0 ⊂ B(S × A, Qmax), and the corresponding sequence (εk)K−1k=0 , we have
‖Q∗ −QK‖1,ρ ≤ G(γ) [Aρ,µ(K)E(ε0, . . . , εK−1) +B(γ,K)Rmax]
where E(ε0, . . . , εK−1) = ∑K−1 k=0 C(k)‖εk‖22,µ.
We point out that the upper bound in Theorem 1 is a high-level version of the one reported in Farahmand (2011), where we omitted some technicalities that go beyond the scope of this paper replacing them with functions G, A, B, and C. This simplified version highlights that the magnitude of the difference between the optimal action-value function Q∗ and the estimate at the K-th iteration QK , is proportional to the magnitude of the approximation errors εk as defined in Equation 1. We refer the reader to the appendix for an extended version of the equation, and to Farahmand (2011) for further details about it.
1In Farahmand (2011), the action-value function at iteration k is denoted byQπk to highlight its dependency on the policy πk. In this paper, we simply write Qk omitting π for simplicity.

heading: 4 CURRICULUM REINFORCEMENT LEARNING WITH BELLMAN RESIDUALS
text: We consider the classic curriculum RL scenario where an agent aims at learning a complex target task by solving a predefined sequence of easier, but increasingly challenging, versions of it (Narvekar et al., 2020). To avoid confusion on the debatable notion of difficulty of a task, in this work we adopt a practical point of view where the difficulty of a task is related to well-known aspects of RL, e.g., the complexity of the policies for solving them and challenging exploration (Florensa et al., 2017; Ivanovic et al., 2019; Klink et al., 2020).

heading: 4.1 APPROXIMATE VALUE ITERATION IN CURRICULUM REINFORCEMENT LEARNING
text: Let T1:n = {T1, . . . , Tn} be a sequence of increasingly complex MDPs sharing the same state and action spaces, i.e., Ti = 〈S,A,Pi,Ri, γ〉, and Tn be the target task. The use of AVI algorithms in this curriculum RL setting consists in starting from an arbitrary estimate Q01 (where the subscript indicates the position of the task in the curriculum) and approximating the application of the taskspecific optimal Bellman operator for the current task Qk+1t ≈ T ∗t Qkt . We assume that the task changes when the estimate of the action-value of the current task converges. For simplicity, and without loss of generality, we denote Kt the number of iterations needed to converge for each task Tt, and denote Q0t = Q Kt−1 t−1 = Q ∗ t−1. Lemma 1. Let K be the current iteration. Then,
‖Q∗n−QKt ‖1,ρ ≤ ‖Q∗n−Q0n‖1,ρ+· · ·+‖Q∗t−QKt ‖1,ρ = n∑
i=t+1
‖Q∗i−Q0i ‖1,ρ+‖Q∗t−QKt ‖1,ρ. (2)
This result can be verified applying the triangle inequality under the assumption that the algorithm switches task when the stopping condition of the algorithm is verified, e.g., when reaching a chosen number of iterationsKt that allows the action-value function estimate to converge, or using heuristic methods checking the magnitude of the update (Lagoudakis & Parr, 2003; Ernst et al., 2005). Note that each component of the sum in (2) can be bounded by the result in Theorem 1. We denote the k-step Bellman residual for task t by
%kt , (T ∗ t ) kQ∗t−1 −Q∗t−1 = (T ∗t )kQ0t −Q0t . (3)
Proposition 1. Given an initial Q01(s, a)=0 for any (s, a) ∈ S × A, and considering that Q∗t = Q Kt t ≈ (T ∗t )KtQ∗t−1, we obtain
%kn+ n−1∑ t=1 %Ktt = (T ∗ n) kQ0n−Q0n+ ( n−1∑ t=1 (T ∗t ) KtQ0t −Q0t ) = (T ∗t ) k . . . (T ∗1 ) K1Q01−Q01 ≈ Qkn. (4)
This result shows that, approximately, the action-value function of the target task is equivalent to the sum of k-step Bellman residuals. Notably, especially if the curriculum is sufficiently fine-grained, residuals becomes progressively smoother and smaller. In the following, we describe how to compute the estimate shown in (4).

heading: 4.2 BOOSTED CURRICULUM REINFORCEMENT LEARNING
text: It is well-known from supervised learning that: (i) small function approximators are easier to train, and thus are desirable to solve simple tasks; (ii) large function approximators can overfit or suffer slow training speed in simple tasks, but they are more suitable to handle complex problems. Ideally, we want to increase the representativeness of the function approximator with the increase of task complexity. Recalling (4), we propose to use a separate function approximator for each residual %t, i.e. a separate approximator for each task. Given a dataset Dt = {(sit, ait, rit, s′it )}Ni=1 for each task, we denote the empirical Bellman operator by (T̂ ∗t Q)(s i t, a i t) , r i t + γmaxa′ Q(s ′i t , a ′), and define the k-step empirical residual as %̃kt , (T̂ ∗ t ) kQ0t−Q0t . At iteration k, for a current task t, and defining the nonlinear operator Ŝ%̃kt = arg inff∈F‖f − %̃kt ‖2Dt as the empirical version of the operator S, we compute an approximation
Qkt = Q 0 t + βBk Ŝ%̃ k t = t−1∑ i=1 %̂Kii + %̂ k t , (5)
Algorithm 1: Boosted Curriculum Reinforcement Learning (BCRL) Input: Tasks T1:n, t = 1, Q01 = 0; while t < n+ 1 do
Collect dataset Dt using policy induced by Q0t (e.g., ε-greedy); for k = 0, . . . ,Kt do
%̃kt ← T̂ ∗t Qkt −Q0t ; Qk+1t ← Q0t + βBk arg inff∈F‖f − %̃kt ‖Dt ;
end Q0t+1 ← Q Kt t ; t← t+ 1;
end Output: QKnn = ∑n t=1 %̂ Kt t .
where we defined %̂kt = βBk Ŝ%̃ k t for compactness. For ease of notation, we use Q k t also to denote the Q-function obtained by applying the empirical Bellman operator. We call this approach boosted curriculum reinforcement learning (BCRL), for its resemblance with the boosting procedure in supervised learning (Schapire, 1990; Freund, 1995), and we show its pseudocode in Algorithm 1.
Remarks. Our approach is based on the key insight that the strength of the function approximator should increase according to the complexity of the task at hand. In BCRL, we accomplish this estimating an action-value function through a sum of action-value functions of the previous tasks in the curriculum. Thus, contrary to methods using the same functional space for all tasks, our approach has the advantage of acting in an augmented functional space resulting from the sum of the functional space of each approximator. In supervised learning literature, the function approximators in the sum are commonly known as weak regressors, meaning that boosting has the advantage of estimating complex functions as a sum of simple regressors (Geurts et al., 2006). Similarly, our BCRL procedure can use simple function approximators for each task in the curriculum, with the advantages that (i) easy tasks can be learned with easy function approximators curbing the risk of overfitting, (ii) the complexity of the function approximator can be chosen according to the first tasks in the curriculum, contrarily to regular curriculum RL where the function approximator needs to be suitable for the target task, and (iii) the training time to fit the model on each task is reduced due to the smoothness of the residuals. Conversely, at inference time, our method requires a forward pass for each approximator in the ensemble. Nevertheless, the small size of the regressors results in negligible increase of computation time. Finally, we clarify that the soundness of this procedure is guaranteed by the fact that if the functional space of each weak regressor is Glivenko-Cantelli, i.e., ”the error due to the empirical process goes to zero at least asymptotically”, then, due to the preservation theorem, also the space resulting from the sum of weak regressors is Glivenko-Cantelli (Van Der Vaart & Wellner, 2000; Tosatto et al., 2017).

heading: 5 THEORETICAL ANALYSIS
text: We provide a theoretical analysis of BCRL in terms of convergence guarantees and finite-sample approximation error analysis. We assume the tasks in the curriculum have the same transition kernels, and different reward functions. Nevertheless, our results can be straightforwardly extended to the general case. We refer to the well-known results in AVI (Farahmand, 2011; Farahmand et al., 2010), and the analysis provided in Tosatto et al. (2017), with which our analysis share some similarities.

heading: 5.1 CONVERGENCE GUARANTEES
text: Theorem 2. Let Q∗t−1 be the learned action-value for task Tt−1, and (Qit)ki=0 be a sequence of measurable action-value functions for a target task Tt obtained following our BCRL procedure (5), where Q0t = Q ∗ t−1. Denote L = γCµ→∞ the Lipschitz coefficient of the optimal Bellman operator, where Cµ→∞ is the one-step concentrability coefficient w.r.t. µ (Farahmand, 2011), and assume the operator S is such that ∃λ > 0 : ‖(I − S)y‖µ ≤ λ‖y‖µ for all y ∈ B(S ×A). Then,
‖Qkt −Q∗t ‖µ ≤ ((1 + Lk)λ+ Lk)‖Q0t −Q∗t ‖µ. (6)
The assumption on the operator S stated by Theorem 2 dictates that the approximation power of the used functional space should be good enough to learn the target function y; specifically, the upper bound of the approximation error is proportional to the magnitude of the function to approximate. This assumption holds for reasonable choices of function approximators and it is present in related works on the derivation of finite-time bounds for policy iteration (Munos, 2003), and value iteration (Munos, 2005; Tosatto et al., 2017). We observe that the boosting procedure adds the (1+Lk)λ term in the regular AVI bound, that is obtained for λ = 0. This result shows that for each task, for appropriate values of λ and L, the boosting procedure converges to the optimal action-value. Corollary 1. Given the settings of Theorem 2, the sequence of (Qit)ki=0 converges to Q∗t when
λ < 1− Lk
1 + Lk and Lk < 1. (7)

heading: 5.2 FINITE-SAMPLE APPROXIMATION ERROR ANALYSIS
text: In Lemma 1, we show how to derive the AVI performance loss analysis (Farahmand, 2011) for curriculum RL. Now, we want to characterize it for our BCRL method. Instead of using the regular AVI approximation error defined in (1), we consider the approximation error for each task t in the curriculum defined as
εkt = (T ∗ t ) kQ0t −Qkt , ε0t = (T ∗t−1)Kt−1Q0t−1 −Q0t . (8)
Theorem 3. Let (Qit)ki=0 be a sequence of action-value function for each task t, (εit)ki=0 be the respective sequence of approximation errors as defined in (8), F ⊆ B(S × A) be a subset of measurable action-value functions. Denoting the regular AVI residual as %̄kt = (T ∗ t ) k . . . (T ∗1 )
K1Q01 − (T ∗t−1) Kt−1 . . . (T ∗1 ) K1Q01, we have
inf f∈F ‖f − %kt ‖µ ≤ inf f∈F ‖f − %̄kt ‖µ + (1 + Lk) ( t−1∑ i=1 LKi‖ε0i ‖µ + ‖ε0t‖µ ) . (9)
This bound shows the relation between the approximation error of the residual for task t at step k, the AVI Bellman Residual %̄kt , and the approximation error for the residuals of the previous tasks. Lemma 2. Let (Qit)ki=0 be a sequence of action-value function for each task t, (εit)ki=0 be the respective sequence of approximation errors as defined in (8). Then,
‖%̃kt ‖∞ ≤ k−1∑ i=1 γk−i‖εit‖∞ + (1 + γk)Rmaxt . (10)
We use (9) and (10) to finally bound the approximation error of the residual as follows. Theorem 4. Let Btk = max(‖%̃kt ‖∞, 1), and VF+ be the VC-dimension of F+, i.e., the class of all subgraphs of functions f ∈ F (Györfi et al., 2006). For given dataset Dt = {(sit, ait, rit, s′it )}Ni=1 for each task t, and a given sequence of action-value functions (Qit) k i=0 generated by BCRL, we have
‖εkt ‖2µ ≤ (i) approximation error︷ ︸︸ ︷ 2 inf f∈F ‖f − %̄kt ‖2µ + (ii) propagation error︷ ︸︸ ︷ 2(1 + Lk)2 ( t−1∑ i=1 LKi‖ε0i ‖µ + ‖ε0t‖µ )2
+ 5136Bkt
4
N
( log 42e+ 2 log(480eBkt 2 N)VF+ ) ︸ ︷︷ ︸
(iii) estimation error
. (11)
This result bounds the error of BCRL by a sum of three components: (i) the approximation error of the residual %̄kt , (ii) the propagation error due to approximation errors at previous iterations, (iii) the estimation error due to the regression problem with finite amount of samples. The advantages of BCRL are motivated by the use of residuals %̄kt and %̃ k t , whose range of values become smaller as the curriculum proceeds, resulting in tighter approximation and estimation error bounds compared to regular curriculum RL. Moreover, BCRL enjoys advantages in terms of sample-efficiency, as fewer samples than regular curriculum RL can be used to achieve comparable estimation errors, due to the smaller range and smoother shape of the target ‖%̃kt ‖µ compared to Qmaxt .

heading: 6 EXPERIMENTS
text: This section serves to provide empirical evidence to the insights obtained in the previous section. More precisely, we want to provide evidence that boosted curricula can indeed improve the residual in an AVI setting and with that improve the achieved agent performance. Further, we show that the additional flexibility of boosting w.r.t. the individual function approximators can be leveraged to choose the best-suited learning approach for each learning task. We conduct experiments in multiple environments and with two different RL algorithms using the MushroomRL library (D’Eramo et al., 2021).2 To evaluate the benefit of curricula in boosted AVI settings, we turn towards the fitted Q-iteration (FQI) algorithm in the car-on-hill environment (Ernst et al., 2005), as the low-dimensionality allows for uniform sampling of the state-action space assumed in the previous section and the ground truth optimal Q-function can be computed via bruteforce methods (Ernst et al., 2005). Next, we evaluate the FQI algorithm in a maze environment in which exploration is guided by the currently estimated optimal policy. Finally, we investigate boosting in a control task with DQN (Mnih et al., 2015), in which a point-mass needs to be steered over a narrow pathway subject to external perturbations. To disentangle the interplay between boosting and the use of a curriculum, we will compare different methods in the experiments: the algorithm under investigation (FQI, DQN), a version using both a curriculum with boosting (BC-FQI, BC-DQN) as well as two ablations of the second method - one without boosting (C-FQI, C-DQN) and one without a curriculum (B-FQI). The boosted methods that do not use a curriculum will introduce the additional approximators at the same iteration at which the curricula switches between tasks.

heading: 6.1 CAR-ON-HILL
text: The three car-on-hill tasks T1, T2 and T3 considered for curriculum learning in this experiment differ in the mass of the car, taking values of 0.8, 1.0 and 1.2 respectively. The default mass of the environment is 1.0 which means we are considering a version of this environment with more challenging exploration, as the car needs more energy to escape the valley and receive a reward signal. The dataset for learning the Q-function in each task is generated by executing 1000 trajectories with a random policy. To not make the results in this section dependent on the parametric form of the function approximator, we resort to the tree-based regression investigated in Ernst et al. (2005). The results are visualized in Figure 1. We can see that the combination of boosting and a curriculum (BC-FQI) outperforms all other methods both in terms of final approximation error achieved on T3 but also in terms of the performance of the greedy policy derived from the estimated Q-function. Comparing the residual of BC-FQI and C-FQI, we can see that C-FQI seems to be challenged with adapting the Q-function from T1 to T2, as the jump in residual shows. BC-FQI does not exhibit such a jump in residual when moving from T1 to T2. Furthermore, BC-FQI reduces the increased residual after switching from T2 to T3 while the residual of C-FQI steadily increases once arriving at the target task. We can particularly see that the pre-training in T1 and T2 leads to a significantly smaller Q-function error of BC-FQI compared B-FQI at iteration 40, which is in line with the discussion in the previous sections.
2Code for reproducing the results is contained in the supplementary material and will be made available upon acceptance. Additional experimental details can be found in the appendix.

heading: 6.2 MAZE
text: We design a maze environment, in which an agent needs to reach a target position by navigating around two large obstacles. To reach the goal, the agent can choose between 4 discrete actions that move the agent up, down, left, or right. It obtains a dense reward based on the distance to the target and a reward of +5 upon reaching the goal. We design a curriculum composed of 10 tasks, in which the size of the walls gradually increases (see Figure 3a for a visualization of tasks contained in the curriculum). The reward function and the target task are designed to induce highly challenging exploration, requiring the use of curricula to solve the problem. As done for the caron-hill experiment, we use FQI with tree-based regression (Ernst et al., 2005). For all methods, we collect a dataset for each task running 500 episodes using ε-greedy exploration, decreasing the strength of exploration as the curriculum proceeds. As can be seen in Figures 2 and 3, regular learning on the target task does not allow find a good solution, regardless of whether boosting is used or not (B-FQI and FQI). This is due to the highly challenging exploration problem that needs to be solved in this environment. The initial random exploration is insufficient to maneuver around the second wall in the target task. Consequently, the agent is not aware of the benefit of this detour, as obvious in the learned Q-function (Figure 3b). Subsequently reducing the exploration does not lead to any new evidence and hence the agent quickly converges to the sub-optimal solution (Figure 2). Looking at the results of C-FQI, we see that the curriculum alleviates the aforementioned exploration problem. However, the estimatedQ-function deteriorates before approaching the target task, leading to unreliable policies. By introducing additional capacity as learning proceeds, BC-FQI allows to learn an optimal policy. Indeed, we show in the appendix that the residuals of BC-FQI decrease in later iterations, easing the function approximation problem when progressing to the target task.

heading: 6.3 LINEAR SYSTEM CONTROL
text: The last task aims at highlighting a more subtle benefit of BCRL: Choosing the architecture of the function approximators appropriately for each task in the curriculum. We show that this flexibility can improve sample efficiency in a control task, in which a point mass needs to be steered towards
a goal position over a narrow pathway along which it is subject to a drift moving it away from the target position (Figure 4b). The agent receives a reward of −1 until reaching the goal, which issues a reward of 0 and ends the episode. If the agent falls off the pathway, it is reset to the initial position. We learn a policy for solving this target task using DQN and introduce a curriculum that first trains in an easier system to induce a bias of moving towards the target. In this easier system, the point mass does not face external perturbations, obtains a reward equal to the negative squared distance to the target position and does not need to stay on a particular pathway. Since the easier environment is a linear quadratic (LQ) problem (see appendix C.3), the Q-function is known to be a quadratic function of state and action (Bradtke, 1993). The boosting framework allows to exploit this knowledge by using quadratic features in the first learning task and only rely on a neural network to realize theQ-function in the target task. With quadratic features, theQ-function can be efficiently learned from experience with least-squares policy iteration (LSPI) (Lagoudakis & Parr, 2003). In the boosted curriculum evaluated in this task (BC-DQN), we hence first learn a Q-function using LSPI in the LQ task and then adjust this Q-function in the target task with a residual using DQN. Figure 4a shows that this incorporation of additional structure into the curriculum leads to improved performance over both directly learning on the target task (DQN) and not adjusting the structure of the agent to the learning task in the curriculum (C-DQN). It is particularly surprising that C-DQN is performing even worse than DQN. There are multiple potential causes for this poor performance. One is that the DQN algorithm takes significantly longer to learn in the LQ problem compared to LSPI (10.000 vs. 2.000 steps), diminishing the benefit of bootstrapping the policy in the easier learning task. We further see no accelerated learning of C-DQN on the target task compared to DQN. This may be caused by the less accurate Q-function learned in the LQ problem with DQN compared to LSPI (Figure 4b), which does not perform as targeted movements to the goal. We also evaluate residual policy learning (RPL, Silver et al. (2018)) and probabilistic policy reuse (PPR, Fernández et al. (2010)) leveraging the policy learned in the LQ problem with LSPI (details in C.3). We see that RPL increases learning speed compared to C-DQN, but both RPL and PPR do not improve upon DQN.

heading: 7 CONCLUSION
text: We introduced boosted curriculum reinforcement learning (BCRL), a new method for action-value function estimation in curriculum RL. For each task, BCRL approximates the respective action-value function as a sum of residuals of the previous tasks in the curriculum, increasing the representativeness of the functional space alongside the complexity of the tasks. We proved that BCRL enjoys advantageous theoretical properties in terms of convergence to the optimal action-value function of the target task. Moreover, we empirically validated BCRL across different problems and algorithms, showing its advantages over regular curriculum RL. Our work is a step towards understanding the complex interplay between curricula and the structure of the learning agent. We assume that the curricula are so-called sequence curricula, while recent progress in automated curriculum generation defines curricula as a distribution over tasks (Narvekar et al., 2020). Adapting our theoretical framework to these recent advances would allow to couple them with BCRL. Further, the complexity of the network, and hence the required computation, increases with each task. Finding ways to decay the influence of older Q-functions may allow for pruning, avoiding linear growth of the network.

heading: 8 REPRODUCIBILITY STATEMENT
text: We aim to guarantee the reproducibility of our work by providing the proofs of the main paper theorems as well as additional details of the conducted experiments in the appendix. Further, we provide the code for running the experiments alongside the submission and will make this code publicly available upon acceptance.

heading: A DISCUSSION OF RELATED TRANSFER LEARNING METHODS
text: Given our focus on knowledge transfer via Q-functions in curriculum RL, our investigations are closely related to the field of transfer learning and we hence want to situate our method in this field by this short review. Transfer learning is a well-established concept in RL and multiple surveys have been conducted in the single- and multi-agent RL setting (Taylor & Stone, 2009; Lazaric, 2012; Da Silva et al., 2018; Da Silva & Costa, 2019). Apart from detecting a change in the current task (Hernandez-Leal et al., 2017), determining from which task to transfer knowledge (Fernández & Veloso, 2006; Barrett & Stone, 2015; Hernandez-Leal & Kaisers, 2017) to the current task is an important problem in transfer learning. For an adequately chosen curriculum, the aforementioned problems are less severe as a) the agent is assumed to be aware of the task change and b) the knowledge from the most recent task in the curriculum can be assumed to be the most relevant for solving the current one. The transfer of knowledge between tasks can then happen in various forms, e.g., via samples (Lazaric et al., 2008; Lazaric & Restelli, 2011), policies (Fernández & Veloso, 2006; Fernández et al., 2010; Silver et al., 2018), reward functions (Brys et al., 2015) or demonstrations/teachers (Chernova & Veloso, 2009; Billard et al., 2016; Koert et al., 2020). When sharing value- or Q-functions, which resembles the boosting scenario investigated in this paper, incorporating abstract concepts like objects, classes or relations (Koga et al., 2013; 2014; Da Silva & Costa, 2017; Silva & Costa, 2018) can drastically improve the generalization of learned Q- or value-functions between tasks at the expense of additional user-specified information. When not assuming any additional information of the aforementioned forms in a value- or Q-function transfer setting, methods that extend upon the naive idea of initializing the Q-function of the next task with the one learned in the previous one, as e.g. done in Narvekar et al. (2016), are rather sparse. Rusu et al. (2016) present a particular neural network architecture – progressive neural networks – that aims to improve transfer between tasks by adding so called columns for each encountered task. Those additional columns are connected to the columns of the previous task by learnable weight matrices. Reward shaping (Ng et al., 1999) allows to reuse a value function from a source task as a shaping function in a target task. Both progressive neural networks and reward shaping are orthogonal to our investigation of boosting and its influence on the residual of Q-function approximators in curriculum RL. As we show in Figure 5, boosting hence can still provide benefits when combined with such approaches. Boutsioukis et al. (2011) investigate the idea of sparsely initializing the Qfunction in the new task with a bias value for the optimal actions of the previous task in discrete state-action spaces. We compare to residual policy learning (RPL, Silver et al. (2018)) in Section 6.3, as it follows a similar idea of learning a residual, however in the form of a policy, and furthermore avoids the complication of the overall curriculum by e.g. introducing a secondary RL objective (Brys et al., 2015) to realize the knowledge transfer between tasks or the need to choose appropriate bias values for Q-function initialization (Boutsioukis et al., 2011). For the environment in Section 6.3, the idea of a residual policy is well-suited since the 8 discrete actions in the target task (see appendix C.3) allows to define reasonable ways to combine the actions of the previous and the current policy. For the tasks in Section 6.1 and 6.2, combining actions is problematic due to the action spaces of the tasks. For the car-on-hill task, combining the two opposing actions of moving left or right will either
always ignore the actions of the previous policy or ignore the actions of the current policy. The same problem occurs for the maze task with its four actions left, right, up and down. Further, we evaluate probabilistic policy reuse (PPR, Fernández et al. (2010)) on the linear control task as it – like RPL– introduces no crucial additional design choices in a value function based curriculum.

heading: B ADDITIONAL THEOREMS AND PROOFS
text: We report an extended version of our Theorem 1 based on Theorem 3.4 in Farahmand (2011).
Theorem 1. (Theorem 3.4 of Farahmand (2011)). Let K be a positive integer, ρ an initial state distribution, and Qmax ≤ Rmax1−γ . Then, for any sequence (Qk) K k=0 ⊂ B(S × A, Qmax), and the corresponding sequence (εk)K−1k=0 , we have
‖Q∗ −QK‖1,ρ ≤ 2γ
(1− γ)2
[ inf
r∈[0,1] C
1 2
VI,ρ,µ(K; r)E 1 2 (ε0, . . . , εK−1; r) +
2
1− γ γKRmax ] where E(ε0, . . . , εK−1; r) = ∑K−1 k=0 α 2r k ‖εk‖2µ, and CVI,ρ,µ and αk as defined, respectively, in Definition 3.1 and Equation 3.3 in Farahmand (2011).
We proceed reporting the proofs of the theorems and lemmas described in the main paper.
Theorem 2. Let Q∗t−1 be the learned action-value for task Tt−1, and (Qit)ki=0 be a sequence of measurable action-value functions for a target task Tt obtained following our BCRL procedure (5), where Q0t = Q ∗ t−1. Denote L = γCµ→∞ the Lipschitz coefficient of the optimal Bellman operator, where Cµ→∞ is the one-step concentrability coefficient w.r.t. µ (Farahmand, 2011), and assume the operator S is such that ∃λ > 0 : ‖(I − S)y‖µ ≤ λ‖y‖µ for all y ∈ B(S ×A). Then,
‖Qkt −Q∗t ‖µ ≤ ((1 + Lk)λ+ Lk)‖Q0t −Q∗t ‖µ. (12)
Proof. ∥∥∥Qkt −Q∗t∥∥∥ µ ≤ ∥∥∥Qkt − (T ∗t )kQ0t∥∥∥ µ + ∥∥∥(T ∗t )kQ0t −Q∗t∥∥∥ µ
= ∥∥∥QKt−1t−1 + S%kt − (T ∗t )kQ0t∥∥∥ µ + ∥∥∥(T ∗t )kQ0t −Q∗t∥∥∥ µ
≤ λ ∥∥∥%kt ∥∥∥
µ + Lk ∥∥∥Q0t −Q∗t∥∥∥ µ
(13)
≤ ( λ(1 + Lk) + Lk ) ∥∥∥Q0t −Q∗t∥∥∥ µ . (14)
where (13) considers the assumption on the operator (I − S) and (14) follows noting that∥∥∥%kt ∥∥∥ µ ≤ ∥∥∥(T ∗t )kQ0t − T ∗t Q∗t∥∥∥ µ + ∥∥∥T ∗t Q∗t −Q0t∥∥∥ µ
≤ (1 + Lk) ∥∥∥Q0t −Q∗t∥∥∥
µ .
Theorem 3. Let (Qit)ki=0 be a sequence of action-value function for each task t, (εit)ki=0 be the respective sequence of approximation errors as defined in (8), F ⊆ B(S × A) be a subset of measurable action-value functions. Denoting the regular AVI residual as %̄kt = (T ∗ t ) k . . . (T ∗1 )
K1Q01 − (T ∗t−1) Kt−1 . . . (T ∗1 ) K1Q01, we have
inf f∈F ‖f − %kt ‖µ ≤ inf f∈F ‖f − %̄kt ‖µ + (1 + Lk) ( t−1∑ i=1 LKi‖ε0i ‖µ + ‖ε0t‖µ ) . (15)
Proof. For an arbitrary function f ∈ F and task t, we have ‖f − %kt ‖µ ≤ ‖f − %̄kt ‖µ + ‖%̄kt − %kt ‖µ. Then,∥∥∥%̄kt − %kt ∥∥∥ µ ≤ ∥∥∥(T ∗t )k . . . (T ∗1 )K1Q01 − (T ∗t )kQ0t∥∥∥ µ + ∥∥∥(T ∗t−1)Kt−1 . . . (T ∗1 )K1Q01 −Q0t∥∥∥ µ
≤ Lk ∥∥∥(T ∗t−1)Kt−1 . . . (T ∗1 )K1Q01 −Q0t∥∥∥ µ + ∥∥∥(T ∗t−1)Kt−1 . . . (T ∗1 )K1Q01 −Q0t∥∥∥ µ
= (1 + Lk) ∥∥∥(T ∗t−1)kt−1 . . . (T ∗1 )K1Q01 −Q0t∥∥∥
µ = (1 + Lk) ∥∥∥(T ∗t−1)Kt−1 . . . (T ∗1 )K1Q01 − ((T ∗t−1)Kt−1Q0t−1 − ε0t ) ∥∥∥
µ ≤ (1 + Lk) (∥∥∥(T ∗t−1)Kt−1 . . . (T ∗1 )K1Q01 − (T ∗t−1)Kt−1Q0t−1∥∥∥ µ + ∥∥∥ε0t∥∥∥ µ ) ≤ (1 + Lk) ( LKt−1 ∥∥∥(T ∗t−2)Kt−2 . . . (T ∗1 )K1Q01 −Q0t−1∥∥∥ µ + ∥∥∥ε0t∥∥∥ µ
) ≤ (1 + Lk) ( LKt−1 (∥∥∥(T ∗t−2)Kt−2 . . . (T ∗1 )K1Q01 − (T ∗t−2)Kt−2Q0t−2∥∥∥ µ + ∥∥∥ε0t−1∥∥∥ µ ) + ∥∥∥ε0t∥∥∥ µ
) ≤ · · · ≤ (1 + Lk)
( t−1∑ i=1 LKi ∥∥∥ε0i∥∥∥ µ + ∥∥∥ε0t∥∥∥ µ ) .
Theorem 4. Let Btk = max(‖%̃kt ‖∞, 1), and VF+ be the VC-dimension of F+, which is the class of all subgraphs of functions f ∈ F (Györfi et al., 2006). Given a dataset Dt = {(sit, ait, rit, s′it )}Ni=1 for each task t, and a sequence of action-value functions (Qit) k i=0 generated by our BCRL, we have
‖εkt ‖2µ ≤ 2 inf f∈F ‖f − %̄kt ‖2µ + 2(1 + Lk)2 ( t−1∑ i=1 LKi‖ε0i ‖µ + ‖ε0t‖µ )2
+ 5136Bkt
4
N
( log 42e+ 2 log(480eBkt 2 N)VF+ ) . (16)
Proof. Using Theorem 11.5 from Györfi et al. (2006), we obtain
‖εkt ‖2µ ≤ 2 inf f∈F ‖f − %kt ‖2µ +
5136Bkt 4
N
( log 42e+ 2 log(480eBkt 2 N)VF+ ) .
We complete the proof using (15) and the Cauchy-Schwarz inequality to bound the first term.
Lemma 2. Let (Qit)ki=0 be a sequence of action-value function for each task t, (εit)ki=0 be the respective sequence of approximation errors as defined in (8). Then,
‖%̃kt ‖∞ ≤ k−1∑ i=1 γk−i‖εit‖∞ + (1 + γk)Rmaxt . (17)
Proof. First, we bound the k-step Bellman residual.
Lemma 3. Let (Qit)ki=0 be a sequence of action-value function for each task t, (εit)ki=0 be the respective sequence of approximation errors as defined in (8). Then,
‖%kt ‖∞ ≤ k−1∑ i=1 γk−i‖εit‖∞ + γkRmaxt . (18)
Proof.
‖%kt ‖∞ = ‖(T ∗t )kQ0t −Q0t‖∞
= sup s∈S,a∈A ∣∣∣r(s, a) + γ ∫ S P(ds′|s, a) max a′∈A Qk−1t (s ′, a′)−Q0t (s, a) ∣∣∣
= sup s∈S,a∈A ∣∣∣r(s, a) + γ ∫ S P(ds′|s, a) max a′∈A ( (T ∗t ) k−1Q0t (s ′, a′)− εk−1t (s′, a′) ) −Q0t (s, a) ∣∣∣ ≤ γ‖εk−1t ‖∞ + sup
s∈S,a∈A ∣∣∣γ ∫ S P(ds′|s, a) ( max a′∈A (T ∗t ) k−1Q0t (s ′, a′)− max a′′∈A Q0t (s ′, a′′) ) ∣∣∣ ≤ γ‖εk−1t ‖∞ + γ sup
s∈S,a∈A ∣∣∣ ∫ S P(ds′|s, a) ( max a′∈A ∣∣(T ∗t )k−1Q0t (s′, a′)−Q0t (s′, a′)∣∣) ∣∣∣ ≤ γ‖εk−1t ‖∞ + γ‖%k−1t ‖∞.
Since ‖%1t‖∞ ≤ Rmaxt , solving the recursion proves the lemma.
We are now able to derive the bound for the k-step empirical Bellman residual.
‖%̃kt ‖∞ = ‖(T̂ ∗t )kQ0t −Q0t‖∞
= sup (s,a,r,s′)∈Dt
∣∣∣r + γ max a′∈A Qk−1t (s ′, a′)−Q0t (s, a) ∣∣∣ = sup
(s,a,r,s′)∈Dt
∣∣∣r + γ max a′∈A ( (T ∗t ) k−1Q0t (s ′, a′)− εk−1t (s′, a′) ) −Q0t (s, a) ∣∣∣ ≤ γ‖εk−1t ‖∞ +Rmaxt + γ sup
s′′∈S max a′∈A ∣∣∣(T ∗t )k−1Q0t (s′′, a′)−Q0t (s′′, a′)∣∣∣ ≤ γ‖εk−1t ‖∞ +Rmaxt + γ‖%k−1t ‖∞. (19)
The bound is proved using (18).

heading: C EXPERIMENTAL DETAILS
text: This section serves to present additional details on the experiments that did not fit in the main paper, such as algorithm hyperparameters and additional details of the learning environments. These additional details will be provided for each experiment individually in the following subsections. The computations were executed on a desktop computer with a Geforce RTX 2080, 64 GB memory and an AMD Ryzen 9 3900X processor. All experiments were run in roughly a week of computation time on this single machine. The employed MushroomRL library is available under the MIT license.
C.1 CAR-ON-HILL
As mentioned in the main text, we used the FQI algorithm with extra-trees (Ernst et al., 2005) implemented in MushroomRL (D’Eramo et al., 2021) to conduct this experiment. The number of
trees in the extra-trees implementation was set to 50, the minimum number of samples required to split an internal node to 5 and the minimum number of samples required to be a leaf node to 2. All other parameters were left to the implementation defaults of MushroomRL. Based on this implementation we created a boosted version that runs the original FQI algorithm on the residuals of the previously learned models. The hyperparameters for those extra-trees models were the same as for the regular FQI. The implementation can be found in the accompanying code. The car-on-hill environment used for this experiment is also implemented in MushroomRL.
C.2 MAZE
The state space of the maze environments consists of the two-dimensional coordinates s=[sx, sy]∈[0, 1]2. The initial state is s0=[0, 0], and the goal state is g0=[0.95, 0.95]. The four actions displace the agent in x- or y-position by a value of 0.05. The discount factor is set to γ=0.99 and the horizon length is 200. We use a dense reward functionR(·, ·, s′) = −|g− s′| when |g−s′| >= 0.1, otherwiseR(·, ·, s′) = +5 and the episode terminates. There are two walls centered at x = 0.2 and x = 0.6, both with width w=0.05, and height ht depending on the task t. We design a curriculum composed of 10 tasks, with h1,...,9={0.05, 0.15, . . . , 0.85} and h10=0.95. Hence in the final task T10, there is only a very narrow passage through which the walls can be passed. We again make use of the FQI algorithm with extra-trees implemented in MushroomRL to conduct this experiment, again using 50 trees, a minimum number of 5 samples to split an internal node, a minimum number of 2 samples to be a leaf node and everything else left to the implementation defaults of MushroomRL. The main conceptual different to the car-on-hill experiment is that exploration is guided by the currently estimated Q-function, as we are employing an εgreedy exploration strategy to generate the samples for learning the Q-functions of the learning tasks. The exploration percentage ε is annealed in later environments. More precisely, we set ε1,...,10 = {1., 1., 1., 1., .75, .75, .5, .5, .25, .25} for the tasks T1, . . . , T10. Figure 6 visualizes the residuals of the starting state s0 that theQ-functions learned in the individual tasks, i.e., the additional values the Q-functions needed to predict in addition to the Q-value predicted from the ensemble of previously learned Q-functions. We see that the magnitude of residuals continuously decreases from task T1 to task T6. Switching to task T7 increases the magnitude of the residuals after which it then continuously declines again. The reason for this jump is that, while the optimal policy is largely unaffected by the presence of the small walls in the early learning tasks, a more significant detour is required starting from task T7.
C.3 LINEAR SYSTEM CONTROL
The linear system that needs to be controlled is given by
ṡ = ẋẍẏ ÿ  = 0 1 0 00 −0.1 0 00 0 0 1 0 0 0 −0.1  xẋy ẏ + 0 01 00 0 0 1 [axay ] = As + Ba,
representing a simple, fully-actuated point-mass with a slight amount of friction. For the linear quadratic (LQ) task, to which the curriculum learning agents are exposed first, the reward function is given by
r(s,a, s′) = −sT 3 0 0 00 1 0 00 0 3 0 0 0 0 1  s− aT [0.1 00 0.1 ] a
and the initial state is given by s0 = [−4 vx,0 0 vy,0]T , where vx,0 and vy,0 are sampled uniformly within [−0.3, 0.3]. In the target task, the agent receives the following reward signal
r(s,a, s′) = { −1, if ‖[x y]T ‖2 ≥ 0.2 0, else
and its initial position is given by s0 = [−4 vx,0 y vy,0]T , where vx,0 and vy,0 are sampled uniformly within [−0.1, 0.1] and y within [−0.4, 0.4]. Furthermore, the agent needs to keep its y-position
within [−0.5, 0.5] in order to stay on the pathway indicated in Figure 4b and it faces an additional drift moving it away from the target, particularly
ṡ = As + Ba + −0.500 0  . Consequently, the policies pre-trained in the LQ task do not quite reach the target but need to explore that they need to counteract this external force while staying on the pathway. To learn with LSPI in the LQ task, we represent the policy by a PD-controller with explorative noise
a ∼ N (Ks, 0.1I) as this ensures the quadratic form of the optimal Q-function mentioned in the main text. More precisely, it can be shown that
Q(s,a) = θTφ(s,a),
where φ(s,a) computes linear and quadratic terms of s and a (please see Bradtke (1993) for additional details). When learning with DQN in both the LQ and target task, the agent can choose between applying 8 discrete actions
a1= [ 1 0 ] , a2= [ 0 1 ] , a3= [ −1 0 ] , a4= [ 0 −1 ] ,
a5= [ .71 .71 ] , a6= [ .71 −.71 ] , a7= [ −.71 .71 ] , a8= [ −.71 −.71 ] .
Consequently, we predict these discrete Q-values with the function approximator learned in the LQ task with LSPI when training on the target task. The Q-networks employed in DQN consist of two hidden layers of 128 neurons and ReLU activations. During training, we realized that the update frequency of the target network in the DQN algorithm had a strong impact on the final agent performance. Hence, we conducted a grid search testing values in [25, 50, 100, 200, 500, 1000, 2000]. For regular DQN on the target task, an update frequency of 200 performed best, while BC-DQN yielded best results with an update frequency of 2000. For C-DQN, best results where achieved when using an update frequency of 1000 in the LQ task and an update frequency of 25 in the target task. We used Adam for optimization of the network with a learning rate of 10−4 and (β1, β2) = (0.9, 0.999). To exploit the previously learned policy in the target task for the curriculum methods, we used a fixed value of ε = 0.1 in the target task. For default DQN, we annealed ε from 1 to 0.1 over the first 1000 environment steps. As mentioned in the main paper, we additionally investigate residual policy learning (RPL) and probabilistic policy reuse (PPR) in this environment. Both approaches exploit a policy πsource learned in a source task (for our experiment this is the LQ task) to accelerate learning in the target task. As the methods are agnostic to the structure of the source task policy, we make use of the policy learned with LSPI, as this policy exhibits a more structured movement towards the target (see Figure 4b) and further requires less environment interactions to be learned (see Figure 4a). To implement RPL (Silver et al., 2018), we need to specify how to combine the actions ai and aj of the source task policy πsource and the residual policy to be learned in the target task. In our experiment, we can simply add the actions ai and aj and then select the discrete action that is more similar to the combined action in terms of euclidean distance. If there are multiple actions that are within the same minimum distance to the combined action, we choose the action that is more similar to the action of the residual policy, i.e. more similar to aj . This allows the residual policy to still move opposite to the previous policy if necessary, while preserving the bias induced by the previous policy if the residual policy does not produce an action exactly opposing the one from the previous policy. RPL has an offset parameter that controls for how many steps the residual policy does not interfere with the source task policy. For the described way of combining actions, not interfering means simply choosing the same actions as the source task policy. We tried values of 0, 2000 and 4000 steps for this offset value, where 2000 performed best. PPR requires the user to choose a decay factor ν to anneal the likelihood of executing the source task policy via p(πsource) = νt, where t is the number of past interactions (note that we follow the interpretation of PPR by Brys et al. (2015) for transfer from a single source task). As for the other baselines, we do a grid search over the target network update frequency, choosing the best. For RPL, a value of 25 performed best. For PPR, a value of 100 performed slightly better than 25 or 50.

Review summaries:
The paper proposes a new curriculum for RL method. The basic idea is to "learn" a residual for each task, modeling in this way how the tasks differ. The research topic is highly relevant and contemporary and the theoretical analysis of the method is interesting. The major drawback is the empirical evaluation. 

This paper studies a fundamental issue in curriculum design for a complex reinforcement learning problem (target task). When the target task is complex to solve with direct training on it, the learner can be trained over a sequence of tasks with increasing difficulty. Here, the tasks in the sequence vary in either the transition dynamics or reward function. The central question of the paper: developing a principled method for transferring the knowledge (Q-value function or residuals) gained in the current task of the curricula to the next task. The authors propose to use the sum of residuals trained on each task for knowledge transfer and develop a novel curriculum RL method called Boosted Curriculum Reinforcement learning. By leveraging techniques from approximate value iteration literature, they theoretically justify their choice for knowledge transfer and their algorithmic proposal. The authors also conduct interesting empirical investigations on fleshing out the importance of boosting and the curriculum components of their algorithm.

The paper tackles the problem of curriculum learning and presents a new technique (boosted CRL) that provides a tighter bound on the approximation error of the action-value function than standard curriculum learning. The authors show both theoretically and empirically the effectiveness of the approach over standard CRL. The presented methodology learns a function approximation based on the sum of `residuals'. The evaluation was done on 3 environments that had scope for the generation of a curriculum by varying the reward and exploration factors -- car on hill, maze, linear system control. Results show that BCRL performs significantly better than CRL in all environments.

This paper proposed a curriculum value-based reinforcement learning algorithm. Inspired by boosting methods, the algorithm learns on the Bellman residuals between the value function of the current task and that of the previous task. This paper provides analysis on the convergence of the algorithm and some finite-sample guarantee on the output value function. The method is tested on four different problems and is compared with two 3 baseline methods.