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

We sincerely thank the reviewer for their positive evaluation and thoughtful feedback. We are especially grateful for the encouraging remarks regarding our motivation, technical contributions, and the significance of the results. Below, we respond to the reviewer’s two follow-up questions concerning (i) natural motivating examples for the proposed partial linear $q^{\pi}$ setting, and (ii) how our reduction approach differs from those in prior hardness results.

Answer to Question 1 (Practical Examples)

That is an excellent question, as addressing it can provide insights into both the design of theoretically motivated algorithms and the analysis of current real-world applications from the perspective of partial $q^{\pi}$-realizability. We offer two perspectives for identifying practical examples: one directly motivated by our problem setting, and another arising from an extension of our framework to a broader setting known as Agnostic RL ([1]).

A directly related example, fully aligned with our setting, is that of autonomous driving. In this case, the RL agent (i.e., the automated vehicle) must choose among a set of possible policies, which can be interpreted as feasible trajectories. These policies might be generated by a neural network trained via supervised learning or provided by human experts. Consequently, the policy set is constructed independently of the learning parameters. For instance, one could associate the policy representation parameters with elements such as fuel level, engine power, and the primary navigation system settings. These parameters correspond to our first feature vector, $\phi'$, which governs the policy construction in the partial $q^{\pi}$-realizability setting. In addition to this, another feature vector is used to represent state-action pairs, capturing aspects such as localization and other factors directly tied to the learning process for identifying near-optimal policies (i.e., trajectories).

On the other hand, there is a close connection between partial $q^{\pi}$-realizability and the well-known Agnostic RL framework, where the goal is to find the best policy with respect to a given policy class, even if the optimal policy is not included in that class. Although the Agnostic RL framework is traditionally defined for tabular settings, the conceptual similarity to our problem formulation becomes more apparent as we explore extensions to our model. A key insight here is that, in many real-world scenarios, one might only have access to a finite policy set, and the true optimal policy may not be included due to the complexity of the underlying value function. Returning to the autonomous driving example, this would correspond to a situation where the best possible trajectory (in terms of reward) is not included in the available set due to the limitations of model expressivity or safety constraints.

Identifying such real-world applications---and understanding their connections to partial $q^{\pi}$-realizability---is one of our core goals, as it not only validates the theoretical framework but also offers potential pathways for practical algorithm development.

Answer to Question 2 (Comparison of Our Reduction Approach with Prior Work)

The reduction process typically involves two main steps: (1) designing a polynomial-time reduction from a known complexity problem to an instance of the target problem, and (2) establishing a rigorous algorithmic connection between solutions to the original complexity problem and the constructed instance.

Our approach significantly differs from prior work in the first step, which is arguably the most critical part of the reduction. Specifically, we base our reductions on carefully crafted hardness problems of our own design---namely, $\delta\text{MAX-3SAT}$ and $\delta\text{MAX-3SAT}(b)$. These problems are NP-optimization problems, and designing reductions from them requires more intricate polynomial transformations than those used in prior works such as [2] and [3], where such NP-optimization variants were not employed.

From a high-level perspective, our reduction is also distinct in its ability to handle stochastic policy sets. This enables us to develop a randomized reduction under the softmax policy class, which further differentiates our work in the second step of the reduction, where the connection between solution spaces is established to complete the hardness proof.

--- [References]---

[1] Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable?, 2023.

[2] D. Kane, S. Liu, S. Lovett, and G. Mahajan. Computational-statistical gaps in reinforcement learning, 2022.

[3] D. Kane, S. Liu, S. Lovett, G. Mahajan, C. Szepesv´ari, and G. Weisz. Exponential hardness of reinforcement learning with linear function approximation, 2023.

We sincerely thank the reviewer for their thoughtful and encouraging feedback, as well as for raising these insightful questions.

Comment on Minor Weakness 1 (Selection of Softmax Policy and Anticipated Hardness Results Under General Policy Classes)

We thank the reviewer for the thoughtful question. At the beginning of Section 3.1 (“Problem Statement and Definitions”), in the part discussing softmax policies, we motivate our choice primarily due to the widespread use of such policies in actor-critic and policy gradient methods. Their effectiveness in promoting exploration and enabling smooth parameterization makes softmax a natural choice for our partial $q^{\pi}$-realizability setting.

Regarding the second part of the question, we refer to Remark 4.2, which outlines the conditions necessary for achieving similar hardness results for general policy classes. In summary, an important requirement is that the policy set must be expressible in a parametric form (as is the case with greedy and softmax policies). Additionally, during the reduction process, it must be possible to construct any policy $\pi \in \Pi$ in polynomial time with respect to the input size of the given NP-hard problem. Together with the other conditions highlighted in Remark 4.2, these properties enable us to extend the hardness result to broader classes of policies.

In future work, we plan to explore other well-defined policy classes, such as those discussed in [1], to examine whether the hardness result can still be maintained.

Comment on Minor Weakness 2 (Having Two Feature Vectors)

We appreciate the reviewer’s comment and the opportunity to clarify this point. The key reason for using different feature vectors is that it enables a cleaner and more tractable hardness proof, allowing us to bypass some otherwise very challenging and unnecessary technical complications.

From a design perspective, overloading a single feature representation to simultaneously satisfy both the linear realizability condition and the policy class definition can significantly constrain the expressiveness of both components. This makes the theoretical and practical design considerably more difficult.

Moreover, using two distinct representations aligns well with real-world scenarios. In practice, there is no requirement that the policy class available to the agent must be parameterized in the same way as the features used for learning. These are inherently separate concerns. One can easily imagine that the parameters for policy being executed come from a representation learning algorithm (e.g., via neural networks) or even from human expert demonstrations. Therefore, the main learning feature vector (i.e., the feature vector $\phi$) can—and often should—differ from the representation used to define the policy class. This separation provides flexibility and better models practical systems.

Comment on Questions and Suggestions

We sincerely thank the reviewer for the thoughtful and constructive high-level suggestions raised in the Questions section. We appreciate the positive assessment and take this opportunity to clarify several key points that shed more light on the motivation behind our framework and the technical details of our results.

• $**[Suggestion regarding broader applicability of the hardness results]:**$ We acknowledge that understanding how our hardness result interacts with different classes of policies and representations is a promising direction. In fact, the parametric design and constructibility conditions stated in Remark 4.2 can serve as a basis for testing other classes of policies, such as those studied in recent works like [1], and we are actively exploring this line of inquiry.
• $**[Typos / Writing Suggestions Section - Q2]:**$ Your understading is completely true regarding this propoer subset notation, and we wanted to say that definitly optimal policy $\pi^* \in \Pi$, but along side of this policy other policies are also in the set.
• $**[Typos / Writing Suggestions Section - Equation between lines 106/107]:**$ The use of $\sup$ instead of $\max$ is intentional and reflects a standard practice in analysis for ensuring generality. Specifically, when optimizing over the space of all policies $\pi$, the set of achievable value functions $v^{\pi}(s)$ may not have a maximum, even though a supremum exists. This situation typically arises in settings where:
  • The space of policies is infinite or uncountable,
  • The policy space is not compact, or
  • There is no policy that attains the highest value due to the lack of continuity or closure in the space.

In such cases, there may exist a sequence of policies $\pi_n$ for which $v^{\pi_n}(s)$ approaches the supremum, but no individual policy achieves the maximum. Hence, $\sup$ ensures that the value function $v^*(s) = \sup_{\pi} v^{\pi}(s)$ is always well-defined, even when an optimal policy does not exist in the strict sense. In finite MDPs, where the set of policies is finite or compact, the supremum is attained, and $\sup$ and $\max$ are equivalent. But to maintain mathematical rigor and generality, especially in theoretical settings, the supremum is preferred.

• $**[Typos / Writing Suggestions Section - Problem Statement and Main Results - Definition 3.3]:**$ We use the notation $\mathcal{S}_h$ to denote the set of states reachable at step $h$ because, for any $s_h \in \mathcal{S}_h$, we associate a specific parameter vector $\theta_h$ and a feature vector $\phi(s_h, a_h)$. This horizon-dependent view of the state space is crucial for our hardness proof, particularly in the worst-case design of the learning approximation parameters: $\phi$, $\theta$, and the policy class parameterization $\phi'$. Including this structure makes the analysis and presentation of the proof clearer and more organized.

• $**[Typos / Writing Suggestions Section - Problem Statement and Main Results - Theorem 3.1]:**$ We thank the reviewer for the thoughtful question. The threshold $\epsilon \leq 0.05$ in Theorem 3.1 is not fundamental to the inherent hardness of the underlying RL problem; rather, it arises from the specifics of our reduction. In particular, we reduce from the well-known NP-hard problem $\delta$MAX-3SAT, for which it is NP-hard to approximate within a factor of $\frac{7}{8}$. In our reduction, due to the scaling and normalization within the MDP construction, this gap translates into a value difference of at most $1/16$. Therefore, the theoretical limit for which our current reduction can prove hardness is $\epsilon \le 1/16$. The specific choice of $\epsilon = 0.05$ reflects a conservative parameter tuning to ensure clarity and correctness, but tighter analysis could likely push the bound closer to this $1/16$ threshold. Thus, we view the $\epsilon$-bound as a feature of the reduction and not as evidence that the problem becomes easier for larger $\epsilon$.

We appreciate the reviewer’s insightful comments, which have helped us refine both the theoretical and practical positioning of our contributions. We will carefully address the noted typos and writing issues in the final version to ensure clarity and precision throughout the paper.

---[References]---

[1] Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable?, 2023.

We thank the reviewer for their valuable comments and constructive feedback. We appreciate your time in reading the paper carefully and for raising important points. Below, we address your main concerns in detail.

Comment on Weakness 1 (Ambiguity of Definition 3.1)

We agree with the reviewer that, technically, the parameter $\theta$ depends on the policy. However, in much of the literature, this dependency is often left implicit to improve the clarity and readability of expressions. Since the policy class is indexed by $\theta$, it is generally understood that $\theta$ parameterizes the policy, and adding a superscript to denote this dependence is redundant in context. That said, we acknowledge the potential ambiguity and will clarify this point in the revised version.

Comment on Weakness 2 (Clarification of Our Contributions)

We appreciate this insightful observation. First, note that this is a hardness result, so it is not necessary to demonstrate NP-hardness for all possible policy classes. It suffices to show that there exists a policy class for which the learning problem becomes NP-hard. In our work, we show that two broad and widely used policy classes---greedy and softmax policies---indeed have this property.

Importantly, this work does not aim to investigate structural properties of policy classes. Our focus is solely on the fact that the policy class contains the optimal policy along with some additional policies, which introduces a new family of problems characterized by partial $q^{\pi}$-realizability.

The concerns raised in the comment are certainly relevant when the goal is to design efficient algorithms---statistically or computationally. In such settings, one may leverage structural assumptions on the policy class to guide the design of efficient algorithms. However, that is not the objective of this paper.

In the $q^*$-realizability setting, the policy class contains only the optimal policy, and prior work has already established hardness results for this case. In contrast, our goal is to examine how the hardness result evolves when we expand the policy set to include other policies as well---thus moving toward the stronger assumption of $q^{\pi}$-realizability, under which efficient algorithms are known to exist. Our result provides insight into the limits of algorithm design, by showing that even under rich policy classes such as greedy and softmax, one cannot hope for efficient solutions in general.

We acknowledge that establishing hardness results for other types of policy classes would pose a valuable technical challenge. However, such an extension is not essential to our main message, as the policy classes we study already encompass two of the most widely used classes in practical reinforcement learning algorithms, namely argmax and softmax.

Comment on Weakness 3 (Comprehensive Comparison of Proof Techniques)

We thank the reviewer for this insightful comment. The referenced work [1] is indeed one of the key related papers, and we have discussed its connection to our approach in detail in the Extended Discussion of Related Work section in the appendix. While both papers reduce from SAT-style problems, the settings and techniques differ significantly. In [1], the policy class includes only a single deterministic optimal policy, and the proof techniques are tailored to that restricted setting. In contrast, our work considers more general and potentially stochastic policy classes (e.g., softmax policies), which necessitates a randomized reduction technique to reflect this broader structure. Furthermore, our MDP construction techniques are novel and differ substantially from those in [1], as they are specifically designed to accommodate the partial $q^\pi$-realizability setting with a richer policy class. These distinctions are critical for achieving our hardness result and are explained in detail in the appendix. To clarify this point, we will bring some of these discussions to the main body of the paper in the revised version. Thank you again for the comment.

Answer to Question 1 (Clarification of $\Pi_g \subseteq \Pi_{sm}$)

Thank you for the question. In our construction, the softmax policy class $\Pi_{sm}$ is parameterized by $\theta' \in \mathbb{R}^{d'}$. By appropriately choosing values of $\theta'$, the softmax policy can assign arbitrarily high probability to a specific action in each state. Consequently, $\Pi_{sm}$ can approximate any deterministic greedy policy arbitrarily closely. This is what we mean by stating that "$\Pi_g \subseteq \Pi_{sm}$ holds with high probability."

To be more formal, we appeal to an analogy with the coupon collector problem. Suppose there are $N$ distinct deterministic greedy policies in $\Pi_g$, each corresponding to a different configuration of preferred actions across states. If we randomly sample $O(N \log N)$ parameter vectors $\theta'$ (from a distribution with full support over $\mathbb{R}^{d'}$), then with high probability, for each greedy policy in $\Pi_g$, there exists a sampled $\theta'$ such that the resulting softmax policy assigns sufficiently high probability to the same action choices—effectively mimicking that greedy policy.

Thus, the probability is defined over the random draws of $\theta'$ used to generate policies in $\Pi_{sm}$. Because the parameter space is continuous and unbounded, we can sample enough softmax policies to cover all greedy policies with high probability.

We will clarify this interpretation further in the final version to improve precision and readability.

Answer to Question 2 (NP-Hardness of SLINEAR-κ-RL in Theorem 3.2)

Thank you for your comment. You are correct that Theorem 3.2 does not explicitly state that SLINEAR-$\kappa$-RL is NP-hard. However, the theorem is based on the Randomized Exponential Time Hypothesis (rETH), which is strictly stronger than the standard assumption that P $\ne$ NP. Specifically, rETH rules out not only polynomial-time deterministic and randomized algorithms, but also sub-exponential time randomized algorithms for NP-complete problems like 3-SAT.

Therefore, the intractability result in Theorem 3.2 already implies NP-hardness, and in fact goes further by showing that no sub-exponential time randomized algorithm (with low error probability) exists for SLINEAR-$\kappa$-RL under rETH.

--- [References]---

[1] D. Kane, S. Liu, S. Lovett, G. Mahajan, C. Szepesv´ari, and G. Weisz. Exponential hardness of reinforcement learning with linear function approximation, 2023.

We sincerely thank the reviewer for the thoughtful and constructive feedback. We are encouraged by the engagement with our work and appreciate the opportunity to clarify key aspects of our approach, assumptions, and contributions. Below, we address each of the reviewer’s comments in detail.

Comment on Weakness 1 (The Use of Separate Feature Representations)

We appreciate the reviewer’s comment regarding the use of two different feature representations. As clarified in the paper, our problem formulation involves two feature vectors: $\phi'$ is used solely for defining the policy class, while $\phi$ is used for learning. This separation enables us to construct rich policy classes without the restriction that the same representation must satisfy the linear realizability condition, which is required only for $\phi$. In contrast, if we were restricted to using a single feature vector for both policy class construction and learning, we would face significant technical challenges. Specifically, any constraint imposed by the policy class would directly affect the realizability condition, making the design of the linear approximation architecture highly constrained and difficult to analyze. This modeling choice is also motivated by real-world applications where the policy class may come from external sources — for example, from human demonstrations or a neural policy prior — and is thus independent of the features used in learning. A concrete example is autonomous driving, where the set of feasible trajectories (i.e., the policy class) may be determined by physical parameters such as engine power or wheel dynamics, while the learning features could be derived from GPS-based localization, camera input, or LIDAR — representations not necessarily tied to the internal mechanics of the vehicle. That said, we agree that understanding the complexity of learning under a single feature vector remains an important technical question. We experimented with constructions such as concatenating $\phi$ and $\phi'$ into a joint representation, but found that this approach introduces new complications due to our hardness construction methods. We leave this as an open and important direction for future work.

Answer to Question 1 (Additional Conditions for Efficient Learning)

We interpret "efficient learning" here as referring to computational efficiency. This is indeed a compelling and largely open problem. Existing works have primarily focused on the extremes of full $q^*$-realizability and full $q^\pi$-realizability, and relatively no attention has been paid to intermediate cases like the partial $q^\pi$-realizability setting we introduce. One clear case where efficient learning is possible is when the policy class includes all possible policies — in such cases, previous results (e.g., those assuming full coverage with generative model access) imply tractability. However, beyond this trivial case, it remains unclear what structural properties of the policy class or function class (e.g., covering number, spanning capacity) would ensure computational tractability under partial realizability. On the statistical side, we believe that results from the Agnostic RL literature [1] may offer useful tools. In particular, the notion of bounded spanning capacity in that work might extend to our setting with linear function approximation, suggesting a potential path toward identifying conditions for statistical efficiency. Exploring both the computational and statistical aspects of learning under partial realizability is part of our ongoing work.

Answer to Question 2 (Possibility of Simple Experiment)

We appreciate this suggestion. However, current linear function approximation algorithms are typically designed for $q^*$-realizability or full $q^\pi$-realizability settings. These assumptions are fundamentally incompatible with our partial $q^\pi$-realizability setting, making such algorithms inapplicable without significant modification. As a result, any empirical failure of these methods on our constructed MDPs would primarily reflect an assumption mismatch rather than illuminate the computational hardness at the core of our contribution. That said, an important direction for future work is to investigate how existing algorithms can be adapted or extended to work under partial $q^\pi$-realizability. This would help bridge the gap between theoretical hardness results and practical algorithmic design. Once such adaptations are available, they could serve as meaningful baselines to empirically test the computational challenges in this regime.

Answer to Question 3 (Hardness Results under Weaker Access Assumptions)

Yes — our hardness results extend to weaker access models, including the online access model. In fact, our lower bound construction remains valid under this assumption, and the proof does not require modification. The online model restricts learners to follow complete trajectories rather than arbitrarily querying any state-action pair, making it a strictly weaker assumption than generative model access. Thus, our hardness results apply directly to this setting as well.

--- [References]---

[1] Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable?, 2023.