Cover Image

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Feng, Guhao, Zhong, Han
Format:	Preprint
Published:	2023
Subjects:	Machine Learning Artificial Intelligence Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Diversity-aware clustering: Computational Complexity and Approximation Algorithms
by: Thejaswi, Suhas, et al.
Published: (2024)

Theoretical limitations of multi-layer Transformer
by: Chen, Lijie, et al.
Published: (2024)

Compression Barriers for Autoregressive Transformers
by: Haris, Themistoklis, et al.
Published: (2025)

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
by: Blum, Avrim, et al.
Published: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

The Computational Complexity of Almost Stable Clustering with Penalties
by: Khodamoradi, Kamyar, et al.
Published: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
by: Sato, Atsuki, et al.
Published: (2025)

$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
by: Nye, Logan
Published: (2025)

On the Power of Interactive Proofs for Learning
by: Gur, Tom, et al.
Published: (2024)

Efficient and Private Property Testing via Indistinguishability
by: Dwork, Cynthia, et al.
Published: (2025)

Private graphon estimation via sum-of-squares
by: Chen, Hongjie, et al.
Published: (2024)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

Active Learning for Decision Trees with Provable Guarantees
by: Moakhar, Arshia Soltani, et al.
Published: (2026)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Rate-optimal community detection near the KS threshold via node-robust algorithms
by: Ding, Jingqiu, et al.
Published: (2025)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
by: Tran, Tan D., et al.
Published: (2025)

Avoiding Obfuscation with Prover-Estimator Debate
by: Brown-Cohen, Jonah, et al.
Published: (2025)

Sorting by Strip Swaps is NP-Hard
by: Roy, Swapnoneel, et al.
Published: (2025)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

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

AdaBoost is not an Optimal Weak to Strong Learner
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

Differentially Private Verification of Distribution Properties
by: Du, Elbert, et al.
Published: (2026)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)

Adaptive and oblivious statistical adversaries are equivalent
by: Blanc, Guy, et al.
Published: (2024)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Samplability makes learning easier
by: Blanc, Guy, et al.
Published: (2025)

Efficient Turing Machine Simulation with Transformers
by: Li, Qian, et al.
Published: (2025)

Is nasty noise actually harder than malicious noise?
by: Blanc, Guy, et al.
Published: (2025)

Low-degree phase transitions for detecting a planted clique in sublinear time
by: Mardia, Jay, et al.
Published: (2024)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

Supersimulators
by: Dwork, Cynthia, et al.
Published: (2025)