# Issues with Measuring Task Complexity via Random Policies in Robotic Tasks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 25 of its 59 references that are in the map.
- First posted on arXiv 21 Feb 2026.

## 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, 25 of 25)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [DeepMind Control Suite](https://mlsanity.com/paper/1801.00690/) (2018)
- [Deep Reinforcement Learning at the Edge of the Statistical Precipice](https://mlsanity.com/paper/2108.13264/) (2021)
- [Leveraging Procedural Generation to Benchmark Reinforcement Learning](https://mlsanity.com/paper/1912.01588/) (2019)
- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [Quantifying Generalization in Reinforcement Learning](https://mlsanity.com/paper/1812.02341/) (2018)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [How to Train Your Robot with Deep Reinforcement Learning; Lessons We've Learned](https://mlsanity.com/paper/2102.02915/) (2021)
- [Exploration in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2205.00824/) (2022)
- [Behaviour Suite for Reinforcement Learning](https://mlsanity.com/paper/1908.03568/) (2019)
- [Illuminating Generalization in Deep Reinforcement Learning through Procedural Level Generation](https://mlsanity.com/paper/1806.10729/) (2018)
- [Reinforcement Learning with Perturbed Rewards](https://mlsanity.com/paper/1810.01032/) (2018)
- [An empirical investigation of the challenges of real-world reinforcement learning](https://mlsanity.com/paper/2003.11881/) (2020)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Accelerating Robotic Reinforcement Learning via Parameterized Action Primitives](https://mlsanity.com/paper/2110.15360/) (2021)
- [Learning Robotic Assembly from CAD](https://mlsanity.com/paper/1803.07635/) (2018)
- [Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning](https://mlsanity.com/paper/2103.12726/) (2021)
- [Learning Stable Normalizing-Flow Control for Robotic Manipulation](https://mlsanity.com/paper/2011.00072/) (2020)
- [Analyzing Reinforcement Learning Benchmarks with Random Weight Guessing](https://mlsanity.com/paper/2004.07707/) (2020)
- [MDP Playground: An Analysis and Debug Testbed for Reinforcement Learning](https://mlsanity.com/paper/1909.07750/) (2019)
- [Bad-Policy Density: A Measure of Reinforcement Learning Hardness](https://mlsanity.com/paper/2110.03424/) (2021)
- [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)

Reinforcement learning (RL) has enabled major advances in fields such as robotics and natural language processing. A key challenge in RL is measuring task complexity, which is essential for creating meaningful benchmarks and designing effective curricula. While there are numerous well-established metrics for assessing task complexity in tabular settings, relatively few exist in non-tabular domains. These include (i) Statistical analysis of the performance of random policies via Random Weight Guessing (RWG), and (ii) information-theoretic metrics Policy Information Capacity (PIC) and Policy-Optimal Information Capacity (POIC), which are reliant on RWG. In this paper, we evaluate these methods using progressively difficult robotic manipulation setups, with known relative complexity, with both dense and sparse reward formulations. Our empirical results reveal that measuring complexity is still nuanced. Specifically, under the same reward formulation, PIC suggests that a two-link robotic arm setup is easier than a single-link setup - which contradicts the robotic control and empirical RL perspective whereby the two-link setup is inherently more complex. Likewise, for the same setup, POIC estimates that tasks with sparse rewards are easier than those with dense rewards. Thus, we show that both PIC and POIC contradict typical understanding and empirical results from RL. These findings highlight the need to move beyond RWG-based metrics towards better metrics that can more reliably capture task complexity in non-tabular RL with our task framework as a starting point.