Operator Splitting Value Iteration
Authors: Amin Rakhsha
Andrew Wang
Mohammad Ghavamzadeh
Amir-massoud Farahmand
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
model-based reinforcement learning

Abstract: We introduce new planning and reinforcement learning algorithms for discounted MDPs that utilize an approximate model of the environment to accelerate the convergence of the value function. Inspired by the splitting approach in numerical linear algebra, we introduce \emph{Operator Splitting Value Iteration} (OS-VI) for both Policy Evaluation and Control problems. OS-VI achieves a much faster convergence rate when the model is accurate enough. We also introduce a sample-based version of the algorithm called OS-Dyna. Unlike the traditional Dyna architecture, OS-Dyna still converges to the correct value function in presence of model approximation error. 

Operator Splitting Value Iteration
Amin Rakhsha 1.2
Andrew Wang 1.2
Mohammad Ghavamzadeh"
Amir-massous Farahmand 2,1
1 DDparrmeett of Computer Science, University of Toronto
Vector Institute
GGoogle Research
Abstract
We introduce new planning and reinforcement learning algorithms for discounted MDPs that utilize an approximate model the environment to accelerate the convergence of the value function. Inspired by the splitting approach in numerical linear algebra, we introduce Operator Splitting Value Iteration (OS- VI) for both Policy Evaluation and Control problems. OS-VI achieves much faster conver- gence rate when the model is accurate enough. We also introduce a sample-based version of the algorithm called OS-Dyna. Unlike the traditional Dyna architec- ture, OS-Dyna still converges to the correct value function in presence of model approximation error.
Introduction
Consider planning problem for a discounted MDP with dynamics P. Suppose that we have access to an approximate model P x P well. For example, P might be high-fidelity, but slow, simulator, and P is a lower-fidelity, but fast, simulator. Or in the context of masel- reinforcement learning (MBRL), P is the unknown dynamics of real-world system, from which we can only acquire expensive samples, and P is learned model, from which samples can be cheaply acquired. Can we use this approximate model P to accelerate the computation of the value function of a policy æ (Policy Evaluation (PE) problem) or the optimal value function (Control problem)?
The Value Iteration (VI) algorithm and its approximate variant are fundamental algorithms in Dy- namic Programming that can find the (approximate) value of policy or the optimal value function. They are also the backbone of many reinforcement learning (RL) algorithms such as Temporal Difference Learning [Sutton, 1988], Fitted Value Iteration [Gordon, 1995, Ernst et al., 2005, Munos and Szepesvári, 2008], and Deep Q Network [Mnih et al., 20.55. Value Iteration, however, can be slow when the discount factor close to 1, as its convergence rate is (***). Morcover, even though we could use VI using P instead of P to avoid expensive queries to P, the obtained value function would converge solution different from the value function of the original MDP.
This paper proposes an algorithm called Operator Splitting Value Iteration (OS-VI) that benefits from an approximate model P. to potentially accelerate the convergence the value function sequence to the value function with respect to (w.r.t.) the true model P (Section 3). This algorithm is for both PE (Section 3.1) and Control (Section 3.2) problems. The acceleration not uniform though, and depends on how close P is to P (Section 4).
A key inspiration behind OS-VI is the (matrix) splitting approach in the numerical linear algebra, which is used to iteratively solve large linear systems of equations [Varga, 2000, Saad, 2003, Golub and Van Loan, 2013]. With proper choice of splitting, one may change the convergence rate of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

linear systems solvers. We show that the conventional VI for PE can be seen as a particular choice of splittin. This observation suggests that one may choose other forms of splitting as well in order to change the convergence rate. It turns out that we can choose a splitting that benefits from having access to P (Section 2). The new splitting leads to OS-VI for PE. For the Control problem, the connection between solving linear system of equations and VI is not as straightforward anymore, as the former is linear, while the latter is not, but we can still get inspired from the splitting approach to design OS- VI for Control. The key step of such an algorithm is a new policy improvement step.
The form of the OS-VI VI algorithm opens up a connection to MBRL where the approximate model P is learned using data. This leads to the OS-Dyna algorithm, inspired by generic Dyna architec- ture [Sutton, 1990]. OS-Dyna is a hybrid of model-free and model-based algorithms. It uses the learned model in its inner planning loop, alike Dyna, but uses samples from the true model P in order to correct the effect of errors in the model. Existing MBRL algorithms would converge to an incorrect solution the approximate model P does not converge to the true model P. This would be the case whenever model approximation error exists. On the other hand, OS- OS-Dyna can still converge to the correct value function even when P does not converge to P. As far know, this is the first model-based RL algorithm with such property.
2 From value iteration to splitting-bssed linear system of equations solvers and back
We briefly describe the VI algorithm and the splitting methods for solving linear system of equa- tions, and explain their connections. We consider discounted Markov Decision Process (MDP) (X. A. R. P.7) [Bertsekas and Tsitsiklis, 1996, Szepesvári, 2010, Sutton and Barto, 2019]. We defer formal definitions to the supplementary material. We only mention that for a policy オ, denote by p its transition kernel, by r" X' + R the expected value of its reward distribu- V (R,, P) its state-value function. We also represent the optimal state-value function by V* = (*,,, P) and the optimal policy by xt T"(R, The Bellman operator T B(x)= > B(X) for policy a and the Bellman optimality operator 7 :B(X) - B(x) are.
tion, and by V
(T*) & max r(z, +7 / P(dyle, aEd
(T) e (x) + +7 (dyl=)
These operators can be written more compactly as T : V + rr + VPV and T V + max, (T"H + V). The greedy policy at state x E X' is
a(z, (z V) + argmax r(z, a) + 7 P(dylz, ((()) aEA
(2.1)
or more compactly, (V) + argmax, T We have TV = TVV, that is, the effect of the Bellman optimality operator T applied to value function V is the same applying the Bellman operator of the greedy policy w.r.t. V to V.
2.1 Value Iteration
The value function V and the optimal value function V are the fixed points of the operators T and T*, respectively, and satisfy the Bellman equation. For the PE problem, this means that
V
>P"V" = (I - <---P">V==
(2.2)
There are several ways to compute the value function of policy и or the optimal value function V including the iterative methods such as VI and Policy Iteration (PI) algorithms, or solving linear system of equations (for PE) or linear programming (for Control). We focus on the VI algorithm in this work. VI repeatedly applies the Bellman operator to the most recent approximation of the value function: Given an initial value function Vo, it generates a sequence (Vi.) k as follows:
( (--
(Policy Evaluation)
Ve
(2.3)
(Control)
For countable state and action spaces, the integrals are replaced by summations. We present OS VI and its theoretical analysis for general state/action spaces, but limit our experiments to finite state/action problems.

---

VI for Control can be written in an equivalent form: At iteration k. we first compute the greedy policy Fy < Tg (V:-1) (policy improvement step), and then V&& f- 7 - Therefore, the policy improvement step is obtained through finding policy that is greedy w.r.t. the last value function Vk-1, that is, the best policy if we only look one step ahead. This form will be conductive for our later developments. As the Bellman operator is y-contraction w.r.t. the supremum norm, the convergence rate Vi to V (or V*) would be O(7*). This rate can be slow when y is close to 1.
2.2 Matrix splitting for solving linear system of equations
The VI for PE can be seen as a (matrix) splitring-based iterative method to solve the linear system of equations (2.2). Consider the linear system A= b, with A E IRdxd and z, E Rd. Suppose that A is decomposed to A = M N for some choices of M, N E Rdxd (more generally, A. M, and N can be linear operators). Therefore, z satisfies M N + The splitting-based iterative approach defines the new approximation zμ given the current - by solving
M = 2 + b,
or equivalently,
2/
b).
(2.4)
To analyze the convergence of this iterative method, consider the error eR A 2 2. As =
M-1(Nz b), we have ex = M MN +) M- + M dynamics of the error is
M-1 =), so the
Ck M NM
(M (N)
(2.5)
Let G M- The norm of the sequence (ex) (ex)x21 can be upper bounded as
||x|| = | eol s ||c* ||lool s |eol-
(2.6)
The errors are (norm-) convergent ||G|| = || < 1, for some choice norm. More generally, the necessary and sufficient condition for convergence is that the spectral radius p(G), the maximum absolute value of eigenvalues of G, smaller than one, see e.g., Theorem 4.1 of Saad [2003] or Theorem 1.2.1 of Golub and Van Loan [2013].2 The convergence is faster if the spectral radius (or norm) is closer to zero.
The success of this iterative procedure depends on how we choose M and N such that the norm (or spectral radius) is as small as possible. Also we want to choose an M such that solving M N Nzk-1 + b is not very expensive. For example, if M is an identity matrix I, we get that N =I A, and the iteration becomes 2g (I 2 + b. This iteration is convergent if p(I - A) < Other commonly used choices lead to the Jacobi and Gauss-Seidel methods that are described in the supplementary material.
We are now ready to make the connection between splitting-basse iterative methods and VI for PE. If we choose policy π (2.2). The VI for PE, which is V2 = >P*V= + r = (I - - + r", corresponds to the choice of M and N y/P". This brings up the question of whether it is possible split A differently so that the resulting VI-like procedure has better convergence properties. We next suggest a particular choice.
- yP", we see that equation AV r" indeed the Bellman equation for
3 Operator splitting value iteration algorithm
We introduce the Operator Splitting Value Iteration (OS-VI) algorithm. We start from the PE problem and develop the Control version based on that. We also present visualization of how VI works.
3.1 OS-VI for policy evaluation
Given policy true model P. and approximate model P. split I - -yP= to M and N
M = - 7p""
N = yPP - pDa).
For matrix norm, we have p(G) < ||G]], so the condition on the norm is sufficient, but not necessary. Our analysis will be nosm-based.
3

---

Following the recipe of (2.4), the OS-VI algorithm for PE would be
V& f- (I (I->P")
(rT + tP - -PT)
(3.1)
starting from an initial Vo.² To gain more intuition and prepare for further developments, we define few notations. We define the Varga operator 5 (x)) + (( named after Richard S Varga (1928 2022) who has made significant contributions to matrix analysis, as the mapping between the space of all bounded functions over X to the same space
8 V - (I (I- (I- (
-PP=-PT)V pT.V].
Observe that (3.1) can be compactly written
V V
(3.2)
It is not difficult to see that S*V* = VT, i... the value function of a policy т is fixed-point of the Varga operator ST. This and other properties the Varga operator are shown the supplementary material.
Given any value function V, define an auxiliary reward function Py : x A R as
/ (P(dyla, -(dylo,, V(y).
fv a) a r(x, a) +7
(3.3)
Similar to r define the notation Fi. X - R as (x) Fr (x, (2)) for deterministic policy x (and similarly for a stochastic policy). With this notation, the effect of applying S to V is
SV (I 10->pp>>> -
This is the value function of following æ in an MDP with dynamics P and reward îv. Therefore, each iteration of VI (PE), we evaluate the policy x according to the approximate dynamics, and reward function that consists of the original reward and the correction term 7(P -PP The computation of this value function is standard PE problem with the approximate model. For instance, we may use another VI (PE) with dynamics P to solve it: We initialize Uo + V, and then for i 2 1, we set U, +- F. + +P This converges to S = "TV==I-- -I-->>>---a rate of O(r'). Note that aside from the computation of rV. which requires querying P in order to compute the V term, this iterative process only uses the approximate model P, which is assumed to be cheap to access.
with the usual
What is the benefit of this OS-VI procedure? the approximate model P is close to the true dynamics P. this leads to faster convergence of V22 to VT as shall be quantified soon. The faster convergence in terms of the number of queries to P. which assumed to be expensive. To see this, consider the hypothetical case that P is exactly the same as P. for example, the cheap simulator happens perfectly match the reality. Then, S for the original MDP is obtained in one iteration of VI- Of course, we often can only hope for P RJ P. In Section 4, we study the impact of error in Pe on the convergence rate of OS-VI in more details, and show that the convergence of OS-VI can be much faster than classic algorithms even if P only close approximation of P.
>P* > (r" + OV) V", and the value function
3.2 OS-VI for control
The VI for Control can be seen iterative procedure that computes the greedy policy कą < Tyg (Vo=1) = argmax_ argmax_7**V. T-V in policy improvement step, and then uses one step of the Bellman operator w.r.t. the obtained policy Ty to compute the estimate of the value function V/2 + 7 Vx-1. as described after (2.3). The OS-Vi OS-VI algorithm for Control follows a similar structure with the difference that 1) the improved policy is the optimizer of the Varga operator, and not the Bellman
Although splitting is originally studied mostly in the context of linear algebra and matrices, we are applying the idea more generally. We are not assuming that the state space X' is finite, and we allow it to be more general, such subset of Rt Consequently. A1 N p etc. operators rather than matrices.

---

operator, and 2) the new value function is obtained by applying the Varga operator of the newly obtained policy. To be concrete, given a value function V, define the S-improved policy
TV (V) _ argmax ST V[= (1 (1- (1->p=)--1Fp
(3.4)
This policy is the optimal policy for the auxiliary MDP AA Fv. P, p,)). We also define the Varga optimality operator S* :B(X) + (() as
S" V + max S
The function S is equal to VVV i... the Varga operator of the S-improved policy w.r.t. V applied to a value function V (compare it with T VV..
The OS-VI (Control) is then simply
V V
(3.5)
which in its expanded form, consists of the following two steps:
Th + TV VV (Vk-1); (policy improvement).
(3.6)
V - STM V (I- (1- +
- Va--)>l (partial policy evaluation). (3.7)
Comparing the S- S-improved policy (3.4) used in the policy improvement step (3.6) of OS-VI with the conventional greedy policy (2.1) is insightful. The greedy policy is argmax,, st TV. Expanding T*V, we see that the greedy policy is the maximizer of rx +PVV. The function r* + +PP V is a single-step bootstrapped estimate of the value of V*, and its maximizer, the greedy policy, is in general different from the optimal policy, which maximizes V On the other hand, the S-improved policy TV (V) solves a full MDP with an approximate model P and a reward function that has both the original reward r and the correction term 7(P - V. In the special case that P. P, the correction term is zero, and πy (V) would be the optimal policy x² for the original MDP. As often P P. the value function of policy Ty is not exactly the optimal value. The partial policy evaluation step (3.7) updates the value function to value that is closer to the optimal value function.
The use of matrix splitting- based ideas, either explicitly or implicitly, in the context of dynamic programming is not completely novel to this work. Kushner and Kleinman [1971] is one of the earliest paper that mentions the Jacobi and Gauss-Seidel procedures for computing the value function. Porteus [1975] proposes several transformations to the reward and probability transition matrix with the goal of improving the computational cost of solving the transformed MDP. One of the transformations, called pre-inverse transform, has some similarities with the operator splitting of this work. The end result, however, is different. Bacon and Precup [2016] offer matrix splitting perspective on planning with options. The connection between multi-step models and matrix splitting developed in Chapter 4 of Bacon [2018]. Refer to the supplementary material for more discussion.
Remark.
3.3 Visualizing how OS-VI works
To present some intuition on how OS-VI works, we visualize the value function trajectories of several algorithms, including OS- VI, on a 2-state MDP, in Figure 1. We consider the policy evaluation for the dynamies pr' = [ 0.1 with the reward xxx = ( (-b.s) and 7 = 0.9. We consider two approximate
models: relatively accurate P
0.05 0.95 J. and an inaccurate Pr inascurate
0.6 10.3 0.
In addition OS-VI (PE), the first algorithm the conventional VI (PE), which repeatedly applies the Bellman operator according to the true model pa to the most recent approximation of the value function. We use 73 to refer to its Bellman operator and to label the corresponding trajectory in the value space. This algorithm converges to the true value function V*_ The second algorithm is VI (PE) that uses TD as the model. This procedure is the basis of the Dyna architecture. We use T to refer to its Bellman operator and to label the corresponding trajectory in the value space. Due to the error of TÆ compared to T7, the algorithm converges to wrong value function V== as both figures show. We observe that even when the model is relatively accurate as in Figure 1a, the converged value function quite wrong. This illustrates one limitation of the conventional model-based RI. algorithms where an inaccurate model may lead to significantly inaccurate estimate of the value function.
5

---

Va
VOD
V(1
T
2
2
((0)
V(0)
(a) More accurate model Pa Paccuuae
(b) Less accurate model Pinacurrat
Figure The value function trajectories of (PE) with the true model (7T), VI (PE) with approximate model T. and OS-VI (PE) (S"; and Ti for its inner loop) for 2-state problem.
The OS-VI algorithm repeatedly applies the Varga operator S to the most recent approximation of the value function. As discussed earlier, each computation of 5" V corresponds to solving an
auxiliary MDP (X', A. Fv.-1 P.r) 7). We denote the Bellman operator of this auxiliary MDP by Tg. The figures show the trajectory generated by the iterative application S on the most recent value function as well as the trajectory for solving each auxiliary MDP, indicated by Tg. We observe that OS-V VI algorithm converges to the correct value function despite using an incorrect model. When the model is more accurate, very few iterations of OS-VI gets value close to V (two iterations in Figure la); when the model less accurate, few more iterations are needed. Compared to VI, at least in these examples, the total number of iterations of OS-V VI is significantly smaller.
When the initial value function Vo value function computed by the VI with the wrong model pT. This is because V1 < 5 (I- and 1%o rM, so Vi (I- -p=))=,- the same solution the value function obtained using the approximate model P. In these figures, this shows itself by the overlapping of the red arrows followed by Т and the first segment of the orange arrows, which are generated by the repeated application of 7T. In further iterations of OS-V DI-VI, the auxiliary MDPs change and the path followed by T (k 2) deviates from the solution of the VI with the wrong model.
the result of the first iteration of OS-VI is the same
4 Convergence analysis of operator splitting value iteration
In this section, we present the convergence analysis of OS-VI. Our results show that OS-VI has an 0(1%)) convergence rate for an effective discount factor 7' that depends on the error between P and P. For small enough error, o < 7 and OS-V SS-VT has a faster convergence rate compared to the classic
VI, Policy Iteration (PI), and Modified Policy Iteration (MPI), which all have O()*)) behaviour. We provide results for both the Lo and L, norms.
4.1 Convergence of OS-VI for policy evaluation
We study the convergence behaviour of OS-VI (PE) in presence of error in value updates. Specifically, we consider that each iteration k, the update (3.2) has an error, i.c..
V& 5 value
(4.1)
The error value encompasses various sources of errors that might occur in solving the auxiliary MDP (X, Fv.., P.7). One source the function approximation error due to using a function approximator to represent Ve. which is often required in large state spaces. Another is the estimation (i.e., statistical) emoor caused due to having a finite number samples, instead of direct access to P, in the RL setting. Refer to Munos and Szepesvári [2008], Antos et al. [2008), Farahmand et al. [2016], Chen and Jiang [2019], Fan al. [2019] for the discussion of function approximation and estimation errors in the RL context. In this work, do not analyze how the number of samples, the function

---

approximator, etc. affect the errors Ck ci We offer enror propagation results similar to Munos [2007]
(approximate VI), Munos [2003] (approximate PI), and Scherrer al. [2015] (approximate modified Pl) for approximate OS-VI.
To study the convergence behaviour of OS-VI (PE), let GT = (I- ----p-----0 - -p)). We use the fact that ST V and write
|| lo -| - -5 - value
100 =
G" (V* x - -V--1) c xaluell llac
- |oo V -V---V-1ll 11-0 + ||ck ||eaaue) 11.0"
(4.2)
Now, we have that
|| lo0 (pm
pp))
||_
7 pr pr
(4.3)
0a
where we used the fact that for any square matrix F with matrix norm |1 1, it holds that [[(I F) S -- (see Lemma 2.3.3 of Golub and Van Loan 2013), and that the supremum norm of a stochastic matrix p' is 1. Assuming that || S value for all k 2 1 and defining effective discount factor Y = l|p - P b0 the upper bounds (4.2) and (4.3) lead to ||VT- V lee S ~V* Vo loe + 1-2" 1-3r valuue
few remarks are in order. First, whenever <. this is guaranteed to be faster than the convergence rate of the conventional VI, which O()*). This happens || - -'1l < 11-1 - If the model is very accurate, we obtain much faster rate than VI's. Since each iteration k corresponds to query to the true model P. faster rate entails that the algorithm requires fewer number of queries to the expensive model to reach the same level of accuracy.
Second, although the model error ||PT - PTl is reasonable choice to measure the distances between distributions (it is the maximum of the Total Variation distance between (=|x/)) and pT (-Jar over v, which itself can be upper bounded by their KL divergence; see the supplementary material), is somewhat conservative it takes the supremum over the state space. Likewise, requiring l|e deal |l to be small is also conservative, as approximating S V using a function approximator given samples (RL setting) often leads to an Lp -nom type of guarantee. We now provide different analysis to address these issues.
To present the norm result, we need to define some notations. First, we define the conditional discounted future-state distribution of policy under Po the following probability distribution:
Given a measurable set B, we have r (B(z) (1 7) E "PP X, E B|X, x. π, PP.. where
the chain (X)) starts from state x and evolves by following policy π under transitions P. For an arbitrary distribution over the state space, we define the discounted future-state distribution concentration coefficient of the upproximate model as
d (+Ix)
(r(6)² = 7 p(dx)
(4.4)
dp
Here d-l(
dp is the Radon-Nikodyy derivative of the distribution (-1x) w.r.. the distribution
It is assumed that for any x E X, (-1z) < P. ie.. (-1x)) is absolutely continuous w.r.t. (otherwise, the coefficient would be set to infinity). This coefficient measures how concentrated the distribution f/" (-[ar) is compared to p. This is weighted according to the state distribution p. Similar concentrability coefficients, but not exactly this one, have appeared in the error propagation results [Kakade and Langford, 2002, Munos, 2003, 2007, Farahmand et al., 2010, Scherrer et al.,
2015]. Finally, we define the weighted -ddvieereence of PM and pT
p (PT(() - PT
= o(de) /
x (P || 1T)) &
PT =
Pr (ddy(a
This notion of model error is less strict in requiring accurate approximation P. in all states. Usually only subset of the state space is important or even reachable in a problem. The above model error can focus on only specific areas of the state space through the choice of distribution p.
We are now ready present the main thcorem for the approximate OS-VI (PE).
7

---

Theorem 1. Consider the approximate OS- VI algorithm for PE (4.1). Let ll-ll, be either the supremum
norm II-Il (x= 00) or for p being an arbitrary distribution over the state space (+ p).
Assume that [|ega ||+ S e palue for all k. Z 1. Furthermore, define the effective discount factor as
1
(+=
(0)x22) || px)) (+= 4, p). y 1
For any k 2 0, we have ||V Vill. S - Voll. +
L-7 Top evulue
4.2
Convergence of OS-VI for control
We turn to analyzing OS-VI for Control. We consider two types of errors: The first is the error between the computed value function and the true optimal value function of the auxiliary MDP, i.c. Vi= V+ The second is the suboptimality of obtained policy compared to the optimal policy of the auxiliary MDP, i.e., T V - -5*V V Concretely, we have
V2 = V' + = V- S V-1 + Ek
(4.5)
policy
(4.6)
We have the following result for the approximate OS-VI (Control).
Theorem 2. Consider the approximate OS-VI algorithm for control (4.5)-(4.6). Let Il-Il, either for
the supremum norm II-Iloo (* = oo) or a.lla.p for p being arbitrary distribution over the state space (* 4, p). For any k 2 let I ; } U {TTv(V-1) : S < k). Assume that
||ckelue] S e value for all 2 1. Furthermore, define the effective discount factor as
maxx p 1 PM
(* = (+=00),
1-7 max (2 Pa)
(* 4, p).
We then have
27th - - < 1- VIVo - V*I,+ + 21 17
value
policy
(1 -/1)2
ck
We can compare this result with the convergence result of VI. For VI with the supremum norm, following the proof of Equation (2.2) by Munos [2007], we can show that | V my**|aa ||x s
2+ ||V - Voll + 2y(1-gk-1 y vatee with ||V - 1Vl S value for all < & (similar result for the -orm also holds, see Theorem 5.2 in Munos 2007). For the approximate VI, the initial error -|V* 1r*-Vol Volloo decays with the rate of ((r²). This should be compared with ") rate of OS-Vi VI. The effect of error at each step value is also similar: approximate VI has (1 7) dependence while approximate OS-VI has (1 - -/)-2 2. What is remarkable is that as opposed to 7 which is fixed parameter of the problem and can be close to 1, 7 can be made arbitrary close zero when the approximate model P becomes more accurate. The additional information given by P allows us to get much faster rate than VI. Of course, this requires the model to be accurate. An inaccurate model might be detrimental to the convergence rate, and may even lead to divergence. Similar conclusions can be made in comparing OS-VI with Policy Iteration and Modified Policy Iteration, as discussed in the supplementary material.
1-7
(1-7)2
Operator splitting Dyna
In the RL setting, only have access to samples from P. MBRL algorithms, such variants of the Dyna architecture, learn P from those samples, and use it to find the value function or policy. The learned model P generally different from P due to the finiteness of the samples as well as the possibility of model approximation error: the true dynamics P may not be representable with the function approximator used to represent P. This is another way to say that the world may be too big to be represented by models. A MBRL algorithm that uses P in lieu of P does not find
8

---

Algorithm OS-Dyna
I: Initialize Vo,F F 0, and the approximate model P.
for 1, 1,2.... do
3: Sample Ax, X;) from environment.
4: Update the model P with (Xe, A,, Re, Xi).
5: At) <- F(Xe, Ae) + ar Re + *VV--1(X) - x(xx)) aV =(Xe,
6: V/2 + (FFF P) (For PE) + (F, P), ne t (F, P) (For Control).
7:
end for
the true value of the true MDP. Based on OS- VI, we propose OS-Dyna, as hybrid model-based and model-free RL algorithm, that takes advantage of both the true environment and the model in its updates and can converge to the true value function despite using inaccurate P.
Learning P in OS-Dyna is similar to other MBRL algorithms [Moerland et al., 2022]: one can use various model learning approaches, either based on maximum likelihood estimate or a decision-aware model learning approach, to learn the model. Given learned P. we can compute Vi: from the auxiliary reward function Fą A Tv--, by solving the PE or the Control problem in the auxiliary MDP (X, A, Tk, P), as discussed in Section 3.
As Vj is function of Fk, we focus on how Fe should be estimated. The update rule of Fs in OS-VI entails that for every (x, a), we have
Fz a) = r(z, a) + P()22,)) - -(-22, (o (T V (=(Fk-1,
(Policy Evaluation)
(5.1)
= r(z,)) ( + (P(+),, - -
(Control)
(5.2)
We update our estimation of f using samples, as shall be discussed soon, and then the value function is updated to (*(F, P) (PE) or (F P) (Control) with most recent estimate of F. The challenge that the above update rules need access to distribution P(-|z, a) for every (z, a). while we only have samples from P at some (Ir, a) pairs. Fortunately, this challenge has been tackled in developing sample-based algorithms based on the classic VI:
V(a,a):
Qx(2, a) = ((x,a)
(P(-jr,a)Ve-
(5.3)
PE and V max Q=-1 (x, a) in Control. There are multiple approaches to develop sample-based algorithms based on (5.3) such Fitted Value Iteration and Stochastic Approximation (SA) [Borkar, 2008]. In this paper we use SA to develop OS-Dyna, but we point out that other algorithms and techniques can also be applied to develop other versions of OS-Dyna. The key step SA is to use samples to form an unbiased estimate of the intended update value. For step in the true environment leading to (X,, A., R2 X;) tuple, can have the estimate Y, = R2 + 7V (Xt) - TEE x [V(X)) where the expectation can also be estimated by samples from P', At). This estimate Y, of the update rule can then used to update As an example, for finite state-action problem, the update rule is
where -1-=-Q-1(2100
F(XI, As) <- r(x,, A.) ox(Y, r(X,, Ar)),
(5.4)
where is the learning rate. The final procedure of OS-Dyns is presented in Algorithm 1.
Experiments
We evaluate both OS-VI and OS-Dyna in finite MDP and compare them with existing methods. Here we present the results for the Control problem on modified cliffwalk environment in a 6 x 6 grid with 4 actions (UP. DOWN, LEFT. RIGHT). We postpone studying the PE problem, the results for other environments, and other relevant details to the supplementary material. Our convergence analysis shows that the convergence rates of our algorithms depend on the accuracy of P. To test OI and OS-Dyna with models of different accuracies, we introduce the smoothed model P of transitions P with smoothing parameter
P(,z,a; (1 - x)P(Hzz, (U 0}),
(6.1)

---

10
Normalized [| V lla
Model
10
Model (A 0.5)
Model
-25
Q-Learning
OS-VI (A
Vo(o)
Dyna (A=
10
OS-VI- 0.1)
-50
Dyna =
OS-VI (A 0.5)
-75
Dyna (A 0.51
10-3
05 Dyna (x=
110
OS-Dyna 0.1)
O5-Dyna (A 0.5)
10
-25
0
10
15
20
25
0k
20k
40k
60k 80k
Iterations
Environment Samples
Figure 2: (Left) Normalized error comparisons of OS-VI, VI, and the optimal policy of model P.
(Right) Comparison of OS-Dyna with Dyna and Q-Learning in the RL setting.
where (A) for some set A is the uniform distribution over A. Here, À allows making adjustments to the amount of error introduced in P w.r.t P. If X p P will be the accurate model, and if = P. will be uniform over possible next states in PP
The left plot in Figure 2 shows the convergence of OS-VI VI compared to VI and the solutions the model itself would lead to. The plot shows normalized error of V w.r.t V*, iee. !| can be seen that OS-VI has faster convergence with more accurate models and introduces acceleration compared to VI across different model errors. Note that the convergence of OS- DS-VI has been achieved despite the error in the model. The dashed lines show how fully model-basee algorithm, which only uses P. would obtain suboptimal solution.
/
We also compare OS-Dyna with Dyna and Q-Learning in the RL setting. At each iteration t, the algorithms are given a sample (Xx, At, RG, X;) where X,, A, are selected uniformly random. For OS-Dyna and Dyna we use the smoothed Maximun-likelihon Estimation (MLE) model. PMIE the current MLE estimation of the environment transitions, OS-Dyna and Dyna use P(PMLE, A) defined in (6. as their models. The learning rates are constant for iterations t s N and then decay in the form of a₃ = a/(t - N) afterwards. We have fine-tuned the learning rate schedule for each algorithm separately for the best results.
The right plot Figure 2 shows the results for the RL setting. We evaluate the expected return of the policy at iteration in the initial state of the environment, i.e., V (0). Again, OS-Dyna has converged the optimal policy much faster than Q-Learning. Unlike OS- OS-Dyna, Dyna has failed to find the optimal policy in presence of model error. The results show that OS-Dyna can effectively converge faster than Q-Learning without introducing bias to the final solution due to model error.
7 Conclusion
This paper introduced the Operator Splitting Value Iteration (OS-VI) algorithm, which can benefit from an approximate model P ~ P to accelerate the convergence of the approximate value to the true value function in terms of the number of queries to the true model P. With small model error, its convergence rate is exponentially faster compared to well-known dynamical programming algorithms such as Value Iteration and Policy Iteration. We also proposed OS- OS-Dyna as a hybrid saseee-bbbddmmmd-fiiii algorithm that can bring in the benefits of a model- RL algorithm without converging to a biased solution, as Dyna or any other purely model-based RL algorithm does. This paper opens up several future directions. Empirically studying the algorithms on problems with large state spaces, for which function approximator such as DNN is required, an obvious one. This is postponed to future work as our aim was to build the mathematical foundation and conducting experiments without worrying about challenges such as the optimization a DNN. There are other algorithmic and theoretical directions to be pursued. One is exploring the space of splittings of yP" The other whether we can design Operator Splitting variants of other DP algorithms such Policy Iteration and Modified Policy Iteration, and study their convergence behaviour.
10

---

Acknowledgments and Disclosure of Funding
We would like thank the anonymous reviewers for their comments that helped improve the clarity of the paper, as well as other members of the Adaptive Agents Lab 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. AR was partially supported by Borealis AI through the Borealis AI Global Fellowship Award. 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
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning, 1198 2008. 6
Pierre-Lue Bacon. Temporal Representation Learning. PhD thesis, McGill University. 2018.
Pierre-Lue Bacon and Doina Precup. A matrix splitting perspective on planning with options. In Continual Learning and Deep Networks Workshop at NIPS. 2016.
Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
Vivek S. Borkar. Stochastic approximation: dynamical systems viewpoint. Cambridge University Press, 2008. 9
Jinglin Chen and Nan Jiang. information-theorre considerations batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019. 6
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research (JMLR), 6:503-556, 2005. 1
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning.
37v3, 2019. 6
Amir-massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. In J. Lafferty, C. K. I. Williams, J. Slawe-Taylor, R. S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems (NeurIPS 23). pages
2010. 7
Amir-massoud Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Regular- ized policy iteration with nonparametric function spaces. Journal of Machine Learning Research (JMLR), 17(139):1666 2016.
Gene H. Golub and Charles F. Van Loan. Matrix Computations. The John Hopkins University Press, 4th edition, 2013. 1,
Geoffrey Gordon. Stable function approximation in dynamic programming. In International Confer- ence on Machine Learning (ICML), 1995.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference Machine Learning (ICML), pages 267-274, 2002. 7
Harold J. Kushner and Allan J. Kleinman. Accelerated procedures for the solution of discrete Markov control problems. IEEE Transactions Automatic Control, 16(2):147-152, April 1971. 5
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 February 2015. 1

---

Thomas M. Moerland, Joost Broekens, Aske Plaat, and Catholijn M. Jonker. Model-based reinforce- ment learning: survey. arXiv:2000.1671224,, 2022. 9
Rémi Munos. Error bounds for approximate policy iteration. In Proceedings of the 20th International Conference Machine Learning (ICML), pages 560-567, 2003. 7
Rémi Munos. Performance bounds in Ly norm for approximate value iteration. SIAM Journal
Control and Optimization, pages 541-561, 2007. 7,
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research (JMLR), 9:815-857, 2008. 6
Evan L. Porteus. Bounds and transformations for discounted finite markov decision chains. Operations Research, 23(4):761-784 1975. 5
Yousef Saad. Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics (SIAM), 2nd edition, 2003. 1,3
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game of tetris. Journal Machine Learning Research (JMLR), (6(49):1629-166 2015. 7
Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, (1):9-44, 1988.
Richard S. Sutton. Integrated architectures for learning, planning, and reacting based on approxi- mating dynamic programming. In Proceedings of the 7th International Conference Machine Learning (ICML), 1990.
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2019. 2
Csaba Szepesvári. Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010. 2
Richard Varga, Matrix Iterative Analysis. Springer-Verles 2nd edition, 2000.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] In the end of Section we show
that the convergence and speed up need an accurate enough model.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] There are no immediate potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The details are in the supplementary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] The details are in the supplementary material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A] The experiments simple and can be run on a personal computer.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "urHM5sfGMa4", "reviewer": "Reviewer_rQAP", "summary": "Based on the concept of operator splitting, the authors analyzes convergence properties of value iteration with approximate dynamics models.", "questions": "Does the theory apply to continuous state-action cases?", "limitations": "Empirical evaluation is only with a simple cliff wall task.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theory looks sound.\n\nIn addition to the analysis, a new algorithm, operator splitting Dyna is proposed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hjziohKr2-6", "reviewer": "Reviewer_nqCV", "summary": "This paper considers the problem of planning in a discounted MDP when an approximate model of the dynamics is available. The author propose an algorithm that can take advantage of such model to quickly evaluate a policy or compute an optimal one. \n\nEach iteration of the value iteration algorithm can consists of solving a linear system (in discrete MDPs). In the case where two models are available, the matrix to inverse can be expressed as a difference of two matrices: one involving the approximate transition, one involving the model error. It is shown that solving the original problem is equivalent to applying value iteration in a modified MDP with the approximated dynamics, and a new reward function including the model error. \n\nA theoretical analysis of the convergence of the proposed method is provided along with some extension to a model-based reinforcement learning algorithm. \n\nExperimental results on toy problems are provided and show that the proposed method allow for faster convergence in both planning and RL settings. \n", "questions": "1. How does the state space (discrete vs continuous) affect the method? \n2. How do the experimental results look like for more extreme cases when the model is completely off?\n3. Would it be possible to get a convergence rate for OS-dyna? In terms of number of sample to reach a certain model accuracy. \n", "limitations": "As far as I understood, this method is only applicable to problem with discrete state spaces, so that the transition model can be represented as a matrix, but it is never clearly stated. The author should make mention of this limitation or clarify how continuous spaces could be handled. The operators are defined for continuous spaces (e.g. 3.3), but I don’t see how the matrix $(I – \\gamma P)$ would be represented in such case. \n\nThe authors clearly explains that the convergence rate is highly dependent on the quality of the approximate model. \n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall the paper is clearly written and easy to follow. \n\nThe idea of considering value iteration through the lens of operator splitting is very interesting and original. The derivation is mathematically correct and very well explained. \nThe main contribution is theoretical. \n\nHaving approximate model of the environment might be common in many applications. The author also show that when no model is given, but the model is learned (OS-dyna) the method still outperform existing model based RL. \n\nThe extension to model based RL and the learning of the new reward signal is very clear and a very interesting idea. \n\nIt is a bit puzzling that the convergence rate can be made faster, I wish the author added an illustrative example to get a better grasp of this in addition to theorem 2. \n\nminor weaknesses:\n- the lack of discussion about continuous state spaces. \n- The author could provide a more detailed pseudo code of the method in appendix as algorithm 1 relies on a lot of notation. \n- More discussion on how to update the model p_hat would have been useful. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "49f99oT0N-S", "reviewer": "Reviewer_2Dfm", "summary": "In this paper, the authors consider a novel Value Iteration by Operator Splitting for both Policy Evaluation and Control problems. Further, they show a faster convergence rate when the learning model is accurate compared with general RL methods with fixed $\\gamma$. Then, they give the error bound of the proposed OS-VI and develop OS-Dyna. The experimental environment is simple but effective to show the performance of OS-Dyna.", "questions": "Please see the questions in Weaknesses and the following.\n\tFor the proposed algorithm OS-Dyna, the authors claim that the operator splitting approach is a hybrid of MBRL and model-free RL. I agree with this claim. But, I think the authors should add some analysis of the proposed algorithm from the following perspectives.\n       a. Compared with the original Dyna framework, they utilize the learning dynamic model $\\hat{P}^\\pi$ to rollout virtual samplings for improving policy efficiency. How about OS-Dyna’s performance? \n       b. Compared with general model-free RL methods, like Soft-Actor-Critic, OS-Dyna utilize the learning dynamic model $\\hat{P}^\\pi$ as a reward penalty term defined in (3.3). Thus, compared with SAC's entropy policy, how does the proposed penalty term work?\n       c. Can OS-Dyna be extended in non-linear systems? Like some general technologies in RL, the authors may consider the sample-based model $\\hat{P}^\\pi$ and replay buffer to re-sample some experiences for approximately computing the term $P-\\hat{P}^\\pi$.\n", "limitations": "I think that this work would be more convincing if the authors can extend the performance of OS-VI in some complex environments due to its potential performance improvement.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\tA novel value iteration formulation to balance Dyna and MFRL.\n\tPrecise problem formulation and derivation structure;\n\tReasonable experiments and demonstratable results;\n\tClear structure and understandable writing.\n\nWeaknesses\n\tAs mentioned in 2.2, the dynamic error $e_k$ are (norm-) convergent when $\\|G\\|=\\|M^{-1}N\\|<1$. When the OS-VI method is proposed, the authors should also discuss the convergence for $M^\\pi$ and $N^\\pi$ in 3.1, even though they can only be discussed in the linear systems.\n\tIn Theorem 1, the authors give the effective discount as $\\gamma’$. I wonder that is there such a situation about $\\gamma’>1$. And, if $\\gamma’>1$, the proposed Varga operator may not be satisfied (3.2).\n\tIn the proof of Lemma 4, the authors derive $S^\\pi V_1- S^\\pi V_2$ with some doubts. In different iteration epochs, the Varga operator may correspond to the different learning dynamic model $\\hat{P}^\\pi$, i.e., \n$S^\\pi V_i = (I-\\gamma \\hat{P}_i^\\pi)(r^\\pi+\\gamma(P^\\pi-\\hat{P}_i^\\pi))$, which may result different result.\n\tIn the experiments, the authors may consider putting the smooth $\\lambda$ cases in the paper other than in the supplementary materials.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept