# Computational Hardness of Reinforcement Learning with Partial qπ-Realizability

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

## 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.

## Placed in

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

## Builds on (most cited first, 15 of 15)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model](https://mlsanity.com/paper/1806.01492/) (2018)
- [Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization](https://mlsanity.com/paper/1307.4847/) (2013)
- [Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity](https://mlsanity.com/paper/2002.07125/) (2020)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPs](https://mlsanity.com/paper/2210.15755/) (2022)
- [Exponential Hardness of Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2302.12940/) (2023)

## 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.