# Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2018.

## Built on by (most cited first, 14 of 14)

- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [A Study of Global and Episodic Bonuses for Exploration in Contextual MDPs](https://mlsanity.com/paper/2306.03236/) (2023)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs](https://mlsanity.com/paper/2403.11477/) (2024)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [Beyond Optimism: Exploration With Partially Observable Rewards](https://mlsanity.com/paper/2406.13909/) (2024)
- [Multi-Armed Bandits with Self-Information Rewards](https://mlsanity.com/paper/2209.02211/) (2022)
- [Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs](https://mlsanity.com/paper/2205.09056/) (2022)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [Regret-Free Reinforcement Learning for LTL Specifications](https://mlsanity.com/paper/2411.12019/) (2024)

## Abstract (arXiv)

While designing the state space of an MDP, it is common to include states that are transient or not reachable by any policy (e.g., in mountain car, the product space of speed and position contains configurations that are not physically reachable). This leads to defining weakly-communicating or multi-chain MDPs. In this paper, we introduce tucrl, the first algorithm able to perform efficient exploration-exploitation in any finite Markov Decision Process (MDP) without requiring any form of prior knowledge. In particular, for any MDP with S^textttC communicating states, A actions and Gamma^textttC ≤ S^textttC possible communicating next states, we derive a widetildeO(D^textttC √Gamma^textttC S^textttC AT) regret bound, where D^textttC is the diameter (i.e., the longest shortest path) of the communicating part of the MDP. This is in contrast with optimistic algorithms (e.g., UCRL, Optimistic PSRL) that suffer linear regret in weakly-communicating MDPs, as well as posterior sampling or regularised algorithms (e.g., REGAL), which require prior knowledge on the bias span of the optimal policy to bias the exploration to achieve sub-linear regret. We also prove that in weakly-communicating MDPs, no algorithm can ever achieve a logarithmic growth of the regret without first suffering a linear regret for a number of steps that is exponential in the parameters of the MDP. Finally, we report numerical simulations supporting our theoretical findings and showing how TUCRL overcomes the limitations of the state-of-the-art.