Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability
Authors: Shayan Karimi
Xiaoqi Tan
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement Learning
Linear Function Approximation
Computational Complexity
NP-Hardness
Primary area: reinforcement_learning
TL;DR: We propose a novel reinforcement learning problem under more moderate and realistic assumptions, partial $q^{\pi}$-realizability, and show that learning remains computationally hard under greedy and softmax policy sets.

Abstract: This paper investigates the computational complexity of reinforcement learning within 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 corresponding to policies in $\Pi$ are linearly realizable. This framework adopts assumptions that are weaker than those in the $q^{\pi}$-realizability setting yet stronger than those in the q*-realizability setup. As a result, it provides a more practical model for reinforcement learning scenarios where function approximation naturally arise. We prove that learning an $\epsilon$-optimal policy in this newly defined setting is computationally hard. 
More specifically, we establish NP-hardness under a parameterized greedy policy set (i.e., argmax) and, further, show that—unless NP = RP—an exponential lower bound (exponential in feature vector dimension) holds when the policy set contains softmax policies, under the Randomized Exponential Time Hypothesis. Our hardness results mirror those obtained in the $q^*$-realizability settings, and suggest that computational difficulty persists even when the policy class $ \Pi $ is expanded beyond the optimal policy, reinforcing the unbreakable nature of the computational hardness result regarding partial $ q^{\pi} $-realizability under two important policy sets. To establish our negative result, our primary technical contribution is a reduction from two complexity problems, $\delta$-Max-3SAT and $\delta$-Max-3SAT($b$), to instances of our problem settings: GLinear-$\kappa$-RL (under the greedy policy set) and SLinear-$\kappa$-RL (under the softmax policy set), respectively. Our findings indicate that positive computational results are generally unattainable in the context of partial $ q^{\pi} $-realizability, in sharp contrast to the $ q^{\pi} $-realizability setting under a generative access model.

Computational Hardness of Reinforcement Learning with Partial - -ealizabbilyy
Shayan Karimi University of Alberta Edmonton, Canada skarimi @eaalluraaabrrrre
Xiaoqi Tan University of Alberta Edmonton, Canada
xiaoqi tanuua wtw.uallbera...m
Abstract
This paper investigates the computational complexity of reinforcement learning within novel linear function approximation regime, termed partial q" rraallizaaiility. In this framework, the objective is to learn an e-optimal policy with respect a predefined policy set II, under the assumption that all value functions correspond- ing to policies in are linearly realizable. This framework adopts assumptions that are weaker than those in the q" rraliizabbillty setting yet stronger than those in the q² relreaiizayility setup. As a result, provides a more practical model for reinforcement learning scenarios where function approximation naturally arise. We prove that learning an e-optimal policy in this newly defined setting is computa- tionally hard. More specifically, we establish NP- hardddddess under a parameterized greedy policy set (i.c., argmax) and, further, show that that-unless NP RP an exponential lower bound (exponential in feature vector dimension) holds when the policy set contains softmax policies, under the Randomized Exponential Time Hy- pothesis. Our hardness results mirror those obtained in the q" p"-rralizability settings, and suggest that computational difficulty persists even when the policy class is expanded beyond the optimal policy, reinforcing the unbreakable nature of the com- putational hardness result regarding partial g" rrrarizzaabilty under two important policy To establish our negative result, our primary technical contribution reduction from two complexity problems, 5-MAX-3SAF and 5-MAX-3S AT()), instances of our problem settings: GLINEAR-K-BR (under the greedy policy set) and SLINEAR-K- RL (under the softmax policy set), respectively. Our findings indicate that positive computational results are generally unattainable in the context of partial qf realrizabbility. in sharp contrast to the q² -ealliizayyyy setting under a generative access model.
Introduction
In reinforcement learning (RL), the term "efficiency" often refers to statistical efficiency, which relates to the number of samples required for algorithm converge near-optimal solution. Another critical, though less frequently addressed perspective is computational complexity, which focuses on the computational demands of the algorithm. To address these challenges, function approximation techniques- either linear or nonlinear-an commonly employed. These approximation methods enable the estimation of the value function so that resulting complexity bounds become independent of the size of the state space (TVR97 SS188 Ber09). Instead, complexity depends on approximation parameters, thereby offering scalable and efficient framework for RL in large state spaces.
Prominent RL applications employing nonlinear value approximators include AlphaGo [HHM 16), AlphaZero (SHS 17), MuZero [SAH*20) 20), and AlphaStar [MOS 23). Despite their practical success, nonlinear approximators are challenging to analyze theoretically. In contrast, linear value approxima- tors allow for tractable theoretical analysis. Two primary settings for linear function approxima-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

tion are commonly studied. The first, known as the gerrealizability setting [WAS2]] WRI6] involves approximating only the optimal value function as linear function. This setting makes no assumptions regarding the linearity of value functions under non-optimal policies. rendering it the least restrictive assumption. The second setting, known as the q" -realizzability setting [DKWY20), assumes that value functions for all policies are linearly realizable-a significantly stronger condition. Under the q" and v -realizability assumptions, recent works have established quasi-poly quasi-polynomial [KLLM22] and exponential lower bounds [KLL*23 on computational complexity. Under the stronger assumption of geerealizabilltyy it known that computationally efficient methods can be achieved with access to generative model [YHAY+22]
Motivating Questions. The aforementioned studies motivate the following intriguing question:
Ql: Can we still achieve positive results (in terms of computational efficiency) in the q" -reraliizayylityy setting with a restricted policy class II?
Alternatively, the above question can be posed in the reverse direction:
Q2: Can we break the hardness result (in terms of computational efficiency) for the q" -rralizzabill setting when considering a policy class II with {x") S I1?
To illustrate why answering the questions above is interesting, let us consider the spectrum of linear function approximation in RL, characterized by two endpoints. At one end of this spectrum, we have q- -realiizability, representing a relatively weak assumption. At the opposite end is g"-realizability, significantly stronger realizability condition. Addressing the two questions posed above thus provides a means of bridging the gap between these two extreme cases. Towards this end, we propose the concept of partial 9" rrealizabiliyy formally introduced in Section Under this partial realizability concept, our problem setting assumes access to specific class of policies II within which the action-value functions for all state-action pairs are linearly realizable.
From a practical perspective, we can also view this partial n rraliizabiily setting through the lens of agnostic RL with linear function approximation [JLR+23). In agnostic RL, we are given a policy set 11, and the goal learn policy ı that competes with the best policy in the given policy class 11 C AS, where A and S denote the action and state spaces, respectively. Analogously, the partial qº -r-realizability setting incorporates the key concept of inaccessibility to the optimal value function representation, highlighting the relationship between the agnostic RL. framework and our problem setting when linear function approximation is employed.
Main Contributions. In this paper, we introduce partial grareizizabil that bridges the gap between midler -ealliiizabil)yt) and stronger (q"-realizability) assumptions by defining the subclass of realizable policy sets for linear value function approximation. Based on the concept of partial q"- realizability, we obtain two main results. First, we define an instance of partial g ge-realizability in which the policy set 1I consists of deterministic greedy policies. We show that learning a near-optimal policy in this setting is NP-hard. This result provides a partial negative answer to the aforementioned question Ql-it is not possible to ensure computational efficiency when access is limited to only a subclass of linearly realizable policies. Second, we move beyond the deterministic greedy policy set and study partial 9º' -reaaiizabillity under a more general policy set based on stochastic softmax policies. Under the randomized exponential time hypothesis (rETH), we prove that this problem setting exhibits exponential computational hardness, mirroring the result for the q- rrealizzaee setting. This result again provides a partial negative answer to the aforementioned question Q2-thr the computational hardness remains unbreakable even when considering policy set richer than the optimal policy ).
As broader implication, our hardness results for the partial gerreliizability setting also show the existence of computational challenges inherent in Agnostic RL [JLR 233 within the linear function approximation context.
2 Preliminaries
Pu194], an agent aims to maximize expected total reward over time by making optimal decisions through interaction with its given environment. In our problem setting, the environment is modeled as a Markov Decision
Markoy Decision Process. In reinforcement learning SB18
BT%

---

Process (MDP) M = (S, H.) where S is a discrete set of state, A is discrete set of actions, P SxSxx A - A(S) is the stochastic transition probability function which maps each (s, a) E S x A to probability distribution over states, and R: S A ( 1)) is the stochastic reward function, where (XX) the set of probability distributions supported on set X. When we take action a in state we get sampled next state s' ~ P(s,, a), and R ~ R(s, a) is stochastic reward received for taking action a in state s. In the episodic setting, the agent interacts with the environment starting from an initial state 91, where the subscript denotes the time step or stage. During episode, at each step h, taking an action dn in state S₁, results in a deterministic transition to the next state 81.41 and yields reward R The episode continues until the agent reaches terminal state set Sy C S meets another predefined stopping condition. We denote by S,, the set of states reachable from the initial state $1 after exactly h steps. Without loss of generality, into H disjoint subsets, such that S = S US2 U... . Sh and S; ns; = 0 for any distinct i, E {H]. Additionally, consider deterministic stationary policies S + A, mapping each state action, as well as stochastic policies x : S + A(A), which map each state E S to probability distribution over actions. The value function e" (s) and the action-value function q" (s, a) defined for any E S and (s, a) E ES x A under any policy as follows:
assume the state space S is partitioned
single
11
H Σ
0. 88) = Em
Σ L==1
R2 81 = (s, Exr,
RR - -,
1h=1
The optimal policy x² yields the optimal state-value function (*(ss ) and action-value function q (s, a). formally defined as follows:
v² (s) sup 0 (s) sup q" (s, (s su.p"((s.)) R(s, a) + sup (s'), aEA
where s' is the next state after taking action in state Furthermore, the interaction protocol between the agent and the environment based on the generative model. The generative model-often referred to as the random access model [Kak03 SWW+ 19 YW19) represents the strongest form of eevirnennvionmment interaction. Under this model, the learner can query a simulator with any (s, a) E (S x A) to obtain sample (s', R). where s' P(s, a) and R ~ R(s, a). This allows access to any state-action pair, regardless of whether the state has been previously visited. Throughout this paper, we assume the agent has access to generative model.
Linear Function Approximations. In the function approximation setting, given a policy æ, the action-value function q" (sh, a) for any (sh, a) E S x A can be represented using feature mapping 6 S x A + IRd, which assigns d- dddimensional feature vector to each state-action pair. We assume a linear function approximation, meaning there exists a weight vector fn E Rd such that
(s a) = (Ø(sh, On))
This formulation expresses the action-value function as the inner product between the feature represen- tation and the weight vector. Furthernore, we provide additional details on the different realizability settings in Appendix A
3-SAT and Randomized Exponential Time Hypothesis. In the remainder of this section, we provide the relevant background on computational complexity. Let yo be Boolean formula, where the terms x; and oe are referred to as literals. A formula yo is said to be in Conjunctive Normal Form (CNF) if it can be expressed as
s =
C
where C,'s are called clauses and consist of disjunctions (ORs) of literals. In general, a k-SAT formula refers to a CNF-SAT problem in which each clause contains exactly k literals. For 3-SAT, an NP-complete problem [Coo7] Lev73) the Randomized Exponential Time Hypothesis (rETH) is defined as follows:
Definition 2.1 (Randomized Exponential Time Hypothesis (rETH) [DHM+14). There exists a constant e. > 0 such that randomized algorithm can solve the 3-SAT problem with variables in 20 time, with an error probability of at most 3.
Definition 2.1 emphasizes on the fact that randomized algorithms cannot solve NP-complete problems in sub-exponential time. As we will see, we use the rETH to establish an exponential lower bound for partial -realizability setting under the softmax policy class 11
3

---

Problem Statement and Main Results
We begin this section by introducing the concept of partial q" re-realizabilityy followed by formal descriptions of our problem settings under the greedy policy set II and the softmax policy set II" We then present our two main hardness results, stated in Theorem 3.1 (under II9) and Theorem 3.2 (under I[
3.1 Problem Statement and Definitions
Let us first define the concept of partial q" -realiizabilli in Definition 3.1 below.
Definition 3.1 (Partial q" -"-reliiabiility under 11). Given a policy set 11 A and a feature vector
ó : S x A + Rd, an MDP is said to be partially q" -realizze under II if. for all a E 11, there exists 0g Rd such that:
th (Sh; an) (0(Sh, an); On) (sh,,a)) Sn X
Definition 3.1 ensures the exact linear realizability when using Φ E I2 under a subset of policies II C A Clearly, partial -earailizabillty is weaker assumption than the q" re-reelizability assumption, since we only assume linear realizability under given policy set instead of under all the possible policies. On the other hand, partial 9" reeriiiizbbility is stronger than q" rr-eelizability since the policy set IT may include the optimal policy. Thus, by Definition 3.1 we can bridge the gap between these two extreme cases of realizability assumptions. We refer to and partial realizability feature and weight vectors, respectively.
Definition 3.2 (Learner's objective: c-optimality relative to IT). Given an initial state 81 E S, policy π E A is c-optimal with respect to the best policy in II if
max U - - Sc.
(2)
REll
In the case of a learner that employs randomized algorithms, we return the policy т that satisfies the above condition with high probability. Note that the learned policy is deterministic when the policy class II is deterministic, and stochastic when stochastic.
Greedy Policy Set IT9. As our first attempt to have well-defined II, define special class of policy set called greedy policy set, which is parameterized by given feature vector d' Rdd The details regarding this parameterization are given in the definition below.
Definition 3.3 (Greedy policy set II9). Let ø' S x A Rdd be a feature vector with dimension d' E N. For any h [H] and 6' Rdd, let my. Sp A be defined as follows:
z (sh) arg max
(g' 0),
Ysh. S
aEA
In the event of a tie in the argmax, the action with the lowest index is selected. The greedy policy set, induced by any Of E dd" is defined as:
11s = 10 E Rdd
the action TT. (8A) is greedy with respect (o' a),0) (i.e., argmax). Also note that changing 0' can result in different greedy actions at each state 8д Sr. Thus, Definition 3.3 implies that for different values of 0', we may obtain different greedy actions T. (sa) for each 8h E Sn. We refer to ø' and 0' as the policy set parametrization (PSP) feature and weight vectors, respectively. We are now ready formally define our first complexity problem:
By Definition 3.3
Complexity Problem GLINEAR-K-RL
Input:
MDP M that partially qº' -realizabee under T with actions, having access to feature vectors (o E gd and E IRd") horizon = O(dš), and state space of size exp(O(d)) )).
Goal:
Find a policy such that satisfies the e-optimality condition in Equation 2.

---

In the complexity problem GLINEAR- RL, "G" stands for greedy. As special instance of GLINEAR-N-RL, we define the two-action version of the GLINEAR-N- problem as GLINEAR-2- RI.
Softmax Policy Set 11amm Softmax policies widely used in RI., particularly in methods such as policy gradients [SMSM00 HZALI8 SWD+ 17 SLM 17] and actor-critic algorithms [KT99]. Their effectiveness in exploration and smooth parameterization makes softmax a natural choice in these settings, Let us first review the definition of the well-known softmax policies.
Definition 3.4 (Softmax Policy Set II= Let ø' S x A + Red be feature vector with dimension d' E N. For any h E [M] and 0' E Rdd,, let ma Sh. A(A) be defined as follows:
(sn.aa))
Ti To (al(s))
Eis e (0. Ash E Sh-
Here, represents the total number of actions available in state Su. Sh. The policy Tg. (sh) defines a probability distribution over the actions, which updated as 6' changes. Note that we use the softmax without a temperature parameter. The softmax policy set, induced by any I' E TRdd" is defined
Iam == { 10' E RR
(6)
Following the format of the complexity problem GLINEAR-K-RL here we define our second com- plexity problem, termed SLINEAR-S-RL, which has the same objective as GLINEAR-ss but under the softmax policy set IT = IT In the complexity problem SLINEAR-K-RL, "s" stands for softmax. As special instance of SLINFAR-K-RI, we define the two-action version of the SLINEAR-K -EEEARR--RLL problem as S-I
3.2 Main Results: Hardness of Solving GLINEAR-K-RL and SLINEAR-
We show that solving the complexity problems GLINEAR-s-RL and SLINEAR-R-RR RL in computa- tional efficient way is impossible. The formal result under TT is given in Theorem 3.1 below.
Theorem 3.1 (NP-Hardness of GLINEAR-K-RLI. Solving the GLINEAR-R-RL problem for 0.05 is NP-hard. More specifically, there exists polynomial-time algorithm (in terms of the parameters (d, d', H)) to compute an e-optimal policy for the GLINEAR-KR RI. problem, unless P NP.
Theorem 3.1 demonstrates that achieving c-optimality for small values of in GLINEAR ---RR- computationally intractable. Notably, Theorem 3. reveals that under specified greedy policy set (Definition 3.3), the results diverge from those achievable the computationally efficient -"- realizability setting. On the other hand, Theorem 3.1 suggests that even with expanded policy set, existing computational hardness results for the q realizability setting remain unbroken. The main idea of the proof is to reduce an NP-hard problem to GLINEAR-x-RE in polynomial time. We provide a full proof of Theorem 3.1 in the next section.
As our second contribution to the hardness result, we leverage the randomized exponential time hypothesis (Definition 2.1] derive a computational lower bound for solving the SLINEAR-2-RR problem. In the softmax policy set regime, algorithms that interact with the MDP inherently involve internal randomness. Therefore, standard NP-hardness result insufficient, as only rules out polynomial-tine deterministic algorithms and does not capture the limitations of randomized methods. To address this gap, we strengthen our hardness result under the more stringent computational assumption of rETH, which goes beyond the classical NP / P conjecture. Our main theorem regarding the hardness of the SLINEAR-2-RL problem is stated below.
Theorem 3.2 (Hardness under 11 Under rETH, there exist some small constant eo such that for any < ED, no randomized algorithm can solve the SLINEAR-K-RE problem in time 4t
(o( exp
1 with error probability To where denotes the dimension of the partial realizability feature vector é.
(polylogiaa)
Theorem 3.2 establishes the computational hardness achieving an e-optimal policy under partial realizability of the softmax policy class 11 It worth noting that, although 1Iº C. I1 holds with
5

---

high probability, the hardness result for GLINEAR-X-RL relies solely on the standard assumption that NP * P. whereas the stronger result for SLINEAR-K- RL requires the more stringent randomized Exponential Time Hypothesis (rETH). An additional insight from Theorems 3.1 and 3.2 is that both GLINFAR----L. and SL.NEAR----R RL. are NP-hard, revealing a subtle paradox: even when the policy class is infinite and linearly realizable, learning under partial - rraaelizabiilty remains computationally intractable.
4 Proof Sketch of Theorem 3.1
In this section, we provide high-level sketch of the proof of Theorem 3.1 outlining the core techniques and ideas used establish the hardness result. The proof consists which we describe at conceptual level. Since the techniques developed for GLINEAR-2 2-RL readily extend to the SLINEAR- 2-RL setting with only minor modifications, we defer the full proof of the hardness result under softmax policies to Appendix E
main components,
4.1 An Overview of Our Proof
known that reduction procedures are essential for establishing computational lower bounds. Specifically, to prove that a problem L1 is NP-hard, we reduce known NP-hard problem L2 L1. In this context, we use the decision version of the MAX-3SAT problem, referred to as 6-MAX-3SAT. The formal definition of MAX-3SAT is given as follows:
Definition 4.1 (MAX-3SAT). Given a 3-CNF Boolean formula ip with n variables, denoted by the set X = {x1...., Inh and k clauses, denoted by the set C {ci, C2...., h. the MAX-3SAT problem is to find an assignment that satisfies the maximum number of clauses ip.
Let Kassign
f0, 1)" denote the set of all possible assignments to the variables in X' (x1, In Each element x E Kassign represents an assignment where x; E {0, gives the truth value of x, for Kassign: let (x) and Classe (2) denote the set of clauses that are satisfied
i= 1....., n. For any and unsatisfied, respectively. Clearly, Crrue (x:] + |Cratee (x:) = [C] holds for all x E Kassign- The goal of MAX-3SAT AT is find assignment x E X' such that |Care (c) is maximized. We also define the decision version of MAX-3SAT as follows:
Definition 4.2 (6-MAX-3SATY) Given a MAX-3SAT problem with n. variables, denoted by the set X (I,,...,3a) 5-MAX-3SAT is defined as the following decision problem: output "Yes" if we can find an assignment x E Xassiga such that [aom clauses are satisfied; output "No" otherwise.
2 1 8, i.e., at least 1 - fraction of the
The following lemma shows that for any 8 < 3. solving 6-MAX-3SA is NP-hard.
Lemma 4.1 (NP-hardness of 6-MAX-3SAT (HOI). is NP-hard to approximate the MAX-3SAT problem within a factor of Specifically, unless P NP, no polynomial-time time algorithm can guarantee that more than of the maximum number of satisfiable clauses are satisfied for any given MAX-3SAT formula.
The key idea of our proof is to reduce the 5-MAX-3S3 AT problem to GLINEAR-2-RR. Through this reduction process, we show that solution to GLINEAR-2-RL RL can effectively solve 5-MAX-3SAT, indicating that the GLINEAR- 2--R problem is at least as hard as 5-MAX-3SAT for some ó < 5. In the subsequent sections, our proof involves a two-action version of the GLINEAR-K: GLINEAR-2-1 2- and shows that the GLINEAR- 2-R is ha-hard. More specifically, we denote the learner interacting with GLINEAR-2-RD RL as algorithm ARt. We aim to design ASAT algorithm- which interacts with 8- --MA-33ST derived from Agt. an algorithm that interacts with a properly designed MDP M. derived from the 6-MAX-3SAY instance yp. Following this idea, complete the proof of Theorem 3.1 by showing the following two steps:
problem,
Step-1: 1: Polynomial construction of Mg. We show that it is possible to design an MDP instance M
(with the given attributes GLINEAR-22RIA from a given 5-MAX-3SA4 AT instance yp in polynomial time. This requires the polynomial-time construction of the partial realizability features and weight vectors, along with the polynomial-tima construction of parametric policies. These steps form the first part of the proof, which is outlined in Section

---

Step-2: Algorithmic connection between ASAY and AKL. Recall that the learner interacting with GLINEAR- RLL using algorithm Art. and the algorithm solving 1-MAX-3SAT denoted as ASAT- We show that if ARI. succeeds on Mp. then Asar can be algorithmically derived from An. to solve the 5-MAX-3S AT instance &p with comparable efficacy. Specifically, we show that if the 8-MAX-3SA instance yp (1 8 + 2e) -satiffbiee for some e S 5. and algorithm ARt returns an e-optimal policy in solving the MDP instance M.g then following the policy for setting the value of variables in our yp, we can satisfy least 1 fraction of clauses in the 5-MAX-3SAV instance yp, leading to contradiction and completing the hardness proof.
In the next section, present the details of Step-1, the key to our reduction lies in the successful polynomial-time construction of the MDP instance Ma. The details of Step-2 are deferred to Appendix [
4.2 An In-depth Look at 11 Polynomial Construction of M,
As outlined in Section 4.1 we must polynomially transform given 6-MAX-3SAA instance y with the attributes specified in Section[4.1 into a MDP instance that encapsulates the structural properties of the GLINEAR-2-RD 2-RL problem. We assume the 6-MAX-3SAT instance has n variables and, without loss of generality, that the variables first appear in clauses in the order (I), (2, Z.n).
4.2.1 Design of the MDP Structure
We first formalize the structural design of the MDP instance derived from the 6 ensuring the attributes of the GLINEAR- 2- problem are embedded within the MDP.
problem,
States, Actions, and Transitions. Each state is represented the initial state given by $1 = -.,
n-tuple of -1, O. and 1, starting with 1). For any state Sh E Sh. we can take two possible actions ag = {0, J.. namely, the action set of the MDP is A {0, 1}. Once action an is taken, the MDP will transit to the new state 54-+1, where 8 mirrors the current state 8n for all the elements except that the fitth element will be changed from 1 to on For example, if we take action d1 0 at stage h = 1, the next state will be 81 = (0, -
1). In general, for any h E [H]. the state sn 1), where {2; [vie[h- denote the variables of the MAX-3SAT problem that have been assigned based on the actions taken in the first h - 1 stages. Therefore, the transition dynamics in 1ELLNEERR--R-- are deterministic. Namely, starting from any state 8 = (I1, 1, -1
can be represented as 8, (I1,- Ih-1- -1,
1) E Sn, selecting an action an E A will lead to a deterministic transition to the next state 81+1, defined as follows:
Pr[sp+1 = (I), ... Th 1. 0, - ....,, - 1) S/: Og = 0] = 1,
Pr[s (z,, 1h- 1, - ... -1) -1)1s2 ar = 1] = 1.
Note that, based on the structure of the action set A and the state space S, our MDP has a binary tree structure with 2 states.
Terminal States. As mentioned earlier, GLINEAR-K- RL is an episodic problem, and we are in a finite horizon setting. Let Sμ denote the set of terminal states located at the final stage H = + 1. Once one of these states is reached, the episode concludes. Note that for any state 84 E SH. all the n elements are assigned to be 0 or 1, depending on the actions a1," -1
Rewards. The reward of the MDP is zero at all stages except the final stage h H. For any final state ви E SH, the reward is defined as the ratio of the satisfied clauses to the total number of clauses. Namely, the reward R(s)) defined as
(ex)) CI
(#x)l
if = H. otherwise,
R(sh)
where [C] denotes the cardinality of the set of all the clauses in the 5-MAX-3SAT problem yo and Creee (SH) denotes the set of satisfied clauses in y when the variables in an element-wise manner to be the value of the final state sH, i.e., I = s To better illustrate our MDP design, we provide an example in Figure 4.2. with additional details presented in Example 4. below.
(I1, .nn) are assigned
Example 4.1. To better illustrate the constructed MDP, we give an example based Fig. 4.2.1 Suppose that we are given a MAX-3SAT problem ip as follows:
ip: (21 V 22 V xz) A (क) 22 V Zz).
7

---

h =
(1,1111)
False
True
h
h=
(0.-1.-1)
(1-11-1)
False
True
False
True
1=
(0,0,-1)
(0.1,-1)
(1,0,-1)
(1.1.1)
False
True
False
True
False
True
False
True
(0.0.))
(L...))
(0.1.)
(0.1.))
(1.00)
(L.O.))
(1.10)
(LLII)
Figure 4.2.1: Given MAX-3SAT problem y (I) V2 v3) A (क) V V &3) with n 3 variables, the constructed MDP consists of 15 states, each represented as n-tuple of -1, 0, and 1. The initial state defined as (-1, 1, -1) (i.e., the root of the tree). Actions are either "True" or "False," and the total horizon is H = n + 1 = 4. Starting from the initial state (-1, -1,- 1) at step h = 1, if the action "False" is taken (i.c., d1 = 0), the first element of the next state is set to 0, resulting in the state (0, 10.-1-11 at step h = 2 (the red path). Alternatively, if the action "Truc" is taken (i.c., 01 = 1), the first element of the next state is set to 1, leading to the state (1, -1,,,,- -1,-11 -1) at step h = 2 (the blue path). In the figure, both the red and blue paths yield total reward of 2-
This MAX-3SAR formula is always satisfied except when (æ1, Z2, x2) = (0, 1,0) or (1,0, 1). in these cases the ratio of clauses that can be satisfied is 4. Here, state represent tuple containing variables of our MAX-3SAV problem, and the actions are either "True" (1) or "False" (0). In this instance, we have 8 states as our terminal states (starting from 11,1,1 in 4). Starting from the initial state (-1, -1 1). we have two actions: "True" or "False", which can transit us to the second state denoted as (1. -1, (11,-11 11) or (0, (0,-1,-1). For example, if action "True" is taken in state (-,,-1,-1), transit deterministically to state (1,-1.-1). The final stage here is h 4. To illustrate partial satisfiability in the MAX-3S AT problem instance y,, consider the red path starting from state 1- -1) state (0, 1) and the blue path from state (-1, -1,,,1,- 11) state (1, 0, 1). The total rewards of these two paths are (only one of the clauses is satisfied), while the total reward of all the other paths are 1 (all of the clauses are satisfied).
4.2.2 Design of PSP Feature and Weight Vectors ø' and 0'
To guarantee that our MDP captures the attributes of the GLINEAR-2- 2--L problem, we must ensure that PSP feature vector o' is properly designed, allowing for the construction of well-defined greedy policy sets (Definition 3.3
For any given state-action pair (sh, a) E Sb x A, e Rdd, where d' = n, be defined as follows:
0,0,
if a True,
heth element
Φ (((s =
(8)
0,
if a False,
element
where all the elements of o' (sh, a) are except the f-thh one, which is set to (when a = "Truee") or -1 (when a "False"). Recall that the action set A {0, 1}. where 0 corresponds to action "False". and 1 corresponds to action "True", For any 3h. if T (3%) = 1, then the action a = 1 is selected as the result of the maximization:
arg max (a a). aEA
(9)
In this case, it suffices to set the h-th element of the vector 6' as an arbitrary positive number. In contrast, if -1 needs to be selected the result of the above argmax, we can set the hith element of the vector 0' as arbitrary negative number. Without loss of generality, assume that 0' Rd

---

consists only of elements in (-1,1}. Note that for each given H', the greedy actions selected in all the states in S₁ are the same, depending on whether the h-th entry of 6 being 1 or-
4.2.3 Design of partial realizability Feature and Weight Vectors ø and 0
As demonstrated in the complexity problem GLINEAR-R- RL and Definition 3.1 the given partial realizability feature vector & is utilized for the purpose of holding exact linear realizability under a given greedy policy set 119. In this section, we show how to design o. 0, E I such that the linear combination of & and 0,, for any (s),a,) (4) E S₁ x A under any greedy policy E II for all h E [H). Formally, we state the linear realizabilitty results as follows:
action-value function 9% (sh, a4) can be represented
Proposition 4.1. Given exist O6 Sh. 0) E Ted and fr E R.d such that:
policy set IT,, for any state sn E Sn. On A, and π E TT9, there
9 (sh, an) = (Ø(sh, an), 0n), Vh E [M].
(10)
Proof. We prove the above proposition in three steps. First, we design o(sp. a) to track the number of satisfied clauses 5-MAX-3SAT up to stage h, while also keeping record of the remaining unsatisfied clauses after each variable assignment. Next, we construct the partial realizability weight vector 0g to track the policy ı from stage h + onward. We then show by induction that the linear realization described in Proposition 4.1 hhodd.. See Appendix Cf for the details.
Before concluding this section, we present two remarks: one on the polynomial -otoomil---meeeeee time construction of the MDP parameters in Mg. and another on the conditions required for establishing -a-hardness of partial o- -raaliizability under a general policy set II.
Remark 4.1 (Polynomial-Timm Construction). The computationally intensive step in our reduction involves designing the feature vectors & and O, which can be done in O time due to their dependence the size of Cinal- Other components such as Φ', 0', and reward vectors require only ((n) time. Thus, the entire reduction remains within polynomial time, satisfying the complexity- theoretic requirements of the NP-hardness proof. A step-by-step example is provided in Appendix [
Remark 4.2 (General Conditions for NP-hardness under Partial q" "f-realizability). Our proof frame- work naturally extends to other policy classes. For any NP-hard decision problem & with input size 193] and any policy set II C A of size S((S)), learning an e-optimal policy under partial qt -realiizability is NP-hard, provided that (i) each policy x E can be parameterized in polynomial time in (.) (ii) the feature vectors & and I are constructible in polynomial time, and (iii) solving B reduces to finding an c-optimal policy with respect II. These conditions highlight the central role of efficient policy representation in the reduction.
5 Conclusion and Future Work
In this paper, we introduced a novel linear realizability setting in reinforcement learning (RL), termed partial g" q"-realizability, which bridges the gap between the q"- and q" -"-realizability paradigms. The central contribution of this work the establishment of computational hardness results for RL under partial qf -r-raliizability for both greedy (i.e., argmax) and softmax policy sets. These results extend prior work on computational hardness in q- and v" rrealizzable settings [KL], showing that enlarging the policy class beyond the optimal policy n² does not eliminate the fundamental computational challenges.
A limitation of our current setting is that the feature vectors used for policy parameterization in
constructing the policy class II (i.c., o' and 0¹) differ from the realizability parameters (i.c., é and 9), which are central to the learning process. Extending our proof techniques to accommodate partial qT qe-realizability with unified feature vector (i.e., o' σ) remains a significant challenge and is left for future work. It is also worth noting that our NP-hardness results for RL under partial q" qfarriaizabilltty should not be seen as purely negative. While they reflect worst-case complexity, they also highlight the need for efficient algorithms under extra assumptions, such as structural constraints on policies or features. For instance, combining the agnostic RL objective [JLR with linear function approximation captures practical settings where e-ppimallity is defined relative to a policy class. This connection may offer useful directions for developing sample- or computation-efiin efficcient methods.

---

Acknowledgments
The authors thank Gellért Weisz and Csaba Szepesvári for their helpful discussions throughout this research. Xiaoqi Tan acknowledges support from Alberta Machine Intelligence Institute (Amii), Alberta Major Innovation Fund, and NSERC Discovery Grant RGPIN 2022-03646
References
[AB09] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
[Ber09] Dimitri P. Bertsekas. Neuro- Neuro-dynamic progronmiiggNuuu-DDDnniii Programming, pages 2555-2560 Springer US, Boston, MA, 2009.
[BT%6] Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1st edition, 1996.
[Coo71] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium Theory of Computing, STOC '71, page 151-158, New York, NY, USA, 1971. Association for Computing Machinery.
[DHM*14] Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Expo- nential time complexity of the permanent and the tutte polynomial. ACM Transactions on Algoritiums, 10(4):1-32, August 2014.
[DKWY20] Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is good representa- tion sufficient for sample efficient reinforcement learning?, 2020.
[DLMW20] Simon S. Du, Jason D. Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic q-learning with function approximation in deterministic systems: Tight bounds approximation error and sample complexity, 2020.
[DLWZ19] Simon S. Du, Yuping Luo, Ruosong Wang, and Hanrui Zhang. Provably efficient g-learning with function approximation via distribution shift error checking oracle, 2019.
[H11] Johan Hästad. Some optimal inapproximability results. J. ACM, 48(())798-8855) July 2001.
[HZAL18] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor, 2018.
[JLR+233 Zeyu Jia, Gene Li, Alexander Rakhlin, Ayush Sekhari, and Nathan Srebro. When is agnostic reinforcement learning statistically tractable?, 2023.
[Kak03] Sham M. Kakade. On the sample complexity of reinforcement learning. 2003.
[3] Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesvári, and Gellért Weisz. Exponential hardness of reinforcement learning with linear function approximation, 2023.
[KLMM22] Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computational- statistical gaps reinforcement learning, 2022.
[KT99] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.
[Lev73] Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission. 9(3), 1973.
[LSSW0] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with a generative model, 2020.
10

---

[MOS* 23] Michaël Mathieu, Sherjil Ozair, Srivatsan Srinivasan, Caglar Gulcehre, Shangtong Zhang, Ray Jiang, Tom Le Paine, Richard Powell, Konrad Zoina, Julian Schrit- twieser, David Choi, Petko Georgiev, Daniel Toyama, Aja Huang, Roman Ring, Igor Babuschkin, Timo Ewalds, Mahyar Bordbar, Sarah Henderson, Sergio Gómez Col- menarejo, Aäron van den Oord, Wojeiech Marian Czarnecki, Nando de Freitas, and Oriol Vinyals. Alphastar unplugged: Large-scale offline reinforcement learning, 2023.
[Put94] Martin Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Pro- gramming. John Wiley & Sons, Inc., USA, 1st edition, 1994.
[SAH*20] 20) Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):604-00) December 2020.
[SB18] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[SHM* 16] David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvame Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:489-4445 2016.
[SHS+17] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanetot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm, 2017.
[7] John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region policy optimization, 2017.
[SMSM00] R. S. Sutton, D. A. McAllester, S. Singh, and Y. Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12, 2000.
[SWD+ 17] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms,, 2017.
[SWW+19] Aaron Sidford, Mengdi Wang, Xian Wu, Lin F. Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with generative model, 2019.
[TVR97] J.N. Tsitsiklis and B. Van Roy. An analysis of temporal-diffcrence learning with function approximation. IEEE Transactions Automatic Control, 42(5):674-690, 1997.
[WAS21] Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions, 2021.
[WGKS22] Gellért Weisz, András György, Tadashi Kozuno, and Csaba Szepesvári. Confident approximate policy iteration for efficient local planning in rrereaiizalle mdps, 2022.
[WR16] Zheng Wen and Benjamin Van Roy. Efficient reinforcement learning in deterministic systems with value function generalization, 2016.
[WWK21] Yuanhao Wang. Ruosong Wang, and Sham M. Kakade. An exponential lower bound for linearly-realizablee mdps with constant suboptimality gap, 2021.
[YHAY+22] Dong Yin, Botao Hao, Yasin Abhasi-Yadkori,, Nevena Lazić, and Csaba Szepesvári. Efficient local planning with linear function approximation, 2022.
[YW19] Lin F. Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features, 2019.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We introduce novel reinforcement learning framework called partial q"- realizability and establish its computational hardness under both greedy and softmax policy sets, as formalized in Theorems 3.1 and 3.2] The paper also includes complete proofs for each of these results, accurately reflecting the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the conclusion, we acknowledge a key limitation of our work: the feature vector used for defining the policy class II (i.e., o') differs from those used in the realizability condition (i.e., (). Extending our hardness results the setting where single feature vector is used (i.e., ø' = Φ) remains an open and technically challenging direction. In this setting, the reduction must enforce realizability and construct the policy set within unified representation, which complicates the initial step of the proof concerning the polynomial-tine construction the MDP instance.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
12

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: For each theoretical result, provide clear set of assumptions and include both proof sketches and complete proofs. A high-level proof sketch is presented for our first main result (Theorem 3.1 the computational hardness under the greedy policy set TTo, This sketch also partially serves as the foundation for the second result (Theorem 3.2) concerning the softmax policy set IT The full technical details, including all supporting lemmas and formal arguments, are provided in the Appendix. In particular, the complete proof of Theorem 3.2 which establishes the computational hardness of partial ge-realizability under softmax policies, is included in full.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
All assumptions should be clearly stated or referenced
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper is purely theoretical and does not include any experimental results. The main contributions consist of formal definitions, complexity-theoren results, and complete proofs, all of which are fully disclosed the paper and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
13

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing verifying the results. 5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This paper is purely theoretical and does not include any experiments, datasets, code. The contributions consist of complexity-theoree results and formal proofs, all of which are fully described the main text and appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (htttss:/niips. cc/
public/ cellic/guiiee guides//////eeee Souiids/Cooooe CCodeSumdeiimccccccccee ssi cessonnollcco
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https? //nips. cc/ httpp/bbllccgcceeeeeeee / Cwwp:iddeeeeeeeuueueeeeee Chae//ooeSuubba wwr.iissssooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theoretical paper with no experimental setup. The contributions are formal complexity results and proofs, which are fully detailed in the main text and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
14

---

7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is theoretical work with experimental results. Therefore, statistical significance reporting is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This work purely theoretical and does not include any experiments or computational benchmarks requiring resource specification.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
e/Eth caGui de nes
Answer: [Yes]
Justification:
This work is entirely theoretical and does not involve human subjects, sensitive data, or applications with foresecable misuse. The research adheres fully to the NeurIPS Code of Ethics.
Guidelines:
15

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Our paper presents NP-hardness results for reinforcement learning under partial q" d"rrealizability with greedy and softmax policies. While these results are negative in the worst case, they serve constructive purpose by identifying the computational boundaries of the problem. Crucially, they motivate the study of more tractable variants under ** additional assumptions such structural constraints the policy class value function representation. This opens the door to the design of heuristic and approximation algorithms tailored to such restricted settings. Furthermore, our work highlights connections to agnostic RL under linear function approximation [JLR offering a concrete path toward practical algorithm development where e-opimmality is defined with respect policy class. These insights aim to guide the community toward feasible algorithmic strategies within theoretically justified regimes.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is theoretical and does not involve the release of any data, models, or systems with potential for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
16

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper entirely theoretical and does not use any external assets such as code, data, or models.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, ppaperswi twcoooo com / dat aset s has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not introduce or release any new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
17

---

The paper does not include any crowdsourcing experiments or research involving human subjects.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does involve human subjects or study participants and therefore does not require IRB or equivalent approval.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: The core methods of the research do not involve LLMSs as important or non-standard component.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy
httprripss...ccoeeeennneeeee///e /202/ LLM) for what should should not be described.
18

---

A Extended Discussion of Related Work
Under the linear function approximation framework, there are two well-defined problem settings in the literature: the q- rrealizzabyly and q q"-realizability settings. Their definitions are provided below.
Definition A.1 (q" RRelizable MDP). An MDP M is called q" rrealizblle if there exists 8n E R for any h E [H] such that for optimal policy x², (s, a) = (Ø(s, a), Bn) holds for all s E and a E A.
Definition A.2 (q" -Realizable MDP). An MDP M is called q" -realizzall if there exists 0, E R for any E [H] such that qh (8, a) = (é(ss a), 0n)) holds for all n, & and a E A.
For clarity, in Table q² -erralliaability settings.
T we summarize the common assumptions used in both the q" q"-realizability and
Assumptions
Description
Exact realizabiliity !
th a) = (0(8, a), 0,) + 3, where 5 0
Approximate realizability 2
(1 (Ø(s.a) a), 0n) + 3, where 5 0
Access model (
Generative model (M2) ) or online access (Moo)
Minimum suboptimality gap
(s(saa) = V (g.0 2
Low Variance Condition 5
(=- V (+) S no L..E-_.IIVVV
(s)i))
DSEC Oracle Access 6
Tests if predictor generalizes across distributions over all (*.a) pairs
Action set size 7
For exponential variation (exp(d)
Transition Dynamics
For deterministic variation (Pdet)
Bounded feature vector
[ S for all (s.a) E (8 x A)
Estimate Oracle Access 10
Computes approximate value function for any state-action pair
Spanning feature vectors
Matrix & Rexd spans Rd with unique rows
Feature vector hypercontractivity (12)
Anti-concentration of distribution over state-action pairs
List of common assumptions used in related work regarding the q"- and ge -ralliizzayylytyy settings. Note that here 3 is linear approximation error; Mgg and M. represent the generative model and online access model, respectively. In addition, ÇA. (s, a) denotes the suboptimality gap for each (s, a) S A at stage h. Each of the assumptions comes with a number in front of it, and we use them to indicate the main problem setting of the related work provided in the following tables.
Table 1:
We begin by reviewing results for the q re-realizability setting. Research in this category is generally divided between hardness analyses and upper bound guarantees. Exponential lower bounds under specific conditions are reported by [WAS2T], [WWK2T], and (DKWY20), as summarized in Table These results rely on assumptions about the structural properties of the MDP (e.g., number of actions, variance constraints, and feature vector structure) and the type of egent-environment interaction (e.g., online, local, or random access). Despite some variations-such as low variance conditions or a minimum suboptimality gap under the online setting the exponential lower bound remains robust. Nonetheless, polynomial-time algorithms have been proposed under additional assumptions, as detailed by [WW22T], [ (DKWY20), [LWZI99, and 2DLMW2)
There is also growing body of work focused on the g -errealizabilliyy setting. For example, (DWY220 establishes exponential lower bound in the horizon H. However, with additional assump- as bounded feature vectors, access to generative models, estimation oracles, or informa-
tive state-action pairs (core set access) as in [LSW20], [YHAY+ 22). and [WGKS22] polynomial- time algorithms have been developed. These assumptions are summarized in Table
Assumptions
Lower bound
Upper bound
Related works
Q. T (exp(d) (d)) and ① (Mg)
min(e Rid) (
LSVI with (
WAS21
@. ④ A (M.). (22 ( (Paet)
20, constant
poly(') ()) queries for e-optimal policy
WWK21
poly(Eluder Dimension) or polyidim, (Q))
WR16
@ @ (Puz)
poly(dim,) with error
sap.
DLMW7 20
am.
4 ① (M,)).
Exponential
polytd, H, p.
log 3), pt gap, 8: failure prob.
20
4 ()
poly(3 ())
DL
Table 2: Sample complexity results for the g" realiizaabyly setting.
19

---

Assumptions
Lower bound
Upper bound
Related works
2. ① (M₂)
Exponential in H for D #)
DKWY20
2. 3
(Mg).
122
with accuracy
LSW20)
2. 2.0 (My). (10
with accuracy
WGKS22
Table 3: The lower and upper bounds in the q -erraiizabyyl setting under various assumptions. Under the generative model, the statistical hardness is exponential in horizon with approximation error [DKWY20]. Also, the upper bounds, we can see the dependency on d and 2a where d is the size of the feature vector and is an approximation error.
Main Contribution
Lower Bound
Related Works
pulsi-polynomial in size of feature vector,
Unique-3-SAT <p Linear-3-RL
lagi4) dd
KLLM22
Iig higto)
Exponential,
(c.b)-Gap3-SAT <, Linear-3-RL
exp Ö min (at H+
KLLL 23
Table 4: Computational hardness results under the q², v" rea-riaiizability setting. Note that A <p B implies polynomial reduction from problem A to problem B.
Despite these developments. efficient computation remains fundamental challenge. Recent studies by [KLMM22 and [KLL*23] emphasize the gap between statistical and computational efficiency under optimal value function realizability, suggesting that NP-hardness may still arise even when sample efficiency is achievable.
Under the q", reallizzbbil assumption, important studies investigate computational hard- ness, summarized in Table In [2LLM22), the authors establish a quasi-polynomial lower bound
on the feature dimension d, specifically (Pinglostaa) ) under the randomized exponential time hy- pothesis (rETH). However, this bound is not tight, as the reduction technique used may leak in- formation about the optimal action after a quasi-polynomia. number of interactions, resulting in an imprecise lower bound. In contrast, [3] presents stronger exponential lower bound of exp(O (min(d)/4 H!!4))), where H denotes the horizon and d is the feature dimension. This result demonstrates that the computational hardness of learning near-optimal policies under q"- and o" o"-rrelizabilltty is greater than previously established. By reducing from variant of 3-SAT, the authors derive an exponential hardness result that provides a tighter complexity bound.
Both KLLM22) and [ employ the Randomized Exponential Time Hypothesis (rETH) to establish computational lower bounds within the q², u" r'-riiaizabilliyy framework. The core idea of their proofs is construct MDP instance from a given Unique-3-SAT instance (a variant of 3-SAT with a unique satisfying assignment), while preserving the structural features relevant to their RL setting. We now describe the general instance design framework used in [KL as variations of this approach are useful for our reduction in the partial geerealizability setting in Section 3 According to [LLLM22,, when designing MDP instance M, from a Unique-3-SAT formula yp each MDP state represents à candidate assignment, encoded as a tuple of variable values. At each state, the agent is presented with of unsatisfied clauses and can choose flip variables-ias i.e., to assign them "True" or "False." The agent's objective is to take actions that reduce the Hamming distance to the unique satisfying assignment. The reward structure is randomized in way that encourages minimizing this distance, thereby aligning the agent's 's learning objective with the solution to the original SAT instance. The reward is given the last stage of the MDP or when the satisfying assignment is found, and it relies on the Bernoulli distribution. In this work, due to the structure of the learned policy, a deterministic reduction is also applied argue the hardness result.
B An Example of the MDP Instance Ms
In this section, we illustrate the process of designing the MDP instance MM through an example based on the 6-MAX-3SAY instance presented in Example 4.1 That example demonstrates how the components of the MDP are constructed from a given 8-MAx-3S. ASA instance. However, function approximation has not yet been integrated into the framework. As outlined in Sections 4.2.2 and 4.2.3
20

---

the design principles for the PSP and partial realizability vectors have already been established. To improve clarity, we now explicitly construct these parameters for the specific case described in Example [.1
Recall that the complexity problem is given by o = (a1 V 22 V x3) A (3n V V Ta). which involves three variables and two clauses. Figure 4.2.] depicts the transformation of this 6-MAX-38AF AT instance into an MDP instance. However, the attributes required define our GLINEAR-2-RR problem instance are not yet fully specified, as the realizability parameters and a well-defined policy set remain to be constructed. As the first step, we now design greedy policy set for this example using the feature representation. o'.
PSP Parameters Design. As discussed in Section 4.2.2 we design the matrix θ E IRd x2" consisting of 2d vectors, where each 0 E E represents a greedy policy. In our construction, we set d' = n. and specifically, d' = 3. Under this setup, the greedy set ensures that the states S, at each stage h share the same greedy action, while allowing greedy actions to be selected independently across different stages. In this example, [I 8, meaning that there are eight PSP weight vectors 0' E R3, each corresponding to a unique combination elements from {-1,
In the MDP structure depicted in Figure 4.2. for the first state, we have:
o' 0((1-1,-1 -1), "True") [1, 0, 0J.
01(11,-1,-1) "False") [1,,0,0]
Recall that we always update the h-th element of d'(s,, an) based on the action as. Therefore, at each stage ht the value of d' (sh,, ap)) remains consistent for all (sh, an) E Sp x A, since it depends solely the stage.
Partial Realizability Parameters Design. We begin by demonstrating the representation of é(s, a) Rd for all state-action pairs in the MDP shown in Figure 4.2.1 and then illustrate how 0g is assigned for any h E [H] to verify Proposition 4.1
As stated in the proof of Proposition 4.1
we have
& + l2 + f3, which implies:
d d=(21) 2n
+ )2)))())
2n
2n
2n + +n+1.
For n = 3, this yields = 27. To facilitate analysis, consider a specific state at the stage = namely (1, 1, 1,,-1,1),, -1), 6, we focus on Yú and b, omitting the constant 1 for simplicity. In this state, the first variable I is set to 1, while the remaining variables (I2 and vr)) remain undecided. Assume without loss of generality that the greedy policy TT selects the action "True" for all states. From the previous section, this corresponds to QT = 1,]
which lies along the blue path in Figure 4.2.1 When referring to the values of
[C]
We now examine how the feature vector di(1, (1,, "False") is determined. In this example, b2 represents the number of satisfied clauses after setting x1 = 1. Since the first clause of yp is satisfied, we have by 1. Following the structure in the proof of Proposition 4.1
compute Yz. After taking the action "False" in state (1, 1, -1), T2 is set to O in the formula yp Consequently. the remaining undecided clause is 142 {ixh }. The corresponding entry for 33 in Y2 is set to since it appears once, while all other entries in Y2 are set to 0.
Next, we specify the value of 0,, ensure partial linear realizability. Given that and 22 have been determined, the component of fl, corresponding to by is set to For the component corresponding to the clause ē3, have f2 f2())) = 0, which maintains consistency with policy æ. Thus, the dot product Φ([1, 11, -1), "False") ". 0% evaluates to:
[C] (b2 1+1 1
(LL, -1, 1),, "Falsc") 0%
This matches the value of qº' ((1, -1, 11,1,11,1110 11, "False"), thereby validating the realizability condition stated in Proposition 4.1
C Remaining Proof of Proposition 4.1
Given a 1.MAX-3SAA AT instance yp with n variables, let Crotal denote the set of valid clauses that can be formed using the given 6-MAx-3SAY variables, excluding trivial clauses-i.c i.c. those of the
21

---

form (z; V F.) or (z, V &, V 22), which are always satisfied (evaluating to 1 for any assignment). In
particular, we assume w.l.o.g. that the clauses in Crotl are organized in the following order:
Crotal =
Ccatal
totul
Lotull
where of denotes the i-th j j-CNF clause (each clause has exactly j variables) and Ej denotes the total number of valid j-CNF clauses. Note that E = (2r), f2 (22) n1, and f3 (3;) 2n + 2n.
Partial Realizability Feature Vector G. Recall that for any state S/ = (4 (Z1.-... 1h-1: 1,
at the beginning of stage h E [H] (prior to taking action ax)). the first h h-1 variables have been assigned values of either 0 or 1, based on actions taken before stage h. These are referred to as the assigned variables X1:h-1 (I1, #b-1). while the remaining + +1 1 h elements, denoted as Xh.n = (En, Ir), remain unassigned, hence termed unassigned variables. For any state-action pair 5h E Sh and an E A. let Un represent the list of undecided clauses in ip after excluding the first assigned variables (i.e., Ii through JT.). Therefore, Ud includes all clauses initially given by the instance so. where Ug = C C Croial. Upon transitioning to a new state 8h+1 E Sh+1, the set Uh, is updated. leading to two possible events in Un First, since the variable Iy is determined at this stage, certain undecided clauses may become satisfied and are consequently removed from Uh+11 Second, some clauses may be modified, reducing in size based on the assigned value of æg. For better illustration of U₁, 's construction, let us look at the following example:
8p: : (#) V 82) A (æ) V 34 V 25) A (I2 V &4 V 2T) A (ra V Øs V x7). We have Uo ( V 22), (I)
V F. V us), (I2 V T4 V as), (1g V is V x7)}. At the end of stage 2, suppose I1 and T2 0. In this case, the first clause (ă1 82) can be decided, while the remaining three clauses stay undecided. However, the undecided clauses (x1 V ΣΔ V xx) and (xg VI, Vxs) shrink and simplify to (Σ, V 2s). Thus, at the end of stage h 2. the list of (simplified) undecided clauses in & 242 = [(T4 V æz), (T4 V Is), (Iz V I6 V x7)}, where the clause (æ4 V xs) repeats twice. Using the above concepts, we can now explain how the partial realizability feature vector @ is constructed. For any h E [H]. let Y₁ be a vector of natural numbers, defined as follows:
(1) Yn = yh
(I) yh.t 1......... Fh.f2 Di.1 Ni.fa
(2)
(3)
(3)
where yh. denotes the number of times c( repeats in Un It should be noted that v 0 occurs if
the corresponding clause c(5) does not appear in the 6-MAX-3SAT instance y or has been decided (either True or False) at the end of stage h. For any 8h E Sn and a E A, we define the partial realizability feature vector & as follows:
1 [Ci
(5hh a)
[b.. Yn).
Vh [H],
(1))
where bn = [Crue (sn)l. denoting the number of satisfied clauses in at the end of stage h (i.c.. after assigning variable n.)). Based on the definition of lh, we have by I |C| [Mal indicating that the number of satisfied clauses is always upper bounded by the total number of clauses that have been decided at the end of stage h. We further construct partially realizable weight vector 0, such that the realizability condition stated in Proposition 4.1 is satisfied.
Partial Realizability Weight Vector On. We now demonstrate the existence of 02 such that the linear realizability condition 0f (g) (0(sn) an), 0z) holds. Let Sn RR - {0,1) be defined
fa (x') f 0, 00 otherwise,
(12)
where 0% denotes the h-th element of 0', For any state 3₁. with unassigned elements (i.e., any state with at least one element being I),, we define the virtual look-ahead state šy, as follows:
å.. (II, Th- 1, Lb. 2n),
(13)
where d, = (O') holds for all j = h...., n. Thus, the look-ahead state &n mirrors the current state 8y, for the first h elements and matches the final state sh (i.c., the terminal state at stage H by
22

---

following policy π in state $h+1 onwards) for the last H h elements (hence, the term ).
Given S E Sj, and an E A. we know that the next state is S (Z).-
2h Oh:
and the first h variables (i.e., X1th = (I1, ,,,,, will be assigned.
Let Mt be defined vector of O's and I's as follows:
M₁- = h, ... M,, M
h
(2)
m h,1
(3)
where m 0 indicates that the clause e consists of least one assigned variable from X1:h- For any clause c, E c(d) that depends solely on the unassigned variables X1+1=m = (Ii+1, (n) (2) (i.e. the clause is constructed only based unassigned variables), let m represent its satisfiability result, assuming that X/+1:n follows the values of the look-ahead state šn, (i.e., I, By for all
j = h + 1, , .H. Thus, h, = 0 may occur in any of the following three scenarios: (i) 9 depends only on 1 and can therefore be decided, (ii) ( is mixture of X1:h and X or (iii) ( depends solely on X with a satisfiability result of False based on the look-ahead state. We emphasize that all non-zero elements in Mn (i.e., entries of 1 I's) are independent of s), and az and are determined solely by {ff (7') (ff (vvj=+++++--
Based on the M2, vector, let 6j be defined follows:
% = [.].
4h E [H].
(14)
Given the proposed @ and 0, Proposition 4.1 will follow if qī (sh, an) [C] (bn + Mx)) holds for all E Sh, an E A. and π E I1
Realizability Validation. Here, want verify the linear realizabilityy of designed MDP that
satisfies all the conditions of GLINEAR- 2-.L. Given Φ(*), a) = [C] [b,, Yv. as demonstrated in
Equation 11,, will prove by induction that there exists 0, [1, Ma] described in Equation (14
such that the realizability condition in Proposition 4.1 holds for any h E [H].
Base case /: We first show that realizability holds for any state 8y E S₁ at stage h = H 1. Consider
a specific state - where the number of satisfied clauses after taking action a is denoted by
- If we take any action E A in s8-1, the process transitions to the terminal state H. yielding reward of [Cae(sx)] Observe that the reward received after executing action aи-1 in s equals [C]
1 i.e., Th (8 11-1) 1 After this action, all variables in yp become determined, [eT
implying that -11 = 0. This implies:
(h-1(9H11.HH-1)
(0(sn-1,an-1),
0n
+ b
[C|
1
(0+ bH
[C]
by-1
(15)
[C|
Thus, there exists 0H111 = [Mr-1, 1jT that the realizability holds.
Base case 2: In the first base case, the linear realizability of state - depends solely on the scalar quantity by-1, and we have not yet established how the inner product (Yn, Ma) contributes to the linear realizability condition. To proceed, state, upon taking action aи-2. the system transitions to state - where the agent subsequently follows the greedy policy determined by the look-ahead state 8
now examine realizability for the state s In this
Note that after taking action aи-2, the number of satisfied clauses up to stage H 2 is denoted by by- The set 22 contains the undecided clauses, namely those that do not yet have all their variables determined by assignments Ii through -- Moreover, the greedy action selected in state - depends on the elements of @. Specifically, by substituting the value of the undecided variable - into Un--2 2, we can determine all remaining clauses in the 6-MAX-3SAT instance. This substitution is performed according to the greedy action taken in sH-1, meaning that the value
23

---

of 2 is determined by the greedy policy and assigned as fH-1(6") for each vector 6' in the matrix O. Based on this construction, 22 2 represents the number of clauses that are satisfied from stage H - onward when following the greedy policy æ. Thus, we have:
In H 22 = (2 01-
(YH-2, MH 22 + b2-2)
CC]
(sH)
(16)
C
Induction step: Given the number of satisfied clauses up to stage h (i.e., by. and the weight matrix O, suppose that the linear realizability condition holds for all state-action pairs (st, az) E S; x A at every stage 2 h under any greedy policy II that is, of (s; a4) (o(s,, (t a.), 0t). Our goal is to establish that this linear realizability condition also holds at stage - 1 for all state-action pairs and for any greedy policy E IT9. In other words, we aim prove that:
0 Oh (0( (10(5h1,,hh11) On-1) for any (8h ah-1) 1) E Sh-1 X A.
[()(( Let 22 by b denote Note that Th-1 9h--100-11 = [m and th an) [c| [e|
the difference between the numbers of satisfied clauses until stages h and in s. We prove the induction step as follows under policy ı E II9:
hh 18h 1,
R(sh-1,, ah-1) (sh)
4% (sh; (8)) = (0(sn, x. (sn)),
C ((), bb))
((1%, Mb) + 22) + (bp 22)
C
= [C| ((F,, Mn) + 22) + b1-
(17)
To complete the proof, it suffices to show that (Yn, Ma) + = (Mn-1, This is equivalent to demonstrating that (Y MM-1)) (Yn, Ma) 22 bn b Since we follow the greedy policy from state 8h, the resulting terminal state 8и will be the same whether we begin from 8h-1 or 8 (after taking action 4;-1 and subsequently following TT, as both lie along the same trajectory induced by x. Recall that rewards are only received at the terminal state. Therefore, the cumulative reward from 8h-1 | S must equal that from 8₁ to Sn. This implies (Y,-1- 1, M,, 1) + -b, b, + (Yn, M,). Rearranging terms gives the desired equality, thereby completing the inductive step.
Based the construction of é and 0,, and the fact that the linear realizability condition is satisfied, we complete the proof of Proposition 4.1
D An In-depth Look at Step-2: Algorithmic Connection between ASAT and ARL. under I[9
In this section, we detail the second step of the reduction, which establishes the connection between the algorithms An.. and ASAT in the reduction from d-MAX-3SAT to the GLINEAR-2-RL problem. Let us first note the following definition regarding the satisfiability ratio:
Definition D.1 ((-Saiiffiaiility). A MAX-3SAV instance is Ç-satisfiable if there is an assignment
Kansign such that (Z))())
[C] 2 Ç.
We focus on a specific class of 6--MX-3SSA instances in which there exists an assignment x E Massign A
that satisfies at least (1 - 8 + 2c -ra-traction of all clauses, where < 2/2 and < o < 1, where in our setting 5 TØ This condition aligns with Definition D. and throughout this paper, we set < = - 2e for our 5-MAX-3SAT instances. In this problem class, it is guaranteed that minimum (1 - 8)- --ffacatioon of clauses can be satisfied, ensuring valid instance for the reduction
24

---

procedure. Given 5-MAX-3SAT instance that is (1 - - + -aasisiii,,, we use this decision version of the MAX-3SAT problem prove the NP-hardness of the GLINEAR-2-RL RL problem.
To complete the proof of T'eorrm 3.1 the key idea of our remaining proof is as follows: Given a (1 - 8 2sa-sstife d-MAX-3SAM instance yp, which has maximum satisfiability ratio of [C*I Cj transform it instance of GL.NNARR-2RL. problem denoted as Ma in polynomial time such that if random algorithm ARi. runs Map returns e-optimal policy т where < 3. then following the policy for setting the value of variables in our s, we can satisfy at least - ô fraction of clauses in the given instance (p.
Consider that ARL returns an e-optimal policy и in a designed MDP instance Mp. is easy to verify that for any state 8n St. and for any h [H], v= (sh) R(s (sH-1)) Iee (ل Here, [Crus (5 denotes the number of clauses satisfied when setting variables in 8 6-MAX-3SAT problem following policy æ. Furthermore, we can also denote the value function of the optimal policy x² for any given initial state 81 as follows:
C
C
(51)
(18)
Cl
Since we know that n² E 119 based on our constructed me, we have:
C
max U (81)
2 1 5 26,
(19)
REILO
C
where the inequality is due to the fact that the 1-MAX-3SAY instance is (1 - 6 sattstiif for some e g. Based on the definition e-optimality policy a for a given initial state 81, we have
max xa ($1) 2² (5)) Sc. RETTO
(20)
Thus, we have
|e'
max v (81) -
0z (s1) Se.
(21)
#ell
[e|
Note that a 8 2c)-satiffe instance eP also (1 sattisffee If we want to obtain an
output of "Yes" for 1-MAX-3SAT then we need to have [ 2 11-6 8. This is indeed the case because
(sH)((H) ) 2
C* CC]
2 (1-
8 26) c2
(22)
C
where the first inequality comes from the definition of e-optimality and the second inequality is due the fact that yp is - 8 sat-salee, As result, reduction is completed.
E Proof of Theorem 3.2
We begin by presenting an overview of the proof, outlining the two principal components of the reduction. We then formalize each step in detail and conclude by establishing the correctness of Theorem 3.2
E.1 An Overview of Our Proof
Building on the framework presented in Section 4.1 we adapt the core proof methodology with minor modifications, which we make explicit in this section. To facilitate our reduction, we introduce a new complexity problem, termed 6-MAX-3SAT()), defined as follows:
Definition E.1 (6-MAX-3SATO)) Given MAX-3SAT problem yp with n variables, denoted by the sei X {I1,.... Fn), where each variable x; E X appears in at most clauses, 6-MAX-3S (T
defined as the following decision problem: output "Yes" if there exists an assignment E Xassign
such that (Cme(a)
2 1 - 8, i.e. at least a 1 -8 fraction of the clauses are satisfied; output "No"
[C]
otherwise.
25

---

Note that the hardness result of MAX- 3T mentioned in Lemma 4. still holds in the case that each variable appears in at most b 2 clauses. Thus, by considering ò 0.1 and 3, the 5-MAX-3SATH problem remains NP-hard under the NP & P hhpptthess. More specifically, we have the following lemma showing the hardness of 6-MAX-3SAT(h) under rETH.
1-MAX-3SATH under rETH). UnderrETHe there exists constant b, 6 such that no randomized algorithm can solve 5-MAX-3SAT(h problem with variables in time T exp(o( polylom(n)))
Lemma E.1 (Hardness
)) with ervor probability
Lemma E. establishes that 5-MAX-3SAT(CE is at least as hard as 3-SAT under rETH. The proof largely follows the arguments presented in [H01 AB09]; however, for completeness, we restate it in Appendix
Similar to the hardness proof of GLINEAR- the key to our proof relies on a reduction process hinges on two critical components:
Step-1: Polynomial Construction of Ma. We show that it is possible to design an MDP instance Mep (with the given attributes SIIINA----RLL from given 1.MAX-3SATIO instance yp in polynomial time. This requires the polynomial vectors, along with the polynomial-time construction of parametric policies. These steps form the first part of the proof, which is outlined in Section E.2
construction of the partial realizability features and weight
Step-2: Algorithmic Connection between ASAT and ARL. Recall that the learner interacting with SLINEAR -- using algorithm ARL, and the algorithm solving A-MAX-3SAT(() is denoted as ASAT- We show that if ARi. succeeds on M3 with low error probability, then ASAT can be algorithmically derived from Au. to solve the XMAX-3SATIO instance yp with comparable efficiency and low error probability. Specifically, we show that if the 5-MAX-3SAT(0 (SA(())() instance ;p is (1 8)-satiffialle for
some e S v-' 3.06 O VH 0.9, and algorithm ARL returns an c-optimal policy æ in time T
for solving the MDP instance Mi with enror probability Tद then following the policy for setting the value of variables in our sp, we can satisfy at least - fraction of clauses in the M-MAX-3SAY g. Finally, we connect our reduction process to rETH by E.I which leads to our Theorem 3.2.
instance &p in time T with error probability I
given Lemma
Both components are essential for demonstrating the hardness of SLINEAR-2-1 2-RL. Compared to the proof of Theorem the key modification here in this section, which distinguishes Theorem 3.]] from Theorem 3.2 arises from the inclusion of stochastic policies. This stochastic framework allows us to refine our results through the lens of randomized reduction, and further investigating our hardness result under rETH, enabling a more precise characterization of computational hardness.
E.2 An In-depth Look at Step-1: Polynomial Construction of M,
we construct a polynomial-time reduction from A.MA-3SAATH instance oo (as defined in Definition E.1 the structure of the SLINEAR-2-ER 2-RL problem. The instance consists of n Boolean variables ordered as (., ).). with each variable appearing in most b clauses. Since the MDP components-states, actions, transitions, and rewards-remain identical to those in the GLINEAR R- 2-RL framework, we focus exclusively components. In particular, we describe the polynomial-time construction of the PSP vector and the partial realizability vectors, both of which are specifically adapted the SLINEAR-2-RD problem.
Following the framework established in Section 4.1
MDP instance that captures
the modifications made to the approximation-relatee
Design of Partial Realizability Vectors and Realizability Validation. We retain the structure of as described in Section 4.2.3 while modifying the structure of 0 to accommodate the softmax policy set. In particular, adjustments are necessary for the virtual look-ahead state šn, defined in Equation 13). Recall that in $4, the variables æı through æh-1 determined by the actions taken in the preceding stages, whereas the remaining variables, 2t, through 2,, must be selected according to the policy æ.
In Section 4.2.3 the policy x was assumed to belong to the set of deterministic greedy policies IT., For any x E TT9
the nonzero entries in the vector M key component of 0T, are determined by
Note that here we use looser bound error probability bound in comparison with the bound in rETH (Definition 2.1 This error probability match the error probability of ASAT in reduction in Section E.3
26

---

tracing the variable assignments along the look-ahead path using the functions (f) (0) J= which characterize the behavior of the greedy policy in undecided states.
To generalize this construction to the softmax policy setting, require function that similarly governs action selection in undecided states, consistent with the probabilistic nature of softmax- based decisions. Crucially, we show that by suitably modifying the parameters 0, the principle of value function decomposition can still be preserved under this new framework. This leads to the following proposition, which formalizes the linear realizability of value functions in the context of softmax policies:
Proposition E.I. Given a softmax policy set II for any state 8n. E Sh ap E A. and π E I1 there exist (88,,)) E IR and O2 E R2d such that for any stage h E [H]:
h (Sh, an) = ((((h) an): 0n)
(23)
Proof. As we stated at the end of Section 4.2.3 the main idea of design is to guarantee that the feature vector of og) depends 8/ and Og. while the weight vector 0₂ depends only the roll-out of the softmax policy beyond stage h. thereby enabling the linear realizability condition 9% (5); aA) (ó(sh, an), 0x). The approach that we use here again to decompose the value of each state-action pair into two terms:
1 [C]
Th 88, an)
(bn + (Vn, Ma)),
where the first term, by, represents the number satisfied clauses up to stage h. and the second term, Mr). indicates the number of satisfied clauses when following the softmax policy from stage + 1 to the final stage H. Compared to the proof performed under II", the changes that must be applied in the case of given softmax policy E IT only affect the term Mn.
We now proceed to prove linear realizability by appropriately characterizing the structure of Mj, under the softmax policy set 11 The main technical challenge in transitioning to 11 lies in constructing a function-analogout to fa (0') from Section 4.2.3, embedded within 0% that accurately captures the action choices made by softmax policies in undecided states. For ease of exposition, we refer to this function as the policy follower.
Our approach begins by analyzing the structure of the action-value function (sh, an). which provides the foundation for defining the appropriate policy follower under stochastic policies. For any π E IT the action at each stage is drawn according to the probability distribution t <a,,) 8x). inducing stochastic trajectories in the MDP Mç- Consequently, the value g (sh, aA) is expressed as the expected cumulative reward over all possible continuations from (sh, 0h). that is:
9% (Sh: a.. = E, [R(#H) s = Sk, a = a..
(24)
The expectation in (sh, an) accounts for the stochasticity introduced by softmax action selections I when applied to states in stage h (i.e., 8n, E S,,), the
along the trajectory. For any policy resulting action distributions induce a set of possible paths to the terminal state, each corresponding to a different sequence of stochastic decisions. Specifically, this gives rise to 2 distinct transition paths from (sh, as) to the terminal state 8
Let T," (sk, ax) denote the set of all such transition paths generated by taking action in state $). and subsequently following policy æ E I1 Each path r E T, (sh, ax) corresponds to a sequence of state-action pairs beginning at (s), ax) and terminating at SH, i.c.. T = (s), ..,,).....)..................... When the context clear, we will abbreviate this set as Th for notational convenience.
For any T let p(r) denote the probability of the path sampled under the softmax policy π. Let (sH) denote the reward obtained at the terminal state following the path r. Clearly, the above expectation over the terminal reward can be written as
T% Sh, an) = Σ pp (())
(25)
TET
To ensure the linear realizability condition for qf' (sh, an) for any policy æ, we require qf (sh, an) (ō(sn, ax), 0n). Let of.7 represent a vector obtained by incorporating the policy induced by the
27

---

trajectory into the M, component of On. Thus, we have of²²) [1, M, where M denotes the vector Mr when we follow the trajectory T for setting values of Mr elements. Suppose that action value function is realizable:
qh (Sh, and (n),
= Σ p(r) (6(s), )
TET
= (K(sn an),
Σ p(T) ((1))
TETA"
= ((((h,, ah),
Σ p(r), (TT)
(26)
TET
Based on Equation (26). if we design 0g by
On Σ TETK"
eh [H]
(27)
then the linear realizability condition in Equation
23 holds. Note that p(r) is determined in (H) for any policy ıT _1 stage h [4]] and trajectory т. As result, each non-zero element of Mr
(5) (denoted by Mh, in Section 4.2.3) is a weighted sum of clauses' assignments under different possible
paths T E 7 (sh, ah, π) scaled by p(r), We thus complete the proof of Proposition E.1
As previously discussed, it is essential to ensure that the reduction from the 8- 6-MAX-3S instance the SLINEAR-2-RR problem can be carried out in polynomial time. From earlier constructions of the partial realizability and PSP feature vectors, we know that both can be computed in O(n") time. The remaining component to analyze the parameter vector 0₂ E Rd Each entry of 0, which corresponds to elements in Mą-can be efficiently computed via dynamic programming procedure in O(H) time. Given that the dimension d satisfies d = =(n"), the overall time required to construct On On H) Onn²), which remains polynomial in the input size n. This confirms that the full reduction to the SLINEAR-2 instance is computationally efficient.
E.3 An In-depth Look at Step-2: Algorithmic connection between ASAT and Aut. under I[
As we mentioned in Section E.1 the second component of the reduction involves establishing a correct algorithmic connection. To complete the proof of Theorem [3.2] it remains to demonstrate how the ARI. algorithm can be leveraged to construct the ASAT method such that solving the SLINEAR- 2-RL instance efficiently yields an efficient solution for the 6-MAX-3SATIC instance. Our key idea is as follows: Given a (1 5)-satisfiable 6-MAX-3SAT(h) instance yp, which has a maximum satisfiability ratio of [C*| [c We transform it to instance of SLINEAR 2 RL denoted as M, (the constructed MDP instance) in polynomial time such that if randomized algorithm Aqu runs on Map returns e-optimal policy и with error probability J in time T. then following the policy w, if use Aut algorithm as a module in designing randomized algorithm ASAT for setting the value of variables in our s. we can satisfy at least 5 fraction of clauses in time T with error probability 3
Here, since (x*) } C Im we only need to establish the reduction based the best stochastic policy within the set 1m Recall that R(sH) = [Cam((H)] denotes the reward obtained at the terminal state
[C]
8и. Note that R(sh) is random variable due to the stochastic nature of the softmax policy set. We
can now state the e-optimality condition as given in Equation 28
| [C]
arg max #ETTAm
(28)
"More formally, with high probability, the policy class T contains stochastic policies whose value functions closely approximate the optimal value function v". This is because I1"" is constructed from the parameter matrix θ E g x and encompasses an infinite collection of softmax policies. As result, the probability that 11 includes near-optimal policy converges to 1.
28

---

By rearranging Equation sampled rewards.
28 we have the lower bound on the expected value of the observed
C [C]
1 [[[(sn)]
(29)
Note that given an c-optimal policy E IT in the initial state $1, we want to ensure that by following the stochastic policy for setting the value of the 6-MAX-3SAT()) instance, with high probability, we can satisfy at least a 1--6 fraction of the clauses. Therefore, we want to ensure that R(sH) 1 - å holds with high probability. To achieve this, we utilize the McDiarmid inequality, which establishes probabilistic connection between the random variable and its expectation under specific conditions.
Lemma E.2 (McDiarmid's inequality). Let ,I....,AA ,,, independent random variables, where each X takes values in set X4. Let F 2₁ ... x Xn +R be a function satisfying the bounded differences property: for every = 1, 1.....I,, n, if two inputs (.1...., In) and (a',...., differ only
in the i-th coordinate (i.e., I; 2 for all j # i), then
[F(1 xn)
2,,1 STi.
where Tú is a constant for each i. For any t > O, the deviation of f from its expectation satisfies:
-21
Pr X,) - E[F(X Xn)l 2 exp
(30)
2i=1 ri
?
-2t
Pr (F ...,, - X,)) exp
(31)
Σi
Based on the concentration inequality stated in Lemma E.2 consider function comprising inputs (independent random variables X1, .2, X.). ). If altering any single variable X; within its domain X; (while keeping all other variables fixed) results in bounded change r; the value of F, then F satisfies the bounded differences property. For such a function F satisfying these conditions, the concentration inequality in Equation (30p and Equation (3 holds.
we aim to derive a concentration bound for our random variable R(HH). which is bounded between 0 and 1. Our reward function R(sh) also satisfies the bounded difference property as outlined Lemma E.2, since changing any action through the trajectory from 81 to 8H only induces bounded difference in the value of R(SH). In 6-MAX-3SAT(B) instance, since each variable appears in most b clauses, have T3 [c]
Based on Lemma E.2
for any i [n.]. leading to
2t |C|
Pr (R(sh) E[R(sH)) -t) sises exp
(32)
H b²
121
H
Let us consider Po obtain the complement in Equation
exp
Fr.82
then
[c|
2
We can rearrange the terms and
32
as follows:
H H 1
Pr R(sh) 2 [[[[s]]]
Po-
(33)
|C|
We can now substitute the lower bound on [[[(sH)] from Equation incquality:
leading to the following
R(8H) 2
CCa
b
In
Po
|C]
-
C
2
Recall that we want to ensure
Pr Pr(((sH) 2 8)
> 1
Po
for some small probability po. Therefore, based on Equation condition holds:
33
we need ensure that the following
C
b
H In
po
>
- 6.
|C|
C
2
29

---

By rearranging the inequality, we obtain the following condition that must hold for the given
Hln
e E C
(34)
In Equation 34 we have the following negative term:
b
In
(35)
2
To achieve small enror probability Po. we can control this term by increasing (C). Additionally, note that 6 2 3 (we choose b 3) and 5 = 0.1. Here, fix error probability Po $. Furtheromore, note
that here n d', [C| = (n)) = OHH). and S
= v². As result, we have that:
C
VHH (11
c u. 3.06 O
0.9.
(36)
To guarantee that the right hand-side of the above inequality stays positive, we need to have -3.06- 52( (v- (0.99a) Based on the mentioned conditions,
O
V 0.9 0, hence the condition H
we have the following probability inequality:
Pr (R(sh) 1 11-6) 6) 2 1 Po.
where Po represents small probability of failure.
Recall that the goal is to use the randomized algorithm Art as subroutine within AsArs such that, with high probability, at least a 1 - ò fraction of the clauses satisfied. Since the reduction is randomized, we must ensure that the overall success probability- wwichh includes both the correctness of the polynomial-time transformation and the success of solving the 6-MAX-3SAT(b) (see Chapter of [AB09)). As all components of the instance transformation are deterministie, the success probability of the randomized reduction depends
-xceedss
factors: the probability that To and the probability that ASAT succeeds on 6-MAX- AT when employing Au.. which is Po. Combining these, the total success probability is 9
ARL returns an e-optimal policy, which is g
(1 - Po) 3. This completes the reduction.
10
Hardness Result about 6-MAX-3SAT())
To establish the hardness result for 6-MAX-3SAT()) under rETH, as stated in Lemmal E.1 first introduce a complexity problem called (b.3)-GAP- as defined by [KLL*2 +23 which is given as follows:
Definition F.1 ((b.)-GAP-3-SAT KLL-+33), Given a 3-CNF formula with variables and O
clauses, the following conditions hold:
Each variable appears in at most b clauses.
Either &p is satisfiable, or any assignment leaves at least an e-fruction of clauses unsatisfied.
Based on the hardness result for solving (b.e)-GAP33-AATi in KLL+1 +23), we restate the following lemma.
Lemma F.1 (Hardness of GAP-)-GAP (KLL-23)). Under rETH, there exist constants b,e,c > 0 such that no randomized algorithm can solve (bee)-GAP-3-SAT with variables in time exp(ce/per ppolyo//ooylo(u)) with error probability 1/8.
To complete the proof of Lemma E.I it suffices to reduce (b.c)-GAP-3-SAT to 6-MAX-3SAT((). For this, assume very small constants and to ensure that (6.c)-GAP-3-SAT satisfies the conditions of Lemma F.I. while preserving the NP-hardness of 3-MAx-3SATCh Without loss of generality, further assume that 8 > 6.
Given an instance ii of (b.e)-GAP33-S.. with e variables and [C] clauses, we proceed with the reduction follows: we copy (i and create instance 922 for 3-MAX-3SAT(6). Let the algorithm
30

---

that interacts with the (aae)-GAP3--AA. instance be denoted as Agup, and the algorithm that interacts with the (-MAX-3SAT(b) instance as Amax. If the following conditions hold, we have successful reduction:
If Amax solves P22 and returns an assignment a Xasiign such that [Cax(()) following z, we satisfy all clauses of fi and return "Yes".
then
[c]
If Amax cannot solve iP2 and returns assignment Xassign such that [Cmu(a))
8, then
CI
following x, we leave at least an c-fraction of clauses unsatisfied in ş11 and return "No".
For the first argument, if Amax returns an assignment x such that [Gn((a]] > 1 - 6, then since e, [C]
it implies that all clauses in fp are satisfied. For the second argument, if the returned assignment satisfies [c,x()) 1 6, then cannot satisfy all clauses in y22, and at least e-fraction of the clauses remain unsatisfied. The instance transformation occurs polynomial time, specifically Ouv), and the appropriate algorithmic connection is established. Consequently, we conclude that 6-MAX-3SAT(b) is as hard as ------P---ST and the hardness result from Lemma E. also holds for M--MAXX-STTTC under rETH.
31


Reviews:
[{"review_id": "O835RRXkz7", "reviewer": "Reviewer_FVp2", "summary": "This paper studies the computational complexity of reinforcement learning under linear function approximation. The authors introduce a new notion, partial $q^{\\pi}$-realizability, which lies between the existing assumptions of $q^*$-realizability and $q^{\\pi}$-realizability. They show that finding an $\\varepsilon$-optimal policy within the greedy policy class is NP-hard, via a polynomial-time reduction from $\\delta$-MAX-3SAT. For the softmax policy class, they establish an exponential time lower bound in the feature dimension under the randomized Exponential Time Hypothesis (rETH). The authors conclude that even when the policy class is relaxed beyond the optimal policy, the computational hardness of reinforcement learning remains unchanged.", "questions": "1. Under the *partial* $q^\\pi$-realizability assumption, what additional conditions would allow for efficient learning?\n2. Although the paper is theoretical in nature, it would be more convincing if a small illustrative MDP example demonstrated the computational failure or blow-up of existing linear function approximation algorithms. Is there a simple experiment that could be conducted?\n3. Could similar lower bounds be shown under weaker access assumptions than the generative model? If not, could you explain what technical challenges prevent this?", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper proposes a novel realizability assumption called *Partial* $q^\\pi$-realizability, which bridges the gap between the existing $q^*$- and $q^\\pi$-realizability assumptions. It establishes fundamental computational hardness results under linear function approximation by leveraging different complexity hypotheses for two distinct policy classes. The logical structure of the paper is clearly organized, making it easy to follow.\n\n\n**Weaknesses**\n\n\nAs acknowledged in the paper’s limitations, it remains unaddressed whether similar lower bounds hold in the case of shared features.", "was_revised": true, "final_justification": "I believe this paper has met the bar for acceptance, and I will maintain my original assessment.", "rebuttal": "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.\n\n## Comment on Weakness 1 (The Use of Separate Feature Representations)\nWe 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$.\nIn 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.\nThis 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.\nThat 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.\n\n## Answer to Question 1 (Additional Conditions for Efficient Learning)\n\nWe 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.\nOne 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.\nOn 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.\nExploring both the computational and statistical aspects of learning under partial realizability is part of our ongoing work.\n\n## Answer to Question 2 (Possibility of Simple Experiment)\nWe 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.\nThat 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.\n\n## Answer to Question 3 (Hardness Results under Weaker Access Assumptions)\n\nYes — 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.\n\n**--- [References]---**\n\n[1] Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable?, 2023."}, {"review_id": "kRPoMT4ejW", "reviewer": "Reviewer_XQpi", "summary": "Prior work has shown that RL is computationally tractable under the stronger $q^\\pi$-realizability assumption, whereas the weaker $q^*$-realizability assumption leads to exponential lower bounds. To investigate whether improved results are achievable under assumptions weaker than $q^\\pi$-realizability, this paper introduces a partial realizability assumption. It then considers two types of policy classes—greedy and softmax—and proves an exponential lower bound on the computational complexity in both cases.", "questions": "(1) The claims in Lines 214–219 seem a bit unclear to me. Specifically, the policies in $\\Pi_g$ are deterministic, while those in $\\Pi_{sm}$ are stochastic. Why should $\\Pi_g \\subseteq \\Pi_{sm}$ hold with high probability? Also, over what is this probability defined? \n\n(2) Theorem 3.2 does not explicitly claim that SLINEAR-κ-RL is NP-hard. This should perhaps be stated directly in the theorem.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well written, providing a clear introduction that conveys the intuition behind the problem and offering a detailed overview of the proof strategy. Although I did not verify every step of the proof, the theoretical analysis appears to be solid. The paper presents a novel result on the computational complexity of the RL problem, which, to the best of my knowledge, has not been previously reported in the literature.\n\n---\n\nWeaknesses:\n\n(1) Definition 3.1 is somewhat ambiguous, as the weight parameter $\\theta$ should include a superscript $\\pi$ to indicate its dependence on the policy.\n\n(2) One concern I have is that the result is entirely negative and does not hold for every policy class. In particular, because the feature map $\\phi'$ is constructed as part of the proof, the result does not offer insight into which structural properties of a policy class might help reduce the problem’s complexity. Is there any example of a policy class with alternative feature representations that could potentially avoid this hardness? Furthermore, given that the computational hardness of RL under $Q^*$-realizability is already well-established, it is unclear to me what new understanding or contribution this paper adds relative to the existing body of work.\n\n(3) I find the paper to be closely related to [1], especially in its approach to constructing an MDP from a SAT instance. However, it lacks a comprehensive comparison of its proof techniques with those of [1] and other relevant prior works.\n\n[1] Exponential Hardness of Reinforcement Learning with Linear Function Approximation, Kane et al. 2023", "was_revised": true, "final_justification": "After reading the rebuttal, I think it's a good paper. Thus, I lean towards acceptance.", "rebuttal": "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.\n\n## Comment on Weakness 1 (Ambiguity of Definition 3.1)\n\nWe 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.\n\n## Comment on Weakness 2 (Clarification of Our Contributions) \n\nWe 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.\n\nImportantly, 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.\n\nThe 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.\n\nIn 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.\n\nWe 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.\n\n## Comment on Weakness 3 (Comprehensive Comparison of Proof Techniques) \nWe 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.\n\n## Answer to Question 1 (Clarification of $\\Pi_g \\subseteq \\Pi_{sm}$) \n\nThank 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.\"\n\nTo 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. \n\nThus, 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.\n\nWe will clarify this interpretation further in the final version to improve precision and readability.\n\n## Answer to Question 2 (NP-Hardness of SLINEAR-κ-RL in Theorem 3.2) \n\nThank 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.\n\nTherefore, 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.\n\n**--- [References]---**\n\n[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."}, {"review_id": "BGk5NT0jGC", "reviewer": "Reviewer_SdE3", "summary": "This paper presents a new intermediate computational problem called _partial $q^{\\pi}$-realizability_, along with new complexity analysis for this setting. Prior work has examined two end points related to this new setting termed $q*$-realizability (in which $q^*$ is representable using a linear combination invoking features, $\\phi$) and $q^\\pi$-realizability (in which $q^\\pi$ is representable for all policies). Here, the problem of partial $q^\\pi$-realizability_ is defined _relative_ to a choice of policy class, $\\Pi$, which allows the problem to soften its requirements: only the $q$ functions of the policies contained in the set must be representable. Then, the second contribution of the work is new analysis of this partial realizability problem. The analysis comes in two Theorems which differ in which policy class the result centers around. The first (Theorem 3.1), makes use of the class of deterministic greed policies, $\\Pi^g$, while the second (Theorem 3.2) uses softmax policies; in both cases, the corresponding versions of the problem are proven to be hard. The rest of the paper is dedicated to an overview of the proof technique, involving details about the reductions used and examples.", "questions": "I only have a few high-level suggestions:\n- You might consider restructuring Sections 3.1 and 3.2. As a reader, my expectation after having the gLINEAR-$\\kappa-RL problem defined was then to dive into the theorem and analysis around this problem. The flow is slightly disjointed by moving between the two problems, then going onto the analysis. But, I recognize this is personal taste, and I see the tidiness of the current framing as well. Just something to consider.\n- For Theorem 3.1, the proof works for \\epsilon_0 = 0.05. For this reason, I would state the theorem using 0.05 directly and not bother introducing epsilon_0.\n- I can imagine it would be useful to motivate the choice of softmax policies a bit further. Or, at least to comment on whether you believe Theorem 3.2 is tailored to the choice of $\\Pi^{sm}$, and to what extent you believe a similar/nearly-identical result will hold for most well-behaved policy classes.\n- As you'll see, the abstract does not render well on openreview.\n\n__Typos / Writing Suggestions__\n\nThen, I include a few low-level reactions and suggestions below.\n\nAbstract:\n- You can safely remove this \"(a variant of MAX-3SAT)\", as the names of the problems makes this clear already.\n\nIntroduction:\n- Supporting some of these statements with references would be useful: \"...the estimation of the value function so that resulting complexity bounds become independent of the size of the state space\"\n- For Q2, the symbol \"$\\subsetneq$\" seems unecessary here, rather than just $\\subset$, right? Oh, I see, you want to specify that $\\pi^*$ is in the set, but not the only policy in the set?\n- Line 69: \"by defining subclass\" --> \"by defining the subclass\"\n- Line 70: \"of realizable policy set\" --> \"of realizable policy sets\"\n- Equation between lines 106/107: You use $\\sup$ in all cases one but, where you move to the $\\max$; any specific reason?\n\nPreliminaries\n- Line 114 header: \"Linear Function Approximations\" --> \"Linear Function Approximation\"\n\nProblem Statement and Main Results\n- Definition 3.3: I assume there is a good reason to make use of the states reachable after $h$ steps: $\\mathcal{S}_h$, though it seems to add complexity for little benefit so far. \n- Since the softmax policies do not use a temperature parameter, you might flag this somewhere early on. For instance, in the introduction, when you mention you will study softmax policies, you could add a short note indicating that there is no temperature used.\n- Typo: \"Theorem 3.1 (NP-Harness\" --> \"Theorem 3.1 (NP-Hardness\"\n- For Theorem 3.1: Is your intuition that the result also holds for values larger than 0.05, but that your proof simply won't generalize to those cases? Or, do you suspect for some larger epsilon that the problem becomes easier (this would be surprising)?", "limitations": "Yes, the authors call out all assumptions and limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths__\n- [New, Interesting Problem] The relaxation of realizability to the partial case is a clever idea, and presents an interesting new problem.\n- [Fundamental Result] The new hardness results are fundamental and interesting.\n- [Focused Narrative] This paper is ultimately about one clean idea: partial $q^\\pi$ realizability\n- [Clarity] Despite the technical nature of the paper, it is very readable. A lot of work clearly went into making the ideas accessible.\n\n__Weaknesses__\n- There are no major weaknesses. For what this paper sets out to do, it executes on it to a high degree.\n- Two minor weaknesses: (1) I could imagine clarifying some of the design choices in slightly more detail. For example, why did you choose the softmax policies to analyze, rather than another class? Do you anticipate similar results hold for most well-behaved choices of policy class? (2) The different feature vectors did leave me slightly confused by the end. Adding a little more exposition to help the reader understand this will help in communicating some of the main ideas.\n\n\nIn light of the above, unless another reviewer catches a glaring issue, I believe this is a clear accept.", "was_revised": true, "final_justification": "This is a very strong paper: it has a clear focus on a compelling theoretical question, and provides a clean and rigorous answer to this question.\n\nNo major issues were uncovered during the rebuttal, review, or discussion, so I maintain a positive outlook on the work.", "rebuttal": "We sincerely thank the reviewer for their thoughtful and encouraging feedback, as well as for raising these insightful questions.\n\n## Comment on Minor Weakness 1 (Selection of Softmax Policy and Anticipated Hardness Results Under General Policy Classes) \n\nWe 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.\n\nRegarding 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.\n\nIn 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.\n\n## Comment on Minor Weakness 2 (Having Two Feature Vectors) \n\nWe 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. \n\nFrom 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.\n\nMoreover, 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.\n\n\n## Comment on Questions and Suggestions \nWe 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.\n\n   - $$\\textbf{[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.\n   - $$ \\textbf{[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.\n   - $$ \\textbf{[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:\n     - The space of policies is infinite or uncountable,\n     - The policy space is not compact, or\n     - There is no policy that attains the highest value due to the lack of continuity or closure in the space.\n\n\nIn 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.\n\n- $$\\textbf{[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.\n\n- $$ \\textbf{[Typos / Writing Suggestions Section - Problem Statement and Main Results - Theorem 3.1]:}$$\nWe 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$.\n\nWe 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.\n\n**---[References]---**\n\n[1] Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable?, 2023."}, {"review_id": "OiYANvuKsa", "reviewer": "Reviewer_v2tA", "summary": "This paper explores the computational complexity of reinforcement learning algorithms under the partial q^pi-realizability setting, a novel framework introduced by the authors.\n\nThey first establish NP-hardness when considering a class of greedy policies. Furthermore, under the Randomized Exponential Time Hypothesis, they show that learning with softmax policy classes has exponential computational complexity in the dimension of the feature vector.\n\nThe proposed setting and results help bridge the gap between the linear q* and linear q^pi assumptions, offering a more complete understanding of the landscape.\n\nA key technical contribution is the reduction from two well-known complexity problems:  delta-MAX-3SAT and delta-MAX-3SAT(b).", "questions": "The proposed partial q^pi setting is quite interesting. Could you provide some natural or practical examples that illustrate this setting?\n\nThe paper mentions that related works use reductions to establish hardness results. Could you elaborate on how the reduction used in this paper differs from those in prior work?", "limitations": "not applicable", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper is well motivated, as it explores the intermediate regime between two fundamental settings in reinforcement learning theory: linear q* and linear q^pi.\n\nThe discussion of related work is thorough and informative, providing valuable context for the reader.\n\nThe assumption that the agent has access to a generative model strengthens the significance of the hardness results presented.\n\nPrevious work has shown quasi-polynomial and even exponential lower bounds under the q*- and v* -realizability assumptions. On the other hand, under the stronger assumption of linear q^pi-realizability, efficient algorithms exist when using a generative model. This naturally raises the question: Can the positive results be generalized, or do hardness results still hold under more relaxed assumptions? \n\nThis paper provides a compelling answer, demonstrating that computational hardness persists even when the policy class extends beyond the optimal policy pi*, that is, beyond the linear q* setting.\n\nThe two main results (Theorems 3.1 and 3.2) are both significant. The core technical contribution lies in clever reductions from classical complexity problems, which underpin the hardness proofs.\n\nAlthough the proposed partial linear q^pi setting is novel, it appears to lack natural motivating examples.", "was_revised": true, "final_justification": "After carefully reading the other reviews and the subsequent discussions, I am inclined to maintain my accept recommendation. \n\nI believe this paper will be very solid after revisions based on the feedback provided.", "rebuttal": "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.\n\n## Answer to Question 1 (Practical Examples)\n\nThat 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]).\n\nA 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).\n\nOn 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.\n\nIdentifying 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.\n\n## Answer to Question 2 (Comparison of Our Reduction Approach with Prior Work)\nThe 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. \n\nOur 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.\n\nFrom 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.\n\n**--- [References]---**\n\n[1] Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable?, 2023.\n\n[2] D. Kane, S. Liu, S. Lovett, and G. Mahajan. Computational-statistical gaps in reinforcement learning, 2022.\n\n[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."}]

Author rebuttal:

Meta-review: This paper studies the computational hardness of RL with a generative model under the so-called partial $q^{\pi}$ realizability, where there is a subset of policies under which $q^{\pi}$ is linearly-realizable for all $\pi$ in the subset. They consider two types of policy subset: greedy policies and softmax polices. They establish NP hardness for greedy policies and exponential lower bounds for softmax policies. 


**Strengths**. The partial $q^{\pi}$ realizability is well motivated that sits between two other regimes that are more well studied: $q^*$-realizability and all-policy $q^{\pi}$ realizability. The paper is well written and provides a comprehensive related work discussion as well as the high-level ideas of their construction approach. The hardness problem $\delta$-MAX-3SAT seems a novel technical construction compared to other hardness problem constructions in the growing literature of hardness of RL. Understanding computational complexity in RL is a significant problem for the ML community. 

**Weaknesses**. No major issues, as agreed by the reviewers. 

This paper receives positive evaluations from all the reviewers, initially and throughout the discussion. In particular, the discussion phase presents a collegial discussion where the authors have well addressed the issues (mostly minor) raised by the reviewers and the reviewers well acknowledged such responses.
Decision: Accept (poster)