Boosted Curriculum Reinforcement Learning
Authors: Pascal Klink
Carlo D'Eramo
Jan Peters
Joni Pajarinen
Venue: ICLR 2022 Poster (2022)
Keywords: reinforcement learning
curriculum learning
boosting
residual learning

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, discussing 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.

Published as a conference paper at ICLR 2022
BOOSTED CURRICULUM REINEORCEMENT LEARNING
Pascal Klink; Carlo D'Eramo, Jan Peters Department of Computer Science
Joni Pajarinen
Department of Electrical Engineering and Automation Aalto University, Finland
TÜ Darmstadt, Germany
ABSTRACT
Curriculum value-based reinforcement learning (RL) solves a complex target task by reusing action-values across 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 RI., by approximating the action-value fune- tion as a sum of residuals trained on each task. This approach, which we refer to boosted curriculum reinforcement learning (BCRL), has the benefit of naturally increasing the representativeness of the functional space by adding a new resid- ual each time new task is presented. This procedure allows reusing previous action-value while promoting expressiveness of the action-valte function. We theoretically study BCRL as an approximate value iteration algorithm, discussing advantages over regular curriculum RI. in terms of approximation accuracy and convergence the optimal action-valus function. Finally, we provide detailed empirical evidence of the benefits of BCRL in problems requiring curricula for accurate action-valee estimation and targeted exploration.
INTRODUCTION
The combination of reinforcement learning (RL) (Sutton & Barto, 2018) algorithms with powerful function approximators, i.e., deep RI (François-Laavet et al., 2018; Mnih et al., 2015), break- through 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 the cost of massive amount of data needed from the interaction with the environment, hindering the practicality of deep RL methods.
Curriculum RL is biologically inspired approach that frames the problem of learning complex target task into learning a sequence of simplified, increasingly difficult, versions of it (Florensa et al., 2017; Shao al., 2018; Ivanovic et al., 2019; Narvekar 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 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 task in the curriculum. For the success of this procedure, the function approximator needs to be powerful enough 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 aaper-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 vasolvable by non-curriculum RL methods.
initialization for learning the action-value function of the next
"Correspondence Pascal Klink: pascal @ @robottoeea -earriinggnnnnnn .g.de.

---

Published as a conference paper at ICLR 2022
In this paper, we introduce a novel approach that models the action-valie function of a task as sum of residuals learned on the previous tasks in the curriculum. Our method increases the representa- tiveness of the function approximator new tasks are presented to the agent, leading 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- tra-graiddd, 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 approximate the action-value function. In this work, we formalize the curriculum RL problem in the AVI setting to investigate the representation of the action- value function obtained by BCRL and cases in which this representation may result in tighter bound on the approximation eπror compared to regular curriculum RL. We complement this analysis with an em- pirical 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), demonstrating advantages of BCRL over regular curriculum RL.
RELATED WORK
Learning under dynamic set of training experience has been investigated in different fields through- out 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 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 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 behav- ior between subsequent tasks in the curriculum done 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 its evolution during learn- ing (Aoki & Siekevitz, 1988: Rumelhart et al., 1988; Ash, 1989; Fahlman, 1990; Lahnajärvi et al., 2002: Nitanda & Suzuki, 2018) have been conducted in supervised learning scenarios. The adapta- tion of these methods the setting of RL has been limited to on-policy lemporal-differnne learn- ing (Rivest & Precup, 2003; Vamplew & Ollington, 2005b;a) and has not been further pursued in recent years. We shortly review further approaches to knowledge transfer in Appendix A.
Our work aims to improve the information transfer between subsequent tasks in curriculum value- based reinforcement learning via 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 agnostic to any value- based RL algorithm, avoiding the need to adjust the RI. algorithm of choice to be suited for the evolution of the function approximator (Rivest Precup, 2003; Vamplew & Ollington, 2005a;b).
PRELIMINARIES
3.1 DEFINITIONS AND NOTATION
We recall the notions about Markov Decision Processes (MDPs) (Puterman, 1990), and the notation used for approximate value iteration (AVI) (Farahmand, 201 1), that are relevant to our work.
2

---

Published as a conference paper at ICLR 2022
For space E, define MME) as the set of probability measures the o-algebra or. We denote B(E, B) as the space of bounded measurable functions w.n.. og with bound O<B<x.. A finite-action discounted MDP is defined as tuple T = (S, A. P, R, 7), where S is a measurable state space, A is a finite set of actions, P S x A + M(S) is transition kernel, R S x A x S + R is reward function, and Y 10. is a discount factor. A policy is mapping from the state space S to a probability distribution over the action space A. A policy induces an action-value function Q" (s, - E Re Ap=al, corresponding to the expected cumulative discounted reward obtained performing action a in state and following the policy thereafter. RL aims at solving an MDP by finding an optimal policy x² which induces an optimal action-value function (* a) sup, (s, For immediate rewards uniformly bounded by Rmux. the
Re
function is bounded by Quax = Rau/1-7. For a probability measure y E M(S x A), we define the Lp(u)-norm of measurable function Q E B(S x A) as I|Qlln.. A USxA [Q(s,))) ddp(s,)dds(ss.aaaaaaas a)) Given sequence of values Tinm = (21...., In. for some space X, the empirical norn of function f : X + T is p - EH [ 1/8 Conveniently, when X; μr, we have E [I, II From now on, we consider the L2-norm when the subscript is omitted.
Operators. We define the optimal Bellman operator T BBS x A) + B(S A) as
(T)))s,, a) A r(s, a) + / P(ds' 18, a) max Q(s',a'))
a'
The fixed point of the optimal Bellman operator is (T"Qr) = Q- As in Györfi et al. (2006),
we define the truncation operator 3B B(S A) + B(8 B) such that, given a function f E B(S x A), we have fs, a) E I B), V(s E
3.2 APPROXIMATE VALUE ITERATION
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 Q9, AVI algorithms iteratively approximate the application of the optimal Bellman operator in suitable function space, i.e., Q++1 x T*Q². Intuitively, the approximation error at each iteration plays 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 function space F via the application of a nonlinear operator S : BSS x A) + F defined as Sy = arg inf j If - y/lß for any E BSS x A). Then, we define Q = S(T )²),, and the resulting upproximation error by
E 4 T* -
(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 K" Theorem 1. (Theorem 3.4 of Farahmand (2011)). Let K be a positive integer, P distribution
over states s, and Qmax S Rimax Then, for any sequence (Qu) C. B(S x A, Qmax), and the corresponding sequence (EX) we have
K-1
11Q - 20 11,p I ((() (K) (x) + B(y, K) Rmamx
where
EK-o C(A))
We point out that the upper bound in Theorem is high-level version of the one reported in Farah- mand (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 ε as defined in Equation 1. We refer the reader to the appendix for extended version of the equation, and to Farahmand (2011) 1) for further details about it.
In Farahmand (2011), 1), the action-value function at iteration k is denoted by QTh highlight its dependency on the policy .y. In this paper, simply write Q* omitting for simplicity.
3

---

Published as a conference paper at ICLR 2022
4 CURRICULUM REINFORCEMENT LEARNING WITH BELLMAN RESIDUALS
We consider the classic curriculum RI. scenario where an agent aims at learning a complex tar- get task by solving a predefined sequence of easier, but increasingly challenging, versions of (Narvekar et al., 2020). To avoid confusion on the debatable notion of difficulty a task, in this work adopt a practical point of view where the difficulty of task is related to well-known aspects of RL, e.g., the complexity of the policies for solving them and challenging exploration (Flo- rensa et al., 2017; Ivanovic et al., 2019; Klink et al., 2020).
4.1 APPROXIMATE VALUE ITERATION IN CURRICULUM REINFORCEMENT LEARNING
Let TI.. = (TI.... T be a sequence of increasingly complex MDPs sharing the same state and action spaces, i.e., T: = (S, A, P,, R4; 7), and Tn be the target task. The of AVI algorithms in this curriculum RL. setting consists starting from an arbitrary estimate Qi (where the subscript indicates the position of the task in the curriculum) and approximating the application of the task- specific optimal Bellman operator for the current task Q Ti 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 K; the number of iterations needed to converge for each task Tr. and denote Qi = tit = Qi-1- Lemma 1. Let K be the current iteration. Then,
|1Q 26.-Q- 111p - 10 + ........llllle +117 - Σ i=++1
- -QK 112 (2)
This result 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 iterations K, that allows the action-value function estimate converge, using heuristic methods checking the magnitude of the update (Lagoudakis & Parr, 2003; Ernst et al., 2005). Since zero is not a positive integer, the components (2) cannot be bounded by the result in Theorem 1, which motivates our theoretical analysis in section 5. We denote the analytic k-step Bellman residual for task by
de (T;)* Qt (T;) -Qi-1-
(3)
Proposition 1. Given an initial ()(s)a)=11 for any (s, S x A, and considering that
Qi Qk = (i we obtain
K. * Q. E - -0)= (Tx)* ( (T.))...(TT))))))) Q = Q (4)
This result shows that, under above assumptions, the action-value function of the target task is ap- proximately equivalent to the sum of k-step Bellman residuals. Notably, especially if the curriculum sufficiently fine-grained, residuals are expected to become progressively smoother and smaller. In the following, we describe how to compute an estimate of the k-step residuals shown in (4).
4.2 BOOSTED CURRICULUM REINTORCEMENT LEARNING
It is well-known from supervised learning that: (i) small function approximators are easier 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 separate function approximator for each residual z i.c. separate approximator for each task. Given a dataset D, {(t,, ot, rž of L for each task, denote the empirical Bellman operator by (f. Q): at) A rt + max,' Q(+ a'), and define the step empirical residual as / T Qt k-1 Q At iteration kt for current task t, and defining the nonlinear operator Šøž = arg inf jer - o l| as the empirical version the operator S, we compute approximation
+-1
º = Q. + BB. 5े = Σ
ox + Φt
(5)
4

---

Published as a conference paper at ICLR 2022
Algorithm 1: Boosted Curriculum Reinforcement Learning (BCRI)
Input: Tasks Tim Q9 O; for f = I,...,7 do
Collect dataset Dr using policy induced by Q (e.g., e-greedy);
for k = 0,.... K do
dh - --7 -i: Ott1 + Qi + Sn, arg ang -
end
Qi + QK:;
end
Output:
Qh Qn+1 = E/= K
where we defined Ø. BB, Sel for compactness. For ease of notation, we use O also to de- note 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 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 realize this increase in capacity by estimating an action-value function through a sum of action-value residuals of the pre- vious tasks the curriculum. Thus, contrary to methods using the same function space for all tasks, our approach has the ad advantage of acting in an augmented function space resulting from the sum of the function space of each approximator. In supervised learning literature, the function approxima- tors in the sum are commonly known as weak regressors, meaning that boosting has the advantage of estimating complex functions 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 learned with easy function approximators curbing the risk of overfitting, (ii) the complexity of the function approximator can be chosen according the individ- ual tasks in the curriculum, contrarily to regular curriculum RL where the function approximator needs to be suitable for the target task. Conversely, inference time, method requires forward pass for each approximator in the ensemble. Finally, we clarify that the soundness of this procedure is guaranteed by the fact that if the functional space of each weak regressor is Trivenko-Cantell i.e., "the error due to the empirical process goes to zero at least asymptotically". then, due to the preser- vation theorem, also the space resulting from the sum of weak regressors Glivenko-Cantelii (Van Der Vaart & Wellner, 2000; Tosatto et al., 2017).
THEORETICAL ANALYSIS
We provide theoretical analysis of BCRL in terms of convergence guarantees and finite-sample approximation error analysis. We refer to the well-known results AVI (Farahmand, 2011; Farah- mand et al., 2010), and the analysis provided in Tosatto et al. (2017), with which analysis share some similarities.
5.1 CONVERGENCE GUARANTEES
Theorem 2. Let Qi-1 be the learned action-value for task Tr-1, and (Qi) be a sequence of measurable action-value functions for a task T, obtained following our BCRL procedure (5), where Qi = Qi Denote the Lipsehitz coefficient of the optimal Bellman operator w.rt. a norm II-Il, and assume the operator S is such that 3X >
0: [[[ I S)yll S Alaal for all E B(S x A). Then,
k-1
110 - - S
A
[(1+ X)) + (L(1 (1(1+ + 110 -
(6)
1=0
5

---

Published as a conference paper at ICLR 2022
The assumption 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 eπrоr is proportional to the magnitude of the function to approximate. This assumption holds for reasonable choices of function approximators and it is present related works the derivation of finite-time bounds for policy iteration (Munos, 2003), and value itera- tion (Munos, 2005; Tosatto et al., 2017). The following result shows that for each task, the interplay between X and Qi decides upon the approximation error w.I.t Qi
Corollary 1. Given the settings of Theorem 2, if L < 1 and X <
<(1-L) 1+he with c E [o, 1] then
| Q < el - Qi k=000
lim
If now Qi=Qi-1 is close Qi in (pp can hope achieve small error in task Ty-
5.2 FINITE- APPROXIMATION ERROR ANALYSIS
Given the inapplicability of Theorem to the decomposition Lemma 1, we now provide an alter- native analysis for our BCRL method, in which the approximation errors for task t translate
Ex = - -
ot Set e = =T -
(8)
Theorem 3. (Theorem 5.3 of Farahmand (2011)) Let (Q:) be a sequence of action-value func- tions for each task (Ei) be the respective sequence of approximation errors as defined in (8), F C BIS x A) be subset of measurable valuee functions. Then we have
inf inf ei FEF
in
inf
11e
Σ
1' 11m..
This bound shows the relation between the approximation error of the residual for task t step k the AVI Bellman Residual oº and the approximation error for previous residuals in task t. While the error is independent of previous tasks, the next Lemma shows connection between tasks.
Lemma 2. Let (Qi)zo be sequence of value functions for each task t, (ei) be the respective sequence of approximation errors as defined in (8). Then,
k-2 27 10+111+))) (1+7))-11-
||e/llo0 + Rr + k-1 lleb loo. (10)
let S sollet- 1100 +
The above bound is based on the approximation errors Ef in task To well as on the one-step a good
bellman residual e- Q! - Qi- Intuitively, this residual will be small, if Qi=Qi- approximation to Q We use (9) and (10) to finally bound the approximation error of the residual. Theorem 4. Let B max(Ile, lon. 1), and V be the VC-dimension F+, i.e., the class of all subgraphs of functions f E F (Györfi et al., 2006). For a given sequence of action-value functions (Qi) generated by BCRL, we have
propogation
approximation error
E [|E
< 4 inf FEF
|lf
L'
1'11=3-1111
5136BA* +
(log 42e + llgg(480 + 2 logo (N)V=
(11)
N
(ii) estimation error
This result bounds the expected error of BCRL by sum of three components: (i) the approximation error of the analytic residual g!¹ (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. BCRL can be advantageous the range values of the residuals of and ø become smaller as the curriculum proceeds, which can be expected for sufficiently fine-graines curriculum. In this case, fewer samples than for regular curriculum RL can be used achieve comparable estimation errors, due to the smaller range of the target ||Øt || compared to Quax

---

Published as a conference paper at ICLR 2022
7:
72
T1
72
73
Cum. Disc. Return
BC FQI
C-FQI
0.5
R-FQI
0.2
Q-
0.0
0.3
1|Q
0.2
-0.2
BC-FQI
C-FQU
B-FQI
FQI
20 40
10
20
40
80
Iteration
Iteration
Figure 1: Mean absolute error (solid, bold lines) and standard error of the approximated Qr-function over iterations as well as the corresponding performance obtained from greedy policy w.r.t. this Qr-function in task Tr in the car-on-hill environment (computed from 20 seeds). The differently shaded areas highlight the iterations on which BC-FQI and C-FQI train on tasks T1, T2 and T3. The fine, dashed lines indicate the results of the individual 20 runs from which the mean computed.
6 EXPERIMENTS
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 AVI setting and with that improve the achieved agent performance. Further, 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 al., 2021).² 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 al.. 2005), as the diwdemensionallty allows for uniform sampling of the state-action space as- sumed in the previous section and the ground truth optimal Q-function can be computed via brute- force methods (Ernst et al., 2005). Next, we evaluate the FQI algorithm which exploration is guided by the currently estimated optimal policy. Finally, we investigate boost- ing 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 curriculum, we will compare different methods in the experiments: the algorithm under investigation (FQI, DQN), version using both curriculum with boosting (BC-FQI, BC-DQN) 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 curriculum will introduce the additional approximators at the same iteration at which the curricula switches between tasks.
maze environment in
6.1 CAR-ON-IILL
The three car-on-hill tasks T1. T2, and Ts considered for curriculum learning in this experiment dif- fer in the mass of the car, taking values of 0.8, 1.0, and 1.2 respectively. The default mass of the environment 1.0 which means we are considering a version of this environment with more chal- lenging exploration, as the car needs more energy to escape the valley and receive reward signal. The dataset for learning the Q-function in each task is generated by executing 1000 trajectories with 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 Ernst et al. (2005). The results are visualized in Figure 1. We see that the combination of boosting and curriculum (BC-FQI) outperforms all other methods both in terms of final approximation error achieved on Ta 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 Tı Tz, the jump in residual shows. BC-FQI does not exhibit such a jump in residual when moving from Ti to Tz. Furthermore, BC-FQI reduces the increased residual after switching from T2 to Ts while the residual of C-FQI steadily increases once arriving at the target task. We can particularly see that the pre- pre-training in Ti and T2 leads to significantly smaller Q-function error of BC-FQI compared to B-FQI at iteration 40, which is line with the discussion in the previous sections.
"odee for reproducing results available under: https: //gi www.githb.coo.po..eeo wwwp//ct/ppcccccccccocco.......t www.cclkkkk///ooookk k Additional experimental details be found in the appendix.

---

Published as a conference paper at ICLR 2022
T5
7s
Tio
Cum Disc. Reharn
BC-EQI R-FQI
C-FQI
FQQI
40
BC-FQI
C-FQI
B-FQU
FQJ
120
Iteration
Ierattion
Figure 2: Average error the approximated Qr-functions (left) plus corresponding performance obtained from a greedy policy w.r.t. this Q--function (right) in the maze environment. Shaded colored areas correspond to two times standard error estimated from 40 seeds. The different shades of grey highlight the iterations in which BC-FQI and C-FQI train on different tasks T,. The horizontal black dashed line in the right plot highlights the maximum achievable reward in T10-
6.2 MAZE
We design a maze environment, in which 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 dense reward based on the distance the target and 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 visualization of tasks contained in the curriculum). The reward function and the target task are designed to induce highly challenging ex- ploration, requiring the use of curricula to solve the problem. As done for the car-on-hill experiment, FQI with tree-based regression (Ernst et al., 2005). For all methods, each task running 500 episodes using e-greedy exploration, decreasing the strength exploration as the curriculum proceeds. As can be seen in Figures 2 and 3, regular learning the target task does whether boosting used or not (B-FQI and FQI).
collect dataset for
not allow finding good solution, regardless The poor performance highlights the challenging exploration problem that needs be solved in this environment. The initial random exploration 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 estimated Q-function deteriorates before approaching the target task, leading to un- reliable policies. By introducing additional capacity as learning proceeds, BC-FQI allows learning an optimal policy. Indeed, we show the appendix that residuals of BC-FQI decrease later iterations, easing the function approximation problem when progressing the target task.
6.3 LINEAR SYSTEM CONTROL
The last task aims at highlighting 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, which a point mass needs to be steered towards
B-FQI
C-PQI
FQI
C-PQI
FQI
(a) Maze environments
(b) Estimated Q-function in Tip
(c) Generated trajectories using Q1a
Figure 3: (a) visualizes different maze environments T1. T4. Tr and Tio (left right, top bottom). (b) shows the final Q-functions on Tio estimated by the evaluated approaches. (c) visualizes the trajectories generated by the corresponding agents.
8

---

Published as a conference paper at ICLR 2022
x10"
BBC-DQ -C-DQU -DQN -RPL -PPR -SC-DQN -SBC-DQN
X10
1:SPT
DQN
Cum. Disc. Return
1.0
-12
-3
-1.4
-5
Steps
x10
(b) Learned LQ Q Q-functions and target environment.
(a) Agent performance
Figure 4: (a) mean performance and standard error in the linear system control task achieved with different methods. The blue vertical dashed line indicates the iterations at which BC-DQN, RPL, PPR, SC-DQN and SBC-DQN switch from the LQ- to the target task. For C-DQN, this switch indicated by the green dashed line. Statistics have been computed from 100 seeds. (b) visualizes the Q- functions learned during the pre-training in the LQ task with LSPI (for BC-DQN, RPL, PPR, SC-DQN and SBC-DQN) and DQN (for C-DQN). The arrows indicate the policy encoded by the Q-functions.
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 -1 until reaching the goal, which issues reward of 0 and ends the episode. If the agent falls off the pathway, it is reset to the initial position. We learn policy for solving this target task using DQN and introduce a curriculum that first trains in easier system to induce 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 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 knowl- edge by using quadratic features in the first learning task and only relying on a neural network to realize the Q-function in the target task. With quadratic features, the Q-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 L.SPT in the I.Q task and then adjust this Q- Q-function in the target task with residual using DQN.
Figure 4a shows that this incorporation of additional structure into the curriculum (BC-DQN) im- proves performance over both directly learning that does not adjust the structure of the agent to the learning task in the curriculum (C-DQN). We further see that two other transfer knowledge baselines Residual Policy Learning (RPL, Silver al. (2018)) and Probabilistic Policy Reuse (PPR, Fernández et al. (2010)) do not improve learning performance over regular learning on the target task (please see Appendix A for discussion of the methods and why we chose them as baselines). Reusing the quadratic Q-function from the LQ problem as shaping reward (SC-DQN, Ng al. (1999)) drastically improves performance. Com- bined with boosting (SBC-DQN), this improvement is even stronger. It is particularly surprising that C-DQN, RPI,, and PPR do not improve over DQN. For C-DQN, this poor performance may result from the DQN algorithm learning slower in the LQ problem compared to LSPI (10.000 vs. 2.000 steps), while further learning a less accurate Q-function (Figure 4b). For RPL and PPR, it is hard to provide explanations, as both methods rely on the LSPI Q-function. Nonetheless, the success of shaping reward based on the same LSPI Q-function shows the impact of how existing knowledge is reused.
the target task (DQN) and regular curriculum
7 CONCLUSION
We introduced boosted curriculum reinforcement learning (BCRL), a new method for action-valus 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 representa- tiveness 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 and knowledge transfer baselines. Future re- search on the presented findings should investigate ways to counteract the (linearly) growing com- plexity of the (boosted) agent for long task sequences and to adapt the BCRL framework to recent advances in automated curriculum generation (Narvekar et al., 2020).

---

Published as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
We aim to guarantee the reproducibility of our work by providing the proofs of the main paper theorems and additional details of the conducted experiments in the appendix. Further, we provide the code for running the experiment at https::
ACKNOWLEDGMENTS
This project has received funding from the DFG project PA3179/1-1 (ROBOLEAP).
REFERENCES
Chiye Aoki and Philip Siekevitz. Plasticity in brain development. Scientific American, 259(6):56, 1988.
Minoru Asada, Shoichi Noda, Sukoya Tawaratsumida, and Koh Hosoda. Purposive behavior acqui- sition for a real robot by 1996.
reinforcement learning. Machine learning, 23(2):279-333,
Timur Ash. Dynamic node creation backpropagation networks. Connection science, 1(4):365- 375, 1989.
Samuel Barrett and Peter Stone. Cooperating with unknown teammates in complex domains: A robot soccer case study of ad hoc teamwork. In AAAI conference on artificial intelligence, 2015.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Currieulum learning. In- ternational Conference on Machine Learning, 2009.
Aude G Billard, Sylvain Calinon, and Rüdiger Dillmann. Learning from humans. Springer hand- book of robotics, pp. 1995-2014, 2016.
Georgios Boutsioukis, Ioannis Partalas, and Ioannis Vlahavas. Transfer learning in multi-agent reinforcement learning domains. In European Workshop on Reinforcement Learning. Springer, 2011.
Steven Bradtke. Reinforcement learning applied linear quadratic regulation. In Neural Infor- mation Processing Systems, 1993.
Tim Brys, Anna Harutyunyan, Matthew E Taylor, and Ann Nowé. Policy transfer using reward shaping. In AAMAS, pp. 181-188, 2015.
Sonia Chernova and Manuela Veloso. Interactive policy learning through confidence- auton- omy. Journal of Artificial Intelligence Research, 34:1-25, 2009.
Felipe Leno Da Silva and Anna Helena Reali Costa. Towards zero-shot autonomous inter-task mapping through object-oriented task description. In Workshop Transfer in Reinforcement Learning (TiRL), 2017.
Felipe Leno Da Silva and Anna Helena Reali Costa. A survey transfer learning for multiagent reinforcement learning systems. Journal of Artificial Intelligence Research, 64:645-703, 2019.
Felipe Leno Da Silva, Matthew E Taylor, and Anna Helena Reali Costa. Autonomously reusing knowledge in multiagent reinforcement learning. In International Joint Conference on Artificial Intelligence, 2018.
Carlo D'Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Mushroomrl: Simplifying reinforcement learning research. Journal of Machine Learning Research, 22(131): 1-5, 2021.
Jeffrey L Elman. Learning and development in neural networks: The importance of starting small. Cognition, 48(1):71-99, 1993.
10

---

Published as a conference paper at ICLR 2022
Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, al. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55):1-21, 2019.
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556, 2005.
C Lebiere Fahlman. The cascade-correlation learning architecture. Neural Information Processing Systems, 1990.
Amir-massoud Farahmand. Regularization reinforcement learning. PhD thesis, University of Alberta, 2011.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. Advances in Neural Information Processing Systems, 2010.
Fernando Fernández and Manuela Veloso. Probabilistic policy reuse a reinforcement learning agent. In International joint conference on Autonomous agents and multiagent systems, 2006.
Fernando Fernández, Javier Garcfa, and Manuela Veloso. Probabilistic policy reuse for inter-task transfer learning. Robotics and Autonomous Systems, (8(7):866-871, 2010.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Picter Abbeel. Reverse cur- riculum generation for reinforcement learning. Conference on Robot Learning. 2017.
Vincent François-Lavee Peter Henderson, Riashat Islam, Mare G Bellemare, and Joelle Pineau. An introduction deep reinforcement learning. Foundations and Trends@ in Machine Learning, 11 (3-4):2193354, 2018.
Yoav Freund. Boosting weak learning algorithm by majority. Information and Computation, 121 (2):256-285, 1995.
Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63(1):3-42, 2006.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. distribution-ffee theory of nonparametric regression. Springer Science & Business Media, 2006.
Pablo Hernandez-Leal and Michael Kaisers. Towards fast detection of opponents in repeated stochastic games. In International Conference on Autonomous Agents and Multiagent Systems. Springer, 2017.
Pablo Hernandez-Leal Yusen Zhan, Matthew E Taylor, L Enrique Sucar, and Enrique Munoz de Cote. Efficiently detecting switches against non-stationary opponents. Autonomous Agents and Multi-Agent Systems, 31(4), 2017.
Boris Ivanovic, James Harrison, Apoorva Sharma, Mo Chen, and Marco Pavone. Barc: Backward reachability curriculum for robotic reinforcement learning. International Conference on Robotics and Automation, 2019.
Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander Hauptmann. Self-paced curricu- lum learning. AAAI Conference on Artificial Intelligence, 2015.
Pascal Klink, Carlo D'Eramo, Jan R Peters, and Joni Pajarinen. Self-paced deep reinforcement learning. Advances in Neural Information Processing Systems, 2020.
Dorothea Koert, Maximilian Kircher, Vildan Salikutluk, Carlo D' D'Erao, and Jan Peters. Multi- channel interactive reinforcement learning for sequential tasks. Frontiers in Robotics and AI, 7: 97, 2020.
Marcelo L Koga, Valdinei Freire, and Anna HR Costa. Stochastic abstract policies: Generalizing knowledge to improve reinforcement learning. IEEE Transactions on Cybernetics, 45(1):77-88, 2014.

---

Published as a conference paper at ICLR 2022
Marcelo Li Koga, Valdinei Freire da Silva, Fabio Gagliardi Cozman, and Anna Helena Reali Costa. Speeding up reinforcement learning through abstraction and transfer learning. In International conference on Autonomous agents and multi-agent systems, 2013.
Kai A Krueger and Peter Dayan. Flexible shaping: How learning in small steps helps. Cognition, 110(3):380-23 -3)44, 2009.
Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of Machine Learning Research, 4:1 1007-114,, 2000..
Jani JT Lahnajärvi, Mikko Lehtokangas, and Jukka PP Saarinen. Evaluation of constructive neural networks with cascaded architectures. Neurocomputing, 48(1-4):573-607, 2002.
Alessandro Lazaric. Transfer in reinforcement learning; a framework and a survey. In Reinforcement Learning, pp. 143-173. Springer, 2012.
Alessandro Lazaric and Marcello Restelli. Transfer from multiple mdps. Neural information pro- cessing systems, 2011.
Alessandro Lazaric, Marcello Restelli, and Andrea Bonarini. Transfer of samples in batch reinforce- ment learning. International conference on Machine learning, 2008
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 518(7540):529-5333 2015.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pp. 560-567, 2003.
Rémi Munos.
Error bounds for approximate value iteration. In Proceedings the ence on Artificial Intelligence, volume 20, pp. 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
the National Confer-
Sanmit Narvekar, Jivko Sinapov, Mattco Leonetti, and Peter Stone. Source task creation for curricu- lum learning. In International Conference on Autonomous Agents Multiagent Systems, 2016.
Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone.
Curriculum learning for reinforcement learning domains: A framework and survey, Journal of Machine Learning Research, 21(181):1-50, 2020.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations:
Theory and application to reward shaping. In International Conference on Machine Learning (ICML), 1999.
Atsushi Nitanda and Taiji Suzuki. Functional gradient boosting based residual network percep- tion. International Conference on Machine Learning. 2018.
Martin L Puterman. Markov decision processes. Hundbooks in operations research and management science, 2:331-434. 1990.
Françcois Rivest and Doina Precup. Combining td-learning with cascade-correlation networks. In- ternational Conference on Machine Learning, 2003.
David E Rumelhart, James L McClelland, PDP Research Group, al. Parallel distributed process- ing, volume 1. IEEE Massachusetts, 1988.
Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv:1606.044 140.:16600046,, 2016.
J Saul, Leon. The behavior of organisms. an experimental analysis. Psychoanalytic Quarterly, 10: 164-166, 1941.
Robert E Schapire. The strength of weak learnability. Machine learning, 5(2):197-227, 1990.
12

---

Published as a conference paper at ICLR 2022
Kun Shao, Yuanheng Zhu, and Dongbin Zhao. Starcraft micromanagement with reinforcement learning and curriculum transfer learning. JEEE Transactions on Emerging Topics in Computa- tional Intelligence, 3(1):73-88) 84, 2018.
Felipe Leno Da Silva and Anna Helena Reali Costa. Object-oriented curriculum generation for rein- forcement learning. In International Conference on Autonomous Agents and MultiAgent Systems, 2018.
Tom Silver, Kelsey Allen, Josh Tenenbaum, and Leslie Kaelbling. Residual policy learning. arXiv preprint arXiv:1812.06298, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Maxwell Svetlik, Matteo Leonetti, Jivko Sinapov, Rishi Shah, Nick Walker, and Peter Stone. Au- tomatic curriculum graph generation for reinforcement learning agents. AAAI Conference on Artificial Intelligence, 2017.
Matthew Tayllor and Peter Stone. Transfer learning for reinforcement learning domains: survey. Journal of Machine Learning Research, 10(7), 2009.
Samuele Tosatto, Matteo Pirotta, Carlo D'Eramo, and Marcello Restelli. Boosted fitted q q-iteration. International Conference on Machine Learning, 2017.
Peter Vamplew and Robert Ollington. Global versus local constructive function approximation for on-line reinforcement learning. Australasian Joint Conference on Artificial Intelligence, 2005a.
Peter Vamplew and Robert Ollington. On-line reinforcement learning using cascade constructive neural networks. International Conference on Knowledge-Bir Based and Intelligent Information and Engineering Systems, 2005b.
Aad Van Der Vaart and Jon Wellner. Preservation theorems for glivenko-cantelli and uniform glivenko-cannelli classes. In High dimensional Probability 11, pp- 115-133. Springer, 2000.
13

---

Published as a conference paper at ICLR 2022
A DISCUSSION OF RELATED TRANSFER LEARNING METHODS
Given our focus on knowledge transfer via Q-functions in curriculum RI., 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 sur- veys 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 (Feránndez & 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 aforemen- tioned 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 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 (Fernández Veloso, 2006; Fernández et al., 2010; Silver et al., 2018), reward functions (Brys et al., 2015) or demonstra- tions/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- Q-function transfer setting, methods that extend upon the naive idea of initializing the Q-function of the next task with the most recently learned one, as e.g. done in Narvekar et al. (2016), are rather sparse. Boutsioukis et al. (2011) investigate the idea of sparsely initializing the Q-function in the new task with a bias value for the optimal actions of the previous task in discrete state-action spaces. Rusu et al. (2016) present 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 reusing a value function from source task as a shaping function in target task. Both progressive neural networks and reward shaping are orthogo- nal to our investigation of boosting and its influence on the residual of Q-function approximators in curriculum RL. As show in Figure 4a, boosting hence can still provide benefits when combined with such approaches.
For the comparison in Section 6.3, we choose residual policy learning (RPL. Silver et al. (2018)), as it follows a similar idea of learning a residual, however in the form of a policy, and avoids the complication of the overall curriculum by e.g- introducing a secondary RL objective (Brys 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) allow 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 ignore the actions of the current policy. The same problem occurs for the maze task with its four actions left, right, up, and down. Apart from RPL, we also evaluate probabilistic policy reuse (PPR, Fernández al. (2010)) as it like RPL- introduces no crucial additional design choices in the curriculum.
B ADDITIONAL THEOREMS AND PROOFS
We report extended version of our Theorem I based on Theorem 3.4 in Farahmand (2011).
Theorem 1. (Theorem 3.4 of Farahmand (2011)). Let K be a positive integer, p an initial state k distribution, and Qmax < 1-x Then, for any sequence (Qu) C B(S x Amau)) and the
Himax
corresponding sequence (=)) we have
27
2 K Rmma
1Q"" S (1 - (1-
11,
Cha (K;)) (Eu, (Eu....,EK-1:77) inf
[E((0,1]
1 1-
where E(Eo...., EK-1;T) = ΣK-
K-1 2r || and Cvr.pu and ag as defined. respectively, in Def-
inition 3.1 and Equation 3.3 in Farahmand (2011).
14

---

Published as a conference paper at ICLR 2022
We proceed reporting the proofs of the theorems and lemmas described in the main paper. As start, we first restate the most important identities:
प - (T7)* Oi 0º Q. + Set
et - = Qi
el = --
= Se.
2 + + = Q.
Theorem 2. Let Qi-1 be the learned action-value for task Ti-1, and (Qi) be a sequence of measurable action-value functions for a task Tr obtuined following our BCRL procedure (5), where Qi = Qi Denote the Lipschitz coefficient of the optimal Bellman operator w.r.t. a norm II-Il, and assume the operator S is such that YX >
0: [[ - S)yll & Allll for all y E BiS x A). Then,
k-1
110 - -277 S
Σ
[L(++ + (L(1 (Z(1+A))) | Qi
(12)
Proof. Before carrying out the proof, we want to clarify the role of the chosen norm |-||. While it is well known that the Bellman operator is contraction for the supremum norm |1-1|-> (since Q - I >1|Q1 - Q21 x for any Q1, Q2 BSS x A)), the use of the supremum norm puts tougher requirement on the chosen function approximator S, as for the supremum norm the largest approximation error determines A. The use of the (p((4)-orm eases the aforementioned requirement S, however, for the Lp(u)-norm it is not guaranteed that the Bellman operator is contraction for any Q1. Q2 E B(S x A). While Farahmand (2011) upper bounded the Lipschitz coefficient of the optimal Bellman operator for [pp(u)-noms by
Cp-=000 =7 (Von du((s,a) d(saa))
dps.a
1
sup (aTa))SSA To(a'ss") dus (5))
(13)
where a(s = (ss(s) ?C is typically larger than one. Note, however, that this is only an upper-bound and grid-world simulations indicated that L < 1 for many Q1 Q2 B(S A), however, not all. While AVI convergence results in Lp(u))-orm such as (Munos, 2005) obviously apply to BCRL, the bound in Theorem 2 particularly highlights the dependency the Q-function learned in task - 1. After this discussion, we now prove the actual theorem:
0 - 0:1 =
Q: T7
- Qi
ct + T Q:ll
- et - set
+ + -
s / | 0 Q:1|
(14)
s <> 0: Qi + + + -0 Qi|
(15)
where (14) considers the assumption on the operator (7 5) and (15) follows noting that
| < T 170:|| + ||-0 0p|| s 41 - 0: + 09 Q:
Unrolling the recursion in (15) then proves the desired result:
| - 0:1| s 2110% -0: + L +(1+>>|| 1 0:1
< <X100% - 0:
+ 1(1 2) (a/ Q:| 1(1 =1
= a Of Qi /| + + + 20/10 - 0:()) +LL11 + 10 Qi
h-1
.... S Σ
(L(1 (11++)))1100 0:1| + (1(1 1177 08 -2i1
15

---

Published as a conference paper at ICLR 2022
Corollary 1. Given the settings of Theorem 2, if L < 1 and X <(IL)
I+ with [0, 1] then
lim 60000
|1 Qill < <l Qill-
Proof. If we assume X = 1-4 with 0 <ō S - then it follows that L(1 + A) = 1 - L8 <
and hence
lim
(L(1+ AJ)' + (1(1 21(++)))*
70000
=
lim k00
A Σ (1- L8)² + (1-L5)+ L5)a
k-1
A lim
Σ
(1 - L8)* + lim (1 - Lo)*
k-+00 k=0
k0000
1-4
1
1- Lg
8
1- (1-11)
L
122
As next step, we require that the above term is upper bounded by a factor E 10, 1]. This require- ment yields
k-1 E (1(1
= 1- L- L8
lim k+000
A)) + (L(1 + 21)*
<6
I,25
+ 1 - L L8 < L2de
$ 1 1, < 8(T, + T.2c)
1-1
L+ <6
Note that it holds that 0 < 8 トー S - for any e E [0. such that our initial assumption on are fulfilled. Inserting this inequality into our definition of À then finally yields
1 1- L L
1 - L 1-L
+
T T.2e
(1 L)(1 Lc) -(1-L) L)
L L2E
1+ Le L Life 1 +
I, L2c
Le L2e 6 Le
c(1 ()-L)
I2E 1 Le
1
Theorem 3. (Theorem 5.3 of Farahmand (2011) I)) Let (Qi) be a sequence of action-value func- tions for each task t, (ei) be the respective sequence of approximation errors as defined in (8), F FCB( x A) be a subset of measurable action-value functions. Then we have
k-1
inf IIS - ei 12 S il feT
5. lle
- 11,-
(16)
fEr
Proof. Although this theorem the same as Theorem 5.3 in (Farahmand, 2011), we still provide the proof here for ease understanding. For an arbitrary function f F and task t, have Il - ef l1 I Iff - ofllu + løtt ef Iلا. Then,
et et ||_ (TT) T: T:
16

---

Published as a conference paper at ICLR 2022
S
(T)) 0p Q-
(T)) 17 Ti - 12-111
oi
=
(7))
60 171t 2- + e 1
(17) k- 10 - T, Qi Qi-2111 (1,))
7 3
+
(17))
Σ L
+
0
||
01 1 (1,)
+
7
+
01
k-1
E' k 211u + 1
1le
-22 = Σ
L' 111 k- -
'1
For the last equality, we used that ol e! 111 || 11
Noo Theorem 4. Let B max(I loo, 1), and V1 be the VC-dimension F+, which is the class of all subgraphs of functions f E F (Györfi et al., 2006). Given a sequence of action-value functions (Qt) generated by our BCRL, we have
A-1 Σ
2
E [||--1 ||
S inf If
e. +
D'lle 11
SEF
5136Bt* +
[log 42e + 2oog(480ee)))
+llog(N)V
(17)
N
Proof. Using Theorem 11.5 from Györfi et al. (2006), we obtain
e 1l2 + 5136B/*
E [| 2
ilf
(log 42e log 1og(4800 + log((N)V
Completing the proof requires to relate || Schwarz inequality:
of to (16). This is achieved using the Cauchy-
Il
et 11 < (llf
@t 1| + 1let et k1,))
s 2|l 11 2 e <
2|
Le 12 +2
Σ --'lee--11
Plugging above inequality into the result obtained from Györfi et al. (2006) concludes the proof.
Let (Qi) be sequence of action-value functions for each task t, (Ei) be the respective sequence of approximation errors as defined in (8). Then,
Lemma 2.
27 01--11+700
+))
1 - 1ー llee loo. (18)
llet llo S - +
| + Re
1
1=1
Proof. As a first step, we bound the k-step Bellman residual using the following Lemma.
Lemma 3. Let (Qi) be sequence of action-value functions for each task I, (et) be the respective sequence of approximation errors as defined in (8). Then.
k-1 27 (1+7)7
k-i ||etlbo
1 1- 2 +
llet oc -
1 4-y l locc.
(19)
1 1-7
17

---

Published as a conference paper at ICLR 2022
Proof.
llee cl = 1170 Qf + - Qillo
- -1 - Q + Q/ et - 0illz
-177Q Q _ + QT 0
k-1
- Σ (T - Qi +)) + eill.0
a)) a) + / Pr(ds'ls, max O+ (s', (a:laa)----(666 (s, - 'ss(s)))
sup sES
d'EA
k-2
+ Σ (T -Q + = + eel
d'EA a)) + +7 / Pr(ds'ls,a) m)
max O/ (s', - (s, - (s,
sup
A
re(s, a) + / Pr(do'ls,a) d'EA
max 0₂ (8' - Ti -T (s, ( +...
sup aEA
sup sES,aEA
/s Pr(ds'ls,a)
max a'EA
1 (5' d')
max Q - (8'
d'EA
sup sES,aEA
? / Pc(ds'(s.a)
mmx Q (s'.a') = (s',0')
mmax
- (66 +...
('EAA
a'EA
k-2
57 1lo+ 100)) +
Σ (TQQ) Qi - -+t) + et 10.0
ST (1eE|ll><|1 1 + llet
(20)
We need to bound the individual terms ||TiQ - 11 We proceed as Tosatto et al. (2017):
1 1.
r(s, a) + 7 1/8 Pr(do'ls, a) max Qi (s..a) dea
sup sES,eA
r(s,a) a) + Polds'ls, m - - -(; - -(t,a))((s,aa)
sup .ES,EAA
dEA [11+))|l+(le> +y sup Pi(ds((s,a)
max 1 (s',a') - QF (5 (s)
SEA
d'EA
d'
<(1+ <(1+>)llefll> + + Q/-11100
s(1+ (1e/1l0o + + >>1x)=>11>>> + Q.=²
Q. 21
k-1 s... S 71+
> + xh "1TTT Q. loc
=(1 + 7) || so + k llee Ic
(21)
Inserting (21) into (20) then yiclds
||
(0i0(1))) + 1lee1llo
+1
Σ ==1
x i-1 1 1- "1e?/1oc + - 1lo0
+ +lle!
18

---

Published as a conference paper at ICLR 2022
8-1
b 7)
Σ
x
|le? 10
+ Σ
7 l1 1ox0
j=1
i=0
k- 1-1
1- *
>l +11+7)
> |000000 0000000 +
1-7 l o0000
i=1 ;=1
k-1
1-
>lll +
Σ
Σ
x²
-1= - 1leilloo
+ 1 7 -lee ooo
k-1 1-1
1 -h
(1 + +1))))1)))ll (1 + 7)
1| 1100 +
1-7 l o0
+ 1- 1-1h g/
Ielilbo + (1 + 7)
Σ 16
1 ? ll 10x0
7 + 1- 1-th z/
Σ Ellefllo +(1 7)
|6
1 1-7 11 100
1=0
k-1
7 k-j
1- //
Σ I| +(1
2
|10/ +
1 1 l1 11
j=1
7)
1 1- /²
|5ا10 +
- 7 11+7 1 20
1-7
The proof is completed by reformulating (1 + 71 - x) - (1 - 7) = 27 (1 + U
Equipped with the result from Lemma 3, we are now ready to prove Lemma 2 by unrolling l1 loo and using (19):
1 -o || Qi-1 lo
r r+ yax mt (s) a'EA
sup (ED)))))
+ (T. of (s'' a') at (s' - ()
sup (sa)),))))
a'EA
<n1l=²- 11 + Runx +y sup max ""
T: Qt (s" - (e(s",a'))
s <>l107 -1 + Rumux + + - 11:00
k-2 27 (1 7) x --
|sállo0 + Remux + 7 1 k-1
s s -1lx +
1 - lleb
1 1
C EXPERIMENTAL DETAILS
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 desktop computer with Geforce RTX 2080, 64 GB memory and an AMD Ryzen 9 3900X processor. All experiments were run in roughly a week of computation time this single machine. The employed MushroomRI. library is available under the MIT license.
19

---

Published as a conference paper at ICLR 2022
77
Tx
@r (5 a
#
10
15
50
100
150
200
250
280
Iteration
Figure 5: Average residual of the starting state So predicted by the learned Q-functions in the dif- ferent learning tasks of the maze environment. The average and standard error (barely visible) is computed from 40 different seeds.
C.I CAR-ON-HILL
As mentioned the main text, we used the FQI algorithm with extra-trees (Ernst et al., 2005) implemented in MushroomRL (D 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 split 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 boosted version that runs the original FQI algorithm 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- [s2. sy [0, 1J2. The initial state is Sy [0, Oj. and the goal state is S0-90.955, 0.95]. The four actions displace the agent in x- or y y-position by value of 0.05. The discount factor is set to 7=0.99 and the horizon length is 200. We
-lg s'| when gg s'| >= 0.1, otherwise R(, s') = +5 and the episode terminates. There are two walls centered 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 9.....9=(0000) 0.15..... 0.85) and = Hence in the final task Tio. there is only a very narrow passage through which the walls can be passed.
dense reward function R(:
We again make use of the FQI algorithm with extra-trees implemented in MushroomRL to con- duct this experiment, again using trees, a minimum number of samples to split an internal node, minimum number of 2 samples to be a leaf node, and everything else left to the imple- mentation defaults of MushroomRL. The main conceptual difference to car-on-hill experiment is that exploration is guided by the currently estimated Q-function, we are employing an s- 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, set e1....10 1,, 1.. 75,.77 75, -5, 5, 22,25 .25) for the tasks Ti..., T10-
Figure 5 visualizes the residuals of the starting state So that the Q-functions learned in the individual tasks, i.c., the additional values the Q-functions needed to predict in addition to the Q-value pre- dicted from the ensemble of previously learned Q-functions. We see that the magnitude of residuals continuously decreases from task Tj to task Tg. Switching to task T> 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, 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
0
Ir
0
0.1
0
0
+
1
0
0g
As +
Ba,
0
1
0
Qy
0
0
-0.1
0
1
20

---

Published as a conference paper at ICLR 2022
representing simple, fully- point-mass with slight amount of friction. For the linear quadratic (LQ) task, to which the curriculum learning agents are exposed first, the reward function given by
3
0
0
0
r(s, as,
0
0
0
1
3
a
0.1
0 0.1
a
0
1
and the initial state is given by So = within [-0.3, 0.3). the target task, the agent receives the following reward signal
[-4 Un,0 O "ggul", where 1x.0 and uy.0 are sampled uniformly
{ if w 2 0.2
as)
(0. clse
and its initial position is given by so = U2.0 vy,ol', where 0x,0 and 0g.0 are sampled uniformly
within - 0.1] and y within [-0.4, 0.4). Furthermore, the agent needs keep its y-position
within (0.55 0.5] in order to stay on the pathway indicated in Figure 4b and it faces an additional
drift moving away from the target, particularly
- 0.5
As Ba
0
Consequently, the policies pre-trained in the LQ task do not quite reach the target but need to explore that they need counteract this external force while staying the pathway. To learn with LSPI in the LQ task, we represent the policy by a PD-controller with explorative noise
(Ks,, 0.11)
this ensures the quadratic form of the optimal Q-function mentioned in the main text. More precisely, it can be shown that
((s,a) = 0T ((.
where (ss, a) computes linear and quadratic terms of s and a (please see Bradtke (1993) for ad- ditional details). When learning with DQN in both the LQ and target task, the agent can choose between applying 8 discrete actions
0
0
0
A2
1
Ag
a4
-1
.71
.7
- .7
-.71 -.71
a==
.71
a6
a- =
.71
Consequently, we predict these discrete Q-values with the function approximator learned in the LQ task with LSPI when training the target task. The Q-networks employed in DQN sist of two hidden layers of 128 neurons and ReLU activations. During training, we real- ized that the update frequency of the target network in the DQN algorithm had strong im- pact on the final agent performance. Hence, we conducted a grid search testing values in [25, 50, 100, 200, 500, 1000, 2000, 4000). For regular DQN on the target task, update frequency of 200 performed best, while BC-DQN yielded the best results with an update frequency of 2000. For C-DQN, best results were achieved when using an update frequency of 1000 in the LQ task and an update frequency of 25 in the target task. When employing shaping reward, taking 4000 environment steps between an update of the target network performed best for both boosted and non-boosted DQN. We used Adam for optimization of the network with a learning rate of 10-4 and (81,8)) = (0.9, 0.999). To exploit the previously learned policy in the target task for the curriculum methods, we used fixed value of e 0.1 in the target task. For default DQN, annealed from 1 to 0.1 over the first 1000 environment steps.
As mentioned in the main paper, additionally investigate residual policy learning (RPL) and prob- abilistic policy reuse (PPR) in this environment. Both approaches exploit a policy T.ource learned in source task (for experiment this is the LQ task) to accelerate learning in the target task. As the
21

---

Published as a conference paper at ICLR 2022
methods agnostic to the structure of the source task policy, make use of the policy learned with LSPI, as this policy exhibits more structured movement towards the target (see Figure 4b) and further requires fewer environment interactions (Silver et al., 2018), we need to specify how to combine the actions a, and a of the source task pol- icy ssource and the residual policy to he learned in the target task. In experiment, add the actions a; and a, and then select the discrete action that is more similar to the combined action in terms of euclidean distance. If multiple actions 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, iee more similar to ay. This allows the residual policy to still move opposite 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 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 v to anneal the likelihood of exe- cuting the source task policy via p( source) that we follow the interpretation of PPR by Brys et al. (2015) for transfer from a single source task). We tried three different values v=0.998, 0=0.9996 and 0=0.99988, with 0=0.998 performing best. With this value, ='=0.1 after z 1150 environment steps. As for the other baselines. we do grid search over the target network update frequency, choosing the best. For RPL, a value of 25 performed best. For PPR, value of 200 performed slightly better than lower ones. For both methods, update frequencies larger than 1000 did not learn at all on the target task.
be learned (see Figure 4a). To implement RPL
simply
v², where is the number of past interactions (note
22


Reviews:
[{"review_id": "y85ti_l2YEz", "reviewer": "Reviewer_YXe6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe boosting method is an interesting and promising way to adapt the change of task difficulty. As far as I know, this is the first paper that applies boosting to the RL curriculum learning. The experiment is solid and results are impressive. \n\nWeakness:\nMy concern is on the theoretical analysis. I found the formulation and analysis are poorly written. Many notations are not clear. The proof is either trivial or a direct application of previous results.\n\nHere are the detailed concerns. \n\n1. Can authors discuss how strong the assumption on the operator $S$ in Theorem 2 is? It seems a very strong assumption since it holds uniformly for all $y \\in \\mathcal{B}(\\mathcal{S} \\times \\mathcal{A})$.\n\n2. It is weird that the author states that the approximation error comes with two aspects and the second one depends on the nonlinear operator $S$, while the definition of approximation error in Equation (1) is independent of $S$.\n\n3. I think Theorem 1 is too complicated to interpret. For example, what is the behavior of the R.H.S in Theorem 1? The authors should elaborate more on the intuition of Theorem 1 (discussing the meaning of each term).  If the details of Theorem 1 is not important, the author may present only an informal version of Theorem 1 that highlights the high-level idea.\n\n4. In the definition of the nonlinear operator $S$, it is not clear what is $\\mu$-norm. If I am correct, $\\mu$ is the probability measure over $\\mathcal{S} \\times \\mathcal{A}$ and the empirical version $\\hat S$ is the empirical error evaluated on the dataset $\\mathcal{D}_t$. It is also not clear what $\\mu$ means in Algorithm 1.\n\n5. The notation is conflicting at the start of Section 4.1. It seems $Q_t^0$ represents the starting of task $t$. That means when task changes, $k$ should be reset to 0. However, the author also writes that $Q_{t+1}^{k+1} \\approx T_{t+1}^{*} Q_{t}^{k}$.\n\n6. I am assuming that Theorem 2 is analyzing the $Q_t^k$ using the accurate $S$ instead of the empirical version. The authors should make it clear about this point.\n\n7. It seems there are two versions of $Q_{t}^k$ in the paper, one generated from the optimal Bellman operator and the other one from the empirical one. The author should use different notations for them. For example, in Equation (8), the approximation error should be using the empirical one if I understand it correctly.\n\n8. Essentially, Theorem 4 concerns only the error of the last task. There should be more discussions on $\\epsilon_i^0$, which is also some approximation using finite samples. I think a more interesting direction is that when the complexity of the task is actually increasing, when the algorithm without boosting will suffer a high approximation error if they only use simple models. If they use complex models, then the VC-dimension could be high even for the simpler tasks, which slows down the training. ", "summary_of_the_paper": "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.", "summary_of_the_review": "I recommend this is a borderline paper due to the issues I raised on the theoretical part and the notations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nG92n_GuLGE", "reviewer": "Reviewer_N1P2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors propose a Curriculum Learning method to \"learn\" a residual for each task, instead of trying to learn from scratch each of them. \nThe proposed method is interesting and creative, and seems to be beneficial to the learning process in the empirical evaluation.\n\nMy main concern is the omission of the many related works. Although the authors evaluate the algorithm only in simple environments (which means it's relatively easy to implement other baseline methods), they do not compare against the results of any related methods from [1] or [2], for example (the former is.cited in the manuscript).\n\n[1] Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. Journal of Machine Learning Research, 21(181):1–50, 2020.\n\n[2] Silva, Felipe Leno, and Anna Helena Reali Costa. \"A survey on transfer learning for multiagent reinforcement learning systems.\" Journal of Artificial Intelligence Research 64 (2019): 645-703.\n\nFurthermore, some sentences show lack of familiarity with the literature, for example: \"[...]contrary to curriculum RL which uses the same functional space \" (not all Curriculum Learning methods do that). Therefore, I would really like to see a performance comparison between the proposed method and state-of-the-art Curriculum Methods, instead of just against \"baselines\".\n\n\n----\nminor\n----\n\nShouldn't it be \"C-FQI\" in the legend of Figure 1?\n\n\n\n\n\n-----\nPost-rebuttal\n-----\nThe authors tried to address some of my concerns, in special adding some text in an appendix commenting on the distinction of their paper from TL. While I appreciate the (necessary) effort, I don't see the reason for adding this as an appendix, and think it would have been better to incorporate it to the main text even if it would require more effort to make sure space limitations are not exceeded. My evaluation was already positive, and the author response and other reviewers' evaluation had nothing that would make me lower my grades. Therefore, my evaluation is maintained .", "summary_of_the_paper": "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. ", "summary_of_the_review": "Paper investigating a relevant research topic. The manuscript contributes interesting ideas and the proposed method seems to have good performance. However, the lack of comparison against state-of-the-art methods makes it hard to assess how good the method is compared to other related works.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iP-RKeD53QF", "reviewer": "Reviewer_TFaS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper makes an interesting progress/contribution towards applying reinforcement learning methods for real-world challenges (hard exploration problems). The proposed algorithm is novel and justified both theoretically and empirically. \n\nI haven’t carefully checked the theoretical analysis (Section 5) and the corresponding proofs.\n\nThe paper is overall well written and easy to follow. However, the related work discussion seems limited: missing references for the works from (i) curriculum design via environment design, and  (ii) knowledge transfer via reward shaping literature. \n\n----\n\nIn the introduction, the authors state that the existing (value-based) curriculum RL methods are constrained to use the same function approximator throughout all the tasks; this is because the trained Q-value function of the current task in the sequence is used as the initialization for the next task. However, as in [Brys et al. 2015], one can utilize potential-based reward shaping techniques (a principled approach) to transfer knowledge between tasks. In this case: (i) the next task in the sequence will receive a dense/informative reward function that will ease the learning while maintaining the policy invariance property, and (ii) also, has the flexibility of choosing different functions approximators for each task in the sequence. Thus, it is important to both conceptually and empirically compare your proposed curriculum method with the curriculum methods with knowledge transfer based on reward shaping methods (e.g., [Brys et al. 2015]). \n\n[Brys et al. 2015] Brys et al. Policy Transfer using Reward Shaping. AAMAS, 2015. \n\n----\n\nI had a few confusions related to the experiments (Section 6). Please clarify them. \n\nI am a bit confused about the methods compared (mainly FQI and B-FQI) in the experiments section:\n(i) BC-FQI is a method clear: FQI blended with Algorithm 1 (boosting + curriculum)\n(ii) C-FQI: FQI trained over the curricula of tasks; here, the knowledge transferred between tasks is the trained Q-value function (as in existing value-based curriculum RL methods). Is this right?\n(iii) FQI: trained only on the data from the target task or random mixture of data from all the tasks? The FQI (red color) curve in Figure 1 only corresponds to convergence/performance of FQI on the target task T3; or it is region-wise segmented for T1, T2, T3?\n(iv) B-FQI: same confusion as in FQI. If it is trained on the target task only, what is the boosting component here? \n\nA clear description of each method (or even pseudocode in the appendix) compared would be helpful for the reader. \n\nIn summary, \n1/ What is the difference between the curriculum methods? Are the non-curriculum methods only trained on the target task or they are also trained on the same pool of tasks as curriculum methods but presented in a random ordering? \n\n2/ If the non-curriculum methods are trained only on the single target task, what is the role of boosting here, i.e., how is the sum of residuals of different tasks applicable here? \n\n3/ “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.” -- this statement is not clear to me. Please clarify. \n\n----\n\nA question/suggestion/comment regarding the Maze experiment:\n“It obtains a dense reward based on the distance to the target ...”\nIsn’t a dense reward already ease the learning process of the RL agent? Of course, here, the size of the two walls will alter the hardness of the environment (by changing the transition dynamics). Still, considering the target task with a sparse reward that obtains a reward only when it reaches the goal would make it a complex problem to solve. Have you tested the sequence of tasks with such sparse rewards? \n\nThe hardness of the sequence of tasks can be varied by: (i) fixing the reward function, and varying the transition dynamics of each task, (ii) fixing the transition dynamics, and varying the reward function of each task, and/or (iii) varying both reward and dynamics. I see that both Car-on-Hill and Maze experiments fall under case (i). Have you tested the case (ii)?\n\nA simple experiment to cover case(ii): Consider a (stochastic) chain with length L (very large), and the goal is at the end of the chain. Here (keeping L fixed), one can vary the hardness of the tasks by defining reward functions with different granularity: sparse goal-oriented reward (target task), landmark-based rewards (intermediate tasks), and optimal myopic rewards obtained via potential-based reward shaping (easiest task).      \n\nTo cover case(i) with the chain example, fix the reward as a sparse goal-oriented reward, and gradually increase the length of the chain.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper proposes an interesting and novel algorithm for curriculum RL. The paper is overall well written. However, the conceptual and empirical comparison to knowledge transfer via reward shaping methods is missing. There were some clarity issues in the experiments. If these two issues are addressed, I am marginally inclined towards acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fvi8FLPLEWF", "reviewer": "Reviewer_hq3v", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Pros**\n* Writing and Presentation: The paper was clearly written and the graphs were well annotated.\n* BCRL Framework: The BCRL framework was interesting (in particular the idea of boosting using residuals). Some of the presented theorems were a bit mathematically involved, but the presentation of the ideas systematically helped parse the key ideas in the proof. \n\n**Cons**\n* Experiments and evaluation: While the setup is largely well explained, it would have been clear if at least one paragraph explained the details of the Linear System Control environment. From the main paper, it was not clear what was meant by the LSPI applied to LQR -- some of the details from the appendix can be brought to the main paper. Furthermore, the reasoning given for the decline in the performance of CRL in the environment needs more clarification/insights. I was not entirely convinced by the reasoning provided (on unlearning of Q-function when the task was switched to the target task).\n\n* Clarification question: Am I correct in understanding that, the proof (beginning with Proposition 1) assumes that convergence to the optimal state-action function will take place in a finite number of iterations? Extending the ideas presented, can it be said that the subsequent approximation error of the residuals becomes smaller as the number of tasks in the curriculum increase, given that for a task the error of BCRL is bounded?\n\n* Clarification question: The terms in Eq (11) can be made more intuitive in the paragraph explaining them. This was slightly difficult to parse.\n\n* The limitations of the approach could have been addressed better.\n\n**Additional Comments**:\n\nCan the presented methodology be extended to account for the increasing task complexity in the curriculum and weigh the importance of each task gradually presented in learning the state-action value? \n\n**General Summary**:\n\nOverall I thought the paper presented the key ideas in a clean way. The mathematical framework is very interested and opens avenues for future research in the area -- both practical and theoretical. The experimental setup for the Linear Control System could have been better explained.\n\n*Originality*:  Moderate\n\n*Clarity*: Good\n\n*Quality*: Good\n\n*Significance*: Moderate to High", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall I liked the ideas presented in the paper and think it provides a good starting point for analyzing theoretically, the non-trivial task of curriculum learning in RL. The idea of using the sum of residuals to model the state-action function approximation was interesting. I am inclined to accept the paper because of its promise and utility in inspiring similar approaches to curriculum learning (which provide a framework for theoretical analysis), though the experimental set-up could have been made clearer and limitations of the approach be made explicit.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel curriculum learning method for RL based on the concept of boosting. The proposed method builds on the curriculum value-based RL framework and uses boosting to reuse action-values from previous tasks when solving the current task. The method is analyzed theoretically in terms of approximation accuracy and convergence. Moreover, extensive experiments demonstrate the effectiveness of the method. The reviewers acknowledged the importance of the studied problem setting and generally appreciated the results. I want to thank the authors for their detailed responses that helped in answering some of the reviewers' questions and increased their overall assessment of the paper. At the end of the discussion phase, there was a clear consensus that the paper should be accepted. The reviewers have provided detailed feedback in their reviews, and we strongly encourage the authors to incorporate this feedback when preparing a revised version of the paper.
Decision: Accept (Poster)