# On the Limits of Tabular Hardness Metrics for Deep RL: A Study with the Pharos Benchmark

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 26 of its 32 references that are in the map.
- First posted on arXiv 21 Sep 2025.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents](https://mlsanity.com/paper/1709.06009/) (2017)
- [The Primacy Bias in Deep Reinforcement Learning](https://mlsanity.com/paper/2205.07802/) (2022)
- [Neural General Circulation Models for Weather and Climate](https://mlsanity.com/paper/2311.07222/) (2023)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Bigger, Better, Faster: Human-level Atari with human-level efficiency](https://mlsanity.com/paper/2305.19452/) (2023)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Understanding and Preventing Capacity Loss in Reinforcement Learning](https://mlsanity.com/paper/2204.09560/) (2022)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [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)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [The Value-Improvement Path: Towards Better Representations for Reinforcement Learning](https://mlsanity.com/paper/2006.02243/) (2020)
- [Bridging State and History Representations: Understanding Self-Predictive RL](https://mlsanity.com/paper/2401.08898/) (2024)
- [Evaluating the Performance of Reinforcement Learning Algorithms](https://mlsanity.com/paper/2006.16958/) (2020)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Bridging RL Theory and Practice with the Effective Horizon](https://mlsanity.com/paper/2304.09853/) (2023)
- [CompoSuite: A Compositional Reinforcement Learning Benchmark](https://mlsanity.com/paper/2207.04136/) (2022)
- [Understanding the Eluder Dimension](https://mlsanity.com/paper/2104.06970/) (2021)
- [A physics-informed deep neural network for surrogate modeling in classical elasto-plasticity](https://mlsanity.com/paper/2204.12088/) (2022)
- [Hardness in Markov Decision Processes: Theory and Practice](https://mlsanity.com/paper/2210.13075/) (2022)

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

- [Issues with Measuring Task Complexity via Random Policies in Robotic Tasks](https://mlsanity.com/paper/2602.18856/) (2026)

## Abstract (arXiv)

Principled evaluation is critical for progress in deep reinforcement learning (RL), yet it lags behind the theory-driven benchmarks of tabular RL. While tabular settings benefit from well-understood hardness measures like MDP diameter and suboptimality gaps, deep RL benchmarks are often chosen based on intuition and popularity. This raises a critical question: can tabular hardness metrics be adapted to guide non-tabular benchmarking? We investigate this question and reveal a fundamental gap. Our primary contribution is demonstrating that the difficulty of non-tabular environments is dominated by a factor that tabular metrics ignore: representation hardness. The same underlying MDP can pose vastly different challenges depending on whether the agent receives state vectors or pixel-based observations. To enable this analysis, we introduce textttpharos, a new open-source library for principled RL benchmarking that allows for systematic control over both environment structure and agent representations. Our extensive case study using textttpharos shows that while tabular metrics offer some insight, they are poor predictors of deep RL agent performance on their own. This work highlights the urgent need for new, representation-aware hardness measures and positions textttpharos as a key tool for developing them.