# Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs

arXiv: https://arxiv.org/abs/2010.00587 · HTML: https://mlsanity.com/paper/2010.00587/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2020.

## Built on by (most cited first, 30 of 42)

- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [MADE: Exploration via Maximizing Deviation from Explored Regions](https://mlsanity.com/paper/2106.10268/) (2021)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [Optimistic Planning by Regularized Dynamic Programming](https://mlsanity.com/paper/2302.14004/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time](https://mlsanity.com/paper/2305.15546/) (2023)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Neural Logistic Bandits](https://mlsanity.com/paper/2505.02069/) (2025)
- [Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2411.03107/) (2024)
- [Provably Efficient Kernelized Q-Learning](https://mlsanity.com/paper/2204.10349/) (2022)
- [Online Reinforcement Learning with Uncertain Episode Lengths](https://mlsanity.com/paper/2302.03608/) (2023)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)
- [Multi-armed Bandit Learning on a Graph](https://mlsanity.com/paper/2209.09419/) (2022)
- [Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach](https://mlsanity.com/paper/2305.13289/) (2023)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty](https://mlsanity.com/paper/2307.07666/) (2023)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?](https://mlsanity.com/paper/2106.08771/) (2021)
- [CIM: Constrained Intrinsic Motivation for Sparse-Reward Continuous Control](https://mlsanity.com/paper/2211.15205/) (2022)
- [Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs](https://mlsanity.com/paper/2408.11513/) (2024)
- [Safe Learning Under Irreversible Dynamics via Asking for Help](https://mlsanity.com/paper/2502.14043/) (2025)

## Abstract (arXiv)

We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-γ, which is based on the optimism in the face of uncertainty principle and the Bernstein-type bonus. We show that UCBVI-γ achieves an tildeObig(√SAT/(1-γ)1.5big) regret, where S is the number of states, A is the number of actions, γ is the discount factor and T is the number of steps. In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least tildeOmegabig(√SAT/(1-γ)1.5big). Our upper bound matches the minimax lower bound up to logarithmic factors, which suggests that UCBVI-γ is nearly minimax optimal for discounted MDPs.