Truncated Variance Reduced Value Iteration

Authors: yujia  jin
ishani  karmarkar
aaron  sidford
jiayi  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 00:11:46

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.

Main paper: 
 introduction: 
 Markov decision processes (MDPs) are a fundamental mathematical model for decision making under uncertainty. They play a central role in reinforcement learning and prominent problems in computational learning theory (see e.g., [4, 5, 6, 7] ). MDPs have been studied extensively for decades ( [8, 9] ), and there have been numerous algorithmic advances in 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 , r, γ). We consider the tabular setting where there is a known finite set of states S and at each state s ∈ S there is a finite, non-empty, set of actions, A s for an agent to choose from; A = {(s, a) : s ∈ S, a ∈ A s } denotes the full set of state action pairs and A tot := |A| ≥ |S| . The agent proceeds in rounds t = 0, 1, 2, . . . . In each round t, the agent is in state s t ∈ S; chooses action a t ∈ A st , which yields a known reward r t = r st,a ∈ [0, 1]; and transitions to random state s t+1 sampled (independently) from a (potentially) unknown distribution p a (s t ) ∈ ∆ S for round t + 1, where p a (s t ) ⊤ is the (s t , a)-th row of P ∈ [0, 1] A×S . The goal is to compute an ε-optimal policy, where a (deterministic) policy π, is a mapping from each state s ∈ S to an action π(s) ∈ A s and is ε-optimal if for every initial s 0 ∈ S the expected discounted reward of π E[ t≥0 r t γ t ] is at least v * s0 -ε. Here, v * s0 is the maximum expected discounted reward of any policy applied starting from initial state s 0 and v * ∈ R S is called the optimal value of the MDP. Excitingly, a 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 p a (s) are accessible only through a generative model ( [16] ). A generative model is an oracle which when queried with any s ∈ S and a ∈ A s returns a random s ′ ∈ S sampled independently from p a (s) [19] . It was shown in [18] that for all ε ∈ (0, (1 -γ) -1 ] there is an algorithm which computes an ε-optimal policy with probability 1-δ using Õ(A tot (1-γ) -3 ε -2 ) queries where we use Õ(•) to hide polylogarithmic factors in A tot , ε -1 , (1 -γ) -1 , and δ -1 . This result improved upon a prior result of [17] which achieved the same query complexity for ε ∈ [0, (1 -γ) -1/2 ], of [2] which achieved this query complexity for ε ∈ [0, 1], and of [16] which achieved it for ε ∈ [0, (|S| (1 -γ)) -1/2 ]. 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 ε-optimal policies with probability 1 -δ is Ω(A tot (1 -γ) -3 ε -2 log(A tot δ -1 )).Interestingly, recent state-of-the-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-art 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.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 Ω(A tot • min((1 -γ) -3 ε -2 , |S|))-rather than the Õ(A tot ) 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 state-of-the-art model-based methods use Ω(A tot (1 -γ) -3 ε -2 ) samples, the state-of-the-art runtime to compute the optimal policy is either Õ(A tot (1 -γ) -3 max{1, ε -2 }) (using [2] ) or has a larger larger polynomial dependence on A tot 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-the-art runtimes for optimizing DMDPs in the offline setting. Ignoring IPMs (discussed in Section 1.1), the state-of-the-art runtime for optimizing a DMDP is Õ(nnz(P ) + A tot (1 -γ) -3 ) due to [2] where nnz(P ) denotes the number of non-zero entries in P , i.e., the number of triplets (s, s ′ , a) where taking action a ∈ A s at state s ∈ S has a non-zero probability of transitioning to s ′ ∈ S. This method is essentially model-free; it simply performs a 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 A tot (1 -γ) -3 -term in this runtime (see the discussion in Section 1.2.)In this paper, we ask whether these complexities can be improved. Is it possible to lower the memory requirements of near-optimal query algorithms for large ε? Can we improve the runtime for optimizing MDPs in 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 sample-complexity gap between model-free and model-based methods for optimizing DMDPs?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 Õ(A tot )-space provided suitable access to the input. In addition to computing ε-optimal policies, these methods also compute ε-optimal values: we call any v ∈ R S a value vector and say that it is ε-optimal if ∥v -v * ∥ ∞ ≤ ε.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 state-of-the-art such IPM methods obtain improved running times but use Ω(|S| 2 ) space and Ω(|S| 2 ) time and use general-purpose linear system solvers. As such they are perhaps qualitatively different from the more combinatorial or dyanmic-programming based methods, e.g., value iteration and stochastic value iteration, more commonly discussed in this introduction.In the sample setting, our main result is an algorithm that usesÕ(A tot [(1 -γ) -3 ε -2 + (1 -γ) -2 ])samples and time and O(A tot )-space. It improves upon the prior, non-IPM, state-of-the-art which uses [3] and nearly matches the state-of-the-art sample complexity for all ε = O((1 -γ) -1/2 ). See Table 2 for a more complete comparison.Õ(A tot [(1 -γ) -3 ε -2 + (1 -γ) -3 ]) timeTheorem 1.1. In the sample setting, there is an algorithm that usesÕ(A tot [(1-γ) -3 ε -2 +(1-γ) -2 ])samples and time and O(A tot ) space, and computes an ε-optimal policy and ε-optimal values with probability 1 -δ.Particularly excitingly, the algorithm in Theorem 1.1 runs in time nearly-linear in the number of samples whenever ε = O((1 -γ) -1/2 ) and therefore, provided querying the oracle costs Ω(1), has a near-optimal runtime for such ε! Prior to this work such a near-optimal, non-IPM, runtime (for non-trivially small γ) was only known for ε = Õ(1) ( [2] ). Similarly, Theorem 1.1 shows that there are model-free algorithms (which for our purposes we define as an Õ(A tot ) space algorithm) which are nearly-sample optimal whenever ε = O((1 -γ) -1/2 ). Previously this was only known for ε = Õ(1). As discussed in prior-work ([18, 17] ), 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 Õ(nnz(P ) + A tot (1 -γ) -2 ) time. It improves upon the prior, non-IPM, state-of-the-art which use Õ(nnz(P ) + A tot (1 -γ) -3 ) time ( [2] ). See Table 1 for a more complete comparison with prior work. Theorem 1.2. In the offline setting, there is an algorithm that uses Õ(nnz(P ) + A tot (1 -γ) -2 ) time, and computes an ε-optimal policy and ε-optimal values with probability 1 -δ.The method of Theorem 1.2 runs in nearly-linear time when (1 -γ) -1 ≤ (nnz(P )/A tot ) 1/2 , i.e., 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 γ) were only known for (1 -γ) -1 ≤ (nnz(P )/A tot ) 1/3 ([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 a Õ(nnz(P )) data-structure so 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 Õ(A tot )-space then so can the algorithm in Theorem 1.2.Table 1 : Running times to compute ε-optimal policies in the offline setting. In this table, E denotes an upper bound on the ergodicity of the MDP.Value Iteration [22, 11] Õ nnz(P )(1 -γ) -1 Õ(nnz(P ))Empirical QVI [16] Õ nnz(P )+ A tot (1 -γ) -3 ε -2 Õ(nnz(P )) Randomized Primal-Dual Method [23] Õ nnz(P ) + EA tot (1 -γ) -4 ε -2 Õ(A tot )High Precision Variance-Reduced Value Iteration [2] Õ nnz(P )+ A tot (1 -γ) -3 Õ(A tot ) Algorithm 4 This Paper Õ nnz(P ) + A tot (1 -γ) -2 Õ(A tot )Exact DMDP Algorithms. In our our comparison of offline DMDP algorithms in Table 1 , we ignored poly(log(ε -1 ))-factors. Consequently, we did not distinguish between algorithms which solve DMDPs to high accuracy, i.e., only depend on ε polylogarithmically, and those which solve it exactly, e.g., have no dependence on ε. There is a line of work on designing such exact methods and the current state-of-the-art is policy iteration, which can be implemented in Õ(|S| 2 A 2 tot (1 -γ) -1 ) time ( [13, 14] ) and a combinatorial interior point method that can be implemented in Õ(A 4 tot ) time ( [10] with no dependence on ε. Note that these methods obtain improved runtime dependence on ε at the cost of larger dependencies on |S| and A tot .Table 2 : Query complexities to compute ε-optimal policy in the sample setting. M erg denotes an upper bound on the MDP's ergodicity. Here, model-free refers to Õ(A tot ) space methods.Queriesε range Model-Free Phased Q-learning [15] Õ Atot (1-γ) 7 ε 2 (0, (1 -γ) -1 ] Yes Empirical QVI [16] Õ Atot (1-γ) 3 ε 2 (0, ((1 -γ) |S|) -1/2 ] No Sublinear Variance-Reduced Value Iteration [2] Õ Atot (1-γ) 4 ε 2 (0, (1 -γ) -1/2 ] Yes Sublinear Variance-Reduced Q Value Iteration [3] Õ Atot (1-γ) 3 ε 2 (0, 1] Yes Randomized Primal- Dual Method [23] Õ MergAtot (1-γ) 4 ε 2 (0, (1 -γ) -1Empirical MDP + Planning [17] ÕAtot (1-γ) 3 ε 2 (0, (1 -γ) -1/2 ] No Perturbed Empirical MDP, Conservative Planning [18] Õ Atot (1-γ) 3 ε 2 (0, (1 -γ) -1 ] No Algorithm 5 This Paper Õ Atot (1-γ) 3 ε 2 (0, (1 -γ) -1/2 ] YesComparison with IPM Approaches. In the offline setting, [2] showed how to reduce solving DMDPs to an ℓ 1 -regression problem in P ∈ R A×S . For ℓ 1 regression in a matrix A ∈ R n×d for n > d, [12] provides an algorithm that runs in Õ(d 0.5 (nnz(A) + d 2 ))-time, [24] provides an algorithm that runs in Õ(nd + d 2.5 ), and [25, 26, 27] yields an algorithm that runs in Õ(A ω tot ) time for the current value of the fast matrix multiplication exponent ω < 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 Õ A tot (1 -γ) -2 ε -3 queries to the generative model and time, one can construct a DMDP M such that an optimal policy in M is an ε-optimal for M. Consequently, provided polynomial accuracy in computing the policy suffices, applying the IPMs to M yields runtimes of Õ(nnz(P ) |S| + |S| 2.5 ) ( [12] ), Õ(A tot |S| + |S| 2.5 ) ( [24] ), and Õ(A ω tot ) time [25] . This combination of model-based and IPM-based 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 to S and A tot in the offline setting, or when, additionally, ε is sufficiently small relative to S and A tot in the sample setting.Here we provide an overview of our approach to proving Theorem 1.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 ε-optimal values and discuss computing ε-optimal policies at the end of this section.Value iteration. Our approach stems from classic value-iteration method ( [22, 11] ) for computing ε-optimal and its more modern Q-value and stochastic counterparts ( [16, 3, 29, 30, 31, 32] ). As the name suggests, value iteration proceeds in iterations t = 0, 1, . . . computing values, v (t) ∈ R S . Starting from initial v (0) ∈ R S , in iteration t ≥ 1, the value vector v (t) is computed as the result of applying the (Bellman) value operator T : R S → R S , i.e., v (t) ← T (v (t-1 ) where T (v)(s) := max a∈As (r a (s) + γp a (s) ⊤ v) for all s ∈ S and v ∈ R S . (1) It is well-known that the value operator is γ-contractive and therefore, 11, 22, 2] ). If we initialize v (0) = 0 then since ∥v * ∥ ∞ ≤ (1 -γ) -1 [22, 11] , we see that∥T (v) -v * ∥ ∞ ≤ γ ∥v -v * ∥ ∞ for all v ∈ R S ([∥v (t) -v * ∥ ∞ ≤ γ t ∥v (0) -v * ∥ ∞ ≤ γ t (1 -γ) -1 ≤ (1 -γ) -1 exp(-t(1 -γ)). Thus, v (t) are ε-optimal values for any t ≥ (1 -γ) -1 log(ε -1 (1 -γ) -1). This yields an Õ(nnz(P )(1 -γ) -1 ) time algorithm in the offline setting.Stochastic value iteration and variance reduction. To improve on the runtime of value iteration and apply it in the sample setting, a line of work implements stochastic variants of value iteration ( [16, 2, 3, 23, 17, 18] ). Those methods take approximate value iteration steps where the expected utilities p a (s) ⊤ v in (1) for each state-action pair are replaced by a stochastic estimate of the expected utilities. In particular, note that p a (s) ⊤ v = E i∼pa(s) v i , i.e., the expected value of v i where i is drawn from the distribution given by p a (s). This is compatible in the sample setting, as computing v i for i drawn from p a (s) yields an unbiased estimate of p a (s) ⊤ v with 1 query and O(1) time.State-of-the-art 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 p a (s) ⊤ v of each state-action pair (s, a) ∈ A. Broadly, given an arbitrary v (0) they first compute x ∈ R A that approximates P v (0) , i.e., x a (s) approximates [P v (0) ] (s,a) = p a (s) ⊤ v (0) for all (s, a) ∈ A. In the offline setting, x = P v (0) can be computed directly in O(nnz(P ))-time. In the sample setting, x ≈ P v (0) can be approximated to sufficient accuracy using multiple queries for each state-action pair. Then, in each iteration t ≥ 1 of the algorithm, fresh samples are taken to compute g (t) ≈ P (v (t-1) -v (0 )) and perform the following update: v (t) (s) ← max a∈As (r a (s) + γ(x a (s) + g a (s) (t) ) for all s ∈ S and v ∈ R S .(EQUATIONThis approach is advantageous because sampling errors for estimating P (v (t-1) -v (0) ) depend on the magnitude of v (t-1) -v (0) . After approximately computing x, the remaining task of computing g (t) ≈ P (v (t-1) -v (0 )) so that x+g (t) ≈ P v (t-1) may be easier than the task of directly estimating P v (t) (since v (t-1) -v (0) is smaller in magnitude than v (t) entrywise.) Due to similarities of this approach to variance-reduced optimization methods, e.g. ( [33, 34] ), this technique is called variance reduction [2] .The works [2, 3] , showed that if x is computed sufficiently accurately and v (0) are α-optimal values then applying (2) for t = Θ((1 -γ) -1 ) yields v (t) that is α/2-optimal in just Õ(A tot (1 -γ) -3 )time and samples! [2] leverages this technique to compute ε-optimal values in the offline setting in Õ(nnz(P )+ A tot (1 -γ) -3 ) time. [3] uses a similar approach to compute ε-optimal values in Õ(A tot [(1 -γ) -3 ε -2 + (1 -γ) -3) 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 ≈ P v (0) .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 x. Where we differ from prior work is in how we estimate the change in approximate utilities g (t) ≈ P (v (t-1) -v (0) ). Rather than directly sampling to estimate this difference we instead sample to estimate each individual P (v (t-1) -v (t) ) and maintain the sum. Concretely, for t ≥ 1, we compute ∆ (t) such thatEQUATIONso that these recursive approximations telescope. More precisely, setting g (0) = 0, for t ≥ 1, we setEQUATION)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 (t) ≈ P (v (t-1) -v (0) ) as a martingale and analzye it using Freedman'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 (t) , 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 (t) 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 ∥g (t+1) -P v (t) ∥ ∞ ≤ O((1 -γ)α). However, imagine that v * = α1, v (0) = 0, and in each iteration t one coordinate of v (t) -v (t-1) is Ω(α). If |S| ≈ (1 -γ) -1 and ∥p a (s)∥ ∞ = O(1/|S|) for some (s, a) ∈ A then the variance of each sample used to estimate p a (s) ⊤ (v (t) -v (t-1) ) = Ω(1/|S|) = Ω((1 -γ)). Applying Freedman's inequality, e.g., [36] , and taking b samples for each O((1 -γ) -1 ) iteration would yield, roughly, ∥g (t+1) -P (v (t) -v (0) )∥ ∞ = O((1-γ) -1 (1-γ)/ √ b) = O(1/ √ b). Consequently b = Ω((1 -γ) -2 )and Ω((1 -γ) -3 ) 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 a second algorithm technique, which we call truncation.Truncated-value 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 Ω(α). 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 v (t) changes too much! To motivate our algorithm, consider the following truncated variant of value iteration whereEQUATIONWhere median applies the median of the arguments entrywise. In other words, suppose we apply value iteration where we decrease or truncate the change from v (t-1) to v (t) so that it is no more than (1 -γ)α in absolute value in any coordinate. Then, provided that v (t) is α-optimal, we can show that it is still the case that ∥v(t) -v * ∥ ∞ ≤ γ∥v (t-1) -v * ∥ ∞ .In other words, the worst-case progress of value iteration is unaffected! This follows immediatly from the fact that∥v (t) -v * ∥ ∞ ≤ γ∥v (t-1) -v * ∥ ∞ invalue iteration and the following simple technical lemma.Lemma 1.3. For a, b, x ∈ R n and γ, α > 0, let c := median{a -(1 -γ)α1, b, a + (1 -γ)α1}, where median is applied entrywise. Then, if ∥b -x∥ ∞ ≤ γ ∥a -x∥ ∞ and ∥a -x∥ ∞ ≤ α, then ∥c -x∥ ∞ ≤ γ ∥a -x∥ ∞ .Applying truncated value iteration, we know that∥v (t) -v (t-1) ∥ ∞ ≤ (1 -γ)α.In other words, the worst-case change in a coordinate has decreased by a 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 (v (t) -v (0) ), reduces the total samples required to estimate this and halve the error from Õ((1 -γ) -3 ) to just Õ((1 -γ) -2 per state-action pair.Our method. Our algorithm applies stochastic truncated value iteration using sampling to estimate each g (t) ≈ P (v (t) -v (0) ) as described. Some minor additional modifications are needed, however, to obtain our results. Perhaps the most substantial is our use of the monotonicity technique, as in prior work ( [2, 3] ). That is, we modify our method so that each v (t) is always an underestimate of v * and the v (t) increase monotonically as t increases. Thus, we only truncate the increase in the v (t) (since they do not decrease, and the median operation in (5) reduces to a 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 ε-approximate policy as well as an ε-optimal value vector. We do this by tracking the actions associated with changed v (t) values, i.e., the argmax in (2) in a variable Choose i n ∈ S independently with P {i n = t} = p(t); x a (s) = Sample(u, p a (s), M, η);3 x = 1 M n∈[M ] u(i n ); 4 σ = 1 M n∈[M ] (u(i n )) 2 -x 2 ; 5 x ← x- √ 2ησ-4η3 return x π (t), which denotes the current estimated policy in iteration t 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 π (t) , v (t) satisfy the relation ) ]. Note that this ensures that the value ofv (t) ≤ T [v (tπ (t) (denoted v π (t) ) is at least v (t) because v (t) ≤ T [v (t) ] ≤ T 2 [v (t) ] ≤ • • • T ∞ [v (t) ] = v π (t)Thus, whenever v (t) is an ε-optimal value, π (t) is an at least ε-optimal policy.By computing initial expected utilities x = P v (0) exactly, we obtain our offline results. By carefully estimating x ≈ P v (0) as in [3] we obtain our sampling results. Finally, building off of the analysis of [37] for deterministic or highly-mixing MDPs, we also show our method obtains even faster convergence guarantees under additional non-worst-case assumptions on the MDP structure.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. 0 and 1 denote the all-ones and all-zeros vectors, [m] := {1, ...., m}, and ∆ n := {x ∈ R n : 0 ≤ x and ∥x∥ 1 = 1} is the simplex. For v ∈ R S , we use v i or v(i) for the i-th entry of vector v. For vectors v ∈ R A , we use v a (s) to denote the (s, a)-th entry of v, where (s, a) ∈ A. We use √ v, v 2 , |v| ∈ R n for the elementwise square root, square, and absolute value of v respectively and max{u, v} and median{u, v, w} for element-wise maximum and median respectively. For v, x ∈ R n , v ≤ x denotes that v(i) ≤ x(i) for each i ∈ [n] (analogously for <, ≥, >.) We call x ∈ R n an α-underestimate of y ∈ R n if y -α1 ≤ x ≤ y for α ≥ 0 (see the discussion of monotonicity in Section 1.2 for motivation).DMDP. As discussed, the objective in optimizing a DMDP is to find an ε-approximate policy π and values. For a policy π, we use T π (u) : R S → R S to denote the value operator associated with π, i.e., T π (u)(s) := r π(s) (s) + γp π(s) (s) ⊤ u for all value vectors u ∈ R S and s ∈ S. We let v π denote the unique value vector such that T π (v π ) = v π and define its variance as σ u π := P π (u π ) 2 -(P π u π ) 2 , where P π ∈ R S×S is the matrix such that P π s,s ′ = P s,π(s) (s ′ ). The optimal value vector v ⋆ ∈ R S of the optimal policy π ⋆ is the unique vector with T (v ⋆ ) = v ⋆ , and P ⋆ ∈ R S×S := P π ⋆ .Outline. Section 2 presents our offline setting results and Section 3 our sample setting results. Section A discusses specialized settings where we can obtain even faster convergence guarantees. Omitted proofs are deferred to Appendix B. 
offline algorithm: 
 In this section, we present our high-precision algorithm for finding an approximately optimal policy in the offline setting. We first define Sample (Algorithm 1), which approximately computes products between p ∈ ∆ S and a value vector u ∈ R S using samples from a generative model. The following lemma states some immediate estimation bounds on Sample using linearity and the fact that p ∈ ∆ S .Lemma 2.1. Let x = Sample(u, p, M, 0) for p ∈ ∆ n , M ∈ Z >0 , ε > 0, and u ∈ R S . Then,E [x] = p ⊤ u, |x| ≤ ∥u∥ ∞ , and Var [x] ≤ 1/M ∥u∥ 2 ∞ .We can naturally apply Sample to each state-action pair in M as in the subroutine ApxUtility (Algorithm 2). If x = ApxUtility(u, M, η), then x(s, a) is an estimate of the expected utility of taking action a ∈ A s from state s ∈ S (as discussed in Section 1.2). When η > 0, this estimate may potentially be shifted to increase the probability that x 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 x arise from applying Bernstein's inequality (Theorem B.2) to guarantee that x ≤ x -η with high probability.The following algorithm TVRVI (Algorithm 3) takes as input an initial value vector v (0) and policy π (0) such that v (0) is an α-underestimate of v ⋆ along with an approximate offset vector x, which is a β-underestimate of P v (0) . It runs runs L = Õ((1 -γ) -1 ) iterations of approximate value iteration, making one call to Sample(Algorithm 1) with a sample size of M = Õ((1 -γ) -1 ) in each iteration. The algorithm outputs v L which we show is an α/2-underestimate of v ⋆ (Corollary 2.5).TVRVI (Algorithm 3) is similar to variance reduced value iteration [2] , in that each iteration, we draw M samples and use Sample to maintain underestimates of p a (s) ⊤ (v (ℓ) -v (ℓ-1) ) 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 transitions p a (s) ⊤ (w (t) -w (0) ) for a general sequence of ℓ ∞ -bounded vectors {w (i) } T i=1 . The analysis leverages Freedman's Inequality [35] as stated in [36] and restated in Theorem B.1.Lemma 2.2. Let T ∈ Z >0 and w (0) , w (1) , ...,w (T ) ∈ R S such that w (i) -w (i-1) ∞ ≤ τ for all i ∈ [T ]. Then, for any p ∈ ∆ S , δ ∈ (0, 1), and M ≥ 2 8 T log(2/δ) with probability 1 -δ, p ⊤ (w (t) -w (0) ) -i∈[t] j∈[M ] Sample(w (i) -w (i-1) , p, 1, 0) • 1/M ≤ τ /8 for all t ∈ [T ].Algorithm 3: TVRVI(v (0) , π (0) , x, α, δ)Input: Initial values v (0) ∈ R S , which is an α-underestimate of v ⋆ . Input: Initial policy π (0) such that v (0) ≤ T π (0) (v (0) ). Input: Accuracy α ∈ [0, (1 -γ) -1 ] and failure probability δ ∈ (0, 1).Input: Offsets x ∈ R A ;// entrywise underestimate of P v (0) 1 Initialize g (1) ∈ R A and ĝ(1) ∈ R A to 0; 1) and π (ℓ) = π (ℓ-1) ; 6 for each state i ∈ S do // Compute truncated value update (and associated action)2 L = ⌈log(8)(1 -γ) -1 ⌉ and M = ⌈L • 2 8 log(2A tot /δ)⌉ ; 3 for each iteration ℓ ∈ [L] do 4 Q = r + γ(x + ĝ(ℓ) ); 5 v (ℓ) = v (ℓ-7 ṽ(ℓ) (i) = min{max a∈Ai Qi,a , v (ℓ-1) + (1 -γ)α} and π(ℓ) i = argmax a∈Ai Qi,a ; // Update value and policy if it improves 8 if ṽ(ℓ) (i) ≥ v (ℓ) (i) then v (ℓ) (i) = ṽ(ℓ) (i) and π (ℓ) i = π(ℓ) i ;// Update for maintaining estimates of P (v (l) -v 0 ). 9 1) , M, 0) and g (ℓ+1) = g (ℓ) + ∆ (ℓ) ; // Shift estimates so that ĝ(ℓ+1) always underestimates p a (s∆ (ℓ) = ApxUtility(v (ℓ) -v (ℓ-) ⊤ v (ℓ) . 10 ĝ(ℓ+1) = g (ℓ+1) -(1-γ)α 8 1; 11 return (v (L) , π (L) )While it is unclear how to significantly improve the constant of 2 8 = 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 we can maintain additive O((1 -γ)α)-underestimates of the transitions p a (s) ⊤ (v (ℓ) -v (0) ) using only Õ(L) samples (as opposed to the Õ(L 2 ) samples required in [2] ) per state-action pair.Corollary 2.3. In TVRVI (Algorithm 3), with probability 1 -δ, in Lines 9, 10 and 2, for all s ∈ S, a ∈ A s , and ℓ ∈ [L], we have g(ℓ) a (s) -p a (s) ⊤ (v (ℓ-1) -v (0) ) ≤ (1 -γ)α/8 and therefore ĝ(ℓ) a is a (1 -γ)α/4-underestimate of p a (s) ⊤ (v (ℓ-1) -v (0) ).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 v (0) .Lemma 2.4. Suppose that for some β ∈ R A ≥0 , P v (0) -β ≤ x ≤ P v (0) and let β π ⋆ ∈ R S be defined as β π ⋆ (s) := β π ⋆ (s) (s) for each s ∈ S. Then, with probability 1 -δ, at the end of every iteration ℓ ∈ [L] (Line 3) in TVRVI(v (0) , π (0) , x, α, δ), the following hold for ξ := γ((1 -γ)α/41 + β π ⋆ ):EQUATIONEQUATIONCorollary 2.5. Suppose that for some α ≥ 0 andβ ∈ R A ≥0 , P v (0) -β ≤ x ≤ P v (0) ; v (0) is an α-underestimate of v ⋆ ; and v (0) ≤ T π (0) (v (0) ). Let β π ⋆ ∈ R S be defined as β π ⋆ (s) := β π ⋆ (s) (s) for each s ∈ S. Let (v (L) , π (L) ) = TVRVI(v (0) , π (0) , α, δ), and L, M be as in Line 2. Define ξ := γ ((1 -γ)α/4 • 1 + β π ⋆ ). Then, with probability 1 -δ, 0 ≤ v ⋆ -v (L) ≤ γ L α • 1 + (I -γP ⋆ ) -1 ξ, and v (L) ≤ T π (L) (v (L)). In particular, if β = 0, then for L > log(8)(1 -γ) -1 we can reduce the error in v (0) by half: Input: Target precision ε and failure probability δ ∈ (0, 1)0 ≤ v ⋆ -v (L) ≤ (v ⋆ -v (0) )/2.1 K = ⌈log 2 (ε -1 (1 -γ) -1 )⌉, v 0 = 0, π 0 is an arbitrary policy, and α 0 (1 -γ) -1 ; 2 for each iteration k ∈ [K] do 3 α k = α k-1 /2 = 2 -k (1 -γ) -1 ; 4 x = P v k-1 ; 5 (v k , π k ) = TVRVI(v k-1 , π k-1 , x, α k-1 , 0, δ/K); 6 return (v K , π K ) 
sample setting algorithm: 
 In this section, we show how to extend the analysis in the previous section in the sample setting, where we do not have explicit access to P . We follow a similar framework as in [3] to show that we can instead estimate the offsets x in OfflineTVRVI by taking additional samples from the generative model. The pseudocode is shown in SampleTVRVI(Algorithm 5.) To analyze the algorithm, we first bound the error incurred when approximating the exact offsets x in Line 4 of OfflineTVRVI (Algorithm 4) with approximate offsets x ≈ P v k-1 computed by sampling from the generative model. The proof leverages Hoeffding's and Bernstein's inequality, and follows a similar structure as the proof of Lemma 5.1 of [3] .Input: Target precision ε and failure probability δ ∈ (0, 1) 1 K = ⌈log 2 (ε -1 (1 -γ) -1 )⌉ ; 2 v 0 = 0, π 0 is an arbitrary policy, andα 0 = (1 -γ) -1 ; 3 for each iteration k ∈ [K] do 4 α k = α k-1 /2 = 2 -k (1 -γ) -1 ; 5 N = 6500(1 -γ) -3 log(8A tot Kδ -1 ); 6 N k-1 = N max((1 -γ), α -2 k-1 ) ; 7 η k-1 = N -1 k-1 log(8A tot Kδ -1 ) ; 8 x k = ApxUtility(v k-1 , N k-1 , η k-1 ); 9 (v k , π k ) = TVRVI(v k-1 , π k-1 , x k , α k-1 , δ/K) ; 10 return (v K , π K ) Lemma 3.1. Consider u ∈ R S . Let x = ApxUtility(u, m • A tot , η), m ≥ log(1/2δ -1), and η = (mA tot ) -1 log(1/2δ -1 ). Then, with probability 1 -δ,P u -2 2ησ v ⋆ + 2 2η ∥u -v ⋆ ∥ ∞ + 18η 3/4 ∥u∥ ∞ ≤ x ≤ P u.Finally, to obtain our main result Theorem 1.1, we utilize worst-case bounds on σ v ⋆ 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 to technical reasons, from applying Bernstein's inequality, Hoeffding's inequality, union bound over all K outer loop iterations, and bounds on σ v ⋆ 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.1 shows that in the expression N = 6500(1 -γ) -3 log(8A tot Kδ -1 ) there is a 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 |S| , A tot ). Although not the primary focus of our work, such trade-offs might be of practical importance.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 
conclusion: 
 We provided faster and more space-efficient algorithms for solving DMDPs. We showed how to apply truncation and recursive variance reduction to improve upon prior variance-reduced value iterations methods. Ultimately, these techniques reduced an additive Õ((1 -γ) -3 ) term in the time and sample complexity of prior variance-reduced value iteration methods to Õ((1 -γ) -2 ).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, it may be of 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 -γ) -2 ) term in our time and sample complexities can be further improved to Õ((1 -γ) -1 ) is a natural open problem; an affirmative answer to this question would yield the first near-optimal running times for solving a DMDP with a 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. Now, we apply Corollary 2.5 withβ = 2 2η k-1 σ v ⋆ + 2 2η k-1 α k-1 + 18η 3/4 k-1 ∥v k-1 ∥ ∞ 1.Consequently, we have0 ≤ v ⋆ -v k ≤ γ L α k-1 • 1 + (I -γP ⋆ ) -1 ξ k-1 ≤ α k-1 8 1 + (I -γP ⋆ ) -1 ξ k-1 , for ξ k-1 ≤ (1-γ)α k-1 4 1 + 2 √ 2η k-1 σ v ⋆ + 2 √ 2η k-1 α k-1 + 18η 3/4 k-1 ∥v k-1 ∥ ∞ 1, and v k ≤ T π k (v k ). Note that (I -γP ⋆ ) -1 1 ≤ 1 1-γ 1.Hence, if k < ⌈log 2 (1 -γ) -5 /V 3 ⌉, we use Lemma B.4 along with the facts that (I -γP ⋆ ) -1 1 = 1/(1 -γ)1 and the choice of η k-1 to obtain (identical to the proof of Theorem 1.1):(I -γP ⋆ ) -1 ξ k-1 ≤   α k-1 4 + 2 6 η k-1 (1 -γ) 3 + 2 2(1 -γ) 3 min((1 -γ) -1 , α 2 k-1 ) 6500(1 -γ) 2 α k-1   1 + 18 ((1 -γ) 3 min((1 -γ) -1 , α 2 k-1 ) 6500(1 -γ) 8/3 3/4 1 ≤ [α k-1 /4 + 2 6/6500 • α k-1 + 2 2/6500(1 -γ) 1/2 min((1 -γ) -1/2 , α k-1 )α k-1 + 18 • (10 -3 )(1 -γ) 1/4 min((1 -γ) -3/4 , α 3/2 k-1 )]1 ≤ [α k-1 /4 + 4 6/6500 • α k-1 + 18 • (10 -3 )α k-1 ]1 ≤ 3 8 α k-1 1. If instead k ≥ ⌈log 2 (1 -γ) -5 /V 3 ⌉, then α k ≤ 1 128 (1 -γ) 4 V 3 , and η k-1 = α 2 k-1 /(1024 • V 2 ). Consequently, (I -γP ⋆ ) -1 ξ k-1 ≤ 2 2η k-1 (I -γP ⋆ ) -1 √ σ v ⋆ + α k-1 4 + 2 2η k-1 (I -γP ⋆ ) -1 α k-1 + 18η 3/4 k-1 (I -γP ⋆ ) -1 ∥v k-1 ∥ ∞ 1 ≤ α k-1 4 1 + 2 √ 2α k-1 4(1 -γ) √ 1024V V 1 + 18 (1 -γ) 2 α 2 k-1 1024 • V 2 3/4 1 ≤ α k-1 8 + α k-1 4 1 ≤ 3 8 α k-1 1.Therefore in either case,v ⋆ -v k-1 ≤ α k-1 2 1 = α k 1.Moreover, we can use thatv k ≤ T π k (v k ) to see that v k ≤ T π k (v k ) ≤ T 2 π k (v k ) ≤ • • • ≤ T ∞ π k (v k ) = v π k ≤ v ⋆ . This completes the inductive step. Consequently, taking k = K = ⌈log 2 (ε -1 (1 -γ) -1 )⌉ iterations of the outer loop, with probability 1 -δ, we have that 0 ≤ v ⋆ -v π K ≤ v ⋆ -v K ≤ α K ≤ ε and v k ≤ T π k (v k ) ≤ T 2 π k (v k ) ≤ • • • ≤ T ∞ π k (v k ) = v π k ≤ v ⋆ , that is, v k is an ε-optimal value and π K is an ε-optimal policy.The total number of samples and time required is Õ A tot ε -2 V 2 + (1 -γ) -2 . For the space complexity, note that the algorithm can be implemented to maintain only O(1) vectors in R Atot . ■ Theorem A.1 yields improved complexities for solving MDPs when (I -γP ⋆ ) -1 √ σ v ⋆ ∞ is nontrivially bounded. Following [37] we mention two particular such settings where we can apply Theorem A.1 to obtain better problem-dependent sample and runtime bounds than Theorem 1.1.Deterministic MDPs For a deterministic MDP, each action deterministically transitions to a single state. That is, for all (s, a) ∈ A, p a (s) = 1 s ′ (the indicator vector of s ′ ∈ S) for some s ′ ∈ S. In this case, σ v ⋆ = 0. Consequently, if the MDP is deterministic, the algorithm converges with just Õ((1 -γ) 3 ) samples to the generative model and time. We note that in this setting of deterministic MDPs, there may be alternative approaches to obtain the same or better runtime and sample complexity.Small range. Define the range of optimal values for a MDP as rng(v * )def = max s∈S v * s -min s∈S v * s . Note that σ v ⋆ ≤ rng(v * ) 2 1. So, (I -γP ⋆ ) -1 √ σ v ⋆ ∞ ≤ (1 -γ) -1 rng(v * ). Therefore, by Theorem A.1, given an approximate upper bound of (I -γP ⋆ ) -1 √ σ v ⋆ ∞ our algorithm is implementable with Õ(A tot (ε -2 (1 -γ) -2 rng(v ⋆ ) 2 + (1 -γ) -2)) samples and time.Highly mixing domains. [37] showed that a 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 Õ A tot ε -2 (1 -γ) -2 + (1 -γ) -2= median{a -(1 -γ)α1, b, a + (1 -γ)α1}, where median is applied entrywise. Then, if ∥b -x∥ ∞ ≤ γ ∥a -x∥ ∞ and ∥a -x∥ ∞ ≤ α, then ∥c -x∥ ∞ ≤ γ ∥a -x∥ ∞ .Proof. Consider the i-th entry (c -x) i . There are three cases. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] Justification: The paper focuses on theoretical results and mathematical analysis and does not include experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 a 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, or as supplemental material. 
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 on 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. 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.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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 on foundational theory for solving MDPs and is not directly tied to any specific societal impacts (positive or negative). We do not expect any direct, immediate, substantial societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 a 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 to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 to 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 a 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are 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 creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: i -(1 -γ)α ≤ b i ≤ a i + (1 -γ)α. Then, |c i -x i | = |b i -x i | ≤ γ ∥a -x∥ ∞ Second, suppose b i ≤ a i -(1 -γ)α ≤ a i + (1 -γ)α. Then, c i -x i ≥ b i -x i ≥ -∥b -x∥ ∞ ≥ -γ ∥a -x∥ ∞ . Meanwhile, c i -x i = a i -(1 -γ)α -x i ≤ ∥a -x∥ ∞ -(1 -γ)α. Now, because ∥a -x∥ ∞ ≤ α, we have that (1 -γ) ∥a -x∥ ∞ ≤ (1 -γ)α. So, ∥a -x∥ ∞ -(1 -γ)α ≤ γ ∥a -x∥ ∞ . Lastly, suppose a i -(1 -γ)α ≤ a i + (1 -γ)α ≤ b i . Then, c i -x i ≤ b i -x i ≤ ∥b -x∥ ∞ ≤ γ ∥a -x∥ ∞ . Meanwhile, c i -x i = a i + (1 -γ)α -x i ≥ -∥a -x∥ ∞ + (1 -γ)α. Now, because ∥a -x∥ ∞ ≤ α, we have that (1 -γ) ∥a -x∥ ∞ ≤ (1 -γ)α. So, -∥a -x∥ ∞ + (1 -γ)α ≥ γ ∥a -x∥ ∞ . ■ B.2 Omitted proofs from Section 2 First, we prove Lemma 2.1.Lemma 2.1. Let x = Sample(u, p, M, 0) for p ∈ ∆ n , M ∈ Z >0 , ε > 0, and u ∈ R S . Then,E [x] = p ⊤ u, |x| ≤ ∥u∥ ∞ , and Var [x] ≤ 1/M ∥u∥ 2 ∞ .Proof. The first statement follows from linearity of expectation and the second from definitions. The third statement follows from independence and thatVar [v im ] = i∈S p i v 2 i -(p ⊤ v) 2 ≤ i∈S p i ∥v∥ 2 ∞ = ∥v∥ 2 ∞ for any m ∈ [M ] .■ Next, we state Freedman's inequality [35] , which we use to prove the following Lemma 2.2.Theorem B.1 (Freedman's Inequality, restated from [36] ). Consider a real-valued martingale{Y k : k = 0, 1, . . .} with difference sequence {X k : k = 1, 2, . . .} given by X k = Y k -Y k-1 .Assume that X k ≤ R almost surely for k = 1, 2, . . .. Define the predictable quadratic variation process of the martingale:W k := k j=1 E X 2 j |X 1 , ..., X j-1 .Then, for all t ≥ 0 and σ 2 > 0,P ∃k ≥ 0 : Y k ≥ t and W k ≤ σ 2 ≤ exp -t 2 /(2(σ 2 + Rt/3))Lemma 2.2. Let T ∈ Z >0 and w (0) , w (1) , ..., w (T ) ∈ R S such that w (i) -w (i-1) ∞ ≤ τ for all i ∈ [T ]. Then, for any p ∈ ∆ S , δ ∈ (0, 1), and M ≥ 2 8 T log(2/δ) with probability 1 -δ,p ⊤ (w (t) -w (0) ) -i∈[t] j∈[M ] Sample(w (i) -w (i-1) , p, 1, 0) • 1/M ≤ τ /8 for all t ∈ [T ]. Proof. For each i ∈ [T ], j ∈ [M ], let X i,j := Sample(w (i) -w (i-1) , p, 1, 0) -p ⊤ (w (i) -w (i-1) ) /M. Since p ∈ ∆ S , Lemma 2.1 yields that |X i,j | ≤ 2τ M . Next, define Y t,k := i∈[t-1] j∈[M ] X i,j + k j=1 X t,j .The predictable quadratic variation process (as defined in Theorem B.1) is given byW t,k = i∈[t-1] j∈[M ] E X 2 i,j |X 1,1:M , ..., X i-1,1:M , X i,1:j-1 + j∈[k] E X 2 t,j |X 1,1:M , ..., X t-1,1:M , X t,1:j-1 = i∈[t-1] j∈[M ] Var Sample(w (i) -w (i-1) , p, 1, 0) M + j∈[k] Var Sample(w (t) -w (t-1) , p, 1, 0) M ≤ i∈[t] j∈[M ] τ 2 M 2 = T τ 2 Mwhere, in the last line we used Lemma 2.1 to bound the variance. Now, by telescoping,Y t,M =   i∈[t] j∈[M ] Sample(w (i) -w (i-1) , p, 1, 0) M   -p ⊤ (w (t) -w (0) ) for all t ∈ [T ]Consequently, applying Theorem B.1 twice (once to Y t,M and once to -Y t,M yieldsP ∃t ∈ [T ] : |Y t,M | ≥ τ 8 ≤ 2 exp - (τ /8) 2 2( T τ 2 M + 2τ M • τ 8 • 1 3 = 2 exp -M 2 7 T + 1 12 ≤ δ .As an immediate corollary of Lemma 2.2, we obtain Corollary 2.3.Corollary 2.3. In TVRVI (Algorithm 3), with probability 1 -δ, in Lines 9, 10 and 2, for all s ∈ S, a ∈ A s , and ℓ ∈ [L], we have g(ℓ) a (s) -p a (s) ⊤ (v (ℓ-1) -v (0) ) ≤ (1 -γ)α/8 and therefore ĝ(ℓ) a is a (1 -γ)α/4-underestimate of p a (s) ⊤ (v (ℓ-1) -v (0) ).Proof. Consider some s ∈ S and a ∈ A s . Note that g(ℓ) a (s) is equal in distribution to   i∈[ℓ-1] j∈[M ] Sample(v (i) -v (i-1) , p a (s), 1, 0) M   -p a (s) ⊤ (v (ℓ-1) -v (0) ).Then, by Lemma 2.2 and union bound, whenever M ≥ L • 2 8 log(2A tot /δ) we have that withEQUATIONa (s) -p a (s) ⊤ (v (ℓ-1) -v (0) ) ≤ 1-γ 8 α and conditioning on this event, we have p a (s)⊤ (v (ℓ-1) -v (0) ) -1-γ 4 α ≤ ĝ(ℓ) a (s) ≤ p a (s) ⊤ (v (ℓ-1) -v (0)) due to the shift in Line 10. ■Conditioning on the event that the implication of Corollary 2.3 holds, we can prove the following Lemma 2.4Lemma 2.4. Suppose that for some β ∈ R A ≥0 , P v (0) -β ≤ x ≤ P v (0) and let β π ⋆ ∈ R S be defined as β π ⋆ (s) := β π ⋆ (s) (s) for each s ∈ S. Then, with probability 1 -δ, at the end of every iteration ℓ ∈ [L] (Line 3) in TVRVI(v (0) , π (0) , x, α, δ), the following hold for ξ := γ((1 -γ)α/41 + β π ⋆ ):EQUATIONEQUATIONProof. In the remainder of this proof, condition on the event that the implications of Corollary 2.3 hold (as they occur with probability 1 -δ). By Line 7 and 8 of Algorithm 3, for all ℓ ∈ [L],v (ℓ-1) ≤ v (ℓ) ≤ v (ℓ-1) + (1 -γ)α1.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) ≤ T π (0) (v (0) ) holds by assumption. For the ℓ-th iteration, there are two cases. If v (ℓ) (s) > v (ℓ-1) (s) for s ∈ S thenEQUATION≤ T π (ℓ) (v (ℓ-1) ) ≤ T π (ℓ) (v (ℓ) ).Otherwise, if v (ℓ) (s) = v (ℓ-1) (s), then by the inductive hypothesis,v (ℓ) (s) = v (ℓ-1) (s) ≤ T π (ℓ-1) (v (ℓ-1) )(s) = T π (ℓ) (v (ℓ) )(s) .This completes the proof of ( 6).Next, we prove (7) . For the lower bound, by induction and (10), we have that for each s ∈ S ṽ(ℓ) (s) ≤ maxa∈As {r a (s) + γp a (s) ⊤ v (ℓ-1) (s)} ≤ max a∈As {r a (s) + γp a (s) ⊤ v ⋆ (s)} = v ⋆ , so min(ṽ (ℓ) , v (ℓ-1) + (1 -γ)α) ≤ v ⋆ .Next, we prove the upper bound of (7) . For each (s, a) ∈ A and ℓ ∈ [L], letξ (ℓ) a (s) := p a (s) ⊤ v (ℓ-1) -(x a (s) + ĝ(ℓ) a )(s)), and observe thatξ (ℓ) a (s) = [p a (s) ⊤ v (0) -x a (s)] + [p a (s) ⊤ (v (ℓ-1) -v (0) ) -ĝ(ℓ) a )(s))] ≤ β a (s) + (1 -γ)α 4 .Note that for any s ∈ S,(v ⋆ -ṽ(ℓ) )(s) = max a∈Ai [r a (s) + γp a (s) ⊤ v ⋆ (s)] -max a∈As [r a (s) + γ(x a (s) + ĝ(ℓ) a )(s))] ≤ [r π ⋆ (s) (s) + γ (P ⋆ v ⋆ ) (s)] -max a∈As [r a (s) + γp a (s) ⊤ v (ℓ-1) -γξ (ℓ) a (s)] ≤ [r π ⋆ (s) (s) + γ (P ⋆ v ⋆ ) (s)] -[r π ⋆ (s) (s) + γ(P ⋆ v (ℓ-1) )(s) -γξ (ℓ) π ⋆ (s) (s)] ≤ γ P ⋆ (v ⋆ -v (ℓ-1) ) (s) + ξ(s),Consequently, for all s ∈ S,(v ⋆ -ṽ(ℓ) )(s) ≤ γP ⋆ (v ⋆ -v (ℓ-1) )(s) + ξ(s). Consider two cases for v (ℓ) (s). First, if v (ℓ) (s) = ṽ(ℓ) (s) for some s ∈ S then v ⋆ -v (ℓ) (s) ≤ γ P ⋆ v ⋆ -v (ℓ-1) (s) + ξ(s) holds immediately. If not, v (ℓ) (s) = v (ℓ-1) (s) + (1 -γ)α ≤ ṽ(ℓ) (s) and (6) guarantees that v ⋆ -v (ℓ-1) ∞ ≤ v ⋆ -v (0) ∞ ≤ α, which ensures that (1 -γ)(v ⋆ -v (ℓ-1) )(s) ≤ (1 -γ)α and yields the results as, v ⋆ -v (ℓ) (s) = v ⋆ -v (ℓ-1) (s) -(1 -γ)α ≤ γ v ⋆ -v (ℓ-1) (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.Corollary 2.5. Suppose that for some α ≥ 0 andβ ∈ R A ≥0 , P v (0) -β ≤ x ≤ P v (0) ; v (0) is an α-underestimate of v ⋆ ; and v (0) ≤ T π (0) (v (0) ). Let β π ⋆ ∈ R S be defined as β π ⋆ (s) := β π ⋆ (s) (s)for each s ∈ S. Let (v (L) , π (L) ) = TVRVI(v (0) , π (0) , α, δ), and L, M be as in Line 2. Define ξ := γ ((1 -γ)α/4 • 1 + β π ⋆ ). Then, with probability 1 -δ, 0 ≤ v ⋆ -v (L) ≤ γ L α • 1 + (I -γP ⋆ ) -1 ξ, and v (L) ≤ T π (L) (v (L)). In particular, if β = 0, then for L > log(8)(1 -γ) -1 we can reduce the error in v (0) by half:0 ≤ v ⋆ -v (L) ≤ (v ⋆ -v (0) )/2.Additionally, TVRVI is implementable with Õ(A tot M L) sample queries to the generative model and time and O(A tot ) space.Proof. Condition on the event that the implication of Lemma 2.4 holds. First, we observe that ) follows by monotonicity (Equation (6) of Lemma 2.4). Next, we show that0 ≤ v ⋆ -v π (L) ≤ v ⋆ -v (Lv ⋆ -v (L) ≤ γ L α • 1 + (I -γP ⋆ ) -1 ξ,by induction. We will show that for all i ∈ S,v ⋆ -v (ℓ) ≤ γ ℓ α1 + ℓ k=0 γ k P ⋆k ξ .In the base case when ℓ = 0, this is trivially true, as v ⋆ -v (ℓ) ≤ α1 by assumption. Assume that the statement is true up to v (ℓ-1) . Now, by Lemma 2.4, we have two cases for 1) ](i). Then, note that P ⋆ and ξ are entrywise non-negative, so [γ ℓ P ⋆ℓ ξ](i) ≥ 0. By inductive hypothesis, and the fact that γ ∈ (0, 1) we have[v ⋆ -v (ℓ) ](i). First, suppose that [v ⋆ -v (ℓ) ](i) ≤ γ[v ⋆ -v (ℓ-[v ⋆ -v (ℓ) ](i) ≤ γ γ (ℓ-1) α + ℓ-1 k=0 γ k P ⋆k ξ (i) = γ ℓ α + γ ℓ-1 k=0 γ k P ⋆k ξ (i) ≤ γ ℓ α + ℓ-1 k=0 γ k P ⋆k ξ (i) ≤ γ ℓ α + ℓ k=0 γ k P ⋆k ξ (i) = γ ℓ α1 + ℓ k=0 γ k P ⋆k ξ (i). Second, suppose that instead, [v ⋆ -v (ℓ) ](i) ≤ γP ⋆ v ⋆ -v (ℓ-1) (i) + ξ(i). By monotonicity (equation (6) of Lemma 2.4) we know that v ⋆ -v (ℓ-1) ≥ 0. Moreover, P ⋆ is non-negative, and consequently, we can use the inductive hypothesis as follows:v ⋆ -v (ℓ-1) ≤ γ ℓ-1 α1 + ℓ-1 k=0 γ k P ⋆k ξ , hence P ⋆ v ⋆ -v (ℓ-1) ≤ P ⋆ γ ℓ-1 α1 + ℓ-1 k=0 γ k P ⋆k ξ .We can rearrange terms to obtain the following bound:[v ⋆ -v (ℓ) ](i) ≤ γP ⋆ γ (ℓ-1) α1 + ℓ-1 k=0 γ k P ⋆k ξ (i) + ξ(i) = γ ℓ α[P ⋆ 1](i) + ℓ-1 k=0 γ k+1 P ⋆k+1 ξ (i) + ξ(i) ≤ γ ℓ α1 + ℓ k=0 γ k P ⋆k ξ (i).Consequently, by induction, the bound holds. When L > log(8)(1 -γ) -1 , γ L ≤ 1/8 and we havev ⋆ -v k ≤ γ L α • 1 + (I -γP ⋆ ) -1 γ(1 -γ) 4 α1 ≤ γ L α + γ α 4 ≤ α 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 ĝ(ℓ) , g (ℓ) ∈ R Atot , v (ℓ) ∈ R S , π (L) , and at most M A tot samples in invoking Sample.NeurIPS Paper Checklist Justification: Yes, we discuss regimes where our result is optimal and where it 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 no 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.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 NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_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$.
strength_weakness: strength_weakness: 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.
questions: questions: (0) Are these theoretical results the state-of-art even if $\epsilon$ is small?

(1) Could you clarify why it's okay to ignore polylogarithmic factors involving  $\epsilon$ and $\delta$? 
 
(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),
    
 (3)  In line $5$ of Algorithm $1$, could you explain the intuition of the offset parameter and subtraction with different powers?
   
(4) Could these analyses be extended to the settings where the reward is unknown or average reward MDP?
  
 (5) In line 27, why do we need condition $|\mathcal{A}| \ge |\mathcal{S}| $?

            
 (6) In line 98, does `nearly-linear' indicate quadratic?
              
 (7) In line 100, why it is $\epsilon$? If $\epsilon = O(1-\gamma)^{-1/2}$, isn't it $\epsilon^4$?

(8) References [1] and [2] seem the same.

(9) References [17] and [21] seem the same.

(10) In line 104, what is the definition of $w$?

(11) In line 191, $v^{(t-1)}$ should be changed to $v^{(t)}$ 

(12) In line 193, typo $v^{(0)}$

(13) In line 276, typo $v^{(0)}$




 (14) In line 282, need spacing.
limitations: limitations: Yes, the authors addressed limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: See weaknesses.
limitations: limitations: None.
paper_summary: paper_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.
strength_weakness: strength_weakness: Please see the next sections for my comments.


A 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.
questions: 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. 

2. 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 4) The paper is sometimes difficult to follow.
5) 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.
questions: 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: limitations: No limitation.

Comments: title: Response to the authors
Thanks for your response!
Regarding constants
Response to the authors
comment: Thank you for addressing my questions in your rebuttal. I will maintain my score.
Thanks for your reply! We will be sure to tighten constants where possible, and we will also be sure to include a discussion of the constants in the camera-ready version of our paper. Thank you for the suggestion!
Thanks for the reply!
It would be great if the authors could include a discussion about the constants in the camera-ready version. This tradeoff between constant factors and polylog factors in $\epsilon,\delta$, etc is certainly interesting...
Thank you for the detailed response. That clarifies all my concerns. I will maintain my score.