# Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- First posted on arXiv 12 Feb 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [Why Code, Why Now: An Information-Theoretic Perspective on the Limits of Machine Learning](https://mlsanity.com/paper/2602.13934/) (2026)
- [Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs](https://mlsanity.com/paper/2605.01242/) (2026)

## Abstract (arXiv)

Algorithms for reinforcement learning (RL) in large state spaces crucially rely on supervised learning subroutines to estimate objects such as value functions or transition probabilities. Since only the simplest supervised learning problems can be solved provably and efficiently, practical performance of an RL algorithm depends on which of these supervised learning "oracles" it assumes access to (and how they are implemented). But which oracles are better or worse? Is there a minimal oracle? In this work, we clarify the impact of the choice of supervised learning oracle on the computational complexity of RL, as quantified by the oracle strength. First, for the task of reward-free exploration in Block MDPs in the standard episodic access model -- a ubiquitous setting for RL with function approximation -- we identify two-context regression as a minimal oracle, i.e. an oracle that is both necessary and sufficient (under a mild regularity assumption). Second, we identify one-context regression as a near-minimal oracle in the stronger reset access model, establishing a provable computational benefit of resets in the process. Third, we broaden our focus to Low-Rank MDPs, where we give cryptographic evidence that the analogous oracle from the Block MDP setting is insufficient.