Research map / Reinforcement learning / MDPs and planning
Finding good policies in average-reward Markov Decision Processes without prior knowledge
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.
Shows that optimal bias span H cannot be estimated with bounded samples and that online best-policy identification cannot be polynomial in H, then proposes Diameter Free Exploration (DFE), a parameter-free (ε,δ)-PAC algorithm for average-reward MDPs with sample complexity ~SAD/ε² in the generative model setting, plus an online variant with SAD²/ε².
Problem
Identifying an ε-optimal policy in average-reward MDPs without any prior knowledge of the MDP (e.g., the optimal bias span H or diameter D), in both generative-model and online settings.
Approach
Replace the unknown optimal bias span H with a data-driven upper bound on the diameter D (estimated via an SSP-based extended value iteration procedure), and plug it into a known-H algorithm; in the online setting, extend this with a diameter estimator and GOSPRL sampling, and introduce a value-iteration-based data-dependent stopping rule.
Key results
- Sample complexity of DFE in the generative model setting is Õ(SAD/ε² log(1/δ) + D²S²A log(1/δ)) with no prior knowledge, near-optimal versus the Ω(SAD/ε²) lower bound.
- Online-DFE achieves Õ(SAD²/ε² + S²AD³) sample complexity without prior knowledge.
- Any online (ε,δ)-PAC algorithm needs E[τ] = Ω(A^{S-1}/ε) on some weakly communicating MDP with H ≤ S, so polynomial dependence on H is impossible online.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Estimate D and use it as an upper bound on H instead of requiring prior knowledge of H | DFE for communicating AR-MDPs with a generative model · Generative model, small-ε regime | sample complexity: \widetilde{\cO}\left(\left[\frac{SAD}{\varepsilon^2} + D^2SA\right]\log\left(\frac{1}{\delta}\right)+D^2S^2A\right); low | Helped |
| Require prior knowledge of H | Known-H policy identification algorithm · Generative model | sample complexity: \widetilde{\cO}\left( \frac{SAH}{\varepsilon^2}\right) | Mixed |
| Estimate H as a Δ-tight upper bound without prior knowledge | Any generative-model algorithm for estimating the optimal bias span · Ergodic AR-MDPs | sample complexity: H=1/2, S=3, and A=2; more than T samples | Hurt |
| Replace generative-model sample collection with online diameter estimation and GOSPRL | Online-DFE · Online | sample complexity: \bar{\cO}_{\delta}\left(\tfrac{SAD^2}{\varepsilon^2} + S^2AD^3\right) | Hurt |
| Use the Value Iteration stopping rule and its recommendation rule for any sampling rule and bias-vector sequence | Average-reward policy identification · Generative model or online | PAC correctness: \bP\left(\tau < \infty, g^\star - g_{\widehat{\pi}} > \varepsilon\right) \leq \delta | Helped |
| Use uniform sampling with estimated optimal bias vectors and the VI stopping rule | Value Iteration stopping-rule algorithm · Unichain AR-MDPs, generative model | sample complexity: \widetilde{\cO}\left( \frac{SA(H\vee \Gamma_\cM)^2}{\varepsilon^2}\left( \log \frac{1}{\delta} +S\right)\right) | Mixed |
Surprising findings
- Estimating the optimal bias span H to within a multiplicative or additive accuracy can require arbitrarily many samples, even with a generative model and H fixed at 1/2.
- No online best-policy identification algorithm can have sample complexity polynomial in S, A and H, even when H is known.
Limitations
- Online algorithm sample complexity SAD²/ε² is a factor D away from the generative-model lower bound.
- Theoretical results only; no experiments reported.
- Relies on the (mostly theoretical) conversion from generative to online setting via GOSPRL.
Experimental setup
Metrics: sample complexity
Baselines: Zurek and Chen (known-H algorithm) Wang et al. (generative model, known t_mix) Jin and Sidford (known H)
Builds on: Perturbed Empirical Model-Based Planning (PEMP) SSP diameter estimation GOSPRL EVI-SSP
Closest papers by meaning
- Near-Optimal Sample Complexity for MDPs via Anchoring (ICML 2025 · similarity 0.93)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.93)
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.91)
- Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning (NeurIPS 2026 · similarity 0.90)
- Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (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.