Minimum Description Length Control
Authors: Ted Moskovitz
Ta-Chu Kao
Maneesh Sahani
Matthew Botvinick
Venue: ICLR 2023 poster (2023)
Keywords: multitask reinforcement learning
RL
reinforcement learning
MDL

Abstract: We propose a novel framework for multitask reinforcement learning based on the minimum description length (MDL) principle. In this approach, which we term MDL-control (MDL-C), the agent learns the common structure among the tasks with which it is faced and then distills it into a simpler representation which facilitates faster convergence and generalization to new tasks. In doing so, MDL-C naturally balances adaptation to each task with epistemic uncertainty about the task distribution. We motivate MDL-C via formal connections between the MDL principle and Bayesian inference, derive theoretical performance guarantees, and demonstrate MDL-C's empirical effectiveness on both discrete and high-dimensional continuous control tasks.

Published as a conference paper at ICLR 2023
MINIMUM DESCRIPTION LENGTH CONTROL
Ted Moskovitz!" Callin K Maneesh Sahani', Matthew M. Botvinick!2
1. Gatsby Unit, University College London DeepMind
3. Facebook Reality Labs
*Correspondence: www.eaaaaaa..lla........
ABSTRACT
We propose novel framework for multitask reinforcement learning based on the minimum description length (MDL) principle. In this approach, which we term MDL-control (MDL-C), the agent learns the common structure among the tasks with which is faced and then distills it into a simpler representation which facilitates faster convergence and generalization to new tasks. In doing so, MDL- C naturally balances adaptation to each task with epistemic uncertainty about the task distribution. We motivate MDL-C via formal connections between the MDL principle and Bayesian inference, derive theoretical performance guarantees, and demonstrate MDL-C's empirical effectiveness on both discrete and high- dimensional continuous control tasks.
INTRODUCTION
In order to learn efficiently in a complex world with multiple rapidly changing objectives, both animals and machines must leverage past experience. This is a challenging task, processing and storing all relevant information computationally infeasible. How can an intelligent agent address this problem? We hypothesize that one route may lie in the dual process theory of cognition, longstanding framework in cognitive psychology introduced by William James (James, 1890) which lies at the heart of many dichotomies in both cognitive science and machine learning. Examples include goal-directed versus habitual behavior (Graybiel, 2008), model-based versus model-free reinforcement learning (Daw et al., 2011; I; Sutton and Barto, 2018), and "System 1" versus "System 2" thinking (Kahneman, 2011). In each of these paradigms, a complex, "control" process trades off with simple, "default" process to guide actions. Why has this been such a successful and enduring conceptual motif? Our hypothesis is that default processes often serve to distill common structure from the tasks consistently faced by animals and agents, facilitating generalization and rapid learning on new objectives. For example, drivers can automatically traverse commonly traveled roads en route to new destinations, and chefs quickly learn new dishes on the back well-honed fundamental techniques. Importantly, even intricate tasks can become automatic, if repeated often enough (e.g., the combination of fine motor commands required to swing a tennis racket): the default process must be sufficiently expressive learn common behaviors, regardless of their complexity. reality, most processes likely lie on continuum between simplicity and complexity.
In reinforcement learning (RL; Sutton and Barto, 2018), improving sample efficiency on new tasks is crucial to the developement of general agents which can learn effectively in the real world (Botvinick al., 2015; Kirk et al., 2021). Intriguingly, one family of approaches which have shown promise in this regard are regularized policy optimization algorithmss in which a goal-specific control policy is paired with simple yet general default policy to facilitate learning across multiple tasks (Teh et al., 2017; Galashov et al., 2019; Goyal et al., 2020; 2019; Moskovitz et al., 2022a). One difficulty in algorithm design, however, is how much or how little to constrain the default policy, and in what way. An overly simple default policy will fail to identify and exploit commonalities among tasks, while complex model may overfit to a single task and fail to generalize. Most approaches manually specify an asymmetry between the control and default policies, such hiding input information (Galashov et al., 2019) or constraining the model class (Lai and Gershman, 2021). Ideally, we'd like an adaptive approach that learns the appropriate degree of complexity via experience.

---

Published as a conference paper at ICLR 2023
The minimum description length principle (MDL; Rissanen, 1978), which in general holds that one should prefer the simplest model that accurately fits the data, offers guiding framework for algorithm design that does just that, enabling the default policy to optimally trade off between adapting to information from new tasks and maintaining simplicity. Inspired by dual process theory and the MILL principle, we propose MDL-control (MDL-C, pronounced "middle-cee"), principled RPO framework for multitask RL. In Section 2, we formally introduce multitask RL and describe RPO approaches within this setting. In Section 3. we describe MDL and the variational coding framework, from which we extract MDL-C and derive its formal performance characteristics. In Section 5, we demonstrate its empirical effectiveness in both discrete and continuous control settings. Finally, we discuss related ideas from the the literature (Section 6) and conclude (Section 7).
2 REINFORCEMENT LEARNING PRELIMINARIES
The single-task setting We model a task as a Markov decision process (MDP; Puterman, 2010)
M = A, 7; where S, A are state and action spaces, respectively, P S x A + P(8) is the state transition distribution, r : S x A - [0. 1] is reward function, E [0. 1) is a discount factor, and p E P(S) is the starting state distribution. PP.) is the space of probability distributions defined over a given space. The agent takes actions using a policy π S - P(AA). In large or continuous domains, the policy is often parameterized: π - Re, 0 E O, where θ IR represents particular model class with d parameters. In conjunction with the transition dynamics, the policy induces a distribution over trajectories T (S), ah Tz 8 (T). In a single task, the agent seeks to maximize its value V = Er-pro R(T), where R(T) = Enzo 7 (s an) is called the return. We denote by dā the state-occupancy distribution induced by policy æ with starting state distribution pt (s) = E,(1 - 7) Σn 7 Pr(s = s|8o).
Multiple tasks There are a number of frameworks for multitask RL in the literature (Yu et al., 2019; Zahavy et al., 2021; Finn et al., 2017; Brunskill and Li, 2013). For a more detailed discussion, see Appendix Section B. In this paper, we focus primarily on what we term the sequential and parallel task settings. The objective in each case is to maximize average reward across tasks, equivalent to minimizing cumulative regret over the agent's 'lifetime." More specifically, we assume (possibly infinite) set of tasks (MDPs) M = {M} presented to the agent by sampling from some task distribution P.M E (PM).. In the sequential task setting (Moskovitz et al., 2022a; Pacchiano al., 2022), tasks (MDPs) are sampled one at a time from P.M. with the agent training on each until convergence. In the parallel task training (Yu et al., 2019), a new MDP is sampled from P.M at the start of every episode and is associated with particular input feature g E that indicates to the agent which task has been sampled.
Regularized Policy Optimization One common approach which improves performance is regu- larized policy optimization (RPO; Schulman et al., 2017; 2018; 8; Levine, 2018; Agarwal et al., 2020; Pacchiano et al., 2020; Tirumala et al., 2020; Abdolmaleki et al., 2018). In RPO, a convex regular- ization term (20)) is added to the objective: (O) V XQ()). In the single-task setting, the regularization term is often used to approximate trust region (Schulman et al., 2015), proximal point (Schulman et al., 2017), or natural gradient (Kakade, 2002; Pacchiano et al., 2020; Moskovitz et al.. 2020) optimization, or to prevent premature convergence to local maxima (Haarnoja et al., 2018; Lee et al., 2018). In multitask settings, the regularization term for RPO typically takes the form of a divergence measure penalizing the policy responsible for taking actions no. which we'll refer as the control policy, for deviating from some default policy Two which is intended encode generally useful behavior for some family of tasks (Tch et al., 2017; Galashov et al., 2019; Goyal et al., 2019; 2020; Moskovitz et al., 2022a). By capturing behavior which on average useful across tasks, Tw can provide a form of beneficial supervision to hoe when obtaining reward is challenging, either because By has been insufficiently trained or rewards are sparse.
THE MINIMUM DESCRIPTION LENGTH PRINCIPLE
General principle Storing all environment interactions across multiple tasks is computationally infeasible, so multitask RPO algorithms offer a compressed representation in the form of a default policy. However, the type of information which is compressed (and that which is lost) is often
2

---

Published as a conference paper at ICLR 2023
hard-coded priori. Preferably, we'd like approach which can distill structural regularities among tasks without needing to know what they are beforehand. The minimum description length (MDL) framework offers a principled approach to this problem. So-called "ideal" MDL seeks to find the shortest solution written in general-purpos. programming language' which accurately reproduces the data-an idea rooted in the concept of Kolmogorov complexity (Li and Vitnyi, 2008). Given the known impossibility of computing Kolmogorov complexity for all but the simplest cases, a more practical MDL approach instead prescribes selecting the hypothesis H² from some hypothesis class H which minimizes the two-part code H* argmingew L(D|H) + L(H,, where L(D) H) is the number of bits required to encode the data given the hypothesis and L(H) is the number of bits needed to encode the hypothesis itself. There are variety of so-called universal coding schemes which can be used to model these quantities.
Variational code One popular encoding scheme is the variational code (Blier and Ollivier, 2018; Hinton and Van Camp, 1993; Honkela and Valpola, 2004):
L (D) Ea-~ |- log pe (D) + (L(x()),
(3.1)
(11"
where the hypothesis class is of set of parametric models H (D) 0 E θ). The model parameters are random variables with prior distribution p(0) and v(0) is any distribution over O. Minimizing (D) with respect to y is equivalent to performing variational inference, maximizing a lower-bound to the data log-likelihool logp(D) = log p(()) p(0)pp(( (D))d0 2 - -L (D). Roughly speaking, MDL encourages the choice of "simple" models when limited data are available (Grunwald, 2004). In the variational coding scheme, simplicity is enforced via the choice of prior.
Snnduiiy priors and variational dropout Sparsity-inducing priors can be used to im- prove the compression rate within the variational coding scheme, as they encourage the model to prune out parameters that do not contribute to reducing L (D) (0). Many sparsity-inducing pri- ors belong to the family of scale mixtures of normal distributions (Andrews and Mallows, 1974): 2 ~ p()), ~ p(8]2) N(w; 0, ) where p(z) defines a distribution over the variance 2². Com- mon choices of p(z) include the Jeffreys prior p(2) x | (Jeffreys, 1946), the inverse- inverse-Gamma distribution, and the half-Cauchy distribution (Polson and Scott, 2012; Gelman, 2006). Such priors have deep connections to MDL. theory. For example, the Jeffreys prior in conjunction with an exponential family likelihood is asymptotically identical to the normalized maximum likelihood estimator, perhaps the most fundamental 'MDL' estimator (Grünwald and Roos, 2019). Variational dropout (VDO) is an effective algorithm for minimizing Equation (3.1) for these sparsity-inducing priors (Louizos et al., 2017; Kingma et al., 2015; Molchanov et al., 2017). Briefly, this involves choosing an approximate posterior distribution with the form
p(w, =DD = (ww =)
(w; N zn, 2,, 22)2
(3.2)
and optimizing Equation (3.1) via stochastic gradient descent on the variational parameters given by {a. Mg. of. μt, J²). As its name suggests- and importantly for its ease of application to large models-VDOO can be implemented as form of dropout (Srivastava et al., 2014) by reparameterizing the noise on the weights as activation noise (Kingma et al., 2015). Application of VDO to Bayesian neural networks has achieved impressive compression rates, sparsifying deep neural networks while maintaining prediction performance on supervised learning problems (Molchanov et al., 2017; Louizos et al., 2017). Equipped with powerful approach for MDL-grounded posterior inference, we can now integrate these ideas with multitask RPO.
4 MINIMUM DESCRIPTION LENGTH CONTROL
As part of its underlying philosophy, the MDL principle holds that 1) learning is the process of discovering regularity in data, and 2) any regularity in the data can be used to compress (Grunwald, 2004). Applying this perspective to RI. is non-obvious- what 'data' is it trying to compress? Our hypothesis, which forms the basis for the framework
the agent's perspective,
'The invariance theorem (Kolmogorov, 1965) ensures that, given a sufficiently long sequence, Kolmogorov complexity is invariant to the choice of general-purpose language.
3

---

Published as a conference paper at ICLR 2023
Algorithm 1: MDL-C for Sequential Multitask Learning with Persistent Replay
1: Require: task distribution PM policy class O non-increasing coefficients {TH k=
2: Initialize: default policy distribution iA E S P(0), default policy dataset Do K- 0
3: for tasks k = 1, ......... K do
4: Sample a task M = (S, A, Pk. The Ph)) ~ P.)())
5: Optimize control policy:
0x argmax MM alBardy Ewniy KL (-|s), no (-(-
(4.2)
lee
6: Add data to default policy replay (M = |S] for finite/small state spaces):
Dx - Dx-1 U {(sm: to. (5m)) Mm==-
(4.3)
7: Update default policy distribution:
k
Vk-1 argmin
KL(u().pP0]
E Bla (-1sm). (-(sm)
(4.4)
MEN
7K-1
1=1
8: end for
we propose in this paper. that an agent faced with a set of tasks in the world should seek to elucidate structural regularity from the environment interactions generated by the optimal policies for the tasks. This makes intuitive sense: the agent ought to compress information which indicates how to correctly perform the tasks with which it is faced. That is, propose that the data in multitask RL are the state-action interactions generated by the optimal policies for set of tasks: D = [DM MEM {(s.a) Vs E S,a i (-|s)) MEM This interpretation is in line with work suggesting that a useful operational definition of 'task' can be derived directly from the set of optimal (or near-optimal) policies it induces (Abel et al., 2021). It also suggests a natural mapping to the multitask RPO framework. In this view, the control policy is responsible for learning and the default policy for compression: by converging the optimal policy for given task, the control policy "discovers" regularity which is then distilled into a low-complexity representation by the default policy. In our approach, the default policy is encouraged to learn a compressed representation not by artificially constraining the network architecture rather through a prior distribution p(w) over its parameters which biases a variational posterior v(w) towards simplicity. The default policy is therefore trained minimize the variational code:
via hand-designed information asymmetry, but
argmin E. AND log (als) + KL(U()) p()] MEN
(4.1)
arggmin EMSPPM E sood The
+ KL(((),p())
WEN
where is the distribution family for the posterior. This suggests the approach presented in Al- gorithm 1, in which for each task Mr. the control policy xo is trained to approximate the optimal policy मं via RPO, and the result is compressed into a new default policy distribution Vx+1- We now further motivate -narsity-idducing priors for the default policy in multitask settings, derive formal performance guarantees for MDL-C, and demonstrate its empirical effectiveness.
4.1 MOTIVATING THE CHOICE OF SINRSIGG-INDUCING PRIORS
In Section 3, compression (via pruning extraneous parameters) is the primary motivation for using sparsity-inducing priors that belong to the family of ccaled-mixtures of normal distributions. Intu- itively, placing distribution over the default parameters reflects the agent's epistemic uncertainty about the task distribution- wwhn few tasks have been sampled, a sparse prior prevents the default policy from overfitting spurious correlations in the limited data that the agent has collected. Here, we make this motivation more precise, describing an example generative model of optimal policy parameters which provides principled interpretation for prior choice p(z) in multitask RI.
4

---

Published as a conference paper at ICLR 2023
(A)
(B)
10
Jeftreys Severse-Gammer
Win Wi
W1
Half-Cauchy
W Wh1l 2 [W, #4
0.2 0.6
Figure 4.1: (A) Illustration of a generative model of optimal policy parameters. ú (1 9)w shrinks towards the origin, growing closer to wy than w11. (B) Sparsity-nnuccing priors over B.
Generative model of optimal policy parameters Consider a set of tasks M = )= that are clustered into 7 groups, such that the MDPs in each group are more similar to one another than to members of other groups. As an example, the overall family M could be all sports, while clusters M; M could consist of, say, ball sports or endurance competitions. To make this precise, we assume that the optimal policies of every MDP belong parametric family Rd, Vs E S} (e.g., softmax policies with parameters w), and that the optimal policies for each group are randomly distributed within parameter space. In particular, we assume that the parameters of the optimal policies of M have the following generative model:
(+|s): w
~ Te [1B o² ~ NN (wi O, (1 -)-3-)8830000 o'1a), Wa] ~ (wix W. daLa)
where La is the d dimensionnn identity matrix. If we marginalize out wi, get the marginal distribution p( wisk 13, o²) = (waz; 0, T2) We can then visualize the parameter distribution of the optimal policies for MM as a d-dimensional Gaussian within which lie clusters of optimal policies for related tasks which are themselves normally distributed (see Fig. 4. for d = 2).
Interpretation of The parameter 3 E (0, 1] can be interpreted as encoding the squared distance between optimal policy parameters within a group divided by the squared distance between optimal policies in M. Intuitively, 8 determines how much information one gains about the optimal parame- ters of a task in group, given knowledge about the optimal parameters of another task in the same group. To see this, we compute our posterior belief about the value w. given observation of wxx: p( 8, o²)) N (w;; (1 3)wsk, (1 La). When 3 (inner circle in Figure 4.1A has the same radius as the outer circle), our posterior mean estimate w. is simply O, suggesting we have learned nothing new about the mean of the optimal parameters in group i, by observing Wik. In estimator
the other extreme when 3 > 0, the posterior mean approaches the wekiiium-likellhann wik, suggesting that observation of Wis provides maximal information about the optimal parameters in group i. Any 3 in between the two extremes results in an estimator that "shrinks" was towards 0. The value of thus has important implications for multitask learning. Suppose the optimal parameters W11 (task 1, group 1), and proceeds to learn task 2 in group 1. The value of B determines whether W11 can be used to inform the agent's learning of w21 In this way, 8 determines the effective degree of epistemic uncertainty the agent has about the task distribution.
RL agent learns
Choice of p(3) and connection to p(2) Given its importance, it's natural ask what value should take. Instead of treating B as parameter, we can choose a prior p(33) and perform Bayesian inference. Ideally, p(3) should (i) encode our prior belief about the extent to which the optimal parameters cluster into groups and (ii) result in a posterior mean estimator ((((())) (x) = 1 - E [3]xr] a that is close to w for x x ~ Nx;;; W. o²). This condition encourages the expected default policy (under the posterior y; Equation (4.1)) to be close to optimal policies in the same MDP group (centered at 17). One prior choice that satisfies both conditions is p(8) 3-1_ It places high probability for small and low probability for high 3, thus encoding the prior belief that the optimal task parameters are clustered (see Figure 4. B. blue). It is instructive compare p(3) B-1 with two extreme choices of p(3). When p(3) = 5(3 - 1), p(=) = 8(0) and the marginal p(w) is the often-used Gaussian prior over the parameters w with fixed variance o², This corresponds the prior belief that knowing wa provides no information about W;2. On the other hand, p(8) = 5(33 recovers a uniform prior over the parameters w and reflects the prior belief that the MDP groups are infinitely far apart. In relation to (ii), one can show the (P())) strictly dominates the maximum-likellhone estimator (ML) (ar) (Efron
5

---

for Published as a conference paper at ICLR 2023
and Morris, 1973; Section D), for p(3) x 8-11. This means MSE( W1 w((())) < MSE W (MM) all w, where MSE(U, W ú) = E ((x-((r || - =(x)]]?
Connection to p(z) and application of VDO Defining =23-2 and applying the change- of-variable formula to p((3 x 3-1 gives p(z) |z|- and thus the Normal-Jeffreys prior in Section 3. VDO (see Section 3) can then be applied to obtain an approximate posterior v(w, 2) which minimizes the variational code Equation (4.1). Similar correspondences may also be derived for the inverse- Garse distribution and the half-Cauchy distribution (Figure 4.IB; Section D).
4.2 PERFORMANCE ANALYSIS
At a fundamental level, we'd like assurance (i) that MDL--'ss default policy will be able to effectively distill the optimal policies for previously observed tasks, and (ii) that regularization using this default policy gives strong performance guarantees for the control policy on future tasks.
Default policy performance One way we verify (i) is to obtain an upper bound on the average KL between default policies sampled from the default policy distribution and an optimal policy for task sampled from the task distribution. This enables us to perform analysis using online conver optimization (OCO). In OCO, the learner observes a series of convex loss functions & N - R, k L...., K, where N S Id is a convex set. After each round, the learner produces an output Iy E N for which it will then incur a loss la (Zx. (Orabona, 2019). At round k. the learner is usually assumed have knowledge of f,..... f but no other assumptions are made about the sequence of loss functions. The learner's s goal is to minimize its average regret. For further background, see Section F. Crucially, the MDL-C learning procedure for the default policy distribution is equivalent to follow the regularized leader (FTRL), an OCO algorithm which enjoys sublinear regret. In each round of FTRL, the learner selects the solution x E N according to the following general objective:
FR+1 = argminzeN the (x) + kk11 (I), where té N - IR is a convex regularization function. Using standard results, this connection allows us to bound MDL-C's s regret in learning the default policy distribution. All proofs are provided in Section G.
Proposition 4.1 (Persistent Replay FTRL Regret). Let tasks Mj be independently drawn from P.M at every round, and let them each be associated with a deterministic optimal policy T : S - A. We make the following mild assumptions: i) The
Tao((a((s (a*ls) 2 E > V' E S. where a* = n (8) and e is
constant. ii) min, (L(v()). p(-)] = 0 asymptotically as Varlu] - Do. Then with 1パ- = log(1 (//c//////
Algorishm 1 guarantees
K (v(vv)
K Σ 1=1
log(1/e)
(x(())) = (KL +1)
(4.5)
K k=
K
/ K
where UK= argmin
Σx= K (x(v).
Control policy performance Intuitively, this result shows that the average regret is upper-bounded by factors which depend on the divergence of the barycenter distribution from the prior and the "worst- case" prediction of the default policy. Importantly, the KL between the default policy distribution and the barycenter distribution goes to zero as K + xx. We can also now be assured of point (ii) above, in that this result can be used to obtain sample-complexity bound for the control policy. Specifically, we can use Proposition G.1 to place an upper-bound bound on the total variation distance between default policies sampled from / and the KL between the maximum likelihood solution and sparsity-inducing prior p. This is useful, as it allows to translate low regret for the default policy into sample complexity result for the control policy using Moskovitz et al. (2022a), Lemma 5.2.
Proposition 4.2 (Control Policy Sample Complexity). Under the setting described in Proposition G.I, denote by Tk the number of iterations to reach c-error for Mj in the sense that minggr, {v*i- v(O} S 6. whenever 1 >> Tk- Further, denote the upper-bound in Eq. (G.1) by G(K). In a finite MDP, from any initial 9(0), and following gradient ascent, EM [Tk]]] satisfies:
80]4[21812
E EMAPPML Mi [Te] 2
EMA~PMI 8~ Unill
(s)
22 - 76
1
6

---

Published as a conference paper at ICLR 2023
phase
phase 2
goal change
ro
plow
plow?
contingency change
plaac
405
16:0 1862
0050
1800
episodes
opisodes
(a)
(b)
(c)
Figure 5.1: MDL-C rapidly adapts new goal locations (top row) and rule changes (bottom row). All curves represent averages taken over 10 random seeds, with the shading indicating standard error.
where On (=) over S such that (us)) Vs E.
== drv(f( #o(-ls)) S VG(), (5) 2,AII - and is measure
2LAK1-a
Intuitively, this means that when the average number of samples is sufficiently large, the control policy is guaranteed to have reached error. Therefore, as the agent is trained more tasks, the default policy distribution regret, upper-bounded by G(K) decrreses asymptotically to zero, and as the default policy regret decreases, the control policy will learn more rapidly, poly (oly()(()).
5 EXPERIMENTS
We tested MDL.-C applied discrete and continuous control both the sequential and parallel task settings. To quantify performance, in addition measuring per-task reward, we also report the cumulative regret for each method in each experimental setting Scction I.I.
5.1 2D NAVIGATION
We first test MDL-C in the classic FOURROOMS environment (Fig. 5. (Sutton et al., 1999)). The baselines in this case are PO entropy-regularized policy optimization (PO), regularized policy optimization with no constraint on the default policy (RPO), an agent with VDO applied to the control policy and no default policy (VDO-PO), and MANUALIA (Galashov et al., 2019) in which the goal feature is manually witheld from the default policy. Details can be found in Section H.
Generalization Across Goals In the first setting, test MDL-C's ability facilitate rapid learning on previously unseen goals. the first phase of training, a single goal location is randomly sampled the start of each episode, and may be placed anywhere in two of the four rooms in the environment (Fig. 5. top left). In the second phase, the goal location is again randomly sampled at the start of each episode, but in this case, only in the rooms which were held in the first phase. Additionally, the agent is limited to 25 rather than 100 steps per episode. Importantly, VDO induces the MDL-C default policy ignore input features which are. on average. less predictive of the control policy's behavior. In this case, the default policy learns to ignore the goal feature and the reward obtained on the previous timestep. This because, when averaging across goal locations, the agent's 's current position (sx) and its previous direction (a+-1) are more informative of its next action-typically, heading towards the nearest door. In contrast, the un-regularized default policy of the RPO agent does not drop these features (Section for visualization and Section H for more details). By learning to ignore the goals present in phase I and encoding useful behavior regardless of goal location, MDL-C's develops more effective regularization in phase 2, enabling it to adapt more quickly than other methods (Fig. 5. top), particularly RPO. which overfits to phase I's goals. MANUAL.IA also adapts quickly, as its default policy is hard-coded to ignore the goal feature.
7

---

Published as a conference paper at ICLR 2023
walker, (sequancial)
walker (poraiial)
walker (perallal)
SIC
VDO
FTL
RRO
legg Willl
Doad
FELC
2084
1880
2000
20000
11000
30.00
190000
1008
1000
cartpola, swingup-sparse (siquential)
cartpale (parallel)
carppole (parallel)
1900
timesttps
cimesteps
Cimsstops
(a)
(b)
(c)
(d)
Figure 5.2: MDL-C improves both sequential and parallel learning in continuous control tasks. All curves represent averages taken over 8 random seeds, with the shading indicating standard error. In (b), insets show the improvement of MDL-C as k increases, and in (d), solid curves represent averages over each feature within a category.
Robustness to Rule Changes In this setting, there are only two possible goal locations, one the top left of the environment, and the other at the bottom right. In training phase 1, the agent receives a goal feature as input which indicates the state index of the rewarded location for that episode. In phase 2, the goal feature switches from marking the reward location to marking the unrewarded location. That is, if the reward is in the top left, the goal feature will point to the bottom right. Here, the danger for the agent isn't overfitting to particular goal or goals, but rather "overfitting" to the reward-based rules associated with a given feature. As we saw Fig. 5. (top), an un-regularized default policy, will copy the control policy and overfit to particular setting, Fortunately, the MDL-C default policy learns to ignore features which are, on average, less useful for predicting the control policy's 's behavior- the goal and previous reward features. This renders the agent more robust to contingency switches like the one described, as we can see in Fig. 5. (bottom). These examples illustrate that MDL-C enables agents to effectively learn the consistent structure of group of tasks, regardless of its semantics, and "compress out" information which is less informative on average.
5.2 CONTINUOUS CONTROL
A more challenging application area is that of digensiiinii continuous control. In this setting, we presented agents with multitask learning problems using environments from the DeepMind Control Suite (DMC; (Tassa al., 2018)). We used soft actor critic (SAC; (Haarnoja et al., 2018)) as the base agent. We tested MDL-C in both the sequential and parallel settings on two domains from DMC: walker and cartpole (Fig. 5.2a). Additional details can be found in Section H.
Sequential Tasks In the sequential setting, tasks are sampled one at time uniformly without re- placement from the available tasks within each domain, with the default policy distribution conserved across tasks. For walker, these tasks are stand, wa walk, k, and run. In stand, the agent rewarded for increasing the height of its center of mass, and in the latter two tasks, an additional reward is given for forward velocity. For cartpole, there are four tasks: balance, bal and swingup-spape in the swi swingup tasks, must additionally learn to swing the pole upwards from an initial down- ward orientation. Performance results for the hardest task within each domain (run in walker and swingup sparse in cartpole) for each method are plotted in Fig. 5.2b, where k indicates the task round at which the task was sampled. We can see that as & increases (as more tasks have been seen previously), MDL-C's performance improves. Importantly, the RPO agent's 's default policy, which is un-regularized, overfits to the previous task, essentially copying the optimal policy's 's behavior. This can severely hinder the agent's 's example, swi ngup-ngppp sparse, if the previous task is swi nguu, the RPO agent performs well,
sparse, swingup, In the balance tasks, the agent must keep rotating pole upright, and
performance when the subsequent task requires different behavior. For
8

---

Published as a conference paper at ICLR 2023
as the goal is identical. However, if the previous task is balance or balance-sparse the agent never learns to swing the pole upwards, significantly reducing its average performance. Another important point to note is that because the agent is not given an explicit goal feature in this setting, methods like MANUAL.A which rely on prior knowledge about the agent's inputs cannot be applied.
Parallel Tasks We also tested parallel-task versions of SAC, MANUALIA, and MDL-C based on the model of Yu et al. (2019). In this framework, a task within each domain is randomly sampled at the start of each episodeand the agent learns a single control policy for all tasks. Performance is plotted in Fig. 5.2c, where we can again see that MDL.-C accelerates convergence relative to the baseline methods. This marks a difference compared to the easier FourRooms environment, in which MDL-C and MANUALIA performed roughly the same. As before, one clue to the difference can be found in the input features that the MDL-C default policy chooses to ignore (Fig. 5.2d). For walker, inputs are 24-dimensional, with 14 features related to the joint orientations, 1 feature indicating the height of the agent's s center of mass, and 9 features indicating velocity components. For cartpole, there are 5 input dimensions, with 3 pertaining position and 2 to velocity. In the walker domain, where the performance difference is greatest, the MDL-C agent not only ignores the added task ID feature, but also the several features related to velocity. In contrast, in the cartpole domain, MDL-C only ignores the task ID feature. just as MANUALIA does, and the performance gap is smaller. This illustrates that MDL-C learns compress out spurious information even in settings for which is difficult to identify a priori. In order to test the effect of the learned asymmetry on performance more directly, we implemented a variant of MANUALIA in which all of the features which MDL-C learned to ignore were manually hidden from the default policy (Fig. I.4). Interestingly, while this method improved over standard MANUALIA, it didn't completely close the gap with MDL-C, indicating there are downstream effects within the network beyond input processing which are important for the default policy's 's effectiveness. We hope to explore these effects in more detail in future work.
6 RELATED WORK
MDL-C can be viewed as an extension of recent approaches to learning default policies ("behavioral priors") from the optimal policies of related tasks (Tch et al., 2017: Tirumala et al., 2020). For default policy to be useful for transfer learning, it is crucial to balance the ability of the default policy to "copy" the control policies with its expressiveness. If the default policy is too expressive, it is likely to overfit on past tasks and fail to generalize to unseen tasks. Whereas prior work primarily hand- crafts structural constraints into the default policies avoid overfitting (e.g.. by hiding certain state information from the default policy: Galashov et al., 2019). MDL-C learns such a balance from data priors via variational inference. MDL-C may also be derived from the RL-as- inference framework (Levine, 2018 8; Section A). MDL-C thus has close connections with algorithms such as MPO (Abdolmaleki et al., 2018) and VIREL (Fellows et al., 2020), discussed in Section A. As general framework, MDL-C is also connected to the long and well-established literature on choosing appropriate Bayesian priors (Jeffreys, 1946; Bernardo, 2005; Casella, 1985), and more recent work that focuses on learning such priors for large-scale machine learning models (Nalisnick and Smyth, 2017; Nalisnick et al., 2021; Atanov et al., 2018). For a further discussion of related work, particularly concerning the application of MDL to the RL setting, see Section C.
with
7 CONCLUSION
Inspired by dual process theories and the MDL principle we propose a regularized policy optimization framework for multitask RI. which aims to learn a simple default policy encoding a low-complexity distillation of the optimal behavior for some family of tasks. By encouraging the default policy to maintain a low effective description length, MDL.-C ensures that it does not overfit to spurious correlations among the (approximately) optimal policies learned by the agent. We described MDL- C's formal properties and demonstrated its empirical effectiveness in discrete and continuous control tasks. There are of course limitations of MDL-C, which we believe represent opportunities for future work (see Section E). Promising research directions include integrating MDL-C with multitask RL approaches which balance a larger set of policies (Barreto et al., 2020; Moskovitz et al., 2022b: Thakoor et al., 2022) as well considering nonstationary environments (Parker-Holder et al., 2022). We hope MDL-C inspires further advances in multitask RL.

---

Published as a conference paper at ICLR 2023
The authors would like to thank Kevin Miller, DJ Strouse, Marcel Binz, and Alexander Galashov for useful discussions and suggested improvements to the manuscript. Work funded by the Gatsby Charitable Foundation.
Acknowledgements
10

---

Published as a conference paper at ICLR 2023
REFERENCES
William James. The Principles of Psychology, volume 1. Henry Holt, New York, 1890.
Ann M. Graybiel. Habits, rituals, and the evaluative brain. Annual Review of Neuroscience, 31(1): 359-387, 2008, doi: 10.1 00.11446annueev.eeume 29.022..051 000000.111111 12851. URL https: https:://bi.org///
1146//nnurev..o neuro. 29, 051605, 112851. PMID: 18558860.
Nathaniel D Daw, Samuel Gershman, Ben Seymour, Peter Dayan, and Raymond J Dolan. Model- based influences on humans' choices and striatal prediction errors. Neuron, (9(6):1204-1215 03 2011.
Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL htttp://incomp) eeeeeeeeiiaae.. http://oookkteebbboobooe
html.
Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, 2011.
Matthew Botvinick, Ari Weinstein, Alec Solway, and Andrew Barto, Reinforcement learning, efficient coding, and the statistics of natural tasks. Current Opinion in Behavioral Sciences, 5:71-77, 08 2015. doi: wtt.0///...oobh..2200 2015.08 .8.9.009.
Robert Kirk, Amy Zhang, Edward Grefenstette, and Tim Rocktäschel. survey of generalisation in deep reinforcement learning, 2021. URL https:://// /awxiv. org/ abaaab//// abbs/2111. 221111919919..
Yee Whye Teh, Victor Bapst, Wojciech Marian Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 4499 4509, 2017.
Alexandre Galashov, Siddhant M. Jayakumar, Leonard Hasenclever, Dhruva Tirumala, Jonathan Schwarz, Guillaume Desjardins. Wojciech M. Czarnecki, Yee Whye Teh, Razvan Pascanu, and Nicolas Heess. Information asymmetry kl-regularized RL. CoRR, abs/1905.01240. 2019.
Anirudh Goyal, Yoshua Bengio, Matthew Botvinick, and Sergey Levine. The variational bandwidth bottleneck: Stochastic evaluation on an information budget, 2020.
Anirudh Goyal, Riashat Islam, Daniel Strouse, Zafarali Ahmed, Matthew Botvinick, Hugo Larochelle, Yoshua Bengio, and Sergey Levine. Infobot: Transfer and exploration via the information bottle- neck, 2019.
Ted Moskovitz, Michael Arbel, Jack Parker- Holder, and Aldo Pacchiano. Towards an understand- ing of default policies in multitask policy optimization. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 10661-10686. PMLR, 28-30 Mar 2022a. URL https:: httt:::://proceednggs. mil press/ html.
w151/moskovii
Lucy Lai and Samuel Gershman. Policy compression: An information bottleneck in action selection. Psychology of Learning and Motivation. 74:195-232, 01 2021. doi: 10.1016/bs.plm. 202...0.00000004
Jorma Rissanen. Modelling by shortest data description. Automatica, 14, 01 1978.
Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley and Sons, 2010.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Avnish Narayan, Hayden Shively, Adithya Bellathur, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning, 2019. URL https: //arxiv.org////o/ooooo.l.... abs/1 9911199000 0.000..0 0897.
Tom Zahavy, Andre Barreto, Daniel Mankowitz, Shaobo Hou, Brendan O'Donoghue, Jurii Kemaev, and Satinder Singh. Discovering set of policies for the worst reward. In International Conference on Learning Representations, 2021. URL https: http:://///eeeeeeeeeeeeee Td=PUkhWz65dy5;
11

---

Published as a conference paper at ICLR 2023
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learinng for fast adaptation of deep networks. In International Conference on Machine Learning, pages 1126 1135. PMLR, 2017.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning, 2013. URL https: / /awxiv..vvvv..////////a..//vaiv. org/ abs/ 1309.6308800 6821.
Aldo Pacchiano, Ofir Nachum, Nilseh Tripuraneni, and Peter Bartlett. Joint representation training in sequential tasks with shared structure, 2022.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.0066 2017.
John Schulman, Xi Chen, and Pieter Abbeel. learning, 2018.
Equivalence between policy gradients and soft qr
Sergey Levine. Reinforcement learning and control probabilistic inference: Tutorial and review, 2018.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 64 66. PMLR, 2020.
Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, Anna Choromanska, Krzysztof Choromanski, and Michael Jordan. Learning to score behaviors for guided policy optimization. In The International Conference on Machine Learning. 2020.
Dhruva Tirumala, Alexandre Galashov, Hyeonwoo Noh, Leonard Hasenclever, Razvan Pascanu, Jonathan Schwarz, Guillaume Desjardins, Wojeiech Marian Czarnecki, Arun Ahuja, Yee Whye Teh, and Nicolas Heess. Behavior priors for efficient reinforcement learning. arXiv preprint arXiv:2010.14274, 2020.
Abbas Abdolmaleki, Jost Tobias Springenberg. Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum posteriori policy optimisation, 2018.
John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region policy optimization. CoRR, abs/1 ht//15002.5577, 2015.
Sham M Kakade. A natural policy gradient. In Advances in neural information processing systems, pages 1531-1538, 2002.
Ted Moskovitz, Michael Arbel, Ferene Huszar, and Arthur Gretton. Efficient wasserstein natural gradients for reinforcement learning, 2020.
Tuomas Haamoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor, 2018.
Kyungjae Lee, Sungjoon Choi, and Songhwai Oh. Sparse markov decision processes with causal sparse tsallis entropy regularization for reinforcement learning. IEEE Robotics and Automation Letters, 3(3):1466 14144666177,,, 2018.
A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1:1-7, 1965.
Ming Li and Paul M.B. Vitnyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer Publishing Company, Incorporated, 3 edition, 2008
Léonard Blier and Yann Ollivier. The description length of deep learning models. Advances in Neural Information Processing Systems, 31, 2018.
Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference on Computational learning theory, pages 5-13, 1993.
12

---

Published as a conference paper at ICLR 2023
Antti Honkela and Harri Valpola. Variational learning and bits-back coding: an cetemmattioo-thoretti view to bayesian learning. IEEE transactions on Neural Networks, 15(4):800 810, 2004.
Peter Grunwald. A tutorial introduction to the minimum description length principle, 2004.
David F Andrews and Colin Mallows. Scale mixtures of normal distributions. Journal of the Royal
Statistical Society: Series (Methodological), 36(1 1:99-1099) 1974.
Harold Jeffreys. An invariant form for the prior probability in estimation problems. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 186(1007):453-46,, 1946. URL https: roya spuietypubl shing. .og..org//oee. /abs/ /10. 1009/009//00 1098//sp... 1946 0056.
Nicholas G Polson and James G Scott. On the half-cauchy prior for global scale parameter. Bayesian Analysis, 7(4):887-990) 2012.
Andrew Gelman. Prior distributions for variance parameters in hierarchical models (comment on article by browne and draper). Bayesian analysis, 1(3):515-534 2006.
Peter Grünwald and Teemu Roos. Minimum description length revisited. International Journal of Mathematics for Industry, 101),, 2019.
Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. Advances in neural information processing systems, 30, 2017.
Durk P Kingma, Tim Salimans, and Max Welling, Variational dropout and the local reparameterization trick. Advances in neural information processing systems, 28, 2015.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In International Conference Machine Learning, pages 2498-2507. PMLR, 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal Machine Learning Research, (866):1929-1958 2014. URL http://jmm tttp:imlll...araeeeeeeeeeee www.org/ppp.//....... /v15/ srivastaval .a.html..
David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, Jnd Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 7799-7812. Curran Associates, Inc., 2021.
Bradley Efron and Carl Morris. Stein's estimation rule and its competitors an empirical bayes approach. Journal of the American Statistical Association, 68(341):117-130, 1973.
Francesco Orabona. A modern introduction to online learning, 2019.
Richard S. Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction reinforcement learning. Artificial Intelligence, 1 112(1): 181-211, 1999. URL https: //wp: www.wseeeeeedeet.....mmmmm com www.//ccinnee..eeooocooooooo /ttp///cnce/aiieeeepiiiiiie/ 50004370299000521.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki. Josh Merel, Andrew Lefrancq. Timothy Lillicrap, and Martin Riedmiller. Deepmind control suite, 2018
Matthew Fellows, Anuj Mahajan, Tim G. J. Rudner, and Shimon Whiteson. Virel: A variational inference framework for reinforcement learning, 2020.
José M Bernardo. Reference analysis. Handbook of statistics, 25:17-90, 2005.
George Casella. An introduction to empirical bayes data analysis. The American Statistician, 39(2): 83-87, 1985.
Eric Nalisnick and Padhraic Smyth. Learning approximately objective priors. arXiv preprint arXiv:1704.01168. 2017.
13

---

Published as a conference paper at ICLR 2023
Eric Nalisnick, Jonathan Gordon, and José Miguel Hemándezz-obato.. Predictive complexity priors. In International Conference on Artificial Intelligence and Statistics, pages 694-702. PMLR, 2021.
Andrei Atanov, Arsenii Ashukha, Kirill Struminsky, Dmitry Vetrov, and Max Welling. The deep weight prior. arXiv preprint arXiv 1.066433, 2018.
Andre Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings the National Academy of Sciences, 117 (48):30079-30087, 2020. ISSN 0027-8424, doi: (..1073/pnaa.190037711111 URL https: / //www. org/
content wwtpaa/..rrcccotettttteeooomeett
Ted Moskovitz. Spencer R Wilson, and Mancesh Sahani. A first-occupancy representation for reinforcement learning. In International Conference on Learning Representations, 2022b. URL
.nt atte:/ooommniidjAzeeeee/e/
Shantanu Thakoor, Mark Rowland, Diana Borsa, Will Dabney, Rémi Munos, and André Barreto. Generalised policy improvement with geometric policy composition, 2022. URL https://
(twiv.org/abb//20/ 08736.
Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Evolving curricula with regret-based environment design, 2022. URL https: http///xxvvvv////// org/ aas//b//////// 220..2203..2 2230.0130..
Samuel Kessler, Jack Parker-Holder, Philip Ball, Stefan Zohren, and Stephen J. Roberts. Same state, different task: Continual reinforcement learning without interference, 2021. URL https: //aaxxii wwwpg//bbb//aa/ 02940.
Jesse Zhang, Karl Pertsch, Jiefan Yang, and Joseph Lim. Minimum description length skills for accelerated reinforcement learning. In Self-Supervision for Reinforcement Learning Workshop- ICLR 2021, 2021. URL https: httL:tttt//ppeeeeeeeeee http::////peeeeeee./. net forum? (oozummid=rxxxxrII0
Sebastian Thrun and Anton Schwartz. Finding structure in reinforcement learning. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems, volume 7. MIT Press, 1994. URL httpa::/prrceeddigg neurips cc cc/papper/194//LLle
Edward George, Feng Liang, and Xinyi Xu. Improved minimax predictive densities under kullback- leibler loss. The Annals of Statistics, pages 78-91, 2006.
Dominique Fourdrinier, William E Strawderman, and Martin Wells. On the construction of bayes minimax estimators. Annals of Statistics, pages 660-671, 1998.
Gabriel Barth-Maron Matthew W. Hoffman, David Budden, Will Dabney, Dan Horgan, Dhruva TB, Alistair Muldal, Nicolas Heess, and Timothy P. Lillicrap. Distributed distributional deterministic policy gradients. CoRR, abs/1804.00 004/1004.,861, 2018. URL http:/ htt///axxxvv http//axx...../bbbb/. wwtp://////////////oo/ 08617.
James Melbourne. Strongly convex divergences. Entropy (Basel, Switzerland), 22(11):1327) 11 2020.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, March 2004.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Maria Florina Balcan and Kilian Q Weinberger, editors. Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings Machine Learning Research, pages 1928-1933 New York, New York, USA, 20-22 Jun 2016. PMLR.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL
https://arxe wwwg//o/////o/eooo 6980.
14

---

Published as a conference paper at ICLR 2023
Minimum Description Length Control
Supplementary Information
A REINFORCEMENT LEARNING AS INFERENCE
The control inference framework (Levine, 2018) associates every time step h with binary "optimality" random variable On E (0, 1} that indicates whether an is optimal at state 8n (On = for optimal, and Oj for not). The optimality variable has the conditional distribution P(On 1|sh, aA) = exp(r(5), an)). which scales exponentially with the reward received taking action aj in state S/-
Denote OH h as the event that O, for s = O..... H 1. Then the log-likelihood that a policy Tw (als) is optimal over horizon H is given by:
p(O
P(O (Flw)
By performing variational inference, can lower-bound the log-likelihood with the ELBO:
H-1
log P(O 2 (y,(,)
Σ (r(sh, an) - Evo(w) KL (s);; Tud (wlaalss))
(A.1)
where (o, w) ua (a(T)us(w) is the variational posterior,
H-1
(o(T) p(so)
II P(sN41lsh, an) A=0
and {8, d} are the variational parameters. We can maximize this objective iteratively by performing coordinate ascent on {0, Ø):
8
(vo(T)
(r(sh (w) KL[To(an (sh), Tea (an(s5))))
(A.2)
Am0
H-1
Φ + Φ V
(vg(T)
Bup(w) KL[To (an(sn))))) a (an ss:]] + (L)vo(w), (L))
(A.3)
A=U
where 7) is learning rate parameter. Note that Equation (A.3) is equivalent Equation (4.1) and Equation (G.8), and Equation (A.2) is equivalent to Equation (G.7) with the KL reversed.
Connection Maximum Posteriori Policy Optimization (MPO) MDL-C is closely related to MPO (Abdolmaleki et al., 2018), with three key differences. First, MDL-C performs variational inference on the parameters of the default policy with an approximate posterior (ww),, whereas MPO performs MAP inference. Second, MPO places a normal prior on which in effect penalizes the 1.2 norm of w. contrast, MDL-C uses sparsity-inducing priors such as the normal-Jeffreys prior. Third, MDL-C uses a parametric To. whereas MPO uses a parrameettri one2. While there is also a parametric variant of MPO, this variant does not maintain and á separately. Instead, this variant directly sets 0 to & in Equation (A.2). This illustrates the key conceptual difference between MDL-C and MPO. MDL-C makes a clear distinction between the control policy Ty and the default policy Tw, with the two policies serving two distinct purposes: the control policy for performing the current task, the default policy for distilling optimal policies across tasks and generalizing to new ones. MPO, the other hand, treats To and Tw as fundamentally the same object.
Like MPO, VIREL (Fellows et al., 2020) can be derived from the control as inference framework. In fact, Fellows et al. showed that parametric variant of MPO can be derived from VIREL (Fellows et al., 2020). The key novelty that sets VIREL apart from both MPO and MDL-C is an adaptive temperature parameter that dynamically updates the influence of the KL term in Equation (A.2).
II practice, MPO parametrizes implicitly with parameterized action-value function and the default policy.
15

---

Published as a conference paper at ICLR 2023
B MULTITASK RL FRAMEWORKS
We believe the objective which best captures naturalistic settings is the average reward obtained over the agent's "lifetime": limr- E r(se, at). Typical objectíves include finding either single policy or a set of policies which maximize worst- or average-case value: max, MinMEM VM (Zahavy et al., 2021) or max; ,, VM (Moskovitz et al., 2022a). When the emphasis is on decreasing the required sample complexity of learning new tasks, useful metric is cumulative regret: the agent's total shortfall across training compared to an optimal agent. In practice, it's often simplest to consider the task distribution P.M to be categorical distribution defined over a discrete set of tasks M := {M² J though continuous densities over MDPs are also possible. Two multitask settings which we consider here are parallel task RL and sequential task RL. In typical parallel task training (Yu et al., 2019), a new MDP is sampled from P. the start of every episode and is associated with a particular input feature E G that indicates to the agent which task has been sampled. The agent's s performance is evaluated on all tasks M M together. In the sequential task setting (Moskovitz et al., 2022a; Pacchiano et al., 2022), tasks (MDPs) are sampled one at a time from P PM, with the agent training each until convergence. In contrast to continual learning (Kessler et al., 2021), the agent's 's goal is simply to learn a new policy for each task more quickly as more are sampled, rather than learning single policy which maintains its performance across tasks. Another important setting is meta-RL, which we do not consider here. In the meta-RL setting, the agent trains on each sampled task for only a few episodes each with the goal of improving few-shot performance and is meta-tested on a set of held-out tasks (Yu et al., 2019; Finn et al., 2017).
Another strain of work in multitask RI. assumes some form of shared structure in the transition dynamics (Pacchiano et al., 2022; ?: ?). Specifically, the core assumption made by these works is that the transition dynamics are linearly decodable from a set of features which is shared across tasks or in which the transition matrix admits a low-rank decomposition. This is very different from our own structural assumption that is, in its simplest form, that the optimal policies of the tasks with which our agents are faced take similar actions in at least some part of the state space. Beyond this, the MDPs in M need only share the same state and action space, with no direct assumptions about transitions or rewards. This is important, because the assumed structures in the transition distribution made by Pacchiano et al. (2022); ?); ? act as the starting points for algorithm development. however, can leverage similarity among optimal policies when it exists, but are not dependent on it as prerequisite. (E.g.. TVPO (and RPO/MDL-C) is guaranteed to perform no worse than barrier regularization, which has a polynomial sample complexity guarantee.) Ideally, we'd d like generalist method which can identify on its own and exploit different types of structure in the environment.
MDL-C/RPO/TVED
C ADDITIONAL RELATED WORK
Previous work has also applied the MDL principle in RL context, though primarily in the context of unsupervised skill learning (Zhang et al., 2021; Thrun and Schwartz, 1994). For example, Thrun and Schwartz (1994) are concerned with set of "skills" which are policies defined only over subset of the state space that are reused across tasks. They consider tabular methods, measuring a pseudo-description length as
DL DL LL (M) 1sab SES MEM
(C.I)
where Pyy(s) (s) is the probability that no skill selects an action in state for task M and the agent must compute the optimal Q-values state s for M, N the number of skills, and [S,] the number states for which skill n is defined. They then trade off this description length term with performance across a series of tabular environments.
One other related method is DISTRAL (Teh et al., 2017), which uses the following objective in the parallel task setting:
I Distral (0 = 7 - Eg-aao [aKL)
+ (-
(C.2)
That is. like the un-regularized RPO method, DISTRAL can be as performing maximum- likelihood estimation to learn the (unconstrained) default policy, while adding an entropy bonus to the control policy.
16

---

Published as a conference paper at ICLR 2023
Another important method in the sequential setting is TVPO (Moskovitz et al., 2022a), in which (in the tabular case) the default policy is defined as a softmax over the average action frequencies of the optimal policies for the tasks that the agent has seen so far. That is, if the average optimal action in state s is given by
(x) E
(x)(()) a),
then the TVPO default policy is
The (a softmax (s.
where ((k) is temperature which decays + cc. In dige-dimmnsional state and action spaces, this tabular solution can be approximated by training a default policy to predict the converged control policy's s actions in each task. Importantly, this is equivalent default policies will converge to the same barycenter policy (Moskovitz et al., 2022a), as long as the distillation is only performed once the control policy has converged in each task. Using KI. distillation in this way is exactly the RPO baseline that we use in this paper. Crucially, the use of the softmax with decaying temperature was introduced by Moskovitz et (2022a) as a useful 'hack' to prevent the default policy from overfitting to early tasks, as the optimal default policy is the barycenter policy (approximated as the number of draws from the task distribution grows). Thus, MDL-C can itself be seen as scalable advancement of TVPO which models the agent's 's epistemic uncertainty about the task distribution by placing sparse prior over the default policy parameters (and uses distillation loss rather than action prediction). In other words, MDL-C represents principled approach to reducing the risk of default policy overfitting in the low-data regime.
using KI. distillation in that the
Finally, Brunskill and Li (2013) consider similar training and task structure our own, but use model-based approach to learn the underlying MDPs.
D MOTIVATING THE CHOICE OF SPARSITY-INDUCING PRIORS
As reminder, the generative model of optimal parameters in Section 4.1 given by:
w w.13,0² N(0. 1
0² o²Ia).
(D.1)
3
Wik: W; 0 NNw, oaIa)
(D.2)
with marginal and posterior densities
p(wal oz ()) N
(D.3)
p W. Wike _3,3) = N ((1 3)wck (1 1))²
(D.4)
In the rest of this section, set の² 1 for simplicity and drop the indices and w remove clutter.
D.1 CORRESPONDENCE BETWEEN p(2) AND p(3)
In Section 4.1, we draw a connection between p(0) 8-1 and the normal-Jeffreys prior, which is commonly used for compressing deep neural networks (Louizos et al., 2017). In Table 1, we expand on this connection and list p(5) for two other commonly-used priors for scale mixture of normal distributions: Jeffreys, Inverse-gand areese-gamma, and Inverse-beta Note that the half-Cauchy distribution p(z) x (1 + 22)-1 is a special case of the inverse-beta distribution for = 1/2.. Half-cauchy prior is another commonly used prior for compressing Bayesian neural networks (Louizos et al., 2017).
D.2 MSE RISK
In this section, we prove that the Bayes estimators for the Jeffreys, inverse-gamin gamma, and the inverse- beta (by extension the half-Caud half-Cauchy) distributions dominate the maximum respect the mean-squared error.
maximum-likelibood likelihood estimator with
17

---

Published as a conference paper at ICLR 2023
Define the reeansquared error of estimator (z)) of iú as
MSE(w, th) = Ex (z) m|
(D.5)
where the expectation is taken over (2; w. a²). Immediately, we have R Rww, ((M) d, where ((()) (a:) x is the maximun-likelihood estimator. An estimator vi()) is said to dominate another estimator (xx) if MSE(T, Ww, (ha) s MSE(W, thş)) for all w and the inequality is strict for a set of positive Lesbesgue measure. is well-known that the maximum-likelihon estimator is minimax (George et al., 2006), and thus any estimator that dominates the maximum-likelihodd estimator is also minimax.
To compute the mean-squared error risk for estimator (xx), observe that | w| + 2((((a)) T7) (x W)
[x(( F = | r())
(D.6)
Taking expectations on both sides gives
MSE(w, 2)) = Ez11x x(xx|] + (z),
(D.7)
= w(+) - d 2E, V w(xx
(D.8)
where V = (0/0z1..... 0/0ra) and we apply Stein's 's lemma
x4) /r; in the last line. the estimator takes the form wxx = x + 7(x), the expression simplifies as:
MSE(W, 2 = d + Ex (=) + 2E, V 7(x).
(D.9)
Therefore, an estimator (xx) x + > (z) dominates úi (ML) (x)) if
MSE(W, a MSE ,., wi (ML) Ez [lx(2))1 + (x)] s
(D.10)
for all w and the inequality is strict on a set of positive Lesbesgue measure.
D.2.1 JAMES-STEIN ESTIMATOR
The famous Hame-Stein estimator is defined as
t (18) (x) 7 (15)
y (1)
-(d (dd2))z/ 112//
(D.11)
with
V 0050 (x) = Σ 1=1
2
+2
d
x2 = (d 2)²
(D.12)
|
(1|=|13)2
x 12
ln (s:))1 = (d 2)²
(D.13)
||~||
Substituting V us (x) and || (15) (x:)) (1: into Equation (D.10), we have
MSE(W, (15) MSE(W, (w, i (ML) E, (d 2)
(D.14)
|
Thus, the James-Stein estimator dominates the maximum-likelihodd estimator for d > 2.
Prior name
p(z2) px22) x
p(3)
Jeffreys gaeese-gamma
p(3) x B-1
p(22) -[]
p(3) x 10-1e 139/2
Inverse-beta
p(2?) (22)t-1 21 (x++) p(B) x 3 (++ - (stt)
Table 1: Correspondence between p(2?) and p(3).
18

---

Published as a conference paper at ICLR 2023
D.2.2 BAYES ESTIMATORS
The Bayes estimator for a prior choice p(3) is given by (?):
(((( (x) + (0())))))) (x) = V logm(x);
(D.15)
where
m(x) / NN[x; 1-)00
(D.16)
= ((2m) (2T) + gd/ exp (-3x² p(3)d3.
(D.17)
Substituting (x)())()) into Equation (D.10), find that the condition for the Bayes estimator be minimax is given by (George et al., 2006):
V2m(z)]
MSE(W, ()) MSE(W, (ML)) Ex
Voo (log)())l
(D.18)
m(x)
V2
m(a)
Ex
S
(D.19)
m(z)
where V = 82/ is the Laplace operator. This condition holds when v /m(x) superhar- monic (i.e., vm(z)) I 0, vr IR'). suggesting recipe for constructing Bayes estimators that dominate the maximum likelihood estimator, summarized in the following proposition.
Proposition D.1 (Extension of Theorem I in Fourdrinier et al., 1998). Let p(3) be a function such that f(3 = B3' (3)/p(B) can be decomposed as fi + fz(3) where fi is non-decreasing.
fi S A, fe S B, and A/2 + B < (d - 6)/4. Assume also that limg- 3d/2+2 = Then, V2 V2VmL (z) S 0 and the Bayes estimator is minimax. If A/22 + B < (d 6)/4, then the Bayes estimator dominates vi(M) (x)).
Proof. This proof largely follows the proof of Theorem (Fourdrinier et al., 1998).
Note that Equation (D.18) holds if
1
[m(())1²) V'm(a)) 2 m(x))
V2 v2Vm(r)
00 Vo E Rdd
(D.20)
2 m(a))
or equivalently
V'm(x) Vm(x)]l
50 Vo Rd. m(x)
(D.21)
|m(()]
Computing the derivatives, we get the condition
So' (31|=| d) 32/22/122222220 200)
1 ||ج|| So g4/2t2
2 So 34122-0011:11/2233)11 S 0. (D.22)
|| So 2lll+11e-lll11)22p((3333
Divide both sides by ||0||| and rearrange to get
fo gd/2 911
1 1 g
(D.23)
Jo ////--1e--00:1//////030000
2 S 3d/22- 010= /1=p1)3331
Next, we integrate by parts the numerator of the first term on the left-hand side to get:
S/ A1|=1 p3
2
ad/2+22-911a4 911=11// (2p(13)
(D.24)
|
d +
1 2// 12 ((3)dB
+
| 1
2
gd/2- - -
p3
|
19

---

Published as a conference paper at ICLR 2023
where the middle term is the same the denominator of the first term in Equation (D.23). Integrating by parts the second term gives the same expression as that of the first term, but with d - 2 in place of d everywhere. Substituting these expressions back into Equation (D.23), collecting like terms, and dividing both sides by 2/| gives:
So 000:1+22-0
1 So g4/2t12=00ll1)//////
+ Ku + K1
(D.25)
So 00/2+1e-Allz111
2
So $0/22--1l=11/2p((3)6
4
1d+2
d-6
-
2
2
4
where
limg-11 g4/2+22 9||=11 /2 /2ppll/pppppp (())
lim gd/2+ (001++1-000])122pp((
K1
(D.26)
No 80/2211-8 (2pp)))
2
Jo 00/22-001=11//p((()))
limg
limm gd/2+1 111z /2p(=
KO Jo 3d/2+1 c (=
(D.27)
|||=| Jo 001
Here, both Kig and Kд are nonpositive: (i) Kig nonpositive because the first term vanishes due the boundary conditions and the second term is nonpositive, and (ii) is nonpositive because the limits of the numerators of the two terms are equal while the denominator of the second term is larger than that of the first. We can thus drop Ky and Ki to get the sufficient condition:
d 6-6
Ed (f)
Fdt 2
(D.28)
2
where Eg denotes expectation with respect to the density
ga(3) fo 21/
(D.29)
and where =(8)= (3)p2)/)
Because g3( a family of monotone increasing likelihood ratio in d and fi is nonincreasing and bounded by A, we have Ex(Si) 2aai))//// < A/2. We have (,( 2(22) < B because f2 B. Taken together, we have
(a( 2 A/2 B (I: 6)/4.
(D.30)
When the inequality strict (i.e., A/2 + estimator dominates the maximum-likelihood estimator.
6)/4,, then V2 V2Vm(x) and the Bayes
Checking whether given p(0) satisfy the conditions in Proposition D.1 may be tedious. The following corollary is useful for construction p(3) that satisfies the conditions in Proposition D. Corollary D.1 (Extension of Corollary in Fourdrinier et al., 1998). Let de be continuous function that can be decomposed as 1/1 + 1/2, with 1 I C, 1h non-decreasing, 0 < 12 < D, and C/2 + < 0. Let
( 3 (xb(u) - du
/
p(B) exp
VSS O,
(D.31)
2
90
u
such that limg--o 2())))p(()3))12p and 30 (0, 1) is constant. Then, v( results in minimax Bayes estimator, which dominates the maximum likelihood estimator when C/2 + D 0.
Proof. The proof is the same as that of Corollary in Fourdrinier et al., 1998, with Proposition D.1 in place of Theorem in Fourdrinier al., 1998.
Using Corollary D.I, we now check that the three priors listed in Table and referenced Section 4.1 lead to Bayes estimators that dominate the maximun-likelihood estimator.
20

---

Published as a conference paper at ICLR 2023
Jeffreys prior
Let 1/1 (u) for and 212(2)) 0. We have
v(3) exp
1
" 2a + d - 6
du
fatldd6)/2.
(D.32)
2
u
To satisfy limg-00 g4/2+ ((3) O, we require 1 - d < S 0. We recover the improper normal- Jeffreys prior p()) ix g-1, for a = d/2. The corresponding Bayes estimator dominates the maximum likelihood estimator when 4.
Inverse-gamma prior
Let 11 (u) and (2)(2) = b(1 u2) for I and b 0. We have
p(3) -exp ( aa b(1 u2/2 (d -6//2 du x 0))2 6)/2 2
(D.33)
u
Setting C a and D b/2, we get the followings conditions: + b S and d S b/2. Note that when these conditions are met with = a (b d 4)/2 and f. = b, we recover the inverse-gamma prior in Table
Inverse-beta (half-Cauchy) prior We have
Let 1/1 (u)) a and (b2(4) b/(u + 1) for a S and 2
p(3) exp (1% 6/(11 + u) (d 2 du x gatbt(d (1
(D.34)
u
Setting C = and D = b, we get the condition a/2 + b S O. To satisfy lim 3 p(3) = 0, we require
< b S 0. Note that this corresponds to the inverse-beta prior in Table with t t= a + (d 8)/2 and b
To recover the half-Cauchy prior, we set = 1 and a = (5 - -d)/2. All conditions Corollary D.1 are satisfied when d > 9.
E LIMITATIONS
One weakness of the current theoretical analysis regarding the choice of pparsityinnuciig priors is the assumption of Gaussian (and in particular, isotropic Gaussian) structure in the parameter space of optimal policies for clusters of tasks. In reality, there is likely a nontrivial degree of covariance among task parameterizations. Extending our analysis to more realistic forms of task structure is an important direction for future work. In similar vein, the assumption that tasks are drawn iid from fixed distribution is also unrealistic in naturalistic settings. It would be interesting to introduce some form sequential structure (e.g., tasks are drawn from Markov process), Another direction for future work is expanding beyond the "one control policy, default policy" setup -aaiing for example, one default policy per task cluster and the ability to reuse and select (for example, using successor feature-like representations (Barreto et al., 2020; Barth-Maron et al., 2018; Moskovitz et al., 2022b)) among an actively-maintainedd set control policies across tasks and task clusters would be useful.
OCO BACKGROUND
online convex optimization (OCO), the learner observes series convex loss functions &x N - R. k 1,... K, where N C Rd is convex set. After each round, the learner produces output Ik E N for which it will then incur a loss la (zx) (Orabona, 2019). At round k. the learner usually assumed to have knowledge of li,..., LR-11, but no other assumptions made about the sequence of loss functions. The learner's goal is to minimize its average regret:
K (a( min K
RK =
(((x).
(F.I)
K
1=1
1=
21

---

Published as a conference paper at ICLR 2023
One OCO algorithm which enjoys sublinear regret is follow the regularized leader (FTRL). In each round of FTRL, the learner selects the solution x E according to the following objective:
A-1
argmin cha (x) + Σ ((x),
(F22)
zEN
1=1
where tha N + R is convex regularization function.
G PROOFS OF PERFORMANCE BOUNDS AND ADDITIONAL THEORETICAL RESULTS
The following result useful.
Lemma G.1. The function f(v) (w)) is L-Lipschitz as long f W R lies within [0, L) Yu E W, where W C I2d a Hilbert space and L < cc.
Proof. We have
(((m)) - {(22) [Ewner (ww Enew (w))
1/y (v) (v)(w) (w) (2(w)) dw
Kff 12)wl
I1/lwwlle 12llw
- L|Im -12llw,
where the first inequality is due to Cauchy-Schwarz Schwarz and the second is by assumption on f.
Proposition G.1 (Default Policy Distribution Regret). Let tasks Mg be independently drawn from P.M at every round, and let them each be associated with deterministic optimal policy nे. :S + A. We make the following mild assumptions: i) Twr (a"(a))) 2 > 0 Vs E S, where a" (s) and is constant. ii) min, KL(v(.), + 0 as Var[v] - oo for an appropriate choice of sparsity-inducing prior p. Then Algorithum 2 guarantees
EP m (((()) - fx (Fx)) KL log(1/e)
(G.1)
VK
where UK = argmin, VN Ek= (V).
Proof. The first part of the proof sets up an application Orabona (2019), Corollary 7.9.
To establish grounds for its application, we first note the standard result that the regularization functional (Vv) = (L(v(W),, p(w)] for probability measures v, E P(W) 1-strongly convex (Melbourne, 2020).
Finally, assumption (i) implies that the KL between the default policy and the optimal policy is upper-bounded: [L[TT, kw] I log 1/c. Then by Lemma G.1, (v( is L-Lipschitz wrt the TV distance, where log 1/e.
Note also that under Gaussian parameterization for the distribution space N is the Gaussian parameter space = {(, E)
E Rd, E E Rdxd E z 0), which convex (Boyd and
Vandenberghe, 2004).
Then Orabona (2019), Corollary 7.9 gives
K (v(vx)
K Σ K
L (x(k)) < |K +a
(G.2)
K 1=1
VR
k=1
where VK = argmin, ΣR (v). The constant E IR is hyperparameter, so we are free to set it to 1 (Orabona, 2019). Finally, we observe that Ep,, K ΣK ((vx) Ep lx (x(UK) and take the
22

---

Published as a conference paper at ICLR 2023
expectation with respect to PM; of both sides of Eq. (G.2) to get the desired result:
L
Mp (v((k) (x(xx)] MB KL +1)
(G.3)
VK
11
Proposition 4.2 (Control Policy Sample Complexity). Under the setting described in Proposition G.I. denote by Tg the number of iterations to reach e-error for Mr in the sense that mingsT, {v
V S whenever t > T&- Further, denote the upper-bound in Eq. (G.1) by G(K). In a finite
MDP, from any initial ( and following gradient ascent, EM [Tt] satisfies:
80|A
dp
EM [Te] N
BMAMPM: unUnif
11
where (s)ss dTv Ro(-ls)) S VG(K,, (s) over S such that pus) > V E.
2[A(1-a(()) and μ is measure (
Note: In the above, there is small error-it should be as((s) E (11s) (-1s)) s
V G()) de refers to the discounted state-occupancy distribution under with initial state distribu- tion
d (8) = Eso~p( 7)
Σ 7 "P= (8) = =(
(G.4)
420
Division between probability mass functions is assumed to element-wise.
Proof. Without loss of generality, prove the bound for fixed state E S, noting that the bound applics independently of our choice of s. We use the shorthand [L[x(-|s), T (-[)] + KL[T,, Tw) for brevity. We start by multiplying both sides of the bound from Proposition G.1 by 1/2 and rearranging:
Ep lx (Px)
(BBM.. KL KL + +1)
VK
2 Ep m, 2 (x(xx)
= EE.m m. Eux
KL KL nwd
2
(G.5)
( EpM:;
V V KKL(mx awd
KL ( V awd
Varyx
+ Eyx
(18)
EPM:
Epg
V KL Tw)
where (i) follows from the definition of the variance, and (ti) follows from its non-negativity. We can rearrange to get
V KL(TTT Tad
EP (EPM, KL KL +1 2 Epm, EvK
2VK
(G.6)
Ep mr Evx [drv )Tr)
where (ii) follows from Pinsker's inequality, Letting (x = - and applying Moskovitz al. (2022a), Lemma 5.2 gives the desired result.
This upper- bound is signficant, as it shows that, all else being equal, a high complexity barycenter default policy distribution Fx (where complexity is measured by KL pl) leads to a slower convergence rate in the control policy.
23

---

Published as a conference paper at ICLR 2023
Algorithm Idealized MDL-C for Multitask Learning
1: require: task distribution PM. policy class 11, coefficients }
2: initialize: default policy distribution V1 N
3: for tasks k = 1, 1. .., K do
4: Sample task M2 (.M(-)
5: Optimize control policy:
# = argmax TIll
Ag B (L
(G.7)
Mr
6: Update default policy distribution:
Mk+1
argmin p] + Bwo nwl
(G.8)
MEN
7: end for
G.1 MDL-C WITH PERSISTENT REPLAY
Rather than rely on iid task draws yield bound on the expected regret under the task distribution, a more general formulation of MDL-C for sequential task learning is described in Algorithm In this setting, the dataset of optimal agent-enviromment interactions explicitly constructed by way of a replay buffer which persists across tasks and used to train the default policy distribution. This is much more directly in line with standard FTRL,, and
obtain the standard FTRL bound.
Proposition G.2 (Persistent Replay FTRL Regret; (Orabona, 2019), Corollary 7.9). Let tasks My be independently drawn from M at every round, and let them each be associated with a deterministic optimal policy 3
A. We make the following mild assumptions: (a" [s) <> 4. E S, where a" = T.. (8) and is a constant. ii) min, KL(v(-), p()) = asymptotically as Var[u] + co.
Then with fj= L. k, Algorithm guarantees
K
1
Σ
(a(vk)
1
Σ (x(U)) (KL pl +l++1 L
(G.9)
K
K
VK*
where dK argmin
Σ =k=1 (v(
Proof. This follows directly from the arguments made in the proof of Proposition G.I.
As before, this result can be used to obtain performance bound for the control policy.
Proposition G.3 (Control Policy Sample Complexity for MDL-C with Persistent Replay). Under the setting described Proposition G.2, denote by Ty the number of iterations to reach c-error for Mj in the sense that minesTa { (VT) -V()) < In a finite MDP, from any initial ((0), and following
gradient ascent, EME~PM [Tg] satisfies:
80|A|2|812
d
EMANPM T 2
c² 7)) EMA~PM, Unils (x)
7)
1
where (r (s) = Ewwnddv (T
The (-1s)) S ViG(K),
K-1
G(K)== = ex((x) +
Σ (ex(DK) (x(wx)) + (KL[ + 1) LVK,
(s) 2[A[(1-a(s)) -]AA(1-a(3))- and μ is probability measure over S such that p(s) > 0''s S.
Proof. Without loss of generality, we select a single state s E S, observing that the same analysis applies Vs S. For simplicity, denote 7--1s) by m. We start by multiplying each side of Eq. (G.2)
24

---

Published as a conference paper at ICLR 2023
by K and rearranging:
(vxx) - Σ (x(pK) (KL[D.pl 1))
k=1
K-1
+ Ex(uk)
S Σ 4x (wx) )
Σ (x(vx) (KL(U,)) +)
(G.10)
k=1
K-1
= [x((x)) +
Σ (lx(DK) (x(vx)) (KLIZ, + LVL
km
CG(K
We multiply both sides by 1/2 and expand (x(ux)
G(K) 2 Ewauk
KL
[ nwl
2
2
2
V2 KL ( Tw)
Varex
V 2
KL|T nwd
Evi
(G.11)
(2i)
Evx
V V KL mwd
(1i2)
m=)))²
where (i) follows from the definition of the variance, (fi) follows from its non-negativity, and (fit) follows from Pinsker's inequality. We then have
En drv ( Tw) S V G(K).
(G.12)
Letting (x(s) GG() and applying Moskovitz al. (2022a), Lemma 5.2 gives the desired result.
G.2 COMMENT ON IMPROVEMENT ACROSS TASKS
To gain intuition for these bounds, there are several important values of ((s) that we can consider. First, as (ss) - 1/|A|, which is the TV distance between a uniform default policy and deterministic optimal policy, (s)
This is an important value because it's the coefficient obtained for log-barrie regularization that is, when the default policy is uniform and encodes no information about the task distribution. Next, as (s(s) >> (that is, as the TV distance between the default policy and the optimal policy decreases), ka (s) - 2|AA1/(2|A) - 1) < 2 for |A] > 1. So, we get faster as the distance between the default policy and the optimal policy decreases, as we would hope. Another crucial point to note is that as [A| co in this case, x²A (s) + 1. Finally, and importantly for MDL-C, as (s)) + - 1/2[A| from below, (xx(8) (s) - co. In other words, sufficiently bad default policy can preclude convergence entirely if it puts too much mass suboptimal action. For an illustration of this phenomenon, see Moskovitz et al. (2022a) Figure 4.1. Indeed, this why our Proposition 4.1 is useful-by effectively placing an upper bound on a(s) which shrinks as the number of tasks K increases, MDL-C's default policy is guaranteed to a) avoid putting too much mass on suboptimal action and thereby preclude or delay convergence for the control policy, and b) improve the rate as the default policy regret drops.
G.3 PARALLEL TASK SETTING
An overview of MDL-C as applied the parallel task setting is presented in Algorithm 3. One important feature to note is the return threshold R As a proxy for the control policy converging to πद. data are only added to the default policy replay buffer when a trajectory return is above this threshold performance (on DM control suite tasks, R corresponded to test reward of at least 700).
25

---

Published as a conference paper at ICLR 2023
Algorithm 3: Off-Policy MDL-C for Parallel Multitask Learning
1: require: task distribution P.M. policy class
2: initialize: default policy distribution E N, control replay Do + 0, default replay D +
3: initialize control policy parameters and default policy distribution parameters ø.
4: while not done do
5: for episodes k: .., do
6: Sample task M2 ~ PM(()) with goal ID feature 9k
7: Collect trajectory (8o, do ro, ........ 88--8111111 aH (H-1, ~ (.)(.), store experience
De t DR-1 U ((5n, (h, Th, 8n+1) H-1
(G.13)
where 8n, = (sh.gk)) gh).
8:
if R(() 2 Re (i..., ne & me then
9:
Add to default policy replay:
Dt + Di U (()))))(1))))
(G.14)
Note that, e.g., when Ta( Naa ((8, gk): E18, gx)) is Gaussian policy, 1u( (h Ih), E(h,. Ih) are added to the replay with 8/.
end if
11:
end for
Update Q-function(s) as Haarnoja al. (2018).
13:
Update control policy:
+ argmin Euiifo [V a.Eun KL KL(TTo (-(B0)) T (-18n))
(G.15)
14:
Update default policy distribution:
Φ + argmin KL (-), p(-] + Eunir of
Bewn (L(To (-15Aa)
(G.16)
15: end while
We leave more in-depth theoretical analysis of this setting future work, but note that as the task experience is interleaved, The E, will converge to the prigh-weighted KI. barycenter. If, in expectation, this distribution a TV distance of less than 1/| from mi. then the control policy will converge faster than for log-barrier regularization (Moskovitz et al., 2022a).
H ADDITIONAL EXPERIMENTAL DETAILS
Below, we describe experimental details for the two environment domains in the paper.
H.1 FOURROOMS
As input, the agent receives a 16-dimensional vector containing the index of the current state, a flattened 3 local view of its surrounding environment, its previous action taken encoded dimmensioonal one-hot vector, the reward on the previous timestep, and a feature indicating the goal state index. The base learning algorithm in all cases is advantage actor critic (A2C; (Mnih al., 2016)).
Environment The FOURROOMS experiments are set an x 11 gridworld. The actions available to the agent are the four cardinal directions, up, down, left, and ri right. and transitions are deterministic. In both FOORS experiments, the agent can begin an episode anywhere in the environment (sampled uniformly at random), and single location with reward 50 is sampled at the beginning of each episode from a set of possible goal states which varies depending on the experiment and the current phase. A reward of -1 is given if the agent contacts the walls. All other states give a reward of zero. Episodes end when either a time (number of timesteps) limit is reached the agent reaches the goal state. Observations were 16-dimensional vectors consisting of
26

---

Published as a conference paper at ICLR 2023
the current state index (1d), flattened 3 x 3 local window surrounding the agent (includes walls, but not goals), a one-hot encoding of the action on the previous timestep (4d), the reward on the previous timestep (Id), and the state index of the current goal (Id). In the "goal generalization" experiment, goals may be sampled anywhere in either the top left or bottom right rooms in the first phase and either the top right or bottom left rooms in the second phase. Each phase comprises 20,000 episodes, and in each phase, the agent may start each episode anywhere in the environment. In the first phase, the agent was allowed 100 steps per episode, and in the second phase 25 steps. In the "contingency change" experiment, the possible reward states in each phase were the top left state and bottom right state. In the second phase of training, however, the semantics of the goal feature change from indicating the location of the reward to the location where it is absent. Each phase consisted of 8,000 episodes with maximum length 100 timesteps. Results are averaged over 10 random seeds.
Agents All agents were trained on-policy with advantage actor-critic (Mnih et al., 2016). The architecture was a single-layer LSTM (Hochreiter and Schmidhuber, 1997) with 128 hidden units. To produce the feature sensitivity plots in Fig. 5.1c, a gating function was added to the input layer of the network:
Zh (bk)) @ O
(H.1)
where o is the current observation, (-) was the sigmoid funcion, E IR is a constant (set to 150 in all experiments), 24, Rd is the filter layer output, and E Rd is parameter trained using backpropagation. In this way, as Fa + oo, (bra)) - 1, allowing input feature on, d through the gate. As Ki + -oo, the gate is shut. The plots in Fig. 5. track a (bwaa) over the course of training. The baseline agent objective functions are as follows:
(P) = V + al HiTT (-|s)]
J (0, Ø) = V - aBBand (Te (-1s), [-[-s
(H.2)
-DDO-PO EEwny VT (KL p())
JManuallA/ (0,0) -V aB KL (-1s), [
8a 5
In all cases a = 0.1, 8 = 1.0, and learning rates for all agents were set to 0.0007. Agents were optimized with Adam (Kingma and Ba, 2014). Agent control policies were reset after phase 1.
H.2 DEEPMIND CONTROL SUITE
Environments/Task Settings We use the wa ler and cartpole environments from the Deep- Mind Control Suite (Tassa et al., 2018). We consider two multitask settings: sequential tasks and parallel tasks. All results are averaged over 10 random seeds, and agents are trained for 500k timesteps. In the sequential task setting, tasks are sampled one at a time without replacement and solved by the agent. The control policy is reset after each task, but the default policy is preserved. For methods which have a default policy which can be preserved, performance on task k is averaged over runs with all possible previous tasks in all possible orders. For example, when walker -erurruunn run is the third task, performance is averaged over previous tasks being stand then walk and wa 1k then stand. In the parallel task setting, different task is sampled randomly at the start of each episode, and a one-hot task ID vector is appended to the state observation. Learning was done directly from states, not from pixels.
Agents The base agent in all cases was SAC with automatic temperature tuning, following Haaroja et al. (2018). Standard SAC seeks to optimize the maximum-entropy RL objective:
(H.3) Effectively, then, SAC uses a uniform default policy. The RPO algorithms with learned default policies replace KL(m(-Is), Unif_] with (...( (or (L(m=((-ss) (-|ss)). As MDL-C, RPO, and TVPO require that the control policy approximate the optimal policy before being used to generated the learning signal for the default policy, in the sequential setting, the default policy is updated only after halfway through training. Because variational dropout can cause the network to over-sparsify (and not learn the learn adequately) if turned on too early in training, we follow the strategy of Molchanov et al. (2017), linearly ramping up a coefficient 3 on the variational dropout KL from 0 to I starting from 70% through training 80% through training. Note that MANUALIA A is not.
Jmax- entt (x:) = V" +a H[x[-sss)] = V* + alEy-a (L(sss)s), Uni
27

---

Published as a conference paper at ICLR 2023
applicable to the sequential task setting, there is explicit goal feature. In the sequential task setting, we took inspiration from Haarnoja et al. (2018) and Abdolmaleki et al. (2018) and reframed the soft KL penalty for methods with learned default policies as a constraint, i.c..
max V o.EKL[TT x|
max V s.t. EKL Ta x S c,
where > 0 was target KL divergence. Under this formulation, is treated dual variable via Lagrangian relaxation and optimized with the following objective:
max (() EoKL Nw: क. ac.
a a20
In the parallel task setting, we convert the base SAC agent into the "multitask" variant used by Yu al. (2019), which the agent learns vector of temperature parameters [ai..... 0kk). one for each task. In this setting, we found it more effective to set to constant value. Test performance was computed by averaging performance across all K tasks presented to the agent. The baseline agent objectives are as in Eq. (H.2), and the Distral objective is given by
D (0,4) Φ) V a.
<-[+s)]] AE H [=(()))]]-
TVPO is trained in the same way as RPO, with the difference being that the default policy objective to predict the control policy action, rather than a distillation objective. Hyperparameters shared by all agents can be viewed in Table 2.
As a note on performance, Distral performs very strongly in the parallel task setting, with overall performance slightly worse than MDL-C on Walker and virtually the same Cartpole. However, the gap is significantly greater in the sequential setting, particularly on Walker. We hypothesize that this is due the fact that by regularizing the control policy to be close the default policy, but also encouraging the control policy to have high entropy (rather than regularizing the default policy MDL-C does), Distral can in effect provide conflicting objective the control policy when strong structure is present. In particular, on Walker, the optimal policies for each task have significant overlap, and so by encouraging high entropy in the control policy even on the third task, Distral negates the effect of an informative default policy. As evidence, both RPO and TVPO, which only regularize the control policy be close to the default policy, perform significantly more strongly on Walker in the sequential setting.
Hyperparameter
Value
Collection Steps
1000
Random Action Steps
10000
Network Hidden Layers
256:256
Learning Rate
3 10-
Optimizer
Adam
Replay Buffer Size
10
Action Limit
[-1, 1]
Exponential Moving Avg. Parameters
5 10
(Critic Enviine:Eni Step) Ratio
(Policy Update:Environment Step) Ratio
Expected KL/Entropy Target
0.2/ dim (AA)
Policy Log- Variance Limits
20, 2
Table 2: DM control suite hyperparameters, used for all experiments. "In the parallel setting, was simply set to for methods with learned default policies.
I ADDITIONAL EXPERIMENTAL RESULTS
I.1 FOURROOMS
1.2 DEEPMIND CONTROL, SUITE
28

---

Published as a conference paper at ICLR 2023
Method
Goal Change
Contingency Change
PO
1.25e5 + 1.76e4
8.80e4 + 1.64e4
RPO
1.77e5 + 1.11e4
1.04e5 = 2.20e4
VDO-PO
1,48e5 + 1.91e4
8.23e4 = 1.98e4
ManualIA
1.23e5 + 2.51e4
7.69e4 + 2.89e4
MDL-C
1.08e5 + 2.44e4
5.1 + 1.70e4
Table 3: FourRooms: Average cumulative regret across random seeds phase goal change and contingency change experiments for each method. + values are standard error.
Method
Cartpole
Walker
SAC
1.25e5 + 1.76e
3,42e5 + 6.10e4
RPO-SAC (I: = 3)
1.77e5 = 1.11e4
1.04c5 = 2.20e4
VDO-SAC
1.48c5 = 1.91e4
8.23e4 = 1.98e4
MDL-C (k: 1)
1.23e5 + 2.51e4
7.69e4 + 2.89e4
MIL-C (k:
1.08e5 2.44e4
5.11e4 + 1.70e4
MDL-C (k = 3)
1.08e5 = 2.44e4
5.11e4 = 1.70e4
Table 4: DM Control Suite, Sequential: Average cumulative regret across 8 random seeds in the sequential setting. + values are standard error.
Method
Cartpole
Walker
SAC
1.0155 2.01e3
1.46e5 + 5.11e3
ManualIA
9.90c4 = 1.87c3
1.50e5 + 3.86e3
MDL-C
9.47e4 8.36e2
1.31e5 + 1.35e3
Table 5: DM Control Suite, Parallel: Average cumulative regret across 8 random seeds in the parallel task setting. + values are standard error.
RPO
MDL-C
0.70
0.70
068
0.6
0.66
0.66
0.64
0.64
Figure I.1: Heatmaps of where w E, for MDL-C, averaged over all possible goal states. The RPO default policy nearly perfectly matches the control policy, while the MDL-C default policy diverges most strongly from the control policy the doorways. This because the direction chosen by the policy in the doorways is highly goal-dependent. Because the MDL-CC default policy learns to ignore the goal feature, it's roughly uniform in the doorways, whereas the control policy is highly deterministic, having access to the goal feature.
T-((-1s) Vs E S for RPO and (L(mo(-Is), (-1s] Vs E S,
29

---

Published as a conference paper at ICLR 2023
walker (parallel)
cartpole (parallel)
feature weight
08
08
04
04
position
0.2
velocity
02
velocity
task
task
16000
96200
144000
192000
242000
28000
56000
#1000
112000
110000
timesteps
timesteps
Figure I.2: Without sparse prior, RPO does learn ignore spurious input features.
walker (sequential)
cartpole (sequential)
0.4
S0000
100000
150000
200000
2500000
$0020
100000
150000
200000
252020
timesteps
timesteps
Figure I.3: MDL-C's learned in the DMC sequential setting. Because tends to decay, the control policy is able to specialize to the current task later in training. Results averaged over eight random seeds; error shading denotes standard error.
walker (parallel)
cartpole (parallel)
ManualIA
700
ManuallA+
test reward
MDL-C
500
200
400
100
50000
100000
150000
200000 250000
20000 40000
60000
80000
100000
120000 140000
timesteps
timesteps
Figure 1.4: To test the effect of information asymmetry on its on performance, we trained a variant of MANUAL.IA in which we withheld the input features that MDLL-C learned gate out (Fig. 5.2) in addition to the task ID feature. We call this modified method MANUALIA+. Average performance is plotted above over seeds, with the shading representing one unit of standard error. We can see that while MANUALIA+ narrowly outperforms MANUALIA, the performance gains of MDL-C can't solely ascribed to effective information asymmetry.
30

---

Published as a conference paper at ICLR 2023
stand (parallel)
walk (parallel)
run (parallel)
1880
t2st neward
600
RPO
MOL-C
180006
30000
40000
50000
140000
20083 30083
40000
50000
100000 3008
40000
timesteps
timesteps
Figure I,5: Test reward on each individual task in the walker domain over the course of parallel task training. Average performance is plotted above over 10 seeds, with the shading representing one unit of standard error. We can see the biggest performance difference on walker, run, the most challenging task.
balance (paralla))
(paralle)
balance (paralla)
(paralel)
MBLC
Figure 1.6: Test reward on each individual task in the cartpole domain over the course of parallel task training. Average performance is plotted above over 10 seeds, with the shading representing one unit of standard enror. Interestingly, unlike in the sequential learning setting, joint training seems to impede performance on swingup.sparee with no method succeeding.
31


Reviews:
[{"review_id": "u38MpFrcnK_", "reviewer": "Reviewer_DtWg", "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": "", "summary_of_the_paper": "This paper studies multitask RL and proposes a new framework based on minimum description length (MDL) principle, called MDL-control (MDL-C). The framework contains the learning of the control policy and the default policy. The control policy is trained according to Regularized Polic Optimization regarding the default policy, which is expected to learn the common structure; while the default policy (distribution) is formalized as the hypothesis that meets the MDL principle. Sparsity-inducing priors and variational dropout are motivated and adopted for the effective implementation of learning the default policy distribution. This paper also presents the theories on the regret upper bound of the default policy and the complexity of learning near-optimal control policy. In the experiments, the proposed method is evaluated in FoorRoom and DMC suite with multiple settings, demonstrating the effectiveness in learning desired default policy and the superiority over the considered baseline methods.", "summary_of_the_review": "According to my detailed review above, I think this paper is marginally above the acceptance threshold mainly due to the novelty of the proposed framework along with the theoretical results.", "strength_and_weaknesses": "$\\textbf{Strengths:}$\n+ The paper is well written and organized.\n+ The theoretical results of the proposed algorithm is discussed (for both the control policy and the default policy).\n+ The related work and background are well enclosed and connected in the text.\n+ Multiple settings and evaluation/analysis aspects are considered in the experiments.\n\n&nbsp;\n\n\n$\\textbf{Weaknesses and Questions: }$\n\n\n\nAccording to Algorithm 3 in the appendix, the default policy replay is only added when the control policy is near-optimal, based on which the default policy distribution is trained. Meanwhile, the control policy has a KL constraint on the default policy distribution. I am wondering how the initial phase is dealt with, in another word, is it possible that the initial default policy distribution prevents the control policy from learning a near-optimal policy and in turn the default policy replay remains empty?\n\nI think this may be related to a proper scheduling of the hyperparameter $\\alpha$. Thus, how is $\\alpha$ selected or scheduled? And how different choices of the value or schedule influence the performance?\n\n\n&nbsp;\n\n\n\nFor the experiments, my first question is on the baseline method RPO. According to the formulation in Equation H.2, assuming $\\pi_{\\phi}$ to be the default policy, what does ‘regularized policy optimization with no constraint on the default policy (RPO)’ mean? Does it mean that the $\\pi_{\\phi}$ is learned by MLE (or Behavior cloning), i.e., without adopting the KL with a prior distribution?\n\n\n&nbsp;\n\n\nI recommend the authors to additionally consider other domains and tasks in DMC suite (e.g., Finger and Quadruped). Two domains are insufficient to me for a convincing experimental evaluation.\n\nI appreciate that the authors provide the feature weight curves which help a lot in understanding the effectiveness of MDL-C. I am curious about the feature weight curves of the baseline methods (e.g., PO and RPO), can the authors provide the curves especially for DMC? If not, what is the reason?\n\nAnother question is, why is RPO not considered in the parallel setting? And similarly, ManualIA is not shown in the sequential setting.\n\n\n&nbsp;\n\n\nFinally, as the authors present a motivation from the perspective of generative model of optimal policy parameters, with on a group-based assumption. I think it will be interesting and insightful if the authors analyzes the learned optimal parameters (since a shared policy may be used, it may consider the learned representation of features) a posteriori.\n", "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": "Hbam7Wmo_j", "reviewer": "Reviewer_rmSg", "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": "", "summary_of_the_paper": "The paper introduces a new perspective for multi-task RL that to distill each control policies in each task using techniques inspired from the minimum description length principle. Specifically, the proposed algorithm learns a policy parameters distribution that both contains the control policy parameters and constraint to be close to the sparsity induced prior. The paper then shows some motivation of the minimum description length control with some constructed scenarios and show the performance analysis in the tabular case. Finally, the paper has some experiments on both synthetic and popular RL benchmarks. ", "summary_of_the_review": "Overall the idea of enforcing simpler representations into multi-task RL is quite interesting. However, the theory result is a little underwhelming, and the experiments may need stronger baselines. Also there is still some confusion around the current version. Thus I would recommend a weak reject at this point. ", "strength_and_weaknesses": "# Strength\n* The usage of the sparsity induced prior is nicely motivated throughout the paper, the intuition seems quite natural under the paper's constructed scenarios. \n* The paper contains both theory and practical results. \n* The overall flow of the paper is good and well organized.\n\n# Weakness\n* The paper's theoretical study seems a little underwhelming given that it's only in the tabular case, and thus the results do not seem super exciting (more on this below). For example, some recent theory paper already studies multi-task RL in the linear case [1,2,3].\n* The literature review does not seem complete, some previous works in multi-task RL are missing, for example, [4]\n* Is there any reason that the paper does not include the deep multi-task RL baselines in the experiments? The current baselines do not seem super strong, especially if we want to compare in the dm control suite benchmark.\n\n# Questions:\n* Despite the analysis is conducted in the tabular case, the $(1-\\gamma)^{-6}$ rate looks quite suboptimal. Intuitively this rate should have nothing to do with the multi-task setting itself. It would be great to have some clarification.\n* I am rather confused about the rate w.r.t. the number of task $K$. I may overlook something but is the current result saying that $\\kappa^{\\alpha^k}$ stays rather constant despite $K$? Thus what's the benefit here in terms of an increasing number of tasks?\n\n[1] Pacchiano, A., Nachum, O., Tripuraneni, N. and Bartlett, P., 2022. Joint Representation Training in Sequential Tasks with Shared Structure.\n\n[2] A. Agarwal, Y. Song, W. Sun, K. Wang, M. Wang, and X. Zhang. Provable benefits of representational transfer in reinforcement learning.\n\n[3] Y. Cheng, S. Feng, J. Yang, H. Zhang, and Y. Liang. Provable benefit of multitask representation learning in reinforcement learning.\n\n[4] Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Fj_PKNjzIpu", "reviewer": "Reviewer_TuJe", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper deals with the relevant multi-task RL problem. The authors propose a novel method that follows the \"minimum description length\" principle, to learn a common structure between the tasks. The aim of the proposed approach is to improve the generalization. The authors provide sample complexity results in the finite state-action spaces and provide some experiments to show the effectiveness of the novel algorithm.", "summary_of_the_review": "See Weaknesses and Strengths.", "strength_and_weaknesses": "Strengths:\n\n- The problem is relevant to the community.\n\n- As far as I know, the idea of using the \"minimum description length\" principle is novel and well-motivated. The idea is very interesting.\n\n\nWeaknesses:\n\n- The main weakness of the paper is the clarity. The paper, in general, is well-written, but some parts are hard to be understood and the connection with the SotA is not very clear. For example, what is the main difference between the proposed method and Moskovitz 2022? I am sure that there are differences between the two approaches, but I would like to see this difference written more clearly in the paper. \n\n- The performance analysis section could be improved. For example, this sentence is not very clear:\n\"is to obtain an upper bound on the average KL between default policies sampled from the default policy distribution and an optimal policy for a task sampled from the default policy distribution\"\nMaybe is a task sampled from the task distribution? \n\n- Default policy performance section: The connection with FTRL is quite interesting, although here we are not in an adversarial setting, so we are more interested in minimizing the internal regret instead of the external one, or am I missing something? \n\n- Control policy performance section: In proposition 4.2, the $\\ge$ is a typo and has to be instead a $\\le$? Why do we have this dependency of $(1-\\gamma)^6$?\n\n- Experiments: why the authors do not compare their method with the principled RPO algorithm proposed in Moskovitz 2022 (TVPO)? \n\n- The plots are not readable for color-blind people.", "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": {}}, {"review_id": "A_q2L6ABuT", "reviewer": "Reviewer_uHBy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "summary_of_the_paper": "This paper provides a method of combining the minimum description length principle to the finding of optimal policies for multitask RL problems. This allows the model to trade off between adapting to new information, and maintaining simplicity, thus adapting to epistemic uncertainty naturally.\n\nAfter introducing the method, the paper provides discussions about interpretations of some key terms, and carries out some theoretical analyses regarding performance and sample complexity. \n\nExperiments are carried out in the FOURROOMS environment and the DeepMind Control suite against several baselines. ", "summary_of_the_review": "My score is based on the fact the seeming novelty of the work, how well it is written, as well as the suite of experiments carried out. I wasn't able to check the correctness of the theory. ", "strength_and_weaknesses": "### Strengths\n- Good structuring of the exposition. \n- Clear intuitive explanation before jumping into the maths\n- Nice theoretical analysis\n- Experiments seem good, with both simple and complex tasks. \n\n### Weaknesses\n- Some paragraphs could be split up.\n- ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster