Minimax Optimal Reinforcement Learning for Discounted MDPs

Jiafan He, Dongruo Zhou, Quanquan Gu

Reinforcement Learning (RL) agents typically operate in environments modeled as Markov Decision Processes (MDPs). In the discounted setting, future rewards are weighted by a factor $\gamma \in (0,1)$. While the "generative model" setting (where an agent can sample from any state-action pair) is well-understood, the online setting—where an agent learns from a single continuous trajectory—has long harbored a significant theoretical gap. Specifically, a factor of $1/(1-\gamma)$ separated the best-known regret upper bounds from the theoretical lower bounds.

This work introduces UCBVI-$\gamma$, the first model-based algorithm to achieve a minimax optimal regret bound for online discounted MDPs, effectively closing this gap.

The UCBVI-$\gamma$ Algorithm

UCBVI-$\gamma$ (Upper Confidence Bound Value Iteration for discounted MDPs) is a model-based algorithm that maintains an empirical estimate of the transition probabilities and rewards. To ensure efficient exploration, it follows the "Optimism in the Face of Uncertainty" (OFU) principle by adding exploration bonuses to its value estimates.

The core innovation lies in the use of a refined Bernstein-type bonus. Unlike simpler Hoeffding-based bonuses, Bernstein bonuses incorporate the variance of the estimated value function. By leveraging the law of total variance—a recursive property of variance in MDPs—the authors are able to bound total uncertainty more tightly. This technical advancement is the key to achieving the optimal $1.5$ exponent in the $(1-\gamma)$ term of the regret bound.

Theoretical Results

The primary contribution of this research is the alignment of upper and lower regret bounds. The authors prove that UCBVI-$\gamma$ achieves a regret of $\tilde{O}\left(\frac{\sqrt{SAT}}{(1-\gamma)^{1.5}}\right)$, where $S$ is the number of states, $A$ is the number of actions, and $T$ is the total time steps.

Comparison of sample complexity and regret bounds for various RL algorithms in discounted MDPs.

As shown in the table above, UCBVI-$\gamma$ improves upon previous model-based and model-free methods, such as Double Q-learning and UCRL, by a factor of $1/(1-\gamma)$. This improvement is particularly significant in long-horizon tasks where $\gamma$ is close to 1.

The Hardness of Discounted RL

To prove that their algorithm is minimax optimal, the authors also established a matching lower bound. They demonstrated that for any learning algorithm, there exists a "hard" MDP that forces a regret of at least $\Omega\left(\frac{\sqrt{SAT}}{(1-\gamma)^{1.5}}\right)$.

A class of 'hard' MDPs used to establish the regret lower bound.

The construction of these hard MDPs (illustrated above) involves a chain of states where a single suboptimal action can lead the agent away from high-reward regions for an extended period. Because the online setting lacks a "reset" mechanism, early mistakes in these environments lead to unavoidable regret, highlighting a fundamental difference between discounted and episodic RL.

Conclusion and Future Directions

By matching the upper and lower bounds, this work identifies the fundamental limit of learning in online discounted tabular MDPs. While UCBVI-$\gamma$ is statistically optimal, several challenges remain. The current analysis is restricted to the tabular setting; extending these minimax optimal results to environments requiring function approximation (e.g., using neural networks) is a critical next step. Additionally, the algorithm's computational complexity and performance during the initial "burn-in" phase of learning offer avenues for further optimization.

Summary updated

BibTeX
@inproceedings{he2021minimax,
  author = {Jiafan He and Dongruo Zhou and Quanquan Gu},
  title = {{Minimax Optimal Reinforcement Learning for Discounted MDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=dZroM7SIhh},
}
Figure