Research map / Learning theory and algorithms / Sample complexity
Truncated Variance Reduced Value Iteration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives truncated variance-reduced value iteration with recursive variance reduction, achieving improved sample (Õ(A_tot[(1-γ)^-3 ε^-2 + (1-γ)^-2])) and offline (Õ(nnz(P) + A_tot(1-γ)^-2)) complexities with O(A_tot) space.
Problem
Computing ε-optimal policies and values for discounted MDPs with lower time/sample cost and low memory, closing the gap between model-free and model-based methods.
Approach
Truncate each value-iteration update so that per-iteration coordinate change is at most (1-γ)α, which shrinks the variance-bound in Freedman's inequality for recursive variance reduction of the transition-utility estimates, reducing the per-state-action sample cost from (1-γ)^-3 to (1-γ)^-2 additive term.
Key results
- Sample-setting algorithm uses Õ(A_tot[(1-γ)^-3 ε^-2 + (1-γ)^-2]) samples and time with O(A_tot) space, improving the prior (1-γ)^-3 additive term.
- Offline algorithm runs in Õ(nnz(P) + A_tot(1-γ)^-2) time, improving prior Õ(nnz(P) + A_tot(1-γ)^-3).
- Problem-dependent variant achieves Õ(A_tot[ε^-2 V^2 + (1-γ)^-2]) where V bounds the variance term; deterministic MDPs need only Õ((1-γ)^-3) samples per state-action pair.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add truncated value updates to recursive variance-reduced value iteration | Truncated VRVI · Offline setting | time: \tilde{O}(\nnz{\bm{P}} + \Atot (1-\gamma)^{-3}) -> \tilde{O}(\nnz{\bm{P}} + \Atot (1 - \gamma)^{-2}) | Helped |
| Add truncated updates to recursive variance-reduced value iteration | Truncated VRVI · Sample setting | time: \tilde{O}(\Atot[(1-\gamma)^{-3}\varepsilon^{-2} + (1-\gamma)^{-3}]) -> \tilde{O}(\Atot[(1-\gamma)^{-3} \varepsilon^{-2} | Helped |
| Use recursive variance reduction and truncate each iteration's value change | Truncated VRVI · Per-state-action transition-estimation step | samples: \tilde{O}((1-\gamma)^{-3}) -> \tilde{O}((1-\gamma)^{-2}) | Helped |
| Adapt the sample count using an upper bound on transition variance | Problem-Dependent Truncated VRVI · Sample setting with variance bound V | time and samples: \tilde{O}(\Atot(\varepsilon^{-2}V^2 + (1-\gamma)^{-2})) | Helped |
| Apply the variance-adaptive method when transitions are deterministic | Problem-Dependent Truncated VRVI · Deterministic MDP | samples and time: \tilde{O}((1-\gamma)^3) | Helped |
Limitations
- Improvement applies only to the additive term; the (1-γ)^-3 ε^-2 term is unchanged.
- Analysis is theoretical with polylogarithmic factors hidden; no empirical evaluation is presented in the provided text.
- Problem-dependent gains require an upper bound V on the variance term, which must be known or estimated.
Experimental setup
Metrics: query complexity runtime space
Baselines: Empirical QVI Sublinear Variance-Reduced Value Iteration High Precision Variance-Reduced Value Iteration Randomized Primal-Dual Method Empirical MDP + Planning Phased Q-learning Perturbed Empirical MDP, Conservative Planning
Builds on: variance-reduced value iteration sublinear variance-reduced value iteration SARAH Freedman's inequality
Closest papers by meaning
- Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model (NeurIPS 2018 · similarity 0.91)
- Efficiently Solving Discounted MDPs via Predictions with Unknown Prediction Errors (ICML 2026 · similarity 0.89)
- Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity (ICML 2021 · similarity 0.88)
- Almost Horizon-Free Structure-Aware Best Policy Identification with a Generative Model (NeurIPS 2019 · similarity 0.88)
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.87)
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.