Maximum Entropy Model Correction in Reinforcement Learning
Authors: Amin Rakhsha
Mete Kemertas
Mohammad Ghavamzadeh
Amir-massoud Farahmand
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning
model-based reinforcement learning
maximum entropy
planning
Primary area: reinforcement learning
TL;DR: Planning algorithm that corrects the model

Abstract: We propose and theoretically analyze an approach for planning with an approximate model in reinforcement learning that can reduce the adverse impact of model error. If the model is accurate enough, it accelerates the convergence to the true value function too. One of its key components is the MaxEnt Model Correction (MoCo) procedure that corrects the model’s next-state distributions based on a Maximum Entropy density estimation formulation. Based on MoCo, we introduce the Model Correcting Value Iteration (MoCoVI) algorithm, and its sampled-based variant MoCoDyna. We show that MoCoVI and MoCoDyna’s convergence can be much faster than the conventional model-free algorithms. Unlike traditional model-based algorithms, MoCoVI and MoCoDyna effectively utilize an approximate model and still converge to the correct value function.

Published as a conference paper at ICLR 2024
MAXIMUM ENTROPY MODEL CORRECTION IN REINFOR LEARNING
Amin Rakhsha's 1.2 Mete Kemertas Mohammad Ghavamzadeh" Aaaaaazzdeei"AAiiimmmmsuuuu Farahmand Department of Computer Science, University of Toronto, Veecoor Institute, 3 AAmazon lamir, kemertas, farahmand (cs. toronto. edu, ghavamza amazon. com
ABSTRACT
We propose and theoretically analyze approach for planning with an approximate model in reinforcement learning that can reduce the adverse impact of model error. If the model is accurate enough, accelerates the convergence the true value function too. One of its key components is the MaxEnt Model Correction (MoCo) procedure that corrects the model's s next-state distributions based on Maximum Entropy density estimation formulation. Based on MaxEnt MoCo, we introduce the Model Correcting Value Iteration (MoCoVT) algorithm, and sampled-bar variant MoCoDyna. We show that MoCoVI and MoCoDyna's 's convergence can be much faster than the conventional model-free algorithms. Unlike traditional model- based algorithms, MoCoVI and MoCoDyna effectively utilize approximate model and still converge to the correct value function.
INTRODUCTION
Reinforcement learning (RL) algorithms can be divided into model-free and model-based algorithms based on how they use samples from the environment with dynamics P. Model-free algorithms directly use samples from to approximately apply the Bellman operator value functions. At its core, the next-state expectations Ex'=P( [x(X')] are estimated for a function o, such as the value function, at all state-action pairs (xr, a). Model-based reinforcement learning (MBRL) algorithms, on the other hand, use samples from the environment to train world model P to approximate P. The world model P can be considered approximate but cheap substitute of the true dynamics P. and is used instead P to solve the task.
The world model P often cannot be learned perfectly, and some inaccuracies between P and P is inevitable. This error in the model can catastrophically hinder the performance of an MBRL agent, especially in complex environments that learning accurate model is challenging (Talvitie, 2017: Jafferjee et al., 2020; Abbas et al., 2020). In some these challenging environments, estimating the next-state expectations accurately might be much easier than learning model. Motivated by this scenario, we aim to bridge the gap between model-based and model-free algorithms and ask: Can we improve MBRL algorithms by using both the next-state expectations and the approximate model P??
In this paper, consider discounted MDP with the true dynamics P, and we suppose that we have access an approximate model P z P. At this level of abstraction, we do not care about how P is obtained - it may be learned using a conventional Maximum Likelihood Estimate (MLE) or it might be a low-fidelity and fast simulator of the true dynamics P. We further assume that for any function & of states, we can obtain the next-state expectations Ex Ex--(() [Ø(X)) X')] for all states x and actions a. We consider this procedure costly compared to ones involving P which will be considered free.
We propose the MaxEnt Model Correction (MaxEnt MoCo) algorithm, which can reduce the impact of model error on MBRL agents regardless of their plamning algorithm. MaxEnt MoCo first estimates Ex'=(()) job. (X')] for all (xr a) and set of measurement functions éi. The main idea is that whenever the planning algorithm normally uses P(-|z, a) for some state-action (I, a). a corrected distribution P calculated and used instead. The distribution is obtained by minimally modifying Pl a) that the next-state expectations E [o [X')) based on are (more) consistent with the estimated Ex (. (xx('))) (X')). This procedure is known as Maximum Entropy density estimation (Dudik et al., 2007) hence the name MaxEnt MoCo. We show that if the true value function can

---

Published as a conference paper at ICLR 2024
be well-approximated by linear combination of the measurement functions 6., the value function estimated by MaxEnt MoCo can be significantly more accurate than the normally computed one using P.
We also introduce Model Correcting Value Iteration (MoCoVI) (Section 4) and its sample- based variant MoCoDyna (Section 5), which iteratively update the set of measurement functions Φ.. These algorithms select their past value functions as the measurement functions, and execute MaxEnt MoCo to get a new, more accurate value function. This choice of measurement functions proves to be effective. We show that if the model accurate enough, MoCoVI and MoCoDyna can converge the true value function, and the convergence can be much faster than a model algorithm that doesn't t have access to model. In this paper, we study the theoretical underpinnings of maximum entropy model correction in RL. We provide theoretical analysis that applies to both finite and continuous MDPs, and to the approximate versions the algorithms with function approximation.
BACKGROUND
In this work, we consider discounted Markov Decision Process (MDP) defined as M = A, R. P.)) (Szepesvári, 2010). We use commonly used definitions and notations, summa- rized in Appendix B. We briefly mention that we denote the value of a policy by V and the optimal value function by V*. Whenever we need to be explicit about the dependence of the value functions to reward kernel R and the transition kernel P. we use V (*,R, P) and V* P). For
any function Ø: X + R. we define Po: X x A R as (Po) a) & P(dx' (z, a))(x') for all (x. E X' x A. We refer to the problem of finding V for a specific policy TPE as the Policy Evaluation (PE) problem, and to the problem of finding an optimal policy as the Control problem. In this paper, we assume an approximate model P ~ P is given.
We define V and म* in the approximate MDP M (2, R. P,7) similar to their counterparts in the true MDP M. We assume the PE and control problems can be solved in M as it is a standard part of MBRL algorithms.
2.1 IMPACT OF MODEL ERROR
In MBRL, the agent relies on the approximate model P to solve the PE and Control problems (Sutton, 1990). A purely MBRL agent learns value functions and policies only using P. which means it effectively solves the approximate MDP M (X' A, R, P, 7) instead of the true MDP M. The advantage of this approach is that it only requires access the cost-efficient P. hence avoiding costly access to P (e.g.. via real-world interaction). However, the model error can dramatically degrade the agent's performance (Talvitie, 2017; Jafferjee al., 2020; Abbas al., 2020). The extent of the performance loss has been theoretically analyzed in prior work (Ávila Pires and Szepesvári, 2016; Talvitie, 2017; Farahmand et al., 2017; Farahmand, 2018). To characterize model errors and their impact mathematically, we define the following error measure for each state-action pair (I, a):
EModel a) = V DKL P(- a) || ((-1x,)) a) ).
(2.1)
We note that the choice of KI. divergence for quantifying the model error is natural one. Indeed, in conventional model learning (see c.g., Janner et al. 2019), common choice of optimization objective the maximum likelihood estimation (MLE) loss, which minimizes the empirical estimate of the KL-divergence of the approximate next-state distribution to the ground-truth. The following lemma provides performance guarantees for an MBRL agent as a function of Model. Similar bounds have appeared in recent work (Ávila Pires and Szepesvári, 2016; Farahmand, 2018: Rakhsha et al., 2022). Lemma 1. Suppose that P is the true environment dynamics, P. is approximation of P, and [|eModel loo = suux,,axXxx (Madel (I, a) is the worst-case error between them. Let C1 =212/(1 7). We have T|V V/ S 1 11 - -pmm)) ffam)/aalllll Va S ei cilleModallix || || and
||*
- y* 1 <
20, |/leeeeetaall Il ||V*
I-cylleModal
Note that the model error impacts the PE solution through the term (pr - pmm) V A similar observation can be made for the Control problem. This dependence has been used in designing value-aware losses for model learning (Farahmand et al., 2017; Farahmand, 2018; Voelcker et al., 2022; Abachi et al., 2022) and proves to be useful in our work well.
2

---

Published as a conference paper at ICLR 2024
2.2 MAXIMUM ENTROPY DENSITY ESTIMATION
Consider a random variable Z defined over domain 2 with unknown distribution E M(2), and set of measurement functions Oi 2 IR for i 2,..... ...,, Suppose that the expected values 6, = that bg (2) matches Φe for all i. For example, if 2 = IR, Φ1(2) = 2, and (2(2) = =², we are interested in finding a q such that its first and second moments are the same p p's.
of these functions under p are observed. Our goal is to find a distribution such
In general, there are many densities that satisfy these constraints. Maximum entropy (MaxEnt) princi- ple prescribes picking the most uncertain distribution measured via (relative) entropy that is consis- tent with these observations (Jaynes, 1957). MaxEnt chooses qº = (e) H where H (q) is the entropy of q, equivalently. it minimizes the KL divergence (relative entropy) between q and the uniform distribution (or Lebesgue measure) u, i.e., q" = argmin (ox DxL q (| u u).
In some applications, prior knowledge about the distribution q is available. The MaxEnt principle can then be generalized to select the distribution with the minimum KL divergence to prior p:
argmin (Z)
DRI q i.
(2.2)
This is called the Principle of minimum discrimination information or the Principle of Minimum Cross-Entropy (Kullback, 1959; Shore and Johnson, 1980; Kapur and Kesavan, 1992), and can be viewed as minimally correcting the prior ý to satisfy the constraints given by observations 6;- line with prior work, we call density estimation under this framework MaxEnt density estimation whether or not the prior is taken to be the uniform distribution (Dudík et al., 2004; Dudík et al., 2007).
While the choice of KL divergence is justified in various ways (e.g.. the axiomatic approach of Shore and Johnson 1980), the use of other divergences has also been studied in the literature (Altun and Smola, 2006; Botev and Kroese, 20111 1). Although we focus on KL divergence in this work, in principle, our algorithms can also operate with other divergences provided that solving the analogous optimization problem of the form (2.2) computationally feasible.
Problem (2.2) and its variants have been studied in the literature; the solution is member of the family of Gibbs distributions:
d Σ (xx((2) - - -Ax)
(x(A)= = f p(dz) exp
(2.3)
=EA
where A C 2, X E Rd, and Ax is the log normalizer, i.e., Ax = log f(dz) exp Ee Aede(z)).
The dual problem for finding the optimal À takes the form
X = aargarnnoo log AERd
/ p(dz) exp
Σ (()e(()
d
Σ X
d
(2.4)
Iterative scaling (Darroch and Ratcliff, 1972: Della Pietra et al., 1997), gradient descent, Newton, and quasi- quasi-Newton methods (see Malouf, 2002) have been suggested for solving this problem. After finding A", if Varlexp( (+))( for 2 ~ á is small, e.g. when ý has low stochasticity, A can be estimated with samples from p. Then, one can sample from q" by sampling from Zo ~ P and
assign the importance sampling weight exp (Σi= (Z)) Ax- In general algorithms such Markov Chain Monte Carlo can be used for sampling (Brooks et al., 20. When the observations 5, are empirical averages, Maximum entropy density estimation is equivalent to maximum likelihood estimation that uses the family of Gibbs distributions of the form (2.3) (Della Pictra et al., 1997).
3 MAXIMUM ENTROPY MODEL CORRECTION
As discussed in Section 2.2, MaxEnt density estimation allows us correct initial estimated distribution of random variable using the expected values of some functions of it. In this section, introduce the MaxEnt Model Correction (MaxEnt MoCo) algorithm, which applies this tool to correct the next-state distributions in the approximate model Pe towards the true distributions in P.
3

---

Now, we introduce the MaxEnt MoCo algorithm. In large or continuous MDPs, is not feasible to perform MaxEnt density estimation for all x, a. Instead, we take a lazy computation approach and calculate P(- jr, a) only when needed. The dynamics P. : X x - M(X)) is never constructed as a function of states and actions by the agent, and it is defined only for the purpose of analysis. First, we obtain Pét, for = 1, 2....... d through queries to the true dynamies P. Then, we execute any planning algorithm that can normally be used in MBRL to solve the approximate MDP M. The only modification is that whenever the plamning algorithm uses the distribution P0- a) for some state Published as a conference paper at ICLR 2024
We assume that for any function o: X - R. can obtain (an approximation of) Ps. This operation is at the core of many RL algorithms. For instance, each iteration is of Value Iteration (VI) involves obtaining PV₁ for value function Vg. This procedure can be approximated when samples from P are available with techniques such as stochastic approximation (as in TD I Learning) or regression (as in fitted value iteration). Due to its dependence on the true dynamics P. we consider this procedure costly and refer to it as query. On the other hand, we will ignore the cost of any other calculation that does not involve P. such as calculations and planning with P. In Section 3.1, we consider the exact setting where similar to the conventional VI, we can obtain Po exactly for any function Φb X' - IR. Then in Section 3.2, we consider the case that some error exists in the obtained Ptò which resembles the setting considered for approximate VI.
3.1 EXACT FORM
In this section, we assume that for any function Φ: X + R. we can obtain Po exactly. We show that in this case, MaxEnt density estimation can be used to achieve planning algorithms with strictly better performance guarantees than Lemma To see the effectiveness of MaxEnt density estimation to improve planning, consider the idealized case where the true value function VT for the PE problem is known to us. Consequently, we can obtain PV by querying the true dynamics P. Assume that we could perform MaxEnt density estimation (2.2) for every state and action a. We minimally change ( ar, a) to new distribution ((1|2r, a) such that IE (x [VTE (X') (PV (2,, a).
We then use any arbitrary planning algorithm using the new dynamics P instead of P. which means we solve MDP M = (X' A. R, P) instead of M. Due to the constraint in finding P. we have PV/M " therefore TTE + 7/P T THE + TPP V V In other words, V satisfies the Bellman equation in M. This means that MaxEnt MoCo completely eliminates the impact of the model error on the agent, and we obtain the true value function V/H, The same argument can be made for the Control problem when we know V and correction is performed via constraints given by PV The true optimal value function V satisfies the Bellman optimality equation in M, and it can consequently be shown that the optimal value function / and policy म in M match V and n².
In practice, the true value functions V TT or V* are unknown - we are trying to find them after all. In this case, we do the correction procedure with set of measurement functions funciiio .1.... Qa with o, X' - R. The set of measurement functions can be chosen arbitrarily. As shall be clear later, we prefer to choose them such that their span can approximate the true value function V V well. In this section and Section 3.2, we focus on the properties of model error correction for any given set of functions. In Sections 4 and 5, we will introduce techniques for finding good set of such functions.
and action a, e.g. when simulating rollouts from (z, a), we find a corrected distribution P(-|ær, a) using MaxEnt density estimation and pass it to the planning algorithm instead of P(-|x, a) that would normally be used. The new distribution P(1 a) is given by
P(-12, e argmin DKL q P(-12,
(PI)
qEM(X)
such that Ex-
(z)
(i= 1,,.,...., .).
As discussed in Section 3. the optimization problem (P1) can be solved through the respective convex dual problem as (2.4). Also note that the dual problem only has parameters, which is usually small,' and solving it only involves P that is considered cheap.
For a reference, in our experiments d < 3. Even if d is large, specialized algorithms have been developed to efficiently solve the optimization problem (Dudfk al., 2007).
4

---

Published as a conference paper at ICLR 2024
We now analyze the performance of MaxEnt MoCo in PE. Let V be the value function of TeE in MDP M = (A, R. P.y). We will show that the error MaxEnt MoCo depends on how well T can be approximated with linear combination of the measurement functions. To this, first note that the constraints (P1) mean that (Pmee p )0; = 0. Thus, for any w E RRd we can write the upper bound on ||V Va olo that is given in Lemma
7 |( - pam Vam
- ( P
7
Σ with)
(3.1)
1-7
22
sup V DEL P(- a) || (( a) 2,a
w.
where the last inequality is proved similar to the proof the second inequality Lemma 1. Now, from the general Pythagoras theorem for KL-diieegencc (see Thm. 11.6.1 of Cover and Thomas 2006), for any (x, a), we have
D a() P(|az, a) S D P(+ a) P()1,a))
(3.2)
This inequality is of independent interest as it shows that MaxEnt MoCo is reducing the MLE loss of the model. It is worth mentioning that since P not constructed by the agent, this improved MLE loss can go beyond what is possible with the agent's model class. A feature that is valuable in complex environments that are hard to model. Inequalities (3.2) and (3.1) lead an upper bound on || 7T oc We have the following proposition:
Proposition Suppose that P is the true environment dynamics, P an approximation of and Model is defined as (2.1). Let C1 2V2/(1 (1) as in Lemma Then,
d Σ
Va
S ci |lllMeletlloo
inf
wiss
wERd
2e1 |||Model inf
V - v=
V
Σ
wiss
1 ci ||
WERd
The significance of this result becomes apparent upon comparison with Lemma 1. Whenever the value function can be represented sufficiently well within the span of the measurement functions {dr} used for correcting P,, the error between the value function The of the modified dynamics P compared to the true value function /T is significantly smaller than the error of the value function TH obtained from P compare inf | -i W;Orlloc with ||V
3.2 APPROXIMATE FORM
In the previous section, we assumed that the agent can obtain PΦ; exactly. This is an unrealistic assumption when we only have access to samples from P such as the RL setting. Estimating Pé; from samples is regression problem and has error. We assume that we have access to the approximations v/: X x
R of Po; such that v/ = PΦ: with the error quantified by CQuery- Specifically, for any (z, a), we have EQuery (z, a) [ a) (Pø)(z, a)ll2 where Φ: X - Rd and vb: X A R are the d-dimensional vectors formed by Φ; and th functions.
When the observations are noisy, MaxEnt density estimation is prone to overfiting (Dudík et al., 2007). Many techniques have been introduced alleviate this issue including regularization (Chen and Rosenfeld, 2000a; Lebanon and Lafferty, 2001), introduction of prior (Goodman, 2004), and constraint relaxation (Kazama and Tsujii, 2003; Dudík et al., 2004). In this work, we use & regularization (Lau, 1994; Chen and Rosenfeld, 2000b; Lebanon and Lafferty, 2001; Zhang, 2004; Dudík et al., 2007) and leave the study of the other approaches to future work.
The regularization is done by adding | to the objective of the dual problem (2.4). This pushes the dual parameters remain small. The hyperparameter 3 controls the amount of regularization. Smaller leads a solution closer to the original one. Notice that with extreme regularization when oc, we get X 0, which makes the solution of MaxEnt density estimation the same as the
5

---

Published as a conference paper at ICLR 2024
initial density estimate p. The regularization of the dual problem has intuitive interpretation in the primal problem. With the regularization, the primal problem (P1) is transformed to
P(-aa, a) A argmin D a ((112, a) )
3 g (xx) -xx)
(P2)
We now have introduced new hyperparameter 3 to MaxEnt MoCo. As 3 + O, the solution converges to that of the constrained problem (PI), because intuitively. 3 controls how much we trust the noisy observations 14. Smaller values of 3 means that care about being consistent with the queries more than staying close to P, and larger values of 33 shows the opposite preference. It turns out the impact of the choice of B is aligned with this intuition. As Model oc increases or || decreases, we should rely on the queries more and choose a smaller 3. We provide the analysis for general choice of [ in the supplementary material, and here focus on when B = ||equery M|Model
Theorem 1. Lel C1 = 2/12/(1 - 7). c2 = 33vdd/(1 - 7), and B = || / MModel locc For any Wmax 2 have
V VT
S 30 Malel loo [ loo wmax
inf
V
With
+ 02 +c2|| ||//equeryylla llac Waax
i=1
| v*
11-5
- 1 - --1ccl [eoollMo
6Cg Medlllldelloooo
inf Swmse
v
Σ
+ 00 - 3c1 |eModel
202 202]|eQuerylle Iloo
Wmax-
||
The above theorem shows that the error in the queries contribute an additive term to the final bounds compared the exact query setting analyzed in Proposition 1. This term scales with wmax which can be chosen arbitrarily to minimize the upper bound. Larger values of Umax allow better approximation of t and V in the infimum terms, but amplify the query error <Query- Thus, if Va (or V*) can be approximated by some weighted sum of the measurement functions using smaller weights, Wmax can be chosen to be smaller. Unlike the exact case discussed in Proposition 1, the choice of measurement functions is important beyond the subspace generated by their span. Therefore, transformations of the measurement functions such as centralization, normalization, or orthogonalization might improve the effectiveness of MaxEnt Model Correction.
One limitation of the results of Theorem 1 is that they depend on the le norm of éModel and EQuery- However, if the functions P and 4/s are estimated with function approximation, their error is generally controlled in some weighted Ep norm. Thus, error analysis of RL algorithms in weighted Ep norm is essential and has been the subject of many studies (Munos, 2003; 2007; Farahmand et al., 2010; Scherrer et al., 2015). We do provide this analysis for MaxEnt MoCo, but to keep the main body of the paper short and simple, we defer them the supplementary material.
4 MODEL CORRECTING VALUE ITERATION
In the previous section, introduced MaxEnt model correction for given of measurement functions Φ1,..., hs. We saw that a good set of functions is one that for some w E Rd, the true value function mi or V* is well approximated by Σ; w. In this section, we introduce the Model Correcting Value Iteration (MoCoVI) algorithm that iteratively finds increasingly better measurement functions. We show that if the model is accurate enough, Mo can utilize the approximate model to converge to the true value function despite the model error, and do so with a better convergence rate than the conventional VI. Since MoCoVI calls the MaxEnt MoCo procedure iteratively, we introduce notation for it. If P is the corrected dynamics based on the set of measurement functions & and their query results V, and V Aie. V*, म are the respective V Van, V* "²."" TT" in M = A, A, R, P), we define MoCo x 3 (R. PD, Φb V) A Va and MoCoz(R P, + V) A (V*, t to be the solution of PE and Control problems obtained with MaxEnt MoCo.
To start with, consider the PE problem and assume that
make exact queries P. We set o1....,0, Ox: X + I to be an arbitrary initial set of measurement functions, with query results v/ = Pob for 1 < i < d. We perform the MaxEnt MoCo procedure using &1ad and th to obtain

---

Published as a conference paper at ICLR 2024
Vi = M & (R, P, #1.d; t/1:)). In the next iteration, set Φd+1 Vo.² Then, query P at Φd+1 to obtain da+1 Po4+1. By executing MaxEnt MoCo with the last d queries, we arrive at Vi 3oCo (R, P. 22.411 (2d411). We can use Proposition to bound the enoor of V1-
7 |V - V2llo S 1-7 ||eMMddell
inf weR
VT Di=12,01+1
|| Volloo
| Vollxo
As Ex= 0;0++ ; is equal to Vo with the choice of Wind-1 = 0 and wi 1, the fraction above is less than or equal to Generally, the fraction gets smaller with larger d and better measurement function, leading to more accurate V1. If the model is accurate enough, the new value function Vi is more accurate approximation of VA than the initial Vo. By repeating this procedure, we may converge to the true value function
VT
We now introduce MoCoVI based on the above idea. We start with an initial set of measurement functions $1 ......: &a and their query results t/1, t/,,..,, tha such that v/s ~ Pés for 1 S i S d. At each
iteration & 2 0, we execute MaxEnt MoCo with @++ and +x+ to obtain V& (and my).. In
the end, we set @x+d+1 V₂ and query P to get the new query result. That is, for any k 2
S = 3M (R, P. PR v++1sk+a) or VEL = MoCo P, @k+Istd vk+1+++d) (b+dd+1 Vx, th++d+1 R Pos+d+1.
The choice of value functions can be motivated from two viewpoints. First, it has been suggested that features learned to represent the past value function may be useful to represent the true value functions as well (Dabney al., 2021). This suggests that the true value function may be approximated with the span of the past value functions. A property shown to be useful in Theorem 2. Second, this choice means that the corrected transition dynamics P at iteration & will satisfy PV--s R PVA-; for i = 1.2..... ... d. This property has been recognized to be valuable for the dynamics that is used for planning in MBRL, and implemented in value-aware model learning losses (Farahmand et al., 2017; Farahmand, 2018; Abachi et al., 2020; Voelcker et al., 2022; Abachi et al., 2022). However, practical implementations of these losses has been shown to be challenging (Voelcker et al., 2022: Lovatto et al., 2020). In comparison, MoCoVI works with any model learning approach and creates this property through MaxEnt density estimation. The next theorem provides convergence result of MoCoVI in supremum norm based on the analysis in Theorem 1.
Theorem 2. Let K 2 1. Assume Query (x,a)= a) Vd sup (Pε,) a) (x( and
[[cquery] ao /lo//l//oooo MMoealloooo Let C1, 02 be as in Theorem and Wmax 2 1. Define plarget = t for PE and Vtarget = V for Control. Finally, let
inf well Samar Vtarget Eim widh+slloo
r' = 3c |eModet
max ISASK
Vtarget - Ve-1lloc
We have
1 7 c2ll cell=Query Qqueryyla llse Wmax:
|| -Vxllo S
-ooloo
+ 1 1-
2 ||V - VT 100 S 1- 3c, c|Moeell
1 1- / 202 @uereyyyll l + 1 3' 3ca [cModel
||V - Volloo
Wmax--
This result should be compared with the convergence analysis of approximate VI. Notice that both MoCoVI and VI query once per iteration, which makes this comparison fair. According Munos (2007), V V* |1.c for VI is bounded by 2nd
2 ||&Querylloo. Here we considered the error in applying the Bellman operator equal the query error. In VI, the initial error ||V* Voll o decreases with the rate O(>*), In comparison, for MoCoVI, the initial error decreases with the rate (²) While the convergence rate of VI is tied to the fixed parameter y and become undesirable if y is close to 1, the rate of MoCoVI improves with more accurate models. Consequently, the convergence rate of MoCoVI can be much faster than VI if the model is accurate enough.
1-1 I|V Volla + 2x(1- (1-7)²
According to the discussion after Theorem 1, might he heneficial to set ds+1 to some linear transformations of Vo presence of query error. For the sake of simplicity of the results, we don't 't consider such operations.
7

---

Published as a conference paper at ICLR 2024
Algorithm I MoCoDyna(T,d,,s) K)
1: Initialize .1,.... ................................ Oetcr 0eter 1h....., Pates and P,
2: for t= 1.2...., ......TT6. do
3: Sample X,, Ar, Re: X2 from the environment.
4: r, - Upd P.Xe. As, X.).
5: Wi:dto + Update(1baaat (1hi:tta Xe, At, X()
6: Vi + MoCo3 (r, P. tist, viaa) or VA + MoCo)(f or:a t1.a),
7:
if mod K = 0 then
8: Pop P1, 1/1
Pd+c MeasurementCCrettion (1d-c-11 Va+c(a,
closely comparable algorithm to MoCoVI is OS-VI (Rakhsha et al., 2022). OS-VI also does solve a new MDP at each iteration, but instead of changing the transition dynamics, changes the reward function. The convergence rate of OS-VI, when stated in terms of our Model using Pinsker's inequality, is ci ||eModel] In comparison, 7 can become much smaller if the past value functions can approximate the true value function well or dl is increased. Moreover, OS-VI can diverge if the model is too inaccurate, but even if / > 1, the bound given in Theorem I still holds for V& for all k which means MoCoVI does not diverge.
MODEL CORRECTING DYNA
We extend MoCoVI the sample- sample-based setting where only samples from the true dynamics are available. The key challenge is that we can longer obtain th from de by single query. Instead, we should form an estimate of Pdb using the samples. In general, this a regression task that studied in supervised learning. In algorithms that a replay buffer of transitions (X4, A,, R2, X is stored, the regression can be done with (X,, A,) as the input and Φx (X;) as the target. In this paper, present version of the algorithm based stochastic approximation, but emphasize that the algorithm can be extended to use function approximation without any fundamental barriers.
For some integer 2 0, keep d + c measurement functions $1...., Pdte. As explained later, this set functions is updated similar to MoCoVI: the oldest function is regularly substituted with the current value function. A set of approximate query results vh,,..., thtt for the measurement functions is also maintained. That is, we will have th s Po; for each i via stochastic approximation. At each step, we get a sample (Xe, Rs,
An overview of MoCoDyna for finite MDPs is given in Algorithm 1.
X/) from the environment. We update bh (X,, Ar) for i = 1,...,, d c by
(X,,, 2. Ar) f (), A.) N.X...A)) (X,) - (X,, A.)). Here, [N,, A.) is the number of times (Xe, Ar) has been visited since the function Φb has been added to the set of measurement functions. At every step, the agent also updates its approximate model F, P with (X,,At. R₁, X;).
At each iteration, MoCoDyna runs the MaxEnt MoCo procedure to obtain the new value function and policy. That is, the agent uses an arbitrary planning algorithm to solve the PE or control problem with rewards f and the dynamics obtained by correcting P. The correction only uses the d oldest measurement functions among the d + c functions. The reason is that for a measurement function ø that has been added the recently, the agent has not had enough samples to form an accurate approximation of Po.. Finally, every steps, the agent updates its set measurement functions. The oldest function di is removed along with 11. The new measurement function Φa4c is chosen such that V, belongs to span of 01.dte- In the simplest form, we can set óste = V₁, but as discussed after Theorem some linear transformations might be beneficial. We allow this transformation by defining date + Measurement Vi, 01.d+c-1).
NUMERICAL EXPERIMENTS
We empirically show the effectiveness of MoCoVI and MoCoDyna to utilize an approximate model. We consider the 6 x 6 grid world environment with four actions introduced by Rakhsha et al. (2022), with y = 0.9. We defer the details of the environment to the supplementary material. As shown in Theorem 2, the convergence rate of MoCoVT depends on the model error and d. We introduce emror
8

---

Published as a conference paper at ICLR 2024
Low Model Error
Medium Model Error
High Model Error
10
Normalizes aaldddzzdde JIV.
10
10-2
10-3
14
100
10
Iteration (k)
MoCovi (d-1)
MoCovI (d-2)
McCoVi (dl-3)
OS-VI
...0 VI
Pure MBRL
Low Model Error
Medium Model Error
High Model Error
-50
-75
-100
0k
50k
100k
150k
Ok
50k
100k
150k
Ok
50k
100k
150k
Environment Samples (t)
McCoDyna (d-1)
McCoDyna (d-2)
MoCoDyna (d-3)
OS-Dyne
QLearning
Dyne
Comparison of (top) MoCoVI with VI, pure MBRL and OS-VI, and (bottom) MoCoDyna with eLaamning Dyna, and OS-Dyna. (Left) low (A = 0.1), (Middle) medium (A = 0.5), and (Right) high = model errors. Each curve is average of 20 runs. Shaded areas show the standard error.
Figure 1:
to P by smoothing the true dynamics P as suggested by Rakhsha al. (2022): for À E [0, 1], the smoothed dynamics p(A) is (- a) _ (1 (1-b) A) P(-|z, a) + - ([a' a) > 0}). where U(S) the uniform distribution over set S. The parameter controls the model error, from no error with À = 0 to large error with X 1 (uniform transition probability over possible next-states).
Fig. 1 first compares MoCoVI with OS-V VI (Rakhsha al., 2022), VI, and the value function obtained based on the model. We set p = p(A) for À = 0.1, 0.5 and 1. The plot shows normalized error of Va against V*, that is, V V |I /|| MoCoVI can converge to the true value function in few iterations even with extreme model errors. The robustness, as expected, improved with larger values of d. In comparison, OS-V VI and VI show much slower rate than MoCoVI and the value function obtained from P suffers from the model error. Fig. 1 then shows the results in the RL setting. We compare MoCoDyna with OS- OS- Dyna (Rakhsha et al., 2022), QLearning, and Dyna. At each step, the algorithms are given sample (X,, Ar, R2, X;) where X,, A, are chosen uniformly in random. We use P = (A)) MLE where PMLE is the MLE estimate of dynamics at the moment. For OS-Dyna and QLearning which have learning rate, for some a, N > we use the constant learning a for t S N and a/(t N) for > N to allow both fast initial convergence and stability. The results show a similar pattern as for MoCoVI. MoCoDyna can successfully solve the task with any model error. In fact, MoCoDyna significantly outperforms other algorithms. In comparison, QLearning and OS-Dyna show slower rate convergence, and Dyna cannot solve the task due model error.
CONCLUSION
In this work, we set bridge model-based and model-free approaches in RL by devising a cost- efficient approach to alleviate model errors. We develop the MaxEnt model correction framework, which adopts MaxEnt density estimation to reduce model errors given small number of queries to the true dynamics. A thorough theoretical analysis indicates that our framework can significantly accelerate the convergence rate policy evaluation and control algorithms, and ensure convergence to the true value functions despite model errors if said emror are sufficiently small. We also develop a sample-base variant, MoCoDyna, which extends the Dyna framework. Lastly, we confirm the practical relevance of our theoretical findings by benchmarking MoCo-basse planning algorithms against their naive counterparts, and showing superior performance both in terms of convergence rate and expected returns. Future work should investigate deep RI applications of the MoCo framework.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We would like thank the members of the Adaptive Agents Lab, especially Claas Voelcker, who provided feedback on draft of this paper. AMF acknowledges the funding from the Canada CIFAR AI Chairs program, as well as the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) through the Discovery Grant program
MK acknowledges the support of NSERC via the Canada Graduate Scholarship Doctoral program (CGSD33-68898-2000) Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.
REFERENCES
Romina Abachi, Mohammad Ghavamzadeh, and Amir- moir-mmssouu Farahmand. Policy-aware model learning for policy gradient methods. arXiv:2003.000 0003002 2020. 7
Romina Abachi, Claas A Voelcker, Animesh Garg, and Amir massoud Farahmand. VIPer: Iter- ative value-aware model learning the value improvement path. In Decision Awareness in Reinforcement Learning Workshop at ICML 2022, 2022. 2,7
Zaheer Abbas, Samuel Sokota, Erin Talvitie, and Martha White. Selective dyna-style planning under limited model capacity. Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 1-10. PMLR, 2020. 1,
Yasemin Altun and Alex Smola. Unifying divergence minimization and statistical inference via convex duality. In Proceedings of the 19th Annual Conference on Learning Theory (COLT), pages 139-153. Springer Berlin Heidelberg, 2006. 3, 17
Bernardo Ávila Pires and Csaba Szepesvári. Policy error bounds for model-based reinforcement learning with factored linear models. In 29th Annual Conference on Learning Theory (COLT), volume 49 of Proceedings of Machine Learning Research, pages 121-151. PMLR, 2016. 2
D. Bertsekas. Convex Optimization Theory. Athena Scientific optimization and computation series. Athena Scientific, 2009. ISBN 978 1881836529311
D. Bertsekas and J.N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996. ISBN
9781886529106. 13
Jonathan M Borwein and Adrian S Lewis. Duality relationships for entropy-like minimization problems. SIAM Journal on Control and Optimization, 29(2):325-338, 1991. 17
Zdravko I Botev and Dirk Kroese. The generalized cross entropy method, with applications to probability density estimation. Methodology and Computing in Applied Probability, 13:1-27, 2. 3
S. Brooks, A. Gelman, G. Jones, and X.I.. Meng. Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC Handbooks of Modern Statistical Methods, CRC Press, 2011. ISBN 978 9781420079425. 3
S.F. Chen and R. Rosenfeld. A survey of smoothing techniques for me models. IEEE Transactions on Speech and Audio Processing, 8(1 (133775,,, 2000a. doi: 10.1 (0.1109/898874555 5
Stanley F Chen and Ronald Rosenfeld. A survey of smoothing techniques for me models. IEEE Transactions on Speech and Audio Processing, 8(1):37-50, 2000b.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition ( (Wiley Series in Telecommunications and Signal Processing). Iiley-Intersciencee 2006. ISBN 047 1241954. 21
Will Dabney, André Barreto, Mark Rowland, Robert Dadashi, John Quan, Mare G Bellemare, and David Silver. The aalue-ipprovement path: Towards better representations for reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7160-7168, 2021.
10

---

Published as a conference paper at ICLR 2024
John N Darroch and Douglas Ratcliff. Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, pages 1470-1488 1972. 3
Andrée Decarreau, Danielle Hilhorst, Claude Lemaréchal, and Jorge Navaza. Dual methods in entropy maximization. application to some problems in crystallography. SIAM Journal on Optimization, (2):173-199) 1992. 16, 17
S. Della Pietra, Della Pietra, and Lafferty. Inducing features of random fields. IEEE Transactions Putfern Analysis and Machine Intelligence, 19(4)3300-393, 1997.
Miroslav Dudík, Steven J. Phillips, and Robert E. Schapire. Performance guarantees for regularized maximum entropy density estimation. In Proceedings of the 17th Annual Conference on Com- putational Learning Theory (COLT), volume 3120 Lecture Notes in Computer Science, pages 472-486. Springer Berlin Heidelberg. 2004. 3,5
Miroslav Dudik, Steven J. Phillips, and Robert E. Schapire. Maximum entropy density estimation with generalized regularization and application to species distribution modeling. Journal of Machine Learning Research, 8(44): 2007. 1, 3, 4, 5, 20
Amir-massout Farahmand. Iterative value-aware model learning. Advances in Neural Information Processing Systems (NeurIPS), volume 31. Curran Associates, Inc., 2018. 7,7
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems (NeurIPS), volume 23, Curran Associates, Inc., 2010. 6, 27
Amir-Massoud Farahmand, Andre Barreto, and Daniel Nikovski. Value- Aware Loss Function for Model-based Reinforcement Learning. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 54 of Proceedings of Machine Learning Research, pages 1486-1494 1494. PMLR, 2017. 2,7
Joshua Goodman. Exponential priors for maximum entropy models. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computa- tional Linguistics; HLLTNAACL 2004, pages 305-312, Association for Computational Linguistics, 2004.
Taher Jafferjee, Ehsan Imani, Erin Talvitie, Martha White, and Micheal Bowling, Hallucinating value: pitfall dyna-style planning with imperfect environment models. arXiv preprint arXiv:2006. 04363, 2020. 2,2
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. In Advances in Neural Information Processing Systems (NeurIPS), volume 32. Curran Associates, Inc., 2019.
E. T. Jaynes. Information theory and statistical mechanics. Phys. Rev, 106:620-630) 1957.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the 19th International Conference on Machine Learning (ICML), pages 267-274. Morgan Kaufmann Publishers Inc., 2002. 26
J. N. Kapur and H. K. Kesavan. Entropy Optimization Principles and Their Applications, pages 3-20. Springer Netherlands, 1992. ISBN 118-94-011-2230-44 3
Jun'ichi Kazama and Jun't ichi Tsujii Evaluation and extension of maximum entropy models with inequality constraints. In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing, pages 137-144, 2003. 5
Solomon Kullback. Information Theory and Statistics. Wiley publication in mathematical statistics. Wiley, 1959. 3
Raymond Lau. Adaptive statistical language modeling. PhD thesis, Massachusetts Institute of Technology, 1994.
11

---

Published as a conference paper at ICLR 2024
Guy Lebanon and John Lafferty. Boosting and maximum likelihood for exponential models. In Advances in Neural Information Processing Systems (NeurIPS), volume 14. MIT Press, 2001. 5
Ângelo G. Lovatto, Thiago P. Bueno, Denis D. Mauá, and Leliane N. de Barros. Decision-aware model learning for actor-critic methods: When theory does not meet practice. In Proceedings on "I Can't Believe It's Not Better!" at NeurIPS Workshops, volume 137 of Proceedings of Machine Learning Research, pages 76-86. PMLR, 2020. 7
Robert Malouf. A comparison of algorithms for maximum entropy parameter estimation. In COLING- 02: The 6th Conference on Natural Language Learning 2002 (CoNLL-2002), 2002. 3
Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the 20th International Conference Machine Learning (ICML), page 560-567. AAAI Press, 2003. 6, 27
Rémi Munos. Performance bounds in Lp norm for approximate value iteration. SIAM Journal Control and Optimization, 46(2): 2007. 6, 27
Amin Rakhsha, Andrew Wang, Mohammad Ghavamzadeh, and Amir-massoud Farahmand. Operator splitting value iteration. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 38373-38385. Curran Associates, Inc., 2022. 2, 8, 9, 15, 33, 34
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and application to the game tetris. Journal of Machine Learning Research (JMLR), 16(49):1629-1676 2015. 6, 27
J. Shore and R. Johnson. Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy. IEEE Transactions on Information Theory, 26(1):26-377 1980.
Richard S. Sutton. Integrated architectures for learning, planning, and reacting based on approxi- mating dynamic programming. In Proceedings of the 7th International Conference on Machine Learning (ICML), pages 216-224. Morgan Kaufmann, 1990. 2
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2019. 13
Csaba Szepesvári.
Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010. 2, 13
Erin J. Talvitie. Self-correcting models for model-based reinforcement learning. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 2597-2603. AAAI Press, 2017. 1.2
Claas A. Voelcker, Victor Liao, Animesh Garg, and Amir-massoud Farahmand. Value gradient weighted model- reinforcement learning. In International Conference on Learning Represen- tations (ICLR), 2022. 2.7
Tong Zhang. Class-size independent generalization analsysis of some discriminative multi-category classification. In Advances in Neural Information Processing Systems (NIPS), volume 17. MIT Press, 2004. 5
12

---

Published as a conference paper at ICLR 2024
A
LIST OF APPENDICES
Appendix provides extended background on MDPs.
Appendix contains the proofs for Section 2.1.
Appendix D provides technical details of Maximum Entropy Density Estimation. Appendix E contains the proofs for Section 3.1.
Appendix F contains the proofs for Section 3.2.
Appendix G provides the analysis of MaxEnt MoCo in lp norms
Appendix H contains the proofs for lp analysis of MaxEnt MoCo.
Appendix I contains the proofs for Section 4.
Appendix J shows additional empirical results.
B BACKGROUND ON MARKOV DECISION PROCESSES
In this work, we consider a discounted Markov Decision Process (MDP) defined as M = (X, A, R, P, (Bertsekas and Tsitsiklis, 1996; Szepesvári, 2010; Sutton and Barto, 2019). Here, X' is the state space, A is the action space, R: X x A - .MR)) is the reward kemel, P: X A - M(X) is the transition kernel, and S 7 1 is the discount factor.' We de- fine r: X x A + IR to be the expected reward and assumee it is known to the agent. A policy mapping from states distributions over actions. We denote the expected rewards and transitions of a policy by r*: X + IR and p X + M(X), respectively. For any function Φ: IR, we define PT: X A R as
T: X M(A)
(P)) A P(dx'lr,a)dla
(Vx, a)-
The value function V (*(R, P) of policy is defined as
(T(x) A E
7 Xo Xo = x
where actions are taken according to æ, and X, and R₂ are the state and reward at step t. The value function of satisfies the Bellman equation: For all X, we have
v ("(x)= (x) rx)) + / (dr'
(B.1)
or in short, V nT + VPV The optimal value function V V*(R,) P) is defined such that V*(x)= = max, (x) for all states æ E X. Similarly, V* satisfies the Bellman optimality equation:
max (r(o,a) a) + +> ((dele,,a) aeA
V*(x)
(B.2)
We denote an optimal policy by T = x² (P, for which we have V = V= We refer to the problem of finding T for specific policy Tre the Policy Evaluation (PE) problem, and to the problem of finding an optimal policy as the Control problem.
The greedy policy state E X' is
r(2,0)+ +7 P(dy)a,
T V)
argmax a
(B.3)
In this paper, we assume an approximate model P. P given. We define Ve and #* in the approximate MDP M = (X, R, P,7) similar to their counterparts in the true MDP M.
For domain S, we denote the space of all distributions over S by M(S).
13

---

Published as a conference paper at ICLR 2024
C PROOFS FOR SECTION 2.1
In this section, we provide the proof of Lemma 1. Before that, we first show two useful lemmas. Lemma 2. For two transition dynamics P1, P2 and any policy π have
- S v2 rddala) ( P2(-1x,a)
Proof. We have
[-][(1>)) - -P J, (PT(dy))) - (dylac) -
f.V. T(da, x)) (
P2(dy/z,a))
T(da, ())ddlz)) (:)[ddy),a)-PP((dll.. Pa(dyla,a)
(dda,)) / PP P2(dyla,a)
Tda, x)|(P((111,.)) P2(-12r,
(C.I)
T(da, x) x) (P (2(((x,a)
where we used the Pinsker's inequality.
Lemma 3. For two transition dynamics P1, P2 and any policy Define
GPI.2 - (I - ) (TP - P
We have
7 sup / DKL Pi a) (2)
Gpp
7-7 x.a
Proof. When clear from context, we write G instead of P2 We have
||G 1l00 S | - xP2)
30 |PT - P3 loc
1 1- supli (z) - P/ (+)=)]
where we used || -)- 1/(1 |1AAll olco for ||A|| < and the fact that |P] ao 1. Due
to Lemma 2 we have for any x
[PPT(-1)) (- S v2 / T(da ()) DKr. (1),, P2(-(x,))
< sup / 2Dxi () P2({).,))
3.0
substituting this in the bound for ||G 1l gives the result.
We now give the proof of Lemma
Proof of Lemma for PE
Proof. Since -. (I >pm))11 and nT (I XP") we have
V :. (I (I >p= (I (I-
= (I - >P') -1(1 - >D - 11-P">VV
(I {pT) -1 -p=jV"
G G V
(C.2)
14

---

Published as a conference paper at ICLR 2024
Thus,
1 9 [I - ypm) (p= - -a
(pT - -P-
7
(PT - -p=) |
7
M || V
where we followed the proof of Lemma 3 for the last inequality.
Proof of Lemma for Control
Proof. Define To = r (yP yPV similar to Rakhsha et al. (2022, Lemma 3)
v (ro, (ro.P) (r,
Assume f f g mean f(x) 2 g(z) for any x. We can write
0 x V= (r, P) y* (r,P)
/x (ro, P) y Pr;
V= (ro, P) - V" (r,(r, (r, + V- (r, - V$ (r,P)
V (ro, P) - y" (r,P) V* (r
-V* (r,P)-v**(1 (r,
(I 7PT ) ''6 - -r²) + V* (r, - -V* Pr;
(I pp" ( 7p" V + +V* (r, V* (r. P)
G P,
V 1V (r, y (r,P)
p V -G / (r,
G p.p
V' -G - V' + +G (V* - V (r. P))
G p V* G V* + (V v* (r,
where we used (C.2). Comparing the first line with the least, we obtain
|| y**
c p v
+ + p v + (1-
(C.3)
20, || |l + +c I|eModallla0 12 V=*
where we used Lemma 3. Rearranging the terms give the result.
D TECHNICAL DETAILS OF MAXIMUM ENTROPY DENSITY ESTIMATION
In this section we present the technical details of maximum entropy density estimation. This involves the duality methods for solving the optimization algorithms and some useful lemmas regarding their solutions. These problems are well studied in the literature. We do not make any assumptions on whether the environment states space, which will be the domain of the distributions in this section, is finite continuous, and make arguments for general measures. Due to this, our assumptions as well as our constraints may differ from the original papers in the literature. those cases, we prove the results ourselves.
15

---

Published as a conference paper at ICLR 2024
D.1 MAXIMUM ENTROPY DENSITY ESTIMATION WITH EQUALITY CONSTRAINTS
Assume Z is a random variable over domain Z with an unknown distribution E M2)). For set of functions (1,..., Pd: 2 R the expected values
(x))p((((Z) are given. We will c: 2 IRd and E IR refer to the respective vector forms. We also have access to approximate distribution P E M( such that & 2 p. The maximum entropy density estimation gives new approximation q" that is the solution of the following optimization problem
min gEM(2)
DKL P):
(D.1)
s.t. Ez 1o. (Z) -. (Lsisd).
The KL-divergence in (D.1) is finite only q is absolutely continuous w.r.t. p. In that case, g can be specified with its density w.r.t defined as f _ dg
Z + IR where dg the Radon-Nikodyn ap derivative. Let (1, p) be the L1 space over Z with measure p. We have f E (2,
dp
Also for any f Li such that z 0 and f {(=)((dz) 1 can recover distribution q E _M(2) as
g(A) / f(z))(dz).
(D.2)
Consequently, (D.1) can be written in terms of f. We have
DKL q (1 = f ((dz) log g(dz)
p(dz)
g(dz)
log g(dz)
p(dz) f(dz)
=
p(dz)
/ [() log ((z) p(dz)
We can write (D.1) as
/ f(z) f()) p(d2),
min
(D.3)
s.t. / [(=))((=)) p(dz) = (ISisd),
/ f(() p(dz)= 11
E (2,
The constraint 2 0 is implicit in the domain of the KL objective. The Lagrangian with dual parameters X, A' is
L(F.AA') 1 f(x) f(z) - Σ x=((=)0;(z) + A'f(z) p(dz) + ExO: -A. (D.4)
i=1
Then, obtain the dual objective Dz(A, A inf, L(f, A') from this result by Decarreau et al. (1992, Proposition 2.4). Lemma 4 (Decarreau et al., 1992)). For any fixed E RR. A E R, the Lagrangian L in (D.4) has unique minimizer fx.N defined as
d ~vo((=)) -N1-1)))
JAN - exp
The dual objective is given by
D²(A. = - exp
d x1)0(2)- - + E - N.
It is concave, continuously differentiable, and its partial derivatives are (D,(A,A)
(D,(A.N) Φ. -f(nav(2000()))((e)))
1 / (z)(()))(dz).
0h;
0N
16

---

Published as a conference paper at ICLR 2024
Thus, for the dual objective (A),,A) have Dz(A, = A,A,,,,,,) We arrive at the following dual problem
[-/ cxp
-6-0)--11111 +
A
max Aa(
(D.5)
MER
i=1
The following result by Borwein and Lewis (1991, Corollary 2.6 and Theorem 4.8) shows the duality of the problems.
Theorem 3 (Borwwei and Lewis, 1991)), Assume 6E E L (2, fori=1..... Under certain constraint qualification constraints, the value of (D.3) and (D.5) is equal with dual attainment. Furthermore, let X" A be dual optimal. The primal optimal solution is fx"
We do not discuss the technical details of the constraint qualification constraints and refer the readers to (Altun and Smola, 2006; Borwein and Lewis, 1991; Decarreau et al., 1992) for a complete discussion.
For any À E Rd, the optimal value of can be computed. Due to Lemma 4, we have a (A, 0D @Da. (2)
/ (x)x())
(D.6)
Ox'
0A'
solving for the optimal A gives the following value
exp xx0oi())-1) - p(dz) (()())))))(())))---))))))))))))) - 11
M
(D.7)
1=1
where A₃ is defined Section 2.2. Note that since functions Φ; are bounded this quantity finite. Thus, we can just optimize (2 A3)) over A. By substitution we get
(2(A) & (2(A,A)) - Σ Aoo -log
exp Σ ExSO(E)) p(dz).
(D.8)
We observe that Max D3 (A) is equivalent to (2.4). From Theorem 3, if X optimizes Dz. we know that fx. optimizes (D.3). Due to equivalence of (D.3) and (D.1), then gx- defined as
Ax ax (A) J JN-A,. (z))(dz) / p(dz) exp Σ Mp)(2) -Ax-
(D.9)
SSeA"
for all A C 2 optimizes (D.1).
D.2 MAXIMUM ENTROPY DENSITY ESTIMATION WITH & REGULARIZATION
We now study relaxed form of the maximum entropy density estimation. In this form, instead of imposing strict equality constraints, the mismatch between the expected value
(Z) with 5, is added to the loss. The benefit of this version is that even if é; values are not exactly equal to Ez~plós (Z)]. the problem remains feasible. Moreover,
adjust the weight of this term in the loss based on the accuracy of o; values. Specifically, we define the following problem.
1 d
DKL 9 11)) GEM(Z)
min
EzzgI (2)) - (.))
(D.10)
B2
Similar to the previous section, we can write the above problem in terms of the density dg and write (Decarreau al., 1992)
dp
d
/ f(e) f()) p(dz) +
1
min fi
(D.11)
82 i=1
/ [(=)0(())) M(dz) - 5. =
s.t.
(1
{ ((:) p(dz)= =1,
f (E EERR
17

---

Published as a conference paper at ICLR 2024
The Lagrangian of this problems be written
Ls(S,,, - -(SA,)
Σ
c Σ
ArE
(D.12)
The dual objective is then
D Da. = inf L 1.
It can be observed that f and & can be independently optimized for any fixed X, A. Due to Lemma 4, the optimal value of f is fx,V. The optimal value of & can be calculated
εx - 8A
(D.13)
We arrive the following dual objective
d
D A)) = L(FAA,
82
X
ExT
+
A
(D.14)
4
32 1=1
1=
i
1
1
A,( + 8
X
3
X
4
2
i=1
d
-2(AAA)
32
X2
which means we have the dual problem
D2(A, 1 32 Σ
max ERER
(D2)
We show the duality of the problems. Notice how this problem has extra 1 3 Σ -i=1 X?
compared to (2.4). This is the reason this problem is considered the regularized version of (2.4). Notice that the regularization term also makes the dual loss strongly concave. This makes solving the optimization problem easier.
Theorem 4. Assume di is bounded for = 1 1...., T. and B > O. The value of (D.11) and (D2) is equal with dual attainment. Furthermore, let X* N be dual optimal. The primal optimal solution fx..
Proof. First, we show that the some solution A A exists for the dual problem. To see this, first note that for any Rd, the optimal value of A' is A₂ defined in (D.6). Now need show D,,a(A, is maximized by some X². We have
d Σ x2
D2 = D - g2
(D.15)
Since D is concave, D& (A, and therefore D (A, AÇ) is also concave. Due Weierstrass' Theorem (Bertsekas, 2009, Proposition 3.2.1) it suffices to show the set
(A,
$ = (=EER Da,aA,, AN) 2 Da (0. A6) }
18

---

Published as a conference paper at ICLR 2024
is non-empty and bounded. It is trivially non-empty. Assume (Ø(z) S Omax for any and 1 S < d. For any À E S, we have
P3.a(0 A6) -
d 32
- (D)
X2
i=1
- exp
(2)
A33 - p(d=) Σ
X -A3-
1=1
i=1
=-1 + Σ A - -log| / exp Σ (x)x(()) - (((2)) -1)p(d))) 82
क 1.00 - -log / exp
dll Amax - -1) ())p(()) - 1 11
S /| 0z
s 1I + =1 + dl|il Omax + 1.
M
which enforces upper bound | This means that some optimal solution X A₁ exists.
Now we show that Ax, is primal optimal with Ex-. First, note that the derivative (D.6) zero for X", A². due to the derivation of 2/. Thus, fx-,A.. is feasible. Similarly using Lemma 4 we have from (D.15)
aD 3. (x,,,
0 =
O2,
DD ODA(A',A's 8ax;
ad:
の. - FAAAAA (2)( Ex
which shows Ex- is feasible.
Consider another feasible f. E for (D.11).
/ f()) log f(d)) + 8² im
Σ Ls(f,E,xtA..))
Daa(A A2-)
Ls
= -/ (x)A)-())0nn fx, fAr (2) p(dz) - g2
d
Σ Ex-
im
which proves the claim.
Similar to the exact formulation, we can substitute A' with AG, to obtain a loss function based on A. We arrive the loss function
d
(A) 2 Dr.a(A, = D2(A,
- 32
4
1=1
D2(A) 32
X²
Σ 21ē log / exp
)(de)) Erdi((e) p(dz)
d
32 Σ x (D.16)
If X* optimizes Dg.a. Theorem 4 shows fx Ass, optimizes (D.11). Due to equivalence of (D.11) with (D.10), we get that yx- optimizes (D.10).
19

---

Published as a conference paper at ICLR 2024
D.3 LEMMAS REGARDING MAXIMUM ENTROPY DENSITY ESTIMATION
Lemma 5 (Dudík et al. (2007)). For の0 .0(0) E Rd let , (22 be the maximizers of D 9,2(0 and
D 9, respectively. We have
[100 -
- 1
Φ
(1)
-2
Proof. Define
d exp Σ (cdi(z)) p(dz).
9(1) 2 log
)((e))
Since g(A) -Ei= ) D
an / (A) and D
Dzaa) /) (A) is concave, know that g is convex. Due to
optimality of (2)), (22) we have
VD 8, (, (A(1)) -Vg(A()) + T 8²2(10) = 0,
2
VD 8 ()(2)) ( + 82
By taking the difference we get
8A -12))
(6 -1
Multiplying both sides by (1(2) - (12)) get
2 82 - - -Vo(((()) - Vo(A(3)), 10)) - -1(2)) 16 (1 T (2) 2 1()) - -1
Due to the convexity of g, have
-v((22)) 200) - -1(2)) 20.
Thus, we continue
1 32 11)
-((V((1()) Vo(A(2)), 1 2(2)) + 11)0))0) -000) (2)) ((2))
-
2
() -00) 11-- (22)
<1000h (1) / 1/.1 2// (2)
where we used the Cauchy-Schwarz inequality. Dividing by ||A(1) A22) proves the result.
Lemma (Dudik et al. (2007)). Let X maximize DR. defined in (D.16). Then for any X, we have
2 DKL p gx ) < DxL p ax + g² B2
2112-
332 |
Proof. Define x² A (Eznl(((2)) First, we show that for any A E Rdd, we have
/ p(dz) log p(dz) (x(22)
DKL p 11
/ p(dz) log
p(dz)
p(dz) Σ >xob((2) - AA)
/ p(dz) log p(dz)
p(dz) / p(dz)) Σ (1de((2) +
DRL( (1)) (), Φ-)) + +Ax
(D.17)
20

---

Published as a conference paper at ICLR 2024
Now can write from (D.16) and (D.17) that
(a. (), Φ) - AA 1 3
1
- DKL [1) D p 11 P) + (4."") 2¹) -A,
4 11121
= =DR((p [b) DxL qx + (A, ~¹) 11111
(D.18)
Define
A _ argmax D3 D3 (20)-
Ao
Due to optimality of X*, we have D3. (A**)= S (B. Expanding both sides with (D.18), we get from the Cauchy-Schward and Lemma
| p (1 + (A Φ 3²) 4 -
-
1
DRI( ll ex- )
DKL p l1 1) - DKL(p (pl -2-- ) + 11a , Φ-) 1
1 11-""188811111 1111111
= =DR((P ll ax.. ) (A* - X", "- Φ¹) 1 8² (11^ - -11>"112)
211 + 1 3911-*
DKL(P |I 9x- ) + | - -220=
S (p ll yx- ) + 32 / क5 11/
2
+
1 1 3 1 l/-
4
On the other hand, due to optimality of A we have Dr.5 (A) S D 3.5 (A**). Expanding both sides with (D.18), we get
1 81112 2 Del (p ax- ) + 32 || 12.
1
DEa 11 2x )+
Combining the last two inequalities, we get
D ax- ) S DK.(p 22 ) 4 11 + 1 "" 11
which proves the claim.
E PROOFS FOR SECTION 3.1
We first show the following lemma:
Lemma 7, For any policy n, we have G 00
S <c]l|eModetll
Proof.
Since the feasibility set of Problem (PI) is convex, and P(-1ar, a) belongs to it, we have from Pythagoras theorem for KL-divergence (see Thm. 11.6.1 of Cover and Thomas 2006) that
DRL a() II ((12, ) > ( P(+ a) P(- a) + DRL ((()x, a) ((-1z,))) > D P(-x, a) P(-Ix,a) ).
From Lemma we have
< ci sup v DKI. P(1lar,) || P()x,
a.a
ci sup a,a
V DKL( a() P(|2, a))
< C1 [MModellac
21

---

Published as a conference paper at ICLR 2024
Proof of Proposition 1
Proof. Due the constraint Problem (PI), for any we have (P - P)Φ: = and therefore
G
p = 0. Thus, using the proof of Lemma I, for any Rd
Vam
Tee p,
V A9B
mm
Σ
wids)
p,p
T P,P
V Σ
WiP;
= c1 cilleModell
Van Σ
W
Similarly for control, from (C.3), we have for any w R2d
VT
V=¹
<
G
p.p
V
+
+
+ G Gp - -
c p
(V* - -E widhi
+ 0 (V Σ midhil
+
- -V=
v/ 3
|| 1" Σ w + callessdael
| || - l
$ 201 Modell
where we used Lemma the last inequality. Rearranging the terms yields the result.
F PROOFS FOR SECTION 3.2
In this section, provide the analysis of MaxEnt MoCo in supremum norm. We will show sequence of lemmas before providing the result for general | and then proof of Theorem 1. Lemma 8. P is the solution of the optimization problem (P2).for any we have
DKL ((-22, a) ((-(x,a)) s DKL ((())x,)) || P() a)) + za Querry (x, Querry(x a)2.
Proof. For À E Rd, define
d Σ (,ri(1) - - -A)
(A) A / P(dylæ, a) exp
where A2 is the log-normalizer and A C X. Due Lemma 6, for any À we have
DEL a)))x,a) (())a,a)) S DKL, (P((,,)))))) a) (x((2,))
z Σ (P)))) (x(x))))
g2
|||
4
Since 9n PP(122, a), substituting = gives the result.
22

---

Published as a conference paper at ICLR 2024
Lemma 9. If is the solution of the optimization problem (P2). for any x, we have
P(|t,, a) - P(-k,, a1)l, 3 V2eModel a) + 3 &Query (I, a).
Proof. Using Lemma and Pinsker's inequality, and the fact that va a va + vb, we write
||P()a, a) ((,a,, a))l - 2Dxx ((+)2, (P P()))a))
4 (P)(((()) P(+(x,
+ 32 "Quary 0)2 S 22eModel2 a) 3 EQuery (z, a).
2 2Dxx ((()2,,))
Lemma 10. For any æ, a we have
- (Poi) V2(2rquery(aa (I, + (2, a))
also for any policy
- Σ (P" -P')))(a)((P") (p))))()) s svā π (dal)) (2e
(2da)))(2equor) (2, 0) + (e))
Proof. For more compact presentation of the proof, let p P(-Iz,a), P P(-(ar, a), and P(-|z, a). Let Φ: X + Rd and wh: X x A + R be d-dimensional vectors formed by ov, vh. For q E M(X) and f: X' + RRd we write
aff A [f(x]]
We write
|1 p[0)]| 5 vd]ppdd -
s Vd [p| (1 2)ll + (1, a) pl6ll1))
$ vd Quuery (z. a) (zb( a) pl0)112).
(F.1)
Now note that p is the solution of (P2), the value of objective is smaller for than it is for p. We obtain
DKL (
||[ (x a)l s DKL p)+ +
g2
ga
1
Moddl (I, a)²
QQuery a
z2
Thus.
[(( (b<x, S / PeModal a)2 + eQuory a)3 DKD ( V )
< 3ReMudal (z, a)2 + EQuary (2, a)
< BEModal (I, a) + (xQuery(I a).
Substituting in (F.1) we get
|
- V - -p(ell
S Val (Ip(b) (b a)ll2 + (1, p(0)))
s /dl 2eQuery (z, a) + (2).
23

---

Published as a conference paper at ICLR 2024
For the second part we simply write
Σ (Pa oz) (P 2x)))
= Σ T (Po.)..)) (P)
iml
/ ((dal)) (P))
(Po,((1)) - (P
$
(ddaxx) 2cQuery( + SeM)del(z,0))
where we used the first part for the second inequality.
Lemma 11. Pf is the solution of the optimization problem (P2), for any policy n, w E Rd and
v: X + E, we have
7 - ( Veooellel + 2 I 1 - Σ wi
$ 1-7
vd ( (Bleelell + 22leeQuery ml 1100100
1
Proof. We have
G p
= [I - 1/=))=t((7 ->P")o/l
(F.2)
S
[I - 1->pp)-1a (rpp" -pp")(E- Σ widi)
+
(F.3)
00
(xpT (I ) 1 -pp") Σ wiot)
(F.4)
Using (C.1) in proof of Lemma 2 and Lemma 9 we have
< /
Pm (+1z) PDT (-xx)]
< / (dda)z) (2eMode((IA + 3 eeQurry (2, (z,
2
2
S 2 / + 3 IIcuuerylloo
Thus, for the first term (F.3), we can write
I p1pp)-((pp>
(xp" - 7p-)(1
Σ mxddi)
7 supl| (T(()))) p -p-((<>>)1
Σ wich
1 -
1
5 7 1- \V
+ 9
2
| [oa]
1 Σ w
24

---

Published as a conference paper at ICLR 2024
Now, for the second term (F.4), can write
[I (I-PP=)
1
->p" ( widi)
2
7 1 1-9
(P" :D)) Σ wibss
7 sup
Σ wi w;((P=*.)(x) - (.)))
1 - 7
7 sup 1
(PD (x) - (P* ()))))
7
2||cQueryll 3llcModell lxx ||
1 7
Putting the bounds for (F.4) and (F.3) finishes the proof.
Theorem 5. Define the mixed error values
2 e1 1-7 :
(V (V2l(Moddelloo + ((Qqueryllo))) 62
vd.
(alleModellloo + 2) 2/1equerylloe)
1-7
Then, for any Wmax 2 0. we have
| - pamll 11 S1
inf || Swhma
| Σ
wi Oi
+ C2 Wmaxs
1c
d
1" 1-= v=
1
2e1
[
inf SWaanx
r- Σ
wi Φ
00
+ 1- El
20z
-Wmax-
Proof. The PE result is direct consequence of Lemma 11 and (C.2). We have
|
1000
Tre p.
V
TpE
< inf WERd
El
ym
Σ
Wi Φb 0
+ 62 ||
i=1
|| |
S E1
inf
Wi Φb
+ Wmax-
||
1=1
For control, from (C.3) we have
| V*
s $| p.r Vol|
+ +1
Va
+
-V>)
p,P
2
Choosing w 0 in Lemma 11 we get
- /*4) /1| Se pz p* _
Also for any we get
d
GT. p.
Vo
Se V' ,
Σ
Wi di
+ -|wlloo
i=1
d
Se
V
Σ
W/ 01
+ 02 ||w1l
10
i=1
20
25

---

Published as a conference paper at ICLR 2024
Thus,
V" V
S 2e,
V Σ
W; 0:
+ 2e2
|10|
te
V
v
im
By rearranging, we get
1" - V.
S inl wERd
201
V
Σ
10 Φ1
202
||
1 - 61
61
d
S 201
202
inf
W/
+ - c1
-Wmax-
61 ||w||
Wmax
1=1
Proof of Theorem 1 It is the direct consequence of Theorem 5 with choosing 8 ||EQueryll ol MMddel and observing
1(2 + V e1
||eModetlloo S 3c, Mooo
1-7 3vd. 2
62 1-7
||cQuery Il calleQuerylloe
G Ep ANALYSIS OF MAXENT MoCo
The analysis in the Section 3.2 is based on the supremum norm, which can be overly conservative. First, the error the model and queries are due to the error in a supervised learning problem. Supervised learning algorithms usually provide guarantees in a weighted lp norm rather than the supremum norm. Second, in the given results, the true value function VTT and V should be approximated with the span of functions o; according the supremum norm. This is strong condition. Usually, there are states in the MDP that are irrelevant to the problem or even unreachable. Finding a good approximation of the value function in such states is not realistic.
Hence, in this section we give performance analysis of our method in terms weighted Ep norm. We first define some necessary quantities before providing the results. For any function f X IR and distribution E M(X)), the norm |l.lllp.p is defined as
11 & (ISC))OOaa) 1/P
Let æ an arbitrary policy, and P be the m-step transition kernel under x. The discounted future-state distribution 17"' X M(xx) is defined as
1
(-1x)
A
PT (-1z).
m=0
Define (-12)) A " (dz(=))) This is the distribution our state when making one transition
according to pM from an initial state sampled from the discounted future-state distribution 17 (2|z). - Model X' + and Query' X' + IR be defined based on eXodel and éQuery similar the way Also let
r defined based on r. Assume for any and æ, a we have A B/2 < (1) a) < A + B/2 for some values A and B 2 0.
Let p E M(X) be some distribution over states. We define two concentration coefficients for Similar coefficients have appeared in e, emro propagation results in the literature (Kakade and
26

---

Published as a conference paper at ICLR 2024
Langford, 2002; Munos, 2003; 2007; Farahmand et al., 2010; Scherrer et al., 2015).
Define
B CT ( =xp
/ p(x)
dnj (-|x)
2
dw " (+x)
B2
dp
dp
C (0) 1. mloo)
dn" (-12)
dp
Here, dyy(-lar) dp and (:laa dp are the Radon-Nikodyne derivatives of 1y" (-|2) and 17" (-(x) with respect to p. In the CT (p) defined above, the exponential term forces us to only focus large values of 3, which is not ideal. This term is appears as upper bound for similar to more recent studies on approximate value iteration, it is possible to introduce coefficients that depend on the ratio of the expected values with respect the distribution instead of their densities, Due to the more involved nature of those definitions, we only include this simple form of results here and provide further discussion the supplementary material. The next theorem shows the performance guarantees of our method in terms of weighted e, norms.
However,
Theorem 6. Define
27
2 B |
(CT(P) + CD() v
V2. lle Modelll +
1
2nVd
C 1 y
C2(p) [llc + +2| =21cquueryl1.pp)
Then
V TM
5
2e Tre
inf
v Σ
d
+
2e
Tew
1 - 1-2e
1
2e
4,0
also i m Ge./ [0T7(11- 2e7)) and es m
.5 6e (1
2e we have
Iv- va
11
2ej
2e
A.p
I-
inf || Swaa
v"
Wi
02
ef
Wmaxx
4.p
Notice that the 33 appears in the bound the same manner as Theorem 5. This will lead to the same dynamics on the choice of B. We provide the proof of this theorem in Section H.
H PROOFS FOR lp ANALYSIS OF MAXENT MoCo
We first show some useful lemmas towards the proof of Theorem 6. J2, J X' - R. we have
Lemma 12. For m functions
llfi + ........ fmlllt, S m
fe a.p'
Proof. We have
[|1 + .... + fm lla = / p(dx)
Σ Si(x))
( [(Oo)) 1n
- / plam)
(2 14/3) 3/1
m² / p(dx)
Σ Ei(x))
m3 > 11
27

---

Published as a conference paper at ICLR 2024
Lemma 13. For any policy n,, we have Gppp ppppppp p,P G Gp.pp
Proof. We write
G Gpp.ppp - Gpp P,P
P.
(I - (TTp - 7p= -
(1-- + +1) (>p** 110*-17P' -
(I yp=)) ((rD= YP=) - -p-)-1
(1--))11---111 + 1) (7p=-1pT))
(I yPa) 11 (G7D* xPx)) -p--)- + (I (I- -yp-)-1) (s)pp
(2Px - -ppr
(I yP*) -1 (I->/=)(( (I pp=) (np² - -pp*)
(I yP") 1 (>pp" - -pp")
Gpp.p.
Lemma 14. For any Rd we have
| DT) unbiill S
+ =11(tooalll..)) -lwlllo.
Proof. We write
I(P" (1p"-Pa)) pp) Euiiill1 =
f / Σ W/ (P""))(t)((P""))))) (0)roo(=o))
=
- (P"
$ ||l|| / p(dx) Σ ((P) - (pm (pm)))(z))
$ || / M(lr)) vd / (ddalo) 2e (2r, a) + (eMtnda(Z (2, a))
=1|w|l>> / p(dx) Vil ( 2r (x) + Me)
vil (2l| 11,, + 3 31lehoodall1.)) ||w0lloo
where we used Lemma 10.
Lemma 15. Define
(V, & / p(dx))|p*((aa) - PT P'((1=)]1
We have
(V, S v2 @Model
II 1, + 3 @l@@urrylll.
Proof. Using (C.1) in proof of Lemma 2 and Lemma 9 we have
/ p(dz)) (P= - PnT (+1x))| ||| < / ((dx)) /
- (-)lx,
< / p(dr) / T(da(z) /2eModee a) + 3 EQuary (2,a)
1, + 2 B /'uerryl2..
= =V
28

---

Published as a conference paper at ICLR 2024
Lemma 16. Assume for any and x, we have A - B/2 U,(a), (I,, & A+ for some values A and B 2 0. Then we have
dP (- Lr a) d'((1 x. a)
2 32
S exp
Proof. Assume À is the dual problem of MaxEnt density estimation resulted in P(-|2, a). We have
(P a) (3) exp
- -Aa) An)
dP
We have by Jensen's inequality
A^ = log / P(dylz,
Σ Xcdi(u)
Σ Aros((u) )
2 / P(dylz, a) log a)
exp
/ P(dylz;a) Σ (rol(())
Σ
Thus
dP( dp(()
pr, a)
(3) = exp
Σ (oi(l)) -Ax
dP(-12r,))
Σ A((di()) By (y
$ exp
< exp((i\Alln..
Now to bound [ note that for (x, u) = P [Y)( the solution of (P2) is P- a) that corresponds dual parameters X' 0. Using Lemma 5,
2 (V((,,)) (((ra)))ls S VaB. zz
2
2
|All| = I|d X112 S
32
We get
dP((1a, a) d)(((x,)) (v) < <exp(BIAA1) exp exp(BVal\ll)) S eex
22B2d
Lemma 17, Let eq, cz be defined as in Theorem For any policy n, v: X - R and E Idd
huve
Σ w
+ (eg)) -1lw|1
4.p
4,p
29

---

Published as a conference paper at ICLR 2024
Proof. Define
_ Σ w
("(+)x) / 17" (d22lx))P
AP(d2
'D' (de(y) - (dz(y))
TV, A / (dxx)l (1)z)) - PT (-|x)]1
D (I (I- ->p") ( Σ widd)
E E [I -I- ->p") w;ds).
We have
G Gp = (xp= >p=")v
= =(I --==)-=---- 7p= (v= Σ wish) + (I (1--pP"--10 ""'p" -pD=) wisss)
=D+B. E.
We bound norm of each term separately. For A, we write using the Cauchy-Schward inequality
- p(dxz)
// 1 17 (dylzz (P* - (=(dll)) u(z))
|DD|| 4,p
< / pldz) [/] "
7" (dylzz) APP()2)y) |
(1 7)a I p(dx)
[/] (Veldy) AP(dal))
"7" (dy(z)))) |u(2)] / AP((2ly))
Vp(dy)
$ (1 7)2 S. pldx) (fl p(dy) AP(aal))
71
(/l
(dylxx) u(=)² <P (y)
p(dy)
U.2
2 (1 - -- TV2. [ /o(LL) (J] (dy]l)) u(2)2 AP(da
7/
p(dy)
TV2 p. / p(aan) (VVcdde)).w())))) (1, (
71
m(()))
(1 - 7)
Vp(dz) p(dy)
f p((c)) [P(de)alee)] 1.1. 77 AP(dzll)) 27 vp(dz) p(dy)
5 (1 - 7-
TV2. p
TV2 ||ul|,,0 JI p(dx) (1 (ddgp))) (APd)))).AP(dde)) AP(d2)y) 2
y
(1 7)
Voldz). p(dy)
7
TV2 p |ullā, C.
(1 7)
30

---

Published as a conference paper at ICLR 2024
For C' we write
c= /1 p(dx) (
AP(dzlu) APP(dall)
Vpldz) p(dy)
p(dx) /. o(dE)
p(dy)p(dz)
/ p(dx)
(-(x)
[ ((d=))
18" ((dd)))))((d))))
dp
p(dz)
(-|z)
S (dd((y)))P + I, 77 (dylz))P<dzzl))
p(dx)
p(dz)
dp
p(dz)
dr (-1z)
11
((dz(y)
p(dr)
p(d=)
dp
p(dz)
p(dz)
dn l (1xx)
2 17 (dz/z)
2
((22ly)
27
p(dz)
p(dz)
+
dp
p(dz)
p(dz)
/ p(dx)
dr (11x) dp
dny dn (+1x)
2
(-yy)
p(dz)
dp
dp
dr) (+Iz) dp d1) dp
1
dry (-13)
2
doo
2 p(dx)
+2 p(dx)
dp
dp
20
S 2-- /. p(dr))
4422d
(+|x)
dw
2
+ 2eep
p(dr)
32
dp
dp
(p) + (0T(p)*,
where we used Lemma 16. Also from Lemma 15 we have
2 B Quurrll1
TV S 2| +
This means
|DII S (1 71 (0)(0)+ ( (V2lleModell
2-
+ 1/ -lull2,
7) C ( [
27
B (1uueryll
2
2
-lullla
Now we bound the E term. Define
f(x) & Ey-pr(1a)
Σ (r) Ey
Σ ())
Using Lemma 14, have
11/ S vil (2d(2ll -11extooelll1.)) ||wlloo
(H.I)
We have
74
( ((T((bll))()))
1.p
<
(1 - 7)4 p(dx)
< (1 - 7)4 / p(dx)
74
dn (dr((1a))' ( p(aivle)(()))
do
(1 7)4 llf 11, / p(dx)
dn (-Ix)
dp
.00 (0) dp d(22 @ul Alle 11
(1 71- 7)²
31

---

Published as a conference paper at ICLR 2024
Putting things together using Lemma 12:
G p
|1,0 =I1 + Elli,p
8| D 1i. + 81
4 3 $ (1 7) (CT(p) ( +T())) (VIlccioaaellll + 2 || (1 lir)) ?
1
Iaalli
8yy
(1 (1- (D) d @2urerllrl + (l1ektodall...)) 11ooll
$ $(e))* 1|ull1 + +cz)) -1w1
Proof of Theorem 6 for PE
Proof. We have
G Van p.
4,p
4,p
p.
p.p
V
G.p. VTE
1.
3 23/4
Goee VA /...p
+ +23//
C.p.p V
p,P
4.p
4.0
s 2
T p.p
V
G
V
p.P
p,
4.p
4,p
Using Lemma 17 with w = 0 we have
p.p. C.p.p
V
S e
4,p
4,p
< -
V
7m
14.p"
Also from Lemma 17 we have
1/4
c Van
(e) ( p
//2
+ +e (e (/
4,p
4.p
Tp S ej
V
Σ
wosds/
+ez ThE 1/llllll +
4,
with substitution we get
||VTHe VA 1,, S 20 - V.
111.0 + =207m0
V Σ Eusbbll 4.
+ +2 [||l
Rearranging the terms give the result.
Proof of Theorem for Control
Proof. From proof of (C.3), we get
||ve ya
V+
G
va +
6r. (1V - vay) -Va) / 1lap a,p
P.
+
4.p
< 3
GT
p.
Voll
+3/ G
+3
p
vol
+ + - v= -v= 11a0
1,p
1p
From Lemma 17 with w =0
6 (V* -
- 4.
1.
32

---

Published as a conference paper at ICLR 2024
Also for any
3
Gm
P.
V*
<e V -0-
Σ wi
+ +
1,
1p
3
G p
V*
S eñ
v- Σ
wiss
+ @glluoooo
4,p
4.0
Thus,
V
V=
26
v-
V
Σ
widi
+ +222|lulla
+ v-
-V#
4,p
4,p
4,
Rearranging proves the result.
I PROOFS FOR SECTION 4
Here, we give the proof of Theorem 2 after the following lemma.
Lemma 18. If V is the value function at iteration ic of MoCoVI for control. Let B, Query be defined in Theorem 2. We have
I 1o S 3c, [|Model oo || SWmma
inf
V-
Σ wedel
-calleuuery aoo
Wmax.
Proof. Let Pk the corrected transition dynamics used to obtain V4. Let = r + -PP->Pa))' According to Rakhsha et (2022), V (rk Pk) V* (rx: Pk). Now we have
V V (" Pk) - (r, (r)
x V (rk: Pk) V (r; Pk)
(I ypr ) (rit =
(I (--pp -1 (TpTA V-
P V"
On the other hand
V
V2 = V" (rk, Pk) - ('(r, Pa)
& V" (rk, Pk) V= Pk)
(I 7p" -1 (rr" - -
= (I pp - (ypp* -ypa V
P,P. V*.
Thus,
||V - -Velloe S max
(axx(G/ c p.p. V'
1 11)
inf || Swmax
| Σ wrrktts + [ || Wmax:
where the last inequality is from Theorem 1.
Proof of Theorem 2
Proof.
For PE, we note that from Theorem we have for any K < 2
VTvE Σ wirhetil || + +call Wmax
- Vellos
5 3e, [|MModtll
inf || Swmmn
xc I V - VA-1lloe + 0z Queery |l Wmax-
33

---

Published as a conference paper at ICLR 2024
By induction, get
/7"K|[ Vollo + 1 1 7/k
,1k C2
| Vxllo
|Queryyl Wmax-
1- 7
For control, note that according to Lemma 18, for 1 S k: K
Vo Σ widk+t 11o +call blac Wmax
||V Vell mx I 3e, ||eModellll
inf || Swmax
$ >1IV Vi--1lo + 02 Equryy 1lo0 Wmaxx.
Consequently
1 - 1- -V- VK- S / -Voll +
C2
Quecryy Il Wmax
000
1 1-
Finally, based on Theorem 1,
60n Modall
V
V 10 I - 3c, eModellloo || Simmax
inf
wi Ni Σ
i=1
+ 202 | loc
1 3eg | lc
-max
202 aaa||euurylla
r" VK-1 11 + 1- 3c, /|MModelllls
$ 3c1 ||Modelll
Wmax
2
1-
1
2c2 Seal|Queryyli llo Wmaxx
S 3c1 ccoleMoocllloo
V" V- Vol
1 1- 3c1 ||
J ADDITIONAL EMPIRICAL DETAILS
f
t
1
t
f
t
Figure 2: Modified Cliffwalk environment (Rakhsha al., 2022).
We perform our experiments on 6 gridworld environment introduced by Rakhsha et al. (2022). The environment is shown in Figure 2. There are 4 actions in the environment: (UP, RIGHT, DOWN, LEFT), When an action is taken, the agent moves towards that direction with probability 0.9. With probability of 0.1 it moves towards another direction at random. If the agent attempts to exit the environment, it stays in place. The middle states of the first, third, and fifth row are cliffs. the agent falls into cliff, it stays there permanently and receives reward of -22, -16, -8 every iterations for the first, third, and fifth row cliffs, respectively. The top-right corner is the goal state, which awards reward of 20 once reached. We consider this environment with 7 0.9.
34

---

Published as a conference paper at ICLR 2024
Low Model Error
Medium Model Error
High Model Error
10
Normal (edmalized led [|V
10
10
12
100
14
Iteration (k)
McCoVI (d+1)
McCoVi (d-2)
McCoVI (dl+3)
06-V1
....
VI
Pure MERL
Figure 3: Policy evaluation results comparing MoCoVI with VI, pure MBRL and OS-VI. (Left) low (A = 0.1), (Middle) medium (A = 0.5), and (Right) high (A = 1) model errors. Each curve is average of 20 runs. Shaded areas show the standard error.
Low
Medium
High Error
Normalizes aalazeddd llv -vll
10a
10
8k Environment Samples (t)
10k
MoCoDyna (d=1)
McCoDyna (d=2)
MoCoDyna (d=3)
O5-Dyna
DD-Leaming
Dyna
Figure 4: Policy evaluation results comparing MoCoDyna with Dyna, OS-Dyna and TD-learning (Left) low (A 0.1), (Middle) medium (A 0.5), and (Right) high (A 1) model errors. Each curve is average of 20 runs. Shaded areas show the standard error.
For MoCoVI, we set the initial measurement functions Φ; for 1,.... d constant zero functions. We can set vb 0 for i ..... d without querying P. This makes the comparison of algorithms fair as Mo not given extra queries before the first iteration. The convergence of MoCoVI with exact queries and 3 = 0 is shown in Figures I and 3 for the control and PE problems.
Figures and show the performance of MoCoDyna compared other algorithms in the PE and control problems. As discussed after Theorem 1, it is beneficial to choose measurement functions such that the true value function can approximated with Σ; w.d, for some small weights w,. To achieve this in our implementation, in line 9 of Algorithm 1, we maintain this property of measurement functions by subtracting the projection of the new value function V/2 onto the span of the previous d functions before adding to the measurement functions. We have
initialize 01:d+e with an orthonormal set of functions. Also,
d+c-1
Odtc t V1
Σ 1=011
(pi, Vi)
di.
(J.1)
and then we normalize da-c have a fixed euclidean norm. The hyperparameters of MoCoDyna for PE and control problems are given in Tables 3 and 4.
Model Error Reduction. To show that the model correction procedure MoCoDyna improves the accuracy of the model, we plot the error of original and corrected dynamics in the control problem in Figure 5. The model error is measured by taking the average of |P(-|ar, a) P-- a) or [[P(-|a, a) P a-)ll over all x, a. We observe that higher order correction better reduces the enror
Computation Cost. In Table we provide the average time the calculation of P has taken in MoCoDyna in the control problem. This is total time to calculate P(- a) for all 144 state-action
35

---

Published as a conference paper at ICLR 2024
pairs in the environment. In our implementation, the dual variables of the optimization problem for all state- lute-action pairs are optimized with a single instance of the BFGS algorithm in SciPy library. Note that in general, different instances of the optimization problem (P2) for batch of state-action pairs can be solved in parallel to reduce the computation time. Table shows the full run time of the algorithms. It is important note that in Algorithm 1, apart from reporting the current policy for the purpose of evaluation in line 6, MoCoDyna only needs to plan with P every K steps to have V2 line 9. In our implementation, planning done every 2000 steps evaluate the algorithm. Performing the planning only when needed in line 9 would make the algorithm computationally faster.
Low Model Error
Medium Model Error
High Model Error
1.0
Model Error
0.6
0.4
0.0
100k
150k 0k
100k 150k
50k
100k
150k
Environment Samples (t)
Dynamics
Dynamics
Corrected Dynamics (d+2)
Corrected Dynamics (dm3)
Figure 5: Comparison of the error of the original uncorrected model compared to error of corrected dynamics in the PE problem. (Left) low (A 0.1), (Middle) medium (A 0.5), and (Right) high (A = 1) model errors. Each curve is average of 10 runs. Shaded areas show the standard error.
Table Average computation time (seconds) during run algorithms in the control problem for low (A = 0.1), medium (A 0.5), and high (A 1) model errors.
MoCoDynal
MoCoDyna2
MoCoDyna3
0.1
0.24
0.58
1.51
À 0.5
0.29
0.52
1.39
À =
0.2
0.5
1.44
Table Run time (seconds) for a single run of algorithms in the control problem for low (A 0.1), medium (A = 0.5), and high (A 1) model errors.
TD Learning
Dyna
OS-Dyna
MoCoDynal
MoCoDyna2
MoCoDyna3
0.1
44
50
555
119
134
200
0.5
44
34
565
113
114
169
À =
44
33
600
91
110
172
Table 3: Hyperparamters for the PE problem. Cells with multiple values provide the value of the hyperparameter for different model errors with 0.1, 0.5, and
1, respectively.
TD Learning
OS-Dyna 0.05, 0.05, 0.05
MoCoDynal
MoCoDyna2
MoCoDyna3
learning rate
0.2
c
2,2,2
2,2,2
2,2,2
0.02, 0.02, 0.02
0.16, 0. 0.16
0.14, 0.14, 0.14
K
250, 400, 750
300, 300, 400
300, 300, 400
36

---

Published as a conference paper at ICLR 2024
Table 4: Hyperparamters for the control problem. Cells with multiple values provide the value of the hyperparameter for different model errors with À = 0.1, À = 0.5, and X = 1, respectively.
TD Learning
OS-Dyna
MoCoDynal
MoCoDyna2
MoCoDyna3
learning rate
0.2
0.02, 0.02, 0.02
2,2,2 0.02, 0.02, 0.02
2,2,2 0.16, 0.16, 0.16 6k,, 6k, 6k
2,2,2
0.14, 0.14, 0.14 10k, 10k, 10k:
K
10k, 10k, 10k
37


Reviews:
[{"review_id": "0heVcVZaRd", "reviewer": "Reviewer_aRvY", "summary": "This paper proposes a novel method for planning with an imperfect model, called MaxEnt Model Correction (MaxEnt MoCo). It *corrects* the next-state distribution of the model such that its expected value aligns with the true environment. This is achieved through Maximum Entropy density estimation.\n\nBuilding on top of MaxEnt MoCo, they propose Model Correcting Value Iteration (MoCoVI) and the sample-based variant Model Correcting Dyna (MoCoDyna). Both methods iteratively update the basis function, using the value functions derived from MaxEnt MoCo.\nTheoretical analysis suggests that the MoCoVI may converge to the true value function at a faster rate than approximate VI, under specific conditions. The efficacy of the proposed methods is empirically validated in a 6x6 grid world environment.", "questions": "Please see the weakness section for my questions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper delivers rigorous theoretical results.\n\n2. The approach is novel to the best of my knowledge.\n\n3. The paper is overall well organized, making it relatively easy to follow.", "weaknesses": "1. I am not fully convinced by the potential faster convergence of MoCoVI than VI. \n\n    Let’s say that the model is perfect, why should MoCoVI enjoy a faster convergence? Also, in Theorem 2, the comparison between the order of $\\gamma'$  and the order of $\\gamma$ could be oversimplified. For instance, the constant could matter: the big O hides the constant $(3\\sqrt{2})^K$ which could become significant.  Besides that, the $\\gamma'^K$ also hides $(\\frac{1}{1-\\gamma})^K$ but is not addressed in the paper.\n\n    Another concern is regarding the maximum of the ratio over K steps in $\\gamma'$. Can the authors comment on the implications of it on the robustness of the algorithm?\n\n2. The gap between theory and experiments: the theoretical analysis suggests applicability to both finite and continuous MDPs, yet experimental validation is confined to a small-scale tabular MDP. Broadening the experimental scope to include continuous MDPs would substantiate the theoretical findings more comprehensively.\n\n3. The requirement in MaxEnt MoCo to sample the dynamics `d` times for each state-action visited, seems to restrict its practical applicability.\n\n4. The paper could be improved with additional clarifications in certain sections. I would ask the authors to help address the following:\n\n    a. Is there any assumption on the action space? It does not appear to have been stated in the paper, except for MoCoDyna where Algorithms 1 assumes a finite MDP. It appears that there's an implicit assumption that MaxEnt MoCo and MoCoVI are applicable to both finite and infinite action spaces. However, the approximate VI method that MoCoVI is compared with, traditionally assumes a finite action space [Munos 2007]. Could the authors clarify why the finite action space assumption is not necessary for MoCoVI?\n\n    b. The introduction claims that the theoretical analysis is applicable to “both finite and continuous MDPs”. Does this applicability refer to both the exact and approximate versions of the proposed methods? Considering the complexity often associated with analyzing continuous spaces in RL, a further explanation on how the proposed analysis overcomes these challenges would be beneficial.\n\n    c. The algorithm for MoCoDyna, as presented in Section 5, is specific to finite MDPs, yet prior analysis encompasses both finite and continuous MDPs. The paper suggests the possibility of extending MoCoDyna to incorporate function approximation without elaborating on the approach. Could the authors clarify if the focus on finite MDPs is solely for the sake of a simpler presentation, or are there inherent difficulties when adapting the algorithm to function approximations?\n\n    d. The significance of the additional `c` features in the `d+c` features in MoCoDyna is not clear. Could the authors provide clarifications, and guidance on how to select `c`?\n\n    e. The paper assumes that we can make exact queries to P in MoCoVI. Yet, the algorithm description only has approximation $\\psi$ and lacks details on how $\\psi$ is updated.\n\nMinor:\n\nIt would be beneficial if the algorithmic procedures for MaxEnt MoCo and MoCoVI were presented (perhaps in the appendix) in a structured algorithm format, similar to MoCoDyna. \n\nTypos:\n\n1. Is the $|| V^{\\pi_{PE}} ||_\\infty$ before Sec. 3.2 missing anything?\n\n2. Sec. 3.2: domain of $\\phi$ should be $\\mathcal{X}$ $\\times \\mathcal{A}$ instead of $\\mathcal{X}$.\n\n3. Sec. 3.1: in the equation at the end of paragraph 1, the expectation should be w.r.t. $\\bar{P}$.", "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": "", "extra_scores": {}}, {"review_id": "L0jl3Xi5v6", "reviewer": "Reviewer_sy6v", "summary": "The paper proposes a new method for MBRL, where a correction of the model is learnt. The correction improves the distribution of the next state prediction. The work consists of a model correcting approach, and its application to value iteration and to a dyna-based approach. A benefit of the approach is the combination of a model with a faster convergence thanks to the use of a model. The model-correcting prediction helps to keep the model close to the true dynamics of the environment.", "questions": "- In the introduction, you say MaxEnt MoCo first obtains $E[\\phi_i(X')]$ for all $(x,a)$. That sounds expensive and seems to be computed on demand; but what is the cost of solving the lazy approximation (P1).\n- Can you comment about computational cost and scalablity of the approach given that the experiments were limited?\n- I may have missed it but would it make sense to compare how close the dynamics of the real environment with the predicted and corrected one? If that's the case, evaluations of how well the environment can be predicted might be helpful even without additional results from RL experiments.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work is well motivated and the introduction / background are concise yet provide enough detail to set the scene. The paper is well, logically written. At times, it leads to a question (eg isn't computing this for all (x,a) expensive?, in the intro), to later answer the question. The approach is interesting and improves over conventional approaches. Good theoretical contributions.\n\nThe appendices are useful, equally logically structured, and contain additional analysis and proofs.", "weaknesses": "The main weakness in my view is the limited number of experiments, moreover the experiments are relatively simple.  I would have liked to see how the approach is used and how its performs (also in terms of time) for large or continuous environments (which seems to be planned for future work).\n\nI'm not quite sure about the related work and comparison to approaches that use multiple models to improve predictions, which would be a more appropriate comparison (apart from OS-VI, eg residual models or even ensemble models), along with a comparison of computational costs (during training or inference). Even the additional empirical results in the appendix are not particularly large.", "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": "", "extra_scores": {}}, {"review_id": "sQvooqqduN", "reviewer": "Reviewer_gS8c", "summary": "This paper proposes Value Iteration (VI) and Dyna-style sample-based version utilizing an approximate environmental model. Under the assumption that the approximate model $\\hat{\\mathcal{P}}$ is given, a corrected model $\\bar{\\mathcal{P}}$ is derived by minimizing the KL divergence $D_{KL} ( \\cdot \\parallel \\hat{\\mathcal{P}})$ with feature matching constraints. The proposed method, MoCoVI and MoCoDyna, employ the corrected dynamics to learn a state value function. Then, the value function trained with the corrected dynamics is used as a new basis function used in the feature matching constraints. MoCoVI and MoCoDyna are compared with OS-VI and OS-Dyna, respectively, on the modified Cliffwalk environment. The experimental results show that the proposed methods converge to the true value function faster than the baselines.", "questions": "1. At the $k$-th iteration, the proposed method uses the basis functions $\\phi_{k+1:k+d}$ and the query results $\\psi_{k+1:k+d}$ to obtain $V^k$. I would like to know why $\\psi_{1:k}$ and $\\psi_{1:k}$ are discarded. Would you discuss this point?\n2. The function approximator for the value function is unclear. Is $V$ approximated by $\\sum_{i}^d w_i \\phi_i$? If so, adding $V$ as a new basis function at the next iteration is problematic because it is linearly dependent on the basis functions. \n3. On page 4, the authors mentioned that the number of basis functions, $d$, is usually small, but I am unsure whether it is true in general. I do not know the details of the modified Cliffwalk environment, but I think it is a toy problem. Is $d$ still small if the proposed method is applied to tasks with huge state space?\n\nThe following are minor comments.\n- The end of the second paragraph in Section 2.2: $\\phi(Z)$ should be $\\phi_i(Z)$. \n- The paragraph below equation (3.2): I do not understand the following sentence: $\\bar{\\mathcal{P}}$ is not constructed by the agent.\n- In the first paragraph of Section 3.2, the authors define the function $\\phi: \\mathcal{X} \\to \\mathbb{R}^d$, but $\\phi (x, a)$ is used to compute $\\epsilon_{\\mathrm{Model}}(x, a)$. Is it a typo?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The motivation is well explained, and the paper is overall well-written and well-organized. The proofs given in the supplementary materials are complicated, but the authors provide a detailed explanation.", "weaknesses": "The proposed method is evaluated on the modified Cliffwalk environment that is relatively small. I am unsure if the proposed method is scalable.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)