Research map / Learning theory and algorithms / Sample complexity
Near-Optimal Sample Complexity for MDPs via Anchoring
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.
Proposes SAVIA+, a model-free algorithm combining Halpern anchored value iteration with recursive (SARAH-style) sampling and a doubling-trick stopping rule, achieving near-optimal O~(|S||A|h*^2/eps^2) sample complexity for weakly communicating average-reward MDPs without prior knowledge, plus an analogous SAVID+ for discounted MDPs.
Problem
Computing an epsilon-optimal policy for average reward MDPs (weakly communicating) with a generative model, model-free, without prior knowledge of the span of the bias vector, with a near-optimal sample complexity.
Approach
Combine Halpern's anchored value iteration (in the quotient space modulo constants) with recursive sampling that estimates only the increments of the Bellman operator, using a Azuma-Hoeffding-style analysis to set sample sizes, plus a doubling-trick stopping rule based on the empirical Bellman residual in span seminorm.
Key results
- SAVIA+ attains O~(|S||A| h*^2/eps^2) sample and time complexity for weakly communicating average-reward MDPs, with probability 1-delta, without prior knowledge of h*.
- The expected sample complexity of SAVIA+ is of the same order O~(|S||A|h*^2/eps^2), with expected policy error at most 16 eps + delta*span(r), derived via the doubling trick.
- SAVID+ for discounted MDPs achieves O~(|S||A| ||Q*||_inf^2/((1-gamma)^2 eps^2)), improving the basic SAVID bound by a factor 1/(1-gamma)^2 when ||Q*|| is smaller than 1/(1-gamma).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SAVIA+ instead of the prior model-free method | Model-free algorithms for weakly communicating average-reward MDPs · Weakly communicating average-reward MDPs | sample complexity: $\widetilde{O}\left({|\mathcal{S}||\mathcal{A}|\sp{h^*}^7}/{\varepsilon^{7}}\right)$ to $\widetilde{O}(|\mathcal{S}||\ma | Helped |
| Use SAVIA+ instead of the prior model-based method | Algorithms for weakly communicating average-reward MDPs · Weakly communicating average-reward MDPs | sample complexity: $\widetilde{O}\left(|\mathcal{S}||\mathcal{A}|\sp{h^*}^2/{\varepsilon^{2}}\right)$ to $\widetilde{O}\big(|\mathcal{S}||\ | No clear effect |
| Add doubling and an empirical Bellman-residual stopping rule | SAVIA · Weakly communicating average-reward MDPs | sample complexity: SAVIA complexity depends on $n^2$; SAVIA+ complexity is ${O}\big(\widehat{L}\,|\mathcal{S}||\mathcal{A}|((\nu^2/\varepsi | Helped |
| Add doubling and a Bellman-residual stopping rule | SAVID · Discounted MDPs | sample complexity: SAVID requires $\widetilde{O}(|\mathcal{S}||\mathcal{A}|/((1\! -\!\gamma)^4\varepsilon^{2}))$; SAVID+ has complexity $${ | Helped |
Limitations
- Complexity is larger than the known lower bound by a factor of the span h*, so not fully optimal.
- Analysis is in the generative model setting only; episodic or online sampling not addressed.
- Expected-complexity bound contains extra delta-dependent terms from unlucky events.
Experimental setup
Metrics: sample complexity span seminorm Bellman residual optimality gap
Baselines: Halpern-anchored value iteration with mini-batching (SAVI-type, s^7/eps^7) model-based weakly communicating algorithm (h*^2/eps^2) model-based communicating algorithm with diameter D model-free mixing-time methods
Builds on: Halpern iteration Azuma-Hoeffding inequality SARAH variance reduction Anc-VI for Q-learning (Lee & Ryu)
Closest papers by meaning
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.94)
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.93)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.92)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.90)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.90)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
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.