Minimal Value-Equivalent Partial Models for Scalable and Robust Planning in Lifelong Reinforcement Learning
Authors: Safa Alver
Doina Precup
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning
lifelong learning
transfer learning
model-based reinforcement learning

Abstract: Learning models of the environment from pure interaction is often considered an essential component of building lifelong reinforcement learning agents. However, the common practice in model-based reinforcement learning is to learn models that model every aspect of the agent's environment, regardless of whether they are important in coming up with optimal decisions or not. In this paper, we argue that such models are not particularly well-suited for performing scalable and robust planning in lifelong reinforcement learning scenarios and we propose new kinds of models that only model the relevant aspects of the environment, which we call minimal value-equivalent partial models. After providing the formal definitions of these models, we provide theoretical results demonstrating the scalability advantages of performing planning with minimal value-equivalent partial models and then perform experiments to empirically illustrate our theoretical results. Finally, we provide some useful heuristics on how to learn such models with deep learning architectures and empirically demonstrate that models learned in such a way can allow for performing planning that is robust to distribution shifts and compounding model errors. Overall, both our theoretical and empirical results suggest that minimal value-equivalent partial models can provide significant benefits to performing scalable and robust planning in lifelong reinforcement learning scenarios. 

Under review as a conference paper at ICLR 2023
MINIMAL VALUE-EQUIVALENT PARTIAL MODELS FOR SCALABLE AND ROBUST PLANNING IN LIFELONG REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Learning models of the enviromment from pure interaction often considered an essential component of building lifelong reinforcement learning agents. However, the common practice in model-based reinforcement learning is to learn models that model every aspect of the agent's 's environment, regardless of whether they are important in coming up with optimal decxisions or not. In this paper, we ar- gue that such models are not particularly well-suited for performing scalable and robust planning in lifelong reinforcement learning scenarios and we propose new kinds of models that only model the relevant aspects of the environment, which we call minimal value-equie equte-equivleen partial models. After providing the formal defini- tions of these models, we provide theoretical results demonstrating the scalability advantages of performing planning with such models and then perform experi- ments to empirically illustrate our theoretical results. Finally, we provide some useful heuristics on how to learn these kinds of models with deep learning archi- tectures and empirically demonstrate that models learned such way can al- low for performing planning that is robust to distribution shifts and compounding model errors. Overall, both our theoretical and empirical results suggest that mini- mal value-equivalent partial models can provide significant benefits to performing scalable and robust planning in lifelong reinforcement learning scenarios.
INTRODUCTION
It has long been argued that in order for reinforcement learning (RL) agents to perform well in lifelong RL (LRL) scenarios, they should be able to learn a model their environment, which allows for advanced computational abilities such as counterfactual reasoning and fast re-planning (Sutton & Barto 2018 Schaul et al., 2018 [Sutton et al., 2022). Even though this is a widely accepted view in the RL community, the question of what kinds of models would better suite for performing LRL still remains unanswered. As LRL scenarios involve large environments with lots of irrelevant aspects and periodic non-periodic distribution shifts, directly applying the ideas developed in the classical model-based RL literature (see c.g., Ch. 8 of SStton & Barto 2018) to these problems is likely to lead catastrophic results in building scalable and robust lifelong learning agents. Thus, there is a need to rethink some of the ideas developed in the classical model-based RL literature while developing new concepts and algorithms for performing model-based based RL in LRL scenarios.
In this paper, we argue that one important idea to reconsider is whether if the agent's 's model should model every aspect of its environment. In classical model-based RL, the learned model is model over every aspect of the environment. However, due to the large state spaces of LRI. environments, these types of models are likely to lead to serious problems performing scalable model-based RL, i.c., in quickly learning model and in quickly performing planning with the learned model to come up with an optimal policy. Also, due to the inherent non-stationarity of LRL environments, these types of detailed models are likely to lead to models that overfit to the irrelevant aspects of the environment and cause serious problems in performing robust model-based RL, i.e., learning & planning with models that robust distributions shifts and compounding model errors.
To this end, we argue that models that only model the relevant aspects of the agent's environ- ment, which we call minimal value-equivalent partial models, would be better suited for performing

---

Under review as a conference paper at ICLR 2023
model-based RL in LRL scenarios. We first start by developing the theoretical underpinnings of how such models could be defined and studied in model-based RL. Then, we provide theoretical results demonstrating the scalability advantages, i.c., the value and planning loss and computational and sample complexity advantages, of performing planning with minimal value-equivalent partial models and then perform several experiments to empirically illustrate these theoretical results. Fi- nally, we provide some useful heuristics on how to learn these kinds models with deep learning architectures and empirically demonstrate that models learned in such way can allow for perform- ing planning that is robust to distribution shifts and compounding model errors. Overall, both our theoretical and empirical results suggest that minimal ealivlequivalentt partial models can provide significant benefits to performing scalable and robust model-based RL in LRL scenarios. We hope that our study will bring the community a step closer in building model-based RL, agents that are able to perform well in LRI. scenarios.
2 BACKGROUND
Reinforcement Learning. In RI. (Sutton & Barto 2018), an agent interacts with its enviromment through a sequence of actions to maximize its long-term cumulative reward. Here, the environment is usually described as a Markov decision process (MDP) M = (S, A. P. R, 7), where S and A are the (finite) set of states and actions, P A + [0, I] is the transition distribution, R S'A + [0, Rmax] is the reward function, and 7 E [0, 1) is the discount factor. On the agent's 's side, through the use of a perfect state encoder 6- S + F, every state s E S can be represented, without any loss of information, as an n--imensional feature vector
[fi, f2..... fn] E F, which consists of n different features FF = [[a] where Si E Fi Vi E {1...., n (also see Boutilier et al. (2000) Note that there is no loss of information, IF contains all the possible features that are relevant in describing the states of the environment. Thus, from the agent's 's side, the MDP M can losslessly be represented another MDP m = (F,A,p" r", 7), where F and A are the (finite) set of feature vectors and actions, p¹ F x A x F + [0, 1] and r- F x A + [0, Bmaa]] are the transition distribution and reward function, and y E [o, 1) the discount factor. For convenience, we take the agent's 's view and refer to the environment as m throughout this study. The goal of the agent is to learn value estimator Q x A + that induces policy ग E II = {क : x A [0, 1]]. maximizing Ex Fx,,- - (Fz, A.) Fol for all Po F.
[=]
Model-Based RL. One of the prevalent ways of achieving this goal is through the use of model- based RL methods in which there are two main phases: the learning and planning phases. In the learning phase, the gathered experience is mainly used in learning an encoder Φ :S + F and model = (p.r) M (p,r) p F A x F - 10, F A + [0, Rmaxx 1) and optionally, the experience may also be used in improving the value estimator. In the planning phase, the learned model is then used either for solving for the fixed point of a system of Bellman equations (Bellman 1957). or for simulating experience, either to be used alongside real experience in improving the value estimator, or just be used in selecting actions at decision time (Alver & Precup 2022 Sutton& & Barto 2018).
Value-Equie Equivalllvveeecee One of the recent trends in model-based RL is to learn models that are specifi- cally useful for value-based planning (see e.g., (Silver et al. 2017 Schrittwieser et al. 2020), which has been recently formalized several different ways through the studies of Grimm al. (2020) 2021). Inspired by these studies, we define related form of value-equivalence as follows. Let V E RR be the value vector of policy π E IT evaluated in model m, whose elements are defined vf E F as V (f) = =Er.p 12 (IF,, A:) f), and let V E 1 be the optimal value vector in model m. We say that model m E MM is value-equivalent (VE) model of the true environment m E . if the following equality holds:
V = m
VT E II,
where ,,, is an optimal policy obtained as a result of planning with model m..
3 MINIMAL VALUE-EQUIVALL
PARTIAL MODELS
In classical model-based RL (Ch. 8 Sutton & Barto 2018), an agent learns a very detailed model of its environment that models every aspect of it, regardless of whether these aspects are relevant
2

---

Under review as a conference paper at ICLR 2023
in the process of coming up with optimal decisions or not. However, in LRL scenarios, where the agent is "small" and the environment is "vast" (Schaul et al. 2018), this approach is likely to be problematic modeling every aspect of the environment becomes quite impractical. Even if the agent overcomes its capacity limitations and manages to model every aspect, as we will demonstrate, these kinds of detailed models can lead large planning losses and dramatically slowdown both the model-lcarning and planning processes. And, as we will further demonstrate, detailed models can also be fragile the distribution shifts in the environment and the compounding model errors that happen during the unrollment of the learned model. In order to overcome these challenges, we start by proposing new kinds of models that only model certain aspects, either relevant irrelevant, of the agent's environment. For this, we first start by clarifying the notion of "aspect": in this study, by "aspect", we mean a feature of the environment Si E F; that is learnable by the agent (see Sec. 2 We are now ready to define partial models:
Definition 1 (Partial Models). Given a set of features F, let Ep C. F S.t. [Epl < [F). Let Fp be space of feature vectors in which the feature vectors consist the features in Fp. We say that a model mp is partial model of the true environment m² E EM if is defined over the feature vector space Fp, Le., mp E Mp ((pp.r) rp) pp: Fp A Fp [0, rp.rp: Fp
[0, Rmax]]
According Defn. I any model that only models certain features of the environment is partial model of the environment m E .M. However, in order for partial model to be useful, it should be able to model the relevant features of the environment that allow for achieving the task of interest. In order to separate out the relevant features from the irrelevant ones, we define the relevant ones as:
Definition (Relevant Features). Given set of features F, let FR C F. Let FR be space of feature vectors in which the feature vectors consist of the features in FR. We say that the features Si FR are relevant features of the task of interest if they are necessary and sufficient for defining space of models MR {(PR. TR) PR FR x A FR + [0. TR : FR x [0, Rmaa]] that contains nalue-equivalent models of the true environment m E M.
Now that we have defined partial models and distinguished between the relevant and irrelevant features of the environment, we ready to define important class of partial models that the very least model the relevant aspects of the environment:
Definition 3 (VE Partial Models). Given a set of features F, let EVEP C. F s.t. Eveel < [F| and FR S Ever. Let FVer be space of feature vectors in which the feature vectors consist of the features in F VEP. Let MyEr be a partial model that is defined over the feature vector space FVEP, i.e., mvvER &VVEP= ((VVE,, TVEP) PvEp : FVEP A FVEP + [0, 1], TVEP : FyEP A [0, Rmax]]: We say that myEr is a VE partial model of the true environment m E if VE model of m², ie..
Yimuor IvEr, where Tauge is optimal policy obtained as a result of planning with model mVVE and IlvEP = { FUEE x A + [0, 1]].
V
Although is important to learn partial models that at the very least model the relevant aspects of the environment, as will theoretically and empirically demonstrate, partial models mostly beneficial when they only model the relevant aspects of the environment, i.e., when IF EvEr = Fg- We refer to these models as minimal VE partial models. Note that minimal VE partial models are special class of VE partial models, and VE partial models are a special class of partial models.
Illustrative Example. As an illustration of the models defined above, let us start by considering the Squirrel's World (SW) environment depicted in Fig. [ in which the squirrel's (the agent) job is to navigate from cell E1 to cell E16 to pickup the nut without getting caught by the hawk that flies back and forth horizontally along row C. At each time step, the squirrel receives input an 5x 16 image of the current state of the environment and then, through the use of pre- defined state encoder, transforms this image into a feature vector that contains information regarding all aspects of the current state of the environment, i.e., the feature vector contains information on the
10 11
15
16
s
Figure 1:
The SW environment.
3

---

Under review as a conference paper at ICLR 2023
current position of the squirrel, hawk and the cloud, the current direction of the hawk, the current wind direction in rows A and and the current weather condition. Based on this, the squirrel selects an action that either moves it the left right cell, or keeps it position fixed. If the squirrel gets caught by the hawk or it is out of time, it receives a reward of 0 and the episode terminates, and if the squirrll successfully navigates the nut, it gets reward of +10 and the episode terminates. In this environment, as the hawk moves 5x the speed of the squirrel, a straightforward policy of always moving to the right will not get the squirrel to the nut. Thus, the squireel has to come up with non-trivial policies that take into account both the cells with bushes (see e.g., cells E2, E3), which allow for sheltering, and the position and direction of the hawk.
In this environment, examples of partial models can be model that only models the cloud position and the wind direction for rows and B, or a model that only models the weather condition and the hawk's 's direction. However, for partial model to be VE or minimal VE, it has to model the relevant features for the tasks of interest which reaching the nut. In the SW environment, there are three relevant features: (i) the squirrel's position, (ii) the hawk's position, and (iii) the hawk's direction, as the squirrel would have to have access to all three these features to come up with optimal policies. Thus, an example of a VE partial model can be model that models both the three relevant features and the weather condition, and an example of a minimal VE partial model can be a model that only models the three relevant features.
4 THEORETICAL RESULTS
In this section, we first analyze the value and planning losses (Sec. 4.1 of VE partial models and then derive formal results demonstrating the computational and sample complexity benefits (Sec. of using such models. We then discuss scenarios where the VE partial model is minimal one.
4.1 VALUE AND PLANNING Loss ANALYSES
We start our formal analysis by studying the value loss incurred due to planning with a VE partial model myer in place of the true environment m². To simplify the analysis, assume that the agent already has access to this model and does not need to learn it. Theorem 1.
Let myer MYEP be a VE partial model of the true environment m E M. Then, the value loss between an optimal policy in m", π.". and an optimal policy in myEP, π Tawg is given by:
V
V
0.
m
Due to space constraints, we defer all the proofs to App. A Theorem D says that by planning with (non-minimal minimal) VE partial model, an agent would incur no value loss compared to planning with the true environment itself.
Next, study the planning loss (Jiang et al. 2015) incurred due planning with an approximate VE partial model myyr E .MVEP in place of the actual VE partial model myEr E .MVE.. Similar to Tiang et al. (2015), we also consider the vertainty-equivalen
control setting in which the agent acts according to a policy that is optimal with respect to its current approximate model.
Theorem Let MVEE E MVEP be a VE partial model of the true environment m² M, and let MIVEP E MyEP be model that comprises of the reward function of mvEP and a tran- sition distribution that is estimated from n samples for each (f,a) pair. Let Urye = {or 3 pver s.t is optimal in (pvEr, (DvEr,TvEr)), Then, certainty- -iqduitt--quvvalecce planning with myye has plan- ning loss:
| miger
Vilingar
< 2Rmax
1
log
2|
(4)
(1 7)2
2n
8
with probability at least 1
Theorem 2 implies that given a fixed amount of data, the upper bound of the planning loss of VE partial model depends on both the size of its feature vector space, [Fver]. and the size of its policy class being searched over by planning, I This in turn implies that, given a fixed amount of
Note that Fugel also affects [T [T i.e., as [Fverl grows, TTage also grows.
4

---

Under review as a conference paper at ICLR 2023
data, compared regular model, VE partial model is likely to have less planning loss and this loss is likely to be minimized when the VE partial model a minimal one.
4.2 COMPUTATIONAL AND SAMPLE COMPLEXITY BENEFITS
We now study the computational and sample complexity benefits of performing model-based RL with VE partial models. Due to the well-established theoretical results around it, we choose to study these benefits in the context of value iteration (Bertsekas & Tsitsiklis, 1996). However, we note that the implications of our results would apply to wide variety of planning algorithms.
Starting with the computational complexity benefits, well-known that the computational com- plexity of performing single step of value iteration with an arbitrary model m E M is ((IF)) (Agarwal et al. 2022). Thus, the computational complexity of performing a single step of value iteration with VE partial model myve MMEP would be O( [[[A]. This implies that com- pared to planning with regular models, planning with VE partial models would provide significant computational complexity benefit and this benefit would be maximized when the model used for planning is a minimal VE partial model.
Moving on to the sample complexity benefits, previous studies of Kearns & Singh (9988 Kakade (2003) Azar et al. (2012) have shown that the sample complexity of obtaining an estimation of the optimal action value function through the use of Q-value iteration (see Alg. I given access only to a generative model is in the order of the magnitude of the model's 's state and action space. Building on top of this result, now study the sample complexity benefits of planning with approximate VE partial models that are obtained as a result of sampling generative VE partial models.
Theorem 3. Let myer E MVER be a VE partial model of the true environment m² E M. Let MYEE&& MvEP be the corresponding approximate VE partial model that has the same reward func- tion as myEp, but whose transition distribution is estimated by m calls to the generative model myEr, where
|ueel|A (1-7))46
m =
(5)
and let Qua be the value returned by Q-value iteration at the kth epoch. Then, with probability greater than 1 8, the following holds for all f E FyEP and a A:
11Q Qimge Se,
(6)
where& k- log(e(1->)) and Quyyer the optimal action value function in myEEr- logy
Theorem 3 implies that compared to a regular model, a VE partial model is likely to require less estimation of the optimal action value function through the of Q-value iteration with a generative model, and the number of samples required is likely to be minimized when the VE partial model is minimal one.
samples in obtaining
EXPERIMENTAL RESULTS
We start this section by performing experiments to demonstrate the scalability advantages of minimal VE partial models, which are illustrations of the theoretical results derived in Sec. and then we perform experiments demonstrate the robustness advantages of these models. The details of our experiments can be found in App.
Environments. We perform experiments on both the SW environment (see Fig. D and on varia- tions of the Two Rooms Dynamic Obstacles (2RDO) environment that are built on top of Minigrid Schevalier-Boisver et al. 2018) (see Fig. [ as these environments allow for designing controlled experiments that are helpful in answering the questions of interest to this study. Some of the details of the SW environment are already presented in Sec. and we refer the reader to App. C for more details. In the 2RDO environments, the agent, depicted by the red triangle, spawns in top-left of the top room and has to navigate to the green goal cell located in the bottom- -rght of the same room, regardless of the gaseous motions of the obstacles in the bottom room. At each time step, the agent receives an image of the current state of the grid and then, through the use of a learned state encoder, transforms this image into feature vector. Based on this, the agent selects action that either turns
5

---

Under review as a conference paper at ICLR 2023
(a) 8x8 BlueBalls
(b) 8x8 RedBoxes
(c) 8x8 NoObstacles (d) 16x16 RedBalls (e) 16x16 BlueBoxes
Figure 2: Variations 2RDO environment with grid sizes of 8x8 and 16x16. In these envirouments, there
are either no obstacles (c), or there are several obstacles (balls and boxes) with different colors (a, b, d. e).
left right, or moves it forward. If the agent successfully navigates the goal cell, it receives reward of +1 and the episode terminates. More details on the 2DRO environments can be found in App. as well.
5.1 SCALABILITY EXPERIMENTS
For our scalability experiments, we perform experiments with several non-VE (m1, m2, ma) and VE (m4, ms, mş) partial models both the deterministic and stochastic versions of the SW en- vironment, referred to Det-SW and Stoch-SW, respectively. The details of these models can be found in Table I For all of our experiments, we use value iteration as our planning algorithm.
10
Plarning Time
15
Planning
20-
De
Stoch
Medels
Models
Value Loss
(b) Planning Loss
(c) Planning Time
The (a) value losses, (b) planning losses, and (c) planning times of several models. Plot (a) was obtained over single run and plots (b) and (c) were obtained by averaging over runs per model.
Figure 3:
Question 1. Do minimal VE partial models allow for planning with no value loss?
In Sec.
argued that by planning with (non-minimal minimal) VE partial model, an agent would incur no value loss compared to planning with the true environment itself. To empirically verify this, we present the agent with partial model m4, and compare the value losses on both the Det-SW and Stoch-SW environments. Results shown in Fig. 3a We can indeed that while the VE partial model incurs value loss, the non-VE VE ones do incur serious value losses.
of non-VE partial models m1, m2, my and minimal VE
Question 2. Do minimal VE partial models allow for planning with less planning loss?
In Sec. 4.1 we argued that given a fixed amount of data, compared to regular model, VE partial model likely to incur less planning loss, and this loss is likely to be minimized when the VE partial model is minimal one. For empirical verification, we compare the planning losses of a minimal VE partial model m4, two (non-minimal) VE partial models my and mc, and regular model m7, across dataset sizes of 3, 5, 10 and 20, which corresponds to the number of samples for each (f, a) pair, on the Stoch-SW environment. Results in Fig. 3b show that, as expected, VE partial models indeed incur less planning losses than regular models, and the minimal VE partial model incurs the least planning loss.
Question 3. Do minimal VE partial models provide computational complexity benefis?
In Sec. 4.2 we argued that compared to regular models, planning with VE partial models would provide a Significant computational complexity benefit and this benefit would be maximized when the model used for planning a minimal VE partial model. To empirically verify this, we present the agent with minimal VE partial model m4, two VE partial models my and mg, and a regular model m, of the Det-SW environment, and compare the average time takes to perform a single step of value iteration for each of these models. Results shown in Fig. 3el As can be seen, planning with VE partial models indeed provides significant computational complexity benefits, and this benefit maximized when the VE partial model is minimal

---

Under review as a conference paper at ICLR 2023
Question 4. Do minimal VE partial models provide sample complexity benefits?
In Sec. 4.2, we argued that compared to reg- ular models, planning with VE partial models is likely to provide a sample complexity ben- efit and this benefit is likely to be maximized when the model that is used for planning is minimal VE partial model. For empirical ver- ification, we present the agent with a minimal VE partial model my and with a regular model my as generative models, and compare the sam- ple efficiencies, as a result of performing Q- value iteration, on the Det-SW and Stoch-SW environments. In these experiments, after ev- ery episodic interaction, the agent updates its model with the collected trajectory, and then performs Q-value iteration until convergence. Re- sults in Fig. 4 show that, as expected, planning with minimal VE partial models indeed provides significant sample efficiency benefits compared to planning with regular models.
regular min VEP
Topl Roware
Total Homaad
6-
2
10
20 30
40
50
10
20
30
40
50
Epiandes
Eptendes
(a) Det-SW
(b) Stoch-SW
Figure 4: The total reward obtained a result of plan- ning with models my and my on the (a) Det-SW and (b) Stoch-SW environments. Shaded regions are standard errors over 50 runs.
5.2 ROBUSTNESS EXPERIMENTS
For our robustness experiments, we perform experiments on variations of the 2RDO environment with grid sizes of 8x8 and 16x16. For convenience, we will refer to these environments with their grid size followed by their obstacle type. For example. we will refer to the 8x8 2DRO environment with red balls 8x8 RedBalls (see Fig. 2). For all of our experiments, we use the straightforward decision-time planning algorithm of Zhao et al.] (202T) (see Alg. 2 whose details can be found in App. C As this algorithm makes use of neural networks, before moving on the robustness experiments, we try to answer the following question.
Question 5. How to learn minimal VE partial models with deep learning architectures?
So far, for illustration purposes, we have only performed experiments in which we had a direct control over the features of the agent's model (see the models in Table []. However, in realistic scenarios, the agent would have to come up on its own with a set of features to build model of the only relevant aspects of its enviromment. own features is to use neural networks in the representation of the agent's encoder, value estimator and model, and then to train end-to-end on the environment of interest. However, in order for the agent to come up with only the relevant features, it has to be trained with the right inductive biases. Even though finding the right inductive biases to train a model-free or mooellbbaedd RL agent is still an open problem in the representation learning literature (Bengio et al. 2013), in this study, we propose two inductive biases that are likely to guide the agent in coming up with only the relevant features. The first one is to only let the value estimator shape the encoder and prevent the model from doing so (see Fig. 7). In this way. the agent can be guided in learning the features that are relevant for predicting the right values in the environment. And, the second one is to train the agent across variety of environments in which the irrelevant aspects keep changing and the relevant ones stay the same. In this way, the agent can be guided in not learning the irrelevant aspects of the environment.
very popular way of letting the agent come up with its
In order to test the usefulness of these two inductive biases in coming up with only the relevant features of the environment, we compare three different agents: (i) a regular agent, AREG, that was trained on the 8x8 BlueBalls environment and whose encoder was jointly shaped by its value estimator and model, (ii) an agent, AvEs, that was again trained on the 8x8 BlueBalls environment, but whose encoder was only shaped by its value estimator, and (iii) an agent, AVES+ tyEs that was trained on the 8x8 BlueBalls, GreenBalls, PurpleBalls and YellowBalls environments and whose encoder was only shaped by its value estimator. We compare these agents on the 8x8 BlueBalls and NoObstacles environments. If the agent is successful in coming up with only the relevant features of the environment, which are the positions of the agent and the goal, and not the positions and motions of the obstacles, we would expect it to perform similarly on the 8x8 BlueBalls and 8x8 NoObstacles environments. Results the agents perform well on the 8x8 BlueBalls environment, the AREG agent completely fails on the 8x8 NoObstacles environment, demonstrating that without the necessary inductive biases agent is
shown in Fig. 5a & 5b As can be seen, even though all of
7

---

Under review as a conference paper at ICLR 2023
REG VES
50
100
VES-NE
40-
Tata Stops
-0-
20
-0-
60-
600
1268
Tolel
Tole
10-
20-
20
0.5
1.0
1.5
2.0
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
10
1.5
2.0
Time Siaps (x10P)
Time Staps (x20%)
Time Stape (x20f)
Time Steps (xte*)
(a) 8x8 BlueBalls
(b) 8x8 NoObstacles
(c) 16x16 BlueBalls
(d) 16x16 NoObstacles
Stope Staps
40
40
Total Stoos
30
1o6al
20-
10-
10-
10-
0.5
1.5
2.0
0.5
1.0
2.0
0.3
1.5
2.0
1.0
1.5
2.0
Time Steps (x109)
Time Steps 1st0f)
Time Stepw (4101)
Time Steps lxtol
(c) 8x8 RedBalls
(f) 8x8 GreyBalls
(g) 8x8 RedBoxes
(h) 8x8 GreyBoxes
100
BD
80
T08h Stegs
St82
Staps
Tubal Stops
60
60-
60-
60
20-
20
20
20
0.5
3.0 1.5 2.0
0.5 1.0
15
20
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
T Stoss (K209)
Time Stepa 0120")
Time Stees (x20%)
Time Steps balo
(i) 16x16 RedBalls
(j) 16x16 GreyBalls
(k) 16x16 RedBoxes
16x16 GreyBoxes
The total steps reach the goal in the 8x8 and 16x16 versions of the (a. c) BlueBalls, (b, d) NoObstacles, (e, i) RedBalls, (f. j) GreyBalls, (g, k) RedBoxes and (h, 1) GreyBoxes environments for the Aseo AvEs and AvEs+ME agents. Black dashed lines indicate the performance of the optimal policy the corresponding environments. Shaded regions are standard errors over 100 runs.
Figure 5:
not capable of coming up with only the relevant features itself. We also see that the Aygs agent achieves a better performance than the AREC agent and that the AyEs+ME agent achieves an even better performance than the Aves agent, demonstrating the usefulness of our proposed inductive biases in inducing models that display the behavior of minimal VE partial models. In order to test the scalability of our results, we have also performed the same experiments with 16x16 versions of the environments. As can be seen in Fig. 5c 5d obtain similar results.
Question 6. Can minimal VE partial models be useful for performing robust transfer?
As minimal VE partial models only model the relevant aspects of the environment, we would expect them to be robust to the distribution shifts happening in the irrelevant aspects of the environment. In order to test this, compare the performances of the AREG. AVES and AvES+ME agents the 8x8 and 16x16 RedBalls, GreyBalls, RedBoxes and GreyBoxes environments. Results are shown in Fig. 5e 51 As can be seen, while the AREG agent fails and the Avgs agent only shows signs of robust transfer, the AyES+ME ME agent is able to perform robust transfer without any problem. These results illustrate the ability of minimal VE partial models in performing robust transfer.
Question 7. Are minimal VE partial models more robust to compounding model errors?
As minimal VE partial models only model the relevant aspects of the environment, compared to regular models, we would expect them to be less susceptible to compounding model errors during planning. In order to test this, compare the performances of the AREa and AvEs+ME agents with search budgets of 20, 40 and 80 on the 16x16 BlueBalls environment. Note that this environment has been seen before by both of the agents. Results in Fig. 6 show that while the performance of AReO agent drops significantly with the increase in the search budget, the performance of the Aves-Me agent stays close to optimal, demonstrating the robustness of minimal VE partial models to compounding model errors.
6 RELATED WORK
8

---

Under review as a conference paper at ICLR 2023
Partial Models. In the context of RL, the ini- tial studies of partial models can be dated back to the seminal study of Talvitie & Singh (2008) which proposes to learn several models of an uncontrolled dynamical systems that are partial at the observation level. In contrast, we pro- pose to learn a single and useful partial model of a controlled dynamical system that is partial the feature level, which provides several ad- vantages such as eliminating the question of how to combine the learned models, using them for control purposes, and making them compatible with function approximation. Our work also has very close connection to the study ohao et al. (202T) which proposes a transformer- based deep model-based agent that dynamically attends to relevant parts of its state representation during plan- ning. However, our work differs in that we propose the general concept of partial models for LRL that is independent of the agent's implementation details. Lastly, another related line of research is the studies of Khetarpal et al.) (2020) 2021) on affordances which focus on building models that partial in the action space. Our study is complementary to these studies in that they can still lever- age tmon-minima or minimal) VE partial models to reduce the size of the feature space and further increase the benefits of performing model-based RL with partial models.
100
100-
20
Tosal Stows
80
Toral Steps
80-
40
50
60
.10-
0.5
Time Steps
Stees
(a) The AREG agent (b) The AvEs+ agent
Figure 6: The total steps to reach the goal in the 16x16 BlueBalls environment for the ArsE and AvEs agents with search budgets of 20, 40 and 80. Black dashed lines indicate the performance of the optimal policy in the corresponding environments. Shaded regions are standard errors over 100 runs.
halue-Equivalennee A recent trend in model-based RL is to learn models that are specifically useful for value- based planning (see e.g. [Silver et al., 2017) Oh et al., [2017] |arquharr et al., [ Schrittwieser et al., 2020; Grimm et al. 2020 (021). Even though our work also advocates the idea that models should be useful in value-based planning, our work differs in that we also argue that
the explicit partiality of the models can provide significant scalability and robustness benefits when performing model-based RL in LRL scenarios.
Planning in Learned Feature Spaces. Even though there has been recent studies that study the ef- fect of the introduction of the irrelevant features in the agent's 's learned representation (Efroni et al. 2022a b). our study differs in that are mainly interested in LRL environments in which environ- ment mostly consists of irrelevant features and the relevant features to the agent do not change over time. Our work is also different from the studies that learn models through self-supervised learning (see e.g., [Sekar et al. 2020) in that we explicitly study the structure of the learned representation having relevant and irrelevant components.
7 CONCLUSION AND DISCUSSION
In conclusion, in this study, we have introduced special types of models, called minimal VE partial models, that only model the relevant aspects of the environment and are particularly useful in LRI. scenarios. Our theoretical results suggest that these models can provide significant advantages in the value and planning losses that are incurred during planning and in the computational and sample complexity of planning. Our empirical results (i) validate our theoretical results and show that these models can scale large environments, and (ii) show that these models can be robust to distribution shifts and compounding model errors. Overall, our findings suggest that minimal VE partial models can provide significant advantages in performing model-based RL in LRL scenarios. One limitation of our work is that, rather than providing a principled method, we have only provided several heuristics for training deep RL agents that can come up with only the relevant features of the environment. However, we note that this is mainly due to the lack of principled approaches in the representation learning literature, and we believe that this limitation can be overcomed with more principled approaches being introduced in the literature. We hope to tackle this limitation in future work. Another important limitation that, due to the need to perform illustrative and controlled experiments, we have only performed experiments in the SW and 2RDO environments where there is just a single task and there is no sequence of tasks, requiring a model the same relevant features, that unfold over time. However, experiments in more environments that have this sequential nature can be helpful in further validating the advantages of minimal VE partial models in LRL scenarios, which we also hope to tackle in future work.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alekh Agarwal, Nan Jiang, Sham M. Kakade, and Wen Sun. Reinforcement Learning: Theory and Algorithms. https//rltheorybook. citoookgittubbioo. 2022.
Safa Alver and Doina Precup. Understanding decision-time vs. background planning in model-based reinforcement learning. arXiv preprint arXiv:2206. 08442, 2022.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. On the sample complexity of reinforcement learning with generative model. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1707-1714, 2012.
Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1957.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence, 35(8):1798-188 1828, 2013.
Dimitri P Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artificial intelligence, 121(1-2):49 2000.
Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. https: petps://githute com www.////www////////ooo.ooot..e/e wtmptg/ccbgooooeeeeeee gym minigrid, ii 2018.
Yonathan Efroni, Dylan J Foster, Dipendra Misra, Akshay Krishnamurthy, and John Langford. Sample-efficient reinforcement learning in the presence of exogenous information. arXiv preprint arXiv:2206.04282, 2022a.
Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Provably filtering exogenous distractors using multistep inverse dynamics. In International Con- ference on Learning Representations, 2022b. URL https: ftttt::://openevvieee net / forum?
iddRQLLLMCeEQQ.
Gregory Farquhar, Tim Rocktäschel, Maximilian Igl. and Shimon Whiteson. Treeqn and atreec: Differentiable tree-structured models for deep reinforcement learning. arXiv preprint arXiv: 2017.
Christopher Grimm, Andre Barreto, Satinder Singh, and David Silver. The value equivalence prin- ciple for model-based based reinforcement learning. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5541 Curran Associates, Inc., 2020. URL httl:hhtt:////ooooto 0ttp:///0000/./eeaaaaaeeeeeeee.0 350eeeeeeeaae000000000eeeeeeeaaa 65a358 Pwp.r.
ngs www.nneu...... cc/
Christopher Grimm, Andre Barreto, Gregory Farquhar, David Silver, and Satinder Singh. Proper value equivalence. In A. Beygelzimer. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL htttts:
het:/forum2dd=attuubbbe 2d=aabbubbtaataax......
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon on model accuracy. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 1181-1189. Citeseer, 2015.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998.
Khimya Khetarpal, Zafarali Ahmed, Gheorghe Comanici, David Abel, and Doina Precup. What can do here? a theory affordances in reinforcement learning. In International Conference on Machine Learning, pp.
PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2023
Khimya Khetarpal, Zafarali Ahmed, Gheorghe Comanici, and Doina Precup. Temporally abstract partial models. Advances in Neural Information Processing Systems, 14:1979-199 2021.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. Advances in neural
information processing systems, 30, 2017.
Tom Schaul, Hado van Hasselt, Joseph Modayil, Martha White, Adam White, Pierre-Luc Bacon, Jean Harb, Shibl Mourad, Marc Bellemare, and Doina Precup. The barbados 2018 list of open issues in continual learning. arXiv preprint arXiv: 1800000 2018.
Julian Schrittiieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7833):604 609, 2020.
Ramanan Sekar. Olch Rybkin, Kostas Danilidiis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning explore via self-supervised world models. In International Conference Machine Learning, pp. 8583-8592. PMLR, 2020.
David Silver, Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac- Arnold, David Reichert, Neil Rabinowitz, Andre Barreto, et al. The predictron: End-to-end learning and planning. In International Conference on Machine Learning, pp. 3191-3199. PMLR, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Michael H Bowling, and Patrick M Pilarski. The alberta plan for ai research. arXiv preprint arXiv:2208. 11173, 2022.
Erik Talvitie and Satinder Singh. Simple local models for complex dynamical systems. Advances in Neural Information Processing Systems, 21, 2008
Mingde Zhao, Zhen Liu, Sitao Luan, Shuyuan Zhang, Doina Precup, and Yoshua Bengio. A consciousness-inspee inssiiie planning agent for model-based reinforcement learning. Advances in Neu- ral Information Processing Systems, 34, 2021.

---

Under review as a conference paper at ICLR 2023
A PROOFS
Theorem 1. Let mver E MVEP be a VE partial model of the true environment m E M. Then, the value loss between an optimal policy in m", π and an optimal policy in myVE. T mov is given by:
V
V Tives
0.
Proof. This result directly follows from Defn.
3 Recall that, according to Defn. 3 we have:
muge m
V
Vm mage
Nvvr
(8)
which implies:
Vi
0
VT ΠyE..
(9)
Theorem Let myEr MvEr be VE partial model of the true environment m² M, and let TIVEP MvEP be model that comprises of the reward function of myEP and tran- sition distribution that is estimated from n samples for each (F,a) pair. Let Ur {i
a pver s. is optimal in (pvEr, TVEP)}. Then, certaint--quuiallncce planning with TyErr has plan- ning loss:
V
Myar
< (1 7)2
2Bmax
1
log
2 |A
(10)
20
2n
8
with probability at least 1
Proof. Similar Jiang et al. (2015), we prove Theorem 2 with two lemmas: Lemma [ translates planning loss to value error, and Lemma relates value error to a Bellman-residual-ike quantity that has a uniform deviation bound which depends on [[Trvrll
Lemma 1. For any myyE (PVEP; FvEr) with EVEr bounded by [0, Rmaax)
Vi
<
2
max J. T:F-t
| mrygr
V Miyer
1lo0
(11)
In particular, if TVEP, we have
V mayarr
Tayge Viver
max HEllryar
||
V marr
V Vinaa llo
(12)
Proof. vff E FVEP,
Vinwerr (f)
V Viriaa (f)
V
Vinwarr (f)
V
myver
(f)
(iiinnar (f)
(
V
Viteerr
(f)
(13)
(f)
(f)
frver
Tovr
marr
(f)
mover
(f)
Viitinar (f)
V Tnggr Treper
(f)
(14)
2
max
(f)
V
Vipge (f))- (f)l
(15)
RE{
Eqn. [[] from taking the max over all feature vectors on both sides of the inequality and noticing that the set of all policies is trivial superset of [ (Trvge ) If TvEP rVep, the bound
can be tightened since { (Ti " Trygs and Eqn. 12 follows.
L
Lemma 2. For any mvge (ĀvER, TVEP) with Evge bounded by [0, Rmaa] VT FVEP A.
1 Ti <
iver(f.a) Y(Pver V - Qiann (f,a)).
max JeFwreEA
1-
(16)
12

---

Under review as a conference paper at ICLR 2023
Proof. Given any policy x, define action value functions such that Qo, Q1.................... . Qu.... such that Qo = muugo and
Qn(J,a) = ()) + (ivEr(( a, (,,,,,))
(17)
where
-nn Notice that
1Q Qn-1llo0 ? max
( (Vn=) Vn-2))1
(18)
/ JEFur.OEA
S
max /EFigp.nEA
- Vn-
(19)
>/|V-11 1 - 2/
(20)
711Qn-1 Qn 2000
(21)
SO
11Qn Q0llo0 - Σ
1Q Qulloo
(22)
k=0
n-
S [|Q - Qolloe
Σ ク-
(23)
Taking the limit of n + oo, On - Q and we have,
1
1 Qo S I- -1111: - -Qolloo
(24)
This completes the proof, noticing that Qo = =Q Qmiee Vo Vinger and Qi(,aa) (ver(J.a) +
Y (pvEE a, +), Vi Vimpp)
From Eqn. 12 in Lemma and Lemma 2 we have
Vinver
2 max #Ellrvar
V
V
Viiverllo 11
(25)
< 2 max
||Q
Q miyer 11
(26)
#EllrvEr
max
10 (f, -- (fia)
(27)
JEF.m.EEA,EEl
2
< 1 7 JEFVEE.EEA.EETTTT..
max |iver(f. + (ōver af, Vini.)
2myar (f, a)
(28)
For any particular f.a, a, æ tuple, according to Hoeffding's 's inequality, 11 > 0,
((iver(J, a) + //vver(veee V Vivver Q (f,a)] >t) S 2exp (-R R2 (1 7)2
2nd
(29)
as Fyer(f, a) + (pvEr a, a). Viraan is the average of i.i.d. samples bounded in [0, Rmax/ (1xxx//111)))
- -))]
with mean Q Maver (f, a). To obtain uniform bound over all (f, a, T) tuples, we set the right-hand side of Eqn. 29 to 6/ F AlllUrverl and solve for i, and the theorem follows.
Theorem 3. Let mvEP E MVEP be a VE partial model of the true environment m E MM. Let MYVER& MVEE be the corresponding approximate VE partial model that has the same reward func- tion as MyEr, but whose transition distribution is estimated by m calls to the generative model myvEr, where
( [iveellA)
m =
(30)
and let Qi be the value returned by Q-value iteration at the kth epoch. Then, with probability greater than 1 8. the following holds for all f E FVEP and A:
|1Q Qiinge bo Se
(31)
where k- log(s(1-71) and Qimper is the optimal action value function in myyrr- logy
13

---

Under review as a conference paper at ICLR 2023
Proof. Before starting the proof, let first define generative models. A generative model, sampler, a model that can provide us with samples f' ~ p(f. a, )) for all f FVEr and a E A. Now that have defined generative models, let assume we have access myEr and suppose we call our this model N times at each (f,a) pair. Let á be the transition distribution of our empirical model, defined as follows:
generative model
E Ci=T:
a count( f, a, 8)
(32)
N
where Si ~ pff,a, a, ) vi E (1...., N). and count( 8') is the number of times the pair (f,a) transitions to f
Moving on the main proof, by adding and subtracting Q follows:
Tiverr Onver
we can rewrite Q
Qmvon as
Qunwer - Vinger
T inver Q
+ Q
T mmyer
Q
(33)
rivarr
rrvver
ringep
(5)
(6i)
Bounding Term (i):
Q maver
max J
(vEr(f,a) + YDVER rPvErVeK-L (f (IVEr(f.a) + YDVEP
V (F,a))
Fayarr
00
(34)
max JEFom
? pVEP
(V-1
V Tayeer mayer
(f:a)
(35)
V Avvr
1100
(36)
S Y max fe3
max aEA
+#-
Maggr
(f(
-ma Q aEA
max
maye
(f.a)
(37)
max S
Q (f,a)
Tinver riverr
(f,a)
(38)
=> - muge
(39)
Unrolling the last inequality times, we obtain:
|| @ - Q
5 x 11
arysP Q
(40)
5 1-7
(41)
Bounding Term (is):
(Qiiee Qi (S,a) = ViVER V (J,a) "VDVEP Vo (n,
(42)
= 7 (ŌvEr PVEr) Vi (f,0) - YpVEr (Viines
(f,a)
(43)
7 (ŌVER pVFP) Vinunn (S,u)
(44)
Σ pvve(ss 8') Q MEF
Taver (f',a')
(f',a))-
max a'EAA
O'EA
Therefore,
Tinee Q
Qinnge
S
max JEFIgA
(δVEr PVEP) Vi (f. a)) + +
-iinge
(45)
<
γ
(ivEr PVER) V
(46)
1-7
14

---

Under review as a conference paper at ICLR 2023
Fix (f,a) pair:
(δvEr pver) V
Viver
V
maga (f)) ( Viree (f')
(47)
N
1=1
N (SN - E[SN)),
(48)
where SN = Σm= X, and X; = V (fi). X; are random independent variables and |X Σ
1
1-7"
Applying Hoeffding's s inequality, we obtain A1. > O:
1 N
N226
p
(SN E[Sw]) 2t) - 2 exx
(V/(1-2)3
(49)
= 2 exp
(-No((L- - (1)))
(50)
(θVEP - PVEP) Vinve (s: a)) 21) = =3(3 s.t. (iVEr - -VEP) Vinee (,,) 2
p
max SEFvraaEd
(51)
Σ p (((VEr - PVEP) Vinger (f, a) 2 t)
fEF,aEA
(Union Bound)
F A exp (-NP(1-7))
(52)
Let the failure probability 8 > 0. Solve for I
2| |l exp (-Nee(1 7) =t
(53)
log(2/ [gg FVER [A/5))
(54)
N
With probability at least 1 - 8,
inver ravee
VinVEr
S
max /EFir.nEE
(pvEr - PVEP)
V* muger 11
(55)
7
log F FVEPl |A188)
(56)
(1 - 7)3
N
We conclude
Q @ungze
bl 1 @t
Q
Tavar Sevver
10
+
Q Tanee
Qinyee
(57)
'lo(2) (2(FFvEEPl [2/FFp||AA// |||15)
7 < (1 7)) + (1 (1- V
(58)
N
By choosing
k: log(2(1 - -7)/E)
log
and
4-2
N
(1 - 4g- FIEellA|/))
we get Q - Q < c/2 e/2 c. Therefore, the total number of samples (calls to the generative model) to get an e estimation of the optimal Q-value is:
||FvEe|IA| = (11 | AA]
(59)
(1 182
15

---

Under review as a conference paper at ICLR 2023
B ALGORITHM PSEUDOCODES
Algorithm Model-Based Q- Value Iteration
1: Initialize the parameters //0 = 0 and Q"
2: for episode k .....,
.., K do 3: for (S.a) E F A do
4: (²,)a = r( + +zpVk-1([.a) (*()) m (f.ca
5:
6: end for
7: end for
8: Return QK
Algorithm 2 The Straight-Forward Decision-Tine Planning Algorithm of Zhao et al. (2021)
1: Initialize the parameters 0, 17 & of de - F. Qn F x A - R & mw (pwi Tw)
2: Initialize the replay buffer <- {
3: Nple number of episodes to perform planning and learning
4: Nrss + number of samples that the replay buffer must hold to perform planning and learning
5: ng number of time steps to perform search
6: Thss &- number of samples to sample from the replay buffer
7: h search heuristic
8: T' + replay buffer sampling strategy
9: 0
10: while i < Nple do
S reset environment
12: while not done do
A f- e-greedy (tree serreh.earrhh..m with bootstrapping((u(S)....) mW, Quy nsy 1t)
14:
Rt S' done <- environment(A)
15:
+ B {(S. A, S" ,done)}
16:
if B Nrse then
17:
D + sample batch(B, 16s, T) Update do. Qr & m with D end
18:
19:
20:
S S"
21:
end while
i+i+1
23:
end while
Return do. Qn m
Note that Alg, does not employ the "bottleneck mechanism" introduced in Zhao et al. 2021
C EXPERIMENTAL DETAILS
In this section, provide the implementation details of the environments that are used in Sec. together with the details of the models that are used in the scalability experiments of Sec. 5.1 We also provide the implementation details of the straightforward decision-time planning algorithm of Zhao et al. 2021) that was used Sec. 5.2
C.1 IMPLEMENTATION DETAILS OF THE SW ENVIRONMENT
As stated Sec. 3 in the Squirrel's World (SW) environment the squirrel's job is navigate from cell E1 (its initial state) to cell E16 (the terminal state) to pickup the nut without getting caught by
See https: //g thub. com/m mi aa-
ous- Pans-Planning for the publicly available
tual code.
16

---

Under review as a conference paper at ICLR 2023
the hawk that flies back and forth horizontally along row C. At each time step, the squirrel receives as imput an 5x 16 image of the current state of the environment and then, through the use a pre- defined state encoder, transforms this image into feature vector that contains information regarding all aspects of the current state of the environment, i.e., the feature vector contains information on the current position of the squirrel and the cloud, the current wind direction in rows A and B, the current position and direction of the hawk and the current weather condition. Based on this, the squirrel selects an action that either moves agent is trying to move out of the boundaries of the world in which case its position is kept constant). the squirrel gets caught by the hawk if it is out of time, it receives a reward of 0 and the episode terminates, and if the squirrel successfully navigates to the nut within the given time limit, it gets a reward of +-1 and the episode terminates. The agent-environment interaction lasts for 100 time steps, after which the agent receives done signal, marking the end of the episode.
the left or right cell, or keeps it position fixed (except if the
C.2 IMPLEMENTATION DETAILS OF THE 2RDO ENVIRONMENTS
In the 2RDO environments, the agent, depicted by the red triangle. spawns in top-left of the top room and has navigate to the green goal cell located in the bottom-right of the same room, regardless of the gaseous motions of the obstacles in the bottom room. Here, at each time step, the obstacles move one of its neighboring cells (except if it is trying move out of the boundaries of the world in which case its position is kept constant). At each time step, the agent receives an image of the current state of the grid and then, through the use of learned state encoder, transforms this image into a feature vector. Based on this, the agent selects an action that either turns it left or right, or moves forward (except if the agent is trying to move out of the boundaries of the world in which case its position is kept constant). If the agent successfully navigates to the goal cell within the given time limit, receives a reward of +-1 and the episode terminates. The agent-environment interaction lasts for 50 time steps for the 8x8 environments and 100 time steps for the 16x 16 environments, after which the agent receives a done signal, marking the end the episode.
C.3 DETAILS OF THE HAND-ENGINEERER MODELS
The details of what the models in Sec. 5.1 model can be found in Table
Table 1: Several non- VE and VE partial models of the SW enviromment.
m1
squirrel position, cloud position
m2
squirrel position, cloud position, wind direction
mg
squirrel position, cloud position, wind direction, hawk position
m4
squirrel position, hawk position, hawk direction
m
squirrel position, hawk position, hawk direction, cloud position
me
squirrel position, hawk position, hawk direction, cloud position, wind direction
squirrel position, hawk position, hawk direction, cloud position, wind direction, weather
C.4 DETAILS AND HYPERPARAMETERS OF THE DECISION-TIME PLANNING ALGORITHM
The details and hyperparameters of the straightforward Docision-time Zhao al. 2021 that we have used can be found in T
Table 2: Details and hyperparameters of Alg.
Φ
A regular neural network feature extractor
Qu
A regular neural network
m
A regular neural network
Npte
50M
N rbt
50k
ng
20
Tbe
128
h.
best-first search (training), random search (evaluation) random sampling
T
linearly decays from 1.0 to 0.0 over the first IM time steps
17

---

Under review as a conference paper at ICLR 2023
For more details (such as the NN architectures, replay buffer sizes, learning rates, exact details of the tree search, ... ), we refer the reader to the publicly available code and the supplementary material of Zhao al. (202I)
C.5 DETAILS THE ENCODER SHAPING PROCEDURE DURING TRAINING
we argued that one of the important inductive biases that is likely to guide the agent in coming up with only the relevant features of the environment only let the value estimator shape the encoder and to prevent the model from doing so. This is pictorially depicted in Fig. 7
In Sec. 5.2
Valke Extimator
Villow
Value Estimatar
Vidu
Tow Obsonvato
Eppocde Inmerastoon
Roae Olsunvation
Eidenda Tammrakie
Festur yoor
Encodar
Ercodor
Reward
Reward
Flaoor
Nesd Fastun Veedttr
Nes Nosd Panluu Viettor
Backsaer Piece
Backward Para
Figure 7: A pictorial representation of how the agent can be trained so that it can come with relevant features of the environment. (Right) The regular way of training, (Left) the way it can be done.
18


Reviews:
[{"review_id": "go8SeD16acO", "reviewer": "Reviewer_5G3f", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work focuses on model-based RL, particular in the life-long setting. It sets up the notation of minimal value-equivalent models, which are minimal-sized models which can capture all task relevant features of the environment. The authors show theoretical results that under a particular definition of partial minimal value-equivalent models, the agent does not incur a performance cost of planning using the model, but experiences improvement in computational and sample complexity. This is verified in experiments based on the MiniGrid domain. The second part of the experimental section is concerned with learning such models from interaction with deep learning architectures. The authors experimentally find that:\n\n1. Models which use representations trained through the loss of the value function perform and scale better than models trained through dynamics prediction as well. \n2. Models trained on a variety of environments perform better than models trained on a single environment in terms of robust transfer. \n3.. Models based using representations based on value-function training are more robust to model compounding errors.", "summary_of_the_review": "The paper provides good theoretical analysis of model-based learning in life-long/multi-task setting, however these seem of limited applicability in more complex and realistic domains. ", "strength_and_weaknesses": "Strengths:\n\nThe paper carries out thorough theoretical analysis of the performance gap of MVE models and their performance in terms of planning and complexity costs.\n\nWeaknesses:\n\n1. It is unsurprising that models which only encode task-relevant features would perform better than generic models, which might have multiple distractions. The difficulty is learning these models using salable architectures. The results presented here are incomplete and somewhat inconsistent with current model-based RL literature, i.e. value and reward signals are often insufficient to learn meaningful representations in more complex environments. \n2. Related to the previous point, the experiments are limited to GridWorld domains, which are relatively straightforward not realistic. It is unclear whether the experimental results presented here would hold in larger more realistic domains (probably not, based on previous works, i.e. Dreamer/SLAC).\n\nI am willing to increase my score if more involved experiments with realistic environments/control problems and current baselines are added.\n\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UEwsiexLwH", "reviewer": "Reviewer_SiWS", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present a framework to define partial models, value-equivalence and a simple method to learn partial models which are minimal and value-equivalent to the underlying MDP. The paper presents empirical results on two grid-world environments.", "summary_of_the_review": "I can currently only advocate a weak accept given that the experimental evaluation is not strong enough to warrant a better score. I highly recommend removing the word \"lifelong\" from the paper title, abstract etc. since it is very misleading and feels like the paper is about continual learning.\n\nEdits post-discussion phase:\n---------------------------------------\nI thank the authors for their clarifications. After more discussion with other reviewers and the AC, I have decided to lower my score to 3: reject, not good enough. I initially kept my original score of 6 following the authors' responses, since I do see value in the work when it comes to learning good partial models of the world. However, the authors have not addressed my concern that the work is not useful for lifelong learning. It currently only deals with a very specific kind of distribution shift which does not require acquiring any new features over time, and hence the model would not truly scale to a lifelong setting. I believe that more thorough experimentation with complex distribution shifts is required to prove that the model would indeed work in the lifelong setting before the work can be accepted.", "strength_and_weaknesses": "Strengths:\n\nThe paper is trying to address a very important research problem and the presented approach is simple to implement which I appreciate a lot. The authors have also presented theoretical results on differences in value-equivalence when learning approximate VE models.\n\nImprovements/Clarifications:\n\n1. What is \\delta in Theorem 3? How is it related to \\epsilon here?\n2. In fig 3, why is 3a only over a single run? Also there are no error bars/variances in 3b and 3c.\n3. In section 5.1, the text only talks about models m1-m6. But fig 3 also has m7. What is m7? For fig 3, please show results for all the 7 models in 3a, 3b and 3c? Why only sample 4 out of 7?\n4. The results are only for discrete grid-world environments, which makes it unclear if the proposed approach will generalize to more realistic settings.\n5. While answering question 7 (on page 9), what does the search budget refer to? Planner lookahead steps or planner time cutoff or something else?\n6. The word lifelong is very misleading because it seems to indicate a continual learning flavor, which is not the case. Please consider removing the word from the title and the paper.", "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": "84yxl5s0Yh4", "reviewer": "Reviewer_oVRM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper examines the advantages of using minimal value equivalent feature sets for state representation compared to feature spaces including irrelevant features. Value-equivalence is given if a reduced feature set leads to the same equivalent policies. The paper performs some experiments comparing partial models to complete models on basic environments with limited state and action spaces.\n", "summary_of_the_review": "All in all, the contribution of the paper is limited as it basically examines the effects of optimal subsets which are obvious if they can be determined. However, the paper does not really help to answer questions on how to find representation spaces which are value-equivalent. In addition, there is a strong link to causal analysis in MDPs. Causality analysis basically yields a framework for analysing whether features yield a dependency in estimating a distribution.\n\n\n", "strength_and_weaknesses": "Strong points:\n* The paper defines all concepts step by step and the results are clear\n\nWeak points:\n* The paper's contribution is limited as it formalizes a relatively well-known effect.\n* The paper argues much with MDPs where function approximation might not even be necessary.\n\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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6PSlZHDRQZ", "reviewer": "Reviewer_xzJK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work introduces minimal value-equivalent partial models, which are models of the environment built on top of a minimal subset of features from the observational space and holds the property of value-equivalence property. This property ensures that the value function associated with an optimal policy obtained as a result of planning with the model is equivalent to the optimal value function in the true environment. The work theoretically analyzes the value and planning losses for such models and provides estimations for computational and sample complexity. Finally, it illustrates such insights in controlled experiments and suggests inductive biases to implement these models in the Deep RL context, with proper ablation studies.", "summary_of_the_review": "The proposed work provides didactic definitions and theoretical grounding from planning in “partial” models. The experimental part also provided a good illustration of the insights presented, although more experiments are required to claim that the proposed inductive bias works for more complex scenarios. There are some concerns about questions and limitations to be discussed in the paper.\n\nReferences \n\n[1] Efroni et. al. Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information. COLT, 2022.\n\n[2] Efroni et. al. Provable RL with Exogenous Distractors via Multistep Inverse Dynamics. ICLR, 2022.\n\n[3] Ekar et. al. Planning to Explore via Self-Supervised World Models. ICML, 2020.\n\n[4] Hafner et. al. Learning Latent Dynamics for Planning from Pixels. ICML, 2019.\n\n\n====================POST-REBUTTAL============================\n\nI appreciate the authors’ efforts to clear my concerns. After considering the rebuttal and the discussion with other reviewers, I decided to change my score to {5: marginally below the acceptance threshold} for the following reason: despite having interesting theoretical contributions and experiments that illustrate them in a controlled environment, it is hard to evaluate if the proposed inductive bias (illustrated in Appendix C.5) hold for more complex scenarios. My second concern point remains open, as the paper does not provide evidence to support that this proposed inductive bias is robust to deal with more complex distribution shifts, a critical aspect of lifelong RL. This is essential to clear in the experiments once prior work often suggests that more signals are needed for effective representation learning in complex scenarios [3, 4]. As pointed out by other reviewers, this is somehow conflicting with prior literature, which makes it necessary to address for acceptance.\n", "strength_and_weaknesses": "Strengths:\n\n- The work analyzes the problem of learning dynamics models with relevant information for planning, showing an important direction to develop principled methods. Hence, it is well-motivated.\n\n- It formalizes the class of minimal value-equivalent partial models and provides its theoretical grounding. The definitions are clear, and the assumptions made are also clearly stated.\n\n- The theoretical understanding provides important insights in terms of value/planning losses, as well as the considerations for the sample and computational complexity. Furthermore, the experimental methodology and empirical results support the proposed theory, raising and answering the appropriate questions with the right choice of baselines and ablations.\n\n- Lastly, the work suggests inductive biases to scale its finding for the Deep RL scenario, and conduct ablation studies to support their recommendations.\n\nConcerns:\n\n- There is a limitation of the minimal VE partial models worth discussing in the paper. By definition, the relevant features are directly related to the reward and the task. Therefore, these models do not seem to be well-suited for scenarios where generalization across tasks is crucial (e.g., multi-task/meta-learning), which are important in the context of lifelong RL.\n\n- The distribution shifts analyzed in question 6 only relate to the irrelevant aspects of the environment. It would be interesting to discuss or provide empirical results for distribution shifts in a relevant feature, or even in scenarios where the set of relevant features changes over time, especially given the motivation of lifelong RL. The hypothesis is that the suggested inductive biases are not robust enough to deal with such shifts when it needs to learn the representation.\n\n- The current related work section does not place the work very well in the literature. For instance, I believe the work should contrast with recent literature on RL in the presence of exogenous distractors [1, 2] (once it approaches a very similar problem) and planning in learned latent spaces [3].\n\n\nFurther Suggestions/Minor Concerns:\n\n- It would be interesting to provide a small high-level description of how the Straight-Forward Decision-Time Planning algorithm works, besides the pseudocode. This should help in the presentation of this baseline.\n\n- In Question 3: “D minimal…” -> “Do minimal…”\n\n- Last line of Section 5: “compunding” -> “compounding”\n\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": {}}]

Author rebuttal:

Decision: Reject