Proper Value Equivalence
Authors: Christopher Grimm
Andre Barreto
Gregory Farquhar
David Silver
Satinder Singh
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: model-based reinforcement learning
reinforcement learning
value function
muzero
value equivalence
planning

Abstract: One of the main challenges in model-based reinforcement learning (RL) is to decide which aspects of the environment should be modeled. The value-equivalence (VE) principle proposes a simple answer to this question: a model should capture the aspects of the environment that are relevant for value-based planning. Technically, VE distinguishes models based on a set of policies and a set of functions: a model is said to be VE to the environment if the Bellman operators it induces for the policies yield the correct result when applied to the functions. As the number of policies and functions increase, the set of VE models shrinks, eventually collapsing to a single point corresponding to a perfect model. A fundamental question underlying the VE principle is thus how to select the smallest sets of policies and functions that are sufficient for planning. In this paper we take an important step towards answering this question. We start by generalizing the concept of VE to order-$k$ counterparts defined with respect to $k$ applications of the Bellman operator. This leads to a family of VE classes that increase in size as $k \rightarrow \infty$. In the limit, all functions become value functions, and we have a special instantiation of VE which we call proper VE or simply PVE. Unlike VE, the PVE class may contain multiple models even in the limit when all value functions are used. Crucially, all these models are sufficient for planning, meaning that they will yield an optimal policy despite the fact that they may ignore many aspects of the environment. We construct a loss function for learning PVE models and argue that popular algorithms such as MuZero can be understood as minimizing an upper bound for this loss. We leverage this connection to propose a modification to MuZero and show that it can lead to improved performance in practice.

Proper Value Equivalence
Christopher Grimm Computer Science Engineering University of Michigan crgrimm@umicom ch, edu
André Barreto, Gregory Farquhar, David Silver, Satinder Singh DeepMind Sandrebarreto,gregfar bavid
Abstract
One of the main challenges in model-based reinforcement learning (RL) is to decide which aspects of the environment should be modeled. The value-equivalence (VE) principle proposes simple answer to this question: a model should capture the aspects the environment that are relevant for value-based planning. Technically, VE distinguishes models based said to be VE to the environment if the Bellman operators it induces for the policies yield the correct result when applied the functions. As the number of policies and functions increase, the set of VE models shrinks, eventually collapsing to single point corresponding a perfect model. fundamental question underlying the VE principle is thus how to select the smallest sets of policies and functions that are sufficient for planning. In this paper we take an important step towards answering this question. We start by generalizing the concept of VE to order-k counterparts defined with respect to k applications of the Bellman operator. This leads to a family of VE classes that increase in size as k - co. In the limit, all functions become value functions, and we have a special instantiation of VE which we call proper VE or simply PVE. Unlike VE, the PVE class may contain multiple models even in the limit when all value functions are used. Crucially, all these models are sufficient for planning, meaning that they will yield an optimal policy despite the fact that they may ignore many aspects of the environment. loss function for learning PVE models and argue that popular algorithms such as MuZero can be understood as minimizing an upper bound for this loss. We leverage this connection to propose modification to MuZero and show that it can lead to improved performance in practice.
of policies and of functions; model is
construct a
Introduction
It has long been argued that, in order for reinforcement learning (RL.) agents to solve truly complex tasks, they must build a model of the environment that allows for counterfactual reasoning (29. Since representing the world in all its complexity is hopeless endeavor, especially under capacity con- straints, the agent must be able to ignore aspects of the environment that are irrelevant for its purposes. This is the premise behind the value equivalence (VE) principle, which provides formalism for focusing on the aspects of the environment that are crucial for value-based planning [17].
VE distinguishes models based set of policies and set of real-valued scalar functions of state (henceforth, just functions). Roughly, model is said to be VE to the environment the Bellman operators induces for the policies yield the same result the environment's Bellman operators when applied to the functions. The policies and functions thus become a "language" to specify which parts of the environment model should capture. As the number of policies and functions increase the requirements on the model become more stringent, which is to say that the class of VE models shrinks. In the limit, the VE class collapses to single point corresponding perfect model.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Although this result is reassuring, in practice we want to stop short of collapsing -aterr all, at this point the agent no longer ignoring irrelevant aspects of the environment.
fundamental question is thus how to select the smallest sets of policies and functions such that a resulting VE model is sufficient for planning. In this paper we take an important additional step in this direction: we show that the VE principle can be formulated with respect to value functions only, This result drastically reduces the space of functions that must be considered by VE, as in general only a small fraction of the set of all functions will qualify as value functions in a given environment. Since every policy has an associated value function, this new formulation of VE removes the need for selecting functions, only requiring policies. We name our new formulation proper value equivalence (PVE) to emphasize its explicit use of value functions.
PVE has several desirable properties. Unlike with VE, the class of PVE models does not collapse to singleton in the limit. This means that, even if all value functions used, we generally end up with multiple PVE modchss-hich can be beneficial some of these are easier to learn or represent than others. Crucially, all of these models are sufficient for planning, meaning that they will yield an optimal policy despite the fact that they may ignore many aspects of the environment.
Finally, we make more precise Grimm et al. 17 suggestion that the VE principle may help explain the good empirical performance of several modern algorithms 38 33 24 12 30]. Specifically, we show that, with mild assumptions, minimizing the loss of the MuZero algorithm [3]] can be
understood as minimizing a PVE error. We then leverage this connection to suggest a modification to MuZero and show small but significant improvement in the Atari Learning Environment 3
2 Background
The agent's interaction with the environment will modeled as a Markov decision process (MDP)
M = (S, following taking a from 8, p(s'|s, a) the transition kernel and y E [0. 1) is a discount factor [27]. A policy is mapping
where S and A are the state and action spaces, r(s, a) is the expected reward
S + ((A)) where P(AA) is the space of probability distributions over A;
we define 01 = [ π : S + ((4)) as the set of all possible policies. A policy л is deterministic
(als)) > 0 for only one action per state A policy's 's value function is defined as
Ex
Σ r'r(SS+s: Ac-i) Ss s(=s] }
where [-]
[-] denotes expectation over the trajectories induced by π and the random variables S, and A, indicate the state occupied and the action selected by the agent time step t.
The agent's goal is to find a policy π E Mn that maximizes the value of every state [36 37 Usually, crucial step to carry out this search is to compute the value function of candidate policies. This process can be cast in terms of the policy's Bellman operator:
Ta [s]ss) E (11
[r(s, + yo(5")
(2)
where v is any function in the space V = f : - TR.. It known that lim,- TH7 Ur. that is, starting from any E V. the repeated application of T will eventually converge U. Since in
RL the agent does not know p and it cannot apply 2 directly. One solution is to learn a model i (f, p) and use it to compute (2) with p and replaced by p and [36] We denote the set of all models as M.
The value equivalence principle defines model value equivalent (VE) to the environment m = (r.p) with respect to a set of policies II and a set of functions V if it produces the same Bellman updates as m² when using II and V [17]. Classes of such models are expressed as follows:
M(II V) = (m M T.u Tuu VT E I1, V M V}
(3)
where M C M is a class of models, Tr denotes one application of the Bellman operator induced by model m and policy и to function U, and Tx is environment's Bellman operator for æ.
Grimm et al. 17 showed that the VE principle can be used to learn models that disregard aspects of the environment which are not related to the task of interest Classical approaches to model learning
A related approach is taken in value-aware model learning [|] which minimizes the discrepancy between the Bellman optimality operators induced by the model and the environment.

---

do not take the eventual use of the model into account, potentially modeling irrelevant aspects of the environment. Accordingly, Grimm al. [17 have shown that, under the same capacity constraints, models learned using VE can outperform their classical counterparts.
3 Proper value equivalence
One can define spectrum of VE classes corresponding to different numbers of applications of the Bellman operator. We define order-k VE class as:
M V) = (m M T=v = T Vn E II, E)
(4)
where T denotes k applications of T. to u. Under our generalized definition of VE, Grimm et al. 17 studied order-one VE classes of the form M (II, V). They have shown that M (UI, V) either contains only the environment or is empty. This is not generally true for k > 1. The limiting behavior of order-k value equivalent classes can be described as follows
Proposition 1. Let V be set of functions such that if V then Ta E for all II. Then, for k, K E z+ such that k divides K, it follows that:
(i) For any M S and any II C,, we have that MI V) S (MM(II,))
(ii) If Il non-empty and V contains least one constant function, then there exist environments such that M* (II, V) C MM V)..
We defer all proofs of theoretical results to Appendix A.2 Based on Proposition T we can relate different VE model classes according to the greatest common divisor of their respective orders: specifically, two classes M (II, V) and M (II, V) will intersect at M) V) (Figure Proposition[aalls implies that, in contrast to order-one VE classes, higher order VE classes potentially include multiple models, even if VE is defined with respect to all policies 11 and all functions V. In addition, the size of a VE class cannot decrease as we increase its order from in some cases it will strictly increase). This invites the question of what happens in the limit as we keep increasing the VE order. To answer this question, we introduce a crucial concept for this paper: Definition 1. (Proper value equivalence). Given a set of policies 11 C 01, let
a multiple of le (and
M (TT) = lim M (TI {m E M 02 = 0z VT II,,
(5)
k+000
where ix and Ux are the value functions of a induced by model in and the environment. We say that (II)
each i E (III is a proper value equivalent model to the environment with respect to II.
M (II)
Because the process of repeatedly applying a policy's Bell- man operator function converges the same fixed point regardless of the function, in an order-oc VE class the II uniquely determines the set This reduces the problem of defining II and V to defining the former only. Also, since all functions in an order-co VE are value functions, we call it proper VE or PVE.
(I
M V
M V
It is easy show that Proposition 1 iis valid for any & Z+ when K = 0o (Corollary in Appendix (..)). Thus, in some sense, M is the "biggest" VE class. It also possible to define this special VE class in terms of any other:
(1
(
M V)
Mu
Proposition 2. For any II C 01 and any Z follows that
M
n M (( (u+)) xeIl
(6) Figure 1:
Topology of the space of order-k VE classes. Given a set of poli- cies II, set of functions V closed un- der Bellman updates, and k, K E Z+ such that & divides K, have that M¹ (II, V) S M MM(III))
where Us is the value of policy in the environment.
We thus have two equivalent ways to describe the class of models which are PVE with respect to set of policies II.
3

---

The first, given in (5). is the order-co limit of value equivalence with respect to II and the set of all functions V. The second, given in (6). the intersection of the classes of models that are order-k VE with respect to the singleton policies in IT and their respective value functions. This latter form is valid for any k, and will underpin our practical algorithmic instantiations of PVE.
Setting k = 1 in Proposition] 2 we see that PVE can be written in terms of order-one VE. This means that M inherits many of the topological properties of MM shown by Grimm al. [17]. Specifically, we know that M (II) C (I) if M' C M and also that M (II') C CM (II) when II C II' (these directly follow from Grimm et a [7] Properties I and respectively).
Proposition _ also sheds further light into the relation between PVE and order-k VE more generally. Let II be set of policies and Vx their value functions. Then, for any & Z we have that
M (+) = n n M (f DEV,
S n M (MT) (ux M M
(7)
TEnl
which is another way to say that M is, in some sense, the largest among all the VE classes. The reason why the size of VE classes is important is that it directly reflects the main motivation behind the VE principle. VE's premise that models should be constructed taking into account their eventual use: if some aspects of the environment are irrelevant for value-based planning. it should not matter whether model captures them or not. This means that all models that only differ with respect to these irrelevant aspects but are otherwise correct qualify valid VE solutions. A larger VE class generally means that more irrelevant aspects of the environment are being ignored by the agent. We now make this intuition more concrete by showing how irrelevant aspects of the environment that are eventually captured by order-one VE are always ignored by PVE:
Proposition 3. Let II C n. the environment state can be factored as S = X x y where ( > 1 and Ux (8) = ux ((x, u)) = Un (x) for all π E II, then M*
(I1 V) C (II.
Note that the subset relation appearing in Proposition 3] is strict. We can think of the variable 'y' appearing in Proposition 3 as superftuous features that do not influence the RL task, like the background of an image or any other sensory data that is irrelevant the agent's goal. A model is free to assign arbitrary dynamics to such irrelevant aspects of the state without affecting planning performance. Since order-one VE eventually pins down model that describes everything about the environment, one would expect the size of M relative to M to increase as more superfluous features are added. Indeed, in our proof of Proposition 3 we construct a of models in M (IT) which are in one-to-one correspondence with y, confirming this intuition (see Appendix A.2)
Proper value equivalence yields models that are sufficient for optimal planning
In general PVE does not collapse to single model even in the limit of II U. At first this may cause the impression that one is left with the extra burden of selecting one among the PVE models. However, it can be shown that such choice needs to be made:
Proposition 4. An optimal policy for any m E MP(II is also an optimal policy in the environment.
According to Proposition 1 any model m M used for planning will yield optimal policy for the environment. In fact, in the spirit of ignoring as many aspects of the environment as possible, we can define an even larger PVE class by focusing on deterministic policies only:
Corollary 1. Let Nan be the set of all deterministic policies. An optimal policy for any m E M (Tazr) is also optimal in the environment.
Given that both M (T) and M (Maa) are sufficient for optimal planning, one may wonder if these classes are in fact the same. The following result states that the class of PVE models with respect to deterministic policies can be strictly larger than its counterpart defined with respect to all policies:
Proposition 5. There exist environments and model classes for which M (IT) C M (Taet).
Figure 2 illlsttrate Proposition 5 with an example of environment and a model m such that m M (TTa) but m & (M).
To conclude our discussion on models that are sufficient for optimal planning, we argue that, in the absence of additional information about the environment or the agent, (0 is in fact the largest
possible VE class that is guaranteed to yield optimal performance. To see why this is so, suppose

---

Environment:
(+1,
100%
(+0.
100%
Model:
(+1,L)
100%
(+0,
100%
(+0,,
() 100%
90%
(+0,
100%
(+0, R) 100%
(+0, 100%
(+0, R)
[+0, RI 50%
100%
Figure 2: An environment model pair with the same values for all deterministic policies but not all stochastic policies. The environment has three states and two actions: A = {L. R.J. The percentages in the figure indicate the probability of a given transition and the corresponding tuples (r, a) indicate the reward associated with given action. A deterministic policy cannot dither between 81 and 83 but a stochastic policy can. Note that the dynamics between the pair differs when taking action R from 82. This difference will affect the dithering behavior of such a stochastic policy in way that results in different model and environment values.
remove single deterministic policy from Met and pick an arbitrary model m E (M {m})) Let Ü be the value function of π according to the model m. Because not included in the set of policies used to enforce PVE, ü, may not coincide with the actual value function of x according the environment. Now, i happens to be the only optimal policy the environment and o not the optimal value function of m, the policy returned by this model will clearly be sub-optimal.
4 Learning a proper value-equivalent model
Having established that we want to find a model in _ we now turn our attention to how this can be done in practice. Following Grimm et al. [17], given finite set of policies II and finite set of functions V, we cast the search for a model E (TT, V) as the minimization of deviations from
t ( m)
Σ FELL
|T
where T~ are Bellman operators induced by m and ||-11 is a norm Note that setting k = 0o in yields loss that requires computing m value function-which impractical do if vn is being repeatedly updated. Thankfully, by leveraging the connection between order-k VE and PVE given in Proposition 2 we can derive practical PVE loss:
Cn (m" mm
Σ I1T 7 T.ull1
Σ 1|0 *Ell
1 u=
Interestingly, given set of policies II, minimizing 99) for any h will result in model m E _ (cf. Proposition p. As we will discuss shortly, this property can be exploited generate multiple loss functions that provide a richer learning signal in practical scenarios.
Contrasting loss functions (8) and ( observe important fact: unlike with other order-k VE classes, PVE requires actual value functions to be enforced in practice. Since value functions require data and compute be obtained, it is reasonable to ask whether the benefits of PVE justify the associated additional burden. Concretely, one may ask whether the sample transitions and computational effort spent in computing the value functions be used with PVE would not be better invested in enforcing other forms of VE over arbitrary functions that can be readily obtained.
We argue that in many cases one does not have to choose between order-k VE and PVE. Value- based RL algorithms usually compute value functions iteratively, generating a sequence functions U1 U2 ... which will eventually converge to č₂ for some A model-based algorithm that computes Ox in this way has to somehow interleave this process with the refinement of the model m. When comes to VE, one extreme solution is to only use the final approximation 0, 0x in attempt to enforce PVE through (9). turns out that, as long as the sequence U1, 02, ... is approaching Un, one use all the functions in the sequence enforce PVE with respect to Our argument based on the following result:
We can also impose VE with infinite sets of functions and policies by replacing the respective sums with integrals: in this case one may consider taking supremum over VE terms to avoid situations where VE is not necessarily satisfied measure 0 sets.
5

---

Proposition 6. For any т E 11, WE and kn _,, we have that
17 - vzloo S (7* k + (²) 1 - ulloo + |T T 1l
(10)
Fec
Note that the left-hand side of (TO) corresponds to one of the terms of the PVE loss 2 associated with a given æ. This means that, instead of minimizing this quantity directly, one can minimize the upper-bound on the right-hand side of {TOp. The first term in this upper bound, Ev. is the conventional value-function approximation error that most value-based methods aim to minimize (either directly or
indirectly). The second term, Éve. is similar to the terms appearing in the order-k VE loss (8) except that here the number of applications of TT and of its approximation T do not have to coincide.
All the quantities uppearing in Eve are readily available or can be easily approximated using sample transitions [17]. Thus, Eve can be used to refine the model m using functions v that are not necessarily value functions. As -> U,, two things happen. First, Cue approaches one of the terms of the PVE loss ( associated with policy æ. Second, c vanishes. Interestingly, the importance of also decreases with n and k, the number of times Tx and T~ are applied in Eve, respectively. This makes sense: since T="" + Ug as n + oo and, by definition, VE approaches PVE - OC, we have that fv approaches the left-hand side of (10) as both and k grow.
An extended example: MuZero through the lens of value equivalence
Grimm et al. [1 suggested that the VE principle might help to explain the empirical success of recent RL algorithms like Value Iteration Networks, the Predictron, Value Prediction Networks, TreeQN, and MuZero (38 33
31. In this section we investigate this hypothesis further and describe a possible way to interpret one of these algorithms, MuZero, through the lens of VE. We acknowledge that the derivation that follows abstracts away many details of MuZero and involves few approximations of its mechanics, but we believe it captures and explains the algorithm's 's essence.
24
12
MuZero is model-based RL algorithm that achieved state-of satte-of-tee the--rte performance across both board games, such as Chess and Go and Atari 2600 games [3I]. The model rn in MuZero is trained sequences of states, actions and rewards resulting from executing "behavior policy" in the environment:
$t-++++K tt Tis+n-K where n and K are hyperparameters of the agent which will be explained shortly. The agent produces an "agent state" 2. from s, and subsequently generates .1:K by using its model to predict the next K agent states following actions dza-k. The agent also maintains reward and value function estimates
function of agent states, which we denote f(=) and v(z) respectively. A varian of MuZero's 's per-state model loss can thus be expressed as:
(* _ (V v(2))) v(2)))) + (re+h F(z))))²
(11)
where Vi+* Tt+k + ... 7"- -e---rr4nn-111 + narg (arg (=++ The term eaarg is value target produced by Monte- Carlo tree search (MCTS, (7]). Because the behavior policy is itself computed via MCTS, we have that darrg u; for simplicity we will assume that darg and only use
In what follows we show, subject to a modest smoothness assumption, that minimizing MuZero's loss with respect to its behavior policy, also minimizes corresponding PVE loss. Put precisely:
C T.EE, [e)())) 2 (m
(12)
for some C > O, where d, a stationary distribution. We proceed by combining two derivations: a lower-bound on Ex,, [()) in (15) and an upper-bound on (ek (00 (m" m))² in (17)
As preliminary step we note that e" (s,) and eK (x) (m" m) are expressed in terms of samples and expectations respectively. We note the following connection between these quantities:
E3 E s:] = P (st),
[E[e+ = P [sc), Blu(2>)) (u))((s)
(13)
[ ) | s = 1s
'In reality MuZero uses a categorical representation for its value and reward functions and minimizes them using a cross-entropy objective. We argue that this choice is not essential to its underlying ideas and use scalar representations with squared loss simplify our analysis.

---

where Pe is the k-step environment transition operator under policy म. (s)) B[s(Se+*)]ss m", m².=, rs(ss) EA-=(r(s, A)] and Pk and îッ are the corresponding quantities using the model instead of the environment. The above expectations are taken with respect to the environment or model and и as appropriate. We now derive our lower-bounds on Ed, _ [(()]
K
Edd (1t (S:)l Bd=
(Vi++ - u(2)))
S
E (re+h - [S.]]
k=
K
K
2 Ed
[ Vi+k -
1
E rotk [t) B[F(zf) st 1t
k=
k=0
K
K
Σ K=
Ba
- - (()()))) +
Σ k=0
Ed
(p (St) - F (.)))
(14)
where we apply the tower-property, Jensen's inequality and the identities in 13 3
We write the
expression using norms and drop all terms except & E {0, K} in the first sum to obtain:
Ea, (()) 2 1T - oll2, + ||
1 T v - PK v112, + Σ P T P 112
(15)
recalling that ||--- v1 = E,, [(x(()))))))))))))( - [S.)))
To derive an upper-bound for (xx), (m" (m= ,m))²
we assume that the error in value estimation is smooth in the sense that there is some 9 > 0
(independent of v) such that |/c - /x/lxx g- u=lld, We can then use a modified version of I00 for the d, d--egighted fz-norm (see Appendix A.2p. plugging in n + K and K:
||v- Txuulll valla, S (gr* + + )| v11a, + IT k T vlla,
7 (g + " ulla, + |P T plllle
| - -
k=0
S y x (g + (1)
(1 (1-7m |1 - 011a, ||P - PK ulla,
K
| r. -
+
(16)
from here we can square both sides and apply Jensen's 's inequality,
K ||0z - jx Va 112. S abblTT"' v- - =112- + bbIPP PK olla, b
Σ
I Tx
ph 1 (17)
k=0
where = *k + (1) - - and b = a K + 2. Combining and 15 we obtain:
Ea, [ (((())) ž - - Ur 12 (e [m] (m (m", m))
(18)
thus minimizing MuZero's loss minimizes squared PVE loss with respect to a single policy.
Experiments
We first provide results from tabular experiments stochastic version of the Four Rooms domain which serve to corroborate our theoretical claims. Then, we present results from experiments across the full Atari 57 benchmark [3] showcasing that the insights from studying PVE and its relationship to MuZero can provide a benefit practice at scale. See Appendix A.3 for a full account of our experimental procedure.
In Section we described the topological relationships between order-k and PVE classes. This is summarized by Proposition which shows that, for appropriately defined V and II, M C MM if K a multiple of We illustrate this property empirically by randomly initializing a set of models and then using (8) (or (9) for the limiting case of k oo) to iteratively update them towards (T,, V), with (1,30, 40, 50, 60, 60,oo). oo). We take the vectors representing these models and project them onto their first two principal components in order to visualise their paths through learning. The results
7

---

Orber
Order 30
Order 60
Order
00
Figure 3: All seatter plots are generated by tracking the training progress over 500,000 iterations of models with different order-k VE objectives. In each plot 120 models were tracked; at every 1000 timesteps the full set of models is converted into vector form and projected onto their first two principal components before being plotted (details in the appendix). Top row: points colored according to their progress through training. Bottom row: points are colored according to the average value of the associated model's optimal policy on the environment. Rightmost plot: line-plor of the diameters of these scatter plots against the model-class order.
shown on the top row of Figure 3 In accordance with the theory, we see that the space of converged models, represented with the brightest yellow regions, grows with k. This trend is summarised in the rightmost plot, which shows the diameter of the scatter plots for each k. In the bottom row of Figure 3 we use color to show the value that the optimal policy of each model achieves in the true environment. As predicted by our theory, the space of models that are sufficient for optimal planning also grows with k.
Model classes containing many models with optimal planning performance are particularly advan- tageous when the set of models that an agent can represent restricted, since the larger the set of suitable models the greater the chance of an overlap between this set and the set of models repre- sentable by the agent. Proposition and Corollary compared M*((I) and M ([lde)) showing that, although any model in either class is sufficient for planning, _ S (Tde). This suggests that it might be better learn model in M (Nldtt when the agent has limited capacity.
Environment
PVE Model
10
70
Normalized Traj anieettoyy Time
Normalized endedooyy
60
60
0.5
10-
0.4
()
30-
M
0.2
20
40
63
S0
100
Model Rank
(a)
Figure 4: (a) Comparison of the performance of optimal policies obtained from capacity constrained models trained to be in M (Naet) and M (T).. For each action A, the transition dynamics Pa is constrained have a rank of at most k. The red dashed line represents the performance of the optimal environment policy. (b) Trajectories starting from the bottom-right state (red dot) sampled from the optimal environment policy both the environment and a PVE model. Note the numerous diagonal transitions in the PVE model which are not permitted in the environment.

---

We illustrate that this is indeed the case in Figure 4b. We progressively restrict the space of models that the agent can represent and attempt to learn models in either M or (M Indeed, we find that the larger class, .M - dNet)), yields superior planning performance as agent capacity decreases.
Given their importance, we provide intuition on the ways that individual PVE models differ from the environment. In Figure a we compare trajectories starting the same initial state (denoted by red-circle) from the optimal environment policy in both the environment and in a randomly sampled model from M (I)). In the PVE model there are numerous diagonal transitions not permitted by the environment. Note that while the PVE model has very different dynamics than the environment, these differences must "balance out", as it still has the same values under any policy as the environment.
In Section we showed that minimizing Muzero's loss function is analogous to minimiz- ing an upper-bound on a PVE loss D with re- spect to the agent's current policy π which cor- responds to finding a model in M where
Mesien human normalised score
MuZero Baseline
ll =l {m). Note that our guarantee on the perfor-
mance of PVE models (Corollary] [ holds when
contains all deterministic policies. While is not feasible to enforce II = Mdet. we can use previously seen policies by augmenting the MuZero algorithm with a buffer of past policies and their approximate value functions (we so by periodically storing the corresponding pa- rameters). We can then add an additional loss to MuZero with the form of the original value loss but using the past value functions. use sampled rewards construct value targets, but use the stored policies to compute off- policy corrections using V-trace [9].
2
3
Frames
les
Figure 5: Comparison of our proposed modifica- tion to MuZero with an unmodified baseline.
still
To test this proposal we use an on policy (i.e., without a replay buffer) implementation of MuZero run for 500M frames (as opposed to 20B frames in the online result of (31) the Atari 57 benchmark and find that using our additional loss yields an advantage in the human normalised median performance shown in Figure 5 MuZero's data efficiency can also be improved with the aid of replay buffer of trajectories from past policies [32], which may also capture some the advantages expanding the set of policies used for PVE.
Related work
Our work is closely related the value-aware model learning (VAML, IterVAML, [I]] 10) which learns models to minimize the discrepancy between their own Bellman optimality operators and the environment's on the optimal value function an priori unknown quantity. To handle this VAMI. specifies a family of potential value functions and minimizes the worst-case discrepancy across them, whereas IterVAML. minimizes the discrepancy with respect to model's current estimate of the value function in a value iteration inspired scheme. PVE and the VAML family are complementary works, with VAML addressing its induced optimization problems and PVE addressing its induced model classes. Both, however, advocate for learning models with their eventual use in mind view that is aligned with many criticisms of the maximum likelihood objective for model learning IT 21 23
It is worth mentioning the relationship between PVE and TD models [35 which, for given policy, defines any R E R and P E R|S| x|S] with lim pk = 0 as a valid model if V = R + PT
where V E R represents Un- Clearly all models (f=) are valid models, however, since P necessarily transition matrix, the converse does not hold. While TD models restricted to prediction rather than control, their generality warrants further inquiry.
Order-k and PVE model classes form equivalences between MDPs and thus can be situated among other equivalence notions which can formulated as state-aggregations [ 26 25 16
39 5 44) As pointed out by Grimm et al. [17]. the interaction between arbitrary aggregaggoo

---

and models can be captured with special cases of order-one VE. Our extension of higher-order VEs potentially offers the possibility of "blending" existing notions of state aggregation with PVE.
notable instance of slate-aggregation is bisimulation [22] which uses a relation to aggregate states that have the same immediate rewards and transition dynamics into other aggregated states. Bisimula- tion metrics [33 provide smooth measures of how closely pairs of states satisfy bisimulation relations. These concepts have become increasingly popular in deep reinforcement learning where they are used to guide the learning of effective representations 4 13 I. Although both bisimulation and PVE provide direction for learning internal aspects of agent, they are fundamentally different concerns representation learning, while PVE concerns the learning of models given a representation of state.
in their purview-bisiminee
including several modern works which explicitly study the conjunction of model learning with state representation 44 42 15]. These are further complemented by efforts to learn state representations and models
Beyond bisimulation, representation learning has a wide literature 41 20
jointly in the service of value-based planning [12 33 24 18 31 38).
7 Conclusion and future work
We extended the value equivalence principle by defining a spectrum of order-k VE sets in which models induce the same k-step Bellman operators as the environment. We then explored the topology of the resulting equivalence classes and defined the limiting class when h + oo as PVE. If a model is PVE to the environment with respect to set policies II, then the value functions of all policies in Il are the same in the environment and the model. The fact that PVE classes can be defined using only a set of policies eliminates the need for specifying set of functions to induce Ve-resolving fundamental issue left open by Grimm et al. [17]. Importantly, we showed that being PVE with respect to all deterministic policies is sufficient for a model to plan optimally in the environment. In the absence of additional information, this is the largest possible VE class that yields optimal planning. On the practical side, we showed how the MuZero algorithm can be understood as minimizing an upper bound on PVE loss, and leveraged this insight to improve the algorithm's 's performance.
Though our efforts have advanced the understanding of value equivalence and proven useful algo- rithmically, there is still work to be done in developing a VE theory whose assumptions hold in practice. This remaining work can broadly grouped into two areas (1) understanding the role of approximation in VE and (2) establishing performance guarantees for VE models with arbitrary sets of policies and functions. We leave these as future work.
10

---

Acknowledgements
We thank Angelos Filos and Sonya Kotov for many thought-provoking discussions. Christopher Grimm's work was made possible by the support of the Lifelong Learning Machines (1.2M) grant from the Defense Advanced Research Projects Agency. Any opinions, findings, conclusions, recommendations expressed here are those of the authors and do not necessarily reflect the views of the sponsors.
References
[1] Rishabh Agarwal, Marlos C Machado, Pablo Samuel Castro, and Marc Bellemare. Contrastive behavioral similarity embeddings for generalization in reinforcement learning. arXiv preprint arXiv:2101.05265, 2021.
[2] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474. PMLR, 2020.
[3] Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253- 2299, 2013.
[4] Ondrej Biza, Robert Platt, Jan- Willem van de Meent, and Lawson LS Wong. Learning discrete state abstractions with deep variational inference. arXiv preprint arXiv:2003.04300, 2020.
[5] Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10069-10076, 2020.
[6] Dane Corneil, Wulfram Gerstner, and Johanni Brea. Efficient model-based deep reinforcement learning with variational state tabulation. International Conference on Machine Learning, pages 1049-1058. PMLR, 2018.
[7] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference computers and games, pages 72-83. Springer, 2006.
[8] Thomas Dean and Robert Givan. Model minimization in markov decision processes. In AAAI/IAA,, pages 106-111, 1997.
[9] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, pages 1407-1416. PMLR, 2018.
[10] Amir-massoud Farahmand. Iterative value-aware model learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 9090-9101 2018.
[11] Amir-Massoud Farahmand, André Barreto, and Daniel Nikovski. Value-Aware Loss Function for Model-basee Reinforcement Learning. In Proceedings of the International Conference on Artificial Intelligence and Statisties (AISTATS), volume 54, pages 1486-144 1494, 2017.
[12] G Farquhar, T Rocktäschel, M Igl. and S Whiteson. Treeqn and atreec: Differentiable tree- structured models for deep reinforcement learning. In 6th International Conference on Learning Representations, ICLR 2018- 111-oonfeeeece Track Proceedings, volume 6. ICLR, 2018.
[13] Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In UAI, volume pages 162-169, 2004.
[14] Vincent François-Laved Yoshua Bengio, Doina Precup, and Joelle Pineau. Combined reinforce- ment learning via abstract representations. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3582-3589, 2019,

---

[15] Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Mare G Bellemare. Deep- mdp: Learning continuous latent space models for representation learning. In International Conference Machine Learning, pages 2170-21799 PMLR, 2019.
[16] Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):163-22,, 2003.
[17] Christopher Grimm, Andre Barreto, Satinder Singh, and David Silver. The value equivalence principle for model-based reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
[18] Matteo Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent Sifre, Theo- phane Weber, David Silver, and Hado van Hasselt. Muesli: Combining improvements in policy optimization. arXiv preprint (:Xi:2204.06/// 2021.
[19] Matteo Hessel, Manuel Kroiss, Aidan Clark, lurii Kemaev, John Quan, Thomas Keck, Fabio Viola, and Hado van Hasselt. Podracer architectures for scalable Reinforcement Learning CoRR, abs/2104.06277. 2021.
[20] Maximilian Igl. Luisa Zintgraf, Tuan Anh Le, Frank Wood, and Shimon Whiteson. Deep varia- tional reinforcement learning for pomdps. In International Conference on Machine Learning, pages 2117-2126. PMLR, 2018.
[21] Joshua Joseph, Alborz Geramifard, John W Roberts, Jonathan P How, and Nicholas Roy. Rein- forcement learning with misspecified model classes. In 2013 IEEE International Conference Robotics and Automation, pages 939-946. IEEE, 2013.
[22] Robin Milner. Communication and concurrency, volume 84.
[23] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of rein- forcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
[24] Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In Advances in Neural Information Processing Systems, pages 211186128. 2017.
[25] Pascal Poupart and Craig Boutilier. Value-directed belief state approximation for POMDPs. pttttp:://aaxii.org//bbaa 1887/
CoRR, abs/1301.3887 2013.
[26] Pascal Poupart, Craig Boutilier, al. Value-directed compression of pomdps. Advances in neural information processing systems, pages 1579-1586, 2003.
[27] Martin L. Puterman. Markov Decision Processes Discrrte Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
[28) Balaraman Ravindran and Andrew G Barto. Approximate homomorphisms: A framework for non-exact minimization in markov decision processes. 2004.
[29] Stuart J. Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Pearson Education, 3 edition, 2003.
[30] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. arXiv preprint arXiv: 19/ 1.08265, 2019.
[31] Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-699 2020.
[32] Julian Schritwiisser, Thomas Hubert, Amol Mandhane, Mohammadamin Barekatain, Ioannis Antonoglou, and David Silver. Online and offline reinforcement learning by planning with learned model. arXiv preprint arXiv:2104.06294 2021.
12

---

[33] David Silver, Hado van Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac-Arold,, David Reichert, Neil Rabinowitz, Andre Barreto, et al. The predictron: End-to- end learning and planning. In Proceedings of the 34th International Conference Machine Learming-Volune 70, pages 3191-3199. JMLR. org, 2017.
[34] John P Spencer, Michael SC Thomas, and JL McClelland. Toward a unified theory of develop- ment. JP Spencer, MSC Thomas, & JL McClelland (Eds.), pages 86- 18, 2009.
[35] Richard S. Sutton. TD models: Modeling the world at mixture of time scales. In Proceedings of the Twelfth International Conference on Machine Learning, pages 531-539, 1995.
[36] Richard S. Sutton and Andrew G. Barto.
Reinforcement Learning: An In-
troduction. MIT Press, 2018. URL
httts::/miitrres.nniit mit. edu/btoku//kkkk edition 2nd edition.
reinforcement-
[37] Csaba Szepesvári. Algorithmss for Reinforcement Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan Claypool Publishers, 2010.
[38] Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Picter Abbeel. Value iteration networks. In Advances in Neural Information Processing Systems, pages 2154-2162 2016.
[39] Jonathan Taylor, Doina Precup, and Prakash Panagaden. Bounding performance loss in ap- proximate mdp homomorphisms. Advances in Neural Information Processing Systems, 21: 1649-1656, 2008.
[40] Elise van der Pol, Thomas Kipf, Frans A Oliehoek, and Max Welling. Plannable approximations to mdp homomorphisms: Equivariance under actions. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 1431-1439, 2020.
[41] Manuel Watter, Jost Tobias Springenberg, Joschka Boedecker, and Martin Riedmiller. Embed to control: a locally linear latent dynamics model for control from raw images. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 2, pages 2746 2754, 2015.
[42] Amy Zhang, Zachary C Lipton, Luis Pineda, Kamyar Azizzadenesheli, Anima Anandkumar, Laurent Itti, Joelle Pineau, and Tommaso Furlanello. Learning causal state representations of partially observable environments. arXiv preprint arXiv: 1rXX::1906.1043: 10437, 2019.
[43] Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006.100 10742, 2020.
[44] Marvin Zhang, Sharad Vikram, Laura Smith, Pieter Abbeel, Matthew Johnson, and Sergey Levine. Solar: Deep structured representations for model-based reinforcement learning. In International Conference on Machine Learning, pages 7444-7453, PMLR, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Code for the illustrative experiments is available at URL provided in Appendix A.3 Sufficient detail for reproducability provided in the same section.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "uSgfbxlqHmg", "reviewer": "Reviewer_uAfL", "summary": "This paper first extends value equivalency (VE) to k-step value equivalency, where the equivalency holds for k-step application of the Bellman operator. In the limit of k to infinity they then show this becomes ‘proper value equivalence’ (PVE), for which the policy uniquely defines the VE class. They also show that MuZero is a special case of the PVE class, and derive empirical experiments on PVE, also extending MuZero with a new loss. \n", "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": "Strong:\n– It like the fact that VE starts to get theoretical grounding, and this paper indeed extends the previous ideas of Grimm. It is also nice to see MuZero be put in a theoretical framework.\n– The theoretical part seems sound. I am not deeply read up on the theory, and I could therefore not verify all proofs in detail, but they seem correct.\n– Apart from the theory, the paper also has experiments, including extensive high-dimensional Atari experiments in which they indeed (slightly) outperform baseline MuZero. \n\nWeak:\n– You are quite fast in some of your explanations. For example, Figure 2 is not clear for me, I do not understand what exactly I should see (it needs more text in the caption). In general, I get the feeling you tried to squeeze a lot of information into the paper, and this makes you go pretty fast at several points. \n– I miss some more intuition on what happens, especially why the k-step models, in particular the infinity variant (PVE), has such different properties than the one-step VE. You quickly move into the technical terms, but I think it would help if you first gave a more intuitive explanation of what is happening here, why the VE class grows with k, and why this is relevant.\n– For your empirical section, I think it would really benefit if you gave an explicit algorithm of your PVE method. It is not entirely clear from the text to me how your overall interaction loop with the environment and training procedure takes place now. I would also prefer to see the exact loss with which you extend MuZero, and how it is embedded in the algorithm (L295). \n– I miss a Discussion section, with weaknesses and potential future work.\n\nSmaller:\n– Fig 4b: “bottom-right” should be “bottom-left”\n\nConclusion:\nThis is a good theoretical paper on an important topic (value equivalency), which has shown state-of-the-art empirical results recently. As far as I can tell, the theoretical results are sound and relevant, although I miss some broader motivation and intuition. The empirical section is good as well, although it would benefit from more explicit algorithms. In general, my biggest issue with the paper is its density: it seems like there was just a bit too little space for both the theoretical and empirical parts (see my comments above), and a discussion is completely omitted. (Maybe the derivation of MuZero being in the PVE class could move to the appendix, and the authors could give additional intuition, explanation and discussion in the main text.) I will nevertheless vote for accept given the positive aspects of the paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors state societal impact is not applicable, I agree", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "c0CdINWTOtq", "reviewer": "Reviewer_bRZz", "summary": "The paper \"Proper Value Equivalence\" addresses the question of how models for reinforcement learning can be obtained which are sufficient for planning without modelling irrelevant details of the environments. The authors build upon previous work by Grimm et al. and expand the notion of value equivalence to only require value functions actually obtainable by policies in the environment. They show several illustrative examples and proofs of why this notion of proper value equivalence alleviates some problems with previous work, such as not collapsing the space of admissible models down to the optimal model. This is very important in many cases where the true model might not be recoverable due to irreducible approximation errors or missing data.", "questions": "", "limitations": "", "rating": 8, "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": "Praise for the paper:\n\nThe paper can be seen as a direct successor to Grimm et al. \"The value equivalence principle for model-based reinforcement learning\". This is not a criticism, the paper builds substantial novel results on this previous work and greatly reduces the gap between the principle outlined by Grimm et al. and practical algorithms. It addresses a clear limitation of the previous work, in which the set of admissible models collapses to the true model, which might not be learnable in practice. PVE shows that more models than just the true model are sufficient for planning and outlines the necessary requirements for these models, which is that they match in value function for all policies in the environments. The propositions and proofs are presented in a manner that is clear to the reader and they are easy to follow.\n\nThe paper concludes with a short experimental section in which the authors first show how the successful MuZero algorithm can be understood and modified using proper value equivalence. This presents a very interesting addition to the field since explanations for empirically well performing algorithms are often missing or neglected in the literature.\n\nCriticism of the paper:\n\nMissing from the paper are discussions about the setting in which the Bellman error is not applied directly but minimized by some approximate approach such as Squared Bellman error minimization. Such schemes make up the majority of current literature and addressing the interplay between approximate value iteration and PVE are of significant interest.\n\nThe clarity of the paper could be slightly improved by making clear that the resulting $\\infty$ Bellman operators are equivalent to the policy value functions under the respective policies. I think the distinction between Grimm et al. general notion of \"functions\" and the actual value functions of considered policies here could be pointed out more directly.\n\nThe paper does not discuss the relationship between proper value equivalence and bisimulation theorems (or related approaches), a topic which has recently become very popular in the field. At least a part of the related work should be used to discuss related work in that field and similarities and differences to the presented approach. The reference to Grimm is a bit unsatisfactory, since that paper also does not provide a real comparison, remaining fairly vague on the topic.\n\nFinally, some few sections of the paper seem unfinished. At at least two places (line 81 and line 134) the authors have added comments in parentheses which feel like they should be expanded into full sentences or footnotes.\n\nConclusion:\n\nOverall the paper provides novel and interesting insights, is well written and easy to read despite mostly discussing theoretical results. In my eyes, the paper should be accepted to NeurIPS.\n\n\nChecklist:\n\nOriginality: The stated results are novel.\nQuality: The proofs seem correct and all theoretical assumptions are listed.\nClarity: The writing style is clear and easy to follow.\nSignificance: The results build on previous work and expand the understanding of the field of model-based RL. Furthermore they offer a way to gain insight into a SOTA applied RL algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the proposed approach are not discussed, one such a potential limitation was pointed out above.\nSince the paper addresses foundational questions of reinforcement learning, a discussion of societal impact seems out of scope.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "63_9dba6hWw", "reviewer": "Reviewer_2msG", "summary": "This paper introduces a k-th order generalization of the Value Equivalence (VE) principle of Grimm et. al. 2016, generalizing that the candidate value functions are equal under multiple (rather than one) iterations of the Bellman operator for a candidate set of policies. Taking k -> infinity leads to the special case of Proper Value Equivalence (PVE), which only depends on a candidate set of policies. Several structural results and derived, and it is shown that models obtained from PVE (with the set of deterministic policies) have the same optimal policies as the true environment.  A loss function is introduced to learn k-VE models, connections with MuZero are drawn, and experimental simulations are carried out. ", "questions": "", "limitations": "", "rating": 7, "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": "Overall this is a good paper which I recommend for acceptance. There are a couple of issues that I have concerning disconnects between it’s theoretical claims and it’s empirical claims, which I will get into later. \n\nFirstly the paper is well-written and well-organized. The k-th order generalization of VE models is a novel and interesting extension. The theoretical claims are technically sound. The structural properties are interesting and well-investigated (some of them were a bit surprising/counter-intuitive). The result of Corollary 1 is an interesting characterization for the set of models which are sufficient for planning. \n\nHowever, I am not quite as convinced by the connections with MuZero. The derivation of Sec. 4 establishes that (with some smoothness assumptions), the proposed PVE loss for a singleton policy class is a lower bound to the MuZero loss function. It is not quite clear to me what this is demonstrating. The guarantee of Corollary 1 says that planning is optimal when the policy class is all deterministic policies, and there are no obvious guarantees for the quality of a model that is PVE for a singleton policy class, so this does not seem to give any concrete guarantees for MuZero as far as I can tell. \n\nOn the same note, it is not clear to me how useful the loss functions (8) (or (9)) are. The summation over policies seems infeasible, especially since Corollary 1 requires \\Pi to be the set of all deterministic policies, which is obviously exponentially large in |S|. Even more, the value function for each of these policies must be estimated. As far as I can tell the full set of policies is never used, and in the MuZero experiments (Figure 5) the loss is minimized for a few policies. This seems to give some empirical advantages, but once again the theory does not indicate why doing this would be helpful.\n\nOverall, the paper would be greatly strengthened with further theoretical evidence for the quality of PVE models with respect to a smaller (feasible) set of policies, or with more extensive support for the empirical uses of the PVE loss function.\n\nTypos: - extra parenthesis in Eq (11)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above: “the paper would be greatly strengthened with further theoretical evidence for the quality of PVE models with respect to a smaller (feasible) set of policies, or with more extensive support for the empirical uses of the PVE loss function”.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1D3Y2E0ycAX", "reviewer": "Reviewer_kSxE", "summary": "The paper proposes an extension to the value equivalence (VE) principle in MBRL called Proper VE (PVE).\nThe original VE states that a model is equivalent to the true model if the induced Bellman operators coincide for a set of policies and value functions.\nPVE is motivated by the observation that a repeated application of the Bellman operator will eventually converge to a value function of a given policy for a chosen model.\nPVE defines a model to be equivalent to the true if, for a set of policies, it results in the same value functions as in the original MDP.\nWhile PVE assumes an infinite Bellman operator application (called order-∞), the paper studies the relation between non-asymptotic versions of PVE. \nFor example, the authors prove that order-k PVE models are also order-K PVE models if k divides K and demonstrate the result empirically.\nThe paper shows that PVE models are sufficient for planning, i.e. a policy that is optimal for a PVE model is optimal in the true MDP.\nFinally, the authors propose a PVE-inspired loss for model learning and show that MuZero optimizes an upper bound on the loss corresponding to a behavior policy.\nInspired by the observation, the authors extend to the MuZero loss with additional terms corresponding to previous policies and show an increase in the median score on the Atari 57 benchmark.\n", "questions": "", "limitations": "", "rating": 7, "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": "Originality:\n\nThe overall originality of the paper is reasonable.\nOn one hand, PVE is very closely related to the special case of VE when the chosen set of (arbitrary) value functions coincide with the value functions of the given policies (eq 7).\nOn the other hand, the paper deepens the understanding of the (P)VE principle by proving a number of propositions.\nProp 1 and Prop 2 provide two different characterizations of PVE models.\nProp 3 shows that PVE models are preferable when an MDP can be factored into a part with the information relevant for planning and an irrelevant part.\nProp 6 shows that the PVE-inspired loss can be upper bounded by a sum of a value approximation error and a difference between results of the application of the model and the true Bellman operators.\n\n\nQuality:\n\nThe overall quality of the paper is high.\nIn addition to establishing the understanding of the sets of PVE models, the authors visualize the trajectories from the PVE models on the (stochastic) four rooms domain.\nInterestingly, PVE models admit transitions that are not allowed by the environment -- could you think about a way to address this phenomenon?\n\n\nClarity:\n\nOverall, the paper is well-written.\nThe main text contains a self-sufficient exposition of results and the appendix contains the details about the experiments and proofs.\nThe reviewer felt that the pace in some parts of the text (e.g. around Prop 5 and Figure 2) was a bit too high and thus required extra time to understand.\nPerhaps moving eq 13 - 18 to the appendix would be a better use of space (e.g. for discussing the limitations of learning value-equivalent models).\n\nTypos:\n- L543 \\tilde{T}^k_π v is written twice\n- L547 “non-empty. and produce”\n\n\nSignificance:\n\nThe overall significance of the paper is fair.\nThe paper provides a foundational block for learning decision-aware models which is an important research direction in RL.\nProviding scores for all 57 Atari games would increase the significance of the paper because a scalar can sometimes be insufficient to make conclusions about the performance on 57 games.\n\n\nRecommendation:\n\nThe reviewer leans towards recommending to accept the paper.\nAddressing the outlined concerns could improve the quality of the paper and increase the score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The answer to the question about the limitations is Yes but the reviewer did not find any relevant discussion.\nWhile the main contribution of the paper is not an algorithm, including a discussion about the limitations would still strengthen the paper.\n\nSome suggestions for improvement are provided in the main review.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are positive about this work, and they believe the paper provides novel insights to the value equivalency principle. Some issues are brought up in the reviews, most of which are satisfactorily answered in the authors' responses (we had private discussions). Please consult their reviews for the details. Some of them are:

- The paper is sometimes too rushed in its explanations.
Perhaps the authors can remove some of the derivations (e.g., Eqs. 13-18) to an appendix, so that they can expand their discussions elsewhere.
- Some reviewers found the detail insufficient for reproducibility.
- More clear discussion on the relation between bisimulation and value equivalence can be helpful.

The revisions required to improve the paper are minor enough that another round of reviews is not required. Therefore, I recommend the *acceptance* of this paper.

=== 

In addition to these comments from reviewers, I have some questions and comment that I would appreciate if the authors answer them in their revisions. These are not critical, so they are inconsequential to the decision.

- The loss function in Eq. (8) and (9) have summation over policies (and value functions). 
But (P)VE requires the exact match for all policies (and values, for VE). 
Requiring an exact match suggests that we need to have a loss that encourages the error to be small *uniformly* over values and policies. This means that we may need to consider the supremum over $v$ and $\pi$, instead of summation over them.

The summation can be just too relaxed to impose the required equivalency. This might be more of an issue when the value and policy space is very large, e.g., infinite number of elements. In that case, a large error in a small (say, zero measure) subset of the value/policy space does not affect the loss at all, but it violates the value equivalency.

If we agree that this is the right/better way to write the loss function, then the losses (8) and (9) might be written as

(8') $\sup_{\pi \in \Pi} \sup_{v \in V} || T_\pi^k v - \tilde{T}_\pi^k v||$

and

(9') $\sup_{\pi \in \Pi} || v_\pi - \tilde{T}_\pi^k v||$.

These show some similarities with VAML. VAML uses the Bellman optimality operator, but we can easily have a version for Bellman operator for a policy $\pi$. In that case, with k = 1, the inner optimization $\sup_{v \in V} || T_\pi^k v - \tilde{T}_\pi^k v||$ would be the original VAML's, and for k > 1, it would be a multi-step extension of VAML (which was not introduced in that paper though).

(2) Is there any typo in Proposition 1(ii)? Currently, we have $\mathbb{M}^k$ there, but shouldn't it be $\mathcal{M}^k$? The same comment for Proposition 3.
Decision: Accept (Spotlight)