Deflated Dynamics Value Iteration
Authors: Jongmin Lee
Amin Rakhsha
Ernest K. Ryu
Amir-massoud Farahmand
Venue: Accepted by TMLR ()

Abstract: The Value Iteration (VI) algorithm is an iterative procedure to compute the value function of a Markov decision process, and is the basis of many reinforcement learning (RL) algorithms as well. As the error convergence rate of VI as a function of iteration $k$ is $O(\gamma^k)$, it is slow when the discount factor $\gamma$ is close to $1$. To accelerate the computation of the value function, we propose Deflated Dynamics Value Iteration (DDVI). DDVI uses matrix splitting and matrix deflation techniques to effectively remove (deflate) the top $s$ dominant eigen-structure of the transition matrix $\mathcal{P}^\pi$. We prove that this leads to a $\tilde{O}(\gamma^k |\lambda_{s+1}|^k)$ convergence rate, where $\lambda_{s+1}$ is the $(s+1)$-th largest eigenvalue of the dynamics matrix. We also extend DDVI to the RL setting and present Deflated Dynamics Temporal Difference (DDTD) algorithm. We empirically show the effectiveness of the proposed algorithms.

Published in Transactions on Machine Learning Research (05/2025)
Deflated Dynamics Value Iteration
Jongmin Lec
dluhd20000ssrruccm ac. kr
Seoul National University
Amin Rakhsha
aminn@cs. edu
Deportment of Computer Science, University of Toronto
Vector Institute.
Ernest K. Ryu University of Colifornia, Los Angeles
eryu@math. ucla. edu
A Amir-massoud Farahmand
amir onii--assoout//onnnnndddoopppppp
Polytechnique Montréol
Mila Queber AI Institude
University of Toronto
Reviewed on OpenReview: https: // // openreviee.. net/ net/forun? id- IdQTE2242
Abstract
The Value Iteration (VT) algorithm an iterative procedure to compute the value function of a Markov decision process, and is the basis of many reinforcement learning (RL) algorithuns as well. As the error convergence rate of VI as a function of iteration when the discount factor y close 1. To accelerate the computation of the value function, propose Deflated Dynamics Value Iteration (DDVT). DDVI uses matrix splitting and matrix deflation techniques to effectively remove (dellate) the top 8 dominanl eigen-structure of the transition matrix pr, We prove that this leads to a 0(771s4111)) convergence rate, where As+1 is the (s + 1)-th largest eigenvaluc of the dynamics matrix. We also extend DDVI to the RL setting and present Deflated Dynamics Temporal Difference (DDTD) algorithm. We empirically show the effectiveness the proposed algorithms.
O(r*), it is slow
1 Introduction
Computing the value function V for policy æ or the optimal value function V is an integral step of many planning and reinforcement learning (RL) algorithms. Value Iteration (V1) is a fundamental dynamic programming algorithm for computing the value functions, and its approximate and sample-based variants, such as Temporal Different Learning (Sution, 1988), Fitted Value Iteration (Ernst et al., 2005; Munos & Szepesvári, 2008), Deep Q-Network (Mnih et al., 2015), are the workhorses of modern RL algorithms (Bertsekas & Tsitsiklis, 1996; Sutton & Barto, 2018; Szepesvári, 2010; Meyn, 2022).
The VT algorithm, however, can be slow for problems with long effective planning horizon problems, when the agent has to look far into future in order make good decisions. Within the discounted Markov Decision Processes formalism, the discount factor 7 determines the effective planning horizon, with 7 closer to corresponding longer planning horizon. The error convergence rate of the conventional VI as function of the iteration k is *,)*), which is slow when is close to 1.
Recently, there has been a growing body of research that explores the application of acceleration techniques of other areas of applied math to planning and RL; Geist & Scherrer (2018); Sun et al. (2021); Ermis & Yang (2020); Park al. (2022); Ermis et al. (2021); ; Shi al. (2019) applics Anderson accelcration of fixed-point iterations, Lee & Ryu (2023) applies Anchor acceleration of minimax optimization, Vieilarr al. (2020); Goyal &
(2022); Grand-Clément (2021); Bowen et al. (2021); Akian et al. (2022) applies

---

Published in Transactions on Machine Learning Research (05/2025)
Nesterov acceleration of convex optimization, and Farahmand & Ghavamzadch (2021); Bedaywi et al. (2024) borrow ideas from control theory /engineringn specifically PID controllers, to accelerate planning and RL algorithms.
We introduce a novel approach to accelerate VI based on modification of the eigenvalues of the transition dynamics, which are closely related the convergence rate of VI. To see this connection, consider the policy evaluation problem where the goal is find the value function v for a given policy и. VI starts from arbitrary 0 and iteratively sets V +- r + +yP= where r" and p are the reward vector and the transition matrix of policy т, respectively. If V = 0, the error vector/function at iteration & is V" - Vk Ei= (1PP))r) Let us take closer look at this difference.
For simplicity, assume that pr is a diagonalizable matrix, so we can write P === UDU with U consisting of the (right) eigenvectors of pd and D being the diagonal matrix diag(A diaag(A......................... An) with 1 = A1l 2 ....2 1nx)- Since (P*y = UD'U-1, after some manipulations, we see that
(+
I-
(122)
V - vk= = U
U-1y
(rrnn)) )
1-
The diagonal terms are of the form (+Ax)* so they all converge to zero. The dominant term is (7^1)*, which corresponds to the largest eigenvalue. As the largest eigenvalue Àι of the stochastic matrix p is 1, this leads to the dominant behaviour of O))*). This is the same rate that we also get from the cruder norm-based contraction mapping analysis. The second dominant, term behaves as )(()))))**) and so on.
If we could somehow remove from P the subspace corresponding to the top s eigen-structure with eigenvalues A Aes the dominant behaviour of the new procedure would be O((rl>++1)*)) which can be much faster than O()*t) of the conventional VI. Although this is perhaps too good seem feasible, this is exactly what the proposed Deflated Dynamics Value Iteration (DDVT) algorithm achieves. Even if pa is not diagonalizablee matrix, DDVI works. DDVI is based two main ideas.
The first idea is the deflation technique, well-studied in linear algebra (see Section 4.2 of Saad 2011), that allows us to remove large cigenvalues of pr This is done by subtracting a matrix from p This gives us a "deflated dynamics" p E that does not have eigenvalues Aı,..., As The second idea is based on matrir splitting (see Section 11.2 of Golub & Van Loan 2013), which allows us to use the modified dynamics pd E to define a VI-like iterative procedure and still converge to the same solution V to which the conventional VI converges.
Deflation has been applied to various algorithms such as conjugate gradient algorithm (Saad et al., 2000), principal component analysis (Mackey, 2008), generalized minimal residual method (Morgan, 1995), and nonlinear fixed point iteration (Shroff & Keller, 1993) for improvement of convergence. While some prior work in accelerated planning can be considered as special cases of deflation (Bertsekas, 1995; White, 1963), to the best of our knowledge, this the first application of the deflation technique that climinates multiple eigenvalues in the context of RL. On the other hand, multiple planning algorithms have been introduced based the general idea of matrix splitting (Hastings, 1968; Kushner & Kleinman, 1968; 1971; Reetz, 1973; Porteus, 1975; Rakhsha et al., 2022), though with a different splitting than this work.
After a review of relevant background in Section 2, we present DDVI and prove its convergence rale for the Policy Evaluation (PE) problem in Section 3. Next, in Section 4, we discuss the practical computation of the deflation matrix. In Section 5, we explain how DDVI can be extended to its sample-based variant and introduce the Deflated Dynamics Temporal Difference (DDTD) algorithm. Finally, in Section 6, we empirically evaluate the proposed methods and show their practical feasibility.
2

---

Published in Transactions on Machine Learning Research (05/2025)
2 Background
We first briefly review basic definitions and concepts of Markov Decision Processes (MDP) and Reinforcement Learning (RL) (Bertsekas& & Tsitsiklis, 1996; Sutton & Barto, 2018; Szepesvári, 2010; Meyn, 2022). We then describe the Power Iteration and QR Iterations, which can be used to compute the eigenvalues of a matrix.
For a measurable set S2 we denote M(22) as the space of probability distributions over set Q. We use F(Ω) to denote the space of bounded measurable real-valued functions over Q. For matrix A, we use spec(A) denote its spectrum (the set of eigenvalues), p(A) to denote its spectral radius (the maximum of the absolute value of cigenvalues), and || Il to denote its 1 norm.
7), where X is the state space, A is the action space, P: &' x A M(X' is the transition probability kernel, R: X' x A - M(R) is the reward kernel, and 7 E [0, 1) is the discount factor. In this work, we assume that the MDP has a finite number of states. We use r: X' x A + R to denote the expected reward at a given state-action pair. Denote r"(x) = Eawn(-la) [r( a)]. The :: X + M(A) for a policy. We define the reward function for a policy i as r"
Markov Decision Process. The discounted MDP is defined by the tuple (X, R,
transition kernel of following policy и is denoted by p*: X - MM and is pa (a' x)) EEEN T(a x)P(a') x, a) (or an integral over actions, if the action space is continuous).
The value function for policy π is V (xxx = E. Ex 7'r(",, a.) zo - x| where E, denotes the expected value over all trajectories (Io, ao. I1, a1,...) induced by P and т. We say that V* is optimal value functions if V = sup, VT. We say x² is an optimal policy if x* E Arg max, V*.
The Bellman operator T for policy π is defined as the mapping that takes V E F(X) and returns a new function such that its value at state x (7) Eo-x((t) [r(x, a) + (V(')) The Bellman optimality operator T* is defined as (z) = supaEA fr(z, a) + (E2:-P(-1za) [=)]] The value functions 8 and V are the fixed points of the Bellman operators, that is, V" =TV= and V* = TVV*.
Value Iteration. The Value Iteration algorithm is one of the main methods in dynamic programming and planning for computing the value function V of a policy (the Policy Evaluation (PE) problem), or the optimal value function V (the Control problem). It is iteratively defined as
T T
(Policy Evaluation) (Control),
where 1/ is the initial function. For discounted MDPs where 7 < 1, the Bellman operators are contractions, so by the Banach fixed-point thcorem (Banach, 1922; Hunter & Nachtergacle, 2001; Hillen, 2023), the VI converges to the unique fixed points, which are V or V*, with the convergence rate of O(**).
Let us now recall some concepts and methods from (numerical) linear algebra, see Golub & Van Loan (2013) for more detail. For any A E Rx (not necessarily symmetric nor diagonalizable) and for any matrix norm || Il, Gelfand's formula states that spectral radius p(A) satisfies p(A) = limg- |/////// Hence, || = ((p(A) + +))²) for any e > 0, which we denote by || = Ó((p(A))*). Furthermore, if A is diagonalizable, then || = ((p(A))).
Power Iteration. Powers of A can be used to compute cigenvalues of A. The Power Iteration starts with an initial vector 80 E R= and for k 2, computes
A
b++1
A ||2
If X is the eigenvalue such that |Ail = p(A) and the other eigenvalues Ag,..., An have strictly smaller magnitude, then (b*)TAB Ab* X1 for almost all starting points 60 (Section 7.3.1 of Golub & Van Loan 2013).
QR iteration. The QR Iteration (or Orthogonal Iteration) algorithm (Golub Van Loan, 2013, Sections 7.3 and 8.2) is generalization of the Power Iteration for finding multiple eigenvalues. For any A E Çaxn let.
3

---

Published in Transactions on Machine Learning Research (05/2025)
U C have orthonormal columns and perform
zh+1 = AU
u 1ht1 = zh+1 (QR factorization)
lor k = 0,,,.... Tf [r,] > [d+til: the columns of U converge to an orthonormal basis for the dominant. s-dimensional invariant subspace associated with the eigenvalues Ap....,A; and diagonal entries of (U*)TAU* AU* converge to A1y..., A for almost all starting U (Golub & Van Loan, 2013, Theorem 7.3.1). Each QR iteration needs O(n2s) flops for its matrix multiplication, which is the dominant part of the computation, and O(ns²) flops for the QR factorization.
3 Deflated Dynamics Value Iteration
We present Deflated Dynamics Value Iteration (DDVI), after introducing its two key ingredients, matrix deflation and matrix splitting.
3.1 Matrix Deflation
Recall from the introduction that would like to remove from P the subspace corresponding to the top eigen-structure with cigenvalues . We use the so-called deflation technique to displace, and in fact remove, some of the eigenvalues of the matrix pa without changing the rest. This is done by subtracting a matrix E of a certain form from p (sce Section 4.2 of Saad 2011 for a discussion of deflation technique).
Let pd be an n X n matrix with eigenvalues A,,...,,,, sorted in decreasing order of magnitude with ties broken arbitrarily. Let T denote the conjugate transpose of u C". We describe three ways of deflating this matrix and some properties of cach approach as the following Facts.
Fact (Hotelling's deflation, Mcirovitch 1980, Scction 5.6). Assume s I n lincarly independent cigenvectors corresponding {> exist. Write {u and {u.li to denote the top right and left eigenvectors scaled to satisfy u, i. = 1 and u, u,un 0 for all S si Tf = Ei= Aaany then p(Ps F.,) [Ast1]-
Hotelling deflation makes p(p E.) small by climinating the top s cigenvalues of pa, but requires both right and left eigenvectors of pd. Wielandt's 's deflation, in contrast, requires only right eigenvectors.
Fact (Wielandt's deflation, Soto Rojo 2006, Theorem 5). Assume s S n linearly independent eigenvectors corresponding {Ai)i=1 exist. Write {ui to denote the top s linearly independent right eigenvectors. Assume that vectors {u:}; which are not necessarily the left eigenvectors, satisfy u, i and u, Uj for all 1 < i
If Ei= \wan, then p(p E.) = |d4t1l.
Wielandt's 's deflation, however, still requires right eigenvectors, which are sometimes numerically unstable compute. The Schur deflation, in contrast, only requires Schur vectors, which are stable to compute (Golub & Van Loan, 2013, Sections 7.3). For any pa E R=xn the Schur decomposition has the form p = UU where R is an upper triangular matrix with Ra >; for i= 1, n, and U is a unitary matrix. We write to denote the i-th column of U and call it the i-th Schur vector for i = I...., n. Specifically, the QR iteration computes the top s eigenvalues and Schur vectors.
Fact 3 (Schur deflation, Saad 2011, Proposition 4.2). Let S n. Write (wikin to denote the top Schur vectors. If E, = Σi= Auany, then p(P - E.)) = -1st1l-
If an E. satisfies the conditions of Facts 1, 2, or 3, we say it is rank-s deflation matria. Later, it will be needed that for E, Σi= doany T the identily
a7 (1- 1+ Σ 1 a7
(1)
should hold. Indeed, the conditions of Facts 1, 2, 3 do imply equation
4

---

Published in Transactions on Machine Learning Research (05/2025)
3.2 Matrix Splitting: Successive over-relaxation
We now describe the second key ingredient of DDVI: matrix splitting. Recall that the policy evaluation problem is the problem of finding the value function V such that T*V* = = This is in fact system of linear equations:
(I (1-P"")"'""
(2)
DDVI's approach solve this equation is based on the Successive over-relaxation (SOR) algorithm, an iterative approach to solve linear systems.
To introduce SOR in its general form, consider a matrix A E Rax* and the linear system Az = b. SOR starts by splitting A in the form of = B 3+C++ + D. D. Let a & 0. Then, z solves the linear system A= = if and only if
+ aD+ ab - (aC (a 1)D)2,
which, in turn, holds if and only if
aD (aC + (a - (a)))
provided that + a is invertible. SOR attempts to find a solution through the fixed-point. iteration
k+1 (D+aB) (aC + (a 1)D)²²)
Note that classical SOR uses a lower triangular B, upper triangular C, and diagonal D. Here, we generalize the standard derivation of SOR to any splitting A B C D.
In the case of the policy evaluation problem of equation 2, we have A = I ppp and b = r For any E E Rexn, we can consider the splitting
I I- = --pE-a(p -E)
where we chose == - = ->((p" - -E,, and D = With these choices, the SOR, iteration for PE is
vk+1 = (I- -a-y (ar" + - a1) + ox(P" -)))
(3)
Notice that Va is the fixed point of this iterative procedure: V V= (1- Ey -1 + ((1- E)), Whether these iterations converge to the fixed point, however, depends the choice of and E. As an example, for = and E = O, we recover the original VI, which is convergent with the convergence rate of ).7 Next, we propose particular choices that lead to not only convergence but acceleration.
(7
3.3 Deflated Dynamics Value Iteration
We are now ready introduce DDVI. Let E, Ei d be a rank-s deflation matrix of P satisfying one of the conditions of Facts 1, 2, 3. The SOR iteration for PE with deflation matrix Fg (cf. equation 3) is
vk+l - E..E,) + a(1-a)/+ ta -x)))))))
(4)
By benefitting from equation 1, can write it as
W = (1 -1- ak ar 407 p" Σ
Aonny Vk
1=1
pk+1= 1
a7di a77, !ni!
Wh+1
(5)
We call this method Deflated Dynamics Value Iteration (DDVI). Theorem 3.1 and Corollary 3.2 describe the rate of convergence of DDVT for PE.

---

Published in Transactions on Machine Learning Research (05/2025)
Theorem 3.1. Let be policy and let x An be the eigenvalues of p sorted in decreasing order of magnilude with lies broken arbilrarily. Let 8 S n. Let E, = Ei=1 deuzoy be a rank-s deflalion matria of pa satisfying the conditions of Facts 1, 2, or 3. For 0 < S L, DDVI equation 5 exhibits the rate"
I V 0(12 110 -
as + 0c, where
max ISISONStSSSSN {
1 - a11-a+
When a 1, we can simplify DDVT equation 5 as follows.
Corollary 3.2. In the selling of Theorem 3.1, a 1, then DDVI equation 5 simplifies to
Wh+1 =((P= - -E,) + t
8
vk+1 1+ Σ
1 - ?Ai U; Wh+1
and the the rate simplifies to | -V*--=1| = 0(17s411 110 V*Il) as k + 00.
Let us compare this convergence rate with the original VT's. The rate for Vs is O(7*), which is slow when R 1. By choosing E. to deflate the top 8 eigenvalues of pa, DDVI has the rate of 0(h7s+11)) 1*),, which is exponentially faster whenever ds+1 is smaller than The exact behaviour depends on the spectrum of the Markov chain (whether eigenvalues are close to or far from them) and the number of eigenvalues we decided deflate by Eg.
In Section 4, discuss practical implementation of DDVI based the power iteration and QR iteration and implement it in the experiments of Section 6, We find that smaller values of lead to more stable iterations when using approximate deflation matrices. We also show how we can use DDVI in the RL setting in Section 5.
This version of DDVI equation 5 applies to the policy evaluation (PE) setup. The challenge extending DDVI the Control setup is that p changes throughout the iterations, and so should the deflation matrix Fg. However, when the deflation matrix Ej can be kept constant, and we utilize this fact in Section 4.1.
4
Computing Deflation Matrix E
The application of DDVI requires practical means of computing the deflation matrix Eg. In this section, provide throe approaches as examples.
4.1 Rank-1 DDVI for PE and Control
Recall that for any stochastic x matrix, the vector 1 = [1.....1] 1]_ E R" is right cigenvector corresponding to eigenvalue 1. This allows us to easily obtain a rank-1 deflation matrix E, for pa for any policy π.
Let E₁ 1.T with e gn be a vector with non-negative entries satisfying v T 1 = 1. This rank-1 Wielandt's deflation matrix can be used for DDVI (PE) as in Scction 2, but we can also use it for the Control version of DDVI.
We define the rank-1 DDVI for Control
# max(r" + +(PP= E:) max(r" + - - (
(6)
Here, we benefitted from the fact that Ej is not a function of in order to take out of the max,- The value function V can be computed as
1+ (1+ 1--
7 --10" 10 W
(7)
The precise meaning the Ô notation is || V 0(1 =/=1/10 - V k for any

---

Published in Transactions on Machine Learning Research (05/2025)
Note that the iteration over W does not depend on Vk, do not need to compute V at each iteration only when we need it. Compared to equation 5 of DDVT (PE), we set a 1 for simplicity. We have the following guarantee for rank-1 DDVI for Control. Theorem 4.1. The DDVI for Control algorithm (equation and equation 7) exhibits the rate
2
~ VI | V
for k = 00, l.... Furthermore, if there ezist a unique optimal policy x², then
| VTl - -1 V*ll)
as > 00, where X2 is the second eigenvalue of pp"" (The Ô notation is as defined in Theorem 3.1).
Discussion. Although rank-1 DDVI for Control does accelerate the convergence V + V*, subtle point to note is that the greedy policy x² obtained from v is not affected by the rank-1 deflation. Briefly speaking, this is because adding constant to V through 1 has no effect the arg max computation used in the greedy policy. Indeed, the maximizer *4+1 in equation 6 is the same as arg max, produced by the (non-deflated) value iteration, when W = Vo, Having the term v 11k in the update Wh+1 rx + >(px** v I)W* adds the same constant to all states, so does not change the maximizer of the next policy.
(r" >P*V*,,
4.2 DDVI with Automatic Power Iteration
According to Fact 2, we can construct the defiation matrix Eg for P we have its top s right eigenvectors. The top eigenvector "
known, which as we saw in Section 4.1, gives Ej and rank-1 DDVL. We show that we can start with 1 and run rank-1 DDVI, and using the calculations already done in DDVI updates, estimate the next top eigenvectors and increase the deflation rank.
Assume that the top Let E, = Eiz Nu be rank-s deflation matrix of Pe, as in Fact 2. Consider the DDVI algorithm in equation 5 with a = 1 as in Corollary 3.2. If V = 0, since
eigenvalues of pa have distinet magnitude, i.e., = A1 11 >..>> Dotta
(p* - FF) (T- =p" F,
(verified as equation 10 in Appendix B), we have
W (p" Eg)²r
Therefore, + (W*+1_ Why E.) fd is the iterates of power iteration for the matrix (P E.) starting from initial vector ,=, As discussed Fact 2, the top eigenvalue of (P* - -2) is A For large [[FFI--FTT R w, where is the top eigenvector of (pT -E). With w, we recover the (s + 1)-th right eigenvector of pd through the formula (Bru et al., 2012, Proposition 5)
k we expect w wt
AR w A Ast1 U4
Us+1
w
Leveraging this observation, DDVI with Aulomalic Power Ieraaion (AutoPI) computes an approximate rank-s deflation matrix E, while performing DDVI: Start with a rank-1 deflation matrix, using the first right
eigenvector i = 1, and carry out DDVI iterations. If a certain error criteria is satisfied, use W W approximate the second right eigenvector ug. Then, update the deflation matrix to be rank 2, and gradually increase the deflation rank. We formalize this approach in Algorithm 1.
7

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm DDVI with AutoPI
1: Initialize C,C
For example, C 10, c c 10 10-4
2: function DDV V,, K, (Ar) (wi)i=1)
VO c= 0, E.
Ei= /edyy as Fact 2
for 0,..., K do
5:
if c 2 C' and
|
w k+1
1 2
ve
<6 then
die, w+t1 w+1 1--2o-1
As+1 (w*) /w (7/1/>* [š), us+1 w Li=l
7:
Return (DVI(s+ (111, V. -c, { A= (2:
8:
else
9:
Wh+1 = 7(px E, VR + トr, Vk+1 = (I (I--E,)-1
10:
wh11 Whit Wi w = W Wk-1
11:
c=c+1
Return VK
12:
13:
Initialize V and 21 =1 \1 =1
14:
DDVT(1, Vo, K,)
4.3 Rank-s DDVI with the QR Iteration.
Recall that the QR iteration approximates top Schur vectors. Algorithm 2 uses the QR Iteration to construct the rank-s Schur deflation matrix and performs DDVT. Compared to the standard VI, rank-s DDVT requires additional computation for the QR iteration.
Algorithm Rank-s DDVI with QR Iteration
Initialize a, and 0 {>:)i=1> 1i = (Pitteration(P...
for O,..., do
Wh+1 (P Σi= A V (1 a)vk arr
ard; ph+1 [ Ei= 1-a7d; u.u.) wh+t
The QR iteration of Algorithm 2 can be carried out in automated manner similar to AutoPI. We refer to this AutoQR and formally describe the algorithm in Appendix C.
5 Deflated Dynamics Temporal Difference Learning
Many practical RL algorithms such as Temporal Difference (TD) Learning (Sutton, 1988; Tsitsiklis & V. Roy, 1997), Q-Lerrning (Watkins, 1989), Fitted Value Iteration (Gordon, 1995), and DQN (Mnih et al,, 2015) can be viewed as sample-based variants of VI. Consequently, the slow convergence in the case of y = 1 has also been observed for these amss by Szepesvári (1997); Even-Dar & Mansour (2003); Wainwright (2019) for TD Learning and by Munos Szepesvári (2008); Farahmand et al. (2010); Chen Jiang (2019); Fan et al. (2020) for Fitted VI and DQN. Here we introduce Deflated Dynamics Temporal Difference Learning (DDTD) as a samplo- based variant DDVL. To start, recall that the tabular temporal difference (TD) learning performs the updates
v*+I(X)) (*x)) + Th (XA)) TV (XX) V* (X+)),
where m) (Xx)) is a state-dependent stepsize, (X,XX are random samples from the environment such that X is the subsequent state following Xg, and r5 (X₂) is the expected immediate reward obtained by following
policy æ from state Xg. In practice, we may choose state-independent my (Xx)) = me, which would still result in convergence to the true value function if each state is visited often enough.
8

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm Rank-s DDTD with QR iteration
Initialize a, 8, W, V, Es. P", and K
2: for == 1,..... do
3: Choose X5 uniformly at random.
4: Sample (Txx),, (xX,),,,,,,, Rx, from environment
5: Update P with (X,,,((X)) Ra, x²)
6: if k mod K = then
7:
{A (us = QRiteration Update E, + Eyuu
8:
W + (I-an) ovE.)V
+1 (1-a) (Xx)) t (XXx) (xxx)) aRR + -0-- w(x))
10:
11: V I+ Ei= ond unu W
TD is a sample-based variant of VI for PE. Two key ingredients of TD learning are the random coordinate updates and the lemporal difference error (X) + +X") V(X), whose conditional expectation equal to V - V)(X). Applying the same ingredients to DDVI, we obtain DDTD. The improved convergence rate for DDVI compared to VI suggests that DDTD may also exhibit improved convergence rates.
Specifically, we define DDTD as
wh+ (Xx) (Xx) + Th
a
w* w*(x)
andi ayλ;
pk-1= 1+1
n.o Wh+1
(8)
where E, = -i= Auu;y is a rank-s deflation matrix of p and XK,Xigha Xihho,,,,... are i.i.d. random variables such that X ~ (k) and X2 ~ Unif(X). The -utd-up notation means Wk+1 = W*(x) for all
x + Xx.
DDTD the sample-based variant of DDVI performing asynchronous updates. The following result provides almost sure convergence of DDTD.
Theorem 5.1. Let m (x) = EE 1x,=)) when X = x. For a = 1, DDTD equation converges to V
almost surely.
The following result describes the asymptotic convergence rate of DDTD.
Theorem 5.2. Let . An be the eigenoulue of px sorted in decreasing order of magnilude with lies broken arbitrarily. Let mx(x)) = C((k+1) with the constant C > For a= DDTD equation 8 ezhibits the rate EillV* V = =Ok-1))
2Apero' where ADDTD = minxe Re( - >A).
n
We note that in Theorem 5.2, as the rank of DDTD increases, ADDTD also increases, and this implies that higher rank DDTD has a larger range of convergent step size compared to the plain TD learning.
5.1 Implementation of DDTD
To implement DDTD practically, we take a hybrid of model-free and model-based approach for obtaining Eg. At each itcration, the agent uses the new samples update an approximate model pn of the truc dynamics. This updated approximate model is used to compute E,. We update E, every K-th iterations since the change in TT and consequently the resulting E, at each iteration is small. Whenever new E, is computed, we set W to be (T a7-ayy,)1 This step ensures that V smoothly converges to /" by updating all coordinates of W at once based on new Eg. Also, we use the random sample reward R in place of the expected reward nd (Xx). We formally state the algorithm as Algorithm 3.
We note that DDTD simultancously uses samples to learn the model and to update the value function, making the DDTD framework more effective than model-free learning and more computationally efficient. than purely model-based approach.
9

---

Published in Transactions on Machine Learning Research (05/2025)
10"
109
Normalized I|V* v*Il
10
10 1
10-2
10-2
DDVI (AutoQR)
DDVI (AutopI)
10-3
10-a
DDVI (rank-1)
Normalized
DDVI (rank-2)
10-1
10-1
DDVI (rank-3)
DDVI (rank-4)
10a1
10-1
VI
10-4
10-4
0
200
400
600
800
1000
200
400
600
800
1000
Iterations (k)
Iterations (k)
Figure 1: Comparison of DDVI with different ranks, AutoPI, and AutoQR against VI in (left) Maze and (right) Chain Walk. The plots for DDVI do not start at ileration O because the costs of computing E, through QR iterations are incorporated as rightward shifts. Rate of DDVI with AutoPI and AutoQR changes when E, is updated.
6 Experiments
For our experiments, we use the following environments: Maze with 5 x states and 4 actions, Cliffwalk with 7 states with actions, Chain Walk with 50 states with 2 actions, and random Garnet MDPs (Bhatnagar et al., 2009) with 200 states. The discount factor is set to 7 = 0.99 for the comparison of DDVI with different ranks and the DDTD experiments, and 7 0.995 in other experiments. Appendix D provides full definitions of the environments and policies used for PE. All experiments were carried out on local CPUs. We report the normalized error of y defined as | - V/ |//|//|| 11.
DDVI with AutoPI, AutoQR, different fixed ranks. In Figure 1, we compare rank-s DDVI for multiple values of a and DDVI with AutoPl and AutoQR against the VI in Chain Walk and Maze. In our plots, we incorporate the cost of the QR iteration for a fair comparison. We consider the cost of a QR iteration to be msC where m is the number of QR iterations we applied, is the rank of DDVT, and C is the cost of VI per iteration, and plot rank-s DDVI starting from ms itcrations in Figures 1. In this experiment, QR ileration (Section 2) is used 100 times to calculate E, with Schur vectors. In almost all cases, DDVI exhibits a significantly faster convergence rate compared to VI. Aligned with the theory, we observe that higher ranks achiove better convergence rates. Also, as DDVI with AutoPI and AutoQR progress and update Eg, their convergence rale improves.
DDVI and other basclines. We perform an extensive comparison of DDVI against the prior accelcratod VI methods: Safe Accelerated VI (S-AVI)(Goyal & Grand-Clémmntt, 2022), Anderson VI (Geist & Scherrer, 2018), PID VI (Farahmand & Ghavamzadeh, 2021), and Anchored VI (Lee & Ryu, 2023). In this experiment, we use the Implicitly Restarted Arnoldi Method (Lchoucq et al., 1998) from SciPy package to calculate the eigenvalues and eigenvectors for DDVI. Figure 2 (top-left) shows the convergence behaviour of the algorithms by iteration count in 20 randomly generated Garnet environments, where our algorithms outperform all the baselines. This comparison might not be fair as the amount of computation needed for each iteration of algorithms not the same. Therefore, in Figure (top-right), we compare the algorithms by wall clock time. It can be seen that rank-2 DDVT initially has to spend time caleulate E, before it starts to update the value function, but after the slow start, it has the fastest rate. The fast rate compensate for the initial time if a high accuracy is needed. DDVI with AutoQR and rank-1 1 DDVI show a fast convergence from the beginning.
We further investigate how the algorithms scale with the size of MDP and the discount factor. Figure 2 (bottom-left) shows the runtime to reach a normalized error of 4 as a function of the number of states.
TThe source code for the experiments can found at https://github con cww.:/ib.coo//aaat/eeeeee wwtp:///apptiie-aaaeee-aaaaaa aggnts-lab/daat
10

---

Published in Transactions on Machine Learning Research (05/2025)
10"
10
Normalized [[V - v"Ih
Normalized ||Ve valb
10-2
10-2
10
10
10
10-4
10-a
10-10
10-10
Anderson VI
200
400
600
800
1000
50
100
150
200
250
Iterations (k)
Wall Clock (ms)
S-AVI
1000
250
Anchored VI
DDVI (AutoQR)
Wall Clock (ms)
800
Wall Clock (ms)
200
DDVI (rank-1)
DDVI (rank-2)
600
150
400
100
200
50
0
200
400
600
800
1000
200
400
600
800
1000
Number of States
Horizon (1/(1 /))
Figure 2: Comparison DDVI with other accelerated VIs. Normalized errors are shown against the iteration number (top-left) and wall clock time (top-right). Runtimes to reach normalized error of 10-4 is shown against the number of states (bottom-left) and horizon 1/(1 -) (bottom-right). Plots average of 20 randomly generated Garnet MDPs with shaded areas showing the standard error.
DDVI with AutoQR and rank-1 DDVI show the best scaling. Note that even rank-2, for which the calculation of E, is non-trivial, also scales competitively. Figure (bottom-right) show the scaling behaviour with horizon of the MDP, which is 1/(1 7).. We mcasure the runtime to reach normalized error of 10-4 for the horizon ranging from 100 to 1000 which corresponds to y ranging from 0.99 to 0.999. Remarkably, DDVI algorithms have low constant runtime with long horizon tasks with 1. This is aligned with theoretical result, as the rate >/4+tal remains small as approaches 1.
Rank-s DDTD with QR iteration. We compare DDTD with TD Learning and Dyna (Sutton, 1990; Peng & Williams, 1993) which simultaneously use samples to learn the model and to update the value function. For the sake of making the setting more realistic, we consider the case where the approximate model P cannot exactly learn the true dynamics. Figure 3 shows that DDTD with large enough rank can outperform TD. Note that unlike Dyna, DDTD does not suffer from model error, which shows that DDTD only uses the model for acceleration and is not pure model-basse algorithm.
7 Conclusion
In this work, we proposed framework for accelerating VI through matrix deflation and matrix splitting. We theoretically analyzed the proposed methods, DDVI and DDTD, and presented experimental results showing speedups in various setups. The positive experimental results demonstrate that matrix deflation to be a promising technique that may be applicable to a broader range of RL algorithms.
One direction of future work to extend the theoretical analysis DDVI for Control using a general rank-s deflation matrix. Theoretically analyzing other RL methods combined with matrix deflation is another
11

---

Published in Transactions on Machine Learning Research (05/2025)
1.0
Normalized I|V 1al
0.8
Normalized [|V
Dyna
0.6
0.6
TD Learning
DDTD (rank-1)
0.4
0.4
DDTD (rank-2)
DDTD (rank-3)
0.2
(rank-4)
Ok
5k
10k
15k
20k
Ok
5k
10k
15k
20k
Environment Samples (t)
Environment Samples (t)
Figure 3: Comparison DDTD with QR. iteration, Dyna, and TD learning in (left) Chain Walk (right) Maze.
interesting direction. Another direction is incorporating the DDVT framework with function approximator, such deep neural network, to handle large-scale continuous state and action spaces.
Acknowledgments
We thank the anonymous reviewers, the action editor, as well the members of the Adaptive Agents (Adage) Lab, in particular Tyler Kastner, for their constructive feedback. JL and EKR were supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government. NN..BS-2024-004222033) AMF acknowledges the funding from the Natural Sciences and Engineering Research Council of Canada (NSERC) through the Discovery Grant program (2021-03701). Resources used in preparing this rescarch were provided, in part, by the Province of Outario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.
References
M. Akian, S. Gaubert, Z. Qu, and O. Saadi. Multiply accelerated value iteration for non-symmetric affine fixed point problems and application to Markov decision processes. SIAM Journal on Matriz Analysis and Applications, (3(1):199-233 2022. 1, 16
D. Andre, N. Friedman, and R. Parr. Generalized prioritized sweeping. Neural Information Processing Systems, 1997. 16
M. Azar, R. Munos, M. Ghavamzadeh, and H. Kappen. Speedy Q-learning, Neural Information Processing Systems, 2011.
P. Bacon. Temporal Representation Learning. PhD thesis, McGill University, 2018. 16
P. Bacon and D. Precup. matrix splitting perspective on planning with options. arXic:1612.00916. 2016.
S. Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta. Mathematicae, 311):133-181, 1922. 3
M Bodaywi, A Rakhsha, and A-m Farahmand. PID accelerated temporal difference algorithms. Reinforcement Learning Journal, 5:2071 2095, 2024.
D. P. Bertsekas. Generic rank-one corrections for value iteration in markovian decision problems. Operalions
research letees, 1113)1111-119, 1995. 2, 16
D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamnic Progromming. Athena Scientific, 1996. 1, 3
12

---

Published in Transactions on Machine Learning Research (05/2025)
J. Bhandari, D. Russo, and R. Singal. Conference on learning theory. 2018. 17
S. Bhaanagar, R. S. Sutton, M. Ghavamzadeh, and M. Lee. Natural actor critic algorithms. Aulomalica, 45 (11):2471-244) 2482, 2009. 10, 27
V. S. Borkar. Asynchronous stochastic approximations. STAM Journal Control and Oplimization, 36(3): 840 100-851, 1998. 17
V. S. Borkar and Sean P Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447 469, 2000. 17, 20
W. Bowen, X. Huaqing, Z. Lin, L. Yingbin, and Z. Wei. Finito-time thcory for momentum Q-lcarning. Conference Uncertainty in Artificial Intelligence, 2021. 1, 16
R. Bru, R. Canto, R. L. Soto, and A. M. Urbano. A Brauer's theorem and related results. Central European Journal of Mathematics, 10:312 321, 2012. 7, 24
J. Chen and N. Jiang. Information-theoretiee considerations in batch reinforcement learning. In International Conference Machine Learning, 2019. 8
S. Chen, A. Devraj, A. Busic, and S. Meyn. Explicit mean-square error bounds for Monto-Carlo and linear stochastic approximation. International Conference on Artificial Intelligence and Statistics, 2020. 17,
Z. Chen, S. T Maguluri, S. Shakkottai, and K. Shanmugam. A Lyapunov theory for finite-sample guarantees of markovian stochastic approximation. Operations Research, 2023. 17, 22
P. Dai, D. Weld, and J. Goldsmith. Topological value iteration algorithms. Journal of Artificial Intellignnce Research, 42:181-208 2011. 16
G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor. Finite sample analyses for TD (0) with function approximation. Association for the Advancement of Artificial Intelligence, 2018. 17
A. M. Devraj and S. P. Meyn. Q-lcarning with uniformly bounded variance. IEEE Transactions on Automatic Control, (7(1))55948 1965999966369---- 2021. 16
M. Ermis and I. Yang. A3DQN: Adaptive Anderson acceleration for deep Q-networks. IEEE Symposium Series Computational Intelligence, 2020. 1, 16
M. Ermis, M. Park, and I. Yang. On Anderson acceleration for partially observable Markov decision processes.
IEEE Conference on Decision and Control, 2021. 1, 16
D. Ernst, P. Geurts, and L. Wehenkel. Treo-based batch mode reinforcement learning. Journal of Machine Learning Research, 2005. 1
E. Even-Dar and Y. Mansour. Learning rates for Q-learning. Journal of Machine Learning Research, 2003. 8
J. Fan, Z. Wang, Y. Xie, and Z. Yang. thcoretical analysis of deep Q-lcarning. Learning for dynamies and control, 2020. 8
A-m Farahmand and M. Ghavamzadeh. PID accelerated value iteration algorithm. International Conference on Machine Learning, 2021. 2, 10, 16, 27
A-m Farahmand, R. Munos, and Cs. Szepesvári. Error propagation for approximate policy and value iteration.
Neural Information Processing Systems, 2010. 8
M. Geist and B. Scherrer. Anderson acceleration for reinforcement learning. European Workshop on Reinforcement Leurning, 2018. 1, 10, 16
G. H. Golub and C. F. Van Loan. Matriz Computations. The John Hopkins University Press, 4th edition, 2013. 2, 4, 16
13

---

Published in Transactions on Machine Learning Research (05/2025)
G. Gordon. Stable function approximation in dynamic programming. International Conference Machine Learning, 1995. 8
V. Goyal and J. Heand-Clément. A first-order approach to accelerated value iteration. (122551775535 2022. 1, 10, 16, 28
Operations Research,
J. Srand-Clément From convex optimization to MDPs: A review of first-order, second-order and quasi-newton methods for MDPs. (XXx:21044116677 2021. 1, 16
Gupta, R. Jain, and P. Glyun. An empirical algorithm for relative value iteration for average-cost MDPs. TEEE Conference on Decision and Control, 2015. 16
N. A. J. Hastings. Some notes dynamic programming and replacement. Journal of the Operational Research Sociely, 19:453-464, 1968. 2, 16
T. Hillen. Elements of Applied Functional Anolysis. AMS Open Notes, 2023.
J. K. Hunter and B. Nachtergaele. Applied analysis. World Scientific Publishing Company, 2001.
T. Jaakkola, M. Jordan, and S. Singh. Convergence of stochastic iterative dynamic programming algorithms. Advances in neural information processing systems, 1993. 17
Kushner and A. Kleinman. Numerical methods for the solution of the degenerate nonlinear elliptic equations arising in optimal stochastic control theory. IEEE Transactions on Aulomalic Control, 1968. 2, 16
H. Kushner and A. Kleinman. Accelerated procedures for the solution of discrete Markov control problems. IEEE Transactions on Automatic Control, 1971. 2, 16
M. G. Lagoudakis and R. Parr. Least-squares policy iteration. Journal of Machine Learning Research, 2003. 27
C. Lakshminarayanan and C. Szepesvari. Lincar stochastic approximation: How far docs constant step-size and iterate averaging go? International Conference on Artificial Intelligence and Statistics, 2018. 17
J. Lee and E. K. Ryu. Accelerating value ileration with anchoring. Neural Information Processing Systems, 2023. 1, 10, 16
R.B. Lehoucq, D.C. Sorensen, and C. Yang. ARPACK Users' Guide: Solution of Large-scale Fägenvalue Problems with Implicitly Restarted Arnoldi Methods. Society for Industrial and Applied Mathematics, 1998.
L. Mackey, Deflation methods for sparse PCA. In Newral Information Processing Systems, 2008. 2, 16
H. B. McMahan and G. J. Gordon. Fast exact planning in Markov decision processes. International Conference on Automated Planning and Scheduling, 2005. 16
L. Meirovitch. Compulational methods in struclural dynamics. Springer Science & Business Media, 1980. 4,
16
S. Meyn. Control Systems and Reinforcement Learning. Cambridge University Press, 2022. 1,
V. Mnih, K. Kavukeuoglu, D. Silver, A. A. Rusu, and et al. Human-level control through deep reinforcement learning. Nature, 518(7544)::59--53 533, 2015. 1,
A. W. Moore and C. G. Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine Learning, 1993. 16
R. B. Morgan. A restarted gmres method augmented with eigenvectors. SIAM Journal on Matriz Analysis and Applications, 15(4):11541117) 1995. 2, 16
14

---

Published in Transactions on Machine Learning Research (05/2025)
R. Munos and Cs. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008. 1, 8
M. Park, Shin, and Yang. Anderson acceleration for partially observable Markov decision processes: A maximum entropy approach. arXiv:2211. 14998, 2022.
J. Peng and R. J. Williams. Efficient learning and planning within the Dyna framework. Adaptive Behavior, 1(4):437-454, 1993. 11, 16
E. L. Porteus. Bounds and transformations for discounted finite markov decision chains. Operations Research, 23(4):761 784, 1975. 2, 16
A. Rakhsha, A. Wang, M. Ghavamzadeh, and A-m Farahmand. Operator splitting value iteration. Newral Information Processing Systems, 2022. 2, 16, 27, 28
D. Reetz. Solution markovian decision problem by successive overrelaxation. Zeitschrift für Operations Research, 17:29-32, 1973. 2, 16
Y. Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011. 2, 4, 16, 25
Y. Saad, M. Young, J. Erhel, and F. Guyomarc'h. A deflated version of the conjugate gradient algorithm.
SIAM Journal on Scientific Computing, (1)51:190 1926, 2000. 2, 16
H. Sharma, M. Jafarnia-Jahromi, and R. Jain. Approximate relative value learning for average-reward continuous state mdps. Uncertainty in Artificial Intelligence, 2020. 16
W. Shi, S. Song, H. Wu, Y. Hsu, C. Wu, and G. Huang. Regularized Anderson acceleration for off-policy deep reinforcement learning. Neural Information Processing Systems, 2019. 1, 16
G. M. Shroff and H. B. Keller. Stabilization of unstable procedures: the recursive projection method. STAM Journal numerical analysis, 30(4):1099 1120, 1993. 2, 16
A. Sidford, M. Wang, X. Wu, and Y. Yc. Variance reduced value itcration and faster algorithms for solving Markov decision processes. Naval Research Logistics, 70(5):423-44) 4422244,,, 2023.
R. L. Soto and O. Rojo. Applications of Brauer theorem in the nonnegative inverse eigenvalue problem. Linear algebra and its applications, 416(2-3):844 856, 2006. 4
K. Sun, Y. Wang, Y. Liu, B. Pan, S. Jui, B. Jiang, L.. Kong, et al. Damped Anderson mixing for deep reinforcement learning: Acceleration, convergence, and stabilization. Newral Information Processing Systems, 2021. 1, 16
R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 1988. 1, 8
R. S. Sutton. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In International Conference on Machine Learning. 1990.
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. 1,
Cs. Szepesvári. The asymptotic convergence-rate Q-learning. Neural Information Processing Systems, 1997. 8
Cs. Szepesvári. Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010.
J. N. Tsitsiklis and B. V. Roy. An analysis of temporal difference learning with function approximation. IEEE Trunsactions on Aulomatic Control, 1997. 8
N. Vieillard, B. Scherrer, O. Pietquin, and M. Geist. Momentum in reinforcement learning. International Conference Artificial Intelligence and Statistics, 2020. 1, 16
15

---

Published in Transactions on Machine Learning Research (05/2025)
M. J. Wainwright. Stochastic approximation with cone-contractive operators: Sharp exe -bounds for Q-learning. or (eXxx:9950062600 2019. 8
C. J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, University of Cambride, 1989. 8
D. J. White. Dynamic programming, markov chains, and the method of succossive approximations. J. Math. Anal. Appl, 6(3):373 376, 1963. 16
D. Wingate, K. D. Seppi, and S. Mahadevan. Prioritization methods for accelerating MDP solvers. Journal of Machine Learning Research, 2005. 16
A Prior Works
Acceleration in RL. Prioritized sweeping and its several variants (Moore & Atkeson, 1993; Peng & Williams, 1993; McMahan & Gordon, 2005; Wingate et al., 2005; Andre et al., 1997; Dai al., 2011) specify the order of asynchronous value function updates, which may lead to accelerated convergence to the true value function. Speedy Q-lcarning (Azar al., 2011) changes the update rule of Q-lcarning and employs aggressive learning rates lo accelerate the convergence. Sidford et al. (2023) accelerate the compulation of Pryk by sampling it with variance reduction techniques.
Recently, there has been a growing body of research that explores the application of accelcration techniques of other areas of applied math to planning and RL: Geist & Scherrer (2018); Sun et al. (2021); Ermis & Yang (2020); Park al. (2022); Ermis al. (2021); Shi al. (2019) apply Anderson acceleration of fixed-point iterations, Lee & Ryu (2023) apply Anchor acceleration of minimax optinization, Vieillard et al. (2020); Goyal & Nesterov acceleration of convex optimization, and Farahmand & Ghavamzadeh (2021) apply ideas inspired by PID controllers in control theory.
(2022); Grand-Clément (2021); Bowen et al. (2021); Akian et al. (2022) apply
Specifically, regarding the variants of VI used in our experiments, S-AVI (Goyal & Grand-Clément Clément, 2022) exhibits ((1))) )-ate where 7s satisfies 7 S 7/s S 1, PID VT (Farahmand & Ghavamzadeh, 2021) exhibits a guaranteed O ((XE))))
k)
rate under reversible MDP (and possibly faster, depending on the MDP),
and Anchored VI (Lee & Ryu, 2023) exhibits O (ir 1 --1))1+22-> rrae in terms of Bellman error.
(1)11) 1-ghts
Matrix deflation. Deflation techniques were first developed for eigenvalue computation (Meirovitch, 1980; Saad, 2011; Golub & Van Loan, 2013). Matrix deflation, eliminating top eigenvalues of a given matrix with leaving the rest of the cigenvalues untouchod, has been applied to various algorithms such as the conjugate gradient algorithm (Saad et al., 2000), principal component analysis (Mackey, 2008), the generalized minimal residual method (Morgan, 1995), and nonlinear fixed-point iteration (Shroff & Keller, 1993) to improve the convergence.
Some prior work in RL has explored subtracting constants from the iterates of VI, resulting in methods that resemble our rank-1 DDVI. For discounted MDP, Devraj & Meyn (2021) propose relative Q-learning, which can roughly be seen as the Q-learning version of rank-1 DDVI for Control, and Bertsekas (1995) proposes an extrapolation method for VI, which can be seen as rank-1 DDVT with Schur deflation matrix for PF. White (1963) introduced relative value iteration in the context of undiscounted MDP with average reward, and several variants were proposed (Gupta et al., 2015; Sharma al., 2020).
Matrix splitting of value iteration. Matrix splitting has been studied in the RL literature to obtain acceleration. Hastings (1968) and Kushner & Kleinman (1968) first suggested Gausss-Seidel itcration for computing value function. Kushner& & Kleinman (1971) and Reetz (1973) applied Successive to VI and generalized Jacobi and Traus--Sedde iterations. Porteus (1975) proposed several transformations of MDP that can be seen as a approximate dynamics. Bacon & Precup (2016); Bacon (2018) analyzed planning with options through the matrix splitting perspective.
variant of VI. Rakhsha et al. (2022) used matrix splitting with the
16

---

Published in Transactions on Machine Learning Research (05/2025)
Convergence analysis of TD learning Jaakkola et al. (1993) first proved the convergence of TD learning using the stochastic approximation (SA) technique. Borkar & Meyn (2000); Borkar (1998) suggested ODE- based framework to provide asymptotic convergence of SA including TD learning with an asynchronous update. Lakshminarayanan & Szepesvari (2018) study linear SA under i..d. noise with respect to mean square error, and Chen al. (2020) study asymplotic convergence rate of linear SA under Markovian noise. Finite-time analysis of TD learning was first provided by Dalal et al. (2018) and extended to Markovian noise setting by Bhandari et al. (2018). Leveraging Lyapunov theory, Chen al. (2023) establishes finite-time analysis of Markovian SA with an explicit bound.
B Proof of Theoretical Results
We prove the theoretical results in this appendix.
B.1 Proof of Theorem 3.1
By the definition of DDVT (equation 4) and the property of fixed point V*, which satisfies V (T
aar") + ((1-a) a7 E)) as mentioned in Section 3.2, we have
yb - - =
(I - B.) [1- - (P" E.)l (V--1- -V7)-
-v*) = (1 (1- [(1-a) ((1-)))) - a. ay E.)(1 - ay ((1 (1--a) + an - E.) V*),
- E.) -1 ([1-a)(1 - ay + ay(P" E.)(1 ayE,) ((1-a)1 +n - -
where Eg is a rank-s deflation matrix of p satisfying the conditions of Facts 1, 2, 3. This implies that
I v"I s -o)) an(p" - E) E)) | - V*ll.
(9)
for some constant C' E R.
First, suppose F, satisfies Facts 1 or 2. Let U. = [u], [ui....,, us] and V, = [v,,...,,.] Define De.((h)) for some function f. Then U.. V,, Da,((A)) are x 8 matrices and E, = U. U.D.,A. V.T. By Jordan decomposition, p = UJU-1 where J is Jordan matrix with Jn = A for i= 1,..., n. Let J. be s submatrix of J satisfying (Ja)sj = Jig for 15 i,j S s. Then, by condition of Theorem 3.1, DaAA.s and the i-th column of is u, for 1 Sissa s. By simple calculation, we get PTU,- U,J. U.D.,,. and (I - ayE,) I U,D
J.
Ta VT.
Since
(p" - U.D.,,, V. (U,D
Tad, V, U.D.,, D 30d7
Tad, V. U.D.As D T0 VT J0d7
= 0,
we get
-p=-E.)( - px E..
(10)
Then, the term on the right-han hand side (RHS) of equation 9 can be written
(1 aT oxE tyypp" - -
(1 (1-a) a) 1+U,D
v.T) azy (UJU- -U.DaM..
Jady T
(1 (1-o) o) + UU U.D
Our (1 1)TaP,, VT I=70t
U (1- agy De
(pr Uru V. U-1 T
17

---

Published in Transactions on Machine Learning Research (05/2025)
where e, R" is the i-th unit vector and C1:s [ei...., Es], and (1 a:] an. + C1:DD Aeg-1 V. is 1-xnn;
an upper triangular matrix with diagonal entries (1-a) (1-a) 1 1-md,, (1 a) + ayydst,...... (1 - a.) + an2n.
Now suppose E, = Ei= A satisfies Fact 3. Similarly, let U, [u,...., Uz]. Then, E, U,D U.T By Schur decomposition, pa = URUT where R is upper Iriangular matrix with R2 X for i= ,,..., n1 and U is unitary matrix. By simple calculation, we have P=U, = UgR, where R. is the s x submatrix of R such that (Ra)iz = Ra for 1 I i,j S 8 and (T (T-a I U.D. U..
Since
-U,DDDa
U = U,R.D_
U. - -UDDAAD D
U.
T-
::T=yax
7o T-
= -U, - -D rad1 U.,
we get
(p" - [p)(= E,E = (p" U.D. U.(
rar U,) TI10A
= =P"" -P" U + UU..R. - De,, D U
5, 1-7
Then,
(1 -1-00 (1-a) ar,,)= + a2(P=-E,)(L - -
= (1 a) + (1 - DDU,D, 4i yuus
U. + +OTRRUT - -r,,De. + -R7U,(Rs-DD) -
7adt U g0
(1 T) RRU +U.
D
(larnnd I-70A
Da,ards og(R, Ds,A:) D.
U
Tacks
(1 a) + URU +U, DONTT-DTOP I-90di
+ay(Bs DA,)D
U, I
Juds
(1 a) + URU + U.R 8, 1-701_
10022 U
=U =U (1- + R + 6 (np Deaa Tad,
Clus UT.
Aog-11o2s is X s upper triangular matrix with diagonal entries where R 8, J0d7
(A1--1)a
(
1-70d1
1-7ad,
satisfying R (17-11792 D Un Coe.RR.DD...... Tud,
By simple calculation, we know that (1
a) a) R - eIe is upper triangular matrix with diagonal entries Judr
(1-a)
(1-a)
(1-
I-o7A1
I
a) + aod (1 a) + andn-
Therefore, by spectral analysis, we conclude that
|| - V7I
100 V*I))
as k 00, where
A =
max Isis
||1 11-a
1 - a
B.2 Proof of Collorary 3.2
Putting 1 in Theorem 3.1, we conclude Corollary 3.2.
18

---

Published in Transactions on Machine Learning Research (05/2025)
B.3 Proof of Theorem 4.1
By the definition of DDVI for Control (equation 6 and equation 7),
Vh - = (1 { - (w - (1 -1-1)) V*),
where E = 1... Let W = (I - -1E V*. Note that
max fr + +>(p== B = max + +7(p== - EijV"} max + >/P=V= - -vEiV*
W*
Thus,
W W* = =7(0%, F1) W 70 y (pr -Fi) W p""
Fi)
where "y arg max frr + 7(p= Ei) Ei) and x* is an optimal policy. Then, by the definition of greedy policy, we have
7 (pD' -Fi) W - -- ST - (W) - W*) 7 (P= -i) Wk-1 + ~
7 - Wk + nT ? (p" -Ei) ) W - -r" 21 (p=' - -Ei) (WA-1- - W*).
E1)
This implies that
Wh - W ~ - Fi) (W) - -Wa,,
W - W 27 (pe' - Ei (W - W")
and
ypa (W=-1_ w*) S w W 7 W S 7P* - Wo).
Then, there exist S 44 S 1 such that
(77p=* (W (Wh-1-W*)) W*)), (1 - (4)
-W)) (w - W* + FW w*)),
for sisn. n. Define (a ii) = t, (a (8) + (1 t.)TT((a i) for all E and 1 ssis n. Then To satisfies
W W y (p* - F2) (wk-1-Wi
Thus, get
W - W &
(px:
Fn) (Wo - -W"
i=1
k
(pat
Fi) (T - PFF VV*)
i=1
=
(p=i
E1) (Vo- - V
i=1
1-1 E1)
= 7 (pr
pa: (vo= - V*),
i=1
19

---

Published in Transactions on Machine Learning Research (05/2025)
where the third and last equality follows from (pa. - Ej = 0. This implies that
V V 7p 1 (1+ 1 1-9 Bi) (pre
E1)
II
pm (V-- V*)
Am1
h-1
= gh
patk +
7 Ei pipe
1
luT
II i=1
p (VO 0 V*).
1 1-7
1
Then, we have
- - 1 1- 2/11100 -V*I
since Ep is stochastic matrix with
| =1
Suppose there cxists a unique optimal policy x². Then, if (non-deflated) VI generates V for k = 0, I,.., there exist K such that arg max, T = xt for k > K. Since DDVI for Control generates the samn policy as VI for Control, DDVI for Control also generates greedy policy x² for k > K iterations. Therefore, we get
_10 ) (pm -E1) k-k K K
Ei)A-K 11 (P=L
| v /z
1+ 1-7 10
E (V (V0 VT)
- =ct+|( ( -E1) k-K
|1v0 |1vo -V-l
= = - I)))
for & > and some constant C E R.
B.4 Proof of Theorem 5.1
Consider the following stochastic approximation algorithm
y = yk mm (X.)( (K)
(11)
for k 0, 0, where Y E R", Th (Xx) E R f(.,2) R" is uniformly Lipschitz, and {Sk 1= i.i.d. random variables. Let F(y) = E (k),, (x) = lim F(ry)/r, MK+1 = f(y*, (.) - F(Y),, and
I.... are
Jk = oYY (). The following result from Borkar & Meyn (2000) shows the convergence of the y sequence.
Proposition B.1. (Borkur & Meyn, 2000, Theorem 2.2 and 2.5) If (i) ma = (k+1)-1, (ii) (M*, -==
are martingale difference sequence (ii) E|M I <K11 + [2 for some constant K, (tv) - =()==x(y(0)) has asymptotically stable equilibrium origin, and (v) s(l)= = F(y(()) has a unique globally asymptotically stable equdlibrium y*, then {Y*) kk=.,.... of equation 11 converges to y almost surely, and furthermore, (Y') 1o,, of
- Mo f(Yk (())(()))
(12)
for 1: = 0, where is are random variables taking values in 21. ,n. and Vo Σ (i=ie) when is = satisfying lim inf wikk > for some constant > 0, also converge to yy almost surely.
In equation 12, (*x))) and J(Y*, (1x( are the i-th coordinate of Y and J(Y*, ; (k), respectively. The equation 12 can be interpreted as asynchronous version of equation 11. We note that Proposition B. is a simplified version with stronger conditions of Theorem 2.2 and 2.5 of Borkar & Meyn (2000).
Recall that DDTD equation 8 with a = is
w = ( + Th (Xx) (Xts) + - - - (xx))
vk+1 (1 7.) - Wh-1
(13)
20

---

Published in Transactions on Machine Learning Research (05/2025)
We will first show that W - (I - VV,) and this directly implies that V - V For applying Proposition B.1, consider
W = w + m Z)),
where The (k + 1) 2, E R such that 2,(x) (- (2) and k= are i...d random variables, and f(W*, (z) = (x) + 7(11 - -B.) w (Z,xx) - 7 (1 E.,) - - (x).. Then,
F(W) = [.) = (p(" - -E,((1 - -. 1JW +r" M s(W*, 2.) )( and Fz = o(W M 1 siss).
We now chock the conditions. First, since f(W, (xx) f(W', (I (I- ( (=)((x)) (1 EE, (I -E.) ( (x)()) implies (l,(W, ((W),2) S (1a5) || 11(1 +
BE (1 - v.. --) IDI W'l,, f()z) is uniformly Lipschitz. We have
E E[M (x))+t((1111) (x) Fr)
=E(r((T - -FF.)) ( (Z(()) (
-F.))
- -P =YP" (1-> - -1 -
=0
for all x E X. This implics that M++1 is martingale difference sequence. Also,
Ell E||MM* 11 ||3 JF1 S (1l (1 - -E.) || "1., s K(1 (11+|1110 <
(IW*))
for constant K = (1 (1- -b)
+ -1 -111²
By definition, F& (3) = lim (P= E,)) - -E,) fly. In Section B.1, we showed that spec Fox + T) (7..+1...... 7,,, 0}. Hence, (xcc((22) = {12+41 1,...,y7, - 1, -13. Since |&d S 1 for all s + 1 S S n, real parts of all eigenvalues Fo are negative. This implics that j(t) Fxx (y)()) has an asymptotically stable equilibrium origin and j(() F(y(()) has unique globally asymptotically stable equilibrium T = [ (r(P= - -E)) --1)-11-11
Lastly, since X2 Unif(Xt) and {Xa are i.idd random variables, Vi,e/t converges to 3. almost surely by the law of large numbers. Since Tux,, = (oino 1 1x=xx)_1 Therefore, by Proposition B.1, (W*) "a7*)ean k..0. of equation 13 converge to 8 almost surely, and this implies that v (T- - =(I- - almost surely.
> 11, V
B.5 Proof of Theorem 5.2
Consider the following linear stochastic approximation algorithm
(14) for k = 0, 0,..... where y E R", I are random variables, b((+) E R", A(Cx) E R" x R", and Aislll |[bı]| < xc, for < i,j S n and < k < n. The following result from Chen el al. (2020) provides a rate of convergence of y to the solution y* -A ---b,, where A and are the expectation of matrices A( and vectors b(C+), respectively.
yk+ y + TH (XX))((()))) +
Proposition B.2. (Chen et al., 2020, Theorem 2.5 and Corollary 2.7) If (i) m = gk for > O, (ii) [C=]k=o,1... is ergodic (aperiodic and irreducible) Markov process with a unique invuriant measure p. (188) E,[4' A and E,[[B'= b, (iv) A is Hurwitz, (v) Re(A) < 11/2 for all X spec(gA), then E|llY* Y* = O(k-1) where Y -
We note that Proposition B.2 is also simplified version with stronger conditions of Theorem 2.5 and Corollary 2.7 of Chen et al. (2020).
21

---

Published in Transactions on Machine Learning Research (05/2025)
Define (Xx)) R² as (x))(()) =1 -xx= Then, DDTD equation 8 with 1 is equivalent to Wh+1 = W (Xx,, Xz) + b(x,, x()),
where
= = ((X)) 7 and x (X). Hence ||A Il, 11b2l1 < co, for 1 i S n and 1 s
xx)
-E,))=) -
Since {Xx, X X2IK=00 are ii.d. random variables, {Xx, k= are Markov process. Let μ ~ Xx, and P(1 21 F2, x/2) be transition matrix of (Xg, Xx)==..1.... Then T/ (22 = p( LPT (ví x1). Since (u') P(..-1..)) - p for any distribution p², l is unique invariant measure. Hence, [Xx, K,,,- is irreducible and aperiodic. We have,
((1-)))))))) - v(x)) 7E, (1 - (1- ((xx) Xal E,(A(Xe, [[]] = Ex(b((a)) (16 Pp 10-0p=(111111 (1-) (x(,) (T,,
(11-
7E, (1 (1- -
= Ex(((()) (1-(1--1)))) (1=) - -7E, (1 (1
((P" 7B.) (1 -7E.)= -11). 1),
and ( x() = n L,.. Then, Y = - A = |1 (7(p* Es))(I - -2.) W".
As we discussed in Section B.4, spec(A) () (--) - - 11,-1) Tet ADDTD minn (A. Re(1 7)). Then, if > 2ADDTD the real component of the cigenvalues Re(A) 1/2 for all X E spec(g.)) Therefore, by Proposition B.2, E|] W [ = O(k-)))) and this implies that [ s E - W [P2] = O(k- 1)
B.6 Non-asymptotic convergence analysis of DDTD
Consider following the stochastic approximation algorithm
yk+1= = x + mm (Xx)((((Y (a) -k + 2x)
(15)
for k: = 0, 1,...., where y E RR 7 (Xx) E RR, (ck) are Markov chain with unique distribution p and transition matrix P. Let F(y) (V Se)] and Fk = oYYY M', m, S i sis t). Define mixing time la [min k 2 0,: max, (P*(..)) ~001TVV < < where 1/// stands for the total variation distance. Let Y be fixed point of Fly). Then following proposition holds.
Proposition B.3. (Chen et al., 2023, Theorem 1) Let (i) {GK]k=o,1... is aperiodic and irreducible Markoe chain, (ti) F is 3-contraction respect to some || lle. (iii) f(,,2) : R + R" is A1-unéformly Lipschitz with respect to ||- lle and [If y) < Bi for any y. (ir) (MK, Fkl )==0, are marlingale difference sequence, and (v) El ++ Fk] Ag + |2 for some A2, B2 > 0. Then, if Th
S cdd(1 - d2y) to + d3 E| r-
nta d2
for all h 2 K, and if mh = 1 Ju( we have
K + h k + h
8n dyc2tz log(k: + h)
E|jly* - 1- S cidi
k+1 h
for all k 2 K, where (Xx)))== is nonincreasing sequence satisfying Eisk- a, S min
de 1
for
dz : 4A
all k 2 tx, K = minsk 2 0: ts 2 +x), A = A₁ + 11, B B1 + B2, c1 = = Y || +|
(AllY*le lle + B) Teall ||x 5 - ||le S ueall |I ||s for chosen norm || IIx such that 1 ? L-smooth function
with respect to || Ile, d1 = - dg = 1 - 1-Bd and d3 = 111L(1-0u2)) such that 0 chosen satisfying 8² -1
1+6="
612.
22

---

Published in Transactions on Machine Learning Research (05/2025)
DDTD in equation 8 with is equivalent to
W = w* k + m (Xx)( , [x. W* + kz),
where Zx = 0, and (x) (z) 7),) (X') - -1,
(x)) + (x). As we showed in Section B.5, (Xx, k=,,... is irreducible and aperiodic Markov chain with an invariant mcasure μ. Furthermore, mixing time of {Xx. X is 1.
We also have
(r)))) F(W) E (1)
-
W()) ((x)
Xx-(xx (z) +z)+ ( ()()) - -E, (1 -I, (()) + + x
Ex-(x ( (x==) Pr"
PM P"1 -E.)
() 7E, (1 7B.) -
(r) 7 F.) (1- ((x)) + -
(16)
Let AI....,>,, An be the eigenvalues of pd sorted in the decreasing order of magnitude with ties broken arbitrarily.
Let ADDTD = 7(p F.,) - Since spectral radius is the infimum of matrix norm, for any 6 > 0,
there exists || lle such that pl 1 n ADDTD + (1 1)) S |l
where p( ADDTD (1 1) maxxe (A.4 n ADDTDD + (1 " S p( ADDID + -))++ +
+ 1
The upper bound (0, X, X'Ile ||]==xr S || Be and ((W,x,X)(aa x,''x,X')(x))
((x=)) -E,) (W- - W)(X' - (1 (W- (W-WW)) (x)) implies that
I1/(WX J(W', x,, xx)x (117) -T,, I|e 16 (T PPa) l1e) II W'll
W'
As shown in equation 16, we have F(W)- E E (xx = (r +x(P= -E)) (I- W) +
(1 W).. This shows that
[F(W)) - ((W))) (2 + (1 - (--111 11 (W1 - W2) [ s
( I1 - Walle
and F(W) has fixed point T since 1 ADDTTD + (1 - / and ADDTD share same fixed point.
Thus, by Theorem B.3 and E| V= v= I [I - -| -
[12], we have the following two non-asymptotic convergence results for DDTD one for constant stepsize and the other for diminishing stepsize.
Theorem B.4 (DDTD with constant stepsize). Let A An be the eigenvalues of pa sorted in decreasing order of magnilude with lies broken arbilrurily. Let -- For any > O, there exist a Ce, de >> 0 and || lle such. that for a = 1 and O < 1 < de, DDTD exhibits the rate
E||lK* V 111 S ac(1 7 pb h-1 + CeN
for all h 21 where p == 1-
max faxx|Asaa (1 |xm +
We note that ae be. Ce, de of Theorem B.4 can be obtained by plugging A1 = A2, = B Bg = in Proposition B.3.
Theorem B.5 (DDTD with diminishing stepsize). Let Ai,...,>,, An be the eigenvalues of pd sorted in decreasing order of magnitude with ties broken arbitrarily- For any > O, there exist ae, be, Ce, de > 0 and || lle such that for a = 1 and Ti (Xt) ( DDTD exhibits the rale
El|lk - V*1 < k+ bb
Gr
+
(I-
1
de
cep
k + b.
for all le 2 where 1- 1 max maxf/19411....
Pal tc.
Again, we note that a, c, of Theorem B.5 can be obtained by plugging A Ac. =0 B,, B, in Proposition B.3.
23

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm DDVI with AutoPl (Detailed)
1: Initialize C,C
2: function DDVI(( V,K, (A (wilizn, ))
Vo C=
E, >i=1> A
in Fact 2
for k- = 0,..., K do
6:
if c 2 C and
wh+1
< then
Te 2
X441 (w²)² ww++1/// (w+)
7:
8:
As+1 (N/+1 - -1 (1.0))/((a)))
Ms+1 = k+ -Eiz ad:(1- ++
9:
1-a.7d A,-A
10:
Return
DDVI(s+1, V2 K --c, (A 11 fui as-1)
11:
else
12:
Wh+1 = (1 - 0,) 0₁ + (Px - a, F.F. asr
Vk+1 (1 as B.) - WW
13:
14:
c+1
w+1 Wh+1 W
15:
16:
w = W Wh-1
17: Return VK
18:
Initialize 0 and U1 1, d1 =1
19:
DDVI(1, Vo, K, ,1,1,
C DDVI with QR Iteration, AutoPI and AutoQR
C.1 DDVI with AutoPI and AutoQR
We first introduce DDVI with AutoPI for 0 a If W = 0, we have
-(1-))(1a7E.) t E.)([I -vyE 1=0
by equation 4, and
+ 07 - (7,)) / (W*+1- ((1 (11-ai ay7E) +
are the itcrates of a power iteration with respect to (1 - a]( - -ayE aP* Section B.1, we show that
-E,( an)))-- In
a) - ay..) ty - - -7).)- (1 a)l + arp + U.D (17-111022, V,T
For a se 1, we expect that spectral radius of matrix be 1 1-a+77aAs41 and (a-a)ltayP*+Ul 1y VT T-g0nk
and p + U.DD (1,--1o,, VT have the same top eigenvector. With the same argument as in Section 4.2, we recover the 1-th eigenvector of pa by Bru al. (2012, Proposition 5). Leveraging this observation, formalize this approach in Algorithm 4.
Now, we introduce DDVI with AutoQR for 0 < a 5
Assume the top s ++1 cigenvalues of P are distinct, i.c., 1= A1 > Del ...>>> DA Let E, = =; A.Ru be a rank-8 deflation matrix of pa as in Fact W = 0, we again have
k-1
W
E(1 a) a. a - -1r -1)aarr 1=0
Wh+1 W ((1 a1 aTL.s) an - E.)(1 -
24

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm DDVI with AutoQR
Initialize C,e function DDVI((s, V, K,K, (Ae)i a,))
V =V, = 0,
4: E, = > A as in Fact 3
5: for = 0...., K do
if 2 C and 1 12
#+1
then
1 1
7:
1o41 = (w*)
w /1
As41 (N 1 as (as?)
u'41 wht1 >i=1 W/ W'+1
u, w
U4
10:
Us+1
((H++)) "441
11:
Return
DDVI Vk K K- ():) (Ai) 1 ( (.)))))).))
12:
else
13:
Wh+ (1 -1-0,, + (P
a, F., V + 0rp
vk+1 = =(1 - B,} - WW
14:
15:
= c+1
16:
w = Wh+t W
17:
- Wh Wh-
18: Return yk
19:
Initialize 8 and u1 1, A1
20:
DDVI(1, vo, A1, (1,,1,1)
and
- -1a - -
is the iterates of power iteration with respect to (1 a)([ a] (1 ag E.) an) -1 In Scction B.1, show that
(1 (1-a) a.FF.) + a7 R.)(T (yflT--yFF.---- = (1 ai) + axp" + U.R (u7 Mhnls U.
1-90n
Pu 1r V-T For a s 1, we expect that spectral radius of matrix is 1-a and tar +U.
and pD + U.R ma2-- U. have the same top eigenvector. With the same argument as in Section 4.2, 1-30d4 w w, where is the top eigenvector of pa - U,R, (As Dudd U.T Thus, I-yu
for large k, we expect [W by orthornormalizing wo against uy,..., uas we can obtain top + 1-th Schur vector of p Saad (2011, Section 4.2.4). Leveraging this observation, we propose DDVI with Automatic QR Iteration (AutoQR) and formalize this in Algorithm
D Environments
We introduce four environments and polices used experiments.
Cliffwalk The Cliffwalk is 3 x 7 grid world. The top-left corner is initial state, top-right corner is the goal terminal state with reward of 10, and the other states in the first row are terminal states with reward of -10. There is a penalty of -1 in all other states. The agent has four actio CP(0), RIGHT(1), DOWN(2), and LEFT(3). Each action has 90% chance to successfully move in the selected direction, and with probability of 10% one of the other thrce directions is randomly selected and the agent moves that direction. If the agent attempts get out of the boundary, will stay place. We use the optimal policy for the policy evaluation task in experiments. The environment is shown in Figure 4.
25

---

Published in Transactions on Machine Learning Research (05/2025)
t
4
Figure Cliffwalk environment. Dark shaded region is goal state with a positive reward. Gray shaded regions are terminal states with negative reward. Arrows show the optimal policy.
4
Figure Maze environment. The dark shaded region the goal state with positive reward. Arrows show optimal policy.
Figure Chain walk environment. Dark shaded region the goal state with positive reward and gray shaded region is state with negative reward. Arrows show optimal policy.
26

---

Published in Transactions on Machine Learning Research (05/2025)
Maze The Maze is 5 x 5 grid world with 16 walls. The top-left corner is the initial state, and the bottom-left corner is the goal state with reward of 10. Similar to the Clifffwalk, there is a penalty of -1 in all other states, and the agent has four actions: UP(0), RIGHT(I), DOWN(2), and LEFT((). Each action has 90% chance to successfully move in the selected direction, and with probability of 10% one of the other three directions randomly selected and the agent moves in that direction. If the agent allempts to gel out of the boundary or hits a wall, will stay in place. We use the following policies for the policy evaluation task in our DDVI and DDTD experiments, respectively:
2,, 3,
2, 2, 3, 3,,,,,,,,0333,,3,3,11000
Here, the action for each state is listed row-wise. The environment is shown in Figure 5.
Chain Walk We use the Chain Walk environment, as described by Farahmand & Ghavamzadeh (2021), which is similar to the formulation by Lagoudakis & Parr (2003). Chain Walk is parametrized by the tuple (1X2), [A], Aps b,). It is circular chain, where the state and 50 are connected. The reward is stale-dependent. State 40 is goal state with reward 1, state 11 gives reward -1, and all other states give reward 0. Agent has two actions: RIGHT(() and LEFT((). With each action, the agent has 70% chance to successfully move in the selected direction, 10% chance to stay still, and with probability direction. We use the following policy our experiments: (0, 1, 1, 0, 1, 1, 0, 0, 0, 0, O, O, 0, 0, 0, 0, 0, 0, O, O, O, O, O, 0, 1, 1, 1, 1, 1, 1 1 Figure 6.
20% the agent moves in the opposite
1, 1,
1,
1, 1, 0, 1, 0, 1, 1). The environment is shown 1. 1, 1, 1,
10-1
20.2
10-1
10-
Normalized [V*
10-4
Normalized
10t4
10-1
30-18
10-9
Vi
man-1 DDVI for control
rank: DDM
20
30
50
70
20
60
Rerations
Iteration (k)
(a) Rank-1 DDVT for control in Chain Walk
(b) Rank-1 DDVT for control in Garnet
Figure 7: Comparison of rank-1 DDVT for control and VI in (left) Chain Walk and (right) Garnet.
Garnet We use the Garnet environment as described by Farahmand & Ghavamzadeh (2021); Rakhsha et al. (2022), which is based on Bhatnagar al. (2009). Garnet is parameterized by the tuple (I~2), [A], 6p, 6.)). | and |A|] are the number of states and actions, and b, is the branching factor of the environment, which the number of possible next-states for each state-action pair. We randomly select bp states without replacement and then, transition distribution is generated randomly. We select b, states without replacement, and for each selected x, we assign state-dependent reward to be a uniformly sampled value in (0,1).
E Rank-1 DDVI for Control Experiments
In this experiment, we consider Chain Walk and Garnet. We use Garnet with 100 states, 8 actions, a branching factor of 6, and 10 non-zero rewards throughout the state space. We use normalized errors || - |/|||/|||* 7 = 0.995, and E, II1T, where n is the number of states. For Garnet, we plot average values on the 100 Garnet instances and denote one standard error with the shaded area. Figure 7(a) and 7(b) show that rank-1 DDVT for Control does indeed provide acceleration.
27

---

Published in Transactions on Machine Learning Research (05/2025)
F
Additional DDVI Experiments and Details
In all experiments, we set DDVI's a 0.99. We perform further experiments of DDVI with different ranks for discount factor 7 0.95, 0.995 (Figure and 9), and the QR iteration for 100 iterations in experiments.
10a
Normalized ||v vall
10
10
10
10
DDVI (AutoQR)
Normalized ||V*
DDVI (AutoPI)
10-1
10-1
DDVI (rank-1)
DDVI (rank-2)
10-4
10
DDVI (rank-3)
DDVI (rank-4)
10
3
VI
10-4
10-4
200
400
600
800
1000
200
400
600
800
1000
Iterations (k)
Iterations (k)
Figure 8: Comparison of DDVI with different ranks, AutoPl, and AutoQR against VI with discount factor = 0.95 in (left) Maze and (right) Chain Walk. The plots for DDVI do not start at ileration 0 because the costs of computing E, through QR iterations are incorporated as rightward shifts. Rate of DDVI with AutoPI and AutoQR changes when E, updated.
10a
10a
Normalized || Valla
Normalized lizaliized//o ||V* 1/11
10-1
10-1
10-2
10-2
DDVI (AutoQR)
DDVI (AutoPI)
10-3
10
DDVI (rank-1)
(rank-2)
10-4
10-4
DDVI (rank-3)
DDVI (rank-4)
10 5
VI
10
10
200
400
600
800
1000
0
200
400
600
800
1000
Iterations (k)
Iterations (k)
Figure 9: Comparison of DDVI with different ranks, AutoPI, and AutoQR against VI with discount factor Y 0.995 in (left) Maze and (right) Chain Walk. The plots for DDVI do not start iteration 0 because the costs of computing E, through QR iterations are incorporated rightward shifts. Rate of DDVI with AutoPT and AutoQR changes when E, is updated.
We perform further comparison of convergence in Figures 10, 11, 12, 13. Figure 10 is with Garnet environment with 50 states and 40 branching factor that matches the setting in Goyal & Grand-Clément (2022). In experiments, the QR iteration is run for 600 iterations. For PID VI, we set 0.05 and e 10 In Anderson VI, we have m = 5. In Figure 2, we use 20 Garnet MDPs with branching factor bp = 2, and b, = 0.1
G DDTD Experiments
A key part of our experimental setup is the model P. To show the robustness DDTD to model error and also its advantage over Dyna, we consider the scenario that P has some non-diminishing error. We achieve this with the same technique Rakhsha al. (2022). Assume that each iteration t, the empirical distribution of the next- state from H, is PMLLE( (z, a), which is going to be updated with every sample. For
28

---

Published in Transactions on Machine Learning Research (05/2025)
10"
10
Normalized |[V - v"Ih
Normalized ||Ve Volh
Anderson VI
10-2
10-2
S-AVI
PID VI
10
4
Anc VI
DDVI (AutoQR)
DDVI (rank-1)
10
10
DDVI (rank-2)
10-3
10
10-10
10-10
200
400
600
800
1000
50
100
150
200
250
Iterations (k)
Wall Clock (ms)
Figure 10: Comparison of DDVI with other accelerated Vls. Normalized errors are shown against the iteration number (left) and wall clock time (right). Plots are average of 20 randomly generated Garnet MDPs with 50 states and branching factor of 40 with shaded areas showing the standard error.
10
10
Normalized ||V* wa
Normalized || vall2
VI
Anderson VI
S-AVI
10
10
(AutoQR)
10-6
10
DDVI (rank-1)
DDVI (rank-2)
10
10
10:10 10
10
500
1000
1500
2000
20
60
80
100
Iterations (k)
Wall Clock (ms)
Figure 11: Comparison of DDVI with other accelerated Vls. Normalized errors are shown against the iteration number (left) and wall clock time (right) in Maze.
some hyperparameter 0 E [0, 1], we set the approximate dynamics P(-|,1, a) as
a)) (1 0) -00-- + ( 0f)
(17)
where USS for S X is the uniform distribution over S. The hyperparameter controls the amount of error introduced in P. If = 0, we have P = PMLE which becomes arbitrarily accurate with more samples. With larger 0, P(-l0, a) will be smoothed towards the uniform distribution more, which leads to a larger model error. Dyna, we keep the empirical average of past rewards for each æ, a f: X' A - R and perform planning with P.P at cach iteration to calculate the value function, that is V (I (I-<0 ppa) -1 In Figure 3, have shown the result. for 0 = 0.3. In Figure 14 and Figure 15 show the results for 0 0.1, 0.3, 0.5 in both Maze and Chain Walk environments.
As we see in Figure 14 and Figure 15, DDTD shows faster convergence than the conventional TD. In Maze, this only achieved with higher rank versions of DDTD but in Chain Walk, even rank-1 DDTD is able to significantly accelerate the learning. Also note that unlike Dyna, DDTD is converging to the true value function despite the model error. We observe that the impact model error on DDTD very mild. In some cases such as rank-3 DDTD in Maze, between 0.3 and f 0.5, we observe slightly slower convergence with higher model error. The hyperparamaters of TD Learning and DDTD are given in Tables 1,2, and 3.
29

---

Published in Transactions on Machine Learning Research (05/2025)
10"
10"
Normalized ||V* V
Normalized ||Ve v
Anderson VI
10a2
10
S-AVI
PID VI
10-1
10
Anc VI
DDVI (AutoQR)
DDVI (rank-1)
10
(rank-2)
10-4
10
10-10
10-10
2000
Iterations (k)
Wall Clock (ms)
Figure 12: Comparison of DDVI with other accelerated VIs. Normalized errors are shown against the iteration
number (left) and wall clock time (right) in Chain Walk.
10"
10"
Normalized ||V* 1a
aali ||V 1=1
VI
Anderson VI
10-2
10-2
S-AVI
PID VI
10-4
10
Normalized
(AutoOR)
DDVI (rank-1)
10
10
DDVI (rank-2)
10
10
10-10
10-10
500
1000
1500
2000
20
60
100
Iterations (k)
Wall Clock (ms)
Figure 13: Comparison of DDVI with other accelerated VIs. Normalizod errors are shown against the itcration number (left) and wall clock time (right) in Cliffwalk.
Table Hyperparamters for the Maze environment for 7 = 0.99. Cells with multiple values provide the value of the hyperparameter for 8 0.1, 0 0.3, and 0.5, respectively.
rank-1 DDTD
rank-2 DDTD
rank-3 DDTD
rank-4 DDTD
TD
7) (learning rate)
0.3, 0.3, 0.3
0.3, 0.3, 0.3 0.7, 0.8, 0.8 10
0.07, 0.07, 0.07
0.07, 0.07, 0.07 0.9,
0.3
0.8, 0.8, 0.8
0.9, 0.9.
K
10
10
10
Table 2: Hyperparanters for the Maze enviromment for = 0.95. Cells with multiple values provide the value
of the hyperparameter for 0 = 0.1, 0 = 0.3, and = 0.5, respectively.
rank-1 DDTD
rank-2 DDTD rank-3 DDTD
rank-4 DDTD
TD
7) (learning rale)
0.5, 0.5, 0.5
0.5, 0.5, 0.5
0.4, 0.4, 0.4
0.4, 0.4, 0.4
0.5
a
0.8, 0.8, 0.8
0.8, 0.8, 0.8
0.8, 0.8, 0.8
0.8. 0.8, 0.8
K
10
10
10
Table 3: Hyperparamters for the Chainwalk environment for both 7 0.99 and = 0.95. Cells with multiple values provide the value of the hyperparameter for 0 = 0.1, 0 = 0.3, and 0 = 0.5, respectively.
rank-1 DDTD
rank-2 DDTD rank-3 DDTD rank-4 DDTD TD
learning rate (1)
a
0.9, 0.9, 0.9
0.9, 0.8, 0.8
0.9, 0.8, 0.8
0.9, 0.8, 0.8 10
K
10
10
10
30

---

Published in Transactions on Machine Learning Research (05/2025)
Low Model Error
Medium Model Error
High Model Error
1.0
0.8
Normalized I|V.
0.6
0.4
0K
5k
10K
15k
20k
0k
5k
10k
15k
20k
0K
5k
10k
15k
20k
Environment Samples (t)
Dyna
TD Learning
rank-1 DDTD
rank-2 DDTD
rank-3 DDTD
rank-4 DDTD
Low Model Error
Medium Model Error
High Model Error
1.0
0.8
Normalized I|V.
0.4
0.2
0k
3k
4k
0k
4k 5k
1k
2k
Environment Samples (t)
Dyna
TD Learning
rank-1 DDTD
rank-2 DDTD
rank-3 DDTD
rank-4 DDTD
Figure 14: Comparison of DDTD with TD Learning and Dyna in Maze with 7 0.99 (Top) and 7 0.95 (Bottom). Left: low model error with 0 = 0.1. Middle: medium model error with 0 = 0.3. Right: high model error with f = 0.5. Each curve is average of 20 runs. Shaded area shows one standard error.
31

---

Published in Transactions on Machine Learning Research (05/2025)
Low Model Error
Medium Model Error
High Model Error
1.0
0.8
Normalized I|V.
0.6
0.2
0.0
0k
5k
10k
15k
20k
0k
5k
10k
15k
20k
0k
5k
10k
15k
20k
Environment Samples (t)
Dyna
TD Learning
rank-1 DDTD
rank-2 DDTD
rank-3 DDTD
rank-4 DDTD
Low Model Error
Medium Model Error
High Model Error
1.0
Normalized I|V.
0.6
0.4
0.2
0k
3k
4k
5k
0k
1k
4k
5k
1k
2k
Environment Samples
Dyna
TD Learning
rank-1 DDTD
rank-2 DDTD
rank-3 DDTD
rank-4 DDTD
Figure 15: Comparison of DDTD with TD Learning and Dyna in Chainwalk with 7 0.99 (Top) and 7 0.95 (Bottom). Left: low model error with 0 = 0.1. Middle: medium model error with 0 = 0.3. Right: high model error with f = 0.5. Each curve is average of 20 runs. Shaded area shows one standard crror.
32


Reviews:
[{"review_id": "nx4BbGkB83", "reviewer": "Reviewer_avGa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "See below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a matrix splitting technique in the context of value iteration and temporal difference learning ,and establish that it rigorously improves the convergence rate relative to prior art. Experiments demonstrate the merits of the proposed approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Minor comment: SOR should be given as non-acronym (Successive over-relaxation) for subsection title of 3.2, since it is first introduced inside the subsection. Is the specific form of SOR presented in section 3.2 with A=B+C+D unique to this work, or appears in prior art? If it is the former, could the authors clarify why this generalized decomposition is important or required for the policy evaluation setting? \n\nAlso, several of the quantities specified here are for the space of complex numbers/matrices, but I do not believe any of these probability matrices are actually complex-valued but instead real-valued.\n\nFor the main presentation of equation (2), the authors should contrast the fixed point iteration with the fixed point operator that is usually applied for value iteration. How is the proposal a special variant of a Bellman operator that is restricting focus t the eigenspace of the transition matrix? Not enough time is spent interpreting the meaning of the core algorithm derivation in Section 3.3.\n\nFor the convergence rate comparison with vanilla value iteration, the authors should include dependence on the parameter dimension that also clarifies the computational cost required to evaluate the eigenvalue decompositions proposed. Without this, reporting the pure acceleration of the rate is not valid/fair.\n\nA similar comment holds for the QR decomposition, as well as comparison with vanilla temporal difference iteration.\n\nExperimentally, the authors should compare with alternative techniques for variance reduction, such as SAG, SVRG, zap-Q learning (stochastic Newton Raphson, etc.) to make the case that the specific class of power iteration methods in eigenspace have merits relative to alternative notions of acceleration/variance reduction. Are there specific classes of transition matrices that are particularly advantageous for the proposed algorithm?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "b8kIdAOCN6", "reviewer": "Reviewer_rh77", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well-written. The authors did an excellent job in positioning the paper, explaining the issue with value iteration, presenting technical details in the preliminary and the contribution sections. The theoretical results seem convincing and to the point of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed to improve the standard value iteration which has convergence rate $O(\\gamma^k)$, when $\\gamma \\approx 1$, the convergence rate can be slow as have been observed by existing work. This paper built on the deflation matrix technique and proposed numerical stable solutions. By removing a matrix from the transition dynamics matrix, it is possible to accelerate the convergence rate up to $\\tilde{O}(\\gamma^k |\\lambda_{s+1}^k|)$ which can be significantly faster.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I don't see major issues of the paper. However, I would like to ask the authors to provide additional discussion on how the proposed method can be used to accelerate popular VI methods like DQN, which was briefly discussed in the beginning of section 5. In my understanding, DDTD is an on-policy algorithm, which makes it hard to compete against Q-learning/DQN that can reuse samples. However, as the authors pointed out, slow convergence has been observed for these algorithms. It would be very beneficial to have a paragraph on this point on how DDTD could extend to these cases.", "broader_impact_concerns": "ethical concerns not applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "P0e77DEMF3", "reviewer": "Reviewer_xBYa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\nThe paper proposes a new value iteration methd based on matrix splitting and matrix deflation technique, and a new sample method based on this value iteration idea. The theoretical guarantees for this two methods are provided. For the former one, the authors show it achieves an $|\\lambda_{s+1}|^k$ acceleration compared with the convergence rate of traditional VI. \n\nThe paper conduct rich experiments, comparing different variants of DDVI and other variants of VI for acceleration, in environments with different numbers of states and different discounting levels. \n\nWeakness and questions: \n\nIn corollary 3.2, it shows that the convergence rate is $|\\gamma \\lambda_{s+1}|^k$ when $k$ tends to be $\\infty$. However, for the classic VI method, the convergence rate does not require the iteration time to be $\\infty$. Even though $\\lambda$ may tend to be $1$, the infinite number of iterations of VI can also guarantee great convergence. Could you provide a discussion with respect to this point? \n\nIn Section 1, the authors mentioned some variants of VI to accelerate the convergence. More discussions and comparisons about their convergence rate should be provided. \n\nLine 4 in page 3, a typo $X_k$.\n\nIn Section 5, it is unclear about the theoretical advantage of DDTD's convergence compared with that of TD. \n\nIn experiments, why selecting different discounting levels in experiments of DDTD and other experiments? The paper only compares the performances when $\\lambda$ is very lage (larger than $0.99$). Other levels of $\\lambda$ should also be tested and compared.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a fundamental problem of solving MDPs. It introduces the idea of matrix splitting and matrix deflation to effectively remove (deflate) the top s dominant eigen-structure of the transition matrix and proposes the Deflated Dynamics Value Iteration method. The paper shows that the convergence rate can be guranteed by $\\gamma^k |\\lambda_{s+1}|^k$, achieveing an acceleration of $|\\lambda_{s+1}|^k$ compared with the traditional VI method. The paper also proposes a Deflated Dynamics Temporal Difference algorithm based on this offline value iteration method. Existensive experiments are conducted to verify the advantage of DDVI and DDTD compared with traditional VI and TD.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the last part.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree on the quality of the submission. In particular they highlight that the matrix splitting technique is a particularly interesting contribution, that the paper is well written, that the paper is well positioned in the related literature, and that the experiments are complete. 
Only minor issues were raised, which have already been addressed by the authors in the revised manuscript.
Decision: Accept (poster)