Truncated Variance Reduced Value Iteration
Authors: Yujia Jin
Ishani Karmarkar
Aaron Sidford
Jiayi Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Markov Decision Processes (MDP)
discounted MDP
value iteration
variance reduction
Primary area: reinforcement_learning
TL;DR: We provide faster randomized algorithms for computing an ε-optimal policy in a discounted Markov decision process and take a step towards closing the sample-complexity gap between model-based and model-free methods.

Abstract: We provide faster randomized algorithms for computing an $\epsilon$-optimal policy in a discounted Markov decision process with $A_{\text{tot}}$-state-action pairs, bounded rewards, and discount factor $\gamma$. We provide an $\tilde{O}(A_{\text{tot}}[(1 - \gamma)^{-3}\epsilon^{-2} + (1 - \gamma)^{-2}])$-time algorithm in the sampling setting, where the probability transition matrix is unknown but accessible through a generative model which can be queried in $\tilde{O}(1)$-time, and an $\tilde{O}(s +  (1-\gamma)^{-2})$-time algorithm in the offline setting where the probability transition matrix is known and $s$-sparse. These results improve upon the prior state-of-the-art which either ran in $\tilde{O}(A_{\text{tot}}[(1 - \gamma)^{-3}\epsilon^{-2} + (1 - \gamma)^{-3}])$ time [Sidford, Wang, Wu, Ye 2018] in the sampling setting, $\tilde{O}(s + A_{\text{tot}} (1-\gamma)^{-3})$ time [Sidford, Wang, Wu, Yang, Ye 2018] in the offline setting, or time at least quadratic in the number of states using interior point methods for linear programming. We achieve our results by building upon prior stochastic variance-reduced value iteration methods [Sidford, Wang, Wu, Yang, Ye 2018]. We provide a variant that carefully truncates the progress of its iterates to improve the variance of new variance-reduced sampling procedures that we introduce to implement the steps. Our method is essentially model-free and can be implemented in $\tilde{O}(A_{\text{tot}})$-space when given generative model access. Consequently, our results take a step in closing the sample-complexity gap between model-free and model-based methods.

Truncated Variance-Reduced Value Iteration
Yujia Jin Stanford University
Ishani Karmarkar Stanford University ishanikōstanf edu
Aaron Sidford Stanford University
yuj jaj in@stanford. ctr.tadnoorrduuu edu
sdiforddstanford edu
Jiayi Wang Stanford University jywostanford.cm edu
Abstract
We provide faster randomized algorithms for computing an s-optimal policy in a discounted Markov decision process with Aror-state- pairs, bounded rewards, and discount factor We provide an Ó(Aron [(1 - + (1 7) -1)- time algorithm in the sampling setting, where the probability transition matrix unknown but accessible through generative model which can be queried (()) time, and an Ō(s Ator - algorithm the offline setting where the probability transition matrix is known and s- s-sparse. These results improve upon the prior state-of state-of-the-ar which either ran in ( [11 - 11) +(1 - (-)---) -1)
time ([I, 2]) in the sampling setting, Ö(s + Acor (1 - ->)= time ([3)) in the offline setting, or time at least quadratic in the number of states using interior point methods for linear programming. We achieve our results by building upon prior stochastic variance-reduce value iteration methods [1, 2]. We provide a variant that carefully truncates the progress of its iterates improve the variance new seriance-reducce sampling procedures that we introduce to implement the steps. Our method is essentially model-free and can be implemented in (AAro)) space when given generative model access. Consequently, results take step in closing the sample-complextty gap between model-free and model- based methods.
Introduction
Markov decision processes (MDPs) are fundamental mathematical model for decision making under uncertainty. They play central role in reinforcement learning and prominent problems in computational learning theory (see e.g., [4, 5, 6, 7J). MDPs have been studied extensively for decades (18, 9I), and there have been numerous algorithmic advances efficiently optimizing them ([3, 1, 2, 10, 11, 12, 13, 14]).
In this paper, we consider the standard problem of optimizing a discounted Markov Decision Process (DMDP) M (S, A, P, 7,).). We consider the tabulur setting where there is a known finite set of states and at each state s E there is finite, non-empty, set of actions, A, for an agent to choose from; A a(s.a)
[A] > |S]. S. A.) ) denotes the full set of state action pairs and Arot The agent proceeds in rounds = 0, 1,
action a, E As,, which yields known reward each round t, the agent is in state 8; E S; chooses Te..a E [0, 1]; and transitions random state 8141 sampled (independently) from (potentially) unknown distribution (s()) E A for round + 1, where (s,) is the (sr. -th row of P E [0, A| The goal is to compute an e-optimal policy, where a (deterministic) policy m, is mapping from each state s E S to an action x<s) A, and is e-optimal if for every initial so E S the expected discounted reward of T. E Fx?" is at
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

least V E. Here, Vig is the maximum expected discounted reward of any policy applied starting from initial state 50 and v* E S is called the optimal value of the MDP.
Excitingly, line of work [15, 16, 2, 3, 17, 18] recently resolved the query complexity for solving DMDPs (up to polylogarithmic factors) in what we call the sample setting where the transitions Pa (s) are accessible only through a generative model ([16).. A generative model is an oracle which when queried with any E S and a E A, returns a random s' E S sampled independently from (s( (19). It was shown in [18] that for all & E (0. (1 - 7) there an algorithm which computes an e-optimal policy with probability 1- 6 using (1t (1 --
queries where we use Õ(-) to hide polylogarithmic factors in Atot. e (1 - -))---)- 7) and 8-1 This result improved upon prior result of [17] which achieved the same query complexity for 8 E [o, (1 -)-1//) of [2] which achieved this query complexity for E [0, 1], and of [16] which achieved it for
[o, ([S) (1 - -))- This query complexity is known to be optimal in the worst case (up to polylogarithmic factors) due to lower bounds of [16] (and extensions of [20), which established that the optimal query complexity
for finding e-optimal policies with probability 1- - 6 is ((AAio (1 -7)- -g- log(AAor
Interestingly, recent state-of oef-the-an art results [17, 18] (as well as [16]) are model-based they query the oracle for every state-action pair, use the resulting samples to build an empirical model of the MDP,
and then solve this empirical model. State-of-the-an computational complexities for the methods are then achieved by applying high-accuracy, algorithms for optimizing MDPs in what we call the offline setting, when the transition probabilities are known [2, 17].
Correspondingly, obtaining optimal query complexities for large E, e.g., & >> 1, comes with certain costs. This setting is of interest when the goal is to efficiently compute a coarse approximation of the optimal policy. Model-based methods use space [[rort minn(1 ((1-((1)))))))))) 7) - 2 | than the (Ato)) memory used by model-free methods (e.g., [2, 3, 21]), which run stochastic, low memory analogs of classic popular algorithms for solving DMDPs (e.g.. value iteration). Moreover, although sfate-of-the-are model-based methods use (2( (1 - -33- samples, the state-of-the-art runtime to compute the optimal policy is either Ö(A (1 - 7) -0axm,, (1)) (using [2]) or has a larger larger polynomial dependence on Acot and |S] by using interior point methods (IPMs) for linear programming (see Section 1.1). Consequently, in the worst case, the runtime cost per sample is more than polylogarithmic for sufficiently larger than 1, and it is natural to ask if this can be improved.
These costs are connected to the state-of-thh-art runtimes for optimizing DMDPs in the offline setting. Ignoring IPMs (discussed in Section 1.1), the state-of-the-a art runtime for optimizing a DMDP is Ó(nzz P) + Asot (1 - 7) -3 due to [2] where nnz P) denotes the number of non-zero entries in i.i.e. the number of triplets (s, 6', a) where taking action a E A, at state & E S has a non-zero probability of transitioning to s' E S. This method is essentially model-free; it simply performs variant of stochastic value iteration where passes on P are used to reduce the variance of sampling and can be implemented in ((A))space given access to a generative model and the ability to multiply P with vectors. The difficulty in further improving the runtimes in the sample setting and improving the performance of model-free methods seems connected to the difficulty in improving the additive Ator 11-) --t-rmttmm in this runtime (see the discussion in Section 1.2.)
In this paper, we ask whether these complexities can be improved. it possible to lower the memory requirements of near-optimal query algorithms for large e? Can we improve the runtime for optimizing MDPs the offline setting and can we improve the computational cost per sample in computing optimal policies in DMDPs? More broadly, is it possible to close the gap between model-free free and model -ased methods for optimizing DMDPs?
1.1 Our results
In this paper, we show how to answer each of these motivating questions in the affirmative. We provide faster algorithms for optimizing DMDPs in both the sample and offline setting that are implementable in -space provided suitable access to the input. In addition to computing e-optimal policies, these methods also compute e-optimal values: we call any v E RR a value vector and say that it is c-ottmall if | v" ll S.
Here we present our main results on algorithms for solving DMDPs in sample setting and in the offline setting and compare to prior work. For simplicity of comparison, we defer any discussion and comparison of DMDP algorithms that use general IPMs for linear program to the end of this section. The ofate-of-the-ar such IPM methods obtain improved running times but use 2(((S2) space and

---

((S))) time and use general- purpose linear system solvers. As such they are perhaps qualitatively different from the more combinatorial or and stochastic value iteration, more commonly discussed in this introduction.
based methods, e.g., value iteration
In the sample setting, our main result is an algorithm that uses Õ (1 - - 21 (1-2)) samples and time and ((Atot) -spacc. It improves upon the prior, non-IPM, state-of-the-art which uses OAAvo [1 - 7) + (1 - 2) 2) time [3] and nearly matches the state-of-thh-arr sample complexity for all 5 = O(11 - 1)/2. See Table 2 for a more complete comparison.
Theorem 1.1. In the sample setting, there is an algorithm that uses Ō [11-)) 2 ?1) samples and time and O(Arot) space, and computes an e-optimal policy and 8-optimal values with probability 1 -. 8.
Particularly excitingly, the algorithm in Theorem 1.1 runs in time nearly- in the number of samples whenever O(11 - -)1/) and therefore, provided querying the oracle costs (2(1), has a near-optimal runtime for such e! Prior to this work such a near-optimal, non non-IPM, runtime (for non-trivially small ?) was only known for = = (() ([2)). Similarly, Theorem 1.1 shows that there are model-free algorithms (which for our purposes we define as an ((Aro)) space algorithm) which are -aamle optimal whenever = = O((1 - --)---7-/- Previously this was only known for = Õ(1). As discussed in prior-work ([18, 17J), this large regime is potentially of particular importance in large-scale learning settings, where one would like to quickly compute a coarse approximation of the optimal policy.
In the offline setting, our main result is an algorithm that uses Ó P) + Aroc -7)- time. It improves upon the prior, non-IPM, state-of-the-ar which use ( P) + Ator(1 - -)) time ([2)). See Table for a more complete comparison with prior work.
Theorem 1.2. In the offline setting, there is an algorithm that uses Ó(nn P) + (1o - -7)-2) time, and computes an E-optimal policy and e-optimal values with probability 1 ö.
< (P)) the discount factor is not too small relative to the average sparsity of rows of the transition matrix. Prior to this paper, such nearly-linear, non-IPM, runtimes (for non-trivially small 7) were only known for (1 - (1-2))1 S (nnz(P)/Aunn) (eo)) ) // ([2). Thus, Theorem 1.2 expands the set of DMDPs which can be solved in nearly-linear time. The space usage and input access for this offline algorithm differs from the algorithm in Theorem 1.1 in that the algorithm in Theorem 1.2 assumes that access to the transition P is provided as input and uses this to compute matrix-vector products with value vectors. The algorithm in Theorem 1.2 also requires access to samples from the generative model; if access to the generative model is not provided as input, then using the access to P. the algorithm can build Ó(nzz()) data-structure that queries to the generative model can be implemented in Ó(1) time (e.g., see discussion in [2]). Hence, if matrix- -vector products and queries to the generative model can be implemented in ((Assr)-space then so can the algorithm in Theorem 1.2.
The method of Theorem 1.2 runs in nearly-linear time when (1 - 11-7)-1-
i.c.,
Table 1: Running times to compute e-optimal policies in the offline setting. In this table, E denotes an upper bound on the ergodicity of the MDP.
Algorithm
Runtime
Space
Value Iteration [22, 11]
Ô (Inn(()) - 11
((nnz(P))
Empirical QVI [16]
Ô (nnz(P) + Aune (1 - 7) -32-2)
Ö(nzz(P))
Randomized Primal-Dual Method [23]
Ô (nnz( P) + E.Atot (1 - 12-2)
Ö(Acst)
High Precision Variance-
Reduced Value Iteration [2]
Ô (nnz(P) + Acot (1-))-))
Ö(Avor
Algorithm 4 This Paper
Ô (nnz((P P) + Abor - (1 -)-
Ö(Aro))
3

---

Exact DMDP Algorithms. In our our comparison of offline DMDP algorithms in Table 1, we ignored poly(log(E ())-fa--r)sss.os.. Consequently, we did not distinguish between algorithms which solve DMDPs to high accuracy, i.e., only depend on e polylogarihhmicaly, and those which solve it exactly, e.g., have no dependence on E. There a line of work on designing such exact methods and the current state-of-the-arr is policy iteration, which can be implemented in Ō([S)² (1- time ([13, 14J) and a combinatorial interior point method that can be implemented ( time ([10) with dependence on Note that these methods obtain improved runtime dependence the cost of larger dependencies on |S] and Acot-
Table 2:
Query complexities to compute E-optimal policy in the sample setting. Merg denotes an upper bound on the MDP's ergodicity. Here, model-free refers to ((Aro) space methods.
Algorithm
Queries
range
Model-Free
Phased Q-learning [15]
Ares (1-7)'62
(0, (1 -1
Yes
Empirical QVI [16]
Aus [1 (1-78'²
(0, ((1 - (11-)) 181)
No
Sublinear Variance-
Value Iteration [2]
δ [I [1-7)
Aus
(0, (1 -)/1/
Yes
Sublinear Muriance-Reducee
Value Iteration [3]
Aro (1 (1-7}s²2
(0, 1]
Yes
Randomized Primal-
Dual Method [23]
May (1-g}+z2
(0, (1 - -1
Yes
Empirical MDP
Planning [17]
Aug (1ー1
(0, 7) -
No
Perturbed Empirical MDP,
Conservative Planning [18]
Aus [1-7]-²
(0, (1 71-
No
Algorithm 5 This Paper
δ Aug (I (1-7)
(0, (1 - -121
Yes
Comparison with IPM Approaches. In the offline setting, [2] showed how reduce solving DMDPs to an frrregeesion problem in P E RAXS, For & regression in a matrix A E gn for n > d, [12] provides an algorithm that runs in ((d)5((nn(( + )-mmme, [24] provides an algorithm that runs in O(nd + d2-5), and [25, 26, 27] yields an algorithm that runs in ((At.t) time for the current value of the fast matrix multiplication exponent w < 2.371552 [28]. These offline IPM approaches can be coupled with model-based approaches to yield algorithms in the sample setting. [18] shows that given a DMDP M, with Ô (Ator (1 - ===33= queries to the generative
model and time, one can construct DMDP A such that an optimal policy in M is an e-optimal for M.. Consequently, provided polynomial accuracy in computing the policy suffices, applying the IPMs to M yields runtimes of Ó(nzi( P) V + [S|2.5) ((12)), Ö(A |S] (-) ([24)), and O(4%)) time [25]. This combination of model-based and IbMed approaches use super-quadratic time and space, but they may yield better runtimes than Theorem 1.2 in certain regimes where is sufficiently large relative S and Acot in the offline setting, or when, additionally, is sufficiently small relative to S and Asot in the sample setting.
1.2 Overview of approach
Here we provide an overview of our approach to proving Theorem 1. and Theorem 1.2. We motivate our approach from previous methods and discuss the main obstacles and insights needed to obtain our results. For simplicity, we focus on the problem of computing e-optimal values and discuss computing e-optimal policies at the end of this section.

---

the sample Value iteration. Our approach stems from classic value-iteration method ([22, 11]) for computing e-optimal and its more modern Q-value and stochastic counterparts ((16, 3, 29, 30, 31, 321). As the name suggests, value iteration proceeds in iterations
0, 1, ..... computing values, v(t) E R Starting from initial vi0)) R$ in iteration 2 1, the value vector w(*) is computed as the result of applying the (Bellman) value operator T R + R i.e.,
(+)) t -T((lt-)) where (())(s) == max (8) + (P(()) v) for all 8 E S and v E R aEA,
(1)
It is well-known that the value operator is 7-contractive and therefore, [[ - Im S
y - lo for all E _ ([11, 22, 2D. If we initialize v(0) = 0 then since | S 71
v" v'llx S 5 (1) s (1 -2) exp((1(11-))) Thus, v(()) are e-optimal values for any t 2 (1 - 7) log((= (1 - -)- This yields an
[22, 111, we see that [|0(()~v"") - S >/
Ó(nz
- (1)(17))
time algorithm in the offline setting.
Stochastic value iteration and variance reduction. To improve the runtime of value iteration and apply it in the sample setting, a line of work implements stochastic variants of value iteration (116, 2, 3, 23, 17, 18]). Those methods take approximate value iteration steps where the expected utilities Pa (s) v in (1) for each state-action pair are replaced by a stochastic estimate of the expected utilities. In particular, note that Pa (s T = Ei-p.(s) Uú i.e., the expected value of vs where is drawn from the distribution given by (s). This is compatible in the sample setting, as computing v; for drawn from (s(s) yields an unbiased estimate of (a(s) T v with 1 query and ((1) time.
State-of-the-an model-free methods in the sample setting ([3]) and non-IPM runtimes in the offline setting ((3)) improve further by more carefully approximating the expected utilities Pa(s) of each state-action pair (s, a) E A. Broadly, given arbitrary (00) they first compute E R- that approximates Pv i.c., (s) approximates [Po(*] =pa(s) v(()) for all (s, a) E A. In the offline setting, æ Po(0) can be computed directly in (auuz())-time.
setting, x R (x)(0) can be approximated to sufficient accuracy using multiple queries for each state-action pair. Then, in each iteration & 2 I of the algorithm, fresh samples are taken to compute ((t)) ~ ((t((t-)) - =)))) and perform the following update:
(+)(s))) + max (rax(ra(s) + (s) + (s)) for all s E S and v E R.S. aEA,
This approach is advantageous because sampling errors for estimating P(v(t-1) - (0)) depend on the magnitude of ((t-1) - (0)), After approximately computing x, the remaining task of computing so that x +g(( v Py((-1) may be easier than the task of directly estimating Po(() (since (1-1) - (0)) is smaller in magnitude than v)()) entrywise.) Due to similarities of this approach to variance-reduced optimization methods, e.g. ([33, 34]), this technique is called variance reduction [2].
g00)) s P(u((-1)-p())
The works [2, 31. showed that if æ is computed sufficiently accurately and ((() are a-optimal values then applying (2) for @((1 - -)) yields v(() that is a/22-opimal in just Ö (1 - 7) -99)
time and samples! [2] leverages this technique to compute e-optimal values in the offline setting in Ó(nnz (P) + Aroe (1 - 3)) time. [3] uses a similar approach to compute e-optimal values in O (1 - 7) 33 2 + (1 - 7)-33 time and samples in the sample setting. A key difference in [2] and [3] is the accuracy to which they must approximate the initial utility x Rs (v(
Recursive variance reduction. To improve upon the prior model-free approaches of [2, 3] we improve how exactly the variance reduction is performed. We perform a similar scheme as in (2) and use essentially the same techniques as in [3, 2] towards estimating æ. Where we differ from prior work is in how we estimate the change in approximate utilities ( as P(y(t-1) (0)). Rather than directly sampling to estimate this difference we instead sample to estimate each individual (()((-1) - (())) and maintain the sum. Concretely, for t 2 1, we compute A such that
(t) ~ (()(t) (t-1))
(3)
so that these recursive approximations telescope. More precisely, setting g g0)) 0, for L 2 1, we set g(t) + g" (t-1 + A (t-1) = ((v(t-2) - (0)) + ((v(t-1) - olt-2)) = P(vlt-1) - - (0)). (4)
5

---

This difference is perhaps similar to how methods such as SARAH ([34)) differ from SVRG ([33]). Consequently, we similarly call this approximation scheme recursive variance reduction. Interestingly. in constrast to the finite sum setting considered in [33, 34], in our setting, recursive variance reduction for solving DMDPs ultimately leads to direct quantitative improvements on worst case complexity.
To analyze this recursive variance reduction method, we treat the error in g()) z P(v(t-1) (00)) as a martingale and analzye using Freedman's 's inequality [35] (as stated in [36]). The hope in applying this approach is that by better bounding and reasoning about the changes in v("), better bounds on the error of the sampling could be obtained by leveraging structural properties of the iterates.
Unfortunately, without further information about the change in v(() or larger change to the analysis of variance reduced value iteration, in the worst case, the variance can be too large for this approach to work naively. Concretely, prior work ([2)) showed that it sufficed to maintain that || (++) PulOI O(( - 7))), However, imagine that 2' al, v()) = 0, and in each iteration t one coordinate of o(0) (
v(t-1) is M(a). If [S] ~ (1-7)-1 and Ip (p)(s) 0o (1/||)) for some (s, .) E AA then the variance of each sample used to estimate (s) (v w((-1))
(((1-7)). Applying Freedman's 's incquality, c.g., [36], and taking b samples for each 0 0((1-7)-) ((11|S))= =
iteration would yield, roughly. l|g (t+11) -P(((') - |lx = (((1-))~1(1 (1-r)//bb) =
O(1/Vb)
Consequently b = 2(11 -) and S2(11 (((1-)) -) samples would be needed in total, i.e., there is no improvement. Next, we will discuss how we circumvent this obstacle by combining recursive variance reduction with second algorithm technique, which we call fruncation.
Truncated-vall iteration. The key insight to make our new recursive variance reduction scheme for value iteration yield faster runtimes is to modify the value iteration scheme itself. Recall that in the previous paragraph, we described that the case challenging case for recursive variance reduction occurs when, for example, in every iteration, a single coordinate of v changes by Max) We observe that there is a simple modification that one could make to value iteration to ensure that there is not such a large change between each iteration; simply truncate the change in each iteration so that no coordinate of (t)) changes too much! To motivate our algorithm, consider the following truncated variant of value iteration where
(5) Where median applies the median of the arguments entrywise. In other words, suppose we apply value iteration where we decrease or Iruncate the change from w!(-1) to v(!) so that it is no more than (1 7) in absolute value in any coordinate. Then, provided that (()) is a-optimal, we can show that it is still the case that (| - oo1loo < (t]e -o'l In other words, the worst-case progress of value iteration unaffected! This follows immediatly from the fact that [lo(0) 10 S <]]l(((11] - loe in value iteration and the following simple technical lemma.
(+) median [t - 7),,, (io,,T(((t-)))) (t-1)) + (1 (1-7)) 7)a)
Lemma 1.3. For a, b, x E R and 7,a > O, let e == mediança (a - (1 - 7)a1, b, a + (1 (1-77) {..))
where median is applied entrywise. Then, if llb 01110= S 2 1|a æ1l and l|a x xIl.c S a, then ||c - x: 20100= S y ||a -aa--a x: xlloc.
- (1(0)~((-1)) xc S (1 7)a. In other words, the worst-case change in coordinate has decreased by factor of (1 ?) We show that this smaller movement bound does indeed decrease the variance in the martingale when using the aforementioned averaging scheme. We show this truncation scheme, when combined with our recursive variance reduction scheme (4) for estimating P(o!.) - v (0)),, reduces the total samples required to estimate this and halve the error from Ō( -))) to just Ō((1 - per state-action pair.
Applying truncated value iteration, we know that |00(0)
Our method. Our algorithm applies stochastic truncated value iteration using sampling to estimate each g R ((x(!) (0) as described. Some minor additional modifications are needed, however, to obtain our results. Perhaps the most substantial is our use of the monolonicity technique, as in prior work ([2, 3D. That is, we modify our method so that each ((() is always an underestimate of o² and the (4) increase monotonically as f increases. Thus, we only truncate the increase in the v(()) (since they do not decrease, and the median operation in (5) reduces
minimum in Lemma 1.3).
Beyond simplifying this aspect of the algorithm, as in prior work, this monotonicity technique allows us to simultaneously compute an E-approximate policy well an e-optimal value vector. We do this by tracking the actions associated with changed (!) values, i.c., the argmax in (2) in variable

---

Algorithm 1: Sample(u, M,M,77
Algorithm 2: Apx
Input: Value vector и E IR. E A sample size M, and offset parameter
Input: Value vector u E R sample size M, and offiet parameter 1 0.
7 2 0. for each n E [M] do
for each (8, do
Choose in E S independently with
// In the sample setting,
iin = t) = p(t);
Pa(s) is passed
3 x M EnE[M] u(in):
implicitly.
Ta (s) = Sample u, Pa (s),, M,n):
4 Ō = 1 EmElM] [M]] (e((2))2 =x
5 I. f- x x V2n 4/////4 11elloc -(2/3)m |
return æ
6 return T:
(*),, which denotes the current estimated policy in iteration of value iteration. Concretely, the monotonicity technique allows us to maintain the invariant that at each iteration t, the current value estimate and policy estimate x(0, vl()) satisfy the relation (1)) < T[v(O). Note that this ensures that the value of (+) (denoted w= is at least (t() because
(4)) < T(D <
[T >
S T0.. (b()))
o (6)
Thus, whenever ((() is an E-optimal value, π (*) is at least e-optimal policy.
By computing initial expected utilities x = (v exactly. we obtain our offline results. By carefully estimating æ R (v(0) as in [3] we obtain our sampling results. Finally, building off of the analysis of [37] for deterministic convergence guarantees under additional non-worst-case assumptions on the MDP structure.
highly-mixing MDPs, we also show method obtains even faster
1.3 Notation and paper outline
General notation. Caligraphic upper case letters denote sets and operators, lowercase boldface letters denote vectors, and uppercase boldface letters (e.g.. P, I) denote matrices. O and denote the all-ones and all-zeros vectors, [m] := {I, .l.,, m). and A == {a E R² 0 S x and ||>||| = 13 is the simplex. For u E RSS, we use v; or v(i) for the i-th entry of vector v. For vectors v E R-, we use (s) to denote the (8, a)th entry of where (s,a) E A. We use Vo, v², |vo E R for the element- wise square root, square, and absolute value of v respectively and max u, f} and median u, v, w R",
for element-wise maximum and median respectively. For for each i E [n]] (analogously for <, <,2,>, >.) We call x E R" an a-underestimate of y E R= al S y for
denotes that v(i) < x(1)
(see the discussion of monotonicity in Section 1.2 for motivation).
As discussed, the objective in optimizing DMDP is to find an e-approximate policy π and values. For a policy æ, we use Ta (w) IRS + R denote the value operator associated with म, i.e. Ta (=)) == T=(+ (s) + (P)(s) (s) for all value vectors E R$ and E S. We let v² denote the unique value vector such that (v") nº and define its variance du- == P (u -(P" (P"u*)² where pr E gSSS is the matrix such that P.,. = P (s.)(s)('"). The optimal value vector o² E gS of the optimal policy is the unique vector with T(o*) v², and P R =
DMDP.
Outline. Section 2 presents our offline setting results and Section 3 our sample setting results. Section discusses specialized settings where we can obtain even faster convergence guarantees. Omitted proofs are deferred to Appendix B.
2 Offline algorithm
In this section, we present our high-preecsion algorithm for finding an approximately optimal policy in the offline setting. We first define Sample (Algorithm 1), which approximately computes products between p E A and value vector u E R using samples from a generative model. The following lemma states some immediate estimation bounds on Sample using linearity and the fact that p E A
Lemma 2.1. Let x Sample(u, p, M, for p E A", M E Z > 0, and u E R Then, E [x]] p
[z]| < |/llloo and Var [z] < 1/M [|ul12
7

---

We can naturally apply Sample to each acttinaction pair in M as in the subroutine ApxUtility (Al- gorithm 2). If ApxUtility(C u. M, n7,, then x(s, a) is an estimate of the expected utility of taking action E A, from state E S (as discussed in Section 1.2). When 1) > 0. this estimate may potentially be shifted to increase the probability that a underestimates the true changes in utilities; we leverage this in Section 3 (see also the discussion of monotonicity in Section 1.2). The terms arising in the definition of ī arise from applying Bernstein's 's inequality (Theorem B.2) to guarantee that œ S x 7y with high probability.
The following algorithm TVRVI (Algorithm 3) takes as input an initial value vector w( and policy (0) such that (0)) is an a-undcrestimate of v" along with an approximate offset vector æ, which is a 8-underestimate Po(0), runs runs L = Ō(1 -) iterations of approximate value iteration, making one call to Bample(Algorithm 1) with a sample size of M Ō((1 - 7) in each iteration. The algorithm outputs v² which we show is a /22aunderestimate of o* (Corollary 2.5).
TVRVI (Algorithm 3) similar to variance reduced value iteration [2], that each iteration, we draw M samples and use Sample to maintain underestimates of (s) (v.(e) - for each sate-action pair (s, a.. However, there are two key distinctions between TVRVIand variance-reduced value iteration [2] that enable our improvement. First, we use the recursive variance reduction technique, as described by (3) and (4), and second we apply truncation (Line 7), which essentially implements the truncation described in Lemma 1.3. Lemma 2.2 below illustrates how these two techniques can be combined to bound the necessary sample complexity for maintaining approximate w())) for general sequence of -bounded vectors (w()) The analysis leverages Freedman's Inequality [35] as stated in [36] and restated in Theorem B.1.
transitions (s) (w
Lemma 2.2. Let T Z>o and w()), w())) (T) RR such that || (0(i1))| S T for all E [T]. Then, for any p E A 8 E (0, 1), and M 2 log(2/2 with probability 6,
(w - w0l)) Eiet Σ [ Sample(w)) (i-1)) ,,,10)) 1/M| S T/8 for all I E (T].
Algorithm 3: (v) (z) ax,))
Input: Initial values (0)) E SR which is an a-underestimate of v².
Input: Initial policy (0)) such that (0)) Tx (v1()).
Input: Accuracy a E [0, (1 - [1] and failure probability E (0,
Input:
Offsets x E RA,;
// entrywise underestimate of Pv(")
Initialize (1) E RR- and ( E R- to 0:
2 L = =[oog())(1 7) 7) and M [L- 2 log 28)0
3 for each iteration E [L] do
= r + (0);
b( - ((-1)) and - (e-1); for each state E S do
5
// Compute truncated value update (and associated action)
((0()) (1) = min(max.eA Qu.a, ((-1)) + (1 - 7]a} and मे argmax aEA, Qiai
7
// Update value and policy if it improves
if (1 2 (1) then v1) = (1) and n. = #
8
// Update for maintaining estimates of P - v)) A (t) ApxUtility(b()) - ((t-1), M, 0) and ((+1)) g0 A AA
// Shift estimates so that (((+1) always underestimated (s(s) T(())
g(++l) = ((+1) (1-7)a1;
10
return (v(1), (T))
While is unclear how to significantly improve the constant of 2 256 appearing in Lemma 2.2 (and consequently Algorithm 3), we note that tightening these constants in the application of Freedman's inequality could be of practical interest. By applying Lemma 2.2 to the iterates v(() in TVRVI, the following Corollary 2.3 shows that can maintain additive O(11 7)a)- uadderessttsssss of the
8

---

(v(*) transitions Pa (v(() - -)) using only ((L) samples (as opposed to the Ó(L?) samples required in [2]) per state-action pair.
Corollary 2.3. In TVRVI (Algorithm 3), with probability 1 - 8, in Lines 9, 10 and 2, for all (8)
&Saa As, and 8 [L], we have go (s) Pa(s) (vlc-1) (vltt)) v(01)
(1 - 7)-7///8 and
therefore 9% is (1 - (1)-))a/aa -:)///4-uderestimmat of pa (s) (vll-11 (s)( -v(1).
The following Lemma 2.4 shows that whenever the event in Corollary 2.3 holds, TVRVI (Algorithm 3) is approximately contractive and maintains monotonicity of the approximate values. By accumulating the error bounds in Lemma 2.4, we also obtain the following Corollary 2.5, which guarantees that TVRVI halves the error in the initial estimate (1))
Lemma 2.4. Suppose that for some B E BR - S Pv and let B RR. be defined as Ga. (s) == (e) ( for each S. Then, with probability 1 ô, at the end of every iteration é E [L] (Line 3) in TVRVI( (1) x. a. 6), the following hold for & == 7((1 - 77/44411 + Bx-):
(lt-1) < (0 s (T()
0 S 0² x S max (pP**0"-<(0-1)) -o(e-1)) E.7 - o((-11)).
S Pv( v is an - B x Corollary 2.5. Suppose that for some 2 0 and B E R. -
a-underestimute of v"; and (0)) S T= (v) Let Bar RR be defined as Brr (8) == (a)(e) (b) for each s E S. Let (v()) ((1 7)//44 1 ). Then, with probability 1 - 6, 0 2 0" - vl4) < a 1+
) (VRVI(v(O) T (("), 8), and L, M be as in Line 2. Define & =
-I-- and (LL) < Tx (v(l)), In particular, if 0, then L > (0g(8)(1- 7) we can reduce the error in (00) by half: S vv( < (v- - ) Additionally, TVRVI is implementable with ML sample queries to the generative model and time and O (Aror space.
Theorem 1.2 now follows by recursively applying Corollary 2.5. OfflineTVRVI (Algorithm 4) provides the pscudocode for the algorithm guaranteed by Theorem 1.2.
Algorithm 4: OfflineTVRVI
Input: Target precision & and failure probability 8 E (0, 1)
K = [loga(s-1
[1)], 8o = O, To is an arbitrary policy, and on -1:
2 for each iteration []] do
ak 04-1/ 2- (1 -1
4 == P0k-1:
(UK, TVRVI Tk-1, 0,8/K)
return T))
3 Sample setting algorithm
In this section, we show how extend the analysis in the previous section in the sample setting, where we do not have explicit access to P. We follow similar framework as in [3] to show that we can instead estimate the offsets z in OfflineTVRVI by taking additional samples from the generative model. The pseudocode is shown in (etpeeeeeeVA(AAooiiiie algorithm, we first bound the error incurred when approximating the exact offsets æ in Line 4 of OfflineTVRVI (Algorithm 4) with approximate offsets à R PVR-1 computed by sampling from the generative model. The proof leverages Hoeffding's and Bernstein's 's inequality, and follows similar structure the proof of Lemma 5.1 of [3].
5.) To analyze the

---

Algorithm 5: SampleTVRVI((..)
Input: Target precision & and failure probability 8 E (0,
K (1 -1-
2 vo 0, mm an arbitrary policy, and oo =(1 (
3 for each iteration & E K do
4
ag 04-1/2 = 2 -
5
N = 6500(1 - 7) 1rr
6
- = N max - -,,
- N log K6 K8
Fg ApxUtility 0/ No M]- 77--1)
(Vk, .T) TVRVI 0k Tk- ki 0 11 K
return TK)
Lemma 3.1. Consider u E R... Let a = ApxUtility(u, m Auor, 7). m 2 log(1/26 and 7 (mAwv) 1og(1/26-1) Then, with probability 6,
Pu 2 2n + (2v/2) u - v*1lxo 1817 |20l S S Pu.
Finally, to obtain our main result Theorem 1.1, we utilize worst-case bounds on ae from prior work [1] (see Lemma B.3, Lemma B.4) and inductively apply Lemma 3.1 and Corollary 2.5.
The constant of 6500 appearing in the initialization of N in Algorithm 5 arises due technical reasons, from applying Bernstein's inequality, Hoeffding's 's inequality, union bound over all K outer loop iterations, and bounds on d from prior work [3] to prove Lemma 3.1. While it is unclear how to directly further tighten this constant, the proof of Lemma 3. shows that in the expression N 6500 - 7) log(8AAtor K6-1) there natural trade-off between the leading constant (in this case 6500) and the number of outer loop iterations K. By increasing the number of outer-loop iterations K by constants, one can relax the error requirements of each iteration (i.e., decrease N by constants at the cost of increased logarithmic dependence on ( Although not the primary focus of our work, such trade-offs might be practical importance.
4 Conclusion
We provided faster and more space-efficient algorithms for solving DMDPs. We showed how apply truncation and recursive variance reduction to improve upon prior variance variance-reduced value iterations methods. Ultimately, these techniques reduced an additive Õ((1 - 7) -3 term in the time and sample complexity of prior variance-reduced value iteration methods to Ō(1 - >?)-
Natural open problems left by our work include exploring the practical implications of our techniques and exploring whether further runtime improvements are possible. For example, may be practical interest to explore whether there exist other analogs of truncation that do not need to limit the progress in individual steps of value iteration. Additionally, the question of whether the Ō((1 ->) ->) term
in our time and sample complexities can be further improved to Ō((1 >)- is natural open problem; an affirmative answer to this question would yield the first near-optimal running times for solving DMDP with generative model for all and fully bridge the sample complexity gap between model-based and model-free methods. We hope this paper supports further studying these questions and establishing the optimal runtime for solving MDPs.
Acknowledgements
Thank you to Yuxin Chen for interesting and motivating discussion about model- based methods in RL. Thank you the anonymous reviewers for their helpful feedback. Yujia Jin and Ishani Karmarkar were funded in part by NSF CAREER Award CCF- 1 1844855, NSF Grant CCF-1955039, and a PayPal research award. Aaron Sidford was funded in part by Microsoft Research Faculty Fellowship, NSF CAREER Award CCF-1844855 NSF Grant CCF1955039, and PayPal research award. Part of this work was conducted while visiting the Simons Institute for the Theory of Computing. Yujia Jin's contributions to the project occurred while she graduate student at Stanford.
10

---

References
[1] Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. Naval Research Logistics (NRI.), 70, 2023.
[2] Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.
[3] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. Advances in Neural Information Processing Systems 31 (NeurIPS), 2018.
[4] Qiying Hu and Wuyi Yue. Markov decision processes with their applications, volume 14. Springer Science & Business Media, 2007.
[5] Zeng Wei, Jun Xu, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. Reinforcement learning to rank with markov decision process. Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval, 2017.
[6] Thomas Degris, Olivier Sigaud, and Pierre-Henri Wuillemin. Learning the structure of factored markov decision processes in reinforcement learning problems. 23rd International Conference on Machine Learning (ICML), 2006.
[7] Olivier Sigaud and Olivier Buffet. Markov decision processes in artificial intelligence. John Wiley & Sons, 2013.
[8] Martijn Van Otterlo and Marco Wiering, Reinforcement learning and markov decision processes. Reinforcement learning: State-of-the-art, 2012.
[9] Martijn Van Otterlo. Markov decision processes: Concepts and algorithms. Course on 'Learning and Reasoning, 2009.
[10] Yinyu Ye. A new complexity result on solving the markov decision problem. Mathematics of Operations Research, 30, 2005.
[11] Michael L Littman, Thomas L Dean, and Leslie Pack Kaelbling. On the complexity of solving markov decision problems. 11th Annual Conference on Uncertainty Artificial Intelligence (UAI), 1995.
[12] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in o (vrank) iterations and faster algorithms for maximum flow. 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2014.
[13] Yinyu Ye. The simplex and policy- -iteay-tteration methods are strongly polynomial for the markov decision problem with a fixed discount rate. Mathematics of Operations Research, 36, 2011.
[14] Bruno Scherrer. Improved and generalized upper bounds on the complexity of policy iteration. Advances in Neurul Information Processing Systems 26 (NeurIPS)). 2013.
(15) Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. Advances Neural Information Processing Systems // (NeurIPS), 11, 1998.
[16] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine Learning.
91, 2013.
[17] Alekh Agarwal, Sham M. Kakade, and Lin Yang. Model-based reinforcement learning with a generative model is minimax optimal. 33rd Annual Conference on Computational Learning Theory (COLT), 2020.
[18] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[19] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
11

---

[20] Fei Feng. Wotao Yin, and Lin F Yang. How does an approximate model help in reinforcement learning? arXiv preprint arXiv:1912.02986, 2019.
[21] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent. 37th International Conference on Machine Learning (ICML), 2020.
[22] Paul Tseng. Solving h-horizon, stationary markov decision problems in time proportional to log
(h). Operations Research Letters, 9, 1990.
[23] Mengdi Wang. Randomized linear programming solves the discounted markov decision problem in nearly- (sometimes sublinear) running time. Mathematics of Operations Research, 42, 2019.
[24] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and I1-regression in nearly linear time for dense instances. In 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021.
[25] Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM, 2020.
[26] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 259 278. SIAM, 2020.
[27] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general lps. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 823-832, 2021.
[28] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In 35th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), 2024.
[29] Pengqian Yu, William Haskell, and Huan Xu. Approximate value iteration for risk-aware markov decision processes. IEFE Transactions Automatic Control, 63, 2018.
[30] Mohand Hamadouche, Catherine Dezan, David Espes, and Kalinka Branco. Comparison of value iteration, policy iteration and q-learning for solving decision-making problems. In 202/ International Conference on Unmanned Aircraft Systems (ICUAS), 2021.
[31] Christopher Zobel and William T Scherer. An empirical study of policy convergence in markov decision process value iteration. Computers & operations research, 32, 2005.
[32] Dileep Kalathil, Vivek S Borkar, and Rahul Jain. Empirical v-value iteration. Stochastic Systems, 11, 2021.
[33] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems 26 (NeurIPS), 2013.
[34] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. 34th International Conference on Machine Learning (ICML), 2017.
[35] David A Freedman. On tail probabilities for martingales. pages 100-118. 1975.
[36] Joel A. Tropp. Freedman's inequality for matrix martinglaes. Electronic Communications in Probability, 16, 2011.
[37] Andrea Zanette and Emma Brunskill. Problem dependent reinforcement learning bounds which can identify bandit structure in mdps. In International Conference on Machine Learning, pages 5747-5755. PMLR, 2018
[38] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. 36th International Conference on Machine Learning (ICML), 2019.
12

---

A Faster problem-dependent convergence
In this section, we propose modified version of the SampleTVRVI algorithm, named ProbIeemDependentTVVV. This algorithm adjusts the number of required samples based on the structure of the MDP under consideration. Inspired by [38], we then consider MDPs with small ranges of optimal values and the extreme case of highly mixing MDPs in which state transitions are sampled from a fixed distribution.
Note that in the proof of Theorem 1.1, the emror during convergence caused by approximations of val- ues is bounded by (I->P*)- for (1-2)0s 1 1 1+2/22m (2//2)) 3/4 | 1o0 )1. In its proof, we upper bound the variance term [ - P yor by 3(1 -)) using Lemma B.4. However, as ag decreases and the variance term becomes dominant, number of samples proportional to the size the variance term suffices to control the error during each itcration. we further refine SaRpleTVRVI to duce the number samples taken after an initial burn-in phase and obtain improved complexities
Given V which upper bounds (I --
when V is signficantly small. Hence, obtain the following Algorithm 6 and Theorem A.1.
Algorithm 6: ProbleenDDpeaddettTWWii...
Input: Target precision failure probability E (0, 1), and V (I (T-y1 (I-PP")- Vo
1 K [=og2(== (1-))-
Uu 0, Nu is an arbitrary policy, and og 1-7;
3 for each iteration [K] do
ag 01--1/ 1/2
2-k((1 7)
if 1log2
122(1-7)
then -3 max((1 - -7), [og])og(( (0g2=)))(((40
V/ Nk-1 6500
(1 7)
// Burn-in
phase
else
Na-1 1024 a 2 log (Att K8-1);
// Variance-deepndent phase
T N log.log/ooooo K 18-1)
3g ApxUtility(ee) (k N2 k- Ml 11--1);
(U), TT) TVRVI 11 kb a1- 8/KK)
12 return (U)
Theorem A.1. In the sample setting, there is an algorithm (Algorithm 6) that, given 3(1 7).51, > V > ||(I -1PI- vo بن uses Ô (Arot (5-2V2 (1 (1-7)-2)) samples and time and O (AAro) space, and computes an e-optimal policy and E-optimal values with probability 1 8-8.
Proof. Let K, az, and (UR, be as defined in Lines 1, 4, and 11 of ProbieemDpeendeenTWW[(.. V).
For the correctness of the algorithm. we first induct on k to show that for each to E [K]. with probability k6/ K,
8T < x² 0x S ak and 2k S Tau (vx).
The base case is trivial 0 < V² To < 0- < (1 -11
For the inductive step, observe that by Lemma 3.1, see that with probability 1 1-8/K,
P0k-1 2 20 + (2 (2 + 18 |/ 1 111=0) 1 I x S PUk-1-
(8)
Additionally, by the inductive hypothesis, with probability 1 - (k 1)8/K,
0 0" - 1 v-" 2 ax 1 -I-1-pp"1 - - S a,l, and v2 S Ta (vx).
(9)
Thus, by union bound, with probability k5/ both (8) and (9) hold. We condition on this event in the remainder of the inductive step.
13

---

Now, we apply Corollary 2.5 with
β v. + 12 + +187 3/4
llz- 1loo)) 1.
Consequently, we have
0. o" Uk 5 1 -ppp)- Ex-1
a 1 (1 - -PP'-- Ex-1 Ex-1-
8
for Ex-1 I (1-))a-11 1 + 2/ 2712211000-- + (2/2TH- Tax (Dk)-
3/4 187
| 1, and vk S
L 1. Hence, if h: < [log (1 - -)--~ we use Lemma B.4 along Note that (I ( 5
T- with the facts that 1 1 1/(1 - 7)1 and the choice of 17k-1 obtain (identical to the
proof of Theorem 1.1):
2(1 - 713 (0))mmmnn111111 (1- (in)(1-))_1
11-7 (1-pPt)-1 -E
ER-15
0k-1
+2
77k-1
+ -//
O8 - 1
(1 7)3
6500(1 - 7
((1 733 minn(1 -, ,,, 3/47
+
18
6500(1- - 7//8/3
< (ax-1/ 1/4 + 2/ 6/6500 0k-1 + 2/ 2/6500
1/2 min((1 - 2//2 -00-)))0)00 ,0x-1)ok-1
+ 18. (10 (1- - 7) 3/4 -3/4 --11111
3
S |0u--1/ /4 + 6/650 0n + 18 (10 aak 1] S 8
00k-11 11.
If instead & 2 [log2(1 (1 - -//33 then as S
1 (1 v) and 7h- / V2).
128
Consequently,
(I-
Ex s 2 2 (I - PP') -'..
+
ak-1
+ 2/ 2m II p + 181/ 1 (I -pP-)~1 1111000111l00
a
4
2 2/2or
18
ax
3/4
V1
4
4(1
(1 (1-1) 7)2
1024 1/2
[ak-1
1
1 <
a 11
4
Therefore in either case,
ak-1 1 = ax1
0' Uk- <
2
Moreover, we can use that Up I Tec (vR) to see that
Tk Tan (vx) T2 (wk) S .....
T (vs) - -.¹
This completes the inductive step.
Consequently, taking k K = [log (8 (1 - -7)-11 iterations of the outer loop, with probability 1- 6, we have that 0 < 0² TK S 0² UK S ak S and
S Tap (vx) < T2 (vx) S ... < (ux) = t v0
that is, ii is e-optimal value and R is e-optimal policy.
The total number of samples and time required is Ô (Auot (5-2V2 + (1 - -))) For the space complexity, note that the algorithm can be implemented to maintain only O(1) vectors in A
Theorem A. yields improved complexities for solving MDPs when nontrivially bounded. Following [37] we mention two particular such settings where we can apply Theorem A. to obtain better problem-dependent sample and runtime bounds than Theorem 1.1.
|
is
14

---

Deterministic MDPs For a deterministic MDP, each action deterministically transitions to single state. That is, for all (s. E A. Pa(s) 1. (the indicator vector of s' E S) for some s' E S. In this case, dv- = O. Consequently, if the MDP is deterministic, the algorithm converges with just Õ((1 - -)) samples to the generative model and time. We note that in this setting of deterministic MDPs, there may be alternative approaches obtain the same or better runtime and sample complexity.
Small range. Define the range of optimal values for a MDP as rng (v") del
max.es Dg - minngs v.- $ (1 11-7) 7) -ingg))((e Therefore, by Theorem A.I, given an approximate upper bound of (I - pPP Vo. our algorithm is implementable with Ö(Aro - -rrg>"(("""")) + (1 -)) samples and time.
Note that dv- I 11. So, [| - vo..
Highly mixing domains. [37] showed that contextual bandit problem can be modeled as an MDP where the next state is sampled from a fixed stationary distribution. Using the fact that the transition function is independent of the prior state and action, the authors of [38] show that rng(v") 1 with a simple proof in its Appendix A.2. Hence, by the argument in the preceding paragraph Ô (Arot (1- (1-1111) + (1 - (1--))-7 ?)) samples and time suffice in this setting.
B Omitted proofs from the main body
B.1 Omitted proof of I Lemma 1.3
Lemma 1.3. For a, b. x E IR" a, > 0, let c c:= median (1 - 7) b, a + (1 7)a1), where median is applied entrywise. Then, ||b 201o0 S y la æ01.00 and l|a x: x11.0 a, then
||c - -x01== x1100 S 7 l|a ællxx
Proof. Consider the i-th entry (c x);; There are three cases.
First, suppose a; - (1 - 7)a S b, S a; + (1 7)a. Then, |c - xz1 = 1 -1b,-10 S ||a x 1/
(1 - 7) < a; + +1 71-7)a. Then C - I, 2 b, 24 2 16 x x11,0 2 Second, suppose by < -
-7 a x
loc Mcanwhile, Q -; a; (1 11)aaa- 2, S a x æ11oc (1 7)). Now, because
||a =| oo y =|la-
we have that (1 7) ||a x1100 I (1 7)a. So, |aa x al1.0 oo - (1 7) I
Lastly, suppose a, - - ()- s a; + (1 - 7)a < b, Then, q - x; S b - E2 S b 011,0 S
7 aa æ lloo0 Meanwhile, G. xj a; + (1 7)a r 2 ||a x + +1 7). Now, because
|a - æ11o0 S a, we have that (1 7) la all S (1 - 7)a. So, |a x lll + (1 7) j >
7 la ooooo
B.2 Omitted proof's from Section 2
First, we prove Lemma 1.
Lemma 2.1. Let x = Sample(u, u, p, M,0) for p E A", M E Z,o. & > 0, and u E R.S. Then, E [x] = p |z| < |24|| por and Var [z] < 1/M ||ull3.
Proof. The first statement follows from linearity of expectation and the second from definitions. The third statement follows from independence and that
Var [c:... = Σ pru - (p v)²
<
ps || = || for any m E [M]
iES
IES
Next, we state Freedman's 's inequality [35], which we use to prove the following Lemma 2.2.
Theorem B.1 (Freedman's 's Inequality, restated from [36]). Consider a real-valued martingale (Ys= k O, 1, ...} with difference sequence (X+ k 1,2. given by X = Ys Yk-1- Assume that X₁ I R almost surely for k = 1,2,... Define the predictable quadratic variation
process of the martingale: Wt := Σ} E |X X,-1]. Then, for all t > and o² > 0,
P (3k > 0 Ys 2 t and Wi S o²) < exp (-t/(22(0 RRt33))
15

---

Lemma 2.2. Let T E Z>o and w((), wil)) ..... w(T) R such that || ww(-1) T for all [T]. Then, for any pe E A 8 E (0, and M 2 2 log(2//0 with probability 8.
p (wol) wl Eiel! MjE[M] Sample(wl 10, ,p 1, 1/M T/8 2/88for all I [T].
Proof. For each E j E [M], let
X (Samlleww ((i-1) p. p,,,0) - /M.
-
Since p A Lemma 2.1 yields that [X,م] - M Next, define Yí, EiE(t-1] EjE[Mi X
Σj=1 Xt.. The predictable quadratic variation process (as defined in Theorem B.1) is given by
Wex = E Σ
E E
X1,1:M X1-1,1:M X1115-11
+
Σ
E [x2 X1-1,1M X1.1--11
SE(K]
Sample(w - -i ,p.,1,
Sample (w))))((()))))))) w ...pp.pp.. 1.0)
= Σ
Σ
Var
+
Var
M
M
JE
72
TT
Σ
M2
M
JE
where, in the last line used Lemma 2.1 to bound the variance. Now, by telescoping,
Sample(w w 1), p.)1.0)
YIM =
-p (T((()) ()) for all allte e [2]
M
JEMM
Consequently, applying Theorem B.1 twice (once Yú,s and once -Y,, yields
P f [T]
|Y,M
[ 8
2xxp
(T/8)²
exxp
-M
88.
TT 2(
2r
27 + 12
1
M
M
As immediate corollary of Lemma 2.2, we obtain Corollary 2.3.
Corollary 2.3. In TVRVI (Algorithm 3), with probability 1 8, in Lines 10 and 2, for all E S,a E A,, and l E [4], we have g ( Pa(s) (v(6-1) (c(())(v(((1) -
I (1 7)//88 and
therefore g! is a (1 (1- (111-)))/4aee 7))/44-uderesstimnt of Pa (s) ((o(o(1)))))))) xz()))
Proof. Consider some S and E A,. Note that ga ( (8) is equal in distribution to
Σ Sample (()) w(i-1) (s)..)..0)
Σ
-P((s) (w(e- (P (v(t-1)-o())
M
[E(M_1]JE[M]
Then, by Lemma 2.2 and union bound, whenever M 2 L log(22 (2Arot/ we have that with probability - 8, for all (s,a) E A, gu (s) (s)s) (w(e-1) - (0)) I L and conditioning
on this event, we have (s(s) (o(f-1) the shift in Line 10.
(((s)(( 1) ((0) 3 a S gl (s) S Pa(s) (w(f-1) ()))) due to
Conditioning on the event that the implication of Corollary 2.3 holds, can prove the following Lemma 2.4
(o 33 33 < x < (o and let B., E SRS be defined as Gar (s) := (rr(,) (s) for each E S. Then, with probability 1 ô, at the end of every iteration
Lemma 2.4. Suppose that for some B E TR
L [L] (Line 3) in (v)) T x, a. 8), the following hold == 7(11 - 7)/7))///// /41 11 ). (e-1) < (0) s Txio
0 S 0² ( S max (vp"(u* - o((-1)) + E, 7 o((-1))).
16

---

Proof. In the remainder of this proof, condition on the event that the implications of Corollary 2.3 hold (as they occur with probability 1 d). By Line and 8 of Algorithm 3, for all & [4].
(e-1)) 1) S (0) I v (f-11) 1) + (1 - 7)a1.
This immediately implies the lower bound in (6).
We prove the upper bound in (6) by induction. In the base case when ( = 0, v(0)) S no) (v(0) holds by assumption. For the l-th iteration, there are two cases. If el( > v(t-1)(s) for s E S then
20 (s) - n: (s) + 7 (0(()) + g S TncO (8) + PPTco (s)
(10)
S T (x(ee(11)1)) S Tx(c (v)
Otherwise, if (s) (((-1)(s), then by the inductive hypothesis,
0 (5) (s) TT:e- (o Tace (x))))))))
This completes the proof of (6).
Next, we prove (7). For the lower bound, by induction and (10), we have that for each E S
) (s) S max + (s) (( s (rx + (s) o² (s))
v",
aEA.
aeA,
so min(((())))))) ((-1)) + (1 7))) S v²
Next, we prove the upper bound of (7). For each (8) E A and é E [L], let
( == Pa(s) x (I) (zx (s)).
and observe that
xa(s)]= + - - s Ba(s) + (1-1)a (s) = (sa -10)
Note that for any E S.
(v" )()) = maxx(ra(s) + (p)ss) v'(s)]
max (ra(() (s) + 7 (Ia (s) + (s))] aEA.
rEA:
S (s) + (P')') (s)] max(ral (8) + (s) T 018-1) 7g!
aeA.
S (s) + (P*0") (8)] - (8**())8)+ +
PM (P* 22 (8)
2> pd p' - -p v((-1)) (8) + +{(s),
Consequently, for all s E S,
(0" (()) Pp" o (()-)))(s) + E(s).
Consider two cases for (8) (s). First, if (s) =6(0(s) for some E S then
(o* - v(t) (s) > (p* (2' - -b((-1))) (s) + E(s)
holds immediately. If not, (0 (s) (s))
+ (1 1-7a s 5(0 and (6) guarantees that
0² -e--
< -0* (0) Sa,
x
which ensures that (1 - (1-7)(00 - ((())))((s) S (1 -7)a and yields the results as,
(x+ v10) (s) (o-- - o((-1)) (s) (1 1-7)a S x (o+ ult v(t-11) (s).
We now inductively apply Lemma 2.4 to obtain Corollary 2.5, which allows us to bound the number of iterates required to halve the initial error in TVRVI.
17

---

Corollary 2.5. Suppose that for some 2 0 and B E 20 P - P
v10) is an
a-underestimate of v²; and ( S T (v(0)). ) Let 3.. RRS be defined as Bx (x) (s) for each 8 E S. Let (v(L), x(b))- (VRVI π (1),, a, 5), and L, M be as in Line Define & == Y ((1 - /)/44/441111 1 ). Then, with probability 1- 5, 0 0" v(L) S 7 a. 0. 10.11+I--00 (I--Pt)--1 and (h & Tua (u(1)). In particular, if B = 0, then for L > log(8) 7) we can reduce the error in (0)) by half: 0 v² L I (w- - //2)) Additionally, TVRVI is implementable with
OAArr LL) sample queries to the generative model and time and O (Aeot) space.
Proof. Condition the event that the implication of Lemma 2.4 holds. First, observe that 0 v² xz(l) I v² xx()) follows by monotonicity (Equation (6) of Lemma 2.4). Next, show that
V o 1 S S3aa 1 1+ -1----"")
by induction. We will show that for all e S.
yall
Σ k=
* c
In the base case when this is trivially true, as 0² v()) I al by assumption, Assume that the statement true up v(--1), Now, by Lemma 2.4, we have cases for [v ----0% (i))
First, suppose that [V- -v(0(()) I 7/00 v(()))((i). Then, note that p and & are entrywise non-negative, so h p ( 2 O. By inductive hypothesis, and the fact that y (0, 1) we have
(V" 10'-0'0000 S (00-1) a
Σ K=
(i)
= +7
Σ
p
(i) s 2 +
Σ x p & (1)
(1)s
Σ t p
(1)
k==
[rra
Σ k=0
k R g
(i).
Second, suppose that instead, -0-- v(0 S 1yp* (v- - ((t-1)) + By monotonicity (equation (6) of Lemma 2.4) we know that v" v(e-1) > O. Moreover, P is non-negative, and consequently, we can use the inductive hypothesis as follows:
[ p
6-1
(o- ((- s
hence p (0--v(l-1)) vlt-11) < p f allll Σ *
k=0
k=
We can rearrange terms to obtain the following bound:
(0" - (0))() < ypp (ntt-Da
E-
+
Σ
p
g
(1) E(1)
k=
= =>/a|P'1((t++ +
Σ
E1t1p p p
(1) E()) 1 //al+ Σ *p (1).
km0
Consequently, by induction, the bound holds. When L >> log(8)(1 -1, ,, < 118 and have
v" - U2 < - 11 1+
a (1-11)) a1 < a
7
a 2
Finally, the sample complexity and runtime follow from the algorithm pseudocode. For the space complexity, at each iteration & of the outer for loop in TVRVI, the algorithm needs only to maintain (()) E Ass, (L) E S ILL), and at most M Atot samples in invoking Sample.
(())g(())
18

---

Finally, we are ready to prove Theorem 1.2.
Theorem 1.2. In the offline setting, there is an algorithm that uses ((nnz(P) + Abot -) -2) time, and computes an e-optimal policy and E-optimal values with probability 1 - ó.
Proof. To run Off we can implement a generative model from which we can draw samples in (nnx(()) pre-processing time, that each query to the generative model requires (1) time. For the conrectness, induct on k to show that after each iteration k, 0 S v* Ux I o* - -U I ag with probability 1 - Kō/K. K. In the base case when = O. the bound is trivially true ||00 probability - kö/K, 0*
(1 7)_ Now, by Applying Corollary 2.5 and union bound, we see that with
# Ot,, whenever L > log(8)(1 (1-)))11)))))))))))) - Thus, Ok satisfies the required guarantee whenever ak S E, which is guaranteed by our choice of K. To see that x is an E-optimal policy, observe that Corollary 2.5 ensures
Tk Tap (vw) T (v)) S
T (Ux)= 0Tth 0²
For the runtime, the algorithm completes only K = (1) iterations, and can be implemented with Õ(1) calls to the offset oracle. Each inner loop iteration can be implemented with ( I.2) = ò ()) additional time and queries the generative model. The algorithm only requires 0 (Aoot) space in order store offsets, values, and approximate utilities.
B.3 Omitted proofs from Section 3
Theorem B.2 (Hoeffding's Inequality and Berssten''s 's Inequality, restated from Lemma E.1 and E.2 of [3], Let E A be a probability vector, v E IR", and let y := m > v(i;) where in are
random indices drawn such that ij k with probability p(k). Define a (p upT2² 2 (p (p)))) For any 8 E (0, 1), the following hold, each with probability 8:
(Hoeffding's Inequality) 1p v y $ 11 2m log(25-1) 1) (Bernstein's 's Inequality) (p T v y S v 2mm log(20-1) (2/3)m ||0| logll8811
Theorem B.2 illustrates that the error in estimating Pu for some value vector depends the variance o. := Pu - (Pu)² E R-A, To bound this variance term, we appeal to the following two lemmas from [3].
Lemma B.3 (Lemma 5.2 ([3]), restated). vo. S Vo. + -|00 ol1o0 1.
Lemma B.4 (Lemma C.I of ([3)), restated). For any nI, we have
1+1 [ - PI- 12- < 72 - 7)3
We can now bound the error in estimating Pu using ApxUtility( N. The following Lemma 3.1 obtains such bound by following a similar argument to that of Lemma 5.1 of [3].
Lemma 3.1. Consider u RS. Let ApxUtility(u, m Auot, n), log(1/28~1) and
= -mme - (1/21/1-1), Then, with probability -,
Pu 2 2m (2 | v o'lloo -18 /2el(c)) S S Pu.
Proof. For E 8 and E As. Let i,, in S be random indices such that P =t] (s)) for each.j E [N]. Define the vectors w and o as follows.
N ulis) and oa
N
1
(s) = N
Σ
(u(i;))² (it (s))
N
#=1
1=1
19

---

From the pseudocode of ApxÚtility (Algorithm I), we see that that a = --= 2--v 1100-410 - ||20l100 (2/3) |u|l Now, by union bound over all state-action pairs (s, a) and Theorem B.2, we have that with probability 6/2 for each sate-action pair (s,
x Pux I 2n + 27/1ulloe 1.
(11)
and with probability - 8/22 for each sate-action pair (s,a).
Σ
- (P)())
u²
S u 2m
N
JE[N]
Consequently, by union bound and triangle inequality and (11), we have that with probability 1 both of the following hold.
- -Pullo I 2n + 3" 1/ 1, and ||ō - oulloc I <4 $41120/20 2n11
(12)
We condition on (12) in the remainder of the proof. Now,
Pul S / 2/10 + (4n2/4 |/ell + 3" |1/e 1. σ
and we have that
Pu - 21jō
| + + /11ellloo
1 S x S Pu.
By (12) and Lemma B.3, we have that for a a: l|u - v²1 v'1loo.
Vo E Vou 2| (2n) 1/41 S vo. +al + 22//olloo (21) 1/41,
which implies that
4 x 2 Pu 2 2/ 2m/a1 - 16//3/1 ||el| 1
3"l |1 1/22l10 1.
Since S 1,
2 2 2//00 + (2/210 + 16/ |lull +
s 2 + (2 20j + 18/ [ 3"l |1ll
4
Theorem 1.1. In the sample setting, there is algorithm that uses Ö( samples and time and O(Aro) space, and computes an c-optimal policy and E-optimal values with probability 1-5.
Proof. Let K, aye. (0k: TK), and N₂ be as defined in Lines 1, 4. 9, and 6 of SampleTVRVI(s.0) First, we show, by induction that for each [K]. with probability 1 k8/K
0 x² Th e² U 0g and ds S Tmp (Ux).
In the base case when & the bound trivially true because 0 S 0² Uxo I 00 000-00 S (1-
Now, for the inductive step, by Lemma 3.1 we see that with probability 8/K,
Pok-1 2 20--10.- + (2 (2 20 + 18 3/4 1 1
S Es S P
(13)
and, by inductive hypothesis, with probability 1 - (k 1)5/K,
S x² Te-1 < x² Uy S a and Up S TT (VE-1).
(14)
Consequently, by a union bound, with probability k5/ K, both (13) and (14) hold. Condition on this event for the remainder of the inductive step.
20

---

Next, we can apply Corollary 2.5 with
B = 27 + (2 3/4
10 1.
Therefore,
0 0S 2k -
Ex-1 S 0k-1 1 (I ? Ex-1
for Ek-1 I ao
+ 22 + 181 1 00
1. By Lemma B.4
and the facts that 7/-1 S we obtain
(6500- 11-))- -3 *max( (1- 7), - 1)
and (1 P -1 1 1/ 71 1.
(I - (
Ek-1 S
0k-1
+21 (1 7)3 +/1
61jk-1
2(1 - min 0 Or--1
4
6500 7)2
((1 - 7)3 "mmii(1
- ((1-)))mmn((()
1, 3/47
+
18
6500(1 7/8/3
lak-1/4 1/4 2 6/6500 - + 22/2/600
1/2 min((1 - -7)-1/2 ,0k-1)o
+ 18 (10 (10- 1/4 min(m1 - 7) -3// 3/4,, 221111
3/2
3
1ax 14 + 4v 6/6500 ak-1 + 18 (10 (10- Jok- i]1 S 0h-11
Consequently, V² Us S a/21. To that Te is also au-omtimal policy, observe that Corollary 2.5 also ensures that
2k S Tax (v)) (vx) S S TTe = 0T S²¹
This completes the inductive step.
Consequently, for K = [log2 (E - (1-7) iterations, 2 ak 2 E/4 and with probability 1- 6, UK is E-optimal value and л is e-optimal policy.
For runtime and sample complexity, note that the algorithm can be implemented using only Ō(Nx) = Ō((1 - >) - --- + (1 -samples and time per state-action pair. For the space complexity, note that the algorithm can be implemented to maintain only O(1) vectors A.s...
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the abstract and introduction state our main results and improvements over previous work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we discuss regimes where our result is optimal and where may be suboptimal in the introduction. In the conclusion we also discuss directions for future work and open problems left open by our work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: Sections 2 and 3 of our paper give a sketch of how we obtain our main theorems, and full proofs of all intermediate results well as the full theorems can be found in the supplemental material/appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper focuses on theoretical results and mathematical analysis and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
23

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper focuses theoretical results and mathematical analysis and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips) cc/
Degllic/uudde/CodeeSuiee heaibbmissiooooiccyy... for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iiss... wwwpcccpppc/..ec.cc...ccce.cetle heablicgguides//.//eeee /tt.geee/ooooeuuuaiiiiiii SCodeSuumissionn sewiiisssiiciiiiyicooocioiiiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification:
The paper focuses on theory and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper focuses theoretical results and mathematical analysis and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
24

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper focuses theoretical results and mathematical analysis and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http///neeipppeeeeeeeee cc/public////cpcctccccccccccccct Beeicc//thiissee csuuidelinei
Answer: [Yes]
Justification: Yes, we have read and conformed to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction)
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper focuses foundational theory for solving MDPs and is not directly tied to any specific socictal impacts (positive or negative). We not expect any direct, immediate, substantial societal impacts.
Guidelines:
25

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper focuses on foundational theory and does not pose any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not use any existing code/data/model assets because we do not have any experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
26

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcee thcode com/ con/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper did not involve crowdsourcing research with human subjects.
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper did not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "KMeaqmnx96", "reviewer": "Reviewer_ENzu", "summary": "This paper introduces Truncated Variance-Reduced Value Iteration (TVRVI), which enhances the previous prior state-of-the-art sample complexity for computing an $\\epsilon$-optimal policy in both offline and sampling settings. Specifically, in the offline setting, where the probability transition matrix is known, Theorem $1.2$ established a sample complexity of $\\tilde{O}(nnz(P)+\\mathcal{A}(1-\\gamma)^{-2})$ which improves previous bound of $\\tilde{O}(nnz(P)+\\mathcal{A}(1-\\gamma)^{-3})$ sample complexity. In a sampling setting, where the probability transition matrix is unknown but accessible through a generative model, Theorem $1.1$ established a sample complextiy of $\\tilde{O}(\\mathcal{A}((1-\\gamma)^{-3}\\epsilon^{-2}+(1-\\gamma)^{-2})$, improving upon previous  $\\tilde{O}(\\mathcal{A}((1 \\gamma)^{-3}\\epsilon^{-2}+(1-\\gamma)^{-3})$ bound. In both settings, TVRVI requires $\\tilde{O}(\\mathcal{A})$-space, provided suitable access to the input, and aim to efficiently compute a coarse approximation of the optimal policy for large $\\epsilon$.", "questions": "(0) Are these theoretical results the state-of-art even if $\\epsilon$ is small?\n\n(1) Could you clarify why it's okay to ignore polylogarithmic factors involving  $\\epsilon$ and $\\delta$? \n \n(2) I wonder if this kind of theoretical sample complexity results lead to practical benefits or is more meaningful from a theoretical perspective. For instance, in convex optimization, Nesterov's accelerated gradient descent demonstrates theoretical acceleration and holds significance in the literature of complexity lower bound rather than for its practical applications (While adaptive Nesterov's type algorithm like Adam works well in deep learning, I believe Nesterov's acceleration is more meaningful from a theoretical perspective),\n    \n (3)  In line $5$ of Algorithm $1$, could you explain the intuition of the offset parameter and subtraction with different powers?\n   \n(4) Could these analyses be extended to the settings where the reward is unknown or average reward MDP?\n  \n (5) In line 27, why do we need condition $|\\mathcal{A}| \\ge |\\mathcal{S}| $?\n\n            \n (6) In line 98, does `nearly-linear' indicate quadratic?\n              \n (7) In line 100, why it is $\\epsilon$? If $\\epsilon = O(1-\\gamma)^{-1/2}$, isn't it $\\epsilon^4$?\n\n(8) References [1] and [2] seem the same.\n\n(9) References [17] and [21] seem the same.\n\n(10) In line 104, what is the definition of $w$?\n\n(11) In line 191, $v^{(t-1)}$ should be changed to $v^{(t)}$ \n\n(12) In line 193, typo $v^{(0)}$\n\n(13) In line 276, typo $v^{(0)}$\n\n\n\n\n (14) In line 282, need spacing.", "limitations": "Yes, the authors addressed limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Incorporating Freedman’s analysis, truncation, and other variance reduction techniques from prior works, this work provides a state-of-the-art bound on sample complexity. The high-level idea is demonstrated, and detailed comparisons with prior work are provided. It's worth mentioning that in the literature on the theoretical analysis of sample complexity, the application of increasingly generalized inequalities —progressing from Hoeffding [2] to Bernstein [3], and now to the Freedman inequality in this work— has led to incremental improvements in theoretical results.", "weaknesses": "There are no experimental results, and I am uncertain about the ignorance of the polylogarithmic factors involving  $\\epsilon$ and $\\delta$. Also, in the comparison tables, the range of $\\epsilon$ is not the best.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback! We responded about experiments above and discuss your questions here.\n\n**Applying stronger inequalities-- Hoeffding [2], Bernstein [3], Freedman [this paper] has led to improvements.** \n\nAs discussed in the main rebuttal, Freedman _alone_ is insufficient to obtain our improvements. We also needed two _novel algorithmic changes_ (truncation + recursive variance reduction.) Our key insight is the _combination_ of stronger algorithmic tools plus improved concentration analysis.\n\n**I’m uncertain about ignoring polylogarithmic factors.** \n\nPlease see Q1 below. \n\n**The range of $\\epsilon$ is not the best in the tables.** \n\nIn _Table 1_, all methods have polylog $\\epsilon$ dependence, so there’s no $\\epsilon$ regime constraint. In _Table 2_, [18] has a larger $\\epsilon$ range. However, Table 2 shows just an improved $\\epsilon$ range for _query complexity, not runtime_. As discussed in Lines 48-77, [18] is _model-based_, so it has higher time and space complexity than ours. \n\n**Q0: Are the theoretical results state-of-the-art even for small $\\epsilon$?** \n\nYes, we _match_ state-of-the-art optimal algorithms in the small $\\epsilon$ regime (up to logs) and _improve_ for large $\\epsilon$ regime [Lines 91-94]. \n\n**Q1: Why can we ignore polylogarithmic factors in $\\epsilon, \\delta$?** \n\nIt’s standard to hide polylogarithmic factors (polylogs) in the parameters $\\epsilon$, $\\delta, (1-\\gamma)$, $|\\mathcal{S}|$, and $\\mathcal{A}_{tot}$ inside tilde-notation $(\\tilde{O}/\\tilde{\\Omega})$ in this line of research (as in much machine learning, optimization, and algorithm design theory literature). The long line of work on this problem [2, 3, 17, 18, 24] follow this same convention when comparing methods; thus, ignoring polylogs is natural/important for comparing prior state-of-the-art results. Note the polylogs hidden inside tilde-notation _are not hiding exponential terms or new problem parameters_. Moreover, these polylogs are quantified explicitly in the main body (in all “algorithm” environments and intermediate lemmas) for full transparency. We may investigate ways to make these polylogs more explicit in the formal statements of Thm. 1.1 and Thm. 1.2 in the camera-ready version. To briefly explain why this is convention: polylogs scale much better than polynomial factors, so, when designing algorithms with theoretical guarantees, we focus on improving polynomial factors and not the, relatively, lower order polylogs.\n\n**Q2: Do the methods lead to practical benefits aside from theoretical benefit (e.g., AGD vs. ADAM)?** \n\nOur motivation is the theoretical perspective (as in [3, NeurIPS ‘18] and [17, NeurIPS ‘20] and [15, NeurIPS ‘98]) of better characterizing the fundamental mathematical limits of what runtime/space/sample complexities can be achieved for RL with a generative model. It’s possible our techniques may motivate further practical improvements/analogs, but this is outside the scope of our current work. \n\n**Q3: Why the offset parameter in Alg. 2?** \n\nGreat question! We didn't have space in the submission, but plan to use the extra page of camera-ready to include a discussion of this. \n- Why the offset? The offset shifts estimates of the expected utilities _down_ so that the _shifted estimates_ are _underestimates_ of the true expected utilities. This technique is adapted from [3] and lets us convert optimality guarantees on values to optimality guarantees on policies. If our estimated expected utilities are always underestimates, then one can show that at each iteration _our current value vector estimate is an _underestimate_ of the true value of the current policy._ Note that this ensures that if our current _value_ is $\\epsilon$-optimal, the policy must _also_ be _at least_ $\\epsilon$ optimal! As a further note, this offset enables us to get fine-grained bounds in Section 3 and Appendix A (this arises in the proofs of Theorem 1.1 and Theorem A.1). \n- Why those specific powers? If we use Berstein to guarantee that we _shifted our original estimate down_ far enough be an _underestimate_ of the true utilities, then these terms are what we need to subtract in order to succeed with probability $1-\\delta$ (see for instance, in the proof of Lemma 3.1.)\n\n**Q4: Do the methods extend to average-reward or unknown rewards?** \n\nGreat question! [A] reduced solving average-reward MDPs (AMDPs) to solving discounted MDPs for a sufficiently high discount factor, so our method can apply to AMDPs. We also believe the techniques might be amenable to unknown rewards, but this is an open question. We believe the previous works cited in our tables do not directly consider the unknown reward case either, so it is slightly outside the scope of our work. [A] Yujia Jin and Aaron Sidford. Towards Tight Bounds on the Sample Complexity of Average-reward MDPs. ICML ‘21. \n\n**Q5: Why should $|\\mathcal{A}| \\geq \\mathcal{S}|$?** \n\n$\\mathcal{A}$ is _all state-action pairs_ so $|\\mathcal{A}| \\geq |\\mathcal{S}|$ just ensures we have at least one action available in each state.\n\n**Q6: What is nearly-linear in Line 98?** \n\nHere, it means $\\tilde{O}(A_{tot}(1-\\gamma)^{-2}\\epsilon^{-3})$ because it is equal (up to logs and constants) to the optimal number of samples, $\\tilde{\\Omega}(A_{tot}(1-\\gamma)^{-2}\\epsilon^{-3})$. \n\n**Q7: Can you explain Line 100?** \n\nThm. 1.1 runs in $\\tilde{O}(A_{tot}[(1-\\gamma)^{-2}\\epsilon^{-3} + (1-\\gamma)^{-2}])$. Suppose $\\epsilon = O((1-\\gamma)^{-1/2})$. Then, the $\\tilde{O}(1-\\gamma)^{-2}$ is lower order, and the runtime is $\\tilde{O}(A_{tot}(1-\\gamma)^{-2}\\epsilon^{-3})$, which matches the lower bound of $\\tilde{\\Omega}(A_{tot}(1-\\gamma)^{-2}\\epsilon^{-3})$ up to logs/constants. \n\n**Q10: What is w in Line 104?** \n\nIt is little-omega. A function $f(n)$ is $ \\omega(1)$ if $\\lim_{n \\rightarrow \\infty} f(n) = \\infty$. We’ll add a definition in camera-ready!\n\n**Q8-9, Q11-14: Typos** \n\nThanks for pointing out the duplicate references and typos. We’ll correct in the camera ready!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f7hmdH4nLS", "reviewer": "Reviewer_FfgG", "summary": "The paper provides a randomized algorithm to compute nearly-optimal policies in DMDPs (in the bounded-reward setting) for regimes where the probability transition matrix is either known or unknown. The sample complexities in the paper removes a multiplicative factor of $\\frac{1}{1-\\gamma}$ on one of the terms in each regime. The algorithm provided is model-free and only requires $\\tilde{O}(|A|)$ space. The main claims are all rigorously supported by proofs to verify this work, and (broadly speaking) this work is an important stepping stone towards closing the sample-complexity gap between model-free and model-based methods.", "questions": "See weaknesses.", "limitations": "None.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1) In the sample setting, the algorithm runs in nearly linear time in the number of samples, for a particular choice of $\\epsilon$, which is a novel result.\n2) The analysis differs from existing works in the way the utilities are computed - this work uses a recursive variance reduction method.\n3) In general, the proofs are non-trivial and quite hard to follow, emulating much of a TCS style of writing - but they are all quite rigorous and well-resented. The method uses an elegant construction of $\\nu^{(t)}$ as a supermartingale and adapts Freedman’s inequality with some of the methods from the large-deviations literature. It is interesting that this rather simplistic change in approximating the utilities $g^{(t)}$ results in the drop of the $\\frac{1}{1-\\gamma}$ multiplicative term!", "weaknesses": "I wonder if the constants in Lemma 2.2 and in the burn-in phase in algorithm 6 can be strengthened? A constant of $10^4$ in the term $N_{k-1}$ might not be so practical... I will emphasize that this is of less concern since this paper primarily focuses on theoretical results and mathematical analyses. Beyond this, I do not see any other potential weaknesses. I checked the math as well and it seems sound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! \n\n**Comment/Question: Can the constant of $2^8$ in Lemma 2.2 or the constant of $10^4$ be tightened?** \n\nRegarding the comment about the tightness of the $10^4$ constant in $N_{k-1}$, from a quick calculation, we believe it can be lowered to roughly 6500. We think further improvements in this leading constant should also be possible, but this may come at the cost of slightly larger log factors (e.g., from the analysis in the proof of Thm. 1.1.) because in the proof we have some flexibility to trade off whether constants appear up-front or inside of polylog factors in $\\epsilon, \\delta, |\\mathcal{S}|, \\mathcal{A}_{tot}, (1-\\gamma)$. \n\nSome improvement might be possible in the case of the constant of $2^8 = 256$ in Lemma 2.2, but it is less clear how to do this without paying larger constants inside polylog factors in $\\epsilon, \\delta, |\\mathcal{S}|, \\mathcal{A}_{tot}, (1-\\gamma)$. \n\nAs you already noted, we did not try to reduce constants too much as it wasn’t the focus of our work; however, we will certainly make an effort to tighten the constants where possible ahead of the camera-ready! Thanks for the suggestion!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FwIWbta71x", "reviewer": "Reviewer_r2NT", "summary": "The paper considers the problem of finding an $\\varepsilon$-optimal policy of a discounted Markov decision process. Under the generative model, they propose a new algorithm with an improved the sample and time complexity. They also propose an extension to the case where the probability transition matrix is known and $s$-sparse. The core idea of the paper is to use a new variant of variance reduced learning called the truncated variance reduced learning, where the updates are truncated to ensure that the variance of the updates can be controlled.", "questions": "1.  Can the authors explain how they claim that model based methods use $\\Omega(\\mathcal{A}\\_{\\text{tot}}(1-\\gamma)^{-3} \\varepsilon^{-2})$ memory? The model based methods do not need to store all samples and can simply store the probability transition matrix which takes $\\mathcal{O}(|\\mathcal{S}| \\mathcal{A}_{\\text{tot}})$ memory. \n\n2. The advantage of this work over that in [3] (as cited in paper) is mainly that truncation directly allows to control the burn in costs. By ensuring that one uses only $\\mathcal{O}((1-\\gamma)^{-2})$ samples in each iteration, one directly gets the leading term of $\\mathcal{O}((1-\\gamma)^{-3})$ and the burn-in of one iteration. On the other hand, in [3], the burn in is $\\mathcal{O}((1-\\gamma)^{-3})$ (corresponding to sample complexity of one iteration) and the leading term is controlled by careful analysis using variance of the optimal value function. Is my understanding correct? It seems that the analytical simplification is what is at the core of the contribution. Is there something else that is happening at a more fundamental level or just that the new approach offers improved analysis?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I like the core idea of the paper to use truncation to control variances in the recursive variance reduction. Although simple, it seems to be quite effective.", "weaknesses": "Please see the next sections for my comments.\n\n\nA minor comment: There seem to be a lot of typos throughout the paper, both in terms of formatting issues and spelling errors. I would suggest the authors to carefully go through the paper and address all of them for the final version.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedack! We’ll carefully address the misspellings/typos ahead of the camera-ready. \n\n**Q1: Can the authors explain how they claim that model-based methods use $\\Omega(A_{tot} (1-\\gamma)^{-3} \\epsilon^{-2})$?** \n\nGood point, indeed, the model-based methods actually only require $\\Omega(A_{tot}  \\min( (1-\\gamma)^{-3} \\epsilon^{-2}, |\\mathcal{S}|))$-space. So, in the regime where $|\\mathcal{S}| < (1-\\gamma)^{-3} \\epsilon^{-2}$, you are correct that the space of the model-free methods could be better. We will be certain to correct/clarify this nuance in the camera-ready, and thank you for pointing it out.\n\n**Q2: The advantage of this work over that in [3] as cited in the paper is that truncation directly allows us to control the burn-in costs by ensuring that one uses just ${O}((1-\\gamma)^{-2})$ samples per state-action pair per iteration, whereas in [3], one required $O((1-\\gamma)^{-3})$ per iteration and the leading term was controlled by careful analysis of the variance of the optimal value vector. Is my understanding correct, or is there something happening at a more fundamental level?**\n\nWe addressed this at a high-level in the overall rebuttal response, but we’ll elaborate a bit here. Your perspective has a lot of alignment with our perspective, but we’ll just elaborate on a few points where our perspectives might differ. \n\nRecall, the model-free methods [ours and [3]] run $\\tilde{O}(1)$ rounds, where each round halves the error in some initial value $v^{(0)}$. Each round works as follows (at a high level):\n\n* Estimate $Pv^{(0)}$ using samples\n* For each of $t = 1, 2, 3, ... , T = \\tilde{\\Theta}(1/(1-\\gamma))$ iterations \n  * Maintain estimates of $P(v^{(t-1)} - v^{(0)})$\n  * Run one step of approximate variance-reduced value iteration using these estimates \n\nFirst, you correctly noted if the leading order term (number of samples required in Step 1.) is just controlled using the bound on the variance of the optimal values similar to what was done [3]. Indeed, this is exactly how we bound the leading order term. \n\nSecond, you correctly noted that our main improvement is that we manage to maintain step (2a) using just $O((1-\\gamma)^{-2})$ samples per state-action pair per iteration using a more sophisticated maintenance procedure. In contrast, [3] required $O((1-\\gamma)^{-3})$ per iteration to maintain step (2a)). _However our improvement doesn’t come directly from truncation alone_. Concretely, our method differs from [3] in the following three ways: \n- _What [3] does_: \n  - In [3], Step (2b) is maintained by just estimating $P(v^{(t-1)} - v^{(0)})$ with new samples in each iteration.\n- _How we maintain Step (2b) with fewer samples:_ \n  - **Recursive variance reduction:** At step $t$, notice that estimating the entire difference $P(v^{(t-1)} - v^{(0)})$ from scratch might be inefficient. We instead just estimate the marginal difference $P(v^{(t-1)} - v^{(t-2)})$. Then, we _leverage all our previous estimates from all the previous iterations_: $P(v^{(t-2)} - v^{(t-3)}), ...,   (v^{(1)} - v^{(0)})$. These automatically telescope to $P(v^{(t-1)} - v^{(0)})$.\n  - **Truncation:** Recursive variance reduction on it’s own doesn’t yield a theoretical improvement; but intuitively, it is useful if we can make sure that the entrywise maximum of $P(v^{(t)} - v^{(t-1)})$ is quantitatively smaller _entrywise_ than $P(v^{(t-1)} - v^{(0)})$. We do this by using truncation to ensure that our worst-case bound on $P(v^{(t-1)} - v^{(t-2)})$ is a $(1-\\gamma)$ factor smaller than our worst-case bound on $P(v^{(t-1)} - v^{(0)})$. \n  - **Analysis:** To show that the preceding algorithmic ideas provably lead to an improved sample complexity, we need to model the recursive variance reduction procedure as a martingale and use Freedman’s inequality.\n\nSo, in summary, two algorithmic changes and one analytic change enable our improvement-- truncation is just one piece.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eIYoCWiGU0", "reviewer": "Reviewer_fJN4", "summary": "This paper proposes a new faster randomized algorithms for computing an $\\varepsilon$-optimal policy in a  $\\gamma$. discounted MDP The authors give an $\\tilde{O}(A_{\\text {tot }}\\[(1-\\gamma)^{-3} \\varepsilon^{-2}+(1-\\gamma)^{-2}])-$ time algorithm in the sampling setting, where the transition matrix is unknown but accessible through a generative model which can be called in $\\tilde{O}(1)$ time, and  in the offline setting an $\\tilde{O}\\left(s+A_{\\text {tot }}(1-\\gamma)^{-2}\\right)$-time algorithm where the probability transition matrix is known and $s$-sparse. This bound is attained using stochastic variance-reduce value iteration methods. Moreover, they provide a variant that carefully truncates the progress of its iterates to improve the variance of new variance-reduced sampling procedures. The advantage of their method is that in model-free that it can be implemented in $\\tilde{O}\\left(\\mathcal{A}_{\\text {tot }}\\right)$ space when given generative model access.", "questions": "6) Do you  think it may be possible to bridge the sample complexity gag between model-based and model-free method using variance reduction techniques ?", "limitations": "No limitation.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) The question of improving the computational cost per sample in computing optimal policies in DMDPs is a central question to tackle in MDPs.\n4) The upper bound in terms of number of queries is state of the art for model free algoriths, for large $\\epsilon$.\n2) Maths are well written and proofs seem correct for me.\n3) The truncated variance VI is a nice idea and may also lead to practical algoithms with lower computational cost.", "weaknesses": "4) The paper is sometimes difficult to follow.\n5) I know that it is a theoretical work but a simple example on finite MDPs would be interesting to validate the computational cost and validate the new truncated variance VI algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments! We addressed your comment about experiments in the overall response and discuss individual questions here. \n\n**Comment 1: The paper is sometimes hard to follow.** \n\nWe would be receptive to refining any areas that were challenging to follow. Could you please clarify where the writing made following challenging? We are happy to discuss more in the discussion period!\n\n**Q1: Do you think it may be possible to bridge the sample complexity gap between model-based and model-free methods using variance-reduction techniques?**\n\nThis is a great question, and a key open problem! By narrowing the gap between model-based and model-free methods, we believe our paper provides hope that variance-reduction techniques or variants (such as our recursive-variance reduction plus truncation procedure) can be applied to eventually close the gap. \n\nCurrently, the _only model-free_ methods that obtain optimal sample complexity for _some_ $\\epsilon$ regime leverage variance reduction in some form or another, so it seems like it is a very powerful tool. Our work _reduces_ the sample complexity gap between model-based and model-free methods, and we _reduced_ this gap by _combining_ our new ideas (recursive variance reduction and truncation) with ideas from the previous state-of-the art [2, 3]. So, it is perhaps natural to hope that our techniques can be further combined with a few more tricks to close the gap entirely, but this is an open problem. This is an exciting direction for future work, and we hope our work provides useful tools for tackling this research question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thoughtful feedback and questions! We are encouraged that the reviewers had an overall positive view of our work. In particular, we appreciate that reviewers found our truncated variance reduction idea to be nice as well as novel and felt that the problem we study is central/important. 

We address two of the main comments in the reviews below and respond to reviewer-specific clarification in the reviewer-specific rebuttal responses.

1. **Two Reviewers asked if the analytical improvement (due to our improved martingale analysis) was sufficient to obtain our improvement and expressed curiosity about whether truncation or martingale analysis alone is sufficient.**

Thank you for the question! To recap, as discussed in the approach section of our paper [Lines 187-232], we combined two novel algorithmic ideas (1) truncation and (2) recursive variance reduction to obtain our improvements. To analyze these two algorithmic ideas and prove that they lead to improvement, we use (3) a new analytical approach: martingale analysis via Freedman’s inequality. 

We believe all three ingredients are necessary for the analysis to work. We obtained our result only by the _combination of both of these two new algorithmic ideas along with the new analysis idea_. Thus, our novelty is not only the new martingale analysis but also the new algorithmic ideas. Moreover, to the best of our knowledge, using just one of the algorithmic ideas is insufficient. That is, to the best of our knowledge,  
- Using just truncation without recursive variance reduction is not strong enough for the proofs to go through. 
- Using just recursive variance reduction without truncation is also not strong enough. 

2. **Two reviewers noted that our work does not include experiments.**

We agree that the results of an extensive empirical comparison of various model-free and model-based algorithms for this problem would be an intriguing research direction. One potential obstacle in this direction is that, because the related/cited work is also purely theoretical, we are unaware of the extent to which previous state-of-the-art algorithms for the problem have been implemented (e.g., [18 NeurIPS 2020], [17 COLT 2020], and [24 Mathematics of Operations Research 2019]). While we share the reviewers’ enthusiasm for seeing a comprehensive comparison of the variety of state-of-the-art algorithms on synthetic and real-world MDPs; this is outside the scope of our submission. 

We would be happy to answer further questions during the discussion period. Thanks again to the reviewers!

Meta-review: The paper improves upon the existing results on variance reduced model free methods for RL by introducing two algorithm techniques of truncation and recursive variance reduction and the using Freedman's inequality for concentration of martingales. This brings the sample complexity of model free methods (which are significantly more efficient in runtime and memory requirements) to methods that sample and build a model. These improvements apply in the range of epsilon >> 1. Overall the reviewers unanimously appreciated the contributions of the paper as well as the writing and exposition. The improvement shown in the paper are clear, concrete and interesting to a broad RL theory community. The techniques introduced are also interesting to the wider community in my opinion. I am happy to recommend acceptance. I ask the authors to incorporate the comments and use the extra page for more explanations of the pieces as promised.
Decision: Accept (poster)