POMRL: No-Regret Learning-to-Plan with Increasing Horizons
Authors: Khimya Khetarpal
Claire Vernade
Brendan O'Donoghue
Satinder Singh
Tom Zahavy
Venue: Accepted by TMLR ()

Abstract: We study the problem of planning under model uncertainty in an online meta-reinforcement learning (RL) setting where an agent is presented with a sequence of related tasks with limited interactions per task. The agent can use its experience in each task and across tasks to estimate both the transition model and the distribution over tasks. We propose an algorithm to meta-learn the underlying relatedness across tasks, utilize it to plan in each task, and upper-bound the regret of the planning loss. Our bound suggests that the average regret over tasks decreases as the number of tasks increases and as the tasks are more similar. In the classical single-task setting, it is known that the planning horizon should depend on the estimated model's accuracy, that is, on the number of samples within task. We generalize this finding to meta-RL and study this dependence of planning horizons on the number of tasks. Based on our theoretical findings, we derive heuristics for selecting slowly increasing discount factors, and we validate its significance empirically.

Published in Transactions on Machine Learning Research (06/2023)
POMRL: No-Regret Learning-to-Plat with Increasing Horizons
Khimya Khetarpal*
Deportment of Computer Science
McGill Universily
Claire Vernade* University of Tuebingen
cuair..erradde@@maii.ccmm
Brendan O'Donoghue Google Deepmind
bodonoghhue@@google.coom
Satinder Singh Baveja Google Deepmind
bavejla@googleccom
Tom Zahavy Google Deepmind
tomeahany&ggoogle.com
Reviewed on OpenReview: https: http///vpppeeveeeeeeee net/ forum? id= brGgOAXYtr
Abstract
We study the problem of planning under model uncertainly an online mela-reiinforcementt learning (RT.) setting where an agent is presented with a sequence of related tasks with limited interactions per task. The agent can use its experience in each task and across tasks to estimate both the transition model and the distribution over tasks. We propose algorithm to meta-learn the underlying relatedness across tasks, utilize it to plan in each task, and upper-bound the regret of the planning loss. Our bound suggests that the average regret over tasks decreases as the number of tasks increases and as the tasks are more similar. In the classical dingle-task setting, it is known that the planning horizon should depend on the estimated model's accuracy, that is, on the number of samples within task. We generalize this finding to meta-RL and study this dependence of planning horizons the number of lasks. Based our theoretical findings, we derive heuristics for selecting slowly increasing discount factors, and validate its significance empirically.
1 Introduction
Meta-learning (Caruana, 1997; Baxter, 2000; Thrun & Pratt, 1998; Finn al., 2017; Denevi et al., 2018) offers a powerful paradigm to leverage past experience to reduce the sample complexity of learning future related tasks. Online meta-learning considers sequential setting, where the agent progressively accumulates knowledge and uses past experience to learn good priors and to quickly adapt within each task Finn et al. (2019); Denevi et al. (2019). Robots acting in real world for instance need to be responsive to and robust against perturbation inherent in the environment dynamics and their decision making. When the tasks share structure İee. have similar transition dynamics and are related, such approaches enable progressively faster convergence, or cquivalently better model accuracy with better sample complexity (Schmidhuber & Huber, 1991; Thrun& & Pratt, 1998; Baxter, 2000; Finu et al., 2017; Balcan et al., 2019).
"Equal Contribution
Work partially doue during internship DeepMind. Now at Deepmind.
Work partially done DeepMind.

---

Published in Transactions on Machine Learning Research (06/2023)
In model-based reinforcement learning (RL), the agent uses estimated model of the environment to plan actions ahead towards the goal of maximizing rewards. A key component in the agent's decision making is the horizon used during planning. In general, an evaluation horizon is imposed by the task itself, but the learner may want to use a different and potentially shorter guidance horizon. In the discounted sctting, the size of the evaluation horizon is of order (1 - Tevaz) -1, for some discount factor Jeval E (0, 1), and the agent may use Y * "eeval for planning. For instance, a classic result known as Blackwell Optimality (Blackwell, 1962) states there exists a discount factor Y and a corresponding optimal policy such that the policy is also optimal for any greater discount factor y 2² Thus, an agent that plans with y = = will be optimal for any Teral > 7- In the Arcade Learning Environment (Bellemare et al., 2013) discount factor of Veval = 1 is used for evaluation, but typically a smaller is used for training (Mnih et al., 2015). Using a smaller discount factor acts as a regularizer (Amil et al., 2020; Petrik & Scherrer, 2008; Van Seijen et al., 2009; François- et al., 2019; Arumugam et al., 2018) and reduces planner over-fitting in random MDPs (Arumugam et al., 2018). Indcod, the choice of planning horizon plays a significant role in computation (Kearns et al., 2002), optimality (Koesis & Szepesvári, 2006), and on the complexity of the policy class (Jiang et al., 2015). In addition, meta-learning discount factors has led to significant improvements in performance (Xu et al., 2018; Zahavy et al., 2020; Flennerhag et al., 2021; 2022; Luketina et al., 2022).
When doing model-based RL with a learned model, the optimal guidance planning horizon, called effective horizon by Jiang et al. (2015), depends on the accuracy of the model, and so on the amount of data used to estimate it. Jiang et al. (2015) show that when data is scarce, a guidance discount factor 7 < Jeval should be preferred for planning. The reason for this is straightforward; if the model used for planning is inaccurate, then errors will tend to accumulate along the planned trajectory. A shorter effective planning horizon will accumulate loss error and may lead to better performance, even when judged using the true "eva2- While that work treated only the batch, single-task setting, the question of elfective planning horizon remains open in the online meta-learning setting where the agent accumulates knowledge from many tasks, with limited interactions within each task.
In this work, we consider a medle-reinforeement--eerre problem made of a sequence of related tasks. We leverage this structural task similarity obtain model estimators with faster convergence as more tasks are soen. The central question of our work is:
Can we mela-learn the model across tasks and adapt the effective planning horizon accordingly?
We lake inspiration from the Averuge Regret- Regret-Upper-Berr Upper-Bound Analysis [ARUBA] framework (Khodak et al., 2019) to generalize planning loss bounds to the meta-RL setting. A high-level, intuitive outline of our approach is presented in Fig. 1. Our main contributions are as follows:
We formalize planning in a model-basod meta-RL sctting as an average planning loss minimization problem, and we propose an algorithm to solve it.
Under a structural task-similarity assumption, we prove a novel high-probability task-averagod regret upper-bound on the planning loss of our algorithm, inspired by ARUBA. We also demonstrate a way to learn the task-sinilarity parameter a on-the-fly. To the best of our knowledge, this is first. formal (ARuBA-style) analysis to show that meta-RL can be more efficient than RL.
Our theoretical result highlights a new dependence of the planning horizon on the size of the within- task data m and on the number of tasks T. This observation allows to propose two heuristics to adapt the planning horizon given the overall sample-size.
2 Preliminaries
Reinforccment Learning. We consider tabular Markov Decision Processes (MDPs) M (S, P, Yoral)
where S is a finite set of states, A is a finite set of actions and we denote the set cardinalities as S = |S] and A = [l]. For each state s e S, and for each available action a E A, the probability vector P(- | s a) defines a transition model over the state space and a probability distribution in a set of feasible models Dp C As, where As the probability simplex of dimension S 5-11 1. We denote Σ < the diameter of Dp. A policy is a function S - A and it characterizes the agent's 's behavior.
2

---

Published in Transactions on Machine Learning Research (06/2023)
Tunk Simburiky
Our Result: 2 s
Σ
v7
p
T Taaks
Σ
Without Meta-Learning! E
0
Pul
nasampias per
Onfine Meta-Learning
Planning
Kay-Takeaways
Learning. The agent faces a sequence of lasks with transition vector (P*) (EE2) (probability vectors represented by blue dots) all close to each other (a <=== 1). The agent builds transition model for each task and plans with these inaccurate models. By using data from previous tasks, the agent meta-learns initialization of the model (Po.)), which leads to better planning in new related but unseen tasks. We show improved average regret upper bound that scales with lask-similarily parameter and inversely with the number of lasks T: as knowledge accumulates, uncertainty diminishes, and the agent can plan with longer horizons. All tasks p ~ P are centered at some fixed but unknown po, depicted here by the shaded red dot and pointed by the arrow.
Figure 1: Effective Planning Horizons in
We consider the bounded reward setting, i.e., R E [0, Rmax] and without loss of generality we set Rmax (unless stated otherwise). Given an MDP, or task, M, for any policy π, let VM,y I be the value function when evaluated in MDP M with discount factor y (0, (potentially different from Teva)); defined VM, (s) E E Ry'R,, Su s). The goal of the agent is to find an optimal policy, Th,, arg max, Eg-p V M.y (s) where p > 0 is any positive measure, denoted x when there is no ambiguity. For given state and action spaces and reward function (S,A, R), we denote IL, the set of potentially optimal policies for discount factor y: II, = fo P s.t. π == = where M = (S,A, R, P, We use Big-O notation, O(-) and Ö(),, to hide respectively universal constants and poly-logaritmmic terms in S, A and level).
(the confidence
Model-based Reinforcement Learning. In practice, the true model of the world is unknown and must be estimated from data. One approach to approximately solve the optimization problem above to construct a model, (R, P) from data, then find " for the corresponding MDP A = AS, P,)). This approach is called model-based RL eettainty-qquivalene (CE) control.
Planning with inaccurate models. In this setting, Jiang al. (2015) define the planning loss as the gap in expected return in MDP M when using & Yoval and the optimal policy for an approximate model M:
C(M, 7 Yava1) = ||
The Mitena
V Virii M. |1
Thus, the optimal effective planning horizon (1-7*)-1 - is defined using the discount factor that minimizes the planning loss, i.e., 7" == minogrrreal L(M, M, Tevaa).
Theorem 1. (Jiang el. ul. (2015)) Let M be an MDP with non-negalive bounded rewards and evaluation discount factor Teval. Let M be the approzimate MDP comprising the true reward function of M and the approzimate transition model P, estimated from m > O samples for each state-action pair. Then, with probability at least 1,
Mirren Miraal
Ti Mi
Teval 7
+
27 Rmax
(V (22m
(VE-
A log 8
(1)
(1 Yeva:) )1 77 7)2
where Σ upper-bounded by 1 as P.PEAs. As.
This result holds for a count-based model estimator (i.e, empirical average of observed transitions) given by generator model for each pair (8,a). a). It gives upper-bound on the planning loss function of the
3

---

Published in Transactions on Machine Learning Research (06/2023)
Planning Loss
0.50
Cr 0.75
B10
<ic cla cin c4n
cle ci KM 08
m = 10 m 20
50
On the role of incorporating a ground truth prior of transition model planning horizon. The planning loss is function of the discount factor 7 and is impacted by incorporating prior knowledge. The learner has m = 5, 10, 20, 50 samples per task to estimate the model, corresponding to the curves in each sub figure. Inspecting any of the sub figures, we observe that larger values of m lead to lower planning loss and a larger effective discount factor. Besides, inspecting one value of m across tasks (e.g., m = 5),, ), we see that the same effect (lower planning loss and larger effective discount) occurs when the learner puts more weight on the ground truth prior through a.
Figure 2:
guidance discount factor 7 1. The result decomposes the loss into two terms: the constant bias which decreases as tends to Teval, and the variance (or uncertainty) term which increases with but decreases 1/ym. As m - so that second factor vanishes, but in the low-sample regime the optimal effective planning horizon should trade-off both terms.
Illustration. These effects are illustrated Fig. 2 on a simple 10-state, 2-action random MDP. The leftmost plot uses the simple count-based model estimator and reproduces the results from Jiang et al. (2015). We then incorporate the true prior (mean model p as in Fig and defined above Eq. 3 in Assumption 1) in the
estimator with a growing mixing factor a E (0, 1): P(m) aP (1 - E' We observe that increasing the weight E 1) on good prior knowledge enables longer planning horizons and lower planning loss.
Online Learnngg and Regret. We consider an online meta-RL problem where an agent is presented with a sequence of tasks Mj, M,,..., Mr, where for each E [T). Mr = (S, Pt, R, Tevaz); that is, the MDPs only differ from each other by the transition matrix (dynamics model) pt. The learner must sequentially estimate the model fet for each task from batch of m transitions simulated for each state-action pair".
Its goal is to minimize the average planning loss also expressed in the form of task averaged regret suffered in planning and defined as
1 T T
T
E(Mra Malsrr/MMMa Miar Teval) =
Σ (=1
C(Me M(
= T
V
Meee MesTions
1110
(2)
Note that the reference MDP for each term is the true Me, and the discount factor y is the same in all tasks. One can this objective stochastic dynamic regret: at each task E [7], the learner competes against the optimal policy for the current true model, as opposed to competing against the best fixed policy in hindsight used in classical definitions of regret.
Note that our dynamic regret is different from the one considered in ARUBA (Khodak et al., 2019). They consider the fully online setting where the data is observed as an arbitrary stream within each task, and each comparator simply the minimum of the within-task loss hindsight. In our model, however, given access to a simulator (See Sec. 2) allows us get i.i.d transition samples as batch at the beginning of each task, and consequently we define consequence of this difference is that their regret bounds cannot be directly applied to our setting, and we prove new results further below.
regret with respect to the true generating parameter. One key
So total m.S.A samples.
4

---

Published in Transactions on Machine Learning Research (06/2023)
3 Planning with Online Meta-Reinforcement Learning
We here formalize planning in a model-based meta-RL setting. We start by specifying all our assumptions in See 3.1 including our main assumption about task relatedncss in Sec. 1, present our approach and explain the proposed algorithms POMRL and ada-POMRL in Sec. 3.2. Our main result. is a high-probability upper bound on the average planning loss under the assumed task relatedness, presented as Theorem 2.
3.1 Assumptions
In many real world scenarios such as robotics, it is required to be responsive to changes in the environment and, at the same time, to be robust against perturbation inherent in the environment and their dccision making. In such practical scenarios, the key reason to employ meta-learning is for the learner to leverage task-similarity (or task variance) across tasks. Bounded task similarity is becoming core assumption in the analysis of recent meta learning (Khodak et al., 2019) and multi-task (Cesa-Bianchi et al., 2021) online learning algorithms.
Assumption (Structural Assumption Across Tasks: Task Relatedness). In this work, we exploit the structural assumplion that for all L [T], pt ~ centered al some fixed but unknown po E A and such that for any (s,a),
8.a - Po sa= = max (s, a) 0.8.
(3)
(s,a)
This also implies that m e ||Pt. - -aall S 20, and that the meta-distribution P bounded within a small subset of the simplex. It immodiate to extend our results under a high-probability assumption instead of the almost sure statement above. In our experiments, we will use Gaussian or Dirichlet priors over the bounded with high-probability, not almost surely. Importantly, we will say that
simplex, whose moments multi-task environment is strongly structured when < E, Lee when the effective diameter of the models is smaller than that of the entire feasible space.
Assumption 2 (Access to a Simulator). We assume that for each task E [T] we have access to a simulator of transilions (Kearns el al., 2002) providing m i.idd. samples (Xt.) i..m St Pt(-|s, a) (categorical distribution).
Next, for simplicity we assume throughout that the rewards are known and focus on learning and planning with an approximate dynamics model. Additionally estimating the reward is a straightforward extension of our analysis and would not change the implications of our main result. Assumption 3 (Known Rewards). Given a distribution of tasks, we assume that the rewards are known.
3.2 Our Approach
With access to a simulator (Assumption 2); for each (s, we can compute an empirical estimator for each s' [S]: PL (x') = 1(X 3.0 /m, with naturally Σ. Pt. (s') =1 We perform meta-RL via alternating minimizing a batch within-task regularized least-squares loss, and outer-loop step where we optimize the regularization to optimally balance bias and variance of the next estimator.
Estimating dynamics model via regularized least squares. We adapt the standard technique of meta-learned regularizer (see e.g. Baxter (2000); Cella et al. (2020) for supervised learning and bandit respectively) this model estimation problem. At each round t, the current model P P(s..) is estimated by minimizing a regularized lcast square loss: for a given regularizer h2 (to be specified below)? and parameter X > 0 for each (8,a) E S x A we solve
1 Σ m
1|-
pt. (s.a)
arg min EDs
1(x
- -Peeoo
dellP((e.a) hhlle.
(4)
ElanEEAs
empirical transition prob.
2In principle, this loss is well defined for any regularizer but we specify meta-learned one and prove that it induces good performance.
5

---

Published in Transactions on Machine Learning Research (06/2023)
where use [ s.a to denote the onc-hot encoding of the state into vector in R Importantly, h, and X are meta-learned in the outer-loop (see below) and aflect the bias and variance of the resulting estimator. The solution of equation 4 can be computed in closed form as convex combination of the empirical average (count-based) and the prior: pr ath, + (1 -
A is the currett mixing parameter. (1)) at) where dg 1+}.
Meta-lcarning the regularization. At the beginning of task < S T, the learner has already observed t related but different tasks. We define he as an average of Means (AoM):
Outer-loop:
E=
1 (8.0)
M(s,)) f- poit (s,a)
pd
(5)
(s.a)*
m
Deriving the mixing rate. To set at, compute the Mean Squared Error (MSE) of Pt (s.a)* and minimize upper bound (see details in Appendix B3: (SE(((().)) I afo²(1 t) + (1 ax)² 2 which leads to
a, (((411/)m+T*
A Algorithm depicts the complete pseudo code. We note here that POMRL (o) assumes, for now, that the underlying task-similarity parameter a is known, and we discuss a fully empirical extension further below (See Sec. 4). The learner does not know the number of tasks a priori and tasks are faced sequentially online. The learner performs meta-RL alternating between within-task estimation of the dynamics model pe via a batch of m samples for that task, and an outer loop step to meta-update the regularizer po,++1 alongside the mixing rate 0.+1- For each task, we use a p-Selection-Pe Prooceddeeee to choose planning horizon 7* S 7aval We defer the details of this step to Sec. 6 as is non-trivial and only a partial consequence our theoretical analysis. Next, the learner performs planning with an imperfect model Pt. For planning, we use dynamic programming, in particular policy iteration (a combination of policy evaluation, and improvement), and value iteration to obtain the optimal policy Th "in"" for the corresponding MDP M,.
Algorithm 1: POMRL (a) Planning with Online Meta-Reinforremen Learning
Input: Given task-similarity (a(s,a)) matrix of size S A. Initialize po.1 to uniform, 01 0. for task i E [7] do
for tth batch of m samples do
(m(m) = (1 ax) E X, Poit // regularized least squares minimizer. 2" -
ar, o, S,
n pr + Planning (m)) //
Output: T/p
Update po.t+1 01+1 02(41/0mm
// meeaa- AoM (Eq. 5) and mixing rate
3.3 Average Regret Bound for Planning with Online- taatee--ett--aannne
Our main theoretical result below controls the average regret of POMRL (a), a version of Alg. with additional knowledge of the underlying task relatedness, i.e., the true o > 0.
Theorem 2. Using the notation of Theorem 1, we bound the average planning loss equation 2 for POMRL (a):
Neval - + 245 ò
m
d a
C < (1 Nevaz (1 - 7) (1 - 7
(6)
m2
2 +
with probability at least 1 8, where o² < the measure of the task simi-iiil and max (s, a).
The proof of this result is provided in Appendix D and relies on new concentration bound for the meta- learned model estimator. The last term the r.h.s. corresponds to the uncertainty the dynamics.

---

Published in Transactions on Machine Learning Research (06/2023)
First we verify that if T =1 1 and m grows large, the second term dominates and is equivalent to O m (as o² f/ 1) + 0): which is similar to that of Jiang et al. (2015) as there is no meta-learning, with an additional ) but second order term due to the introduced bias. Then, if m is fixed and small, for small enough values of o² (Lypically a < 1/ym), the first term dominates and the r.h.s. boils down to Ô (/a+T) This highlights the interplay of our structural assumption parameter o and the amount of data m available at each round. The regimes of the bound for various similarity levels are explored empirically in Sec. 5 (Q3). We also show the dependence of the regret upper bound on m and T for a fixed o, in Appendix Fig. F3.
Implications for degrec of task-similarity i.c., values. Our bound suggests that the degree of improvement you can gel from meta learning scales with the task similarity instead of the set size E. Thus, for S Σ, performing meta learning with Algorithm guarantees better learning measured via our improved regret bound when there is underlying structure in the problem space which we formalize through Eq. 3. Should be large, the techniques will still hold and our bounds will simply scale accordingly.
When o = 0, all tasks are exactly the same. Indeed, the mixing rate d2 ~ 1 for all 1, so our algorithm boils down to returning the average of means io. for each task, which simply corresponds to solving the tasks as a continuous, uninterrupted stream of batches from the nearly same model that nas aggregates. Unsurprisingly, our bound recovers that of (Jiang et al., 2015, Theorem 1): the bound below reflects that we have to estimate only one model in space of "sizc" E with mT samples.
(V
278 ò L S (1 Teval) (1 7)) (1 (1-2)²
Neval -7
Σ mT
(7)
When a a= 1, then o -= then the meta-learning assumption is not relevant but our bound remains valid and gracefully degrades to reflect it. We need to estimate T models each with m samples. Then the second term
vm reflects the usual estimation error for each task while the first term is an
added bias (second order in m due to our regularization to our mean prior P that is not relevant here.
E (1 Yaval) (1 (1- (1 (1-
Teval -Y +
1 (1 (
27S
(1 + ) VT
m +
(8)
vm
Connections to ARUBA. As explained earlier, our metric is not directly comparable to that of ARUBA (Khodak et al., 2019) but it is interesting to make a parallel with the high-probability aver- age regret bounds proved in their Theorem 5.1. They also obtain an upper bound in Ó(1//m + 1/VmTT if one upper bounds their average within-task regret U S Bym.
Remark 1 (Role of the task similarity in Eq. 2). When > 0, POMRL naturally integrates each new data batch into the model estimation. The knowledge of a is necessary to obtain this exact and intuitive update rule, and our theory only covers POMRL equipped with this prior knowledge, but we discuss how to learn and plug-in â, in praclice. Nole that it would be possible to exlend our result to allow for using the empirical variance estimator with tools like the Bernstein inequality, but we believe this it out of the scope of this work as it would essentially give a similar bound as obtained in Theorem with an additional lower order term in OLL/T), and it would not provide much further intuition on the meta- eatt-planning problem we study.
4 Practical Considerations: Adaption On-The-Fly
In this section we propose variant of POMRL that meta learns the task similarity parameter, which we call ada-POMRL. We compare the two algorithms empirically in 10 state, 2 action MDP with closoly related tasks with a total of T = 15 tasks (details of the experiment setup are deferred to Sec. 5).
Performance of POMRL Recall that POMRL is primarily learning the regularizer and assumes the knowledge of the underlying task similarity (i.c. o). We observe in Fig. 3 that with each round E T POMRL is able to plan better it learns and adapts the regularizer to the incoming tasks. The convergence rate and final performance corroborates with our theory.
7

---

Published in Transactions on Machine Learning Research (06/2023)
Can also meta-learn the task-similarity parameter? In practice, the parameter may not be known and must be estimated online and plugged in (see Appendix C for details).
adia POWRL POWALUI
Alg. ada-POMRL uses Welford's algorithm to compute an online estimate of the variance after every task using the model estimators, and simply plugs-in this estimate wherever POMRL was using the true value. From the perspective of ada-POMRL POMRL is 'oracle', i.c. the underlying task-similarity is known. However, in most practical scenarios, the learner does not have this information priori.
3.0
Paaniing Loss
2.0
1.
05
We compare empirically POMRL and ada-POMRL on a strongly structured problem (o s 0.01) in Fig. and observe that meta-learming the under- lying task relatedness allows ada-POMRL to adapt to the incoming tasks accordingly. Adaptation on-the-fly with ada-POMRL comes at a cost i.e., the performance gap in comparison to POMRL but eventually converges albeit with a slower rate. This is intuitive and similar theoretical guarantee applies (See Remark 1).
Figure 3: ada-POMRL enables mela-learning the lask-similarity on-the-fly with a performance gap for the initial set of tasks as com- pared to the oracle POMRL but improves with more tasks
This online estimation of a means that ada-POMRL now requires an initial value for o1, which is a choice left to the practitioner, but will only affect the results of a finite number of tasks the beginning. Using σ1 too small will give a slightly increased weight to the prior initial tasks, which is not desirable as the latter is not yet learned and will result in increased bias. On the other hand, sctting ô1 too large (i.c close to 1/2) will decrease the weight of the prior and increase the variance of the returned solution; in particular, in cases where the true a is small, large initialization will slow down convergence and we observe empirical larger gaps between POMRL and ada-POMRL In the extreme case where a ss 0, a large initialization will drastically slow down ada-POMRL as it will take many tasks before it discovers that the optimal behavior essentially to aggregate the batches.
Algorithm 2: -AM-L Planning with Online Meta- Reinforcement Learning
Input: Initialize po.1 to uniform, (ō), as a matrix of size x A,01 = 0.
for task t E [T] do for (th batch of m samples do
pe(mm = (1 a Eis X₁ + po.t // regularized least squares minimizer. 7" + SSeecctioo Prr.eiiion-Poceuueee..... at, oz, o,, T,A,A)
n² pp +- Planning(P (*(m))
Output: T TM
Update po.t11 δef1 + Welford's 's online algorithm (6o)s, poltt1 poo)) // meta-update AoM (Eq. 5) and task- parameter.
Update a:-1 dess (1+1/)m11 // meta-update mixing rate, plug max(osxx)
Tasks vary only in certain states and actions. Thus far, we considered a uniform notion of task similarity as Eq. holds for any as, However, in many practical settings the transition distribution might remains the same for most part of the state space but only vary some states across different tasks. These scenarios hard to analyse in general because local changes in the model parameters do not always imply changes in the optimal value function nor necessarily modify the optimal policy. Our Theorem 2 still remains valid, but it may not be light when the meta-distribution has non-uniform noise levels. More precisely Theorem 1 in Appendix remains locally valid for each (s, a) pair and one could easily replace the uniform with local (s,a); but this cannot directly imply a stronger bound on the average planning loss. Indoed, in our experiments, both POMRL and ada-POMRL the parameter and respectively, are S A matrices of state-action dependent variances resulting in state-action dependent mixing rate Ox-
8

---

Published in Transactions on Machine Learning Research (06/2023)
5 Experiments
We now study the empirical behavior of planning with online meta-learning in order to answer the following questions: Q1.Does meta-learning a good initialization of the dynamics model facilitate improved planning accuracy for the choice of y = Tevar? (Sec. 5.1) Q2.Does meta-learning a good initialization of the dynamics model enables longer planning horizons? (Sec. 5.2) Q3.How does performance depend on the amount of shared structure across tasks i.e., o? (Sec. 5.3) Source code is provided in the supplementary material.
Setting: For each experiment, fix a mean model P A (see below how), and for each new task E [T], we sample P from a Dirichlet distribution centered at P As prescribed by theory (see Sec.3.2), we set a Rs 0.01 S 1/5vm unless otherwise specified (see Q3). Note that a and & respectively, are S x A matrices of state-action dependent variances that capture the directional variance as we used Dirichlet. distributions as priors and these have non-uniform variance levels in the simplex, depending on how close to the simplex boundary the mean is located. Aligned with our theory, we use the max of the a matrices resulting in the aforementioned single scalar value. As in Jiang et al. (2015), pe (and each Pt) characterizes random chain MDP with S = 10 states and A A= 2 actions, which is drawn such that, for each state action pair, the transition function P(s, s') is constructed by choosing randomly k = 5 states whose probability is set to O. Then we draw the value of the S - k remaining states uniformly in [0, 1] and normalize the resulting vector.
5.1 Meta-reinforcement learning leads to improved planning accuracy for [eral. [Q1.]
We consider the aforementioned problem setting with a total of T' = 15 closely related tasks and focus on the planning loss gains due to improved model accuracy. We fix y = "eval, a rather naive y-Selection-PPocedure and show the planning loss of POMRL (Alg. 1) with the following baselines: 1) Oracle Prior Knowledge knows priori the underlying task structure (Po, o) and uses an estimator (Eq. 4) with exact regularizer oa and optimal mixing rate a -'(1+1/0m=- 2) Without Meta-Learning simply uses pe = pt, the count-based estimated model using the m samples seen in each task, 3) POMRL (Alg. 1) meta-learns the regularizer but knows apriori the underlying task structure, and 4) ada-POMRL (Alg. 2) meta-learns not only the regularizer, but also the underlying task-similarrtt online. The oracle a strong bascline that provides minimally inaccurate model and should play the role of an 'empirical lower bound". For all baselines, the number of samples per task = 5. Results are averaged over 100 independent runs. Besides, we also propose and empirically validate competitive heuristics for r-Selection-Procetee also run another baseline called Aggregating(a 1), that simply ignores the meta-RL structure and just plans assuming there is a single task (See Appendix F.2).
in Sec. 6. Besides, we
Inspecting Fig. 4(a), we can see that our approach ada-POMRL (green) results in decreasing per-lask planning loss as more tasks are seen, and decreasing variance as the estimated model gets more stable and approaches the optimal value returned by the oracle prior knowledge bascline (blue). On the contrary, without meta-learning (red), the agent struggles to cope as it faces new tasks every round, and its performance does not improve. ada-POMRL gradually improves as more tasks are seen whilst adaptation to learned task-similarity on-the-fly which is the primary cause of the performance gap in ada-POMRL and POMRL Importantly, no prior knowledge about the underlying task relatedness enables a more practical algorithm with the same theoretical guarantees (See Sec. 4). Recall that oracle prior knowledge is strong baseline as it corresponds to both known task relatedness and regularizer.
5.2 Meta-learning the underlying task relatedness enables longer planning horizons. [Q2.]
We run ada-POMRL for T 15 (with a x 0.01) as above and report planning losses for a range of values of guidance y factors. Results are averaged over 100 independent runs and displayed on Fig. 4(b). We observe
The variance of this distribution is controlled by its coefficient parameters a1:s: the larger they are, the smaller is the variance. More details on choices given in Appendix F.I. Dirichlet distributions with small variance satisfy the high--robabbiity version of our structural assumption 3 for max; 0;
divide the thcoretical rate by S ensure the max *Our priors are multivariate Dirichlet distribution in dimension
bounded by 1//m. See App. for implementation details.
We provide additional experiments with varying size of the state space Appendix Fig. F5.
9

---

Published in Transactions on Machine Learning Research (06/2023)
1.0
1.0
3.5-
y-
%
Frir Kocnletge if their Herts Leaming POMRI5O
3.5
Tw2
Optimal Gamma (+*)
Emipiccalyy aptima al gustancce
3.0
3.0
0.8
2.5
Pharning Logs
2.5
Plenning Less
doscsurt factor
Penning
2.0-
1.5
0.4
1.0
1.0
Planning Loss
0.2
0.5
0.3
0.00
0.0
10
0.0
0.1
02
03
0.4
0.5
0.6
0.7
0.8
0.9
1.0
0.0
9 10 15
Task (7)
Task
(a)
(b)
(c)
Figure 4: Planning with Online Meta-Learning. (a) Per-task planning loss of our algorithms POMRL and ada- ada-POMRL compared to an Oracle, and Without Mcta-lcarning baselines. All methods use a fixed 7 = Teval = 0.99. (b) ada-POMRL planning loss decrrases as more lasks are seen. Markers denote the y that minimizes the planning loss in respective tasks. Error bars show standard error. (c) ada-POMRL 's empirically optimal guidance discount factor (right y axis) depicts the effective planning horizon, i.e., one that minimizes the planning loss. Optimal " aka the effective planning horizon is larger with online meta-learning. Planning loss (left y axis) shows the minimum planning loss achieved by the agent in that round T. Results are averaged over 100 independent runs and error bars represent 1-standard deviation.
in Fig. 4(b) when the agent has seen fewer tasks T, an intermodiate value of the discount optimal, i.e., one that minimizes the lask-averaged planning loss (?* < 0.5). In the presence of strong underlying structure across tasks, the agent sees more tasks, the effective planning horizon (?* > 0.7) shifts to a larger value- one that is closer to the gamma used for evaluation (Neval = 0.99).
As we incorporate the knowledge of the underlying task distribution, i.e., meta-learned initialization of the dynamics model, we note that the adaptive mixing rate a₁ puts increasing amounts of weight on the shared knolllno Note that this conforms to the effect of increasing weight on the model initialization that we observed in Fig. 2. As predicted by theory, the per-task planning loss decreases as T grows and is minimized for progressively larger values of 7, meaning for longer planning horizons (See Fig. 4(c)). Tn addition, Appendix Fig. F4 depicts the effective planning horizon individually for ada-POMRL Oracle and without meta learning basclines.
5.3 POMRL and ada-POMRL perform consistently well for varying task-similarity. [Q3.]
We have thus far studied scenarios where the learner can exploit strong task relatedness, í.e., 2 0.01 < 1/(5ym) (for low data per task i.c., m = 5) is small and we now illustrate the other regimes discussed in Section 3.2. We show that our algorithms remain consistently good for all amounts of lask-similarity.
We let a vary cover the three regimes: o 0.01 corresponding fast convergence, o 0.025 in the intermediate regime (needs longer T), and 0.047 is the loosely structured case where we don't expect much meta-learning to help improve model accuracy. The small inset figures in Fig. 5 represent the task distribution in the simplex. In all cases, ada-POMRL estimates o online and we report the planning losses for a range of y's. Inspecting Fig. 5, we observe that while in the presence of closely related tasks (Fig. 5(a)) all methods perform well (except without meta-learning). As the underlying task relatedness decreases (for intermediate regime in Fig. 5(b)), both POMRL and ada-POMRL remain consistent their performance as compared the Oracle Prior Knowledge bascline. When the underlying tasks are looscly related (as in Fig. 5(c)), ada-POMRL and POMRL can stiill perform well in comparison other baselines.
Next, we report and discuss the planning loss plot for ada-POMRL for the three cases are shown in Figures ((d), 5(0), and 5(f) respectively. An intermediate value of task-similarity (Fig. 5(e)) still Icads to gains, albeit at a lower speed of convergence. In contrast, a large value of a = 0.047 indicates little relatedness across tasks resulting in minimal gains from meta-learning here as seen in Fig. 5(f). The learner struggles to learn a good initialization of the model dynamics as there no natural one. All planning loss curves remain U-shaped and overall higher with an intermediate optimal guidance 7 value ( 0.5). However, ada-POMRL does not do worse overall than the initial run T 1, meaning that while there not significant improvement, our method
10

---

Published in Transactions on Machine Learning Research (06/2023)
Strong Structure
Medium Structure Loosely Structured
10
bb)
1x0
Teld
24
1.0
(d)
(c)
(I)
Figure POMRL and ada-POMRL are robust to varying task-similarity for a small fixed amount of data m = 5 available al each round I T. small value of reflects the fact that lasks are closely related to each other and share good amount of structure whereas a much larger value indicates loosely related tasks (simplex plots illustrate the meta-distribution in dimension 2). In the former case, meta-learning the shared structure alongside good model initialization leads to most gains. In the latter, the learner struggles to cope with new unseen tasks which differ significantly. Error bars represent 1-standard deviation of uncertainty across 100 independent runs.
does not hurt performance loosely related tasks Recall that ada-POMRL has no apriori knowledge of the number of tasks (T), or the underlying task relatedness (o) i.e., adaptation on-the-fly
6 Adaptation of Planning Horizon γ
We now propose and empirically validate two heuristics desigu an adaptive schedule for 7 based on existing work (Sec. 6.1) and on our average regret upper bound (Sec. 6.2).
6.1 Schedule adapted from Dong et al. (2021) l = f'm, az,
(i, ot, T)]
Dong et al. (2021) study continuous, never-ending RL setting. They divide the time into growing phases (T))220 and tune discount factor % = 1/T.//5 We adapt their schedule to problem, where the time is already naturally divided into tasks: for each 2 O, we define the phase size Te and the corresponding %
SA L
To = m, Ti (11 )4 + (t " =1
T 1/5
efficient sample size
where L the maximum trajectory length. The size of cach Tr, t 2 1, controlled by an "efficient sample size" which includes combination of the current lask's samples and of the samples observed far, as used to construct estimator in POMRL
6.2 Using the upper bound to guide the schedule [n = min (1, 70 + 9}]
Having a second look at Theorem 2, we see that the r.h.s. is a function of y of the form
U U: 1- %eval
+ 7
+ C...T.S.A... (1-7)2²
TTehe theoretical bound may lead think that the average planning loss is higher due the introduced blas, but practice do observe that, which means our bound pessimistic the second order terms.
11

---

Published in Transactions on Machine Learning Research (06/2023)
where the first term is positive and monotonically decreasing on (0, Tevea) and the second term is positive and monotonically increasing on (0, 1). We simplify and scale this constant, keeping only problem-related terms: =- ( // + 1) + o² / + 1), which is of the order of the constant in equation 6. Optimizing y by using the function U with constant C' does not lead to principled analytical value strictly speaking because U is derived from an upper bound that may be loose and may not reflect the true shape of the loss w.r.t. % but we may use the resulting growth schedule to guide our choices online. In general, the existence of a strict minimum for U in (0, 1) is not always guaranteed: depending on the values of C = A....S.A.o: the function may be monotonic and the minimum may be on the edges. We give explicit rangos in the proposition below, proved in Appendix E.
Proposition 1. The eristence of a strict minimum in (0,1) is determined by C = Cm,T,S,AAob (which con be computed) us follows:
cf2
R
CC21
L-c I+C
otherwise, i.e if 1/2 < C<1
We use these values as a guide. Typically, when T' 1 and m is small, the multiplicative term C' is large and the bound is not really informative (concentration has not happened yet), and y should be small, potentially close to but not equal to zero. As a heuristic, we propose to simply offset y by an additional to such that the guidance discount factor is 7 min (1, 70 7), where "oo should be reasonably chosen by the practitioner to allow for some short-horizon planning at the beginning of the interaction. Empirically, To =E (0.25, 0.50) seems reasonable for our random MDP setting as it corresponds to the empirical minima on Fig 4(b).
Bes Floed
10F
10"
Best
Dynamic Rest
q wi
Ranning Loss
Reaniing ning Loo0
Hanning Lova
101
Number tasks (T)
Number tasts
Number (T)
(a)
(b)
(c)
Figure 6: Adapting the planning horizon during online meta-learning reduces planning loss. (a) Planning with onlinc-meta learning shows that all basclines outperform using a constant discount factor. (b) Zoomed in plot of average planning loss over the progression of tasks T shows competitive performance with the proposed schedule of y = f(m, at, o,, T" beating best-fixed more tasks are seen. The y schedule y y= min to + 5 using the upper bound as guidance beats the best-fixed and is very competitive to the dynamic-best bascline. (c) Using the upper bound to guide the schedule significantly outperforms Yeral and is shown for To E (0.25,0.50) Error bars depict 1-standard error for 600 independent runs.
6.3 Empirical Validation
Next, we empirically test the proposed schedules for adaptation of discount factors. We consider the setup described in Sec. 5 with 15 tasks in a 10-state, 2-action random MDP distribution of tasks with a x 0.01. In Fig. 6, we plot the planning loss obtained by POMRL with our schedules, a fixed Yevar and two strong baselines: best fixed which considers the best fixed value of discount over all tasks estimated in hindsight and dynamic best which considers the best choice if we had used the optimal 7 in each round as in Fig. 4(c). It is important to note that dynamic best is a lower bound that we cannot outperform.
We observe in Fig. 6(a) that Tevas results in very high loss, potentially corresponding to trying to plan too far ahcad despite model uncertainty. Upon inspecting Fig. 6(b), we observe that the proposed y f(m, on oe T) oblains similar performance to best faced and is within the significance range of the lower bound. Our second heuristic, 7 = min 70 + }} obtains similarly good performance, as seen in Fig. 6(b). Fig. 6(c) shows the effect of different values of "o in the prescribed range. These results provide evidence that is possible adapt the planning horizon as a function of the problem's is structure (meta-learned simk-similarrty) and sample sizes. Adapting the planning horizon online is an open problem and beyond the scope of our work.
12

---

Published in Transactions on Machine Learning Research (06/2023)
7 Discussion and Future Work
We presented connections between planning with inaccurate models and online meta-learning via a high- probability lask-averaged regret upper-bound on the planning loss that primarily depends on lask-similarity a as opposed to the entire search space Σ. Algorithmically, we demonstrate that the agent can use its experience in each task and across tasks to estimate both the transition model and the distribution over tasks. Mcta-learning the underlying task similarity and a good initialization of transition model across tasks enables longer planning horizons.
Beyond the tabular case: Function approximation is at the heart of practical RL natural question is how to extend our work to parametrized models. For linear MDPs, Müller & Pacchiano (2022) recently derived regret. bounds in the fixed-horizon setting for an algorithm using meta-regullrizees similar to ours. One question is whether this idea could be extended to infinite horizons and further to non-lincar, richer representations. Another, and perhaps deeper question, is around designing and evaluating better planning strategies. Should we revisit such line of work under the light of the planning loss rather than the regret? On- Off- Policy Meta-Learning without simulator: Realistic problem settings in RL involve using sequentially learnt policies to collect data instead of the simulator. One direction could be to extend our approach to model-based RL algorithms via meta-gradieni updates as in ARUBA MAML, and seek regret guarantees induced by our concentration results, Non-stationary meta-distribution Many real-world scenarios have (slow or sudden) drifts in the underlying distribution itself, c.g. weather. promising future direction to consider non-stationary environments where the optimal initialization varies over time.
Acknowledgments
The authors would like to thank Zheng Wen, Andras Gyorgy, and anonymous reviewers for valuable feedback on a draft of this paper, Sebastian Flennerhag, David Abel, and Benjamin Van Roy for insightful discussions during the course of this project. Vernade is funded by the Deutsche Forschungsgemminsccaat (DFG) under both the project 468806714 of the Emmy Nocther Programme and under Germany's 's Excellence Strategy EXC number 2064/1 Project number 390727645. CV also thanks the international Max Planck Research School for Intelligent Systems (IMPRS-IS).
References
Ron Amit. Ron Meir, and Kamil Ciosek. Discount factor regularizer in reinforcement learning. Tn International conference on machine learning, pp. 269-278. PMLR, 2020.
Dilip Arumugam, David Abel, Kavosh Asadi, Nakul Gopalan, Christopher Grimm, Jun Ki Lee, Lucas Lehnert, and Michael L Littman. Mitigating planner overfitting in model-basod reinforcement lcarning. arXiv preprinl 1rXi::1812.01199 2018.
Maria-Florina Balcan, Mikhail Khodak, and Amect Talwalkar. Provable guarantees for gradiont-based meta-learning. In International Conference on Machine Learning, pp. 424 424-4333 433. PMLR, 2019.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12:149-198, 2000.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-277 279,, 2013.
David Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, pp. 719-726, 1962.
Rich Caruana. Multitask learning. Machine learning, 28(1):41 75, 1997.
Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. PMLR, 2020.
In International Conference on Machine Learning, pp.
Nicolò Resa-Bianchi, Pierre Laforgue, Andrea Paudice, and Massimiliano Pontil. Multitask online mirror descent. Xii preprint
2021.
13

---

Published in Transactions on Machine Learning Research (06/2023)
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around common mean. Advances in Neural Information Processing Systems, 31, 2018.
Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-within--nlinee meta-learning. Advances in Neural Information Processing Systems, 32, 2019.
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou, Simple agent, complex environment: Efficient reinforce- ment learning with agent state. arXiv preprint NXiv:2002.05666 2021.
William Fedus, Carles Gelada, Yoshua Bengio, Marc G Bellemare, and Hugo Larochelle. Hyperbolic discounting and learning over multiple horizons. arXiv preprint NXw:1902200666 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pp. 1126 1135. PMLR, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In International Conference on Machine Learning, pp. 1920 1930. PMLR, 2019.
Sebastian Flennerhag, Yannick Schroecker, Tom Zahavy, Hado van Hasselt, David Silver, and Satinder Singh. Bootstrapped meta-lcarning. arXiv preprint arxiv:2109 10..0009904 2021.
Sebastian Flennerhag, Tom Zahavy, Brendan O'Donoghue, Hado van Hasselt, András György, and Satinder Singh. Optimistic vreta-gradients. In Sixth Workshop Meta- Learning at the Conference Newral Information Processing Systems, 2022.
Vincent François-Lavel, Guillaume Rabusseau, Joelle Pineau, Damien Ernst, and Raphael Fonteneau. On overfitting and asymptotic bias in batch reinforcement learning with partial observability. Journal of Artificial Intelligence Research, 65:1-30, 2019.
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon model accuracy. In Proccedings of the 2015 International Conference Autonomous Agents and Mulliogend Systems, pp. 1181 1189. International Foundation for Autonomous Agents and Multiagent Systems, 2015.
Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near-optimal planning in large markov decision processes. Machine learning, 49(2):193 208, 2002.
Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient- based meta-learning methods. arXiu preprint arXiv:1906 02717, 2019.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282 293. Springer, 2006.
Jelena. Luketina, Sebastian Flemnerhag, Yannick Schroecker, David Abel, Tom Zahavy, and Satinder Singh. Meta-gradients in non-stationary environments. In ICLR Workshop on Agent Learning in Open-Endedree Endedness, 2022.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level coutrol through deep reinforcement learning. Nature, 518(754)):529, 2015.
Robert Müller and Aldo Pacchiano. Meta learning mdps with linear transition models. In International Conference on Artificial Intelligence and Statistics, pp. 5928 5948. PMLR, 2022.
Junhyuk Oh, Matteo Hessel, Wojciech M Czarnecki, Zhongwen Xu, Hado van Hasselt, Satinder Singh, and David Silver. Discovering reinforcement. learning algorithms. arXie preprint arXin:2007.087%, 2020.
Marek Petrik and Bruno Scherrer. Biasing approximate dynamic programming with lower discount factor.
Advances in neural information processing systems, 21, 2008.
Joelle Pineau. The machine learning reproducibility checklist. arziv, 2019.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Juergen Schmidhuber and Rudolf Huber. Learning to generate artificial fovea trajectories for target detection. International Journal of Newral Systems, 2(00n022:125-13) 1991.
Terence Tao and Van Vu. Random matrices: universality of local spectral statistics of non-hermitian matrices. The Annals of Probobility, 43(2):782 874, 2015.
Sebastian Thrun and Lorien Pratt. Learning to learm: Introduction and overview. In Learning to learn, pp- 17. Springer, 1998.
Harm Van Seijen, Hado Van Hasselt, Shimon Whiteson, and Marco Wiering, A theoretical and empirical analysis of expected sarsa. In 2009 ieee symposium on adaptive dynamic programming and reinforcement learning, pp. 177 184. IEEE, 2009.
Zhongwen Xu, Hado van Hasselt, and David Silver. Meta-gradient reinforcement learning. orXiv preprint arvi 10511805..00 805.09801, 2018.
Tom Zahavy, Zhongwen Xu, Vivek Veeriah, Matteo Hessel, Junhyuk Oh, Hado P van Hasselt, David Silver, and Satinder Singh. A self-tuning actor-critic algorithm. Advances in neural information processing systems, 33, 2020.
15

---

Published in Transactions on Machine Learning Research (06/2023)
A Additional Related Work
Discount Factor Adaptation. For almost all real-world applications, RL agents operate in a much larger environment than the agent capacity in the context of both the computational and memory complexity (c.g. the internet). Inevitably, it becomes crucial to adapt the planning horizon over time as opposed to using a relatively longer planning horizon from the start (which can be both expensive and sub-optimal). This has been extensively studied in the context of planning with inaccurate models in reinforcement learning (Jiang et al., 2015; Arumugam et al., 2018).
Dong et al. (2021) introduced a schedule for that we take inspiration from in Section 6.1. They consider a 'never-ending RL' problem in the infinite-hrizon, average-regrel setting in which the true horizon is 1, but show that adopting a different smaller discount. value proportional to the time in the agent's life results in significant gains. Their focus and contributions are different from ours as they are interested in asymptotic rates, but we believe the connection between our findings is an interesting avenue for future research.
Meta-Learning and Meta-RL, learning-to-learr has shown tremendous success in online discovery of different aspects of an RL algorithm, ranging from hyper-parameters (Xu et al., 2018) to complete objective functions (Oh et al., 2020). In recent years, many deep RL agents (Fedus et al., 2019; Zahavy et al., 2020) have gradually used higher discounts moving away from the traditional approach of using a fixed discount. factor. However, to the best of our knowledge, existing works do not provide a formal understanding of why this is helping the agents in better performance, especially across varied tasks. Our analysis motivated by the aforementioned empirical success of adapting the discount factor. While there has been significant progress in genta-leaniing-nsppinn Flennerhag et al., 2021), they are largely focused empirical analysis with lot or room for in-depth insights about the source of underlying gains.
meta-gradients techniques in RL (Xu et al., 2018; Zahavy et al., 2020;
B -losed-form solution of the regularized least squares
We note that each P should be understood as (s'.
ve(PIA) = - Σ (xi - PPP h))
1=1
Σxx
V((PIh) =0 + P(I+ A)
Ah.
m X (s 1+ m 1+
Σ,
(9)
Σ'x x'
A
aa + (1 (1-a)
where a 1+ X
(10)
m
Derivation of Mixing Rate a;: To choose at, want to minimize the MSE of the final estimator.
Exap (pe (pipp) pt) p = Exur (ashi + (1 1 ar) -1 2
= =xxpp (ar(h: - pP) + (1 - an) - -pt))²
= agg(h- - pdpa + - 0r) ((p) - pti)² -p')-
where the cross term 2a) - P1) az Exx [ pp] = 0 since E[P²] = pt. This is the classic bias-variance docomposition of an estimator and we see that the choice of ht plays role as well as the variance of pL which is upper bounded by 1/m (because each X is bounded in (0, 1)). For instance, for the choice h = P2, by our structural assumption 3 we get:
Ex-p (pr (p'-pt)² sazo² +(1 (1 a)
16

---

Published in Transactions on Machine Learning Research (06/2023)
and we minimize this upper bound in to obtain the mixing coefficient with smallest MSE: a² g-m+1> equivalently X = = Recall this the within-task estimator's variance where we consider the true Po.
In practice, however, we meta-learn the prior, so for t >>> 1, h4 = po.t Σ Intuitively, as m and grow large, pott + po and we retrieve the result above (we show this formally to prove Eq. 20 the proof of our main theorem). To obtain a simple expression for die, we minimize the 'meta-MSE" of our estimator:
Ep (Pt-Pt) pp) 2
= a2E Ex (h+ - pt) + (1 BP ((P) p!))
2
1-1
S Bp
1
pi
pe p pt
pM)
(1 - a²)
(1--a))2
m
j=1
= (1-aa) oz) 1
S
m
where in the last inequality, upper bounded the variance of 1 - pl (the "denoised" po.t) by o²/t since each pt is bounded in - o, p + o] by our struetural assumption. Minimizing that last upper bound in oe leads to az (03)0-1/0)44
a", when - oc. This means that the uncertainty on the prior implies that its weight in the estimator is smaller, but uvllt converges al a fast rate to the optimal value (when the exact optimal prior is known). This inequality holds with probability 8 because we use the concentration of ao (see proof of Theorem 17 below)
C Online Estimation
Online Estimation of Prior. At each task, the learner gets m interactions per state-action pair. At task 1, learner can compute the prior based the samples far, i.e.:
1 X13==1
p
m
At subsequent tasks,
2m
Xih
1 1/
1 ii=
Xi}
+m=++ Xi}
2m
(s=2(s'|s,
+
2m
2
m
m
1
pt=1
(s)1s,
12 Xi}
2
m
Similarly,
133m Xi)t=1:3
2m 1
X 1 + (Σ 3m
(Zi=2m11 Xi)==
pt= (s'(s, a)
i=
3m
3m
2
2
2m
X.)rm112 1:2
2 Xittm
3m
3
2m
1 (1111) (ssssssss)))) + -i=(t-1mma X1
tm
P
m
Therefore,
F bm X; (i=
( (1 (1- (10pa))((11111
(1)
(11)
m
Online Estimation of Variance. Similarly, we can derive the online estimate of the variance:
(6.)*- = (6)))-1 + (Xmt p(- P.) (0
(12)
t
17

---

Published in Transactions on Machine Learning Research (06/2023)
Since the above method is mumerically unstable, will employ Welford's online algorithm for variance estimate.
D Concentration bounds and Proof of Theorem
D.1 Proof of Theorem
We begin the proof by decomposing each term of the loss:
Lemma 1. For lask & denoted by M, and ils eslimate denoled by M, Vs E E,,,
V ppl praver (5) - Vipt Messs
(8) = Vpr
ppptTean (s) - ptnn Mress
ppt mevel
(s) +
(s) V
Sperr pe resss
(s)
p proet
pt,y
We are going bound each term separately. The term (Ai) corresponds the bias constant due to using y instead of Yeval and was already bounded by Jiang al. (2015): Lemma 2. Jiang et al. (2015) For any MDP M with rewards in [0, Rman], VT : S + A and S Tewel,
Yevai -
V Vp Freas Vp (1 (1-9 Yevat) (1 7)) Rmax
(13)
Yomas (1-ram (1 (1-1) Rmax and notice that E. A,/T= so that bounds the first part of the We denote C(7) average loss.
To bound the second term Bi, we first use Lemma (Equation 18) Jiang et al. (2015) upper bound
V
pt,y
mant (s) -
s 2
max rEll
(V oo (s) - V (s)
(14)
S 2 max aES, selle
1p
Aotooaa (8,a) - Q ape
per (8,
(15)
Using Lemma from Jiang al. (2015) and noticing that in our setting we do not estimate R R R, (7,,11800 a) = R(s, a) + (PP(ss, VTe,,) and 07p,, (s, R(s,a) + (P'(s, a,;). VT ) have
1p (8, a) 2 pm (s, a)) S (1 71 sES.aEA, rella,
(P, - 7 (8. (,, (P',a),)))) v
max sES,aEA, xEllR,;
max
(16)
Notice that we are comparing the value functions of two different MDPs which is non-trivial and we leverage the result of Jiang et al. (2015). We refer the reader to the proof of Lemma therein for intermediate steps. Now summing over tasks, we have
1
VP V
max SES,NEA, TElRR.T
T
(1 1-77
1 T
2y
Σ
(P(ssaa:)PP'(s,.)))
max SES SES.EAA
[1 7)
T
t=l
rEllan
T
2R Rmax
Σ
Pp -
< (1 7) T
max sES
1=1 d'E(S) rElla.
2 2m 5
('(s,a,'') - (ss
max
(1 2-2
s,8' ESAEAA
18

---

Published in Transactions on Machine Learning Research (06/2023)
where upper-bounded the value function by Rmax/(1 - 7) and one sum over S by S x max,'es ... Note that this step differs from Jiang et al. (2015) and allows us to boil down to an average (worst-case) estimation error of the transition model. We finally upper bound the r.h.s using Theorem stated and proved below.
Remark 2. In Jiang et al. (2015), the argument is slightly more direct and involves directly controlling the deviations of the scalar random variables R(s.a) +)(")ss"s V..) centered at Qpe,,(s a). This approach is followed by taking a union bound over the policy space RR and results in a factor RR,,) under the square root. We could have followed this approach and obtoined simälar result but we made the alternative choice above we believe it is informative. In our case, this factor is replaced (and upper bounded) by the extra S term. As result, the size of the policy class, which is function of y and should play a role in the bound. In turn, and al the price of this extra looseness, we get slightly more "exploitable" bound (see our heuristic for a gamma schedule in Section 6). It is easy and straightforward to adapt our concentration bound below to directly bound R(s, a) + 7 a,;); V p.,.) Op- a) as in Jiang et al. (2015), and one would oblain a similar bound as Eq. equation without the factor S, but with extra log.HI...))
,,,,), arguing that it is bounded and
lose the direct dependence
D.2 Concentration of the model estimator
To avoid clutter in the notation of this section, we drop the (s, a, 8') everywhere, as we did Appendix B above. All definitions of P and Po are as stated in the latter section.
Theorem 1. with probability 6:
log( 67 log( TS2A (02 + Elogg 672
log( 37
max pr p*1 S 1 8,0,5'
2a
72m + 1
T
T
02m
Σ Elog( 37S2
(17)
202m + 1
2m
For any E [7], 8, 8, and n E Nn,, define pt.* p====a oo + (1 - Pt the optimally regularized estimator (using the true unknown po for each t). We have
pe pd| S pt p4.11 pp 10--Pp P.
S ar poit
po
+
az) pt
pt
a p Pt
(18)
(1)
(B)
<2-bb assum.
Bounding Term A
Substituting the estimator P. ai Σn m
X, + (1 ar)
1-1
t-1
A A 0t
pp..
pJ
Σ
P3 - Pol
1-1
j=l
j=1
pbL
Σ
Pd
1
Σ
P3
Pol
2 +1
j=1
j=1
(A))
Aa
where an is simply upper bounded by its initial value न and we introduced the denoised (expected)
average - p pt- po.t Indeed, by assumption, Ep-p E pi po and the variance of
19

---

Published in Transactions on Machine Learning Research (06/2023)
this estimator is bounded by /²/(t- 1) by our structure assumption. This allows to naturally bound A using Hoeffding's inequality for bounded random variables: with probability at least. 1 16/3.
log (6522
max Ag S o 8,0,8'
(19)
T
We now bound A1
A1
Σ P/. - P))
We note here that the first term in A1 is indeed martingale M, --p=1 Zjj where Zj =P: Pi such that each increment is bounded with high probability: for each j. |2 S cj w-p 1 E where Gj Moreover, the differences Z Zj+zl are also bounded with high probability:
Σ log(
672 5
Zj Zz+1l S |pj ppt1 + IPj pitt 20 + 2e, D, =2 o v log( log( Vooo
v m
Then by (Tao & Vu, 2015, Prop. 34), for any >> O,
Mr
P
Σ ==1
D3) s 2 2exp( (exp(_2e2) + Σ j=1
1
6
Choosing V 2 log( 12T), we get
V log! ar2 log(
P
P
Py 2
(o
Vm
62
8
5
t
T
6T
6T
3T
j=l
With union bound as before, we get that with probability at least 1 8/33
A1 < log( 8
log( T52
(o²
logg ( mT2)
(20)
T
because (a (a+ +
/
Σ 132002
By combining equation 20 and equation 19, we gel:
1
log(
GT
log(
TS2A
102
log" uZ2
log(352 A AT/8)
max po.t pol ²2m + 8,0,8!
+ o
(21)
T
T
Bounding Term B
Term is simply the concentration of the average of bounded variables pr. = = E, bounded by So by Hooffding's incquality, and a union bound, with probability least 8/4
X1, whose variance is
Σ log 52
max pt pt 6,0,8'
2m
20

---

Published in Transactions on Machine Learning Research (06/2023)
To bound term B, it remains to upper bound - at for all E [T]:
0² + 7
o²m
1 - 0²(1 m +
20 +
We get that with probability 1 - 6-/3
S σ 0mm
Σ (3T
max s,a,s'
(22)
20
2m
Combining all bounds
To conclude, combine the bounds on the terms in equation 18, replacing with equation 21, equation 22, and with a union bound, we get that with probability 1 0,
(Voes 62)) log( TS2A (0² + Elog2 log(
1
log (25335AT///
max 1p p²1 6,0,8'
2a
0²m +
T
T
0 a2m
3 Log (37 S2 A7/))
(23)
2g 2m2m
2m
Discussion
The bound has 4 main terms respectively in σlV 7. 0( ( and σlv 1,,, all scaled by some factor
depending on 2² and m. A first remark is that when m is large and T = 1, the last part in Ö(V 1n dominates - 1, while the coefficient of the first two terms goes 0 fast (in 1/(o2m)).
due the factor slm
p'm
E Proof of Proposition 1
We study the function U defined by
1 γ
U: -evel Veval
+ C...T..AA... (1 (1-7)2²
where 7eval fixed constant and = C,,..S.A.o.66 seen as a parameter whose value controls the general 'shape' of the function. We differentiate with respect to y;
dU -O(y + (1-7)
(1 71-
We see that the sign of the derivative affected by the value of the parameter C:
Vy E (0, 1), - -C(+ + (1 (1-7) 0 then U monotonically decreasing on (0, 1) and the minimum reached for 7 = 1,
Vy (0. 1), -C(r + (1- -2 -C - C 1/2.
Similarly, if C' is really large, U may be monotonically increasing on (0, 1):
Vy (0, 1), C(y+
+ (1-7)
2 1;
Finally, if C (1/2,2), the minimum exists inside (0, 1) and is reached for
1- C
-O7-C - - 7= 1+C
21

---

Published in Transactions on Machine Learning Research (06/2023)
F Experiments:
Implementation Details, Ablations & Additional Results
F.1 Implementation details
We consider Dirichlet distribution of tasks such that all tasks E [T', Ps are centered some fixed mean Pa E A shown in Figure F1. The mean of the task distribution p is chosen sampled random MDP and variance of this distribution is determined such that || P. lloo I a < 1. Next, we compute the variance of this distribution 0, (1=-ū;)
00+1 where a; and Σ,
125 002, 15,000 15.020)
Figure F1: Dirichlet Task Distribution for S = 3 states, with Dir(a) where [15, 15, 15]. resulting in our task-similarity measure approximately to be = 0.0129.
F.2 Ablations
We also run ablations with Aggregating(a = 1), a naive baseline that simply ignores the meta-RL structure and just plans assuming there is a single task. We observe Fig. F2 the aggregating baseline works at-par with our method POMRL which is intuitive when the tasks are strongly related each other in this case. However, the underlying task structure decreases, we note that Aggregating(c- =1 as though it is single task is problematic and suffers from non-vanishing bias due to which for cach new task there is average an error which does not go to zero. More importantly, the Aggregating(a= = baseline cannot have the same guarantees as POMRL and ada-POMRL.
Strong Structure
Medium Structure
Loosely Structured
4.0
4.0
3.5
Oracie Prior Kncwtadge
7 0.00 Tued
Grodi froe Knoeleziee
ads PO981
35.
Crudks Frior edge
Without Hata Leaming
3.0
Negpegprnng
Agpregstiggoe..
3.0
PONBL)))
Plnniing Lacs
2.5
Menninn Loss
2.5
Planning
2.0
2.0
1.5
1.5
0.5
Task
(a)
(b)
(c)
Figure F2: Ablations for Efficacy of POMRL and ada-POMRL for varying task-similarity. depicts the effect of the task-similarity parameter for a small fixed amount of data m 5 available each round. We another baseline called Aggregating (orange) that simply ignores the meta-RL structure and acts if it is all one single task. In the presence of strong structure, meta-learning the shared structure alongside good model initialization leads to most gains and even naively aggregating the tasks transitions might seem to work well. However, such a naive method not reliable as the underlying task similarity decreases the learner struggles to cope with new unseen tasks which differ significantly and the planning loss docsn't. improve. Error bars represent 1-standard deviation uncertainty across 100 independent runs.
22

---

Published in Transactions on Machine Learning Research (06/2023)
1003 Te30
2.0
2.
1.5
14
1.0
03
0.5
002 233 220
050 0220.20000
2320.2
983 0.0 020 1o 0
Mi 10 30..00000000...1. 300.00333000 303330334
(a) m = 5,7 5
(b) m = 20, =3
(c) m 5, 30
Figure F3: Effect of m and T on Average Regret Upper Bound on Planning: for a fixed value of task similarity o, depends on the number of samples per task m and the number of tasks T. (a) For m T, smaller loss is obtained with very small discount factor. This implies that with lot of uncertainty it is not. interesting to plan far too ahead, (b) For m >> T, each task has enough samples to inform itself resulting in slightly larger effective discount factors. Not lot is gained in this scenario from meta-learning, (c) m < T is the most interesting case as samples seen in each individual task are very limited due to small m. However, the number tasks are much more resulting in huge gains from leveraging shared structure across tasks.
F.3 Additional Experiments
We examine more properties ada-POMRL namely Effect of m, and T on Planning Loss in Fig. F3, Individual Baseline's Performance Fig. F4, and Varying State Space [S], m, and T in Fig. F5.
1.0
03
08b
181
(a) ada-POMRL
(b) Oracle Prior Knowledge (c) Without Meta-Learning
Figure F4: Planning with Online Meta Learning Baselines. (a) ada-POMRL. Meta updates include learning Po: 0, a as a function of tasks. (b) Oracle Prior Knowledge considers the optimal a, true mean of the task distribution P. and actual underlying task similarity as known apriori, (c) Without Mernnng estimates the transition kernel in each round T without any meta-learning, All baselines are obtained with T = 15 tasks and 5 samples per task.
F.4 Reproducibility
We follow the reprodueibility checklist by Pincau (2019) to ensure this research is reproducible. For all algorithms presented, we include clear description of the algorithm and source code is included with these supplementary materials. For any theoretical claims, we include; a statement of the result, a clear explanation of any assumptions, and complete proofs of any claims. For all figures that present empirical results, we include: the empirical details of how the experiments were run, a clear definition of the specific measure statistics used to report results, and description of results with the standard error in all cases.
F.5 Computing and Open source libraries.
All experiments were conducted using Google Colab instances
Thttps:/ http:////lolaaab..eececcccee wwg.ghhheeeeeeeccccoooo..o.om
23

---

Published in Transactions on Machine Learning Research (06/2023)
|S| = 20
m T =5
20, T
m 5, 30
2.0
1.0
0.
0.
|S| 30
01 02
03
0A
03
58 07 05
00
01
05
04
05 0b 07 03
900 03 122 03
05 99 36
(d) T
(e) 20, 7 =
5,
15
Figure F5: Varying the size of state-space S, number of samples per task m, and number of tasks T, on Task-averaged Regret Upper Bound on Planning: for fixed value of task similarity a, We note that despite larger state-space we observe the same effect i.e. (a,d,g) For m = T, smaller loss is obtained with very small discount factor i.e. a lot of uncertainty and inability to plan far too ahead, (b,c.h) inform itself resulting slightly larger effective discount.
For m >> T, each task has enough samples factors. Not lot is gained this scenario from meta-learning. (c,f,i) m & T the most interesting case samples seen in each individual task very limited due to small m. Meta-learning has most significant. gains in this case by leveraging the structure across tasks. Results are averaged over 20 independent runs and error bars represent 1-standard deviation.
24


Reviews:
[{"review_id": "DqI3qcN8AA", "reviewer": "Reviewer_C8FM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is well-written and clear. The paper presents its contributions clearly and does a nice job in situating the work in literature. The problem addressed is important and fundamental with a large set of possible real-world applications (though it would be nice for the authors to discuss some of them, preferably right in the introduction where they are motivating the work).\n\nWeaknesses: I think the paper has some very stringent assumptions that reduces the scope of the work. Assumptions of stationary task distribution, similarity of tasks, the tabular setting, and assumptions of known rewards (in several places) are very limiting. The authors could have provided some detailed discussions regarding relaxing some of these assumptions at-least empirically. Nonetheless, I agree that this is a novel theoretical effort and such limiting assumptions may be required in establishing the problem framework and providing the first line of results. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers an environment where a reinforcement learning (RL) agent faces a sequence of related tasks. The objective is to use an online meta-learning approach that learns and exploits the underlying similarities across tasks to effectively adapt to every new task (through planning in a model-based approach). The paper proposes a practical algorithm for the stated objective and theoretically provides a task-averaged regret upper-bound on the planning loss. This bound shows that the regret decreases with the number of tasks and the associated task similarity. Further, the paper provides two heuristics for selecting slowly increasing discount factors, in this online meta-learning approach. Empirically the paper demonstrates that meta-learning an initialization of the transition model and a distribution (underlying similarity) across tasks leads to improved accuracy for planning in each new (unseen) task, and planning ahead (i.e., planning using long horizons).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I only have some minor comments in the paper. I encourage the authors to incorporate as many of these as possible. I would like to recommend acceptance of the paper and the requested changes here are not critical to changing my recommendation.\n\n1) Assumptions: The paper rolls in several assumptions into the text at various places, which hurts the flow of reading and causes some misunderstandings. For example, in Section 3.2, the authors state that \"we shall assume throughout that the rewards are known\", and in Section 2, \"we assume that we have access to a simulator\". I recommend that the authors list their set of assumptions formally early on and refer back to these assumptions in the appropriate places in the text.\n\n2)  Throughout the paper it would be useful to have some real-world examples that motivate the problem setting. I think there can be some immediate applications to domains such as robotics. The authors can use such examples to provide intuition in several places in the paper. \n\n3) I had trouble understanding Equation 4 and connecting back to the text around it. I would encourage the authors to explain each term and variable used in this equation precisely along with the necessary intuitions.\n\n4) In several places, the authors use the term \"task similarity structure\" or \"underlying structure\". The meaning of \"structure\" here was unclear to me. It would be helpful to define/introduce this term early on (or during the first usage) in the paper.\n\n5) In Figure 1, I did not get the meaning of the (blue) circles and arrows in the left-most figure. It will be helpful for the authors to clarify that in the description of this figure. \n\n6) Minors: Section 2: consequently to define -> consequently we define; Section 4: comes comes -> comes; Section 4: will gives a -> will give a; Section 5: several places: dynamics model -> the dynamics model; section 5.1: estimator -> an estimator.\n\n", "broader_impact_concerns": "No concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2MOU3Sk9mq", "reviewer": "Reviewer_7X2a", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the paper is well-executed. The write-up is very clean, the structure is correct, and the research questions are well-stated\n- the problem studied in the paper, planning in a meta-reinforcement learning setting, is of significant\n- Conceptualization and formalization of the problem, even if unsurprising, is valuable for the community\n- The provided regret bounds further solidify the theoretical contribution\n- The experimental part nicely illustrates the theoretical part\n\nWeaknesses:\n- The whole analysis is concerned with the tabular setting, and then even is mostly useful, then the 'size' of the environment is modest. This makes it hard to assess what is the long-term significance. I understand that providing any theory for the case when approximators are used is probably very hard. Nevertheless, even a simple empirical evaluation would be of value.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper develops model-based methods in meta-reinforcement learning. Its contributions are fourfold:\n- they conceptualize and formalize the problem of planning under model uncertainty \n- they prove regret bounds in the above formalization\n- they propose an algorithm to solve the meta-reinforcement learning setting. In particular, they present versions that learn the task-similarity parameter and the planning horizon\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Discuss the expected impact of the results on the field. For example, running empirical evaluations in a non-tabular setting (even simplified) might, in my opinion, significantly strengthen the paper.\n", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Rdp3JvX8am", "reviewer": "Reviewer_pog9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths. \n\nThe paper is well written and clearly positioned with respect to the state of the art. The topic addressed is relevant to the community and the results introduced in the paper appear to be correct.\n\nWeaknesses. \n\nSome of the assumptions in the paper could use some stronger motivation. Not saying that they are unreasonable, but it would help to clarify their need to the reader and how to overcome them in practice (i.e., assumption of known rewards, access to simulator of transitions, etc).\n\nNumerical evaluations are provided for synthetic data. It would be interesting to see the method applied to real datasets instead of a synthetic experiment.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors study online meta-learning. Specifically, they study a problem in which an agent sequentially tackles related tasks. The agent uses data acquired from previous tasks to learn an initial guess of the current task model. The proposed analysis is inspired by the Average Regret-Upper-Bound Analysis (ARUBA) framework, adapted to the meta-learning scenario. Regret upper bounds are derived and numerical results on a synthetic experiment are provided. Source code for the experimental evaluation is provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I find the paper to be of reasonable quality. I'd suggest some of the modifications mentioned in \"Weaknesses\", but overall I found this work to be well-written and worthy of publication.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new model-based meta-learning technique for RL.  While the technique is only demonstrated in the context of synthetic tabular domains, it lends itself to a strong theoretical analysis.  More specifically, regret bounds are provided under syutable assumption.  The applicability of those assumptions was questioned by the reviewers, but they are common for a theoretical analysis.  Overall, this work makes several important theoretical contributions that advance the state of the art of meta RL and our understanding of the various factors that influence performance in meta-RL.  
Decision: Accept (poster)