Computational Hardness of Reinforcement Learning with Partial $q^π$-Realizability

• URL: http://arxiv.org/abs/2510.21888v1
• Date: Fri, 24 Oct 2025 01:18:49 GMT
• Title: Computational Hardness of Reinforcement Learning with Partial $q^π$-Realizability
• Authors: Shayan Karimi, Xiaoqi Tan,
• Abstract summary: This paper investigates the computational complexity of reinforcement learning in a novel linear function approximation regime, termed partial $qpi$-realizability.<n>We prove that learning an $epsilon$-optimal policy in this setting is computationally hard.<n>Our results mirror those in $q*$-realizability and suggest computational difficulty persists even when $Pi$ is expanded beyond the optimal policy.
• Score: 1.6328866317851185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the computational complexity of reinforcement learning in a novel linear function approximation regime, termed partial $q^{\pi}$-realizability. In this framework, the objective is to learn an $\epsilon$-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^{\pi}$-realizability but stronger than those in $q^*$-realizability, providing a practical model where function approximation naturally arises. We prove that learning an $\epsilon$-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, $\delta$-Max-3SAT and $\delta$-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^{\pi}$-realizability, in contrast to $q^{\pi}$-realizability under a generative access model.

Related papers

• Frozen Policy Iteration: Computationally Efficient RL under Linear $Q^π$ Realizability for Deterministic Dynamics [23.744125839429415]
  We study computationally and statistically efficient reinforcement learning under the linear $Q$ realizability assumption.<n>Our algorithm achieves a regret bound of $widetildeO(sqrtd2H6T)$, where $d$ is the dimensionality of the feature space, $H$ is the horizon length, and $T$ is the total number of episodes.
  arXiv  Detail & Related papers  (2026-02-28T15:41:47Z)
• Confident Natural Policy Gradient for Local Planning in $q_π$-realizable Constrained MDPs [44.69257217086967]
  The constrained Markov decision process (CMDP) framework emerges as an important reinforcement learning approach for imposing safety or other critical objectives.<n>In this paper, we address the learning problem given linear function approximation with $q_pi$-realizability.
  arXiv  Detail & Related papers  (2024-06-26T17:57:13Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  We study the sample complexity of learning an $epsilon$-optimal policy in the Shortest Path (SSP) problem. We derive complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_min$, and maximum expected cost of the optimal policy over all states $B_star$.
  arXiv  Detail & Related papers  (2022-10-10T18:34:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  We study policy optimization in an infinite horizon, $gamma$-discounted constrained Markov decision process (CMDP) Our objective is to return a policy that achieves large expected reward with a small constraint violation. We propose a generic primal-dual framework that allows us to bound the reward sub-optimality and constraint violation for arbitrary algorithms.
  arXiv  Detail & Related papers  (2022-04-11T15:08:09Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  Policy-based method in citetshani 2020optimistic is only $tildeO(sqrtSAH3K + sqrtAH4K)$ where $S$ is the number of states, $A$ is the number of actions, $H$ is the horizon, and $K$ is the number of episodes, and there is a $sqrtSH$ gap compared with the information theoretic lower bound $tildeOmega(sqrtSAH
  arXiv  Detail & Related papers  (2021-12-21T01:54:17Z)
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism [34.54294677335518]
  We study the offline reinforcement learning (offline RL) problem, where the goal is to learn a reward-maximizing policy in an unknown Markov Decision Process (MDP) In this work, we analyze the Adaptive Pessimistic Value Iteration (APVI) algorithm and derive the suboptimality upper bound that nearly matches [ Oleft(sum_h=1Hsum_s_h,a_hdpistar_h(s_h,a_h)sqrtfracmathrmmathrmVar_
  arXiv  Detail & Related papers  (2021-10-17T01:21:52Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  We consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies $Pi$ that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank $d$ of the underlying MDP.
  arXiv  Detail & Related papers  (2021-06-22T03:20:40Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states.
  arXiv  Detail & Related papers  (2021-06-18T07:54:23Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps. DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
  arXiv  Detail & Related papers  (2020-12-29T14:06:09Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.