# Hardness in Markov Decision Processes: Theory and Practice

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 43 references that are in the map.
- First posted on arXiv 24 Oct 2022.

## Builds on (most cited first, 14 of 14)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)

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

- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)
- [When Do Skills Help Reinforcement Learning? A Theoretical Analysis of Temporal Abstractions](https://mlsanity.com/paper/2406.07897/) (2024)
- [On the Limits of Tabular Hardness Metrics for Deep RL: A Study with the Pharos Benchmark](https://mlsanity.com/paper/2509.17092/) (2025)

## Abstract (arXiv)

Meticulously analysing the empirical strengths and weaknesses of reinforcement learning methods in hard (challenging) environments is essential to inspire innovations and assess progress in the field. In tabular reinforcement learning, there is no well-established standard selection of environments to conduct such analysis, which is partially due to the lack of a widespread understanding of the rich theory of hardness of environments. The goal of this paper is to unlock the practical usefulness of this theory through four main contributions. First, we present a systematic survey of the theory of hardness, which also identifies promising research directions. Second, we introduce Colosseum, a pioneering package that enables empirical hardness analysis and implements a principled benchmark composed of environments that are diverse with respect to different measures of hardness. Third, we present an empirical analysis that provides new insights into computable measures. Finally, we benchmark five tabular agents in our newly proposed benchmark. While advancing the theoretical understanding of hardness in non-tabular reinforcement learning remains essential, our contributions in the tabular setting are intended as solid steps towards a principled non-tabular benchmark. Accordingly, we benchmark four agents in non-tabular versions of Colosseum environments, obtaining results that demonstrate the generality of tabular hardness measures.