mlsanityData to 14 Oct 2026

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

arXiv 2509.17092 ↗First posted 21 Sep 2025cs.LGcited by 1

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

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.

Key facts. Cited by 1 paper 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.

Builds on

26 of 32 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Bridging State and History Representations: Understanding Self-Predictive RL17 Jan

Other references · 25

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2023A Survey on Large Language Model based Autonomous Agentscited by 2,242
  3. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  4. 2017Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agentscited by 269
  5. 2022The Primacy Bias in Deep Reinforcement Learningcited by 247
  6. 2023Neural General Circulation Models for Weather and Climatecited by 239
  7. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  9. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  10. 2017Deep Exploration via Randomized Value Functionscited by 156
  11. 2023Bigger, Better, Faster: Human-level Atari with human-level efficiencycited by 147
  12. 2019Behaviour Suite for Reinforcement Learningcited by 132
13 more
  1. 2022Understanding and Preventing Capacity Loss in Reinforcement Learningcited by 125
  2. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  3. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  4. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  5. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  6. 2020The Value-Improvement Path: Towards Better Representations for Reinforcement Learningcited by 60
  7. 2020Evaluating the Performance of Reinforcement Learning Algorithmscited by 36
  8. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  9. 2023Bridging RL Theory and Practice with the Effective Horizoncited by 31
  10. 2022CompoSuite: A Compositional Reinforcement Learning Benchmarkcited by 21
  11. 2021Understanding the Eluder Dimensioncited by 19
  12. 2022A physics-informed deep neural network for surrogate modeling in classical elasto-plasticitycited by 15
  13. 2022Hardness in Markov Decision Processes: Theory and Practicecited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Issues with Measuring Task Complexity via Random Policies in Robotic Taskscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024ARLBench: Flexible and Efficient Benchmarking for Hyperparameter Optimization in Reinforcement Learning
  2. 2024Open RL Benchmark: Comprehensive Tracked Experiments for Reinforcement Learning
  3. 2025Rethinking RL Evaluation: Can Benchmarks Truly Reveal Failures of RL Methods?
  4. 2025Gym4ReaL: A Suite for Benchmarking Real-World Reinforcement Learning
  5. 2026RoAd-RL: A Unified Library and Benchmark for Robust Adversarial Reinforcement Learning
  6. 2024Can we hop in general? A discussion of benchmark selection and design using the Hopper environment
  7. 2026RLVR landscapes for iterated multiplications can be benign: Insights from spin-glass theory
  8. 2026When Does Deep RL Beat Calibrated Baselines? A Benchmark Study on Adaptive Resource Control