Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Rohatgi, Dhruv, Foster, Dylan J.
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration
by: Foster, Dylan J., et al.
Published: (2025)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
by: Golowich, Noah, et al.
Published: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
by: Kelner, Jonathan, et al.
Published: (2024)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
by: Jacot, Arthur
Published: (2025)

On the Computational Hardness of Transformers
by: Saha, Barna, et al.
Published: (2026)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
by: Rohatgi, Dhruv, et al.
Published: (2025)

Additive Models Explained: A Computational Complexity Approach
by: Bassan, Shahaf, et al.
Published: (2025)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
by: Jacobs, Peter Matthew, et al.
Published: (2026)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
by: Wang, Jie, et al.
Published: (2024)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
by: Buhai, Rares-Darius, et al.
Published: (2024)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

Decision Tree Learning on Product Spaces
by: Moakahr, Arshia Soltani, et al.
Published: (2026)

Smoothed Agnostic Learning of Halfspaces over the Hypercube
by: Kou, Yiwen, et al.
Published: (2025)

Polyhedral Instability Governs Regret in Online Learning
by: Li, Yuetai, et al.
Published: (2026)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
by: Chandrasekaran, Gautam, et al.
Published: (2024)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
by: Blanchard, Moise
Published: (2024)

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
by: AbdElhameed, Marwan, et al.
Published: (2024)

On the Computational Tractability of the (Many) Shapley Values
by: Marzouk, Reda, et al.
Published: (2025)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
by: Amir, Guy, et al.
Published: (2024)

Computational Complexity Evaluation of Neural Network Applications in Signal Processing
by: Freire, Pedro, et al.
Published: (2022)

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
by: Hollender, Alexandros, et al.
Published: (2023)

Local vs. Global Interpretability: A Computational Complexity Perspective
by: Bassan, Shahaf, et al.
Published: (2024)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
by: Merrill, William, et al.
Published: (2025)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
by: Wein, Alexander S.
Published: (2025)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
by: Li, Xiaoyu, et al.
Published: (2025)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
by: Hu, Jerry Yao-Chieh, et al.
Published: (2024)

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers
by: Liang, Yingyu, et al.
Published: (2024)

Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
by: Khalife, Sammy, et al.
Published: (2024)

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
by: Nagda, Ansh, et al.
Published: (2025)

Low-Rank Matrix Approximation for Neural Network Compression
by: Cherukuri, Kalyan, et al.
Published: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
by: Amiri, Alireza, et al.
Published: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
by: Cao, Yang, et al.
Published: (2025)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
by: Huang, Jizhou, et al.
Published: (2025)

How Global Calibration Strengthens Multiaccuracy
by: Casacuberta, Sílvia, et al.
Published: (2025)

Diffusion Language Models are Provably Optimal Parallel Samplers
by: Jiang, Haozhe, et al.
Published: (2025)

Constant Bit-size Transformers Are Turing Complete
by: Li, Qian, et al.
Published: (2025)

New Hardness Results for Low-Rank Matrix Completion
by: Chawin, Dror, et al.
Published: (2025)

Learnability of Parameter-Bounded Bayes Nets
by: Bhattacharyya, Arnab, et al.
Published: (2024)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)