Introduction
In Reinforcement Learning (RL), an agent's success is often measured by its ability to maximize cumulative rewards in an unknown environment. In the "average-reward" setting, the focus shifts to the long-term reward rate. A critical metric for evaluating these agents is regret: the cumulative difference between the rewards earned by the agent and those that would have been earned by an optimal policy with full knowledge of the environment.
Historically, a significant gap has existed in the theory of average-reward Markov Decision Processes (MDPs). While the theoretical lower bound for regret was established as approximately $\tilde{O}(\sqrt{sp(h^*)SAT})$—where $S$ is the state space, $A$ is the action space, $T$ is time, and $sp(h^*)$ is the span of the optimal bias function—practical algorithms struggled to reach it. Existing solutions were either computationally efficient but sub-optimal (often relying on the MDP's diameter rather than the span) or theoretically optimal but computationally intractable (requiring the solution of NP-hard optimization problems).
This paper introduces PMEVI-DT (Projected Mitigated Extended Value Iteration with the Doubling Trick), the first algorithm to achieve minimax optimal regret in polynomial time without requiring prior knowledge of the environment's complexity.
The Challenge of Average Reward MDPs
The complexity of an average-reward MDP is fundamentally tied to the "span" ($sp(h^*)$) of its optimal bias function, which represents the maximum difference in long-term value between any two states. Many early algorithms, such as UCRL2, relied on the "diameter" of the MDP. However, the diameter can be significantly larger than the span, leading to overly conservative regret bounds.
To achieve the tighter span-dependent minimax bound, algorithms must solve complex optimization problems to find the most optimistic bias function within a confidence set. Previous attempts to solve this required "oracles" for NP-hard problems, rendering them impractical for real-world application.
Methodology: PMEVI-DT
The authors propose PMEVI-DT to bridge this gap. The algorithm utilizes the "Doubling Trick" to manage episode lengths and introduces the PMEVI subroutine, which features two primary innovations:
1. Projection
PMEVI constructs a confidence region for the bias function $h^*$. It then "projects" its value estimates onto this region, ensuring that the agent's planning remains statistically plausible. A key technical contribution is the use of "commute times" (the time required to travel between states) to estimate bias differences without needing to know the span in advance.
2. Mitigation
While optimism is a standard heuristic in RL (Optimism in the Face of Uncertainty), excessive optimism can lead to poor performance. PMEVI employs a "mitigated" Bellman operator. By using empirical Bernstein inequalities to bound the variance of transition estimates, the algorithm keeps optimism in check, preventing the agent from pursuing rewards that are statistically unlikely.
By formulating these components within a Linear Programming (LP) framework, the authors ensure that the entire optimization process remains computationally tractable, running in polynomial time.
Empirical Evaluation
The algorithm was evaluated using the River-swim environment, a classic RL benchmark. River-swim consists of a chain of states where moving "upstream" is difficult but rewarding, while moving "downstream" is easy but offers minimal reward. This environment is specifically designed to test an agent's exploration capabilities, as it has a large diameter and requires a long sequence of correct actions to find the optimal policy.
Key results from the study include:
- Minimax Optimality: PMEVI-DT matches the theoretical lower bound of $\tilde{O}(\sqrt{sp(h^*)SAT})$.
- Computational Efficiency: The algorithm's time complexity is $O(DS^3AT)$, making it as efficient as sub-optimal predecessors like UCRL2.
- Performance: In River-swim experiments, PMEVI-DT matched the performance of existing state-of-the-art methods. Furthermore, when provided with even minimal prior information about the bias function, it significantly outperformed existing methods, reaching the optimal policy much faster.
Discussion and Future Work
PMEVI-DT represents a major milestone in RL theory by proving that minimax optimal regret is achievable in polynomial time for average-reward MDPs. It reinforces the insight that the span, rather than the diameter, is the true measure of MDP complexity.
However, some challenges remain. While polynomial-time complexity is a theoretical success, the practical overhead of solving Linear Programs within value iteration loops can be significant. Future work may focus on minimizing the frequency of these projection operations. Additionally, the current work is limited to tabular MDPs. Extending these optimal, tractable bounds to large-scale problems using function approximation (Deep RL) remains a critical frontier for the field.
Summary updated