Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity

Authors: guhao  feng
han  zhong
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:50:20

Abstract: Reinforcement Learning (RL) encompasses diverse paradigms, including model-based RL, policy-based RL, and value-based RL, each tailored to approximate the model, optimal policy, and optimal value function, respectively. This work investigates the potential hierarchy of representation complexity among these RL paradigms. By utilizing computational complexity measures, including time complexity and circuit complexity, we theoretically unveil a potential representation complexity hierarchy within RL. We find that representing the model emerges as the easiest task, followed by the optimal policy, while representing the optimal value function presents the most intricate challenge. Additionally, we reaffirm this hierarchy from the perspective of the expressiveness of Multi-Layer Perceptrons (MLPs), which align more closely with practical deep RL and contribute to a completely new perspective in theoretical studying representation complexity in RL. Finally, we conduct deep RL experiments to validate our theoretical findings.

Main paper: 
 introduction: 
 The past few years have witnessed the tremendous success of Reinforcement Learning (RL) [43] in solving intricate real-world decision-making problems, such as Go [41] and robotics [27] . These successes can be largely attributed to powerful function approximators, particularly Neural Networks (NN) [30] , and the evolution of modern RL algorithms. These algorithms can be categorized into model-based RL, policy-based RL, and value-based RL based on their respective objectives of approximating the underlying model, optimal policy, or optimal value function.Despite the extensive theoretical analysis of RL algorithms in terms of statistical error [e.g., 5, 21, 42, 24, 23, 14, 17, 58, 51] and optimization error [e.g., 2, 49, 9, 29] lenses, a pivotal perspective often left in the shadows is approximation error. Specifically, the existing literature predominantly relies on the (approximate) realizability assumption, assuming that the given function class can sufficiently capture the underlying model, optimal value function, or optimal policy. However, limited works examine the representation complexity in different RL paradigms -the complexity of the function class needed to represent the underlying model, optimal policy, or optimal value function. In particular, the following problem remains elusive:Is there a representation complexity hierarchy among model-based RL, policy-based RL, and value-based RL?To our best knowledge, the theoretical exploration of this question is limited, with only two exceptions [13, 62] . [13] employs piecewise linear functions to represent both the model and value functions, Table 1 : A summary of our main results. ✓ means that the function can be represented by logprecision MLP with constant layers and polynomial hidden dimension, while ✗ means that this MLP class cannot represent the function. Blue denotes low representation complexity, and red represents high representation complexity.utilizing the number of linear pieces as a metric for representation complexity. They construct a class of Markov Decision Processes (MDPs) where the underlying model can be represented by a constant piecewise linear function, while the optimal value function necessitates an exponential number of linear pieces for representation. This disparity underscores that the model's representation complexity is comparatively less than that of value functions. Recently, [62] reinforced this insight through a more rigorous circuit complexity perspective. They introduce a class of MDPs wherein the model can be represented by circuits with polynomial size and constant depth, while the optimal value function cannot. However, the separation between model-based RL and value-based RL demonstrated in [62] may not be deemed significant (cf. Remark 5.6). More importantly, [13, 62] do not consider policy-based RL and do not connect the representation complexity in RL with the expressive power of neural networks such as Multi-Layer Perceptron (MLP) and Transformers [47] , thereby providing limited insights for deep RL.Our Contributions. To address the limitations of previous works and provide a comprehensive understanding of representation complexity in RL, we explore representation complexity within (1) model-based RL;(2) policy-based RL; and (3) value-based RL, employing (i) computational complexity (time complexity and circuit complexity) and (ii) expressiveness of MLP to rigorously quantify representation complexity. We outline our results below, further summarized in Table 1 .• To elucidate the representation complexity separation between model-based RL and model-free RL 4 , we introduce two types of MDPs: 3-SAT MDPs (Definition 3.2) and a broader class referred to as NP MDPs (Definition 3.7). In both cases, the representation complexity of the model, inclusive of the reward function and transition kernel, falls within the complexity class AC 0 (cf. Section 2).In contrast, we demonstrate that the representation of the optimal policy and optimal value function for 3-SAT MDPs and NP MDPs is NP-complete. Significantly, our results not only demonstrate the significant representation complexity separation between model-based RL and model-free RL, but also address an open question in [62] . See Remark 3.4 for details. • To further showcase the separation within the realm of model-free RL, we introduce two classes of MDPs: CVP MDPs (Definition 4.1) and a broader category denoted as P MDPs (Definition 4.4).In both instances, the representation complexity of the underlying model and the optimal policy is confined to the complexity class AC 0 . In contrast, the representation complexity for the optimal value function is characterized as P-complete, reflecting the inherent computational challenges associated with computing optimal values. This underscores the efficiency in representing policies (and models) while emphasizing the inherent representation complexity involved in determining optimal value functions. • To provide more practical insights, we establish a connection between our previous findings and the realm of deep RL, where the model, policy, and value function are represented by neural networks. Specifically, for 3-SAT MDPs and NP MDPs, we demonstrate the effective representation of the model through a constant-layer MLP/Transformer with polynomial hidden dimension, while the optimal policy and optimal value exhibit constraints in such representation. Furthermore, for the CVP MDPs and P MDPs, we illustrate that both the underlying model and optimal policy can be represented by constant-layer MLPs/Transformers with polynomial hidden dimension. However, the optimal value, in contrast, faces limitations in its representation using MLPs/Transformers with constant layers and polynomial hidden dimensions. These results corroborate the messages conveyed through the perspective of computational complexity, contributing a novel perspective that bridges the representation complexity in RL with the expressive power of MLP/Transformer. In addition, we conduct deep RL experiments to corroborate our theory.In summary, our work unveils a potential hierarchy in representation complexity among different categories of RL paradigms -where the underlying model is the most straightforward to represent, followed by the optimal policy, and the optimal value function emerges as the most intricate to represent. This insight offers valuable guidance on determining appropriate targets for approximation, enhancing understanding of the inherent challenges in representing key elements across different RL paradigms. Moreover, our representation complexity theory is closely tied to the sample efficiency gap observed among various RL paradigms. Given that the sample complexity of RL approaches often depends on the realizable function class in use [21, 42, 14, 23, 17, 58] , our results suggest that representation complexity may play a significant role in determining the diverse sample efficiency achieved by different RL algorithms. This aligns with the observed phenomenon that model-based RL typically exhibits superior sample efficiency compared to other paradigms [22, 42, 45, 20, 54, 56] . Consequently, our work underscores the importance of considering representation complexity in the design of sample-efficient RL algorithms. See Appendix C.1 for more elaborations. Additional Related Works. We have discussed most related works in the introduction part, and more related works are deferred to Appendix A.Notations. We denote the distribution over a set X by ∆(X ). We use N and N + to denote the set of all natural numbers and positive integers, respectively. For any n ∈ N + , we denote [n] = {1, 2, • • • , n}, and 0n = (0, 0,• • • , 0 n times ) ⊤ , 1n = (1, 1, • • • , 1 n times ) ⊤ . 
preliminaries: 
 Markov Decision Process. We consider the finite-horizon Markov decision process (MDP), which is defined by a tuple M = (S, A, H, P, r). Here S is the state space, A is the action space, H is the length of each episode, P : S × A → ∆(S) is the transition kernel, and r : S × A → [0, 1] is the reward function. Moreover, when the transition kernel is deterministic, say P(• | s, a) = δ s ′ for some s ′ ∈ S. we denote P(s, a) = s ′ . A policy π = {π h : S → ∆(A)} H h=1 consists of H mappings from the state space to the distribution over action space. For the deterministic policy π h satisfying π h (•|s) = δ a for some a ∈ A, we denote π h (s) = a. Here δ a is the Dirac measure at a. Given a policy π, for any (s, a) ∈ S × A, we define the state value function and state-action value function (Qfunction) asV π h (s) = E π [ H h ′ =h r h ′ (s h ′ , a h ′ ) | s h = s], Q π h (s, a) = E π [ H h ′ =h r h ′ (s h ′ , a h ′ ) | s h = s, a h = a].Here the expectation E π [•] is taken with respect to the randomness incurred by the policy π and transition kernels. There exists an optimal policy π * achieves the highest value at all timesteps and states, i.e., V π * h (s) = sup π V π h (s) for any h ∈ [H] and s ∈ S. For notation simplicity, we use the shorthands V * h = V π * h and Q * h = Q π * h for any h ∈ [H]. RL encompasses diverse paradigms, including model-based RL, policy-based RL, and value-based RL, each tailored to approximate the model (r and P), optimal policy π * , and optimal value function Q * , respectively. See Appendix B.1 for more details regarding function approximation.Computational Complexity. Our work will use some classical computational complexity theory [3] . Specifically, we will utilize five complexity classes: AC 0 , TC 0 , L, P, and NP. Here, L, P, and NP are defined in terms of the running time of Turing Machines (Definition B.1), while AC 0 and TC 0 are defined based on the complexity of Boolean circuits (Definition B.2). To facilitate the readers, we provide the detailed definition in Appendix B.2. The relationship between these five complexity classes is AC 0 ⊊ TC 0 ⊂ L ⊂ P ⊂ NP. The question of whether the relationship TC 0 ⊂ P ⊂ NP holds as a strict inclusion remains elusive in theoretical computer science. However, it is widely conjectured that P = NP and TC 0 = P are unlikely to be true. 
the separation between model-based rl and model-free rl: 
 In this section, we focus on the representation complexity gap between model-based RL and modelfree RL, which encompasses both policy-based RL and value-based RL.As a warmup example to showcase the separation between model-based RL and model-free RL, we propose the 3-SAT MDPs, whose construction is closely linked to the well-known NP-complete problem 3-satisfiability (3-SAT). The formal definition of 3-SAT is as follows.ψ 0n 0 ψ ψ ψ ψ ψ 1 r = 0.5 r = 1 a = 1 …… ψ v k v 1 v 0 k + 1 k + 1 a = 1 a = 0 …… …… n + 1 n + 1 r = 0 …..…… …..…… v end v end ψ(vend) = 1 ψ(vend) = 0 0n ψ 0n 2n + 2 ψ 0n n + 2 action sequences a = 0 Figure 1: A visualization of 3-SAT MDPs.Here, v is an n-dimensional vector, v 0 and v 1 are vectors obtained by replacing the k-th element of v with 0 and 1, respectively. Additionally, v end , v ′ end , and v ′′ end represent the assignments at the end of the episode. Definition 3.1 (3-SAT Problem). A Boolean formula ψ over variables u 1 , u 2 , • • • , u n is in the 3conjunctive normal form (3-CNF) if it takes the form of a conjunction of one or more disjunctions, each containing exactly 3 literals. Here, a literal refers to either a variable or the negation of a variable. Formally, the 3-CNF formula ψ has the form ofψ = i∈I (v i,1 ∨ v i,2 ∨ v i,3), where I is the index set and v i,j ∈ {u k , ¬u k } for some k ∈ [n]. The 3-SAT problem is defined as follows: given a 3-CNF Boolean formula ψ, judge whether ψ is satisfiable. Here, "satisfiable" means that there exists an assignment of variables such that the formula ψ evaluates to 1. Now we present the detailed construction of 3-SAT MDPs. Definition 3.2 (3-SAT MDP). For any n ∈ N + , let V = {u 1 , ¬u 1 , • • • , u n , ¬u n } be the set of literals. An n-dimensional 3-SAT MDP (S, A, H, P, r) is defined as follows. The state space S is defined by S = V 3n × {0, 1} n × ({0} ∪ [2n + 2]), where each state s can be denoted as s = (ψ, v, k). In this representation, ψ is a 3-CNF formula consisting of n clauses and represented by its 3n literals, v ∈ {0, 1} n can be viewed as an assignment of the n variables and k is an integer recording the number of actions performed. The action space is A = {0, 1} and the planning horizon is H = n + 2. Given a state s = (ψ, v, k), for any a ∈ A, the reward r(s, a) is defined by:r(s, a) =      1 If v is satisfiable and k = n + 1, 0.5 If k = 2n + 2, 0 Otherwise. (3.1)Moreover, the transition kernel is deterministic and takes the following form:P (ψ, v, k), a =          (ψ, v, n + 2) If a = k = 0, (ψ, v, 1) If a = 1 and k = 0, (ψ, v ′ , k + 1) If k ∈ [n] (ψ, v, k + 1) If k > n. (3.2)where v ′ is obtained from v by setting the k-th bit as a and leaving other bits unchanged, i.e., v′ [k] = a and v ′ [k ′ ] = v[k ′ ] for k ′ ̸ = k.The initial state takes form (ψ, 0 n , 0) for any length-n 3-CNF formula ψ.The visualization of 3-SAT MDPs is given in Figure 1 . We assert that our proposed 3-SAT model is relevant to real-world problems. In the state s = (ψ, v, k), ψ characterizes intrinsic environmental factors that remain unchanged by the agent, while v and k represent elements subject to the agent's influence. Notably, the agent is capable of changing 0 n to any n-bits binary string within the episode. Using autonomous driving as an example, ψ could denote fixed factors like road conditions and weather, while v and k may represent aspects of the car that the agent can control. While states and actions in practical scenarios might be continuous, they are eventually converted to binary strings in computer storage due to bounded precision. Regarding the reward structure, the agent only receives rewards at the end of the episode, reflecting the goal-conditioned RL setting and the sparse reward setting, which capture many real-world problems. Intuitively, the agent earns a reward of 1 if ψ is satisfiable, and the agent transforms 0 n into a variable assignment that makes ψ equal to 1 through a sequence of actions. The agent receives a reward of 0.5 if, at the first step, it determines that ψ is unsatisfiable and chooses to "give up". Here, we refer to taking action 0 at the first step as "give up" since this action at the outset signifies that the agent foregoes the opportunity to achieve the highest reward of 1. In all other cases, the agent receives a reward of 0. Using the example of autonomous driving, if the car successfully reaches its (reachable) destination, it obtains the highest reward. If the destination is deemed unreachable and the car chooses to give up at the outset, it receives a medium reward. This decision is considered a better choice than investing significant resources in attempting to reach an unattainable destination, which would result in the lowest reward. Theorem 3.3 (Representation complexity of 3-SAT MDP). Let M n be the n-dimensional 3-SAT MDP in Definition 3.2. The transition kernel P and the reward function r of M n can be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC 0 . However, computing the optimal value function Q * 1 and the optimal policy π * 1 of M n are both NP-complete under the polynomial time reduction. The proof of Theorem 3.3 is deferred to Appendix E.1. Theorem 3.3 states that the representation complexity of the underlying model is in AC 0 , whereas the representation complexity of optimal value function and optimal policy is NP-complete. This demonstrates the significant separation of the representation complexity of model-based RL and that of model-free RL. Remark 3.4. The recent work of [62] raises an open problem regarding the existence of a class of MDPs whose underlying model can be represented by AC k circuits while the optimal value function cannot. Here, AC k is a complexity class satisfying AC 0 ⊂ AC k ⊂ P ⊂ NP. Therefore, our results not only address this open problem by revealing a more substantial gap in representation complexity between model-based RL and model-free RL but also surpass the expected resolution conjectured in [62] . Remark 3.5. Although Theorem 3.3 only shows that Q * 1 is hard to represent, our proof also implies that V * 1 is hard to represent. Moreover, we can extend our results to the more general case, say{Q * h } h∈[⌊ n 2 ⌋]are NP-complete, by introducing additional irrelevant steps. Notably, one cannot anticipate Q * h to be hard to represent for any h ∈ [H] since Q H reduces to the one-step reward function r. This aligns with our intuition that the multi-step correlation is pivotal in rendering the optimal value functions in the "early steps" challenge to represent. Also, although we only show that π * 1 is hard to represent in our proof, the result can be extended to step h where 2 ≤ h ≤ H, as π * 1 also serves as an optimal policy at step h. Finally, We want to emphasize that, since our objective is to show that Q * = {Q * h } H h=1 and π * = {π * h } H h=1 have high representation complexity, it suffices to demonstrate that Q * 1 and π * 1 are hard to represent. Remark 3.6. Our results can be extended to stochastic MDPs and partially observable MDPs (POMDPs) via slight modifications. See Appendices H.1 and H.2 for details.We extend the results for 3-SAT MDPs by introducing the concept of NP MDP-a broader class of MDPs. Specifically, for any NP-complete language L, we can construct a corresponding NP MDP that encodes L into the structure of MDPs. Importantly, this broader class of MDPs yields the same outcomes as 3-SAT MDPs. In other words, in the context of NP MDP, the underlying model can be computed by circuits in AC 0 , while the computation of both the optimal value function and optimal policy remains NP-complete. The detailed definition of NP MDP is provided below. Definition 3.7 (NP MDP). An NP MDP is defined concerning a language L ∈ NP. Let M be a nondeterministic Turing Machine recognizing L in at most P (n) steps, where n is the length of the input string and P (n) is a polynomial. Let M have valid configurations denoted by C n , and let each configuration c = (s M , t, l) ∈ C n encompass the state of the Turing Machine s M , the contents of the tape t, and the pointer on the tape l, requiring O(P (n)) bits for representation. Then an ndimensional NP MDP is defined as follows. The state space S isC n × ({0} ∪ [2P (n) + 2]), and each s = (c, k) ∈ S consists of a valid configuration c = (s M , t, l) and a index k ∈ {0} ∪ [2P (n) + 2]recording the number of steps M has executed. The action space is A = {0, 1} and the planning horizon is H = P (n) + 2. Given state s = (c, k) = (s M , t, l, k) and action a, the reward function r(s, a) is defined by:EQUATIONwhere s accept is the accept state of Turing Machine M . Moreover, the transition kernel is deterministic and can be defined as follows:P (c, k), a =          (c, P (n) + 2) If a = k = 0, (c, 1) If a = 1 and k = 0, (c ′ , k + 1) If k ∈ [P (n)] (c, k + 1) If k > P (n). (3.4)where c ′ is the configuration obtained from c by selecting the branch a at the current step and executing the Turing Machine M for one step. Let x input be an input string of length n. We can construct the initial configuration c 0 of the Turing Machine M on the input x input by copying the input string onto the tape, setting the pointer to the initial location, and designating the state of the Turing Machine as the initial state. The initial state is defined as (c 0 , 0).The definition of NP MDP in Definition 3.7 generalizes that of the 3-SAT MDP in Definition 3.2 by incorporating the nondeterministic Turing Machine, a fundamental computational mode. The configuration c and the accept state s accpet in NP MDPs mirror the formula-assignment pair (ψ, v) and the scenario that ψ(v) = 1 in 3-SAT MDP, respectively. To the best of our knowledge, NP MDP is the first class of MDPs defined in the context of (non-deterministic) Turing Machine and can encode any NP-complete problem in an MDP structure. This represents a significant advancement compared to the Majority MDP in [62] and the 3-SAT MDP in Definition 3.2, both of which rely on specific computational problems such as the Majority function and the 3-SAT problem. The following theorem provides the theoretical guarantee for the NP-complete MDP. Theorem 3.8 (Representation complexity of NP MDP). Consider any NP-complete language L alongside its corresponding n-dimensional NP MDP M n , as defined in Definition 3.7. The transition kernel P and the reward function r of M n can be computed by circuits with polynomial size (in n) and constant depth, belonging to the complexity class AC 0 . In contrast, the problems of computing the optimal value function Q * 1 and the optimal policy π * 1 of M n are both NP-complete under the polynomial time reduction.The proof of Theorem 3.8 is deferred to Appendix E.2. Theorem 3.8 demonstrates that a substantial representation complexity gap between model-based RL (AC 0 ) and model-free RL (NP-complete) persists in NP MDPs. Consequently, we have extended the results for 3-SAT MDP in Theorem 3.3 to a more general setting as desired. Similar explanations for Theorem 3.8 can be provided, akin to Remarks 3.4, 3.5, and 3.6 for 3-SAT MDPs, but we omit these to avoid repetition. 
the separation between policy-based rl and value-based rl: 
 In Section 3, we demonstrate the representation complexity gap between model-based RL and modelfree RL. In this section, our focus shifts to exploring the representation complexity hierarchy within model-free RL, encompassing policy-based RL and value-based RL. More specifically, we construct a broad class of MDPs where both the underlying model and the optimal policy are easy to represent, while the optimal value function is hard to represent. This further illustrates the representation hierarchy between different categories of RL algorithms.We begin by introducing the CVP MDPs, whose construction is rooted in the circuit value problem (CVP). The CVP involves computing the output of a given Boolean circuit (refer to Definition B.2) on a given input. Definition 4.1 (CVP MDP). An n-dimensional CVP MDP is defined as follows. Let C be the set of all circuits of size n. The state space S is defined by S = C × {0, 1, Unknown} n , where each state s can be represented as s = (c, v). Here, c is a circuit consisting of n nodes with c[i] = (c[i][1], c[i][2], g i )describing the i-th node, where c[i] [1] and c[i] [2] indicate the input node and g i denotes the type of gate (including ∧, ∨, ¬, 0, 1). When g i ∈ {∧, ∨}, the outputs of c[i] [1] -th node and c[i] [2] -th node serve as the inputs; and when g i = ¬, the output of c[i] [1] -th node serves as the input and c[i] [2] is meaningless. Moreover, the node type of 0 or 1 denotes that the corresponding node is a leaf node with a value of 0 or 1, respectively, and therefore, c[i] [1] , c[i] [2] are both meaningless. The vector v ∈ {0, 1, Unknown} n represents the value of the n nodes, where the value Unknown indicates that the value of this node has not been computed and is presently unknown. The action space isA = [n] c vunknown r = 1 …… v v 1 v n a = 1 a = n …… …… r = 0 …..…… v end v end c a = i c v i c …… …… …… vend[n] = 1 otherwise …… …… c c cFigure 2 : A visualization of CVP MDPs. Here, v unknown , which contains n Unknown values, is the initial value vector. For any state s including a circuit c and a value vector v, choosing the action i, the environment transits to (c, v ′ i ). Moreover, v end , v ′ end , and v ′′ end are value vectors at the end of the episode. and the planning horizon is H = n + 1. Given a state-action pair (s = (c, v), a), its reward r(s, a) is given by:r(s, a) = 1 If the value of the output gate v[n] = 1, 0 Otherwise.Moreover, the transition kernel is deterministic and can be defined as:P (c, v), a = (c, v ′ ).Here, v ′ is obtained from v by computing and substituting the value of node a. More exactly, if the inputs of node a have been computed, we can compute the output of the node a and denote it as o[a]. Then we havev ′ [j] =      v[j] If a ̸ = j, o[a]If a = j and inputs of a are computed, Unknown If a = j and inputs of a are not computed.Given a circuit c, the initial state of CVP MDP is (c, v unknown ) where v unknown denotes the vector containing n Unknown values.The visualization of CVP MDPs is given in Figure 2 . In simple terms, each state s = (c, v) comprises information about a given size-n circuit c and a vector v ∈ {0, 1, Unkown} n . At each step, the agent takes an action a ∈ [n]. If the a-th node has not been computed, and the input nodes are already computed, then the transition kernel of the CVP MDP modifies v[a] based on the type of gate c[a]. The agent achieves the maximum reward of 1 only if it transforms the initial vector v unknown , consisting of n Unknown values, into the v satisfying v[n] = 1. This also indicates that CVP MDPs exhibit the capacity to model many real-world goal-conditioned problems and scenarios featuring sparse rewards. Hence, we have strategically encoded the circuit value problem into the CVP MDP in this manner. The representation complexity guarantee for the CVP MDP is provided below, and the proof is provided in Appendix F.1. Theorem 4.2 (Representation Complexity of CVP MDP). Let M n be the n-dimensional CVP MDP defined in Definition 4.1. The reward function r, transition kernel P, and optimal policy π * of M n can be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC 0 . However, the problem of computing the optimal value function Q * 1 of M n is P-complete under the log-space reduction. Theorem 4.2 illustrates that, for CVP MDPs, the representation complexity of the optimal value function is notably higher than that of the underlying model and optimal policy. Remark 4.3. We explain why P-completeness is considered challenging. In computational complexity theory, problems efficiently solvable in parallel fall into class NC. It is widely believed that P-complete problems cannot be efficiently solved in parallel (i.e., NC ̸ = P). Neural networks like MLP and Transformers [47] , which are implemented in a highly parallel manner, face limitations when addressing P-complete problems. See Section 5 for details.We broaden the scope of CVP MDP to encompass a broader class of MDPs -P MDPs. In this extension, we can encode any P-complete problem into the MDP structure while preserving the results established for CVP MDP in Theorem 4.2. We introduce the P MDP as follows. Definition 4.4 (P MDP). Given a language L in P, and a circuit family C, where C n ∈ C contains the circuits capable of recognizing strings of the length n in L. The size of the circuits in C n is upper bounded by a polynomial P (n). An n-dimensional P MDP based on L is defined as follows. The state space S is defined by S = {0, 1} n × C n × {0, 1, Unknown} P (n) , where each state s can be represented as s = (x, c, v). Here, c is the circuit recognizing the strings of length [2] , g i ) representing the i-th node where the output of nodes i 1 and i 2 serves as the input, and g i is the type of the gate (including ∧, ∨, ¬, and Input). When g i ∈ {∧, ∨}, the outputs of c[i] [1] -th node and c[i] [2] -th node serve as the inputs; and when g i = ¬, the output of c[i] [1] -th node serves as the input and c[i] [2] is meaningless. Moreover, the type Input indicates that the corresponding node is the c[i] [1] -th bit of the input string. The vector v ∈ {0, 1, Unknown} P (n) representing the value of the n nodes, and the value Unknown indicates that the value of the corresponding node has not been computed, and hence is currently unknown. The action space is A = [P (n)] and the planning horizon is H = P (n) + 1. The reward of any state-action (s = (x, c, v), a) is defined by:n in L with c[i] = (c[i][1], c[i]r(s, a) = 1 If the value of the output gate v[P (n)] = 1, 0 Otherwise.Moreover, the transition kernel is deterministic and can be defined as:P (x, c, v), a = (x, c, v ′ ),where v ′ is obtained from v by computing and substituting the value of node a. In particular, if the inputs of node a have been computed or can be read from the input string, we can determine the output of node a and denote it as o[a]. This yields the formal expression of v ′ :v ′ [j] =      v[j] If a ̸ = j, o[a]If a = j and inputs of a are computed, Unknown If a = j and inputs of a are not computed.Given an input x and a circuit c capable of recognizing strings of specific length in L, the initial state of P MDP is (c, v unknown ) where v unknown denotes the vector containing P (n) Unknown values and P (n) is the size of c.In the definition of P MDPs, we employ circuits to recognize the P-complete language L instead of using a Turing Machine, as done in the NP MDP in Definition 3.7. While it is possible to define P MDPs using a Turing Machine, we opt for circuits to maintain consistency with CVP MDP and facilitate our proof. Additionally, we remark that employing circuits to define NP MDPs poses challenges, as it remains elusive whether polynomial circuits can recognize NP-complete languages. Theorem 4.5 (Representation complexity of P MDP). For any P-complete language L, consider its corresponding (n-dimensional) P MDP M n as defined in Definition 4.4. The reward function r, transition kernel P, and the optimal policy π * of M n can be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC 0 . However, the problem of computing the optimal value function Q * 1 of M n is P-complete under the log-space reduction. The proof of Theorem 4.5 is deferred to Appendix F.2. Theorem 4.5 significantly broadens the applicability of Theorem 4.2 by enabling the encoding of any P-complete problem into the MDP structure, as opposed to a specific circuit value problem. In these expanded scenarios, the representation complexity of the model and optimal policy remains noticeably lower than that of the optimal value function.Consequently, by combining Theorems 3.3, 3.8, 4.2, and 4.5, a potential representation complexity hierarchy has been unveiled. Specifically, the underlying model is the easiest to represent, followed by the optimal policy, with the optimal value exhibiting the highest representation complexity. 
connections to deep rl: 
 While we have uncovered the representation complexity hierarchy between model-based RL, policy-based RL, and value-based RL through the lens of computational complexity in Sections 3 and 4, these results offer limited insights for modern deep RL, where models, policies, and values are approximated by neural networks. To address this limitation, we further substantiate our revealed representation complexity hierarchy among different RL paradigms through the perspective of the expressiveness of neural networks. Specifically, we focus on the MLP with Rectified Linear Unit (ReLU) as the activation function 5 -an architecture predominantly employed in deep RL algorithms.). An L-layer MLP is a function from input e 0 ∈ R d to output y ∈ R dy , recursively defined ash1 = ReLU (W1e0 + b1) , W1 ∈ R d 1 ×d , b1 ∈ R d 1 , h ℓ = ReLU (W ℓ h ℓ-1 + b ℓ ) , W ℓ ∈ R d ℓ ×d ℓ-1 , b ℓ ∈ R d ℓ , y = WLhL + bL, WL ∈ R dy ×d L , bL ∈ R dy ,where 2 ≤ ℓ ≤ L -1 and ReLU(x) = max{0, x} for any x ∈ R is the standard ReLU activation. Log-precision MLPs refer to MLPs whose internal neurons can only store floating-point numbers within O(log n) bit precision, where n is the maximal length of the input dimension.The log-precision MLP is closely related to practical scenarios where the precision of the machine (e.g., 16 bits or 32 bits) is generally much smaller than the input dimension (e.g., 1024 or 2048 for the representation of image data). In our paper, all occurrences of MLPs will implicitly refer to the log-precision MLP, and we may omit explicit emphasis on log precision for the sake of simplicity. See Appendix B.3 for more details regarding log precision. 2 : The input and output of the MLPs that represent the model, optimal policy, and optimal value function.To employ MLPs to represent the model, policy, and value function, we encode each state s and action a into embeddings e s ∈ R ds and e a ∈ R da , respectively. The detailed constructions of state embeddings and action embeddings of each type of MDPs are provided in Appendix G.1. In addition, we specify the input and output of MLPs that represent the model, policy, and value function in Table 2 .We now unveil the hierarchy of representation complexity from the perspective of MLP expressiveness. To begin with, we demonstrate the representation complexity gap between model-based RL and model-free RL. Theorem 5.2. The reward function r and transition kernel P of n-dimensional 3-SAT MDP and NP MDP can be represented by an MLP with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function. Theorem 5.3. Assuming that TC 0 ̸ = NP, the optimal policy π * 1 and optimal value function Q * 1 of n-dimensional 3-SAT MDP and NP MDP defined with respect to an NP-complete language L cannot be represented by an MLP with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function.The proof of Theorems 5.2 and 5.3 are deferred to Appendices G.2 and G.3, respectively. Theorems 5.2 and 5.3 show that the underlying model of 3-SAT MDP and NP MDP can be represented by constant-layer perceptron, while the optimal policy and optimal value function cannot. These demonstrate the representation complexity gap between model-based RL and model-free RL from the perspective of MLP expressiveness. The following two theorems further illustrate the representation complexity gap between policy-based RL and value-based RL, and the proof are deferred to Appendices G.4 and G.5, respectively. Theorem 5.4. The reward function r, transition kernel P, and optimal policy π * of n-dimensional CVP MDP and P MDP can be represented by an MLP with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function. Theorem 5.5. Assuming that TC 0 ̸ = P, the optimal value function Q * 1 of n-dimensional CVP MDP and P MDP defined with respect to a P-complete language L cannot be represented by an MLP with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function.Combining Theorems 5.2, 5.3, 5.4, and 5.5, we reaffirm the potential representation complexity hierarchy uncovered in Sections 3 and 4 from the perspective of MLP expressiveness. To our best knowledge, this is the first result on representation complexity in RL from the perspective of MLP expressiveness, aligning more closely with modern deep RL and providing valuable insights for practice. Remark 5.6. The results presented in this section underscore the importance of establishing NPcompleteness and P-completeness in Sections 3 and 4. Specifically, constant-layer MLPs with polynomial hidden dimension are unable to simulate P-complete problems and NP-complete problems under the assumptions that TC 0 ̸ = P and TC 0 ̸ = NP, which are widely believed to be impossible. In contrast, it is noteworthy that MLPs with constant layers and polynomial hidden dimension can represent basic operations within TC 0 (Lemma I.6), such as the Majority function. Consequently, the model, optimal policy, and optimal value function of "Majority MDPs" presented in [62] can be represented by constant-layer MLPs with polynomial size. Hence, the class of MDPs presented in [62] cannot demonstrate the representation complexity hierarchy from the lens of MLP expressiveness.Applicability and Extensions of Our Theory. As mentioned in the introduction, our representation results have implications for the statistical complexity in RL, as detailed in Appendix C.1. Although we have shown that the revealed hierarchy of representation complexity holds for a wide range of MDPs in theory, examining its broader applicability is essential. We discuss more general theoretical insights and extension to Transformer [47] architecture to Appendices C.2 and C.3.Experiments. We want to emphasize that our theoretical results do not apply to all MDPs, such as the MDP with all zero rewards and complex transitions. However, these additional MDP classes may not be typical in practice and could be considered pathological examples from a theoretical standpoint. To demonstrate that our theory captures practical problems, we conduct an empirical investigation into the representation complexity of different RL paradigms across various MuJoCo Gym environments [7] . Our empirical findings align with our theoretical conclusions. We report part of our experimental results in Figure 3 , more detailed experimental description and results are deferred to Appendix D.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [No] Justification: We will public the data and code after acceptance.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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 as the institution conducting the review. 
conclusions: 
 This paper studies three RL paradigms -model-based RL, policy-based RL, and value-based RLfrom the perspective of representation complexity. Through leveraging computational complexity (including time complexity and circuit complexity) and the expressiveness of MLPs as representation complexity metrics, we unveil a potential hierarchy of representation complexity among different RL paradigms. Our theoretical framework posits that representing the model constitutes the most straightforward task, succeeded by the optimal policy, while representing the optimal value function poses the most intricate challenge. Our work contributes to a deeper understanding of the nuanced complexities inherent in various RL paradigms, providing valuable insights for the advancement of RL methodologies. 
 
 Appendix: Representation Complexity in RL. In the pursuit of achieving efficient learning in RL, most existing works [e.g., 21, 42, 15, 23, 14, 50, 46, 17, 58, 25] adopt the (approximate) realizability assumption. This assumption allows the learner to have access to a function class that (approximately) captures the underlying model, optimal policy, or optimal value function, contingent upon the specific algorithm type in use. However, justifying the complexity of such a function class, with the capacity to represent the underlying model, optimal policy, or optimal value function, has remained largely unaddressed in these works. To the best of our knowledge, two exceptions are the works of [13] and [62] , which consider the representation complexity in RL. As mentioned earlier, by using the number of linear pieces of piecewise linear functions and circuit complexity as metrics, these two works reveal that the representation complexity of the optimal value function surpasses that of the underlying model. Compared with these two works, our work also demonstrates the separation between model-based RL and value-based from multiple angles, including circuit complexity, time complexity, and the expressive power of MLP, where the last perspective seems completely new in the RL theory literature. Moreover, our result demonstrates a more significant separation between model-based RL and value-based RL. In addition, we also study the representation complexity of policy-based RL, providing a potential hierarchy among model-based RL, policy-based RL, and value-based RL from the above perspectives.. There are many classical computational complexity results of RL [37, 11, 32, 6] . These studies characterize the computational complexity of the process of solving the decision problems (finding the optimal decision) in RL. However, our work differs by examining the representation complexity hierarchy among different RL paradigms, using the computational complexity and expressiveness of MLPs as the complexity measure. Consequently, our findings do not contradict previous classical results and cannot be directly compared to them.Model-based RL, Policy-based RL, and Value-based RL. In the domain of RL, there are distinct paradigms that guide the learning process: model-based RL, policy-based RL, and value-based RL, each with its unique approach. In model-based RL, the primary objective of the learner is to estimate the underlying model of the environment and subsequently enhance the policy based on this estimated model. Most work in tabular RL [e.g., 19, 5, 55, 57, 56] fall within this category -they estimate the reward model and transition kernel using the empirical means and update the policy by performing the value iteration on the estimated model. Additionally, some works extend this approach to RL with linear function approximation [4, 61] and general function approximation [42, 17, 58, 51] .Policy-based RL, in contrast, uses direct policy updates to improve the agent's performance. Typical algorithms such as policy gradient [44] , natural policy gradient [26] , proximal policy optimization [38] fall into this category. A long line of works proposes policy-based algorithms with provable convergence guarantees and sample efficiency. See e.g., [33, 1, 2, 8, 39, 59, 9, 49, 48, 29, 60, 34, 40] and references therein. In value-based RL, the focus shifts to the approximation of the value function, and policy updates are driven by the estimated value function. A plethora of provable value-based algorithms exists, spanning tabular RL [22] , linear RL [53, 24] , and beyond [21, 14, 23, 58, 10, 35] . These works mainly explore efficient RL through the lens of sample complexity, with less consideration for representation complexity, which is the focus of our work. In modern reinforcement learning, we need to employ function approximation to solve complex decision-making problems. Roughly speaking, RL algorithms can be categorized into three typesmodel-based RL, policy-based RL, and value-based RL, depending on whether the algorithm aims to approximate the model, policy, or value. In general, policy-based RL and value-based RL can both be regarded as model-free RL, which represents a class of RL methods that do not require the estimation of a model. We assume the learner is given a function class F, and we will specify the form of F in model-based RL, policy-based RL, and value-based RL, respectively.• Model-based RL: the learner aims to approximate the model, including the reward function and the transition kernels. Specifically, F = {(r : S × A → [0, 1], P : S × A → ∆(S))}. We also want to remark that we consider the time-homogeneous setting, where the reward function and transition kernel are independent of the timestep h. For the time-inhomogeneous setting, we can choose F = F 1 × • • • × F H and let F h approximate the reward and transition at the h-th step. • Policy-based RL: the learner directly approximates the optimal policy π * . The function class F takes the formF = F 1 × • • • × F h with F h ⊂ {π h : S → ∆(A)} for any h ∈ [H]. • Value-based RL: the learner utilizes the function class F = F 1 × • • • × F H to capture the optimal value function Q * , where F h ⊂ {Q h : S × A → [0, H]} for any h ∈ [H].In previous literature [e.g., 23, 14, 50, 46, 17, 58, 25] , a standard assumption is the realizability assumption -the ground truth model/optimal policy/optimal value is (approximately) realized in the given function class. Typically, a higher complexity of the function class leads to a larger sample complexity. Instead of focusing on sample complexity, as previous works have done, we are investigating how complex the function class should be by characterizing the representation complexity of the ground truth model, optimal policy, and optimal value function.To rigorously describe the representation complexity, we briefly introduce some background knowledge of classical computational complexity theory, and readers are referred to [3] for a more comprehensive introduction. We first define three classes of computational complexity classes P, NP, and L.• P is the class of languages 6 that can be recognized by a deterministic Turing Machine in polynomial time. • NP is the class of languages that can be recognized by a nondeterministic Turing Machine in polynomial time. • L is the class containing languages that can be recognized by a deterministic Turing machine using a logarithmic amount of space.To facilitate the readers, we also provide the definitions of deterministic Turing Machine and nondeterministic Turing Machine in Definition B.1. Definition B.1 (Turing Machine). A deterministic Turing Machine (TM) M is described by a tuple (Γ, Q, T), where Γ is the tape alphabet containing the "blank" symbol, "start" symbol, and the numbers 0 and 1; Q is a finite, non-empty set of states, including a start state q start and a halting state q halting ; andT : Q × Γ k → Q × Γ k-1 × {Left, Stay, Right},where k ≥ 2, is the transition function, describing the rules M use in each step. The only difference between a nondeterministic Turing Machine (NDTM) and a deterministic Turing Machine is that an NDTM has two transition functions T 0 and T 1 , and a special state q accept . At each step, the NDTM can choose one of two transitions to apply, and accept the input if there exists some sequence of these choices making the NDTM reach q accept . A configuration of (deterministic or nondeterministic) Turing Machine M consists of the contents of all nonblank entries on the tapes of M , the machine's current state, and the pointer on the tapes.To quantify the representation complexity, we also adopt the circuit complexity, a fundamental concept in theoretical computer science, to characterize it. Circuit complexity focuses on representing functions as circuits and measuring the resources, such as the number of gates, required to compute these functions. We start with defining Boolean circuits. Definition B.2 (Boolean Circuits). For any m, n ∈ N + , a Boolean circuit c with n inputs and m outputs is a directed acyclic graph (DAG) containing n nodes with no incoming edges and m edges with no outgoing edges. All non-input nodes are called gates and are labeled with one of ∧ (logical operation AND), ∨ (logical operation OR), or ¬ (logical operation NOT). The value of each gate depends on its direct predecessors. For each node, its fan-in number is the number of incoming edges, and its fan-out number is its outcoming edges. The size of c is the number of nodes in it, and the depth of c is the maximal length of a path from an input node to the output node. Without loss of generality, we assume the output node of a circuit is the final node of the circuit.A specific Boolean circuit can be used to simulate a function (or a computational problem) with a fixed number of input bits. When the input length varies, a sequence of Boolean circuits must be constructed, each tailored to handle a specific input size. In this context, circuit complexity investigates how the circuit size and depth scale with the input size of a given function. We provide the definitions of circuit complexity classes AC 0 and TC 0 .• AC 0 is the class of circuits with constant depth, unbounded fan-in number, polynomial AND and OR gates.• TC 0 extends AC 0 by introducing an additional unbounded-fan-in majority gate MAJ, which evaluates to false when half or more arguments are false and true otherwise.The relationship between the aforementioned five complexity classes isAC 0 ⊊ TC 0 ⊂ L ⊂ P ⊂ NP.The question of whether the relationship TC 0 ⊂ P ⊂ NP holds as a strict inclusion remains elusive in theoretical computer science. However, it is widely conjectured that P = NP and TC 0 = P are unlikely to be true.Uniformity of Circuits. Given a circuit family C, where c i ∈ C is the circuit takes n bits as input, the uniformity condition is often imposed on the circuit family, requiring the existence of some possibly resource-bounded Turing machine that, on input n, produces a description of the individual circuit c n . When this Turing machine has a running time polynomial in n, the circuit family C is said to be P-uniform. And when this Turing machine has a space logarithmic in n, the circuit family C is said to be L-uniform.In this work, we focus on MLPs, of which neuron values are restricted to be floating-point numbers of logarithmic (in the input dimension n) precision, and all computations operated on floating-point numbers will be finally truncated, similar to how a computer processes real numbers. Specifically, the log-precision assumption means that we can use O(log(n)) bits to represent a real number, where the dimension of the input sequence is bounded by n. An important property is that it can represent all real numbers of magnitude O(poly(n)) within O(poly(1/n)) truncation error.To elaborate further on the connections to statistical/sample complexity, the previous sample complexity (in both online and offline RL) of finding an ε optimal policy is typically poly(d, H, 1/ε) • log |H|, where d represents the complexity measure in online RL (e.g., DEC in [17] and GEC in [58] ) or the coverage coefficient in offline RL (e.g., [50] and [46] ), H denotes the horizon, and H stands for the model/policy/value hypothesis. According to our representation complexity hierarchy theory, the model-based hypothesis could be simpler since the ground truth model is easy to represent, resulting in a smaller log |H|. This provides an explanation of why model-based RL typically enjoys better sample efficiency than model-free RL. Furthermore, this connection highlights the importance of considering representation complexity in the design of sample-efficient RL algorithms.We also remark that the planning error of computing the optimal policy and value function using the learned model is an optimization error, and is a parallel direction of statistical error (sample efficiency). In summary, we consider the approximation error (representation complexity of the ground truth model/policy/value) in our work and provide an implication for the statistical error (sample efficiency of learning algorithms). We believe that exploring the twisted approximation error, optimization error, and statistical error, and providing a deeper comparison between modelbased RL and model-free RL would be an interesting direction, and we will endeavor to explore this in our future work.First, we wish to underscore that our identified representation complexity hierarchy holds in a general way. Theoretically, our proposed MDPs can encompass a wide range of problems, as any NP or P problems can be encoded within their structure. More crucially, our thorough experiments in diverse simulated settings support the representation complexity hierarchy we have uncovered. In fact, we have a generalized result establishing a hierarchy between policy-based RL and value-based RL, as stated in the following proposition: Proposition C.1. Given a Markov Decision Process (MDP) M = (S, A, H, P, r), where S ⊂ {0, 1} n and |A| = O(poly(n)), the circuit complexity of the optimal value function will not fall below the optimal policy under the TC 0 reduction.Proof. Note that given the optimal value function Q * , the optimal policy π * can be represented as π * (s) = argmax a∈A Q(s, a), for any s ∈ S. Therefore, we represent the optimal policy as the following Boolean circuits:π * (s) = a∈A a ∧ a ′ ∈A 1[Q * (s, a) ≥ Q * (s, a ′ )] .Therefore, the circuit complexity of the optimal value function will not fall below the optimal policy under the TC 0 reduction.However, our representation complexity hierarchy is not valid for all MDPs. For instance, in MDPs characterized by complex transition kernels and zero reward functions, the model's complexity surpasses that of the optimal policy and value function. However, these additional MDP classes may not be typical in practice and could be considered pathological examples from a theoretical standpoint. We leave the fully theoretical characterizing of representation hierarchy between model-based RL, policy-based RL, and value-based RL as an open problem. For instance, it could be valuable to develop a methodology for classifying MDPs into groups and assigning a complexity ranking to each group within our representation framework.Our theoretical results can also naturally extend to the Transformer architectures. First, we formulate the Transformer architectures to represent the model, policy, and value function. We encode each state s and action a into a sequence s s and s a , the detailed construction of the MDPs in this paper are listed as follows:• Sequences for the 3-SAT MDP. The state of the n-dimensional 3-SAT MDP is denoted as s = (ψ, v, k). Here, ψ is represented by a sequence of literals of length 3n, and v by a sequence of length n. By concatenating these sequences, we represent the state s = (ψ, v, k) using a sequence S s of length 4n + 1. The action a ∈ {0, 1} is represented by a single token.• • Sequences for the P MDP. The state of the n-dimensional P MDP is s = (x, c, v). Assuming the circuit c has a size bounded by P (n), we represent the circuit using a sequence of length 3P (n).The value vector v is encoded by a sequence of length P (n), and the input string x by a sequence of length n. Therefore, the state s = (x, c, v) is represented by the concatenated sequence S s . The action a ∈ [P (n)] is encoded as a scalar.With these formulations, we can extend our theoretical results to the Transformer architectures. Theorem C.2. Assuming that TC 0 ̸ = NP, the optimal policy π * 1 and optimal value function Q * 1 of n-dimensional 3-SAT MDP and NP MDP defined with respect to an NP-complete language L cannot be represented by a Transformer with constant layers, polynomial hidden dimension (in n),and ReLU as the activation function. Theorem C.3. Assuming that TC 0 ̸ = P, the optimal value function Q * 1 of n-dimensional CVP MDP and P MDP defıned with respect to a P-complete language L cannot be represented by a Transformer with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function.Proof of Theorems C.2 and C.3. According to the previous work [36] , a Transformer with logarithmic precision, a fixed number of layers, and a polynomial hidden dimension can be simulated by a L-uniform TC 0 circuit. On the other hand, the computation of the optimal policy and optimal value function for the 3-SAT MDP and NP MDP is NP-complete, and the computation of the optimal value function for CVP MDP and P MDP is P-complete. Therefore, the theorem holds under the assumption of TC 0 ̸ = NP and TC 0 ̸ = P.Theorem C.4. The reward function r and transition kernel P of n-dimensional 3-SAT MDP and NP MDP can be represented by a Transformer with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function. Theorem C.5. The reward function r, transition kernel P, and optimal policy π * of n-dimensional CVP MDP and P MDP can be represented by a Transformer with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function.Proof of Theorems C.4 and C.5. According to previous works [16, 52] , the Transformer model can aggregate the embeddings of the whole sequence to the embedding of one token with the attention mechanism. According to Theorems 5.2 and 5.4, an MLP with constant layers, polynomial hidden dimension (in n) and ReLU activation can represent these functions. Given an input sequence of states, the transformer first uses the attention layer to aggregate the whole sequence into a vector, and then just use the MLP module to calculate the corresponding functions.In this section, we empirically investigate the representation complexity of model-based RL, policybased RL, and value-based RL and validate our theory with a comprehensive set of experiments on various common simulated environments. Following [62] , fixing the depth d and the width w, and denoting the class of MLPs with d layers and w hidden units (with input and output sizes adjusted to the context) as F, we define the relative approximation errors as follows:EQUATION, e policy = minEQUATION, e value = minf ∈F E[ f (s, a) -Q * (s, a) 2 ] 1 2 E[(Q * (s, a) -E[Q * (s, a)]) 2 ] 1 2 , (D.1)where the expectation is taken with respect to the distribution induced by the optimal policy, and the square root of mean squared errors is divided by the standard deviation to ensure that the scales of different errors match. Hence, the quantities e transition , e reward , e policy , and e value defined in (D.1) characterize the difficulty for the MLP to approximate the transition kernel, the reward function, the optimal policy, and the optimal value function, respectively. We conduct experiments on four MuJoCo Gym environments [7] : HalfCheetah-v4, Humanoid-v4, InvertedPendulum-v4, and Ant-v4. To calculate the approximation errors defined in (D.1), we employ the TD3 algorithm [18] to train a RL agent and utilize this agent to generate a dataset of size {30000, 100000, 300000}. The parameters used in TD3 are provided in Table 3 . Subsequently, we use MLPs of different sizes (see Table 4 ) to approximate corresponding functions and calculate the approximation error. We run the experiment for each MLP configuration 5 times with 5 random seeds and report the means and standard deviations. All the experiments are conducted on an NVIDIA GeForce RTX 3090 Ti GPU. Figure 4 illustrates the results. In all experiments, the approximation error of the optimal value function is greater than the error of the optimal policy. And both of them are greater than the approximation error of the transition kernel and reward function. These results consistently indicate that the approximation errors of the optimal Q-function surpass those of the optimal policy, which, in turn, exceed those of the transition kernel and reward functions, across all environments and configurations. These empirical results validate our representation hierarchy revealed from the theoretical perspective. Proof of Theorem 3.3. We investigate the representation complexity of the reward function, transition kernel, optimal value function, and optimal policy in sequence.Reward Function. First, we prove the reward function can be implemented by AC 0 circuits. Given aliteral α ∈ {u 1 , u 2 • • • , u n , ¬u 1 , ¬u 2 , • • • , ¬u n }, we can obtain its value by α = j∈[n] (v[j] ∧ 1[α = u i ]) ∨ j∈[n] (¬v[j] ∧ 1[α = ¬u i ]) .After substituting the literal by its value under the assignment v, we can calculate the 3-CNF Boolean formula ψ(v) by two-layer circuits as its definition. Then the reward can be expressed asr(s, a) = 1[ψ(v) ∧ k = n + 1] + 0.5 • 1[k = 2n + 2],which further implies that the reward function can be implemented by AC 0 circuits.Transition Kernel. Then, we will implement the transition kernel by AC 0 circuits. It is noted that we only need to modify the assignment v, k. Given the input v, k and a, we have the output as follows:ψ ′ = ψ, v ′ [i] = (v[i] ∧ 1[i ̸ = k]) ∨ (a ∧ 1[i = k]), k ′ = (k + 1) • 1[k ≥ 1] + 1[k = 0 ∧ a = 1] + (n + 2) • 1[a = k = 0]. (E.1)It is noted that each element in the output is determined by at most O(log n) bits. Therefore, according to Lemma I.4, each bit of the output can be computed by two-layer circuits of polynomial size, and the overall output can be computed by AC 0 circuits.Optimal Policy. We aim to show that, given a state s = (ψ, v, k) as input, the problem of judging whether π * 1 (s) = 1 is NP-complete. We give a two-step proof.Step 1. We first verify that this problem is in NP. Given a satisfiable assignment v * as the certificate, we only need to verify the following things to determine whether there exists a sequence of actions to achieve the final reward of 1:• The assignment is satisfiable;• When k ∈ [n] or k = 0, v[i] = v * [i], i ∈ [k] and v * [k + 1] = 1.Notably, when exist such certificates, action a = 1 yields the reward of 1 and is consequently optimal.Conversely, when such certificates are absent, action a = 1 leads to the reward of 0, and in this case, a = 0 is the optimal action. Moreover, when k = n + 1 or k = n + 2, selecting a = 1 is always optimal. Consequently, given the certificates, we can verify whether π * 1 (ψ, 0 n , 0) = 1.Step 2. Meanwhile, according to the well-known Cook-Levin theorem (Lemma I.1), the 3-SAT problem is NP-complete. Thus, our objective is to provide a polynomial time reduction from the 3-SAT problem to the problem of computing the optimal policy of 3-SAT MDP. Given a Boolean formula of length n, the number of variables is at most n. Then, we can pad several meaningless clauses such as (u 1 ∨ ¬u 1 ∨ u 1 ) to obtain the 3-CNF Boolean formula ψ ′ with n clauses. Then the Boolean formula ψ is satisfiable if and only if π * 1 (ψ ′ , 0 n , 0) = 1. This provides a desired polynomial time reduction.Optimal Value Function. To show the NP-completeness of computing the optimal value function, we formulate the decision version of this problem: given a state s = (ψ, v, k), an action a and a number γ as input, and the goal is to determine whether Q * 1 (s, a) > γ. According to the definition of NP-completeness, we need to prove that this problem belongs to the complexity class NP and then provide a polynomial-time reduction from a recognized NP-complete problem to this problem. These constitute the objectives of the subsequent two steps.Step 1. We first verify that this problem is in NP. Given the input state s = (ψ, v, k), input action a, and input real number γ, we use the assignments v ′ of ψ as certificates. When γ ≥ 1, the verifier Turing Machine will reject the inputs, and when γ < 0, the verifier Turing Machine will accept the inputs. When γ ∈ [0.5, 1), the verifier Turing Machine will accept the input when there exists a v ′ satisfying the following two conditions:• The assignment v ′ is satisfiable for ψ• When k ∈ [n], it holds that v[i] = v ′ [i] for all i ∈ [k].When γ ∈ [0, 0.5), except in the scenario where the aforementioned two conditions are met, the verifier Turing Machine will additionally accept the input when k = a = 0. Then we have Q * 1 (s, a) > γ if and only if there exists a certificate v ′ such that the verifier Turing Machine accepts the input containing s, a, γ, and the assignment v ′ . Moreover, the verifier Turing Machine runs in at most polynomial time. Therefore, this problem is in NP.Step 2. Meanwhile, according to the well-known Cook-Levin theorem(Lemma I.1), the 3-SAT problem is NP-complete. Thus, our objective is to provide a polynomial time reduction from the 3-SAT problem to the computation of the optimal value function for the 3-SAT MDP. Given a Boolean formula of length n, the number of variables is at most n. Then, we can pad several meaningless clauses such as (u 1 ∨ ¬u 1 ∨ u 1 ) to obtain the 3-CNF Boolean formula ψ ′ with n clauses. The Boolean formula ψ is satisfiable if and only if Q * 1 ((ψ ′ , 0 n , 0), 1) > 3 4 , which gives us a desired polynomial time reduction.Combining these two steps, we can conclude that computing the optimal value function is NPcomplete.Proof of Theorem 3.8. Following the proof paradigm of Theorem 3.3, we characterize the representation complexity of the reward function, transition kernel, optimal policy, and optimal value function in sequence.Reward Function. Given the state s = (s M , t, l, k), the output of the rewardr(s, a) = 1[s M = s accept ∧ k = P (n) + 1] + 0.5 • 1[k = 2P (n) + 2]. (E.2)It is not difficult to see that the reward function can be implemented by AC 0 circuits. Transition Kernel. We establish the representation complexity of the transition kernel by providing the computation formula for each element of the transited state. Our proof hinges on the observation that, for a state s = (s M , t, l, k), we can extract the content x of the location l on the tape by the following formula:χ = i∈[P (n)](1[i = l] ∨ t[i])It is noted that we assume the contents written on the tape are 0 and 1. However, for the general case, we can readily extend the formula by applying it to each bit of the binary representation of the contents. Regarding the configuration c ′ = (s ′ M , t ′ , l ′ ) defined in (3.4), we observe that (i) the Turing Machine state s ′ M is determined by s M , a and χ; (ii) the content of the location l on the tape, t ′ [l], is determined by s M , a and χ, whereas the contents of the other locations on the tape remain unaltered, i.e., t′ [i] = t[i] for i ̸ = k;(iii) the pointer l ′ is determined by l, s M , a and χ.Moreover, the number of steps k ′ is determined by k and a. Therefore, each element in the output is determined by at most O(log n) bits. According to Lemma I.4, each bit of the output can be computed by two-layer circuits of polynomial size, and the output can be computed by the AC 0 circuits.Optimal Policy. Our objective is to demonstrate the NP-completeness of the problem of determining whether π * 1 (s) = 1, given a state s = (ψ, v, k) as input. We will begin by establishing that this problem falls within the class NP, and subsequently, we will provide a polynomial-time reduction from the NP-complete language L to this specific problem.Step 1. Given a sequence of choice of the branch as the certificate, we only need to verify the following two conditions to determine whether the optimal action a = 1:• The final state of the Turing Machine M is the accepted state.• When k ∈ [P (n)], the configuration of the Turing Machine after k-steps execution under the choice provided by the certificate is the same as the configuration in the current state.• When k ∈ [P (n)], the choice of the k-th step is branch 1.Note that, when exist such certificates, action a = 1 can always get the reward of 1 and is therefore optimal, and otherwise, action a = 1 always gets the reward of 0, and a = 0 is always optimal. Moreover, when k = P (n) + 1 or k = P (n) + 2, we can always select the action a = 1 as the optimal action. So given the certificates, we can verify whether π * 1 (ψ, 0 n , 0) = 1.Step 2. Given an input string s input of length n. We can simply get the initial configuration c 0 of the Turing Machine M on the input s input . Then s input ∈ L if and only if π * 1 ((c 0 , 0)) = 1, which gives us a desired polynomial time reduction.Combining these two steps, we know that computing the optimal policy of NP MDP is NP-complete.Optimal Value Function. To facilitate our analysis, we consider the decision version of the problem of computing the optimal value function as follows: given a state s = (s M , t, l, k), an action a, and a number γ as input, and the goal is to determine whether Q * 1 (s, a) > γ.Step 1. We first verify that the problem falls within the class NP. Given the input state s, we use a sequence of choice of the branch as the certificate. When γ ≥ 1, the verifier Turing Machine will reject the inputs, and when γ < 0, the verifier Turing Machine will accept the input. When γ ∈ [0.5, 1), the Turing Machine accepts the input when there is a certificate that satisfies the following two conditions:• The final state of the Turing Machine M is s accept .• When k ∈ [P (n)], the configuration of the Turing Machine after k-steps execution under the choice provided by the certificate is the same as the configuration in the current state.When γ ∈ [0, 0.5), in the scenario where the aforementioned two conditions are met, the verifier Turing Machine will additionally accept the input when k = a = 0. Note that, all these conditions can be verified in polynomial time. Therefore, given the appropriate certificates, we can verify whether Q * 1 (s, a) > γ in polynomial time.Step 2. Given that L is NP-complete, it suffices to provide a polynomial time reduction from the L to the problem of computing the optimal value function of NP MDP. Let s input be an input string of length n. To obtain the initial configuration c 0 of the Turing Machine M on the input s input , we simply copy the input string onto the tape, set the pointer to the initial location, and designate the state of the Turing Machine as the initial state. Therefore, s input ∈ L if and only if Q * 1 ((c 0 , 0), 1) > 3 4 , which provides a desired polynomial time.Combining these two steps, we can conclude that computing the optimal value function of NP MDP is NP-complete.Proof of Theorem 4.2. We characterize the representation complexity of the reward function, transition kernel, optimal policy, and optimal value function in sequence.Reward Function. First, we prove that the reward function of CVP MDP can be computed by AC 0 circuits. According to the definition, the output isr(s, a) = 1[v[n] = 1].Therefore, the problem of computing the reward function falls within the complexity class AC 0 .Transition Kernel. Then, we prove that the transition kernel of CVP MDP can be computed by AC 0 circuits. Given the state-action pair (s = (c, v), a), we denote the next state P(s, a) as s ′ = (c ′ , v ′ ). For any index i ∈ [n], we can simply fetch the node c[i] and its value byc[i] = j∈[n] (c[j] ∧ 1[i = j]), v[i] = j∈[n] (v[j] ∧ 1[i = j]), (F.1)where the AND and OR operations are bit-wise operations. Given the node c[a] and its inputs v[c[a] [1] ] and v[c[a] [2] ], we calculate the value of the a-th node and denote it as ō[a]. Here, ō[a] represents the correct output of the a-th node when its inputs are computed, and is undefined when the inputs of the a-th node have not been computed. Therefore, let ō[a] be Unknown when the inputs of the a-th node have not been computed. Specifically, we can compute ō[a] as follows:ō[a] = 1[g a = ∧] ∧ 1[v[c[i][1]], v[c[i][2]] ̸ = Unknown] ∧ (v[c[i][1]] ∧ v[c[i][2]]) ∨ 1[g a = ∨] ∧ 1[v[c[i][1]], v[c[i][2]] ̸ = Unknown] ∧ (v[c[i][1]] ∨ v[c[i][2]]) ∨ 1[g a = ¬] ∧ 1[v[c[i][1]] ̸ = Unknown] ∧ (¬v[c[i][1]]) ∨ 1[g a ∈ {0, 1}] ∧ g a ∨ Unknown ∧ 1[g a ∈ {∨, ∧}] ∧ 1[Unknown ∈ {v[c[i][1]], v[c[i][2]]}] ∨ 1[g a = ¬] ∧ 1[v[c[i][1]]] = Unknown . (F.2)Furthermore, we can express s ′ = (c ′ , v ′ ), the output of the transition kernel, asc ′ = c, v ′ [i] = (ō[a] ∧ 1[i = a]) ∧ (v[i] ∧ 1[i ̸ = a]),which implies that the transition kernel of CVP MDP can be computed by AC 0 circuits. Optimal Policy. Based on our construction of CVP MDP, it is not difficult to see that π* 1 = π * 2 = • • • = π * H .For simplicity, we omit the subscript and use π * to represent the optimal policy. Intuitively, the optimal policy is that given a state s = (c, v), we find the nodes with the smallest index among the nodes whose inputs have been computed and output has not been computed. Formally, this optimal policy can be expressed as follows. Given a state s = (c, v), denoting c[i] = (c[i][1], c[i][2], g i ), let G(s) be a set defined by: G(s) ={i ∈ [n] | g i ∈ {∧, ∨}, v[c[i][1]], v[c[i][2]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [n] | g i = ¬, v[c[i][1]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [n] | g i ∈ {0, 1}, v[i] = Unknown}. (F.3)The set G(s) defined in (F.3) denotes the indices for which inputs have been computed, and the output has not been computed. Consequently, the optimal policy π * (s) is expressed as π * (s) = min G(s) .If the output of the circuit c is 1, the policy π * can always get the reward 1, establishing its optimality.And if the output of circuit c is 0, the optimal value is 0 and π * is also optimal. Therefore, we have verified that the π * = min G(s) defined by us is indeed the optimal policy. Subsequently, we aim to demonstrate that the computational complexity of π * resides within AC 0 . Let Υ[i] denote the indicator of whether i ∈ G(s), i.e., Υ[i] = 1 signifies that i ∈ G(s), while Υ[i] = 0 denotes that i / ∈ G(s). According to (F.3), we can compute Υ[i] as follows:Υ[i] = 1[g i ∈ {∧, ∨}] ∧ 1[v[c[i][1]], v[c[i][2]] ∈ {0, 1}] ∧ 1[v[i] = Unknown] ∨ 1[g i = ¬] ∧ 1[v[c[i][1]] ∈ {0, 1}] ∧ 1[v[i] = Unknown] ∨ 1[g i ∈ {0, 1}] ∧ 1[v[i] = Unknown] .Under this notation, we arrive at the subsequent expression for the optimal policy π * :π * (s) = i∈[n] (Υ ′ [i] ∧ i), where Υ ′ [i] = ¬ j<i Υ[j] ∧ Υ[i].Therefore, the computation complexity of the optimal policy falls in AC 0 .Optimal Value Function. We prove that the computation of the value function of CVP MDP is P-complete under the log-space reduction. Considering that the reward in a CVP MDP is constrained to be either 0 or 1, we focus on the decision version of the optimal value function computation. Given a state s = (c, v) and an action a as input, the objective is to determine whether Q * 1 (s, a) = 1. In the subsequent two steps, we demonstrate that this problem is within the complexity class P and offer a log-space reduction from a known P-complete problem (CVP problem) to this decision problem.Step 1. We first verify the problem is in P. According to the definition, a state s = (c, v) can get the reward 1 if and only if the output of c is 1. A natural algorithm to compute the value of the circuit c is computing the values of nodes with the topological order. The algorithm runs in polynomial time, indicating that the problem is in P.Step 2. Then we prove that the problem is P-complete under the log-space reduction. According to Lemma I.2, the CVP problem is P-complete. Thus, our objective is to provide a log-space reduction from the CVP problem to the computation of the optimal value function for the CVP MDP. Given a circuit c of size n and a vector v unkown containing n Unknown values, consider s = (c, v unkown ). Let i = π * (s), where the optimal policy π * is defined in the proof of the "optimal policy function" part. The output of c is 1 if and only if Q * 1 (s, i) = 1. Furthermore, the reduction is accomplished by circuits in AC 0 and, consequently, falls within L.Combining these two steps, we know that computing the optimal value function is P-complete under the log-space reduction.Proof of Theorem 4.5. We characterize the representation complexity of the reward function, transition kernel, optimal policy, and optimal value function in P MDPs in sequence.Reward Function. We prove that the reward function of P MDP can be computed by AC 0 circuits. According to the definition, the output isr(s, a) = 1[v[P (n)] = 1].So the complexity of the reward function falls within the complexity class AC 0 .Transition Kernel. First, we prove that the transition kernel of P MDP can be computed by AC 0 circuits. Given a state-action pair (s = (x, c, v), a), we denote the next state P(s, a) by s ′ = (x ′ , c ′ , v ′ ). Similar to (F.1) in the proof of Theorem 4.2, we can fetch the node c[i], its value v[i], and the i-th character of the input string x[i]. We need to compute the output of the a-th node. Given the node c[a] and its inputs v[c[a] [1] ] and v[c[a] [2] ] or x[c[a] [1] ], we can compute the a-th node's value ō[a] similar to (F.2), where ō[a] is the correct output of the a-th node if the inputs are computed, and is Unknown when the inputs of the a-th node contain the Unknown value. In detail, ō can be computed as Here, ō[a] can be computed as:ō[a] = 1[g a = ∧] ∧ 1[v[c[i][1]], v[c[i][2]] ̸ = Unknown] ∧ (v[c[i][1]] ∧ v[c[i][2]]) ∨ 1[g a = ∨] ∧ 1[v[c[i][1]], v[c[i][2]] ̸ = Unknown] ∧ (v[c[i][1]] ∨ v[c[i][2]]) ∨ 1[g a = ¬] ∧ 1[v[c[i][1]] ̸ = Unknown] ∧ (¬v[c[i][1]]) ∨ 1[g a = Input] ∧ x[c[i][1]] ∨ Unknown ∧ 1[g a ∈ {∨, ∧}] ∧ 1[Unknown ∈ {v[c[i][1]], v[c[i][2]]}] ∨ 1[g a = ¬] ∧ 1[v[c[i][1]]] = Unknown . (F.4)Then the next state s ′ = (x ′ , c ′ , v ′ ) can be expressed asx ′ = x, c ′ = c, v ′ [i] = (o[a] ∧ 1[i = a]) ∧ (v[i] ∧ 1[i ̸ = a]),which yields that the transition kernel of P MDP can be computed by AC 0 circuits.Optimal Policy. Given a state s = (x, c, v), the optimal policy finds the nodes with the smallest index among the nodes whose inputs have been computed and output has not been computed. To formally define the optimal policy, we need to introduce the notation G(s) to represent the set of indices of which inputs have been computed and output has not been computed. Given a states = (x, c, v), denoting c[i] = (c[i][1], c[i][2], g i ),the set G(s) is defined by:G(s) ={i ∈ [P (n)] | g i ∈ {∧, ∨}, v[c[i][1]], v[c[i][2]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [P (n)] | g i = ¬, v[c[i][1]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [P (n)] | g i = Input, v[i] = Unknown}. (F.5)Under this notation, we can verify that the optimal policy is given by π * (s) = min G(s). Here we omit the subscript and use π * to represent the optimal policy since π* 1 = π * 2 = • • • = π * H .Specifically, (i) if the output of the circuit c is 1, the policy π * can always get the reward 1 and is hence optimal; (ii) if the output of circuit c is 0, the optimal value is 0 and π * is also optimal. Therefore, our objective is to prove that the computation complexity of π * falls in AC 0 . Let Υ[i] be the indicator of whether i ∈ G(s), i.e.Υ[i] = 1 indicates that i ∈ G(s) and Υ[i] = 0 indicates i / ∈ G(s). By the definition of G(s) in (F.5), we can compute Υ[i] as follows:Υ[i] = 1[g i ∈ {∧, ∨}] ∧ 1[v[c[i][1]], v[c[i][2]] ∈ {0, 1}] ∧ 1[v[i] = Unknown] ∨ 1[g i = ¬] ∧ 1[v[c[i][1]] ∈ {0, 1}] ∧ 1[v[i] = Unknown] ∨ 1[g i = Input] ∧ 1[v[i] = Unknown] .Then, we can express the optimal policy asπ * (s) = i∈[P (n)] ( Υ ′ [i] ∧ i) where Υ ′ [i] = ¬ j<i Υ[j] ∧ Υ[i].Therefore, the computational complexity of the optimal policy falls in AC 0 .Optimal Value Function. We prove that the computation of the value function of P MDP is Pcomplete under the log-space reduction. Note that the reward of the P MDP can be only 0 or 1, we consider the decision version of the problem of computing the optimal value function as follows: given a state s = (x, c, v) and an action a as input, the goal is determining whether Q * 1 (s, a) = 1. we need to prove that this problem belongs to the complexity class P and then provide a log-space reduction from a recognized P-complete problem to this problem.Step 1. We first verify the problem is in P. According to the definition, a state s = (x, c, v) can get the reward 1 if and only if the output of c is 1. A natural algorithm to compute the value of the circuit c is computing the values of nodes according to the topological order. This algorithm runs in polynomial time, showing that the target decision problem is in P.Step 2. Then we prove that the problem is P-complete under the log-space reduction. Under the condition that L is P-complete, our objective is to provide a log-space reduction from L to the computation of the optimal value function for the P MDP. By Lemma I.3, a language in P has logspace-uniform circuits of polynomial size. Therefore, there exists a Turing Machine that can generate a description of a circuit c in log-space which can recognize all strings of length n in L. Therefore, given any input string x of length n, we can find a corresponding state s = (x, c, v unknown ), where v unknown denotes the vector containing P (n) Unknown values. Let i = π * (s), where π * is the optimal policy defined in the "optimal policy" proof part. Then x ∈ L if and only if Q * 1 (s, i) = 1. This provides a desired log-space reduction. We also want to remark that here the size of reduction circuits in L should be smaller than P (n). This condition can be easily satisfied since we can always find a sufficiently large polynomial P (n).Combining the above two steps, we can conclude that computing the optimal value function is P-complete.Embeddings for the 3-SAT MDP. The state of the n dimension 3-SAT MDP s = (ψ, v, k). We can use an integer ranging from 1 to 2n to represent a literal from V = {u 1 , ¬u 1 , • • • , u n , ¬u n }. For example, we can use (i, i + n) to represent (u i , ¬u i ) for any i ∈ [n]. Therefore, we can use a 3n dimensional vector e ψ to represent the ψ ∈ V 3n and a 4n + 1 dimensional vector e s = (e ψ , v, k) to represent the state s = (ψ, v, k). And we use a scalar to represent the action a ∈ {0, 1}.Embeddings for the NP MDP. The state of the n-dimension NP MDP is denoted as s = (c, k). A configuration of a non-deterministic Turing Machine, represented by c, encompasses the state of the Turing Machine s M , the contents of the tape t, and the pointer on the tape l. To represent the state of the Turing Machine, the tape of the Turing Machine, and the pointer, we use an integer, a vector of P (n) dimensions, and an integer, respectively. Therefore, a P (n) + 2 dimensional vector e c is employed to represent the configuration, and a P (n) + 3 dimensional vector e s = (e c , k) is used to represent the state s = (c, k). Additionally, a scalar is utilized to represent the action a ∈ {0, 1}.Embeddings for the CVP MDP. The state of the n-dimension CVP MDP is denoted as s = (c, v). Utilizing a 3 dimensional vector, we represent a node c[i] of the circuit. Consequently, a 3n dimensional vector e c is employed to represent the circuit c, and a 4n dimensional vector e s = (e c , v) is used to represent the state s = (c, v). In this representation, an integer ranging from 1 to n is used to signify the node index, an integer ranging from 1 to 5 is employed to denote the type of a node, and an integer ranging from 1 to 3 is utilized to represent the value of a node. Additionally, a scalar is used to represent the action a ∈ [n].Embeddings for the P MDP. The state of the n dimensional P MDP is denoted as s = (x, c, v). Assuming the upper bound of the size of the circuit is P (n), similar to the previous CVP MDP, a 3P (n)-dimension vector e c is employed to represent the circuit c. Meanwhile, a P (n) dimensional vector v is used to represent the value vector of the circuit, and a n dimensional vector x represents the input string. In this representation, an integer is used to denote the character of the input, the index of the circuit, the value of a node, or the type of a node. Therefore, a 4P (n) + n dimensional vector e s = (x, e c , v) is used to represent the state s = (x, c, v). Additionally, a scalar is used to represent the action a ∈ [P (n)].Proof of Theorem 5.2. We show that the model, encompassing both the reward and transition kernel, of both 3-SAT MDPs and NP MDPs can be represented by MLP with constant layers for each respective case.Reward Function of 3-SAT MDP. First of all, we will prove that the reward function of 3-SAT MDP can be implemented by a constant layer MLP. Denoting the input e 0 = (e s , a) = (e ψ , v, k, a), which embeds the state s = (ψ, v, k) and the action a. For the clarity of presentation, we divide the MLP into three modules and demonstrate each module in detail.Module 1. The first module is designed to substitute the variable in ψ. Let ψ ′ be the formula obtained from ψ by substituting all variables and containing only Boolean value. Recall that we use [2n] to represent {u 1 , ¬u 1 , • • • , u n , ¬u n }. We define a 2n dimensional vector v such that, for anyliteral τ ∈ {u 1 , ¬u 1 , • • • , u n , ¬u n }, v[τ ] = v[i] if τ = u i and v[τ ] = ¬v[i] if τ = ¬u i . Hence, given a literal τ ∈ [2n], we can get its value v[τ ] by v[τ ] = ReLU i∈[n] ReLU(v[i] + 1[τ = u i ] -1) + i∈[n] ReLU(1[τ = ¬u i ]) -v[i] .According to Lemma I.5, the function 1[τ = u i ] and 1[τ = ¬u i ] can be implemented by the constant layer MLP of polynomial size. So we can get the output of Module 1, which ise 1 = (e ψ ′ , v, k, a).Module 2. The next module is designed to compute the value of ψ ′ . Given the value of each literal α i,j we can compute the value of ψ ′ , i.e., ψ(v), by the following formula:ψ(v) = ReLU i∈[n]ReLU(α i,1 + α i,2 + α i,3 ) -ReLU(α i,1 + α i,2 + α i,3 -1) -n + 1 .So we can get the output of Module 2, which is e 2 = (ψ(v), k, a). Module 3. The last module is designed to compute the final output r(s, a). Given the input e 2 = (ψ(v), k, a), we can compute the output r(s, a) byr(s, a) = 1[ψ(v) ∧ (k = n + 1)] + 0.5 • 1[k = 2n + 2].While the input can take on polynomial types of values at most, according to Lemma I.5, we can use the MLP to implement this function. Therefore, we can use a constant layer MLP with polynomial hidden dimension to implement the reward function of n dimension 3-SAT MDP.Transition Kernel of 3-SAT MDP. We can use a constant layer MLP with polynomial hidden dimension to implement the transition kernel of 3-SAT MDP. Denote the input e 0 = (e s , a) = (e ψ , v, k, a), which embeds the state s = (ψ, v, k) and the action a. We only need to modify the embeddings v and k and denote them as v ′ and k ′ . According to (E.1) in the proof of the transition kernel of Theorem 3.3, we have the output v ′ and k of the following form:e ′ ψ = e ψ , v ′ [i] = (v[i] ∧ 1[i ̸ = k]) ∨ (a ∧ 1[i = k]), k ′ = (k + 1) • 1[k ≥ 1] + 1[k = 0 ∧ a = 1] + (n + 2) • 1[a = k = 0]. (G.1)In (G.1), each output element is determined by either an element or a tuple of elements that have polynomial value types at most. Therefore, according to Lemma I.5, each output element can be computed by constant-layer MLP of polynomial size, and the overall output can be represented by a constant layer MLP of polynomial size. which embeds the state s = (c, v) and the action a. Given an index i, we can fetch the node i and its value byv[i] = j∈[n] α i,j , where α i,j = 1[i = j] • v[i], c[i] = j∈[n] β i,j , where β i,j = 1[i = j] • c[i]. (G.2)Then, compute the output of node i and denote it as o[i]. o[i] is determined by the i-th node c i and its input, therefore, can be computed by a constant layer MLP with polynomial hidden dimension according to Lemma I.5. Denoting the output as (e ′ c , v ′ ), according to the definition of the transition kernel, we havee ′ c = e, v[i] ′ = v[i] • 1[i ̸ = a] + v[i] • 1[i = a]Therefore, we can compute the transition kernel of CVP MDP by a constant layer MLP with polynomial hidden dimension.Optimal Policy of CVP MDP. We prove that the MLP can implement the optimal policy, which is specified in the proof of Theorem 4.2 (Appendix F.1). For the convenience of reading, we present the optimal policy here again. Given a state s = (c, v), denoting c[i] = (c[i][1], c[i][2], g i ), we define G(s) G(s) ={i ∈ [n] | g i ∈ {∧, ∨}, v[c[i][1]], v[c[i][2]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [n] | g i ∈ {¬}, v[c[i][1]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [n] | g i ∈ {0, 1}, v[i] = Unknown}. (G.3)The set G(s) defined in (G.3) denotes the indices for which inputs have been computed, and the output has not been computed. Consequently, the optimal policy π * (s) is expressed as π * (s) = min G(s) . Subsequently, we aim to demonstrate that a constant-layer MLP with polynomial hidden dimension can compute the optimal policy π * . Let Υ[i] denote the indicator of whether i ∈ G(s), i.e., Υ[i] = 1 signifies that i ∈ G(s), while Υ[i] = 0 denotes that i / ∈ G(s). According to (G.3), we can compute Υ[i] depends on the i-th node c[i], its inputs and output, therefore, can be computed by a constant-layer MLP with polynomial hidden dimension. Then we can express the optimal policy π * as:π * (s) = ReLU i∈[n] Υ ′ [i] ,whereΥ ′ [i] = ReLU 1 - j<i Υ[j] .Therefore, we can compute the optimal policy by a constant-layer MLP with polynomial size. which embeds the state s = (x, c, v) and the action a. We can fetch the node i and its value by (G.2). Then we compute the output of node i and denote it as o[i], where o[i] is determined by the i-th node c[i] and its inputs. Hence, by Lemma I.5, o[i] can be computed by a constant-layer MLP with polynomial hidden dimension. Denoting the output as (x ′ , e ′ c , v ′ ), together wths the definition of the transition kernel, we havex ′ = x, e ′ c = e c , v ′ [i] = v[i] • 1[i ̸ = a] + v[i] • 1[i = a].Therefore, we can compute the transition kernel of P MDP by a constant layer MLP with polynomial hidden dimension.Optimal Policy of P MDP. We prove that the MLP can efficiently implement the optimal policy in the proof of Theorem 4.5 (Appendix F.2). For completeness, we present the definition of optimal policy here. Given a state s = (x, c, v), denoting cEQUATION], g i ), let G(s) be a set defined by:G(s) ={i ∈ [P (n)] | g i ∈ {∧, ∨}, v[c[i][1]], v[c[i][2]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [P (n)] | g i = ¬, v[c[i][1]] ∈ {0, 1}, v[i] = Unknown} ∪ {i ∈ [P (n)] | g i = Input, v[i] = Unknown}. (G.4)The set G(s) defined in (G.4) denotes the indices for which inputs have been computed, and the output has not been computed. With this set, the optimal policy π * (s) is expressed as π * (s) = min G(s) . Subsequently, we aim to demonstrate that a constant-layer MLP with polynomial hidden dimension can compute the optimal policy π * . Let Υ[i] denote the indicator of whether i ∈ G(s), i.e., Υ[i] = 1 signifies that i ∈ G(s), while Υ[i] = 0 denotes that i / ∈ G(s). Using (G.4), the computation of Υ[i] depends on the i-th node c i , its inputs, and output. This observation, together with Lemma I.5, allows for the computation through a constant-layer MLP with polynomial hidden dimension. Employing this notation, we can formulate the following MLP expression for the optimal policy π * :π * (s) = ReLU i∈[P (n)] Υ ′ [i] ,whereΥ ′ [i] = ReLU 1 - j<i Υ[j] .Therefore, the optimal policy of P MDP can be represented by a constant-layer MLP with polynomial hidden dimension.G.5 Proof of Theorem 5.5Proof of Theorem 5.5. By Lemma I.7, we have that the computational complexity of MLP with constant layer, polynomial hidden dimension (in n), and ReLU as the activation function is upperbounded by TC 0 . On the other hand, by Theorem 4.2 and 4.5, the computation of the optimal value Function of CVP MDP and P MDP is P-complete. Therefore, we conclude the proof under the assumption of TC 0 ̸ = P. . one can choose the observation as a substring of the state, and the representation complexity of the emission function remains low, similar to the transition kernel. However, the optimal policy and optimal value function may depend on the full history rather than just the current state, leading to a higher representation complexity for these two quantities. Consequently, in the presence of partial observations, the representation complexity gap between model-based RL and model-free RL could be more pronounced.In this section, we demonstrate how our construction of the 3-SAT MDP, NP MDP, CVP MDP, and P MDP can be seamlessly extended to their stochastic counterparts. We offer a detailed extension of the 3-SAT MDP to its stochastic version and outline the conceptual approach for extending other types of MDPs to their stochastic counterparts.Stochastic 3-SAT MDP. First, we add some randomness to the transition kernel and reward function. Moreover, to maintain the properties in Theorem 3.3, Theorem 5.3, and Theorem 5.2 of 3-SAT MDP, we slightly modify the action space and extend the planning horizon. Definition H.1 (Stochastic 3-SAT MDP). For any n ∈ N + , let V = {u 1 , ¬u 1 , • • • , u n , ¬u n } be the set of literals. An n-dimensional stochastic 3-SAT MDP (S, A, H, P, r) is defined as follows. The state space S is defined byS = V 3n × {0, 1, Next} n × ({0} ∪ [n + 2]), where each state s can be denoted as s = (ψ, v, k). In this representation, ψ is a 3-CNF formula consisting of n clauses and represented by its 3n literals, v ∈ {0, 1} n can be viewed as an assignment of the n variables and k is an integer recording the number of actions performed. The action space is A = {0, 1} and the planning horizon is H = n 2 + n + 2. Given a state s = (ψ, v, k), for any a ∈ A, the reward r(s, a) is defined by:r(s, a) =    1 If v is a satisfiable assignment of ψ, k = n + 1 and a = Next, 1 2 If k = n 2 + 2n + 2, 0 Otherwise. (H.1)Moreover, the transition kernel is stochastic and takes the following form:EQUATIONwhere v ′ is obtained from v by setting the k-th bit as a with probability 2 3 and as 1-a with probability v ′ [k ′ ] = v[k ′ ] for k ′ ̸ = k.Given a 3-CNF formula ψ, the initial state of the 3-SAT MDP is (ψ, 0 n , 0). Theorem H.2 (Representation complexity of Stochastic 3-SAT MDP). Let M n be the n-dimensional stochastic 3-SAT MDP in Definition H.1. The transition kernel P and the reward function r of M n can be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC 0 . However, computing the optimal value function Q * 1 and the optimal policy π * of M n are both NP-hard under the polynomial time reduction.Proof of Theorem H.2. We investigate the representation complexity of the reward function, transition kernel, optimal value function, and optimal policy in sequence.Reward Function. The reward function is the same as the deterministic version, therefore, we can apply the proof of Theorem 3.3 and conclude that the complexity of the reward function falls in AC 0 .Transition Kernel. Then, we will implement the transition kernel by AC 0 circuits. Slightly different from the deterministic version, in this case, the input of the transition kernel P are two states s = (ψ, v, k), s ′ = (ψ ′ , v ′ , k ′ ) and action a, and the output is the probability of transition from s to s ′ . Given the input v, k, v ′ , k ′ and a, we have the output as follows:• The output is 1 if the input satisfies the following four equations:a = Next, v = v ′ , ψ = ψ ′ , k ′ = (k + 1) • 1[k ≥ 1] + 1[k = 0 ∧ a = 1] + (n + 2) • 1[a = k = 0].• The output is 2 3 if the input satisfies the following four equations:a ∈ {0, 1}, k = k ′ , ψ = ψ ′ , v ′ [i] = (v[i] ∧ 1[i ̸ = k]) ∨ (a ∧ 1[i = k]).• The output is 1 3 if the input satisfies the following four equations:a ∈ {0, 1}, k = k ′ , ψ = ψ ′ , v ′ [i] = ¬(v[i] ∧ 1[i ̸ = k]) ∨ (a ∧ 1[i = k]).• The output is 0 otherwise.It is noted that each element in the previous equations is determined by at most O(log n) bits. Therefore, according to Lemma I.4, the condition judgments can be computed by two-layer circuits of polynomial size, and the overall output can be computed by AC 0 circuits.Optimal Value Function. Next, we will prove the NP-hardness of computing the optimal value function. Similar to the optimal value function part of the proof of Theorem 3.3, we formulate a simpler decision version of this problem: given a state s = (ψ, v, k), an action a and a number γ as input, and the goal is to determine whether Q * 1 (s, a) > 1 2 . According to the well-known Cook-Levin theorem (Lemma I.1), the 3-SAT problem is NP-complete. Thus, our objective is to provide a polynomial time reduction from the 3-SAT problem to the computation of the optimal value function for the 3-SAT MDP. Given a Boolean formula of length n, the number of variables is at most n. Then, we can pad several meaningless clauses such as (u 1 ∨ ¬u 1 ∨ u 1 ) to obtain the 3-CNF Boolean formula ψ ′ with n clauses. When the Boolean formula ψ is not satisfiable, the value of Q * 1 ((ψ ′ , 0 n , 0), 1) is 0. When the Boolean formula ψ is satisfiable, we will prove that the probability of the reward 1 is higher than 1 2 . Note that, when ψ is satisfiable, we only need to modify the values of the variables at most n times to get a satisfiable assignment in the deterministic case. In the stochastic case, we have n 2 chances to modify the value of a variable with a success probability of 2 3 , and to get the reward, we only need n times success. Therefore, we can compute the probability of getting the reward as Pr(n times success in n 2 chances) ≥ Pr(one success in n chances)n = 1 - 1 3 n n > 1 - 1 2n n ≥ 1 2 . (H.3)Therefore, ψ is satisfiable if and only if Q * 1 ((ψ ′ , 0 n , 0), 1) > 1 2 , we can conclude that computing the optimal value function is NP-hard.Optimal Policy. Finally, we will prove that the problem of computing the optimal policy is NP-hard. According to the well-known Cook-Levin theorem (Lemma I.1), the 3-SAT problem is NP-complete. Thus, our objective is to provide a polynomial time reduction from the 3-SAT problem to the problem of computing the optimal policy of 3-SAT MDP. Given a Boolean formula of length n, the number of variables is at most n. Then, we can pad several meaningless clauses such as (u 1 ∨ ¬u 1 ∨ u 1 ) to obtain the 3-CNF Boolean formula ψ ′ with n clauses. When the Boolean formula ψ is satisfiable, according to (H.3), we have Q * 1 ((ψ ′ , 0 n , 0), 1) > 0.7 > Q * 1 ((ψ ′ , 0 n , 0), 0), which gives that π * (ψ ′ , 0 n , 0) = 1. When the Boolean formula ψ is not satisfiable, we have Q * 1 ((ψ ′ , 0 n , 0), 1) = 0 < Q * 1 ((ψ ′ , 0 n , 0), 0), which implies that π * (ψ ′ , 0 n , 0) = 0. So the Boolean formula ψ is satisfiable if and only if π * (ψ ′ , 0 n , 0) = 1, which concludes that the problem of computing the optimal policy is NP-hard.Almost the same as the stochastic version of 3-SAT MDP, we can construct the stochastic version NP MDP. And under the assumption of L ∈ NP, the same theorem as Theorem H.2 will hold. More exactly, the complexity of the transition kernel and the reward function of the MDP based on L fall in AC 0 , and the complexity of the optimal policy and optimal value function are NP-hard. Moreover, similar to the case of the stochastic version of 3-SAT MDP, we add some randomness to the transition function of CVP MDP and P MDP. In the deterministic version of the transition function, given the action i, we will compute the value of the i-th node. In contrast, the computation of the value of i-th node will be correct with the probability of 2 3 and will be incorrect with the probability of 1 3 .By definition, we can verify that f (u) = c(u) for any u ∈ {0, 1} l . When f (u) = 0 for all u ∈ {0, 1} l , we can construct the circuit as c(u) = 0. Therefore, for every Boolean function f : {0, 1} l → {0, 1}, there exists a two-layer circuit c of size O(l • 2 l ) such that c(u) = f (u) for all u ∈ {0, 1} l , which concludes the proof of Lemma I.4.Lemma I.5 (Looking-up Table for MLP). For any function f : X → R, where X is a finite subset of R l , there exists a constant-layer MLP f MLP with hidden dimension O(l • |X |) such that f M (x) = f (x) for all x ∈ X .Proof. Denote the minimum gap between each pair of elements in X by δ min , i.e., δ min = min u,v∈X ∥u -v∥ ∞ .For each u ∈ X , we can construct an MLP asf u (x) = ReLU i∈[l] f u,i (x) -(l -1) • δ min ,wheref u,i (x) = ReLU 2δ min -2 • ReLU(x[i] -u[i]) -ReLU(u[i] -x[i] + δ min ) .We havef u (x) = δ min If x = u, 0 If x ∈ X \{u}.Then we can construct the MLP f MLP asf MLP (x) = u∈S f u (x) δ min • f (u) .It is easy to verify that f MLP (x) = f (x) for all x ∈ X , which concludes the proof of Lemma I.5.Lemma I.6 (MLP can Implement Basic Gates in TC 0 ). Given x ∈ {0, 1} n as input, constant-layer MLPs can implement the following basic operation functions:• AND: f AND (x) = i∈[n] x[i];• OR: f OR (x) = i∈[n] x[i];• NOT: f NOT (x[1]) = 1 -x[1];• Majority:f MAJ (x) = 1[ i∈[n] x[i] > n 2 ].Proof. We express the four functions in the MLP forms as follows:• f AND (x) = ReLU( i∈[n] x[i] -n + 1);• f OR (x) = 1 -ReLU(1 -i∈[n] x[i]); • f NOT (x[1]) = 1 -x[1]; • f MAJ (x) = ReLU(2 • i∈[n] x[i] -n) -ReLU(2 • i∈[n] x[i] -n -1).Therefore, the basic gates of TC 0 can be implemented by constant-layer MLPs with ReLU as the activation function.Lemma I.7 (Upper Bound of Expressive Power for MLP). Any log-precision MLP with constant layers, polynomial hidden dimension (in the input dimension), and ReLU as the activation function can be simulated by a L-uniform TC 0 circuits.Proof. In the previous work by [36] , it was demonstrated that a Transformer with logarithmic precision, a fixed number of layers, and a polynomial hidden dimension can be simulated by a L-uniform TC 0 circuit. The proof presented by [36] established the validity of this result specifically when the Transformer employs standard activation functions (e.g., ReLU, GeLU, and ELU) in the MLP. Considering that the MLP can be perceived as a submodule of the Transformer, it follows that a log-precision MLP with a consistent number of layers, polynomial hidden dimension, and ReLU as the activation function can be simulated by a L-uniform TC 0 circuit.• If the paper includes experiments, a No answer to this question will not be 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.Throughout this paper, we use the term model-free RL to include both policy-based RL and value-based RL.Our results in this section are ready to be extended to other activation functions, such as Exponential Linear Unit (ELU), Gaussian Error Linear Unit (GeLU) and so on.Following the convention of computational complexity[3], we may use the term "language" and "decision problem" interchangeably. 


Decision: The paper analyzes a hierarchy of representation complexity in RL. The reviewers found the paper difficult to read and sometimes needed the help of the authors in identifying key information in the appendices. The authors and reviewers have engaged in a number of rounds of rebuttal, and the reviewers have proposed to accept the paper conditioned that the authors address the nuances discussed in appendix C with a more prominent space in the main paper. Conditioned on addressing this issue, we recommend acceptance as a poster. 
Thank you

Reviews: review: paper_summary: paper_summary: This paper delves into the representation complexity in different RL paradigms. It focuses on the function class needed to represent the underlying model, optimal policy, or optimal value function.
strength_weakness: strength_weakness: See questions.
questions: questions: I apologize for my limited familiarity with the representation complexity area. I have read the paper thoroughly and examined the theorems. I appreciate your work, but I feel I cannot make a solid judgment. So if my questions are off the mark, please correct me.

1. Are the findings regarding the representation complexity hierarchy consistent across a wide range of task settings, or do they vary significantly with different types of tasks?
2. Can you provide case studies or real-world examples for understanding the representation complexity hierarchy that has led to improved sample efficiency in practical applications? I understand you have provided some explanations in the paper. If this question adds extra burden, feel free to disregard it.
limitations: limitations: The authors do not have an explicit limitations section or paragraph.
paper_summary: paper_summary: This paper delves into understanding the inherent representation complexities associated with three different RL categories: model-based RL, policy-based RL, and value-based RL. By studying computational complexity theory and neural networks, MLP, the paper posits a hierarchy in which representing the underlying model is the simplest, followed by the optimal policy, and finally, the optimal value function, which is the most complex to represent. Theoretical analyses and empirical results support these claims.
strength_weakness: strength_weakness: - While the theoretical insights are significant, the paper does not extensively explore their direct implications for real-world RL applications.
- Previous experiments show model-based RL is more sample-efficient than model-free RL, aligning with this paper's finding that representing the dynamic model is easier. However, as training progresses, model-free methods often outperform model-based ones. Could the theories in the paper explain this? While the policy is more challenging to represent initially, it allows model-free methods to optimize more efficiently once learned. 
- Could the proposed hierarchy of representation complexity be applied to other types of neural network architectures beyond MLPs, such as transformers?
questions: questions: Please answer the points mentioned in the weaknesses.
limitations: limitations: The paper does not discuss their limitations.
paper_summary: paper_summary: This paper studies three RL paradigms: model-based RL, policy-based RL, and value-based RL from the perspective of representation complexity. The authors demonstrate that representing the model emerges as the easiest task, followed by the optimal policy, with the optimal value exhibiting the highest representation complexity.
strength_weakness: strength_weakness: - From the perspective of MLP, using simple 2 or 3-layer MLPs to calculate approximation error to validate conclusions provides limited insights for modern deep RL.
- Although it is a theory paper, I would have liked to see more experiments designed to validate the conclusions.
questions: questions: - Intuitively, could you explain in detail the fundamental reasons for the different representation complexities of the optimal policy and optimal value function under different settings in Sec. 3 and Sec. 4?
- Maybe you should describe more examples to intuitively understand the representation complexity of the model, optimal policy, and optimal value function.
limitations: limitations: The paper is mainly theoretical, and no algorithm is implemented. There is no specific potential negative societal impact of this work.
paper_summary: paper_summary: The paper presents an analysis of the representation complexity, the necessary complexity of a circuit, between different paradigms in reinforcement learning. The authors show, with several reductions to well-known theoretical complexity classes, that MDPs exist in which representing a model is "easy" while representing a value function or policy is "hard".
strength_weakness: strength_weakness: I have one major confusions which I list under questions since these are hopefully easily addressable in the rebuttal.

I think the problem of the "strictness" of the hierarchy should be very carefully addressed. It only weakens the conclusion, all the proofs are correct as far as I was able to verify, but I would encourage the authors to engage carefully. This is my main reason for recommending rejection: I think the works is interesting and meaningful, but the conclusion seems wrong due to the problem outlined below. I am very happy to discuss this point in the rebuttal and raise my scores accordingly if appropriate.
questions: questions: The authors explicitly call the studied phenomenon a hierarchy, but I am uncertain if this is actually true. It seems intuitive that their should be MDPs in which the situation is reversed: representing the value function is easy, while representing the full model is difficult. This seems especially true if we don't talk about strict error free representation, but allow for errors. One intuitive reason for me to conjecture this is the existence of an arbitrarily complex model (i.e. one that transitions from a 3-SAT formula with a high likelihood to one of two states depending on the formula is satisfiable or not) but with 0 reward and therefore a trivial value function as well. I think this is my biggest problem with the paper so far: the construction implies the existence of one direction for the hierarchy, but does not imply that the other direction cannot exist.

This also makes the empirical section a bit more difficult: Why should we assume that the Mujoco locomotion environments fall into the category of problems described in the paper and not into the alternative? Empirically this seems to be true. Is there some reason to believe that "realistic" MDPs will exhibit this complexity relationship more, or is this an artifact of the choice of environments?

Other, minor issues:
- All figures are barely legible at a "reasonable" zoom level, I would encourage the authors to quickly redesign these.
limitations: limitations: See above

Comments: title: Answer
Thank the authors for the rebuttal!
comment: Thank you for your detailed response to my review. The authors' rebuttal has addressed some of my concerns. My intuition remains in favor of acceptance, though my limited knowledge in the area of representation complexity.
Dear reviewer,

Thank you again for reviewing our paper. As the discussion period ends soon, we'd like to know if our response has adequately addressed your concerns. If not, we're happy to provide further clarification. We greatly appreciate your time and support.

Best,
Authors
We are happy to hear that we've addressed your concerns. Thank you for your valuable time reviewing our paper.
Thank you for taking the time to read our response and update the score. We appreciate your feedback and will certainly follow your suggestions to polish our paper.
Dear authors, thanks for the clarifications. I acknowledge that I missed the discussion in appendix C, I feel like this is a very important point that might deserve some more prominent space in the main paper.

I still don't fully agree with the argument: the benchmarks are investigated here are all designed to have little to no task irrelevant features such as distractions. Generalizing from these to RL problems in general seems like it can mislead the community. The results also violate a lot of commonly held intuition: in many cases predicting the exact consequences of your actions is very hard, i.e. how many blades of grass are crushed by a step on the lawn, but from the perspective of any task, this is irrelevant. I wish I could provide a nice reference here, but I can't find one at the moment.

I don't have a problem at all with your formal statements and I do applaud the novel and insightful technique. My whole problem is with the nuance of the framing, which I do think is very important to get right to frame your (very interesting results) in the right way.

I am willing to increase my score provided you can give the nuance of this discussion some space in the main paper. Since I want to be an optimistic and constructive reviewer, I have updated my score to recommend acceptance, I hope you follow my concerns.
Thanks for the rebuttal! My concerns have been addressed, so I decide to keep my positive rating.
We are pleased that our response has addressed your concerns. Thank you for taking the time to review our paper.
Thank you for the detailed rebuttal! My concerns have been resolved.
Apologize again for my limited knowledge in your area.
Wish you good luck with this paper!