Approximate Value Equivalence
Authors: Christopher Grimm
Andre Barreto
Satinder Singh
Venue: NeurIPS 2022 Accept (2022)
Keywords: model-based reinforcement learning
reinforcement learning
value function
muzero
value equivalence
planning

Abstract: Model-based reinforcement learning agents must make compromises about which aspects of the environment their models should capture. 
The value equivalence (VE) principle posits that these compromises should be made considering the model's eventual use in value-based planning. Given sets of functions and policies, a model is said to be order-$k$ VE to the environment if $k$ applications of the Bellman operators induced by the policies produce the correct result when applied to the functions. Prior work investigated the classes of models induced by VE when we vary $k$ and the sets of policies and functions. This gives rise to a rich collection of topological relationships and conditions under which VE models are optimal for planning. Despite this effort, relatively little is known about the planning performance of models that fail to satisfy these conditions. This is due to the rigidity of the VE formalism, as classes of VE models are defined with respect to \textit{exact} constraints on their Bellman operators. This limitation gets amplified by the fact that such constraints themselves may depend on functions that can only be approximated in practice. To address these problems we propose approximate value equivalence (AVE), which extends the VE formalism by replacing equalities with error tolerances. This extension allows us to show that AVE models with respect to one set of functions are also AVE with respect to any other set of functions if we tolerate a high enough error. We can then derive bounds on the performance of VE models with respect to \textit{arbitrary sets of functions}. Moreover, AVE models more accurately reflect what can be learned by our agents in practice, allowing us to investigate previously unexplored tensions between model capacity and the choice of VE model class. In contrast to previous works, we show empirically that there are situations where agents with limited capacity should prefer to learn more accurate models with respect to smaller sets of functions over less accurate models with respect to larger sets of functions.

Approximate Value Equivalence
Christopher Grimm Computer Science Engineering University of Michigan crgrinmBumicht ch, edu
André Barreto DeepMind
andrrbbarreto@leeemind.ccmmm
Satinder Singh DeepMind bave jeeeejjaddeeedddcccm com com
Abstract
Model-based reinforcement learning agents must make compromises about which aspects of the environment their models should capture. The value equivalence (VE) principle posits that these compromises should be made considering the model's eventual use in value-based planning. Given sets of functions and policies, model is said be order-k VE the environment if A applications of the Bellman operators induced by the policies produce the correct result when applied to the functions. Prior work investigated the classes of models induced by VE when we vary k and the sets of policies and functions. This gives rise to rich collection of topological relationships and conditions under which VE models are optimal for planning. Despite this effort, relatively little is known about the planning performance of models that fail to satisfy these conditions. This is due to the rigidity of the VE formalism, as classes of VE models are defined with respect to exuct constraints on their Bellman operators. This limitation gets amplified by the fact that such constraints themselves may depend on functions that only be approximated in practice. To address these problems we propose approximate value equivalence (AVE), which extends the VE formalism by replacing equalities with error tolerances. This extension allows us to show that AVE models with respect one set of functions are also AVE with respect any other of functions if we tolerate a high enough error. We can then derive bounds on the performance of VE models with respect arbitrary sets of functions. Moreover, AVE models more accurately reflect what can be learned by our agents in practice, allowing to investigate previously unexplored tensions between model capacity and the choice of VE model class. In contrast to previous works, we show empirically that there are situations where agents with limited capacity should prefer to learn more accurate models with respect to smaller sets of functions over less accurate models with respect larger sets of functions.
Introduction
Reinforcement learning (RL) is general framework in which an agent learns to maximize the reward receives from its environment by interacting with [Sutton and Barto 2018). Though RL makes no prescriptions about their internal processes, agents are sometimes endowed with the ability to learn simulators of their environment, called models, which enable predicting the effects of sequences of actions without executing them in the environment. The subfield of RL which studies such agents referred as model-based reinforcement learning (MBRL.).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In classical MBRL, agents endeavor to learn models that accurately capture the dynamics of their environments and subsequently use these models in their estimation of the values of different policies. Though having an accurate model is sufficient for this task, they are frequently impractical to learn- as MBRL, agents are deployed in more complex environments, the demands of learning models which accurately capture these complexities become more severe. Fortunately, such models are not necessary for learning performant MBRL agents, as demonstrated by several recent works [Oh et al. 2017 Silver et al. 2017 Farquhar et al. 2018 [Schiittwiserr et al. 2020]. The agents in these works learn models that are accurate at what they are eventually used for: the estimation of policy values. In particular, these models are learnt to be able to accurately predict the values of policies in the environment rather than to be able to accurately predict the environment's dynamics.
Grimm et al. [2020, [021] provide theoretical underpinning for models learned in this way by establishing the value equivalence (VH) principle. VE partitions the space of models an agent can learn into different VE classes according to properties of their Bellman operators. For given integer k an order-k VE class consists of models whose k-step Bellman operators of certain policies match the environment's 's when applied to certain functions. The policies and functions used as VE constraints are the identifiers of the equivalent classes. Accordingly, much of the prior work on VE has concerned the selection of these sets such that the corresponding VE models are of use to an agent. In particular, Grimm et al. [202]] proved that any model in the infinite-orde VE-alse known as proper value equivalent or PVE class induced by all deterministic policies is sufficient for optimal planning. However, with the exception of this specific model class and its subsets, the analyses by
Grimm et al. 2020 2021] offer no bounds on the performance of other VE classes.
In this work we extend the VE framework by developing an approximate theory of value equivalence which augments VE classes with an error tolerance parameter that controls the degree to which models can violate their class' constraints (Definition D}. We call the resulting framework approximate value equivalence (AVE). While previous work on VE demonstrated topological relationships between specific instances of VE classes (e.g., between classes with order [Grimm et al., 2020] or between classes with fixed II and V and orders that are multiples of one another [Grimm et al. (02TT),
we show that arbitrary pairs of AVE classes can be topologically related by tolerating sufficient error (Proposition [ This allows to bound the performance of models in any AVE class in terms of the minimum error that must be tolerated in order to topologically relate it to a subset of the aforementioned PVE class (Proposition 2). In Section 4 we proceed by deriving series of topological relationships between AVE classes and leveraging this connection between topology and performance produce various performance bounds for AVE classes. We are ultimately able to combine these relationships together to produce a general performance bound over AVE classes with respect to arbitrary orders and function sets dramatically expanding the set of VE model classes with theoretical guarantees. Finally, we leverage our study of AVE classes to reveal previously overlooked tensions between model capacity and the choice of model class. In particular, we empirically demonstrate situations in which low-capacity agent achieves higher performance by learning a VE model with respect to fewer functions (and tolerating a lower approximation error) than by learning one with respect to more functions (and tolerating a higher approximation error).
Background
An agent's interaction with its environment is modeled using a Markov Decision Process (MDP) [Puterman| 1994] denoted by (S, A, 1,,,,,,, 7), where S is a state-space, AA is a set of actions that can be taken from each state, r(s, a) is the expected reward of taking action from state 8, p(s'|s o'|s, a) is the probability of transitioning to state s' when action a is taken from state s and E [0, 1] is discount factor. We additionally make the standard assumption that the environment has a finite maximum reward: Tmax = max r(s, a) < co. The behavior of an agent is specified by policy, S > P(A), where P(AA) is the set of probability distributions over A. We denote the set of all policies as In and the set of all functions mapping S + R as V. The performance of a policy in an MDP is measured by its value function:
8
Un (s) = ET.D
Σ
rr(SS,, A.)18 =
(I)
1=0
2

---

where En.pH denotes expectation over trajectories generated by policy т in an MDP with transition dynamics given by p. and S. and A, are random variables for the state occupied and action taken by the agent at timestep 1. We denote the set of all value functions in an environment as Vn = (U>
n).
An RL agent's goal is find a policy with maximal value across all states (Sutton and Barto 2018
This process can be carried out by alternating between computing the value of the agent's policy and improving it. Value functions can be computed iteratively using the policy's Bellman operator:
TH [s](s)
(=p(11)))))))) [r(s, A) + (r0(")),
which accepts function V and returns an updated function also in V. We use T to refer applications of Ta, also known as the policy's 's k-step Bellman operator. is known that, in the limit, k- step Bellman operators converge to their corresponding value functions: lim T [b] U, Ve E V. In RL it is assumed that the agent does not have access to r and p. and thus T= cannot be computed directly. MBRL addresses this problem by learning a model, mn = (f: p). that used in place of the environment's 's reward and transition dynamics to construct model Bellman operators, denoted Tz. We denote the model's 's maximum reward f fmax = maX,,a a(s,a).
Traditional MBRL methods attempt to learn models such that F = r and p = p [Sutton 1991]. In contrast, there are alternative paradigms in which model is learned with its eventual use in mind, such as value-aware model learning (VAML; [Farahmand et al. 2017) ) and the VE principle [Grimm et al. 2020]. This work concerns the VE principle, under which models are learned to support their eventual use in estimating value functions. Accordingly. VE delineates models according to VE constraints defined by policies π II and functions e E V. We denote the class of order-k VE models with respect to a set of policies C N and a set of functions C V as
M (TI, V) (m M T T v Vn II, Vo E V).
(3)
In the limit of k oo, Grimm et al. 2022 showed that order-k VE classes converge to special model classes whose models' value functions Ü lim T match those of the environment:
M (II)
(m E M ox Ur VT E II].
These limiting model classes referred to as proper value equivalent (PVE) due to their dependence on model and environment value functions. The PVE class with respect to all deterministic policies, dett. is denoted by M dIleet) and contains only models which can plan optimally. Notably, this is the only non-trivial model class within the VE framework with such a performance guarantee (Grimm al. [02T].
We say that set of functions V mapping S + R is bounded if there exists some Umax < 0C such that u(s) S Umax for all V and S. We also consider notion of boundedness for model classes, referring to a model class as bounded each model in it has bounded maximum reward: Fmax < 00 for each model m in the class.
3 Approximate value equivalence
We begin our treatment of the approximate theory of value equivalence by extending the definitions of order-A VE and PVE classes given in Eqs. and to the approximate setting. Recall that the exact versions of these model classes are characterized by sets of policies and functions which induce a set of VE constraints on the models' Bellman operators. In this work will consider model classes whose models can violate these constraints up to some limited degree, E T where Ii+ denotes the non-negative, extended real numbers: [0, ooj. We say that these approximate value equivalent (AVE) classes tolerate error.
Definition 1. (Approximate Value Equivalence) Given 11 1,, V.V.VV V and E E R_, we denote the set of order-k AVE models which tolerate e error as:
(II, e;+) = (m E M || T Se VT E V.
(5)
where || || denotes the Ex -oom.
Moreover, we can unalogously define approximate proper value equivalent (APVE) classes as follows:
- (m E M: 16 - < VT E
III.
(6)
3

---

3.1 Topological properties
In what follows we investigate the topologiaal properties of AVE classes, ultimately showing that, by introducing approximation to VE, we can relate arbitrary model classes. An order-k VE class is specified in terms of four quantities: a model class M. set of policies II, set of functions V, and an order k. /rimm et al. [2020) illustrated variety of topological properties of order-1 VE classes by studying the effect of varying M, IT and These results were later extended by Grimm et al. (202T) who also investigated the effect of varying the order k. We now conduct similar analysis of AVE classes, which are extensions of VE classes that depend on fifth quantity: an error tolerance c. We start by showing that AVE models are a strict generalization of VE models, which are special case when E = 0:
Property 1. For any 11 C UI, V C V and M C M, it follows that M (1L, V:0) (11, V) and M (II; 0) = M (II).
Proofs of these properties will be deferred to Appendix A.I Since Property | ttells us that AVE is generalization of exact VE, it is natural to inspect which other topological properties carry over.
C Property 2. For any E E R M C C M, 11 S I1' C Il and V = V C v, it follows that M c Vie) S M M (II, V;e).
(II, &
Property generalizss two of the topological properties described by Grimm et al. 20200] to AVE. In particular, the first subset relation in Eq. 7 shows that, like with VE, as the sizes of the sets of policies and functions increase, the corresponding AVE class shrinks. The second relation shows that as the set of models M increases in size, so too do AVE classes.
We now investigate the effect of the new parameter, the error tolerance e, on the topology of the resulting AVE classes:
Property 3. For any I V C V and é E R such that e' 2 e, it follows that
MT V:c) S (TIVV:))
(8)
Property 3 shows that increasing the tolerated error of an AVE class causes it include more models. While this is intuitive obvious, (e.g., "a model class that tolerates higher error also tolerates a lower error"), may be less straightforward that this property can be used to relate AVE classes with respect to arbitrary orders and sets of functions and policies.
Proposition 1. For any E R II' C V. V' CV and k, K E Z there exists some e' E R such that
MT C M (T',),,)))
Moreover, if M, V and V are bounded then e' is finite.
Proposition] D shows that it is possible to relate arbitrary AVE classes. This is significantly broader than previous topological results which VE classes could be related only when their corresponding sets of policies and functions were subsets of each other (when IT C IT' or V C V") [Grimm et al. 2020). or when the orders heing compared were multiples of each other (when divided K) [Grimm et al. 2021]. The proposition follows directly from taking the limit of e' - co in Property 3 by tolerating a high enough error any AVE class can be made to contain any other (as illustrated in Figure D.
Why is it important ensure that one AVE class is sub-class of another? We know that, if property applies to model class, it must also apply to any sub-class. Grimm et al. 2021 have shown that all models in M (Teet; 0) have the same optimal policy as the environment. They also showed that, without further assumptions, this is the "largest" model class with this property. However, prior to our work this was the only known theoretical statement about the performance of VE model classes.
Proposition] 1 aallows us to go much further and provide performance guarantees for any AVE class. This is possible because we know M 0) by tolerating a sufficiently large amount of error e' with respect to the latter model class. Obviously, the tolerated error e' will play role in the resulting performance guarantees. In general, the larger this error the weaker the guarantees. So, we are interested in finding the minimum that makes Proposition true.
relate arbitrary AVE classes of the form M (II, V/c) to

---

The minimum c' for which Proposition Toolds between any two AVE classes can also be thought of function, which we will refer to as the minimum tolerated error.
M (II, MI ve
Definition 2. (Minimum Tolerated Error) For any AVE classes (II,,, V) and MI(II' V'ee) we de- note the minimum e' E IR such that (II, V;e) M (TT', Vi v') as (TT, V (K).
MM V)
M Vie)
When K do we omit V reflect the fact that APVE classes do not depend on sets of functions, that is, we use (II, V. k II', oo) (and analogously for & oo we omit V). Note that the minimum tolerated error is well defined for any two AVE classes. Equipped with this concept, we can now present the following result:
Figure 1: An illustration of the impli-
Proposition 2. For any ñn (TI, V;6) it follows that |0a_ v. < 2 & (1I, V, o0),
cation of Proposition | as é' increases M (II', w;e') grows eventually to the point of containing (T, V;e).
where 7. is any optimal policy of m.
Proposition 2 shows that we can we can bound the per- formance of any AVE class M (II, V:e) e) in terms of its topological relationship with (I)) expressed through the minimum error tolerance & (II, V. |yk| (,, Accordingly, understanding how this function varies with respect to its inputs is crucial to determining the performance of models in M (II, V; c). It is worth emphasizing that (-1-) is fundamentally a function concerned with the topology of AVE classes and that Proposition 2 provides link between such topological properties and the performance of the corresponding models. In the following we will derive a series of novel topological relationships between AVE classes and use them to produce upper bounds on different minimum tolerated errors (- (--)). Through combining these relationships and their associated upper bounds will ultimately be able to derive upper bound & (U), V, l 01, oc) which can be used in conjunction with Proposition [2to provide performance guarantees for a wide range AVE classes.
Bounding the minimum tolerated error
Proposition 2 provides a means of converting upper bounds on minimum tolerated errors E, (II, V. IT, oc) into performance guarantees for models in M* (II, V:e). In this section we show how we can use topological relationships between AVE classes to produce such upper bounds. Remark 1. For any c, E R II C, V, V V and k. K E Z+ M (I1, C MK (1I, Ve:
(1L, V, II' V' sé.
Remark is direct consequence of Definition but is useful to state explicitly since connects the ensuing topological relationships to the upper bounds minimum tolerated errors which will be used to construct our performance guarantees. Having established this, we will now develop series of topological relationships between AVE classes of different kinds and use Remark to generate upper bounds. To facilitate our analysis, we will begin by varying aspects of these AVE classes in isolation, first focusing on those that differ in orders k and K and then those that differ in function sets V and V" Later, we combine these results to obtain an upper bound on & (n1, V, k M, oo) which will in turn yield generic performance bound for models in any AVE class, MM V)e), where and V are arbitrary orders and function sets.
4.1 Model class order and error tolerance
In this section we consider pairs of model classes that share a common set of policies II and functions V, but have different orders & and K. In particular, we explore this dependence in the special case in which & divides K and that V is closed under environment Bellman updates with respect to any of the policies in II.
Proposition 3. For any e E RR+, IIn. S such that v E V = Ta E V VT E II and k. K Z such that lo divides K, we have that
(IL M (I1, -(1->"))
(10)
5

---

Proposition 3 shows that, in our special case, our upper bound on the minimum tolerated error increases according to a multiplicative factor that depends on the orders and K. For fixed kt as K grows our upper bound will also grow, however the rate of growth is decreasing since the numerator of this factor, (1 - >*), approaches as K -> x. The fact that our upper bound does not grow without bound suggests that there is similar relationship between order-k: AVE and APVE classes. Indeed, by sending K - oo we obtain such relationship.
Corollary For any set of policies C M. set of functions V E V such that {vz : IT [T] S and k Zt, it follows that
(T, V3e) M (TI: (-)
(11)
Notice in Corollary D how the constraint on V has been relaxed, since now is no longer required that V be closed under arbitrary compositions of the Bellman operators of the policies in II. Instead, V must contain the value functions associated with II. This looser constraint implies that V can be finite when II is finite.
4.2 Function sets and error tolerance
In this section we consider two AVE classes with the same order k and set of policies II but different function sets, that is, we compare M (II, e) and (II, V'; e'). Though we are able to provide an upper bound on the minimum tolerated error for arbitrary function sets, it can be shown to scale differently when there are special relationships between V and V". We begin by examining this special case.
4.2.1 Related function sets
We begin by examining the case in which V consists of constrained linear combinations of the elements of V. particular, we consider set V of the following form:
c-vspan(V) = aa)u(s): Va, Σa.-1.
(12)
which we refer to as the constrained vspan of V with parameter c. The coefficients of the linear combinations in c-vspan(V) are constrained to sum and to have magnitudes which sum less
than c.
Grimm al. 2020 studied special case of Eq. 12 without the coefficient magnitude constraint (by taking C + (0) and showed that M (II, V: 0) = =M (II, O) (where V co-vspan(V)) Notice how, in the language of Proposition L we have just related two VE classes with different sets of functions and V without tolerating any additional error. However, this result is relatively narrow, only applying exact order-1 VE classes. In what follows we extend this relationship order-k: AVE classes:
Proposition 4. For any set of policies C U1, set functions V, c <>> and error e E R+, we have
(II
M (1, S MI c-vpan(V-v)a
(13)
Proposition Ceroosttioon4hhoon 4shows how M (IT, V;e) is "squeezed" between two other model classes whose function sets are replaced by c-vspan (V). In particular, by considering the rightmost subset relationship in Eq. [3] we see that the error term scales multiplicatively with c. It interesting to note that, for particular choices of e and c, the left- and right-most terms in Eq. 13 can be made identical, reducing the expression to an equality.
Corollary 2. When either = 1 for any 11 S U1, V C V follows that
M V;c) (IT
(14)
Note that, when e 0, Corollary _ recovers Grimm et al. 2020 's result by sending e - oo. On the other hand, when = 1, c-vspan()) reduces to the convex hull of V. In the context of Proposition I this means that, regardless of and k. we do not need tolerate any additional error for M (II, I-vspan(V); e) to contain *1* V;e).

---

4.2.2 Unrelated function sets
In the previous section studied the case in which the set V coincided with c-vspan()) consider a more general scenario where V and V are not assumed to have any relationship to each other. In this setting, will measure the similarity of sets of functions using distance function 3:2² 22 x 2" + R defined as
3(VIV)
max min ||e 10---i e'
(15)
v'EV' NEV
In words, 3 measures the greatest distance from any element in V to its closest element in V. Before continue, is worth pointing out some interesting properties of 3. Proposition 5.
1. (Asymmetry) For any V V V' V C follows that
0 = 3(VIV) & 8(1IV) & B(1[V") and 0 = -(V")1V") 8(V"))*) 3(11)")
2. (Convex, Compact V) When V is convex and compact it follows that
8(1DD) = 3[V||1-vspan (V)))
Proposition iillustratss several interesting features of B. Firstly, it measures the similarity between sets V and V"r asymmetrically: if V grows then 8 also increases, since there are more elements maximize over; however, if V grows, 3 decreases instead, since there are more elements to minimize over. Secondly, when V is convex compact set, V can be replaced with its convex-hull (equivalently, 1-vspan(-)) without changing 3.
Using the similarity measure 3, we then determine the amount of error an AVE class with respect to y must tolerate to contain counterpart defined with respect to V.
Proposition 6. For any II E n, V.V E V and c E R+, follows that
M (I, s M* 2x 27-3(111)))
moreover, V convex and compact, we obtain:
MT V:c) S SM 1-vspan()"); 2 8(V1)))))
Proposition shows that, for any two sets of functions V and V", our upper bound on the minimum tolerated error proportional to (>[[)>",, which we analyzed in Proposition In particular, we know that our upper bound increases V grows and decreases as V grows. In addition, in the special case in which V is convex compact set, V can be replaced by its convex hull without any increase in our upper bound.
4.3 Unifying results
In the previous sections studied upper bounds the minimum tolerated error such that models in particular kinds of AVE classes would be contained in other kinds of AVE classes. Each section concerned different type of upper bound constructed by varying certain aspects of the AVE classes: Section 4. held function sets fixed and varied model-class orders whereas Section (42 held model- class orders fixed and varied function sets. Now, combine these results to obtain more general theorem.
Theorem 1. For any II C n1 VCV, and e E R it follows that
M* C +
min(c- + 2 2 ((cvsspa((V)((n)) e21
which implies that
(11, V, k 11, 00) S T-
min(c-e e (
22
7

---

Proof. The proof follows by sequential application of our previous results.
(I, (1e) =. (II,,, cvssaa
(Proposition
_ (M Vnic. + 27 ((ccvspan
(Proposition 6
=N
n (" (wriic + 2 ((c)vspan(V)[[Mn)
=
s n (MT)
2 B(c ((cvvspa
(16)
Tell
S 0 M (( I- ( ((c-espan())]]
(Corollary
sell
M (II;
| 1-sx (c. e + 3 (c-vspan (V))spp((()[[[))))
Since Eq, 16 holds for e 1, follows that:
M (II, V:c) S M 1 e2
-mimiic c+ 22 (cvsspaaa)
Finally, using Remark we obtain the associated upper bound on (TT, V. oo)-
Theorem reveals an interesting tension. Notice how the quantity inside the minimum is determined by two terms, c e and 2- ((<-vspan(()]]] As grows, the first term increases; however, due the properties of / described in Proposition 5 the second term will shrink.
5 Bounds on model performance
Taken together Propositions I and 2 and Remark [ provide a pipeline for quantifying the performance for any AVE class MM (T), V; c). Propositions | form a powerful connection between the general topology of AVE classes and model performance terms of minimum tolerated errors (Definition Z Remark [T then allows us to use specific topological relationships between kinds of AVE classes to quantify these minimum tolerated errors using upper bounds (see Section 4). Accordingly, in
Section 4 produced topological results about AVE models when policy sets 11 and either order or function sets are held fixed. We ultimately combined these results into Theorem resulting in bound on the minimum tolerated error & (11, V, k 11, oc).
By combining Theorem with Proposition we can obtain a performance bound on AVE classes with respect to arbitrary orders and function sets:
Theorem 2. For any m E M (I,, V:c) follows that
||u - Uz. S
2 1-
min (c. + 27 Blcvspaaaaa())
(17)
e21
where is an optimal policy of m.
Theorem 2 suggests that ideal AVE classes have low error and function sets such that c-vspan()) 5 Vn. However, in practice an agent does not directly have control over error e with which it learns model. Rather, this error is dependent on the choice of V: some functions may be harder to learn VE models with respect to than others. Since finding a model that is VE with respect to small number of functions is generally casier, this dependence between and V introduces tension in the selection of the set V. The smaller the number of functions in V. the smaller the resulting e tends to be. but on the other hand the distance ((c-spaan))) generally increases (see Section 6 for an empirical illustration this tension).
One option for choosing V, which was explored in both Grimm et al. (2000] and Grimm et al. [021] to use some manageable set of value functions: (vn; H This is sensible as known that value functions form polytope Vn which could be covered by c-vspan(-) DDdashi et al. 2019]. However, value functions are quantities of the environment which are not assumed be known by the agent. At best, agent can produce estimates of such quantities.

---

Interestingly, our AVE formalism can address not only the error in the satisfaction of VE constraints but also in the estimation of functions that the constraints depend upon. If an agent can estimate each Ux; by Un; with bounded approximation error |Izz, ox S Fapprox, we have:
M (II f0x, 1imi:)) S M (II, {UT, 1i + 24 B( (
(18)
S M* (II, (Un, + 2 Expppox).
Eq. 18]shows that we can exchange the estimation error of functions in VE function sets for error in the satisfaction of VE constraints. That is, any model in the AVE class with respect to approximate value functions is also AVE with respect to actual value functions if we tolerate additional error proportional their estimation error. This ultimately means that we can bound the performance of models which are approximately VE with respect to functions that are not in Vn (that is, that are not value functions).
Corollary Let Vn= = (θz ι E nJ be sel of approximate value functions satisfying 1|v - G S for all π E IT. Then for any mn E MM cn; it follows that:
2(c + 2 Capprex)
|| - - 11
1-76
where 7a is any optimal policy in m.
6 Trade-offs between model capacity and function set size
In this section we show that our approximate formulation of VE can guide the choice of functions to learn a VE model with respect when model capacity is limited. In particular, show that, depending on the situation, an agent may prefer to either learn a VE model with respect to a larger class of functions (and tolerate higher approximation error e) or learn VE model with respect to a smaller class of functions (and tolerate a lower e). These situations are interesting because, as we showed in Theorem 2 higher approximation error results worse bounds on the planning performance of the associated mhichs-which raises the possibility that in certain situations a model with limited capacity might plan better when it VE with respect to fewer functions.
To illustrate situations where this might occur, we consider the tabular Four Rooms domain Sutton eet al. 1999] and learn tabular VE models whose per-action transition matrices are constrained to have rank at most R. We learn these models to be in the VE class M[,, V), where V is a set of D functions generated by sampling vos) Uniform(-10 10) for each E V and each s E S. Due to the rank constraint on the model, we will only be able to learn approximate VE models with varying error tolerances for different settings of R and D.
Figure 2 shows a histogram of the planning performance of such models. Each cell in the figure corresponds model associated with specific values of R and D, and the cells' color denotes the value of the model's optimal policy averaged over states and over 10 independent executions. Interestingly, near the bottom left portion of the histogram there is region in which low-capacity VE models with respect to small sets of functions perform better than their counterparts generated using more functions.
7 Related work
Our work directly extends previous theoretical results on VE to the approximate setting. This naturally situates us closest to the works that originally explicated value equivalence and its higher order analogues [Grimm et al. 2020 2021 Our effort in deriving performance guarantees for VE is also reminiscent of classical works that studied approximate forms of policy and value iteration [Bertskkas
and T sitsiklis 1995 Munos 2005].
closely related line of work is value-aware model learning (VAML, IterVAML, VaGraM) |Farah mand et al.) 2017] Farahmand (0188) Voeleker et al. (02T)). In VAML models are learned in order to minimize the discrepancy between their Bellman optimality operators and those of the environment. In practice, a family of functions is constructed and model is learned to minimize the maximum discrepancy across this family. In Iter VAMI, instead of minimizing the worst case discrepency across family of functions, the functions generated by the model during value iteration procedure.

---

In VaGraM. the authors consider similar diserepancy-basee loss as in VAML, but use Taylor series approximation avoid having loss terms involving the values predicted future states. This ultimately gives rise to a squared-error loss between predicted and actual next states weighted by the gradients value function. VE and VAMI. can be seen as complementary both concern models that are learned with their eventual use in mind, but VAML. focuses on the associated optimization problems of finding such models whereas VE focuses on characterizing these models into classes (and also providing performance guarantees in this work).
There have also been several re- cent empirical works which explored concepts adjacent to VE. Farquhar et al. [22T]] explored adding auxil- iary terms to different model learn- ing procedures which encouraged the learned models' Bellman operators and value estimates to satisfy the Bellman equations (i.e., to be self- consistent). They show that there are circumstances in which this leads to better data lata-efficiency in practice. An- other example is Nikishin et al. 2202], who study the problem of learning models whose Bellman optimality op- erators induce optimal policies in the environment. In the service of this, they propose using implicit differenti- ation [Christianson, [994] to compute gradients from the model's optimal- ity operator all the way to its optimal policy.
20.0
19
17.5
15
15.0
Num Functions
13
12.5
11
10.0
9
7.5
5
3
1
0.0
11
21
31
41
51
61
71
81
91
101
Figure Illustration of the trade-offs between VE model capacity and the size of V. From left-to-right the capacity of the models increase. from bottom-to-top the size of V increases. Each cell is colored according to the average value of the model's ''s optimal policy.
8 Conclusion and future work
We provided approximate theory of value equivalence that extends the existing VE formalism Grimm et al. 2020 2021]. The main concept introduced was a family of AVE classes whose models violate VE constraints up limited degree. We showed that,
product of introducing approximation to VE, arbitrary AVE classes can be related to each other topologically. Moreover, we showed that, by relating them to specific VE classes for which there are performance guarantees, can derive bounds on the performance of arbitrary AVE classes in terms of their topological properties. Motivated by this link between topology and performance bounds, we proceed to derive isolated topological relationships between AVE classes whose function sets, orders and error tolerances vary, which we then can combine produce bounds which hold over AVE classes with respect arbitrary orders, functions sets and еттоr tolerances. This addresses a fundamental open question in the VE theory: how provide performance guarantees for models that do satisfy the VE constraints exactly. It may be possible to derive topological relationships considering all constraints of VE class jointly and, in so doing, provide tighter performance bounds, but we leave this for future work. We also believe that the performance bounds we have introduced might give rise to new algorithms that attempt to minimize them, either directly or indirectly.
References
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming: an overview. In Proceedings of 1995 34th IEEE conference decision and control, volume 1, pages 560-564. IEEE, 1995.
Bruce Christianson. Reverse accumulation and attractive fixed points. Optimization Methods and Software, 3(4):311-326, 1994.
Robert Dadashi, Adrien Ali Taiga, Nicolas Le Roux, Dale Schuurmans, and Marc G. Bellemare. The value function polytope reinforcement learning- In Proceedings of the International Conference Machine Learning (ICML), volume 97, pages 1486-1455, 2019.
10

---

Amir-massouee Farahmand. Iterative value-aware model learning. In Advances in Neural Information Processing Systems (NeurIPS), pages 9090-9101, 2018.
Amir-Massoud Farahmand, André Barreto, and Daniel Nikovski. Value-Aware Loss Function for Model-based Reinforcement Learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 54, pages
1494, 2017.
G Farquhar, Rocktäschel, M Igl, and $ Whiteson. Treeqn and atreec: Differentiable tree-structured models for deep reinforcement learning. In 6th International Conference Learning Representa- lions, ICLR C0fffConfere Track Proceedings, volume 6. ICLR, 2018.
Gregory Farquhar, Kate Baumli, Zita Marinho, Angelos Filos, Matteo Hessel, Hado Philip van Hasselt, and David Silver. Self-consistent models and values. In NeurIPS, 2021.
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.
Christopher Grimm, André Barreto, Greg Farquhar, David Silver, and Satinder Singh. Proper value equivalence. Advances in Neural Information Processing Systems, 34, 2021.
Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005.
Evgenii Nikishin, Romina Abachi, Rishabh Agarwal, and Pierre-Lue Bacon. Control-oriented model-based reinforcement learning with implicit differentiation. ArXiv, abs/2106.03273, 2021.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In Advances in Neural Information Processing Systems, pages 6118-6128, 2017.
Martin L. Puterman. Markov Decision Processes Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitr, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7833):604-669) 2020.
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 on Machine Learming- Kcarning-Volume 70, pages 3191-3199, JMLR. org, 2017.
Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting. ACM Sigart Bulletin, 160):160 1991.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018 URL httpss//miipress mit wttp://oots/etttfooccaaaeeeeeeea 2nd edition.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):111-21, 1999.
Claas A Voeleker, Victor Liao, Animesh Garg, and Amir-massoud Farahmand. Value gradient weighted model-based reinforcement learning. In International Conference on Learning Represen- tations, 2021.

---

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 your work? [Yes] In the conclusion / future work
section.
(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] Most are in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(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)? [N/A]
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? [N/A]
(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? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or 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 participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "zl23edjuRe6", "reviewer": "Reviewer_pwPJ", "summary": "This paper proposes approximate value equivalence (AVE) which extends the previously proposed VE formalism by replacing equialities with error tolerances. With this extension, it shows that AVE models with respect to one set of functions are also AVE with respect to any other set of functions if a high enough error is tolerated, which then allows for deriving bounds on the performance of VE models with respect to arbitrary sets of functions by relating them to a particular model class with known performance guarantees. Finally, the paper supports these results by providing intuitions and discussions of their implications.", "questions": "**Major:**\n\n1. On the role of the deterministic policy set in PVE classes: Why does the PVE class wrt all deterministic policies contains only models which can plan optimally (see the last par. of Sec. 2)? I mean what is the role of determinism here? Why doesn’t the PVE class wrt all policies (including deterministic and stochastic ones) contains only models which can plan optimally?\n2. On the significance of the theoretical results in terms of practicality: In the previous studies of Grimm et al. (on VE), the authors have provided experimental results that either justify the usage of VE models or improve the currently existing algorithms. However, in this study there is no empirical demonstration of the usefulness of the theoretical results. Even though the theoretical results are interesting by themselves, I think that providing a section on how these results can at least help developing better VE MBRL algorithms can significantly benefit the paper. Is it possible to provide a discussion on how these theoretical results can be useful in giving rise to new algorithms?\n\n**Minor:**\n\n1. In Def. 1 and Property 1, $\\mathcal{V}$ should be a subset of $\\mathbb{V}$?\n2. I think the par. that starts with line 164 should explicitly mention that a certain amount of error will be tolerated for $\\mathcal{M}^{\\infty}$. I had to read it several times to get this part.\n3. In Prop. 2 should it be $\\mathbb{V}_{\\mathbb{\\Pi}}$ in the upper bound?\n4. Why is there $2^{\\mathbb{V}}$’s in line 242? Shouldn’t these be $\\mathbb{V}$’s?\n5. There is a typo at line 257 right after the second column.\n6. There seems to be a typo inside beta in Eq. 18 where one of the value functions should not have a hat?\n\nIf the authors are able to address the concerns provided in this review during the rebuttal period, I am willing to raise my score.\n", "limitations": "Yes the authors mention the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** The paper seems to be original in the sense that it extends the previously proposed VE formalism by replacing equialities with error tolerances and that it develops a whole variety of new theoretical results out of this. I am not aware of any study that does this. The related work section also seems to cover the related studies in the literature.\n\n**Quality:** Overall, there seems to be no serious quality issues with the paper. Though, I would like to indicate that I haven’t checked the proofs in a very detailed manner and just went over them at a high-level. The submission looks technically sound and the core ideas are well-explained. However, I do have a few major and (mostly) minor questions on the quality of the paper (see the Questions section below). \n\n**Clarity:** I found no problems with the clarity of the paper. The paper is very well-written. I have nothing to suggest.\n\n**Significance:** Even though the derived theoretical results seem to be interesting in their own sense, I would like to indicate that I found the paper to have problems in the significance of the results. More specifically, I am not sure if the paper provides enough discussion on how the derived results can be helpful in developing VE MBRL algorithms. More on this can be found in Question 2 below.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R_4G76nCgv", "reviewer": "Reviewer_3UJe", "summary": "This paper extends the notion of \"value equivalence\" among MDPs w.r.t. sets of policies and value functions (and number of steps) to \"approximate value equivalence,\" that permits the values after k steps of the policy to differ by  up to some parameter epsilon. It is then possible, for any two classes of models, to find an epsilon for which the models satisfy the definition. Bounds that relate the performance of policies across such approximate value equivalent models are also obtained.\n", "questions": "Can you point to evidence that it is productive to consider this notion? (See the last part of \"Strengths and Weaknesses\" for a couple examples of what this might look like.)", "limitations": "This is fine.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It seems clear that for the kind of models studied here, we need bounds that control how close the predicted performance is to performance in the actual environment, and it seems desirable to be able to obtain this for bounded orders. This is the main strength of the paper. \n\nThe notion of approximate value equivalence is a very natural generalization of the notion of value equivalence -- indeed, it borders on being \"obvious\" given the existing notion of value equivalence. I am not so moved by the results about relating arbitrary pairs of classes. I don't see the utility of this notion for such large values of epsilon as such relationships would require -- and indeed, intuitively, we would not expect totally arbitrary pairs to be \"equivalent\" in any meaningful sense. This dampens the significance of these contributions.\n\nWhat's really missing from this work is evidence that the definition can be made to do useful work for us. I'd want to see it used to analyze an algorithm or show that some MDP can be represented more compactly, or something of similar flavor.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Img1fRIDdC", "reviewer": "Reviewer_bf62", "summary": "The paper discusses the notion of _approximate value equivalence_ in model-based reinforcement learning. Approximate value equivalence is concerned with the study of families of models that yield $k$-step Bellman updates that are approximately equivalent to the Bellman update yielded by the true model, in the sense that---given a policy $\\pi$ in some set of policies and a value function $v$ in some set of functions---$\\tilde{\\mathcal{T}}^k_\\pi v\\approx\\mathcal{T}^k_\\pi v$ (here $\\tilde{\\mathcal{T}}_\\pi$ and $\\mathcal{T}_\\pi$ represent, respectively, the approximate and exact Bellman operators). The paper provides a number of results that relate different families of models in terms of the error that they incur in terms of Bellman updates. ", "questions": "My main question is related with the practical use of the bounds provided in the paper, in light of the difficulty of determining the factor dependent on the distance/divergence $\\beta$, and the minimum tolerated error $\\mathcal{E}_\\epsilon$.", "limitations": "N/A.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strong points:*\n* The problem addressed (understanding how approximate models impact the error incurred in the computation of the value function in RL) is important and interesting;\n* The presentation is very clear, well-organized, and several of the results are quite intuitive.\n\n*Weak points:*\n* The article is not self-contained, in the sense that most of the less intuitive results are presented with no hint on the proof. The paper still has available 1/2 page that could be used to provide even if a one-liner hint on how the result is established.\n* It is not clear what's the practical use of the proposed bounds. The authors make an effort in Section 5 to discuss this issue, but I believe that this is a core point in assessing the significance of the contributions of the paper. In particular, the provided bounds depend critically on the distance $\\beta$ and the minimum tolerated error $\\mathcal{E}_\\epsilon$, but---as far as I can understand---these are very difficult to assess in practical scenarios (particular in scenarios involving high-capacity approximations). Therefore, it would be important to discuss, in light of this, the practical use of the provided bounds.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept