Research map / Reinforcement learning / MDPs and planning

Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability

NeurIPS 2025 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that learning an epsilon-optimal policy under partial q^pi-realizability is NP-hard for greedy policy sets and exponentially hard (under rETH) for softmax policy sets, via reductions from delta-Max-3SAT.

Problem

Computational complexity of RL with linear function approximation when linear realizability holds only for value functions of policies in a restricted policy set Π (partial q^π-realizability), rather than all policies or only the optimal one.

Approach

Introduces partial q^π-realizability (linear realizability for all policies in a given policy class Π, between q*- and q^π-realizability) and proves hardness by reducing delta-Max-3SAT to MDPs whose greedy or softmax policy classes are parameterized by separate features, with a binary-tree deterministic MDP and reward equal to the fraction of satisfied clauses.

Key results

• Learning an epsilon-optimal policy (epsilon ≤ 0.05) under partial q^pi-realizability with greedy policy set is NP-hard (no poly-time algorithm unless P = NP).
• Under softmax policy set and rETH, no randomized algorithm solves sLinear-κ-RL in time exp(o(d^{1/3}/polylog(d^{1/3}))) with error probability 1/10.
• Hardness mirrors the q*-realizability results, showing enlarging the policy class beyond pi* does not remove computational hardness.

Surprising findings

• Even when the policy class is infinite and linearly realizable, learning under partial q^pi-realizability remains computationally intractable.

Limitations

• The policy-set features phi' differ from the realizability features phi, so a unified feature vector case is left open.
• Results are worst-case hardness and do not rule out efficient algorithms under extra structural assumptions.

Experimental setup

Builds on: q*-realizability hardness (Unique-3-SAT reduction) agnostic RL with linear function approximation randomized exponential time hypothesis

Closest papers by meaning

• Polynomial-Time Approximability of Constrained Reinforcement Learning (ICML 2025 · similarity 0.89)
• On Representation Complexity of Model-based and Model-free Reinforcement Learning (ICLR 2024 · similarity 0.88)
• Oracle-Efficient Reinforcement Learning for Max Value Ensembles (NeurIPS 2024 · similarity 0.88)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.88)
• Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set (ICML 2025 · similarity 0.88)
• Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs (NeurIPS 2024 · similarity 0.88)