Truncated Variance Reduced Value Iteration

Thanks for your comments! We addressed your comment about experiments in the overall response and discuss individual questions here.

Comment 1: The paper is sometimes hard to follow.

We 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!

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?

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

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

Thank you for your feedack! We’ll carefully address the misspellings/typos ahead of the camera-ready.

Q1: Can the authors explain how they claim that model-based methods use $\Omega(A_{tot} (1-\gamma)^{-3} \epsilon^{-2})$?

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

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?

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

Recall, 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):

• Estimate $Pv^{(0)}$ using samples
• For each of $t = 1, 2, 3, ... , T = \tilde{\Theta}(1/(1-\gamma))$ iterations
  • Maintain estimates of $P(v^{(t-1)} - v^{(0)})$
  • Run one step of approximate variance-reduced value iteration using these estimates

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

Second, 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:

• What [3] does:
  • In [3], Step (2b) is maintained by just estimating $P(v^{(t-1)} - v^{(0)})$ with new samples in each iteration.
• How we maintain Step (2b) with fewer samples:
  • 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)})$.
  • 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)})$.
  • 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.

So, in summary, two algorithmic changes and one analytic change enable our improvement-- truncation is just one piece.

Thank you for your feedback!

Comment/Question: Can the constant of $2^8$ in Lemma 2.2 or the constant of $10^4$ be tightened?

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

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

As 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!

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 feedback! We responded about experiments above and discuss your questions here.

Applying stronger inequalities-- Hoeffding [2], Bernstein [3], Freedman [this paper] has led to improvements.

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

I’m uncertain about ignoring polylogarithmic factors.

Please see Q1 below.

The range of $\epsilon$ is not the best in the tables.

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

Q0: Are the theoretical results state-of-the-art even for small $\epsilon$?

Yes, 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].

Q1: Why can we ignore polylogarithmic factors in $\epsilon, \delta$?

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

Q2: Do the methods lead to practical benefits aside from theoretical benefit (e.g., AGD vs. ADAM)?

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

Q3: Why the offset parameter in Alg. 2?

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

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

Q4: Do the methods extend to average-reward or unknown rewards?

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

Q5: Why should $|\mathcal{A}| \geq \mathcal{S}|$?

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

Q6: What is nearly-linear in Line 98?

Here, 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})$.

Q7: Can you explain Line 100?

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

Q10: What is w in Line 104?

It 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!

Q8-9, Q11-14: Typos

Thanks for pointing out the duplicate references and typos. We’ll correct in the camera ready!