Truncated Variance Reduced Value Iteration

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.

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. 4) The upper bound in terms of number of queries is state of the art for model free algoriths, for large $\epsilon$. 2) Maths are well written and proofs seem correct for me. 3) 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. 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

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 ?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

No limitation.

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.

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

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?

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes

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.

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. 2) The analysis differs from existing works in the way the utilities are computed - this work uses a recursive variance reduction method. 3) 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.

Questions

See weaknesses.

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

None.

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$.

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.

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.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, the authors addressed limitations.

Response to the authors

Thank you for the detailed response. That clarifies all my concerns. I will maintain my score.

Regarding constants

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

Response to the authors

Thank you for addressing my questions in your rebuttal. I will maintain my score.