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

AI summary

Overview

Research area: Computational complexity of reinforcement learning (RL) with linear function approximation; specifically, hardness of learning near-optimal policies under a newly defined realizability assumption.

Technical level: Advanced. The paper relies on NP-hardness reductions, the Randomized Exponential Time Hypothesis (rETH), and the Max-3SAT problem family.

Scope: The paper defines "partial q^π-realizability" as a middle ground between q*-realizability and q^π-realizability, and proves that learning an ε-optimal policy in this setting is computationally hard under both a greedy policy set and a softmax policy set.

What This Paper Is About

In reinforcement learning with linear function approximation, two extremes are well studied: q*-realizability (only the optimal value function must be linear) and q^π-realizability (value functions for all policies must be linear). This paper introduces a middle case, partial q^π-realizability, where value functions are linear only for policies drawn from a given policy set Π. The goal is to determine whether learning an ε-optimal policy with respect to the best policy in Π is computationally tractable in this intermediate regime. The authors answer no, proving hardness results for two concrete choices of Π.

Key Contributions

1. Defines partial q^π-realizability. Given a policy set Π ⊂ A^S and a feature vector φ: S × A → R^d, an MDP is partially q^π-realizable under Π if for every π ∈ Π there exists θ_h ∈ R^d such that q^π_h(s_h, a_h) = ⟨φ(s_h, a_h), θ_h⟩ for all (s_h, a_h) ∈ S_h × A. This is weaker than q^π-realizability (which covers all policies) and stronger than q*-realizability (since Π may contain the optimal policy).

2. Defines two complexity problems over this setting. The problem gLinear-κ-RL (over a "greedy" policy set Π^g parameterized by argmax over ⟨φ'(s_h, a), θ'⟩) and sLinear-κ-RL (over a softmax policy set Π^sm induced by π_{θ'}(a|s_h) = e^{φ'(s_h,a)^T θ'} / Σ_{i=1}^κ e^{φ'(s_h,a_i)^T θ'}, with no temperature parameter). Two-action special cases are named gLinear-2-RL and sLinear-2-RL.

3. Proves NP-hardness under the greedy policy set (Theorem 3.1). Solving gLinear-κ-RL for ε ≤ 0.05 is NP-hard; no polynomial-time algorithm in the parameters (d, d', H) can compute an ε-optimal policy unless P = NP.

4. Proves an exponential lower bound under the softmax policy set (Theorem 3.2). Under rETH, there is a small constant ε₀ such that for any ε ≤ ε₀, no randomized algorithm can solve sLinear-κ-RL in time exp(o(d^(1/3)/polylog(d^(1/3)))) with error probability 1/10, where d is the dimension of the partial realizability feature vector φ. The technical core of both results is a reduction from δ-Max-3SAT and δ-Max-3SAT(b) to gLinear-κ-RL and sLinear-κ-RL respectively.

Main Findings

• Hardness persists even with an expanded policy class. The authors state that the hardness results for partial q^π-realizability mirror those for q*-realizability, showing computational difficulty remains even when Π is richer than {π*}.

• Two different complexity assumptions are needed for the two results. The greedy result (Theorem 3.1) rests only on the standard assumption NP ≠ P, while the softmax result (Theorem 3.2) requires the stronger rETH assumption. The paper notes that Π^g ⊂ Π^sm holds with high probability, so the distinction is not about one policy class containing the other.

• Randomized hardness requires a stronger hypothesis. Because algorithms interacting with the MDP under softmax policies inherently involve internal randomness, the authors argue that standard NP-hardness is insufficient—it rules out deterministic polynomial-time algorithms only—so they invoke rETH instead.

• The problem instances have specific parameters. Inputs to gLinear-κ-RL specify an MDP partially q^π-realizable under Π^g with κ actions, feature vectors φ ∈ R^d and φ' ∈ R^{d'}, horizon H = Θ(d^(1/3)), and a state space of size exp(Θ(d^(1/3))).

• rETH is stated formally in the paper. Definition 2.1: there exists a constant c > 0 such that no randomized algorithm can solve 3-SAT with v variables in 2^(cv) time with error probability at most 1/3.

• The reduction hinges on known inapproximability of Max-3SAT. Lemma 4.1 states it is NP-hard to approximate Max-3SAT within a factor of 7/8; the paper's Definition 4.2, δ-Max-3SAT, outputs "Yes" if an assignment satisfies at least a 1 − δ fraction of clauses, and the reduction uses δ < 1/8.

• A "subtle paradox" is highlighted. Both gLinear-κ-RL and sLinear-κ-RL are NP-hard, so even when the policy class is infinite and linearly realizable, learning under partial q^π-realizability remains computationally intractable.

• Contrast with the generative-model result. The paper contrasts its negative findings with the q^π-realizability setting, where computationally efficient methods are known to be achievable with access to a generative model. The learner in this paper is also assumed to have generative-model access (a simulator queryable at any (s, a) pair).

Methodology in Plain English

The authors use reduction-based complexity arguments rather than experiments.

1. Pick a known hard problem. They start from δ-Max-3SAT, the decision version of Max-3SAT, which is NP-hard to approximate for δ < 1/8.

2. Build an MDP out of the SAT formula. For a δ-Max-3SAT instance with n variables, they construct an MDP whose states are n-tuples of −1, 0, and 1, starting at s₁ = (−1, −1, …, −1). There are two actions, A = {0, 1} (interpreted as "False" and "True"), and the horizon is H = n + 1. Each action deterministically fills in one coordinate of the tuple, so the state space forms a binary tree with 2^(n+1) − 1 states. The reward is zero at every stage except the final one, where it equals the fraction of satisfied clauses, |C_true(s_H)| / |C|.

3. Design the feature vectors. The policy-set parameterization (PSP) feature φ' ∈ R^{d'} with d' = n is all zeros except for the h-th coordinate, set to 1 for action "True" and −1 for action "False." Choosing the h-th element of θ' positive or negative then selects the corresponding action via argmax, so the greedy policy set Π^g can express any variable assignment. The partial realizability feature φ and weight θ are designed separately to enforce the gLinear-2-RL structure (a construction the truncated text only begins to describe).

4. Connect the two algorithms. They show that if an algorithm A_rl solves the constructed MDP instance and returns an ε-optimal policy, then an algorithm A_sat derived from it can decide the δ-Max-3SAT instance: if φ is (1 − δ + 2ε)-satisfiable for some ε ≤ δ/2 and A_rl returns an ε-optimal policy, then reading off the variable assignment from that policy satisfies at least a 1 − δ fraction of clauses—contradicting the inapproximability of Max-3SAT. The example formula φ: (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) with n = 3 gives 15 states and horizon H = 4, where two of the eight paths (to (0,1,0) and (1,0,1)) yield reward 1/2 while the others yield 1.

5. Extend to softmax. The authors state that the techniques for gLinear-2-RL extend to sLinear-2-RL with only minor modifications, and defer the full softmax proof to an appendix.

Why This Matters

Impact on research. The paper fills a gap between two widely studied realizability assumptions and shows that the hardness of q*-realizability is not cured simply by enriching the policy class. It also implies computational challenges inherent in agnostic RL with linear function approximation, where the learner competes with the best policy in a given policy class. The authors frame the results as a partial negative answer to two questions: whether computational efficiency can be recovered in q^π-realizability with a restricted policy class Π, and whether the q*-realizability hardness can be broken with a policy class {π*} ⊊ Π.

Real-world applications (drawn from the paper's cited RL domains):

• Value-function approximation in large-state problems where function approximation is necessary for scalability (cited works on linear and nonlinear approximation).
• Game-playing systems with nonlinear value approximators, such as AlphaGo, AlphaZero, MuZero, and AlphaStar.
• Policy-gradient and actor-critic methods, which commonly use softmax policies for exploration and smooth parameterization.
• Practical RL deployments where the algorithm can only be guaranteed to represent values for a restricted, accessible set of policies rather than all policies.

Industry relevance. The results caution practitioners that no polynomial-time algorithm exists for the gLinear-κ-RL problem (unless P = NP), and that under rETH no randomized algorithm can solve sLinear-κ-RL within the stated exponential time bound. This informs expectations about what is achievable when designing algorithms around a fixed or parameterized policy class.

Future Directions

• Closing the gap between the two policy classes. Because the greedy result needs only NP ≠ P while the softmax result needs rETH, an open question is whether a stronger assumption is genuinely necessary for the softmax case or whether it can be relaxed.
• Positive results under extra structure. The paper contrasts its negative results with the generative-model efficient methods known for q^π-realizability; whether additional assumptions on Π or on the feature map could restore tractability is not resolved.
• Extending beyond greedy and softmax. Only two policy sets are analyzed, and the authors present these as two "important" cases; other natural policy parameterizations remain unexamined.
• Tightening the exponential bound. The lower bound in Theorem 3.2 is exp(o(d^(1/3)/polylog(d^(1/3)))), matching the paper's problem parameters of horizon H = Θ(d^(1/3)) and state space exp(Θ(d^(1/3))); whether these exponents can be improved is not reported.

Target Audience

Theoretical computer scientists and RL theorists working on computational complexity, function approximation, and hardness of learning; researchers studying realizability assumptions (q*, q^π) and agnostic RL; and advanced graduate students familiar with NP-hardness, 3-SAT/Max-3SAT, and Markov Decision Processes. Practitioners without a complexity-theory background will find the results informative but the proofs inaccessible.

Authors’ abstract

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 $Π$, under the assumption that all value functions for policies in $Π$ 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 $Π$ 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-$κ$-RL (greedy policy) and SLinear-$κ$-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.