TL;DR
This paper tackles the challenge of identifying near-optimal policies in average-reward Markov Decision Processes (MDPs) without any prior knowledge of the environment's complexity. The authors prove that estimating the optimal bias span ($H$) is fundamentally impossible in finite time, but show that by estimating the diameter ($D$) instead, they can achieve near-optimal sample complexity. They introduce the first completely parameter-agnostic algorithms for both generative (simulator-based) and online reinforcement learning settings.
What Problem Does This Paper Address?
In reinforcement learning, the average-reward setting evaluates a policy based on its long-term asymptotic mean reward per time step. This is ideal for continuous, long-running tasks because it eliminates the need to fine-tune artificial parameters like discount factors ($\gamma$) or finite time horizons ($T$). However, this asymptotic nature makes the problem highly sensitive to tiny changes in the MDP's transition dynamics.
To quantify how hard an average-reward MDP is to solve, researchers typically rely on two complexity measures:
- Diameter ($D$): The expected time it takes to travel between the two furthest states under the quickest policy.
- Optimal Bias Span ($H$): A measure of the transient reward variations before the MDP settles into its steady-state average reward.
While it is known that $H \le D$, prior state-of-the-art algorithms could only find an $\varepsilon$-optimal policy efficiently if they were given the exact value of $H$ or $D$ upfront as an input parameter. In practice, an agent enters an environment completely blind. This paper addresses a fundamental question: Can we design provably efficient, PAC (Probably Approximately Correct) reinforcement learning algorithms that require zero prior knowledge about the MDP's complexity?
Methods
The authors approach the problem by first analyzing the feasibility of estimating these hidden parameters, and then building algorithms around the parameter that proves manageable.
- Proving the Unestimability of $H$: The authors construct a family of trick MDPs to prove that estimating the optimal bias span $H$ within any tight bound requires an unbounded number of samples. Because $H$ cannot be reliably estimated from data, any algorithm relying on a known $H$ cannot easily be made agnostic.
- Diameter Free Exploration (DFE): Since $H$ is a dead end for agnostic design, the authors pivot to the diameter $D$. They design a two-stage algorithm for the generative model (simulator) setting:
- Diameter Estimation: It uses an Extended Value Iteration scheme tailored for Stochastic Shortest Path (SSP) problems to dynamically compute a high-probability upper bound $\hat{D}$ on the true diameter.
- Policy Identification: It plugs this estimated $\hat{D}$ into a modified value-reduction algorithm to safely sample the environment and output an $\varepsilon$-optimal policy.
- Online DFE: The authors extend this approach to the more difficult online setting (where the agent cannot arbitrarily reset to any state) by leveraging an online sample-collection strategy (GOSPRL) to estimate the diameter on the fly.
- Value Iteration Stopping Rule: They introduce a novel, data-dependent stopping criterion based on the span of the Bellman error, laying the groundwork for fully adaptive future algorithms.
Datasets
Not discussed in the paper. This work is purely theoretical and focuses on mathematical proofs, sample complexity upper bounds, and lower bounds. No empirical datasets or benchmarks were used.
Key Insights and Ideas
- The $H$ Trap: Even though the optimal bias span $H$ yields tighter theoretical sample complexity bounds than the diameter $D$, it is a dangerous parameter for practical algorithm design. Because a tiny change in transition probabilities can cause $H$ to explode arbitrarily, it is impossible to guess or estimate safely from data (illustrated by the hard instance in Figure 1).
- Diameter as a Safe Proxy: While $D$ can be larger than $H$, it possesses a key advantage: it can be bounded robustly using empirical transition data. This makes the diameter the right anchor for parameter-agnostic exploration.
- The Online Hardness Barrier: In the online setting, the agent can get trapped in parts of the state space where recovering takes exponential time. The authors prove that no online algorithm can achieve a sample complexity polynomial in $H$ without scaling with the diameter $D$.
Key Results
The paper provides a comprehensive map of how the new algorithms compare to prior work that required prior knowledge:
- Generative Setting (DFE): DFE achieves a sample complexity of $\tilde{O}\left(\frac{SAD}{\varepsilon^2} + D^2S^2A\right)$. In the standard regime of small $\varepsilon$, this scales as $\tilde{O}(\frac{SAD}{\varepsilon^2})$, matching the worst-case lower bound $\Omega(\frac{SAD}{\varepsilon^2}\log(1/\delta))$ up to logarithmic factors—all without knowing $D$ or $H$ beforehand.
- Online Setting (Online-DFE): The online variant achieves a sample complexity of $\tilde{O}\left(\frac{SAD^2}{\varepsilon^2} + S^2AD^3\right)$.
- Worst-Case Online Lower Bound: Theorem 3 proves the existence of a weakly communicating MDP where any online PAC algorithm requires at least $\Omega(A^{S-1}/\varepsilon)$ expected samples if it does not account for a massive diameter, proving that online average-reward RL is fundamentally hard in the worst case.
Limitations and Future Work
- The Online Gap: The online version of DFE scales with $D^2/\varepsilon^2$ rather than the optimal $D/\varepsilon^2$ found in the generative setting. It remains an open question whether an online, parameter-agnostic algorithm can bridge this gap and achieve a sample complexity linear in $D$.
- Algorithmic Complexity of the Stopping Rule: The proposed data-dependent stopping rule relies on solving complex optimization problems ($U^n_{s,a}$ and $L^n_{s,a}$) at each step, which can be computationally expensive. While the authors suggest looser confidence intervals using Pinsker's inequality as a workaround, finding a computationally lightweight yet tight implementation is left for future research.
Summary updated