Rank-One Modified Value Iteration
Authors: Arman Sharifi Kolarijani
Tolga Ok
Peyman Mohajerin Esfahani
Mohamad Amin Sharifi Kolarijani
Venue: ICML 2025 poster (2025)
Keywords: Markov decision process
dynamic programming
reinforcement learning
value iteration
Q-learning
Primary area: reinforcement_learning

Abstract: In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. 
The proposed algorithm follows a policy iteration-type update by using a rank-one approximation of the transition probability matrix in the policy evaluation step. 
This rank-one approximation is closely related to the stationary distribution of the corresponding transition probability matrix, 
which is approximated using the power method. 
We provide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)value function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. 
Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems.

Rank-One Modified Value Iteration
Arman S. Kolarijani' Tolga Ok!
Peyman Mohajerin Esfahani 12 Mohamad Amin Sharifi Kolarijani
Abstract
value function By at iteration & given by
k 0,0,,,,.. (1) 1k++1 = 17 + (T(m))
In this paper, we provide a novel algorithm for solving planning and learning problems of Markov decision processes. The proposed al- gorithm follows policy fieration-type update by using a rank-one approximation of the tran- sition probability matrix in the policy evaluation step. This onnk-one approximation is closely re- lated to the stationary distribution of the corre- sponding transition probability matrix, which approximated using the power method. We pro- vide theoretical guarantees for the convergence of the proposed algorithm to optimal (action-)valus function with the same rate and computational complexity as the value iteration algorithm in the planning problem and as the Q-learning algorithm in the learning problem. Through our extensive numerical simulations, however, we show that the proposed algorithm consistently outperforms first- order algorithms and their accelerated versions for both planning and learning problems.
where G2 = I in the VI algorithm and G¹ (I PPs) in the PI algorithm, I is the identity matrix and Ps: is the state transition probability matrix of the MDP under the greedy policy with respect to 8₁- Both algorithms are guar- anteed to converge to the optimal value function and con- trol policy; see, e.g., (Puterman, 2014, Thms. 6.3.3 and 6.4.2). When it comes to computational complexity, one observes trade-off between the two algorithms: VI has lower per-iteration complexity compared to Pl, while PI converges in a smaller number of iterations compared to VI. The faster convergence of PI is partially explained by its recond-order nature which leads to a local quadratic conver- gence rate (Puterman & Brumelle, 1979; Bertsekas, 2022; Gargiani et al., 2022), compared to the linear convergence rate of VI (Puterman, 2014, Thms. 6.3.3).
-I-
This trade-off between the two algorithms has motivated much research to improve the convergence rate of VI and/or the per-iteration complexity of PI. One of the first improve- ments is the Relaxed VI algorithm (Kushner & Kleinman, 1971; Porteus & Totten, 1978) which allows for a greater step size compared to the standard VI algorithm. A large body of research in this area originates from the correspon- dence between VI and gradient descent method and between PI and Newton method GGrand-Clément 2021; Kolarijani & Mohajerin Esfahani, 2023). Here, approaches such as ac- celerated gradient descent and quasi-Newton methods from the optimization literature are adapted to develop modified versions of VI and PI. For instance, the combination of the VI algorithm with Nesterov acceleration (Nesterov, 1983) and Anderson acceleration (Anderson, 1965) have been explored in (Goyal & Hhand-Clément, 2022) and (Zhang et al., 2020), respectively, for solving the planning prob- lem. More recently, Halpern's 's anchoring acceleration scheme (Halpern, 1967) has been used to introduce the Anchored VI algorithm (Lee & Ryu, 2024) which in particu- lar exhibits (1/kk))rate for large values of discount factor and even for y 1. In the case of the learning problem, Speedy Q-Learning (Ghavamzadeh et al., 201 1), Momenium Q-Learning (Weng et al., 2021), and Nesterov Stochastic Approximation (Devraj et al., 2019) are among the algo- rithms that use the idea of momentum to achieve a better rate of convergence compared standard Q-learning (QL).
1. Introduction
Value iteration (VT) and policy iteration (PI) algorithms lie at the heart of most if not all algorithms for optimal con- trol of Markov decision processes (MDPs) in both cases of the planning problem (i.e., with access to the true model of the MDP) and the reinforcement learning problem (i.e., with access to samples of the MDP) (Sutton& & Barto, 2018; Bertsekas, 2023). Their widespread application stems from their simple implementation and straightforward combina- tion with function approximation schemes such as neural networks. Both VI and PI are iterative algorithms that ul- timately find the operator T: For 7-discounted, finite stale-action MDPs, the
of the Bellman (optimality)
Delfi University of Technology, The Netherlands University of Toronto, Canada. Correspondence to: Arman S. Kolarijani < sa.shariiiollaijaaieee @uudeltt............... <a
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Rank-One Modified Value Iteration
The Zap Q-Learning algorithm (Devraj & Meyn, 2017) can be thought of as second-order learning algorithm which was inspired by the stochastic Newton-Raphson (SNR) algo- rithm (Ruppert. 1985). The Quasi-Policy Lterninnn/Learning algorithms (Kolarijani & Mohajerin Esfahani, 2023) are, on the other hand, an example of using the idea of quasi- Newton methods for developing algorithms for optimal con- trol of MDPs. Another class of modified VI algorithms the Generalized Second- Order VI algorithm (Kamanchi al., 2022) which applies the Newton method on smoothed version of the Bellman operator. Tools and techniques from linear algebra have also been exploited to modify the VI algorithm, particularly for policy evaluation. The Operator Splitting V/ algorithm (Rakhsha et al., 2022) is an exam- ple that exploits the matrix splitting method for solving the linear equation corresponding to policy evaluation for given "cheap-to-acee" tccacssss" model of the underlying MDP. Recently, in (Lee et al., 2024), the authors combined the matrix splitting method with the matrix deflation techniques for removing the dominant eigenstructure of the transition probability matrix to speed up the policy evaluation.
standard VI and QL algorithms for solving the planning and learning problems of MDPs. The proposed R1-VI al- gorithm for solving the planning problem and its analysis are discussed in Section 3. Section 4 presents the RI R1-QL algorithm for solving the learning problem and its analysis. In Section 5, we provide the results of our extensive nu- merical simulations and compare the proposed algorithms with a range of existing algorithms for solving the optimal control problem of MDPs. Finally, some limitations of the proposed algorithms and future research directions are dis- cussed in Section 6. All the technical proof' are provided in Appendix A.
The set of real numbers is denoted by R. For a vector e E IR"", we use e(i)) and [e) (i) to denote its i-th element. Similarly, M (i and [M] denote the ele- ment in i-th row and j-th column of the matrix M E Rm=x. We use (v, u) = Σ v(i) u(i to denote the the inner product of the two vectors u E TR". ||0|] = E Iv(i),, ||l||2 = ((v, v). and ||0||00 max [e())] denote the I-norm, 2-norm, and oo-norm of the vector E R", re- spectively. We use (M) to denote the spectral radius (i.e., the largest eigenvalue in absolute value) of a square matrix M E R=X=, Given a set X. A(X) denotes the set of prob- ability distributions on X. Let x ~ P be a random variable with distribution P E AXX). We use T sample of the random variable x drawn from the sample space X' of x according to the distribution P. We use 1, O, and I to denote the all-one vector, the all-zero vector, and the identity matrix, respectively, with their dimension being clear from the context.
Notations.
Contribution. In this paper, we propose a novel algorithm that modifies the VI algorithm by incorporating a compu- tationally efficient PI-type update rule. To this end, we consider the update rule (1) with matrix gain of the form G₁ = (I- - Pk) where P& is a rank-one approxima- tion of Pg. To be precise, we consider the approxima- tion Ps- = 1d where dę = P d2 is a stationary dis- tribution of Pa and 1 is the all-one vector. The proposed algorithm then uses the power method for approximating dy iteratively using the true matrix Ps in the planning prob- lem and its sampled version in the learning problem. In particular,
to denote a
2. Optimal control of MDPs
Consider finite MDP (S, (S,,.,,c,,). Here, S == (1,2....,n) and A := 21. m) are the state and ac- tion spaces, respectively. The transition kernel P: SSA + (SS) is the conditional probability P(s [s, of the tran- sition to state st given the current state-action pair (s, a). The function e E T S = Thaem bounded from below, represents the stage cost c(s, a) of taking the control ac- tion a while the system is in state s. And, 7 E (0, is the discount factor which can be seen as trade-off pa- rameter between short- and long-term costs. A control policy π : S - A is a mapping from states to actions. Fix policy x. For the corresponding Markov chain under the policy π we define: (i) the state transition probabil- -aax" where pd ss)
(I) we propose the Rank-one VI (RI-VI) Algorithm as the modified VI algorithm for solving the planning problem and prove its convergence to the optimal value function (Theorem 3.3);
(2) we propose the Rank-one QL (RI-QL) Algorithm 2 as the modified QL algorithm for solving the learning problem and prove its convergence to the optimal Q- function (Theorem 4.2);
(3) we compare the proposed RI-VI and RI-QL algo- rithms with the state-of-the-art algorithms for solving planning and learning problems of MDPs and show the empirically faster convergence of the proposed algorithms compared to the ones with the same per- iteration computational complexity (i.e., the first-order algorithms and their accelerated versions).
ity matrix P E R 8|((5] P P(st|s, for 8, s+ E ES, (ii) the state-action transition probability matrix P' E [IAAAIA = [(m)) x (nm) where Ph ((s, a). (st attaat)))) = P(s if = =ss** and otherwise for (s, (),a), (st,at) E SSSxA. and (iii) the stage cost et E [RS R² where c (s) = c(s,T(s)) for E S.
Paper organization. In Section 2. we provide the neces- sary background and the problem definition along with the
2

---

Rank-One Modified Value Iteration
Under policy и, the value function e" E IR R is the expected discounted cost endured by following policy " over an infinite-horizon trajectory, that is, for each s E S,
for each (s, E S x A (Szepesvári, 2009, Fact 3). This characterization is particularly useful when one only has access to samples 3 ~ P(-|s, a) of the next state st for each state-action pair (s, a) E S x A (and not to the true transition probability kernel of the MDP). In partieular, let us define the empirical Bellman operator T : [R x S + R Sx as follows: for each (s, 0 8 st) ESXAX
v (s) = P (ser))
Eree(ss))
=0
1=0
The action-value function q" E TRISAA = R (or the so-called (-function) under policy π is defined as follows: for each (s,a) E x A
[T(q, (ss, a(s,a) + min q(st ,at). a EA
A classic algorithm for the learning problem is then the (syn- chronous) QL algorithm (Watkins & Dayan, 1992; Kearns & Singh, 1998), given in (5).
as) = a(s.a) + (sta)( [e (s+)).
These functions can be shown to satisfy the fixed-point equations (Puterman, 2014, Thm. 6.1.1)
intialize qu E ERSAA Ram
x- = + + q" q==ct+Pp'"
(2)
for k= 0, for (8, E E A k + ~ P((s,a)
The problem of interest is to control the MDP in manner that the expected, discounted, infinite-horizon cost is min- imized. To do so, one aims to find the optimal policy n' such that for any policy n,
(5)
8º = (s,
[T(q: 8 (ss,)))
(s+1(s,a) (3,(s,a) XRde
endfor
endfor
0x 0*)s)= = x= (s)) YsES,
Above, A 2 0 are the step-sizes. The QL algorithm is also guaranteed to converge to q" almost surely given that the step-sizes satisfy the Robbins-Monro conditions (i.e., En A = oo and Σk X < oo) (Tsitsiklis, 1994; particular, with polynomial step-size À = 1/(1 k) with w E (2/2, 1), QL out- puts c-accurate Q-function with high probability after O(7-1/w . -2- + - -1/(1-=)) iterations of synchronous sampling with r = while with a re-scaled linear step-size A = 1/(1 + rk), QL has been shown to require Ö(r 5 e -²) iterations of syn- chronous sampling for the same performance (Wainwright, 2019).
or, equivalently,
( V(s,a) E SSSXA A.
Jaakkola et al., 1993).
The optimal value function can be characterized as the solution to the fixed-point equation ot = T(v*), where T RiS| + || is the so-called Bellman (optimality) oper- ator defined follows: for each s S
(Even-Dar & Mansour, 2003),
(T = min (e(s, + EstrP(len) (s+)]}
aEA
(3)
The operator T is a 7-contraction in the oc-norm (i.e., [T(()) - T(w)ll 00 < 7 7 w for all w E R") (Puterman, 2014, Prop. 6.2.4). This contraction prop- erty is essentially the basis for the VI algorithm, introduced (4).
3. Rank-one value iteration (R1-VI)
Another well-known algorithm for solving the planning problem in MDPs is the PI algorithm. In order to provide this algorithm in a compact form, let us first introduce the notion of greedy policy. Given a value function e E R the greedy policy with respect v, denoted by n² S A, is
intialize vo E RRSI= R
for k = 0, 0k+1(s) (ss), ASES
(4)
endfor
From the Banach fixed-point theorem (see, e.g., (Puter- man, 2014, Thm. 6.2.3)), the VI algorithm converges to e* with a linear rate 7. Correspondingly, one can derive the fixed-point characterization q² = T(q*) of the optimal Q-function, where
t (s) E argmin E,t Est- a) + yo(s+)] Vs S.
aEA
(6)
The PI algorithm is then summarized in (7).
intialize no S - for =0, 0, Us = T
a)(sa)
[policy evaluation eq. (2))
(7)
+ y (P(ea)))
min q² (s+ (st,at) atEd
Tb+1 th endfor
[policy improvement eq. (6)
3

---

Rank-One Modified Value Iteration
The algorithm be proposed in this section is based on an alternative representation of the iterations of the Pl algo- rithm; see also (Puterman, 2014, Prop. 6.5.1).
Algorithm Rank-One Value Iteration (RI-VI)
Input:
transition kernel P: x A + A(S); cost function
I (xAAl; discount factor ? E (0, 1);
Lemma 3.1 (Policy iteration). Each iteration of the Pl
Output: optimal value function t'
algorithm (7) equivalently reads as
1: initialize: no E <R|( d_ E A(S);
vt), where Ps P=:=Po p==* is the state transition probability matrix of the MDP under the greed policy "
Uk+1 2k + -I-
2: for k = 0, 2,1, do
3: P. 0 &Rliiiss
4: for a do
as E argmin (c(s, a) + Ext [b)
5:
[+)) = min (c(s, +7 E, [b)(s*]]};
The PI algorithm outputs the optimal policy in a finite num- ber of iterations (Puterman, 2014, Thm. 6.4.2). Moreover, the algorithm has a local quadratic rate of convergence when initiated in small enough neighborhood around the optimal solution (Bertsekas, 2022; Gargiani et al., 2022). The faster convergence of PI compared to VI comes how- ever with a higher per-iteration computational complexity: The per-iteration complexities of VI and PI are Onn2m) and Onn²m + n²)), respectively. The extra Onn)) com- plexity due to the policy evaluation step, i.e., solving a linear system of equations; see also the matrix inversion in the characterization (8). To address this issue, we pro- pose to use low-rank approximation of Pk instead, Such approach allows us to approximate (I - Pkk) - with reduced computational cost by using the Woodbury for- mula (Hager, 1989). To be precise, we propose the rank-one VI (RI-VI) algorithm
"cA
6:
Ps s ) = P(s*|s, a.),, Vss ES;
7: end for
8:
f = Px d di f/ IIfli
9:
uk+1 = T(mk) (de, T(D:) va)
10: end for
Next be addressed is the computation of the vector de- Considering the fact that de is left eigenvector of Pa corresponding to the eigenvalue 1, we can use the power method (Golub & Van Loan, 2013, Sec. 7.3) to compute it as follows
f i= o. 1-1, (13)
f= PT (()) (0+1)
with some initialization di ASS) and I E {1. We then use d, d_ in the update rule (12). We note that the normalization is only to avoid the accumulation of numerical errors; to see this note that for the row stochastic matrix Pk. we have P E ASS) for any d E (SS). Un- der the assumptions of Lemma 3.2, the preceding iteration converges linearly to the unique stationary distribution with rate equal the second largest eigenvalue modulus of Ps: (Gallager, 2011 1, Thm. 3.4.1).
w = 2k + -t - vx),
(9)
where
p = 1d
(10)
is a rank-one approximation of the true transition probability
matrix P& at iteration k with dę == d E AS) being a stationary distribution of the greedy policy T& "k i.e.,
solution of d PA- d/- Under certain conditions, (10) is indeed "the best" rank-1 1 approximation of Pa:
The complete description of the proposed RI-VI algorithm is provided in Algorithm 1. We note that Algorithm in- cludes a single iteration (i.e., = 1) of the power method in (13) initialized by di = dx-1- The reason for this choice is that the greedy policy π and hence the corre- sponding transition matrix Ps usually stays the same over multiple iterations & of the algorithm in the value space. This means that the algorithm effectively performs multiple iterations of the power method. Despite using this approxi- mation dą of the stationary distribution of Pa with single iteration of the power method, the proposed algorithm can be shown to converge.
Lemma 3.2 (Rank-1 1 approximation). Assume that the tran- sition probability matrix Ps is ergodic (i.e., irreducible and aperiodic). Then,
1d arggii p(P- - -P)) PEROXa
(11)
s.t. P20. 11= rank 1.
where dy is the unique stationary distribution of Ps. That is, Ps- = 1dj is the best rank-1 approximation of Ps in terms of the spectral radius.
Using the Woodbury formula, we then have
Theorem 3.3 (Convergence of RI-VI). The iterates Up of the RI-VI Algorithm I converge to the optimal value function V² = T(u*) with at least the same rate as VI, i.e. with linear rate 7,
(I - - = (I - -1d I 7 1- 1d
and hence the R1-VI update (9) reads as
1k+1 = T(m)) + - (dc, T(mx) - 11)11.
(12) Let us also note that the per-iteration complexity of the

---

Rank-One Modified Value Iteration
proposed RI-VI Algorithm 1 is On12m), i.e., the same as that of VI. We finish this section with the following remark. Remark 3.4 (Generalization to modified policy iteration). Recall the generic value update rule
where Ps: == Pr' is the state-action transition probabil- ity matrix of the MDP under the greed policy T (s) E argmin A,5s, a) for E.
t
The idea is again to use the rank-one approximation Ps 1 of the matrix Ps in the update rule (15), where d, is now the stationary distribution of Pk. This leads to the update rule
(14) with the gain matrix Gk = I in the VI algorithm and G. = (c) in the PI algorithm. Also, note that (1- - 7PP) = = 2014, Cor. C.4). Inserting the truncated sum
1k+ = 2k + GR (T( - -0), k: 0.
since - - < 1 (Puterman,
7 (de. T(gk) - =k)1 T +1+1- T(gs) + 1 1-9
at each iteration of the planning problem. Then, for the learning problem, considering the synchronous update of all state-action pairs (s, a) E x A at each iteration k. we arrive at the rank-one Q-learning (RI-QL) update rule
G t=
G¹ -
P
with L E {0, . the update rule (14), we derive the Modified PI (MPI) algorithm which converges linearly with rate y for any choice of T. (Puterman, 2014, Thm. 6.5.5). (Observe that L = 0 and L oo correspond to the standard VI and PI algoritims, respectively). The proposed rank- one modification can be in general combined with the MPI algorithm. Indeed, we have
7>h (dx: Tx(gk) -qt), 0% 1-7
(16)
ak+1 = =1 + AE Tx(qs)) + 1,
where A 2 0 are properly chosen step-sizes satisfying conditions (e.g.. d 1/(k + 1)), and Te is the empirical Bellman operator evaluated at it- eration kt i.c., (Tx()))((s, a) = [Tiqs, s (((s, a) with $ P(-|s, a) for each (s. a) E S in T denotes the dependence on the next-state sample sy* generated at iteration k:
the
(I-7PA)
P
Σ
P + t p
7 P
t=0
1=0
6=
the subscript
1-1
= Σ t=
/ P
-
Then, by using the approximation PE = ld in the ma- trix inversion on the right-hand side of the equation above, we derive the gain matrix of the rank-one MPI (RI-MPI) algorithm to be
What remains to be addressed is computing the estima- tion dg of the stationary distribution in (16) using the sam- plcs. At each iteration k, define the sparse matrix F₁ e RISxA||
R (nm) (am))(mm)) (nm) with exactly one nonzero entry equal 1 in each row (s,a) E S x A corresponding to the column (st (st,at), where
4-1
G2 = P
t=0
s+ = sxt P(-(s,a), a + = āg E argmin qk ($) aat)
L+1
//pP/
1-7 ld
a EA
Observe that RI-VI is now a special case of RI-MPI with L= 0.
Observe that the matrix Fy is sampled version of the state- action transition probability matrix Px. Using this sample, we can form the stochastic approximation
4. Rank-one Q-learning (RI-QL)
P = (1 Au Pr A.FF
In this section, we focus on the learning problem in which we have access to a generative model that provides us with samples of the MDP (as opposed to access to the true transi- tion probability kernel of the MDP in the planning problem). To start, let us provide the PI update rule for the Q-function. The proof is similar the proof of Lemma 3.1 and omitted. Lemma 4.1 (Policy iteration for Q fuunctiin.). Each iteration of the Pl algorithm for the Q-function is given by
for the state-action transition probability matrix. We note that the same approximation is used in the 7ap Q-learning algorithm (Devraj & Meyn, 2017). With this approximation in hand, we can again use the power method for finding the stationary distribution. In particular, with a single iteration of the power method initialized by the previous stationary distribution dg-1, we have
d PT d = (1 (1-1a)) Px) J.P_1du-1 AuFF d
Mk+1 = q: + (I - (P)=-((((gs)) - 96),
(15)
5

---

Rank-One Modified Value Iteration
Algorithm 2 Rank-One Q-Learning (RI-QL)
Finally, we note that the per-iteration time complexity of the R1-QL Algorithm 2 is the same as that of the synchronous QL algorithm, i... O(mm²).
Input: samples from transition kerne P: 8 x A + A(S); cost function c E RISXA,, discount factor E (0, 1);
Output: optimal Q-function 9²
I: initialize: qo E IR |SAA ài E A(S x A);
5. Numerical simulations
2: for h- = 0... do
In this section, we compare the performance of several plan- ning and learning algorithms with our proposed methods. The experiments are conducted on Garnet (Archibald et al., 1995) and Graph MDPs (Devraj & Meyn, 2017), focusing on the Bellman errors | [T(m;) mxll.s and [T(g:) -u and the value errors || - -v"llx and || - - --1loo- In all of our experiments, we run policy iteration (PI) until it converges to calculate the optimal values o² and q" for ref- erence. Garnet and Graph MDPs are particularly compelling for our empirical analysis as we can run PI compute the optimal values, enabling us to measure value errors through- out the iterations. The Garnet MDPs have a state size of n = 200, an action size of m 5, and randomly generated transition probabilities and costs with a branching factor of 10. For our numerical experiments, we consider 25 ran- domly generated instances of Garnet MDPs and report the three quantiles of the errors. For the Graph MDPs, use the same configuration as described in (Devraj & Meyn, 2017), providing complementary benchmark to validate the effectiveness of our proposed method. In what follows, we report the result of our simulations for the planning and learning problems.
3: A =1/(((++]]] 1);
4: f= RISKAl;
5: for (8.a) E do
6:
8/" ~ P(-lsaa)
ā₂ argginn aat),
7:
atEA
(T)q a( + min qi(tttaa);; aled
8:
f(8-" 2g f 0,2) + d (s.a);
9:
end for
10: du = (1 Aa)ds + A d. d. |ddeli
11: as = T-q
ddا dd, [xt))) qx):
12:
q&+1 (1 )x + >r TT + tcl:;
13: end for
Now, using the approximation d=-1 Ph_ de- (i.e., assuming d is stationary distribution of P which does not hold exactly since dx-1 is only an approximation of a stationary distribution of 1k-1), we derive
d (1- 2b) + Fr dx-1-
We note that the vector f F2 d can be computed using the following pseudo-code:
Planning Algorithms. We compare several value iteration (VI) algorithms with the same per-iteration time complexity our proposed R1-VI Algorithm 1. We also include PI for reference. We mainly focus on comparing R1-VI with accelerated VI methods, namely, Nesterov-Vi VI (Goyal & Grand-Clément, 2022) and Anderson-Vi VI (Geist & Scherrer, 2018). In order to keep the time complexity the same, we use Anderson- with the memory parameter equal to one leading to a rank-one approximation of the Hessian matrix. The update rule of the accelerated VI algorithms is provided in Appendix B.
intialize f= RISA
for (s,a) E ESXA
$6 P()(s,a), ãz argmin q (Fxt (5t+t ,at) atEA
f(ttttt)) = f( a,,tt + (8. endfor
Observe that the approximation d=-1 PT de sig- nificantly reduces the memory and time complexity of the algorithm since we do not need to keep track of the esti- mates Ps of the state-action transition probability matrix and perform full matrix-vectos multiplications for updating the estimates di of the stationary distribution.
In Figure I, we report the median number of iterations re- quired to reach a certain error threshold for each algorithm across both MDPs for four different values of the discount factors 7 Our results indicate that the convergence perfor- mance of RI-VI is comparable with PI while maintaining the same per-iteration time complexity as VI. Additionally, R II significantly outperforms the VI algorithm and its accelerated versions, particularly when the discount factor is close to 1. This observation can be partially explained by the fact that the proposed RI-VI algorithm forms an approxi- mation of the inverse of the "Hessian". i.e., (I (I->Pk)
The complete description of the proposed R1-QL algorithm is provided in Algorithm 2. We again note that the nor- malization is only introduced to avoid the accumulation of numerical errors. The following result discusses the conver- gence of the proposed algorithm.
by incorporating its largest eigenvalue 1_1 A more detailed comparison of the algorithms is provided in Appendix B.2.
Theorem 4.2 (Convergence of RI-QL). The iterates qu of the RI-QL Algorithm 2 converge to the optimal Q- function a* = T(q") almost surely with at least the same rate as QL.
6

---

Rank-One Modified Value Iteration
R1-VT Anderson-VT Nesterov-VT
Graph Ratecco mire 10-05
Voke IIDE (2-33
Ind entr Seadn
10
30"
11F
20
10
10"
Perento
Ecrebto
10
10
10
10
6.92
0.99
0.299
0.55
Figure 1: Planning algorithms the median number iterations required for cach algorithm to reach fixed error threshold across four discount factors y the two MDPs
* Zap QL - R1-QL + Sppeedy QL -
QL
Graph
Graph
Gameet HDP
Carnet
Volue OF
1074
10"4
10'7
10
Figure 2: I Learning algorithms - the median error values achieved by each learning algorithm over course of 5000 iterations across four discount factors y for the two MDPs.
Learning Algorithms. In the learning experiments, re- port the Bellman and value errors of the algorithms trained in synchronous fashion, following the methodology outlined in (Ghavamzadeh et al., 201 1), ensuring consistent evalua- tion. In synchronous learning, in each iteration k, sample ~ P(-ss, a) of the next state generated for each state- action pair (s, a) E S x A and the action-value function q: updated in all state-action pairs; see the update rule in QL algorithm (5) and R1-VI Algorithm 2. All the learning algo- rithms the same samples generated through the training. Besides the proposed R1-QL Algorithm 2, we report the performance of Speedy QL (Ghavamzadeh et al., 201 I), Zap QL (Devraj & Meyn, 2017), and the standard QL (5) in Garnet and Graph MDPs for several discount factors; see Appendix B.1 for the update rule of Speedy QL and Zap QL. We each algorithm using the same step-size sched- ule (= namely, linearly decaying d 1/(1 + k). to ensure fair comparison.
crease in the discount factor ";; see Figure 2. Regarding per iteration complexity, R1-QL has the same time and memory complexity as QL and Speedy QL. In contrast, Zap QL. due to the inherent full-rank matrix inversion, incurs higher time and memory complexity. Albeit Zap QL can be efficiently implemented with lower complexity, typically exhibits higher computational cost in practice. comprehensive analysis of the error trajectories observed during training provided in Appendix B.2.
6. Limitations and future research directions
We finish the paper by discussing some limitations of the proposed rank-one modification of the VI and QL algo- rithms along with some future research directions.
Let start by noting that the provided theoretical results in Theorems 3.3 and 4.2 guarantee the convergence of the proposed algorithms with the same rate as the standard VI and QL algorithms. However, our numerical experiments with Garnet and Graph MDPs in Section 5 show that the pro- posed algorithms have a faster convergence rate compared to standard VI and QL and their accelerated versions. This gap can be explained by the fact that our proof technique does not exploit that the vectors dj and d, used the update rule are specifically constructed to approximate the station- ary distribution of the Markov chain induced by the greedy policy (see Appendices A.3 and A.4 for details). That is, the
Figure 2 shows the final error values after running each algorithm for 5000 iterations. RI-QL achieves comparable or lower error values across both MDPs. contrast to the other algorithms, R1-QL consistently maintains similar level of error values across various discount factors, particu- larly at higher discount factors a characteristic attributed to Policy Iteration (PI) algorithms. It is worth mentioning that since both Zap QL and RI RI-QL estimate (I - >PPx)= using the samples, they behave more robustly against the in-

---

Rank-One Modified Value Iteration
convergence of RI-VI and RI-QL algorithms is guaranteed for any choice of dj E A(S) and dę E A(S x A). In fact, when the stationary distribution concentrates on a sin- gle state, as happens when there is absorbing state with zero reward, the second term in the RIVI update rule (12) vanishes. Appendix B.3 provides an empirical analysis in Gridworld (Sutton & Barto, 2018), which includes an ab- sorbing state and thus violates the assumption of Lemma 3.2. Moreover, the provided proof of convergence shows that the greedy policies generated with respect the iterates of R1-VI and RI-QI. are the same those for the standard VI and QL algorithms, respectively (see Lemmas A.2 and A.4). In other words, the proposed algorithms do not affect the speed of convergence to the optimal policy compared to VI and QL. Nevertheless, at least in the case of RI-VI, the faster convergence in the value spaces leads to a faster termination of the algorithm for a given performance bound for the greedy policy. In this regard, let us also note that the mismatch between convergence in value space and policy space also arises in other "accelerated" VI/QL algorithms; see Appendix B.4.
algorithm in the policy evaluation step for unichains (Puter- man, 2014, Sec. 8.6.1). This algorithm can be characterized via the following update rule in the value space: For fixed s E S,
Mk++ uk + Px) Ub+1(s) = 0,
- (T((v)) -us)
where eg is the s-th unit vector and T is now the undis- counted Bellman operator. Now, observe that
Gx - - +
= -I--P,
Ps + (pr: 6, 1)e,)
= =(I -I-1dd + (px + 1)e_
where ps Pe( is the s-th column of Pa and we used the approximation Ps ~ 1d, in the last equality. The matrix inversion can then be handled efficiently using the Woodbury formula. However, the convergence of this algorithm and any possible improvement in the convergence rate when dy is approximated via the power method requires further investigation.
Second, the proposed algorithms heavily depend on the structure of the transition probability matrices P3 and Ps and their rank-one approximation using the corresponding stationary distributions. This dependence particularly hin- ders the application of the proposed algorithms to generic function approximation setups in solving the optimal con- trol problem of MDPs with continuous state-action spaces. We note that a similar issue for the Zap Q-leaning algo- rithm (Devraj & Meyn, 2017) has been successfully ad- dressed in (Chen et al., 2020).
Acknowledgements
The authors would like to thank the reviewers for their useful comments. This work was partially supported by the Horizon Europe Pathfinder Open project RELIEVE- 101 101099481 and by the European Research Council (ERC) project TRUST-949796.
Third, note that the proposed RI-QI. algorithm 2 is synchronous algorithm that updates all state-action pairs (s. a) E S x A of the Q-function qu at each itera- tion k. This algorithm can be modified in a standard fashion for the asynchronous case. However, the provided conver- gence analysis can not be extended for the corresponding asynchronous algorithm in a straightforward manner. More- over, the straightforward asynchronous implementation of R1-QL leads to (mm) per-iteration complexity for up- dating a single component (s, a) E S x A at each iteration k; which is higher than the (m) per-iteration complexity of the standard asynchronous QL algorithm. We note that the Zap Q-leaning algorithm (Devraj & Meyn, 2017) also suf- fers from this issue. Addressing these issues requires a more involved analysis and modification of the proposed algo- rithm in the asynchronous case, which we leave for future research.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Anderson, D. G. Iterative Procedures for Nonlinear Integral Equations. Journal of the ACM (JACM), 12(4):547-560, 1965.
Archibald, T. McKinnon, K., and Thomas, L. On the Generation of Markov Decision Processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
Bertsekas, D. Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control. Athena Scientific, 2022.
Finally, the basic idea of the proposed algorithms can also be used for developing the rank-one modified version of the existing algorithms for the average cost setting. For example, consider the PI algorithm that uses the relative VI
Bertsekas, D. A Course in Reinforcement Learning. Athena Scientific, 2023.
8

---

Rank-One Modified Value Iteration
Chen, S., Devraj, A. M., Lu, F., Bušić, A., and Meyn, S. Zap Q-Learning with Nonlinear Function Approximation. In Advances in Neural Information Processing Systems, 2020.
Kearns, M. and Singh, S. Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms. In Advances in neural information processing systems, volume 11, 1998.
volume 33, pp.
Kolarijani, M. A. S. and Mohajerin Esfahani, P. From Optimization to Control: Quasi Policy Iteration. arXiv preprint arXiv:231 1. 1.11166,1,,, 2023.
Devraj, A. M. and Meyn, S. Zap Q-Learning In Advances in Neural Information Processing Systems, volume 30, 2017.
Kushner, H. and Kleinman, A. Accelerated Procedures for the Solution of Discrete Markov Control Problems. IEEE Transactions on Automatic Control, 16(2):147-152, 1971.
Devraj, A. M., Bušić, A., and Meyn, S. On Matrix Mo- mentum Stochastic Approximation and Applications to Q-Learning. 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 749-756, 2019.
Lee, and Ryu, Accelerating Value Iteration with An- choring. In Advances in Neural Information Processing Systems, volume 36, 2024.
Even-Dar, E. and Mansour, Y. Learning Rates for Q- Learning. Journal of Machine Learning Research, (1):1-25, 2003.
Lee, J., Rakhsha, A., Ryu, E. K., and Farahmand, A.- M. Deflated dynamics value iteration. arXiv preprint arXiv:2407. 10454, 2024.
Gallager, G. Discrete Stochastic Processes. 2011.
Gargiani, M., Zanelli, A., Liao-McPherson, D., Summers, T., and Lygeros, Dynamic Programming Through the Lens of Semismooth Newton-Type Methods. IEEE Con- trol Systems Letlers, 6:2996-3001, 2022.
Nesterov, Y. A Method for Solving the Convex Program- ming Problem with Convergence Rate (1//k²). Doklady Akademii Nauk SSSR, 269(3))543-544 1983.
Geist, and Scherrer, B. Anderson Acceleration for Rein- forcement Learning. preprint 1809 2018.
Porteus, E. L. and Totten, J. C. Accelerated Computation the Expected Discounted Return in a Markov Chain. Operations Research, 26(2):350-358, 1978.
Ghavamzadeh, M., Kappen, H., Azar, M., and Munos, R. Speedy Q-Learning. In Advances in Neural Information Processing Systems, volume 24, 2011.
Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
Golub, G. H. and Van Loan, C. F. Matrix Computations. JHU Press, 2013.
Puterman, M. L. and Brumelle, S. L. On the Convergence
Policy Iteration in Stationary Dynamic Programming. Mathematics of Operations Research, 40 (1):66669, 1979.
Goyal, V. and (eand-Céément,)) J. to Accelerated Value Iteration. Operations Research, 71 (2):517-535,
Approach
Rakhsha, A., Wang, A., Ghavamzadeh, M., and Farahmand, A.- Operator splitting value iteration. Advances in Neu- ral Information Processing Systems, 35:38373-38388 2022.
Grand-Clément, J. From Convex Optimization to MDPs: A Review of First-Order, Second-Orde and Quasi-Newton Newton Methods for MDPs. preprint arXiv:2104. 10677, 2021.
Hager, W. W. Updating the Inverse of Matrix. SIAM Review, 31(2):221-239, 1989.
Ruppert, D. A Newton-Raphson Version the Multivariate Robbins-Monro Procedure. The Annals of Statistics, 13 (1):236-245, 1985.
Halpem, B. Fixed Points of Nonexpanding Maps. Bulletin of the American Mathematical Society, 73(6)9557-91,, 1967.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT press, 2018.
Jaakkola, T., Jordan, M., and Singh, S. Convergence of Stochastic Iterative Dynamic Programming Algorithms. In Advances in neural information processing systems, volume 6, 1993.
Szepesvári, C. Algorithms for Reinforcement Learning. 2009.
Tsitsiklis, J. N. Asynchronous Stochastic Approximation
and Q-Learning. Machine learning, 16:185-202, 1994.
Kamanchi, C., Diddigi, R. B., and Bhatnagar, S. General- ized Second- OrddrrrOrrrrr Value Iteration in Markov Decision Processes. IEEE Transactions on Automatic Control, 67 (8):4241 4247, 2022.
Wainwright, M. Stochastic Approximation with Cone-
Contractive Operators: Sharp foo Bounds for Q-Learning. arXiv preprint arXiv: 06065, 2019.

---

Rank-One Modified Value Iteration
Watkins, J. and Dayan, P. Q-Learning. Machine Learning, 8(3):279-292, 1992.
Weng, B., Xiong, H., Zhao, L., Liang, Y., and Zhang. W. Finite-Time Theory for Momentum Q-Learning In Un- certainty in Artificial Intelligence (UAI), pp. 665-674, 2021.
Zhang, J., O'Donoghue, B., and Boyd, S. Globally Con- vergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations. SIAM Journal on Optimization, 3004):1 2020.
10

---

Rank-One Modified Value Iteration
A. Technical Proofs
A.1. Proof of Lemma 3.1
We begin by providing two basic results on MDPs, First, recall that given policy x, the value e of solves the (Bellman consistency) equation (Puterman, 2014, Thm. 6.1.1)
2" (s) c² (s) + E, (aTe))
[
E.
Hence, we have
v" (I-
(17)
Moreover, the definitions of the Bellman operator in (3) and of the greedy policy in (6) imlpy that
T(v) c pd v,
E R".
(18)
Recall PA = p** Using these two results, we have at each iteration of the PI algorithm (7),
uk+1 = - = v"' = (17) (I - Pp)) c (18)
7Px) (T((kk) - -Ppu
(I - - (T(wx) (T())))((())) - Uk + (I - PPP))uk
Uk + (1 (4 - vz).
This concludes the proof.
A.2. Proof of Lemma 3.2
Let (px)== be the eigenvalues of Ps such that lpil 2 |02| 2 ... |pal- Since Pa is row stochastic matrix, we have P1 = 1 (Gallager, 2011, Thm. 3.4.1), Moreover, the assumption that Ps is irreducible and aperiodic implies that lps| < for all * 1 (Gallager, 2011, Thm. 3.4.1), that is, P = is the unique eigenvalue of Px on the unit circle in the complex plane and all other eigenvalues inside the unit disc. The unique (up to scaling) right and left eigenvectors corresponding to #ı are the all-one vector and the stationary distribution dę. From these results follows that Ps 1dg the unique solution of (11).
A.3. Proof of Theorem 3.3
For each iteration A: 2 of the RI-VI Algorithm 1, we have
Uk+1 T(vx) + ag
7 1- (ds, T(vu) vk),
(19)
aAk
where dj A(S) an approximation of the stationary distribution of the MDP under the greedy policy with respect to Vp- We start with analyzing the effect of constant shift in the argument of the Bellman operator.
Lemma A.1. For all and E R", we have
T(o + al) T(v) + 70..
Proof. For each S, we have
[T( + a1)](s) = min
c(s,a)+ + Σ P(s (s)0
aEd
el
=7 + min
c(8,a)+ + Σ P(s ((8t(s)0)00(5)
asA
steS
= 7 (s)))(ss.

---

and Rank-One Modified Value Iteration
We next the preceding result provide alternative characterization of the iterates of RI-VI in (19).
Lemma A.2. For each & 2 O, the iterates in (19) are equivalently given by
Uk+1 -T (20) + 8x+11 [k+1 > + ark. with Su 0.
Proof. (Proof by induction.) Consider k = 0 and observe that
TTwb) + 811,
with 31 = 7/00 + og = Og- Next, for some 2 and (3 E IR, assume ty = (vo) + Bc1. Then,
4k+1 T(xx) + ax T + B.1) a+ (((+t) + + agg1,
where the last equality follows from Lemma A.1. Therefore.
Uk+ T((+1)))))))))) (vo) + (r3x ax)1 ((++1) + B,411,
which concludes the proof.
We now employ the preceding lemmas to provide an alternative characterization of the constant shifts og in the RI-VI updates in (19).
Lemma A.3. For each k 2 0, one has
1 1-9 de,, (w)) - (oo) 7Bk-
Proof. From Lemma A.2, we have
Uk (T)) 3,1, k 0, 0,1,.... .....
(Notice that for 0, the preceding equation simply implies un- = uo since (() is the identity operator and Bo = 0.) Then, from Lemma A.1, follows that
T(v:) = T(T(() + Bx1) = -T( + 7.x1.
Thus,
T(w)) Ub = (T(+1) (c))) - 33
(dz. T(Vs) - -bk) = (de, (1++ (())) (1 3e 1) = -de, (1++) (vo)) - B),
where we used d3 E A(S) (i.e.. (ds, 1) = in the second equality above. Therefore, for ag (19), have
1 1-7 dR. ((++1) -T()( -78k.
This completes the proof.
Now, observe that plugging in og from Lemma A.3 in the update rule of Lemma A.2 leads to
U/+1 ((b+))(oo)) 7 (de, ((k+))( (T)) 1, k 0,
(20)
12

---

Rank-One Modified Value Iteration
Then, using the fact that 8* T(v*) and the Bellman operator is 7-contraction in the co-norm, have
uk+1 100 T (vo) (vo) T((")
1 (dx, T(h+ (20) T (T()(()))))))
< T(at -T(*))
+ 1-7 (dx: ((o+)) TT (v)))))))
?
- 7 x+1 1100 001 +
?
( (vo) (T((
1 1-9
g x+1
s xh1 1110
001120
+
I(vb) -oll
1
s s (1|00 - 001l
-0"
+ 1-7
(T(p)) - v00loo ).
That is, 0k - v² as k oo linearly with rate ?.
A.4. Proof of Theorem 4.2
Let us begin with recalling the definition of the empirical Bellman operator
Tx (q) a) == c(s, a) + min q( a a EAA
(21)
where 8x5 ~ ((||s,a) a), that is to say g + is sampled according to the law P(.|8, a) at iteration k. From this definition, immediately follows that
Tx a1) (T))) ra1, VaER, q S
RE
(22)
Also, recall that each iteration & 2 of the RI-QL Algorithm reads as
ak+1 = (1 - Aa + As Tx(k)) + oz
Aa ( 1-7
7 (dx. Tx(qu) -qt).
(23)
where de A(S A) is an estimation the stationary distribution of the state-action transition probability matrix of the MDP under the greedy policy with respect to qt. Let us also consider the standard QL iterates
QL a
(1 Axx >x) + A Ta(a O1.).
1 = 0, 1,...,
with the same initialization g0th qo and empirical Bellman operator (-(-) for all & as the R1-QL algorithm (23).
The first result concerns alternative characterization of the iterates in (23).
Lemma A.4. For each k 2 0, the iterates of R1-QL algorithm (23) equivalently read as
ak+1 -h++1 + Bk+11
QL
(24)
Bk+1
(1 >x) + TdEBR + ag, with 3o
Proof. (Proof by induction) For ls = 0, since 40 = qu. we can write
qi (1 >n)go + No Tx + agl
(1 A0)go
QL + Tx 0L ael
qi 3,1,
13

---

Rank-One Modified Value Iteration
where ogg Assume next 9h
4% + 1x1 for some l: 2 0. Then, it follows that
QL.
(1 AR 9 X₁ (g + 0g1
4k+1
(1 (4 QL Bg1) + > T QL + B₂.1) 1) + 0r.1
(22) (1 (ax QL B₂1) + > (Tx(9:)
OL) + 7,3311 + a+
(1 )E
QL + bE (9 0 + ((1 3x) + 7dABA + ax)
QL 9 + 1 1. This concludes the proof.
We next provide useful characterization of the constant shifts in the RI-QL update rule (23). Lemma A.5. For each k 2 0, one has
(1 7 ( (di, Tu((ph)) ( 7>x.3k-
an Aa 1
Proof. From Lemma A.4 and since qo = qu and 30 = 0, we have
QL + 941, k 0,
qk = qs
Hence, (22) write
(x(g)) (x
QL + 3x1) = Tx(qit + 7.,11
As result,
(x()s) qr: Tx(g
QL) + 7Bx1 4:
QL B&
= -Tx(ah) 00 - qb
- 3
and
(u.. TT(gk) - qqk) = (ds, Tx(9
0l)
9k
QL
(1 7) 1) - (1 7)
= (ds. Te (g
Q1
QL
9k
where we use the identity (dz, 1) 1 in the second line since d, E ASS x A). Recalling the definition of ag in (23), one thus have
as >x 7 )d Tu(9 4b OL) 72t.3.
Plugging the expression for ag from Lemma A.5 into the update rule of Lemma A.4, we derive the iteration
Bx+1 - -1 + A 7 - (d Tx OL,
(
OL)
k = 0, 1...,
(25)
initialized by 96=- O. Next, using the convergence of QL, we show the convergence of Bg: Lemma A.6. The iterates Bu in (25) converge to zero almost surely.
Proof. Define 31.0 32.0 and consider the iterations
Bl = 11-)888 + Au
di. Te(a) Q1,
T(q: QL 1), 4b OL)
(26)
32 = (1 (1-Aa)82,4 + d
7
(d.. Tx(q QL)
(27)
14

---

Rank-One Modified Value Iteration
for 0, ..,,, that Bx F + 32,x for all & 2 O. In what follows, and converge q' "(q*) almost surely (Tsitsiklis, 1994, Thm. 4). First, observe that the iteration (26) converges to almost surely using (Tsitsiklis, 1994, Lem. 1) and the fact that (see also (Tsitsiklis, 1994, Sec. 7))
QL the fact that the QL iterates q are bounded
Fe (de: Tx ) T((gk
})} )
(de; Rez
Tx(9 2 T( 2l
) = 0,
Ft (de: Ta (1k
ol T(q ( )) S Bet
[T(( 2 - T(a (l
)
2 S 1x
Q1
The iteration (27) also converges to zero almost surely since
Σ (TT((e)) - dt -00 ((()))))
82,k+1
Σ
(s a)
(s.0)ESxA
a scaled, weighted average of Cesaro means of the sequences ( 2
Ql [s, a) that converge to zero almost surely
for each (s,a) a) E S x A (recall that A 1/(k + 1) and q" T(q") almost surely).
QL Finally, recall the characterization qr q Therefore, Qs q" almost surely.
+ 3&1 in Lemma A.4 and observe that q QL
q" and 3x. - almost surely.
B. On numerical experiments
B.1. Algorithms
Below, we provide the update rules of the algorithms we employed in our numerical experiments. We adapt the update rules provided by (Kolarijani & Mohajerin Esfahani, 2023) our implementations for the planning algorithms.
Nesterov VI algorithm (Goyal & Grand-Clément, 2022):
1
72
17 +
(Vx 10a--Uh-l 0h-1),
?
1
Wk-
2k +
(T(xx) 2%).
+
Anderson VI algorithm (Geist & Scherrer, 2018): (The following update rule is for Anderson acceleration with memory equal to 1 which corresponds to rank-one approximation of the Hessian.)
24 Uk U4-1s
2/6 T(Vk) -((u-1);
0,
2x (z 2/6) =0
8
2/ (vt-T(mw)
otherwise,
2/. (xt
(1 6x) (Tvw) + 8R T(v
Uk+1
Speedy QL algorithm (Ghavamzadeh et al., 2011): (The following update rule is the synchronous implementation of Speedy QI..
15

---

Rank-One Modified Value Iteration
for (3,0) E X
s ~ P(-ssaa)
=x(8,0) a) c((,,) + min Qx(3 :a*):
a+EA
(s c(s, a)
min a+EA
q aa)),
endfor
h +
9.+1
q: + I+ (zk qs)
I+k (2) =2)).
'ap QL algorithm (Devraj & Meyn, 2017): (The following update rule is also the synchronous implementation
of Zap QL without cligibility trace. The matrix F& E IR |x below denotes the sampled transition matrix at iteration k.)
F3 = BE=00ISSAAMMSSAA
for (8,0) ES
8 P((ss,a),
à + argmin ( (s+ ,at), ateA
[Taqq)](ssa) a(s,a) + min (x - (s, a EA
O(s (3 ,a +)) =1
endfor
Ps P k-1 2 (Fx Pk-1);
(I (--PP)) -Pa)-'(Tx(q))) -u).
g++1 = qk
1+k k
B.2. Extended numerical analysis
In this appendix, we provide the Bellman and value errors observed throughout the iterations of planning and learning algorithms. We run each planning algorithm until the error thresholds in Table are achieved.
Table I: Error thresholds for planning algorithms.
MDP
Error
7 0.9
7
0.9
7
0.9
?
0.9
Garnet
value
10-5
10
10 10-4
10 10-2
Bellman
10-5
10-5
10 10-5
10
Graph
value
10-5
10-1
10-3
10-2
Bellman 10-5
10-5
10
10-4
consider four different values for discount factor 7 across 25 realizations of the Garnet MDP. Note that the planning algorithms are deterministic in nature, hence, the only source of variation in the errors due to the random realization of the Garnet MDPs. Figure shows the range of error values observed within the span of the iterations of the planning algorithms. The solid curve represents the median error values, while the shaded region around the curve indicates the errors between the first and the third quantiles. We follow the same style of presentation in the other figures in this section.
We observe in Figure 3 that Anderson VI has the highest error variance. Furthermore, the error curves for both Anderson VI and Nesterov VI are not monotonically decreasing, which is particularly visible for Anderson VI. This is because the iterations in these algorithms are not necessarily contraction with guaranteed reduction the Bellman/value error.
16

---

Rank-One Modified Value Iteration
R1-VT Anderson-VT Nesterov-V
7=
10
19
7-
0.900
70
10'
Volue 0710
10
Vilue 0114
20
10
10
10-
30'
10'
10-1
10
otin
obin
Bcraton
Dicration
0.9
0.96
0.99
0.999
10'
30"-
30-1
0e 6100
10"2
Be C707
Sclinan C100
10-1
De
10"4
30-4
10
10'
10-1
10:1
10
10
10
10"
10
100 Deration
10
Deration
Figure 3: Comparison of the planning algorithms in Garnet MDP with various y values.
P] R1-VI - Anderson-VI NNsterov-V] VI
7. 0.9
0.95
=- 0.99
TV 0.999
10
10-
1.9
1.2
10
Valve 0/00
Valle 6/10
1.P
Valoo S11 S/0P
10'
10
10:-
10"
10-
10-4
10"1
10"
:0
100
10
107
10
107
107
10
100
10
Deration
The rationn
Teeration
Themstion
Y
7 0.999
10
Am4
10-7
mod 0ri4
Bofrian 0714
30-4
20
10
10
10-9
10-4
30
10-1
20
10-3
10
10:1
10-1
Dheration
Daratton
Barration
Theratton
Figure 4: Comparison of the planning algorithms in Graph MDP with various 7 values.
Nevertheless, in our numerical experiments, both algorithms seem to be convergent. Figure 4 shows the error curves of planning algorithms for the Graph MDP. Here, the non-monotonic behavior of Anderson VI is more apparent as the error values initially increase with an oscillating behavior. Similar to Garnet MDPs, RI-V1 consistently provides lower errors throughout the iterations.
Figure 5 and 6 show the error curves for the learning algorithms in Garnet and Graph MDPs, respectively. In these experiments, we run each learning algorithm with 5 different seeds to marginalize the randomness in the sampling process. We observe that the difference between Zap QL, Speedy QL, and RI-QL is not noticeable at lower values of the discount factors (i.e., 7 I 0.95). However, as the discount factor increases, particularly at γ = 0.999, the gap between the error values increases. At higher values of the discount factors, RI-QL consistently yields lower error values, while QL struggles to minmmize the errors due to the linearly decaying step-size λy. Furthermore, we observe that Zap QL displays higher error
17

---

Rank-One Modified Value Iteration
Zap QL RI-QL
Speedy QL - QL
7=
0.99
0.900
10
1.0
10.00 07104
Vosue
207
10"4
20"
10"1
10'9
10-4
10-3
10
10-1
otio
obin
Boraton
Dicration
0.9
0.96
0.99
0.999
10
10P
Se C100
10
Sc C100
30
10
10
10
10'
10
10
10'
10'
10
10'
10
10
'00"
10
Deration
Figure 5: Comparison of the learning algorithms in Garnet MDP with various y values.
Zap QL - RI-QL- - -Speedy QL - QL
- 0.9
- 0.95
7- 0.99
7y 0.980
10
20
Value ee
10
Value-0r1
Val.2 16
10-4
10-4
30"4
10"4
10"0
10
100
100
100
Decotin
Do otion
Deration
Berotion
y
7
7y
0.999
10
10
100
20
Buliial 0111
mniman
10
30
Deeratin
Demation
Deematio
Reentton
Figure 6: Comparison of the learning algorithms in Graph MDP with various y values.
variance, which may be due to the inversion of the estimated "Hessain" (I->P). In contrast, R1 RI-QI, exhibits considerably lower variance, despite implicitly performing a similar inversion. We argue that the lower error variance observed with RI-QL is due to the low-rank approximation of the transition probability matrix via estimation of the corresponding stationary distribution.
B.3. Reducible MDPs
To illustrate RI-VI's behavior in a reducible MDP, we replicate the comparison from Section within the Gridworld environment of (Sutton& & Barto, 2018), which inherently contains an absorbing state. We consider two Gridworld variants:
1. Absoring Gridworld, in which the absorbing state yields positive reward.
18

---

Rank-One Modified Value Iteration
2. Terminal Gridworld, in which the absorbing state grants zero reward.
Here, "reducibility" refers to the Markov chain induced by the optimal policy. Note, however, that even the absence of an absorbing state, where all actions from a state lead back to itself, non-optimal policy may still produce a reducible chain in Gridworld.
PI -th- R1-VI -i- Anderson-Vi + Nesterov-V -+-V
Absorbing Griettordd
Absorting G-Weoordd bull
Terminal GridWorid vi.s eror 4...
Terminal GriWerid bettran pre
Vaku unter
10"
10"
10P
207
207
10*
302
20-
10"
10
10
(V)
(V)
Figure 7: Comparison of planning algorithms on two reducible Gridworld MDP instances, one with a zero-reward absorbing state and one with a positive-reward absorbing state, across various y values.
In Searrinng-Grdworllee (left side of Figure 7), RI-VI yields the lowest value and Bellman error, apart from Pl, across all 7 values. However, in Terminal Gridworld (right side of Figure 7), RI-VI performs slightly worse than the other accelerated algorithms. This is explained by the fact that under the optimal policy, the stationary distribution concentrates on the absorbing state, which provides zero reward and hence zero Bellman error when the values are initialized to zero. Consequently, the second term in the RI-VI update rule (9) vanishes. In contrast, in Absorbing Gridworld, the Bellman error at the absorbing state is not immediately zero, hence the second term in RI-VI contributes to improve convergence.
B.4. Policy performance
Throughout Section 5, we compared both the planning and learning algorithms, including our proposed RI VI and RIQL methods, using the value and Bellman error metrics. However, rapid convergence in value does not necessarily translate into equally rapid convergence in policy space, which is the ultimate criterion of policy optimization. this section, we present a comparative analysis based on the policy evaluation metric the Graph and Garnet MDPs.
Figure 8 shows that the planning algorithms yield exactly the same policy evaluation, except for PI and Anderson- VI. Anderson- VI initially struggles to find the optimal policy due to instabilities in the value space (shown in Figures 3 and 4), but eventually converges to the optimal policy. In both MDPs, policy convergence occurs in fewer than five steps, except for Anderson-Ve VI, whereas convergence in the value space requires several orders of magnitude more steps.
The convergence of policies among the learning algorithms is more varied than that of the planning algorithms. Figure shows that, for the Graph MDP, all algorithms except Zap-QL. achieve almost identical performance, converging within five steps for every value of y. In the Gamet MDP, convergence requires more steps, and improvements over iterations slower.
In both Figures& 8 and 9, the proposed RIVI and RIQL algorithms match the policy performance of VI and QL, respectively, across all iterations. Moreover, VI in the planning setting and QL in the learning setting produce among the highest policy performance observed across both MDPs, despite exhibiting the slowest convergence in the value space.
19

---

Rank-One Modified Value Iteration
PI R1-VI Anderson-V] Nesterov-VI -V[
Graph MDP
Groph HDP
Groph MDP
Graph HDP
diseet
2lccat 1d)
dipert (g) C.99
1000
Polor taa
Polty EVB Lation
200
1239
108
100
1993
100
0.000
1000
1000
Barsttons
Bwrstions
berafions
Games Cbocust (1) 3.55
Garnet
Zaccurt To m..0
ducoerLo - E.99
Policy ovaluaaon
Pulty eutusain
6000
544
5.2
12.5
Borations
Rorations
Figure 8: Comparison of the value of the greedy policy produced by various planning algorithms (RI-VI, VI, Pl, Anderson VI, and Nesterov-VI VI) on Garnet and Graph MDPs over range of discount factors y. Note that RI-VI, VI, and Nesterov-VI yield essentially overlapping results.
QL Zap QL Speedy RI-QU
Graph MDP
Graph MDP Chocum It 3.55
Graph HDP
Graph HDP
Slocuet 0..0
duperiog 0,929
1000
Pito ereuatoo
Potcyy Manto
600
200
100
1000
10
1000
1008
Ranations
Berattons
Berations
Barations
VDP
Gamett Obocust (s) 3.05
Garnet
Gornet MDP
dimoert. -.
20rout 0.00
shoper - 5.22
0.2
17.4
0.0
Polcc oxtuanos
12.2
Rolcy raattarter
21.0
520
32.4
Rorations
Rerttons
Figure 9: Comparison the value the greedy policy produced hy RI-QI. and QL learning algorithms on Garnet and Graph MDPs as a function of the discount factor y. Results for RI-QL and QL coincide. The y-axis shows the median policy pelicy-evaluation score of the corresponding greedy policies across 5 different seeds.
20


Reviews:
[{"review_id": "ypAG0xf7JR", "reviewer": "Reviewer_BP3b", "summary": "The paper introduces an accelerated value iteration algorithm by using a rank-one approximation of the transition dynamics in policy iteration. They further extend the algorithm to RL and introduce R1-QL. It is theoretically shown that these algorithms converge at least as fast as their conventional counterparts. Empirically, it is shown that the algorithms enjoy a faster convergence rate.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. Here is our response:\n\n__R1. Missing references:__ We thank the reviewer for bringing these papers to our attention; we were not aware of them. We will update the manuscript to include them and the following discussion:\n\nRef. [1] considers the matrix splitting method for solving the _policy evaluation_ problem, i.e.,  the linear equation $v^{\\pi} = (I-\\gamma P^{\\pi})^{-1} c^{\\pi}$, using some given or estimated “cheap-to-access” $\\hat{P}^{\\pi}$ instead of $P^{\\pi}$. The method requires computing/estimating another cost function $\\bar{c}^{\\pi}_v =c^{\\pi} +\\gamma (P^{\\pi} - \\hat{P}^{\\pi}) v$. We also focus on computational complexity in the development of our algorithm. However, we are proposing a specific rank-one approximation $\\hat{P}^{\\pi}$ based on stationary distribution in the PI update rule, which leads to a completely different iterative algorithm. \n\nThere are more similarities between our work and Ref. [2]. In particular, they suggest using a rank-$s$ approximation $\\hat{P}^{\\pi}$ based on the first $s$ eigenvalues (in magnitude) of $P^{\\pi}$ in the matrix splitting scheme of Ref. [1]. However, they only focus on _policy evaluation_ problem. In particular, the rank-one DDVI proposed for the _control (i.e., policy optimization) problem_ uses a _fixed_ approximation $\\hat{P}^{\\pi}$ over the entire iterations of the algorithm. Actually, the improvement provided in [2, Thm. 4.1] is only local and happens when the greedy policy is already optimal. Moreover, we would like to point out that there are two reasons why we did not consider higher order (i.e., $\\geq 2$) approximations based on the eigenvalues of $P^{\\pi}$: (1) the left eigenvector corresponding to the first eigenvalue has certain properties which allow for its estimation directly from the samples without constructing an estimate for  $P^{\\pi}$ which is already exploited in R1-QL ; (2) it restricts the extension of the proposed algorithm to continuous state-action MPDs. \n\nFinally, regarding the existing similarities, as mentioned, we were unaware of [2] till now. Actually, an earlier version of our manuscript, including these similarities, was submitted to Neurips 2024 on 22 May 2024, prior to the arXiv date of [2] (15 July 2024). To preserve anonymity, we cannot share our OpenReview submission details here but would be happy to provide them to the (senior) AC or other conference program members if needed. \n\n__R2. Evaluation metric:__ The reviewer is correct. Indeed, the greedy policies generated by R1-VI are the same as the counterpart VI in each iteration. In this regard, we would like to point out the following: \n\nFirst, despite being a poor proxy for policy evaluation [3], the Bellman error is the most widely used metric because of its computational efficiency – there is no extra cost in using the Bellman error as the termination condition. With that in mind, R1-VI leads to a faster termination of the algorithm for a given performance bound for the greedy policy.  \n\nSecond, the mismatch between convergence in value space and policy space also arises in other \"accelerated\" VI/QL algorithms. In Figure 1 (link below), we report the value of the greedy policies over the iterations of the algorithms of Section 5 of our paper. As can be seen, Anderson/Nesterov -VI and Speedy/Zap-QL also suffer from the same limitation.\n\nThird, the asynchronous implementation of  R1-QL algorithms leads to different policies than QL. As shown in Figure 2 (link below), there is also an improvement in the performance of the greedy policy. As we have pointed out in Section 6 of our paper,  we are currently working on theoretical guarantees for the convergence of this asynchronous algorithm. \n\n__R3. Claims and evidence:__  The assumption of Lemma 3.2, although not required for the convergence of the proposed algorithms, is indeed critical for observing an improved rate of convergence. We have now a better understanding of why this is the case. Our recent theoretical developments show that the speed-up happens only for _aperiodic and irreducible_ MDPs during the _policy evaluation_ step, in line with results of Ref. [2]. Our numerical simulations with a GridWorld environment with an _absorbing state_ (so that the MDP is not irreducible) confirm this; please see Figure 3 (link below). Indeed, existence of an absorbing state leads to R1-VI having the same performance as VI. We will update the manuscript to include this discussion. \n\n__Figures__\n\nFigure 1: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/policy_evaluations.pdf?v=82f0f88e\n \nFigure 2: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/asynchronous_learning.pdf?v=ef94411a\n \nFigure 3: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/reducible_maze.pdf?v=40f97d29\n\n__References__\n\n[3] Fujimoto et al. Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error. ICML, 2022.", "claims_and_evidence": "The theoretical results only show the algorithms have at least the same convergence rate as the conventional VI. The claim of acceleration is only shown through experiments. The experiments, however, are limited to synthetic artificial environments. A more natural environment like a maze could better show​ the viability of the algorithm in real environments. For example the conditions on aperiodicity and irreducibility in Lemma 3.2may be critical to observe the acceleration.", "methods_and_evaluation_criteria": "My first main issue with the paper is that it measures the algorithms' performance in the value function error. This is not the standard metric for the control problem in RL. The real metric of interest is the return of the policy obtained by the algorithms. This is very critical in this case as it can be proven that the improvements introduced by the algorithm to value function accuracy, does not translate to better policies. At all iterations, the value function is provably just a constant factor different from the value function obtained with VI. Therefore, the sequence of greedy policies will remain the same as VI.", "theoretical_claims": "The results appear correct to me.", "experimental_designs_or_analyses": "See \"Methods And Evaluation Criteria\"", "relation_to_broader_scientific_literature": "The problem studied by the paper is very significant and interesting. The paper does a good job with the literature review except for two key papers discussed in the next section.", "essential_references_not_discussed": "There are two very related papers that need to be discussed. R1VI is a special case of OS-VI [1] when the approximate dynamics $\\hat P$ is chosen to be the rank-one approximation. I also think R1VI is very similar if not identical to Rank-1 DDVI [2]. DDVI also uses the rank-one approximated dynamics, its value function is always a constant factor different from VI, and proves acceleration when the stationary distribution is unique (largest eigenvalue of dynamics has no repetition).\n\nI appreciate the perspective the paper provides in arriving at R1VI very unique and potentially more generalizable than the above papers. Some more discussions may help the paper.\n\n\n[1] Operator Splitting Value Iteration. NeurIPS 2022\n[2] Deflated Dynamics Value Iteration. Arxiv", "other_strengths_and_weaknesses": "I highly appreciate the ideas and perspectives the paper provides. The paper is well-written and easy to read, and addresses an important problem.\n\nFor weaknesses, see the missing references and evaluation sections.", "other_comments_or_suggestions": "None", "questions_for_authors": "Please see weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oOn3V7nrvo", "reviewer": "Reviewer_r11J", "summary": "In this paper, the authors have proposed algorithms for planning and learning in MDP based problems. The proposed algorithms use a rank-one approximation of the transition probability matrix in the policy evaluation step. It uses the stationary distribution of the transition probability matrix, approximated using power method.  Theoretical convergence is provided for both the algorithms. It is proved that the convergence rates and computational complexities are same as those of the value iteration algorithm in the planning setting and Q learning in the learning stetting. Experimental results are provided to support the theoretical findings and faster convergence achieved.\n\n## update after rebuttal\nThe response addresses most of my concerns. I have raised my score to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. Here is our response:\n\n__R1.__ Yes. The proposed algorithms can be extended to the average cost setting. For example, consider the PI algorithm that uses relative VI for policy evaluation for unchains proposed in [4, Sec. 8.6.1]. We have managed to characterize that algorithm via the following update rule in the value space: For a fixed $s\\_0\\in\\mathcal{S}$, \n$$ v\\_{k+1} = v\\_k + \\big((I-P\\_k)(I – e\\_{s\\_0} e\\_{s\\_0}^{\\top})+e e\\_{s\\_0}^{\\top}\\big)^{-1} (T(v\\_k) – v\\_k), \\quad  v\\_{k+1}( s\\_0) = 0.$$\nAbove, $ P\\_k $ is again the transition matrix of greedy policy w.r.t. $v\\_k$, $e$ is the all-one vector, $ e\\_{s\\_0}$ is the ${s\\_0}$-th unit vector, $T$ is the undiscounted Bellman operator. Now, observe that \n$$\nG\\_k = \\big((I-P\\_k)(I – e\\_{s\\_0} e\\_{s\\_0}^{\\top})+e e\\_{s\\_0}^{\\top}\\big)^{-1} = \\big(I-P\\_k + (p\\_k -  e\\_{s\\_0} +e) e\\_{s\\_0}^{\\top}\\big)^{-1} = \\big(I - e d\\_k^{\\top} + (p\\_k -  e\\_{s\\_0}+e) e\\_{s\\_0}^{\\top}\\big)^{-1},\n$$\nwhere $p\\_k = P\\_k(\\cdot, s\\_0) $ is the $ s\\_0$-th column of $ P\\_k $ and we used the approximation $ P\\_k \\approx e d\\_k^{\\top}$ in the last equality. The matrix inversion can then be handled efficiently using the Woodbury formula. However, the convergence of this algorithm and any possible improvement in the convergence rate when $d\\_k$ is approximated via the power method requires further investigation. We really appreciate the reviewer bringing this to our attention; we will consider and add the average cost case to the future research direction.  \n\n__R2.__   The reason is that in the VI algorithm and, similarly, in the proposed R1-VI algorithm, the greedy policy $\\pi\\_{v\\_k}$ usually stays the same over multiple iterations of $v\\_k$. This translates to the transition matrix $P\\_k$ being the same over multiple iterations $k$; hence, the R1-VI algorithm effectively performs multiple steps of the power iteration. To show this effect, in Figure 4 (link below), we report the performance of R1-VI with more than one step of power iteration in each iteration $k$ for the same numerical simulations as in Section 5 of the paper.  As can be seen, there is a minimal improvement in the performance of R1-VI. \n\nRegarding the second point on the transition probability matrix, we would like to clarify that in randomly generated Garnet MDPs in our numerical simulations, the branching parameter is set such that more than 90 percent of components of the matrices $P\\_k$ are zero. However, the reviewer is correct in the sense that aperiodicity and irreducibility of underlying MDP is critical for observing an improved rate of convergence (although not required for the convergence of the proposed algorithms). Our numerical simulations with a GridWorld environment with an _absorbing state_ (so that the MDP is not irreducible and the stationary distribution is a one-hot vector) confirm this; please see Figure 3 (link below) for the result of numerical simulations in which the existence of an absorbing state leads to R1-VI having the same performance as VI. We will update the manuscript to include this discussion. \n\n__R3.__  Recall the line (10) of R1-Ql Algorithm 2: \n$$f = (1-\\lambda\\_k) \\widehat{d}\\_{k-1} + \\lambda\\_k F\\_k^{\\top} \\widehat{d}\\_{k-1}.$$\nObserve that each row $(s,a)$ of the matrix $F\\_k \\in \\mathbb{R}^{|\\mathcal{S} \\times \\mathcal{A}| \\times |\\mathcal{S} \\times \\mathcal{A}|}$ is a unit row vector with exactly one entry equal to one corresponding to the column $(s^+,a^+)$ given by \n$$ s^+ = \\hat{s}\\_k^+ \\sim \\mathbb{P}(\\cdot \\mid s,a),\\quad a^+ = \\hat{a}\\_k^+ \\in \\text{arg} \\min_{a\\in\\mathcal{A}} q\\_k(\\hat{s}^+\\_k,a). $$\nThis means that the $(s,a)$ component of the matrix-vector multiplication $F\\_k^{\\top} \\widehat{d}\\_{k-1}$ is simply $\\widehat{d}\\_{k-1}(s^+,a^+)$. That is, computing $F\\_k^{\\top} \\widehat{d}\\_{k-1}$ requires $O(|\\mathcal{S} \\times \\mathcal{A}|)$, as opposed to $O(|\\mathcal{S} \\times \\mathcal{A}|^2)$.\n\n__R4.__ We reported the median since it is more robust compared to the mean. Figure 5 (link below) reports the mean number of iterations for the same numerical simulations as in Section 5. As can be seen, the results are almost the same to the ones reported in Figs 1 and t of the submitted manuscript. \n\n__Figures__\n\nFigure 3: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/reducible_maze.pdf?v=40f97d29\n\nFigure 4: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/power_iterations.pdf?v=c98470fc \n\nFigure 5: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/mean_values.pdf?v=53d762f3\n\n__References__\n\n[4] Puterman. Markov Decision Processes. 2005.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes. There is one concern regarding why median number of iterations are considered to describe the convergence behavior. I wonder what would be the performance of this approximation in a setting where the transition probability matrix is irreducible and aperiodic but some of the transition probabilities are very small.", "relation_to_broader_scientific_literature": "The proposed algorithms use a rank-one approximation of the transition probability matrix in the policy evaluation step. Theoretical convergence is provided for both the algorithms. It is proved that the convergence rates and computational complexities are same as those of the value iteration algorithm in the planning setting and Q learning in the learning stetting. Experimental results are provided to support the theoretical findings and faster convergence achieved.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Overall, the paper proposes a simple yet elegant idea for a modified value iteration algorithm that provides fast convergence. The paper is well-written and easy to follow. The analysis appears solid and experimental results support the theory well. However, there are some concerns related to some experimental settings and some explanations.", "other_comments_or_suggestions": "Typo: MPDs->MDPs (section A.1)", "questions_for_authors": "1.\tCan these algorithms be extended for the average cost settings? Will the approximation using power method behave differently in such a setting?\n2.\tSome intuitions need to be provided regarding why the best rank one approximation works, even though single iteration of power method is performed in a single step. I wonder what would be the performance of this approximation in a setting where the transition probability matrix is irreducible and aperiodic but some of the transition probabilities are very small.\n3.\tThe remark regarding the exploitation of sparse structure of matrix to derive the time complexity of R1-QL needs more clarity.\n4.\tWhy median number of iterations are considered to describe the convergence behavior? What happens if we switch to mean number of iterations?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ykpbv5GXNk", "reviewer": "Reviewer_vCBY", "summary": "This paper proposes a rank-one modified value iteration algorithm which is a modified policy iteration which approximates the transition dynamics by a rank-one update. The authors prove formal convergence guarantees and demonstrate the algorithm's empirical potential through numerical simulations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. Here is our response:\n\n__R1. Convergence of PI:__ The reviewer is right. In the worst case, the convergence of  PI in the value space is similar to VI, which is linear with rate $\\gamma$ [4, Thm. 6.4.6]. However, under certain conditions, this convergence can be quadratic [4, Thm. 6.4.8]. The required condition is particularly satisfied when the greedy policy $\\pi\\_{v\\_k}$ is optimal. This means that at least locally, i.e., when $v\\_k$ is in some neighbourhood of optimal value function $v_{\\star}$, the convergence is quadratic. Let us also note that the greedy policy $\\pi\\_{v\\_k}$ generated by PI is guaranteed to be the optimal policy after a _finite_ number of iterations, which is polynomial in the size of the state action spaces and the effective horizon $1/(1-\\gamma)$ [5]. \n\n__R2. On periodicity and irreducibility:__ The assumption of Lemma 3.2 (i.e., periodicity and irreducibility) is indeed _not_ required for the proposed algorithms to converge. However, they are critical for observing an improved rate of convergence. We have now a better understanding of why this is the case. Our recent theoretical developments show that the speed-up happens only for _aperiodic and irreducible_ chains during the _policy evaluation_ step. Our numerical simulations with a GridWorld environment with an _absorbing state_ (so that the MDP is not irreducible) confirm this; please see Figure 3 (link below) for the result of numerical simulations in which the existence of an absorbing state leads to R1-VI having the same performance as VI. We will update the manuscript to include this discussion. \n\n__R3. On numerical experiments:__ The examples we used for our numerical simulations borrowed from similar studies that focused on developing new algorithms for finite state-action MDPs; see, e.g., (Devraj et al., 2019), (Goyal et al., 2022), and (Kolarijani et al., 2023). As the reviewer also noticed, to handle challenging real-world applications, we must extend the proposed algorithms to continuous state-action MDPs. As we mentioned in Section 6 of our paper, this extension is one of the future research directions and we are working on.  In this regard, we note that an interesting property of the proposed algorithms is that the extra term in the update rule requires the expectation of the Bellman error/temporal difference with respect  to the stationary distribution. This property can be useful in extending the proposed algorithms for handling continuous state-action MDPs.\n\n__R4. Confusion about the discussion around eq. (15):__ We thank the reviewer for the suggestion. We will update the corresponding part as you suggested to make it clear.\n\n__Figures__\n\nFigure 3: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/reducible_maze.pdf?v=40f97d29\n\n__References__\n\n[4] Puterman. Markov Decision Processes. 2005. \n\n[5] Ye.The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research. 2011.", "claims_and_evidence": "In general yes; however some claims feel a bit handwavy. Could the authors be more specific about what they mean when they say the PI algorithm has a local quadratic rate of convergence? My understanding is that PI empirically converges in fewer iterations; but the worst case iteration bound can be bad. Is this right? \n\nIs the assumption of Lemma 3.2 a bit restrictive? In general, the chain may not be reducible and aperiodic, and such assumptions don't seem necessary to solve the MDP for \\gamma < 1, which is the setting discussed in the prelims. Could the authors explain how the results would work for other MDPs that might not satisfy these assumptions?", "methods_and_evaluation_criteria": "The experiments seem reasonable, but it would be interesting to see improvements on more real-world datasets.", "theoretical_claims": "I skimmed the proofs in the appendix.", "experimental_designs_or_analyses": "The experimental analysis seems reasonable.", "relation_to_broader_scientific_literature": "The paper proposes a variant of value iteration that seems to interpolate between value and policy iteration, and the approach is interesting.", "essential_references_not_discussed": "I am unaware of any similar works thta are not discovered.", "other_strengths_and_weaknesses": "The paper seems to be generally well-written overall, and the numerical experiments seem positive. One possible weakness is that the method might not immediately generalize to infinite state-spaces and function approximation analogs, and the experiments seem to be on somewhat synthetic datasets.", "other_comments_or_suggestions": "The discussion around eq. (15) is a bit confusing, and I had to re-read a few times to understand. It would perhaps be clearer to use approximate equals in the derivation to avoid confusion.", "questions_for_authors": "Please see questions mentioned above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BsFzCnok9u", "reviewer": "Reviewer_TaRN", "summary": "The authors propose a novel algorithm for solving planning and learning problems of Markov decision processes.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments/questions. Here is our response:\n\n__R1. Equation (2):__ The first line of eq. (2) is the definition of the value $v^{\\pi}$ of a control policy $\\pi:\\mathcal{S}\\rightarrow\\mathcal{A}$ as the expected, discounted cost endured by following policy $\\pi$:\n$$\nv^{\\pi}(s) := \\mathbb{E}\\_{s\\_{t+1}\\sim P^{\\pi}(s\\_t,\\cdot)}\\left[\\sum\\_{t=0}^{\\infty}\\gamma^t c\\big(s\\_t, \\pi(s\\_t)\\big)\\middle| s_0 = s\\right],\\quad \\forall s \\in \\mathcal{S}.\n$$\nThe second equality in eq. (2) then follows from the definition above: $ v^{\\pi}$ is the fixed-point of the Bellman consistency operator [4, Thm. 6.1.1], that is,\n$$\nv^{\\pi}(s) = \\[T^{\\pi}(v)\\](s) := c\\big(s,\\pi(s)\\big))+ \\gamma  \\mathbb{E}_{s^+\\sim P^{\\pi}(s,\\cdot)} \\left[ v^{\\pi}(s^+) \\right] ,\\quad \\forall s \\in \\mathcal{S}.\n$$\n\n__R2. Theoretical guarantee for item (3):__ After the submission of this work, we were able to identify the reason for the observed speed-up in the proposed algorithms. Our recent theoretical developments show that the speed-up happens only for _aperiodic and irreducible_ MDPs during the _policy evaluation_ step. Our numerical simulations with a GridWorld environment with an _absorbing state_ (so that the MDP is not irreducible) confirm this; please see Figure 3 (link below) for the result of numerical simulations in which the existence of an absorbing state leads to R1-VI having the same performance as VI. We will update the manuscript to include this discussion. \n\n__R3. Discount factor:__ The discount factor can be seen as a trade-off parameter between short- and long-term costs. That is, by choosing $\\gamma$ to be closer to one, we are putting more emphasis on the costs of steps that are further away in the future. \n\n__R4. Algorithm of eq. (4):__ The VI algorithm of eq. (4) outputs a value function $v\\_k$ upon termination, from which one can generate the greedy policy $\\pi^{v\\_k}$ according to eq. (6). For example, if the termination condition is based on the Bellman error, that is, $\\Vert T(v\\_k) -v\\_k\\Vert\\_{\\infty} \\leq \\epsilon$, the greedy policy is guaranteed to be $\\rho$-optimal (i.e., $\\Vert v^{\\pi^{v\\_k}} – v^{\\star} \\Vert\\_{\\infty} \\leq \\rho$), where $\\rho = 2\\gamma\\epsilon/(1-\\gamma)$.  \n\n__R5. Step (5) of Algorithm 1:__ This step is as follows:\n$$\n\\[T(v\\_k)\\](s), a\\_k \\leftarrow \\min\\_{ a \\in\\mathcal{A} } \\left\\[ c(s,a) + \\gamma  \\sum\\_{s^+ \\in \\mathcal{S}} P(s^+ | s,a) v\\_k(s^+) \\right\\], \\quad \\forall s\\in\\mathcal{S},\n$$\nwith $\\[T(v\\_k)\\](s)$ being the optimal value and $ a\\_k $ being an optimal solution of the minimization problem. We note that $\\mathcal{A}$ is finite, and the minimization is solved via enumeration over $\\mathcal{A}$.\n\n__R6. Numerical simulations:__  All the numerical simulations are with finite state-action MDPs borrowed from the related literature. We note the Graph MDP  is relatively small and has 18 state-action pairs, while the randomly generated Garnet MDPs are relatively large and have 1000 state-action pairs. For the proposed R1-VI and R1-Ql algorithm, we implemented exactly the pseudocodes provided in Algorithm 1 and Algorithm 2, respectively. The update rules of all other tested algorithms are provided in Appendix B.1. All the codes are also made available (link below).  We would be happy to provide more details if further clarification is required. \n\n__R7. Future research directions:__ We think the most interesting future research directions are the ones that address three limitations we discussed in Section 6. Actually, we are currently working on these limitations. We believe we already have the answer to the first limitation, i.e., the reason behind the empirically observed speed-up in the convergence rate for a particular class of MDPs. The next interesting research direction is the _asynchronous_ implementation of the proposed algorithms. We are currently working on the convergence proof of the standard asynchronous implementation of the proposed algorithms with $O(|\\mathcal{S}|\\times|\\mathcal{A}|)$ computational complexity. However, we believe the real challenge (that has not been addressed in similar works such as Zap-QL) is in the development of an asynchronous implementation with $ O (|\\mathcal{A}|)$ computational complexity, i.e., similar to the asynchronous QL algorithm. The most interesting future research direction is the combination of the proposed algorithm with function approximation for handling MDPs with continuous state-action spaces. Finally, one of the reviewers brought the average cost setting to our attention and the possibility of extending the proposed algorithm to that setting. We believe this is also an interesting future research direction. \n\n__Figures__\n\nFigure 3: https://anonymous.4open.science/api/repo/r1vi_icml-2F14/file/rebuttal/reducible_maze.pdf?v=40f97d29\n\n__Codes__\n\nhttps://anonymous.4open.science/r/r1vi_icml-2F14/README.md\n\n__References__\n\n[4] Puterman. Markov Decision Processes. 2005.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, to some extent.", "experimental_designs_or_analyses": "Yes, to some extent.", "relation_to_broader_scientific_literature": "The main novelty is about the theoretical guarantees of their work.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "None.\n\nThe writing is clear!", "other_comments_or_suggestions": "None.", "questions_for_authors": "Page 2:\nPlease explain Equation (2).\n\nPage 2:\nItem (3):\nCan you show any theoretical guarantees here as well?\n\nPage 2:\nPlease say a couple of words about the discount factor $\\gamma$.\n\nPage 3:\nWhat is the output of the algorithm that contains Equation (4)?\n\nPage 4:\nAlgorithm 1:\nLine 5:\nHow is this step implemented?\n\nPage 6:\nNumerical simulations:\nCan you please provide further info on the implementations and the architectures that were used?\n\nPage 7:\nThank you for describing limitations :)\nAre there any other future research directions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides new variants of value iteration and Q-learning, where the updates use a rank-1 approximation to the transition dynamics at each step. The authors establish that this does not hurt the convergence rate of the algorithm, as compared with vanilla value iteration and Q-learning. Empirically, however, the authors demonstrate significantly faster convergence (at least in terms of value errors) of the new approaches, as compared with prior baselines. I find that the paper is well-written, clearly explains the contributions and limitations, and demonstrates the strengths and weaknesses of their approach well empirically (esp. including the new experiments in the rebuttal). However, there are a few reasons that I find that the paper is still strictly borderline:
1. I think that the issue of no improvement in policy convergence is too significant to be shrugged off. Bellman errors are notoriously unreliable to use as convergence criteria in stochastic MDPs with function approximation, at which point the lack of gains on the policy side becomes a significant limitation.
2. I find it a significant omission that the authors do not attempt to explain the better empirical convergence, possibly with a better local analysis akin to some prior works. Without this, the theoretical motivations for being excited about the new method are rather minimal, and the empirical evaluation by itself would need to be significantly more extensive to prop up the algorithm on its own, if we ignore the theoretical analysis.
It is quite likely that this is a nice idea, but I find that the authors could have done a bit more to make a more solid contribution to the confererence.
Decision: Accept (poster)