Computational Hardness of Reinforcement Learning with Partial qπ-Realizability
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
This paper investigates the computational complexity of reinforcement learning in a novel linear function approximation regime, termed partial qπ-realizability. In this framework, the objective is to learn an ε-optimal policy with respect to a predefined policy set Pi, under the assumption that all value functions for policies in Pi are linearly realizable. The assumptions of this framework are weaker than those in qπ-realizability but stronger than those in q^*-realizability, providing a practical model where function approximation naturally arises. We prove that learning an ε-optimal policy in this setting is computationally hard. Specifically, we establish NP-hardness under a parameterized greedy policy set (argmax) and show that - unless NP = RP - an exponential lower bound (in feature vector dimension) holds when the policy set contains softmax policies, under the Randomized Exponential Time Hypothesis. Our hardness results mirror those in q^*-realizability and suggest computational difficulty persists even when Pi is expanded beyond the optimal policy. To establish this, we reduce from two complexity problems, δ-Max-3SAT and δ-Max-3SAT(b), to instances of GLinear-kappa-RL (greedy policy) and SLinear-kappa-RL (softmax policy). Our findings indicate that positive computational results are generally unattainable in partial qπ-realizability, in contrast to qπ-realizability under a generative access model.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 15 of its 30 references that are in the map. First posted on arXiv 24 Oct 2025.
Builds on
15 of 30 references.
References · 15
- 2017Proximal Policy Optimization Algorithmscited by 15,215
- 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
- 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
- 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
- 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
- 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
- 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
- 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
- 2021Efficient Local Planning with Linear Function Approximationcited by 23
- 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
- 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
- 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2025Polynomial-Time Approximability of Constrained Reinforcement Learning
- 2020Batch Value-function Approximation with Only Realizability
- 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamics
- 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
- 2026Reinforcement Learning with Function Approximation for Non-Markov Processes
- 2025Agnostic Reinforcement Learning: Foundations and Algorithms
- 2026Commit to the Bit: Reactive Reinforcement Learning Done Right
- 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage