Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
Authors: Guhao Feng
Han Zhong
Venue: NeurIPS 2024 poster (2024)
Keywords: RL theory
representation complexity
model-based RL
policy-based RL
value-based RL
Primary area: reinforcement_learning
TL;DR: We uncover a potential representation complexity hierarchy among different RL paradigms, including model-based RL, policy-based RL, and value-based RL.

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.

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
Guhao Feng"
Han Zhong
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 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 Multi-Layer Perceptrons (MLPs), which align more closely with practical deep RL and contribute to a completely new perspective theoretical studying representation complexity RL. Finally, we conduct deep RL experiments to validate theoretical findings.
Introduction
The past few years have witnessed the tremendous success of Reinforcement Learning (RL) [43] in solving intricate real-world decision-makinn 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, 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 eтror [c.g., 2. 49, 9, 29] lenses, 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 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,
"Alphahetical order.
i School RECS, Peking University, Email: fenguhaodstu, .ku. edu. en "Center for Data Science, Peking University. Email: hanzhongtstu, www.:susuuuuuuuuuuu.o edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Computational Complexity
Expressiveness of Log-precision MI MLP/ Pransforme (constant layers and polynomial hidden dimension)
(time complexity and circuil complexity)
Model
AC
3-SAT MDP
Policy
WP-Complete
NP MDP
Value
NP-Complete
Model
AC
CVP MDP P MDP
Policy
AC
Value
P-Complete
Table I: A summary of our main results. v means that the function can be represented by log- precision MLP with constant layers and polynomial hidden dimension, while X 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 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 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.
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) pplicy-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.
Our Contributions.
To elucidate the representation complexity separation between model-based RL and model-free RL* 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" (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- 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. 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 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 determining optimal value functions.
To provide more practical insights, establish 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 ML.PTransformer 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 the optimal value, in contrast, faces limitations in its representation using M..Ps/Transformet 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.
with polynomial hidden dimension. However,
Throuuhhou this paper, we use the term model-free RL to include both pasicy-based RL and value-based RL.

---

In summary, our work unveils 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 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-effciint RI. 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 set by (X)). We use N and N., to denote the set of all natural numbers and positive integers, respectively. For any E N4, we denote [n] =1,,2 ... n and O,, (0,0. ................................
.1, 11.1....11
times
times
2 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), r). Here S is the state space, A is the action space, H is the length of each episode, P S x A + ((S) is the transition kernel, and S + [0. 1] is the reward function. Moreover, when the transition kernel is deterministic, say P(- s, a) = 6g for some s' S. we denote P(s, from the state space to the distribution over action space. For the deterministic policy Th satisfying (-(s = 5g for some a E .A, we denote Ta (s) a. Here 6₂ is the Dirae measure at a. Given a policy æ, for any (s, a) E S x A. we define the state value function and state sate-action value function (Q- function) as V. (s) F., =
s'. A policy π = {T,, S A(A) !1 consists of H mappings
Th The (Sp' axe) 8h. s). Q7 (s.a)= R E = T'v (shi, asr) 8h.
8, ah = a). Here the expectation E.[] is taken with respect to the randomness incurred by the policy and transition kernels. There exists an optimal policy n¹ achieves the highest value all timesteps
and states, i.e., V (s) sup, V. (s) for any h E [H] and S. For notation simplicity, the shorthands V/ V and Q = QT, for any h E [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 TC L, P, and NP. Here, L, P. and NP are defined in terms of the running time of Turing Machines (Definition B. B. while AC and TC 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 Ç TC C P c NP. The question of whether the relationship TC² C C NP holds as a striet inclusion remains elusive in theoretical computer science. However, it is widely conjectured that P NP and TC P are unlikely to be true.
3 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 model- free RL, which encompasses both policy- based RL. and value-based RL.
3.1 3-SAT MDP
As warmup example to showcase the separation between model-based RL and model-free RL, we propose the 3-SAT MDPs, whose construction closely linked to the well-known NP-complete problem 3-satisfiability (3-SAT), The formal definition of 3-SAT is as follows.
3

---

Vi
V
(Vaaa)
r=1
On
On
7=0
Yend
[Vaad =0
a |
0
action sequences
12 2
2n
Figure I: A visualization of 3-SAT MDPs. Here, v is an r--dimensional vector, Vo and V are vectors obtained by replacing the k-th element of v with 0 and 1, respectively. Additionally, Vend. Vend and Veen represent the assignments at the end of the episode.
Definition 3.1 (3-SAT Problem). A Boolean formula & over variables u1, U2. Un in the conjunctive normal form (3-CNF) if takes the form of conjunction of one or more disjunctions, each containing exactly literals. Here, literal refers either a variable the negation of variable. Formally, the 3-CNF formula zi has the form of & Aiez((n (ti,1 V 1122 V 0r,3), where I is the index set and Vi,; E {uA: ] for some & E [ni]. The 3-SAT problem is defined as follows: given a 3-CNF Boolean formula vh, judge whether assignment of variables such that the formula v evaluates to 1.
satisfiable. Here, "satisfiable" means that there exists
Now we present the detailed construction of 3-SAT MDPs.
Definition 3.2 (3-SAT MDP), For any T2 E N.. let V {u,, -. Uny un 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 y33 x {0, 1 1 x ({0) U [2n 2).. where each state s can be denoted as $ = (t. v, k). In this representation, // is 3-CNF formula consisting of n clauses and represented by its 3n literals, {0, 1}m be viewed number of actions performed. The action space A {0, 1} and the planning horizon is H n Given a state = (v, v. k), for any E A, the reward r(s, a) is defined by:
assignment of the variables and k:
integer recording the
If satisfiable and n
as),a)
0.5 If = 2n 2,
(3.1)
Otherwise.
Moreover, the transition kernel is deterministic and takes the following form:
(v, (0,nn+2
If k 0, Ifa = 1 and l: = 0,
v,
k,))), =
(3.2)
(v. +1)
If E [r]]
If n.
where v' obtained from by setting the k-th bit and leaving other bits unchanged, i.c.. v' vkk] and v'[k'] v[k'] for k' k. The initial state takes form (v), O,, 0) for any length-ni 3- 3-CNF formula v).
The visualization of 3-SAT MDPs is given in Figure 1. We assert that our proposed 3-SAT model relevant real-world problems. In the state (v, v, k), v characterizes intrinsic environmental factors that remain unchanged by the agent, while and & represent elements subject to the agent's influence. Notably, the agent capable changing O,, 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 & may represent aspects of the car that 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 sb is satisfiable, and the agent transforms O,, into a variable assignment that makes &b equal to through sequence of actions. The agent receives a reward of 0.5 if, at the first step, it determines that sb is unsatisfiable and chooses to "give up". Here, we refer to taking action O 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 better choice than investing sigmificant 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 Mn be the n- n-dimensional 3-SAT MDP Definition 3.2. The transition kernel and the reward function r of M,, can be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC However, computing the optimal value function Qi and the optimal policy कं of M,, are both NP-complete under the polynomial time reduction.
The proof of Theorem 3.3 is deferred to Appendix E.I. Theorem 3.3 states that the representation complexity of the underlying model is in AC 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 RI. 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* circuits while the optimal value function cannot. Here, AC* is a complexity class satisfying AC C AC* C P C NP. Therefore, our results not only address this open problem by revealing a more substantial gap in representation complexity be- tween 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 Qi is hard to represent, our proof also implies that V/5" is hard to represent. Moreover, we can extend our results to the more general case, say {QTheell 3 II are NP-complete, by introducing additional irrelevant steps. Notably, one cannot anticipate Q7 to be hard to represent for any h [H] since QH 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 Tf is hard to represent in our proof, the result can be extended to step h where 2 S h S H, as of also serves as an optimal policy at step h. Finally, We want to emphasize that, since our objective is hh and x¹ = { have high representation complexity, it suffices to
to show that Q' = { demonstrate that Qi and पं 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.
3.2 NP MDP: A Broader Class of MDPs
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 corresponding NP MDP that encodes 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", 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 language C 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., and let each configuration
(sM, t, E C., encompass the state of the Turing Machine 8M, the contents of the tape and the pointer on the tape requiring O(P(n) bits for representation. Then an n- dimensional NP MDP defined as follows. The state space S is C, X ((0) ( ()) + 2)), and each 8= (c. k) E S consists of a valid configuration c= (sM, t, 1) and a index & E (0) U (2())) + 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 = (c, k) = (s t, k) and action a, the reward function
r(s, a) is defined by:
SM = Sucppe and l: = P(n) + 1, 0.5 I = 2P(n) +
r(s,0)=
(3.3)
Otherwise,
5

---

where Saccept is the accept state of Turing Machine M. Moreover, the transition kernel is deterministic and can be defined follows:
(c, P(n) +2)
If k= 0,
(c
If 1 and le = 0,
(((c))).a)
(3.4)
(1
I E [P(n)]
kc
If > P(n).
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 Xinput be an input string of length n. We can construct the initial configuration co of the Turing Machine M on the input Xinpur by copying the input string onto the tape, setting the pointer the initial location, and designating the state of the Turing Machine as the initial state. The initial state is defined as (Co. 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 e and the accept state Sncepet in NP MDPs mirror the formula-assignment pair (tb, v) and the scenario that (b(v) MDP is the first class of MDPs defined in the context of (non-deterministicc Turing Machine and can encode any NP-complete problem in MDP structure. This represents 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.
in 3-SAT MDP, respectively. To the best of our knowledge, NP
Theorem 3.8 (Representation complexity of NP MDP). Consider any NP-complete language alongside its corresponding n-dimensional NP MDP Mn. as defined in Definition 3.7. The transition kernel P and the reward function r of M,, can be computed by circuits with polynomial size (in n) and constant depth, belonging the complexity class AC In contrast, the problems of computing the optimal value function Qi and the optimal policy x of M, are both NP-complete under the polynomial time reduction.
The proof of Theorem 3.8 deferred to Appendix E.2. Theorem 3.8 demonstrates that a substantial representation complexity gap between model-based RL (AC") 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 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.
4 The Separation between Policy-based RL and Value-based RL
In Section 3, we demonstrate the representation complexity gap between model-based RL and model- free RL. In this section, our focus shifts to exploring the representation complexity hierarchy within model-free RL, encompassing policy-baste based RL and value- RL. More specifically, we construct 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.
4.1
CVP MDP
We begin by introducing the CVP MDPs, whose construction is rooted in the circuit value problem (CVP). The CVP involves computing the output of given Boolean circuit (refer to Definition B.2) on a given input.
Definition 4.1 (CVP MDP). n-dimensionall CVP MDP is defined as follows. Let C be the set of all
circuits of size n. The state space defined by S = C {0, Unknown] } where each state can
be represented as s = (c, v). Here, c is a circuit consisting of n nodes with c[i] = (c [c]]][]] c|i] 9i) describing the i-th node, where [ and c e(i indicate the input node and g, denotes the type of
gate (including A, V, -. 0. 1). When Si E {A, v). the outputs of c[i][1]-th node and cii] 2 node serve the inputs; and when 9; -, the output of [ node serves the input and [ is meaningless. Moreover, the node type of or denotes that the corresponding node is leaf node with a value of 0 or 1, respectively, and therefore, c[j][]], c[i] are both meaningless. The vector v E {0, 1, Unknown]" }' 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 is A [n]

---

c
Vandin) =1
Vind
Yinkoown
V
otaerwise
12
Figure 2: A visualization of CVP MDPs. Here, Vunknown which contains Unknown values, is the initial value vector. For any state including a circuit с and a value vector v, choosing the action i, the environment transits to (c, v(). Moreover, Vend. v' end and v" end are value vectors at the end of the episode.
and the planning horizon is H = n + 1. Given state-action pair (s = (c, v), its reward r(s, a) given by:
If the value of the output gate v/n] =
r(s, a)
Otherwise.
Moreover, the transition kernel is deterministic and can be defined as: v).a) (c,v') v' is obtained from v by computing and substituting the value of node More exactly, if the inputs of node have been computed, we compute the output of the node and denote ofa]. Then we have
v'). Here,
v
If a # J.
o[a]
If a = j and inputs of are computed,
Unknown
a = j and inputs are not computed.
Given circuit c, the initial state of CVP MDP is (c, Vunknown) ) where Vunknown denotes the vector containing n Unknown values.
The visualization of CVP MDPs is given in Figure 2. In simple terms, each state (c, v) comprises information about a given size-n circuit с and vector {0, 1, Unkown] }". At each step, the agent takes action E [rs]. 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 gate c[a]. The agent achieves the maximum reward of only if transforms the initial vector Vunknowns consisting n Unknown values, into the v satisfying v(n] = 1. This also indicates that CVP MDPs exhibit the capacity to model many real-world coal-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, be the n-dimensional CVP MDP defined in Definition 4.1. The reward function r, transition kernel P, and optimal policy x¹ of Mn be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC However, the problem of computing the optimal value function Qi of M,, 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 com- plexity 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 for details.
4.2 MDP: A Broader Class of MDPs
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 MDP follows.

---

Definition 4.4 (P MDP). Given a language L in P, and a circuit family C, where C. E C contains the circuits capable of recognizing strings of the length in L. The size of the circuits in C,. upper bounded by a polynomial P(n). An n-dimensional
MDP based on L defined as 13 x Cn {0, Jnknown) P(m),, where each state 8 can be represented as 8 (x, c, v). Here, c the circuit recognizing the strings of length a in & with c(j] = [c]:][]], c [22] 91) representing the i-th node where the output of nodes in and ig serves as the input, and ys is the type of the gate (including A, 7, and Input). When I: E {A,V], V). the outputs of c[i][1]-th node and cfa] [2] -t node serve as the inputs; and when 9: - the output of e node serves as the input and c[ meaningless. Moreover, the type Input indicates that the corresponding node is the I| bit of the input string. The vector v E {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 = [[((n] and the planning horizon is H P(n) + 1. The reward of any state-action (s (x, c, v),a) is defined by:
follows. The state space S is defined by S
If the value of the output gate v(P(n)) 1,
r(s a)
Otherwise.
Moreover, the transition kernel is deterministic and can be defined as: P((x, e, v). (x, c, v'), where v' is obtained from v by computing and substituting the value of node a. 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
If a + j,
v
0/0
If a = j and inputs of are computed, a = j and inputs of are not computed.
Unknown
Given an input and circuit capable of recognizing strings of specific length in L, the initial state of P MDP is (c, Vunknowa) where Vunknown 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 recognize the P-complete language C 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 Turing Machine, 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 Mn, as defined in Definition 4.4. The reward function transition kernel P, and the optimal policy of M,, can be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC However, the problem of computing the optimal value function Qi of M,, 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, opposed to a specific circuit value problem. In these expanded scenarios, the representa- tion complexity of the model and optimal policy remains noticeably lower than that of the optimal value function.
Consequently, by combining Theorems 3.8, 3.8, 4.2, and 4.5, a potential representation complexity hierarchy has been unveiled. Specifically, the underlying model is the easiest represent, followed by the optimal policy, with the optimal value exhibiting the highest representation complexity.
5 Connections to Deep RL
While we have uncovered the representation complexity hierarchy between model-based RL, pasecy-based RL., and basued RL through the lens of computational complexity in Sections 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 (ReL.) as the activation function an architecture predominantly employed in deep RL algorithms.
$ OOur 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
8

---

Definition 5.1
MLP). An L-layer MLP is a function from input E IR to output
y E IR4,, recursively defined as
h1 ReLU (Wieg eg + b1): W Rdixd bi E ERA
h, ReLU (Webe-1 + be), W W be ER.
y Wyhh ,y, W. E Rdyxds by E RR",
where 2 S and ReLU(z)= = max x} for any x E I is the standard ReLU activation. Log-precision MLPs refer to MLPs whose internal neurons can only store floating-poin numbers within Ollogn) bit precision, where n is the maximal length of the input dimension.
The log- seg-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 (c.g.. 1024 or 2048 for the representation of image data). In our paper, all occurrences of MLPs will implicitly refer to the log-precision MIP, and we may omit explicit emphasis on log precision for the sake of simplicity. See Appendix B.3 for more details regarding log precision.
To employ MLPs to repre- sent the model, policy, and value function, we encode each state and action into embeddings es E IRd and e, E Rd,, respectively. The detailed constructions of state embeddings and action embeddings of each type of MDPs are provided in Appendix G.I. In addition, we specify the input and output of MLPs that represent the model, policy, and value function in Table 2.
Transition
Reward
Optimal Policy
Optimal Value
Input
(Cay Ca)
(eg C,]
e,
(eg Co) Qi a)
Output
Cg'
r(s,a)
Ca
The input and ouiput of the MLPs that represent the model, optimal policy, and optimal value function.
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 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 1t), and ReLU the activation function.
Theorem 5.3. Assuming that TC # NP, the optimal policy |i and optimal value function Qi of n-dimensional 3-SAT MDP and NP MDP defined with respect to an NP-complete language L cannot be represented by 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. Theo- rems 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 represen- tation complexity gap between policy-based RI. and basue- RI., 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 x* of n-dimensional CVP MDP and P MDP can be represented by an MIP with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function.
Theorem 5.5. Assuming that TC A P. the optimal value function Qi of n-dimensional CVP MDP and P MDP defined with respect to P-complete language L cannot be represented by an MLP with constant layers, polynomial hidden dimension (in ni), 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 ex- pressiveness, aligning more closely with modern deep RL and providing valuable insights for practice.
Remark 5.6. The results presented this section underscore the importance of establishing NP- completeness 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 o and TC" + NP, which are widely believed to impossible. In contrast, it is noteworthy that MLPs with constant layers and polynomial hidden dimension can

---

MLP 16 dimendions and loyers
HLP 16 dimorsions and layers dalaset sue 100000
MLP 26 dimandoons and byers
detasel sue 30000
delawet siew 302000
0.6
0.5
Optimal
0.5
Optimal
Optima Paicy
Optimal O/Tunchinn
Optimall O-function
Optima O-finctiinn
6.3
0.3-
0.3
6.2
0.2-
0.2
0.3
H.C.
Humanoid
Humanoid
Humanoid
(a)
(b)
(c)
MLP of 15 dimensions and layers
HLP 15 dimardions and layers
HLP of 15 dimardions and layers Tocnno
186006
Translton Hamn!
Thrsition Remel
Tharatinn Geme
Nowart Function
Roward Fund
Roward Fundinn
Optinal Pellcy
Optimal Polkyy
Opt mal Po
Optimlll Pu
Optimal Q-functon
Opt O-functin
Agunsimatts
0.4-
0.4
0.3
0.-
0.2
0.1
0.1
0.0
H.C.
Humanold
Humbnald
L.
Humonald I..
(d)
(e)
(I)
Figure 3: The approximation errors computed by employing MLPs with varying depths d and widths to approximate the transition kernel, reward function, optimal policy, and optimal Q-function in four MuJoCo environments. In each subfigure, the title indicates the configuration including hidden dimensions, number of layers, and dataset size. The x-axis lists the four MuJoCo environments, where H.C. represents HalfCheetah and I.P. represents InvertedPendulum. The y-axis represents the approximation error defined (D.1).
represent basic operations within TC (Lemmaa 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 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.I. Although we have shown that the revealed hierarchy of representation complexity holds for wide range of MDPs in theory, examining its broader applicability is essential. We discuss more general theoretical insights and extension 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 theory captures practical problems, we conduct empirical investigation into the representation complexity of different RL paradigms across various MuJoCo Gym environments [7]. Our empirical findings align with our thcoretical conclusions. We report part of our experimental results in Figure 3, more detailed experimental description and results are deferred Appendix D.
Conclusions
This paper studies three RL paradigms - model-based RL, policy-based RL, and value-based RL from 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 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 various RI. paradigms, providing valuable insights for the advancement of RL methodologies.
10

---

References
[1] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in neural information processing systems, 33: 13:13399-13412 2020.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431 1-1061 2021.
[3] Sanjeev Arora and Boaz Barak. Computational complexity: modern approach. Cambridge University Press, 2009.
[4] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. International Conference on Machine Learning, pages 463-474, PMLR, 2020.
[5] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272.
PMLR, 2017.
[6] Vincent D Blondel and John N Tsitsiklis. survey of computational complexity results in systems and control. Automatica, 36(9):1249-1274 2000.
[7] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 1606.015500 2016.
[8] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference Machine Learning, pages 1283-1294. PMLR, 2020.
[9] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563- 2578, 2022.
[10] Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael Jordan, A general framework for sample-efficient function approximation in reinforcement learning, arXiv preprint arXiv:2209.156m 15634, 2022.
[11] Chef-Seng Chow and John N Tsitsiklis. The complexity of dynamic programming. Journal of complexity, 5(4):466-483 1989.
[12] Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, ACM, 1971, page 151-158, 1971.
[13] Kefan Dong, Yuping Luo, Tianhe Yu, Chelsea Finn, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International conference machine learning, pages 2627-2637. PMLR, 2020.
[14] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference Machine Learning, pages 2826-2836. PMLR, 2021.
[15] Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv:1910.03016 2019.
[16] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024.
[17] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13488) 2021.
11

---

[18] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International conference on machine learning, pages 1587-1596. PMLR, 2018.
[19] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1163--100,, 2010.
[20] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32, 2019.
[21] Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1704-1713. PMLR, 06-11 Aug 2017.
[22] Chi Jin, Zeyuan Allen- Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[23] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-effcient algorithms. Advances in neural information processing systems, 14413400-14111 2021.
[24] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[25] Ying Jin, Zhimei Ren, Zhuoran Yang, and Zhaoran Wang. Policy learning" withouutoovrllay Pessimism and generalized empirical bernstein's 's inequality. arXiv preprint arXiv:22 12.09000, 2022.
[26] Sham M Kakade. A natural policy gradient. Advances in neural processnionnrocesssingg 14, 2001.
processing systems,
[27] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11): 2013.
[28] Richard E Ladner. The circuit value problem is log space complete for p. ACM Sigact News, 7(1):18-23 20, 1975.
[29] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sam- pling complexity, and generalized problem classes. Mathematical programming, 198(1):1059- 1106, 2023.
[30] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 3274533)):436 2015.
[31] Leonid Anatolevich Levin. Universal sequential search problems. Problemy peredachi infor- matsii, 9(3):115-118 1973.
[32] Michael L Littman, Judy Goldsmith, and Martin Mundhenk. The computational complexity of probabilistic planning. Journal of Artificial Intelligence Research, 9: 9:1-36, 1998.
[33] Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. Advances in neural information processing systems, 32, 2019.
[34] Qinghua Liu, Gellért Weisz, András György, Chi Jin, and Csaba Szepesvári. Optimistic natural policy gradient: simple efficient policy optimization framework for online rl. arXiv preprint arXiv:2305.1 1032, 2023.
[35] Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. One objective to rule them all: A maximization objective fusing estimation and planning for exploration. arXiv preprint
2023.
12

---

[36] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of pog-preciiion transformers. Transactions of the Association for Computational Linguisties, 11:531-545, 2023.
[37] Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):441-400 1987.
[38] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint vrXiv:1707006344 2017.
[39] Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613. PMLR, 2020.
[40] Uri Sherman, Alon Cohen, Tomer Koren, and Yishay Mansour. Rate-optimal policy optimization for linear markov decision processes. arXiv preprint arXiv:2308. 14642, 2023.
[41] David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[42] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages
PMLR, 2019.
[43] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[44] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
[45] Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference on Learning Theory, pages 3036 3083. PMLR, 2019.
[46] Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226 2021.
[47] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[48] Tianhao WU, Yunchang Yang, Han Zhong, Liwei Wang, Simon Du, and Jiantao Jiao. Nearly optimal policy optimization with stable at any time guarantee. In International Conference Machine Learning, pages 24243-24265. PMLR, 2022.
[49] Lin Xiao. On the convergence rates of policy gradient methods. The Journal of Machine Learning Research, 23(1): 2022.
[50] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. Advances neural information 2021.
processing systems,
[51] Yunbei Xu and Assaf Zeevi. Bayesian design principles for frequentist sequential learning. In International Conference on Machine Learning, pages 38768-38808 PMLR, 2023.
[52] Kai Yang. Jan Ackermann, Zhenyu He, Guhao Feng, Bohang Zhang, Yunzhen Feng, Qiwei Ye, Di He, and Liwei Wang. Do efficient transformers really save computation? arXiv preprins 2402 13934, 2024.
[53] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004, PMLR, 2019.
13

---

[54] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 33: 13:14129-14142, 2020.
[55] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
[56] Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. arXiv preprinl arXiv:2307. 13586, 2023.
[57] Zihan Zhang, Xiangyang Ji, and Simon Du Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528 4531. PMLR, 2021.
(58) Han Zhong, Wei Xiong, Sirui Zheng. Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. Gee: unified framework for interactive decision making mdp, pomdp, and beyond. arXiv preprint arXiv:2211.01992. 2022.
[59] Han Zhong, Zhuoran Yang, Zhaoran Wang, and Csaba Szepesvári. Optimistic policy optimiza- tion is provably efficient in non-stationary mdps. arXiv preprint arXiv:2110.08984, 2021.
[60] Han Zhong and Tong Zhang. A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. arXiv preprint arXiv:2305.0884/ 2023.
[61] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532 4576. PMLR, 2021.
[62] Hanlin Zhu, Baihe Huang, and Stuart Russell. On representation complexity model-based and model-free reinforcement learning, arXiv preprint arXiv:2310.01706, 2023.
14

---

A Additional Related Works
Representation Complexity in RL., In the pursuit of achieving efficient learning in RI., 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 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 more significant separation between model-based RL and value-based RL. In addition, we also study the representation complexity of policy-based RL, providing potential hierarchy among model- RL, policy-based RL, and value-based RL from the above perspectives.
Classic Computational Complexity Results. 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 '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.
B
Additional Background Knowledge
B.1 Function Approximation Model-based, Policy-based, and Value-based RL
In modern reinforcement learning, we need to employ function approximation to solve complex decision-making problems. Roughly speaking, RL algorithms can categorized into three types model-based RL, pasecy-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 RI, which represents class of RI. 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- 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 10, P: S A A(S))). We also
15

---

want to remark that we consider the time- homogeneuss setting, where the reward function and transition kernel are independent of the timestep h. For the ame-inhomogeneouu setting, we can choose F = Fi x ................................ x FF and let Fn. approximate the reward and transition at the h-th step.
Policy-based RL: the learner directly approximates the optimal policy n². The function class F takes the form F Fi x x Fn with Fr. C {Th S A(A) for any h E [H].
Value-based RL: the learner utilizes the function class J = Fi x Fir to capture the optimal value function Q", where Fi C {Qn= : x A + [0, H]] for any h E [H].
In previous literature [e.g.. 23, 14, 50, 46, 17, 58, 25], standard assumption 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.
B.2 Computational Complexity
To rigorously describe the representation complexity, we briefly introduce some background knowl- edge of classical computational complexity theory, and readers are referred to [3] for more compre- hensive introduction. We first define three classes of computational complexity classes P, NP, and
P is the class of languages that can be recognized by deterministic Turing Machine in polynomial time.
NP is the class of languages that can be recognized by 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 nonde- terministic Turing Machine in Definition B.I.
Definition B.1 (Turing Machine). A deterministic Turing Machine (TM) M is described by tuple the tape alphabet containing the "blank" symbol, "start" symbol, and the numbers O and 1; Q is finite, non-empty set of states, including start state ystart and halting state "halting: and T: Q x T + Q x p x [Teft., Stay, Right.), where k 2 2, is the transition function, describing the rules M use in each step. The only difference between nondeterministic Turing Machine (NDTM) and a deterministic Turing Machine is that an NDTM has two transition functions To and T,, and special state Gaccept- At cach 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 Jaccept- A configuration of (deterministic nondeterministie) 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.
(I,Q,T) T). where
To quantify the representation complexity, we also adopt the circuit complexity, a fundamental concept in theoretical computer science, to characterize it. Circuit complexity focuses 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 E N4. a Boolean circuit with n inputs and m outputs is a directed acyclic graph (DAG) containing n nodes with no incoming edges and m edges with outgoing edges. All non-input nodes are called gates and are labeled with one of A (logical operation AND). V (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 e is the maximal length of 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.
'Following the convention of computational complexity [3], we may use the term "language" and "decision problem" interchangeably.
16

---

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 specific input size. In this context, circuit complexity investigates how the circuit size and depth scale with the input size of given function. We provide the definitions of circuit complexity classes AC and TC
AC is the class of circuits with constant depth, unbounded fan-in number, polynomial AND and OR gates.
TC extends AC by introducing an additional unbounded fan--in majority gate MAJ, which evaluates to false when half or more arguments false and true otherwise.
The relationship between the aforementioned five complexity classes is
AC & TC CLCPCNP.
The question of whether the relationship TC с P NP holds as strict inclusion remains elusive in theoretical computer science. However, it is widely conjectured that P NP and TC P are unlikely to be true.
Uniformity of Circuits. Given circuit family C, where c2 E C is the circuit takes n bits input, the uniformity condition is often imposed on the circuit family, requiring the existence of some possibly resource- resource-bounded Turing machine that, on input produces a description of the individual circuit Cn. When this Turing machine has running time polynomial in n, the circuit family C is said to be P-uniform. And when this Turing machine has space logarithmic in n, the circuit family C is said to be L-uniform.
B.3 Log Precision.
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 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 (log(n)) bits represent 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 (ppoly (n)) within (ppoly(1/n) truncation error.
More Discussions and Additional Restuls
C.1 Connections to Statistical Complexity
To elaborate further on the connections to statistical/sampll complexity, the previous sample complex-
ity (in both online and offline RL) of finding an E optimal policy typically poly H, 1/e) ) log [7|), 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//pliccy/val hypothesis. According to our representation complexity hierarchy theory, the model-based hypothesis could be simpler since the ground truth model easy to represent, resulting in smaller log [7|] This provides an explanation of why model-based RI. 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/pollcy/vaalee) in our work and provide an implication for the statistical error (sample efficiency learning algorithms). We believe that exploring the twisted approximation error, optimization error, and statistical error, and providing deeper comparison between model- based RI. and model-free RL would be interesting direction, and we will endeavor to explore this in our future work.
17

---

C.2 Generality of Representation Complexity Hierarchy
First, we wish to underscore that our identified representation complexity hierarchy holds in general way. Theoretically, our proposed MDPs can encompass wide range of problems, as any NP or P problems can be encoded within their structure. More crucially, our thorough experiments diverse simulated settings support the representation complexity hierarchy we have uncovered. In fact, we have a generalized result establishing a hierarchy between policy-based RI. and value-based RI., as stated in the following proposition:
Proposition C.1. Given a Markov Decision Process (MDP) M = {0, 13ad and | (p))))nn)) the circuit complexity of the optimal value function will not fall below the optimal policy under the TC reduction.
where S C
Proof. Note that given the optimal value function Q", the optimal policy x' can be represented as x (s) = argmax,c.A. Q(s, a), for any S. Therefore, we represent the optimal policy as the following Boolean circuits:
V(a (a^(A) (10 ((,,))))).
a'EA Therefore, the circuit complexity of the optimal value function will not fall below the optimal policy under the TC reduction.
aEAA
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 theoretical standpoint. We leave the fully theoretical characterizing of representation hierarchy between model-based RI,, policy-based RL, and value-based RL as an open problem. For instance, could be valuable to develop a methodology for classifying MDPs into groups and assigning complexity ranking to each group within our representation framework.
C.3 Extension to Transformer Architectures
Our theoretical results can also naturally extend to the Transformer architectures. First, we formulate the Transformer architectures represent the model, policy, and value function. We encode each state s and action a into a sequence s, and Sg, the detailed construction of the MDPs in this paper are listed follows:
Sequences for the 3-SAT MDP. The state of the n-dimensional 3-SAT MDP is denoted as s = (z), v, kt). Here, v0 is represented by a sequence of literals length 3n, and v by a sequence of length By concatenating these sequences,
represent the state (vh, v,, k) using sequence
S. of length 4n + 1. The action a E (0, 1} is represented by a single token.
Sequences for the NP MDP. The state of the n-dimensional NP MDP is s = (c, k), where c represents the configuration of non-deterministic Turing machine (NTM). The configuration includes the machine's ' internal state MM the tape content t, and the tape head position These components are encoded an integer, sequence of length P(n), and another integer, respectively. Thus, the state s = (c, k) is represented by a sequence S, of length P(n) +3. The action a E {0, 1) is encoded with single token.
Sequences for the CVP MDP. The state of the n-dimensional CVP MDP is (c, v), where c denotes circuit and v is a vector. Each node cli] of the circuit is represented by a sequence of tokens. Consequently, sequence of length 3n represents the entire circuit and the state s = (c, v) is encoded by a sequence S, of length 4n. The action a E [r]] is represented by a single token.
Sequences for the P MDP. The state of the n-dimensional P MDP is s (x, v). Assuming the circuit e has a size bounded by P(n), we represent the circuit using a sequence length 3P(n). The value vector is encoded by sequence of length P(n). and the input string by sequence of length n. Therefore, the state s = (x, c, v) is represented by the concatenated sequence S.. The action [P(n)] is encoded as scalar.
18

---

With these formulations, we can extend our theoretical results to the Transformer architectures.
Theorem C.2. Assuming that TC o NP, the optimal policy पं and optimal value function Qi of n-dimensional 3-SAT MDP and NP MDP defined with respect an NP-complete language L cannot be represented by a Transformer with constant layers, polynomial hidden dimension (in ri.and ReLU the activation function.
Theorem C.3. Assuming that TC P, the optimal value function Qi of n-dimensional CVP MDP and P MDP defined with respect to a P-complete language cannot be represented by a Transformer with constant layers, polynomial hidden dimension (in n), and ReLU the activation function.
Proof of Theorems C.2 and C.3. According to the previous work [36], a Transformer with logarith- mic precision, fixed number of layers, and a polynomial hidden dimension can be simulated by L-uniform TC 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 A NP and TC 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.S. The reward function r, transition kernel P. and optimal policy x² n-dimensional CVP MDP and P MDP can be represented by Transformer with constant layers, polynomial hidden dimension (in n), and ReLU as the activation function.
Proof of Theorems C.4 and C.S. 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.
D Experimental Details
In this section, we empirically investigate the representation complexity of model-based RL, policy- based RL, and value-based RL and validate theory with comprehensive various common simulated environments. Following [62], fixing the depth 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:
of experiments on
min al)l - a)]
etransition
JEF
E[I/(ss,a) EP.-E
B[(f(s, r(s. r(s.
min Greward
JEF B[(r(s,a) Eir(s, ))
(D.1)
[[]] (s) min
Epolicy
JEF [[][=((s) Ej (s))l1
Evalue
min FEF
(Q' - -)))
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 Exansition: Grewand, Épolicy, and evatue defined (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.
19

---

MLP 16 dimendions and loyers detaset sue
MLP 16 dimorsions and layers dalaset sue 100000
MLP 26 dimandoons and byers
delawet 302000
0.6
0.5
Optimal
Optimal
Optima Paicy
Optimal O/Tunchinn
Optimall O-function
Optima O-flnctiinn
6.3
0.3-
0..
6.2
0.2-
0.2
0.3
H.C.
Humanoid
Humanoid
Humanoid
(a)
(b)
(c)
MLP of 15 dimensions and layers
HLP 15 dimardions and layers
HLP of 15 dimardions and layers Tocnno
186006
Translton Harnel
Thnsition Remel
Tharatenn Keme
Nowarl Function
Roward Fundt
Aggnusimati daaemmallo Ene
Roward Fundinn
Optinal Pellcy
Optimall Polkyy
Opt mat Po
Optimal Pn
Optimal Q-functon
Opt O-functinn
0.4-
0.3
0.2
0.2
6.1
0.1
H.C.
Humanold
Humbnald
L.
Humonald
P...
(d)
(e)
(f)
of dimeevions and layers
MUP 32
layers
MLP dimerrsiurs layers
30000
100000
size 303000
0.6
Ereor
0.5
Rowars Funktion
Optimal
Trassidon Komei
Optirall Poilry
Translion Comel
Noward Punci
0. Erot
6.4
Ronard Punciin
Oprima Paity
Tranation Kemei
0.4-
Optimal Orfunstion
0.4
Optiraal Q-lunetion
0.3
Optima O-tunction
0.3-
0.2
0.0
H.C.
Humanoid
Art
0.5
M.C
Hum aroid
LP
Att
0.0
M.C.
Humanoid
LP.
Ant
(g)
(h)
layers
lvvers
to fit dataset of 30000
dataset sias 100000
datasst size 200000
Vansidan Kamo!
Torstio Sandl
Varsitio Ronel
Reward Function
Noward huncton
0.3
Roward Puncson
Optimal
0.5
Optimal Pally
Optima Poilcy
Segroae alon
0.3-
Optimal Munnsiiion
0.4
Optimaal O-function
6.2
Optima Q-function
0.1
0.0-
H.C.
Humanold
Aet
0.0-
H.C.
Humaneld
L.
Art
0.0
H.C.
Humanold
LR.
Ant
(k)
Figure 4: The approximation errors computed by employing MLPs with varying depths d and widths to approximate the transition kernel, reward function, optimal policy, and optimal Q-function in four MuJoCo environments. In each subfigure, the title indicates the configuration including hidden dimensions, number of layers, and dataset size. The x-axis lists the four MuJoCo environments, where H.C. represents HalfCheetah and I.P. represents InvertedPendulum. The y-axis represents the approximation eиror defined in (D.1).
We conduct experiments on four MuJoCo Gym environments [7]: HalfCheetah-v4, Humanoid-v4, InvereedPendulum-v. 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, 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 times with random seeds and report the means and standard deviations. All the experiments are conducted on an NVIDIA GeForce RTX 3090 GPU. Figure 4 illustrates the results. enror 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
experiments, the approximation
20

---

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.
Table 3: Configurations for training the ground-truv -tnnd agent by TD3 algorithm.
Number of Layers of Actor-Network Hidden Dimensions of Actor-Network Number of Layers of Critic-Network Hidden Dimensions of Critic-Netwond Standard Deviation of Gaussian Exploration Noise
3
256
3
256
0.1
Discount Factor
0.99
Target Network Update Rate
0.05
Table 4: Configurations for fitting the MLP to the corresponding functions and measuring the approximation enror.
Size of Dataset
{30000, 100000, 300000)
Batch size
128
Optimization Steps
70k
Number of Layers
{2.
Hidden Dimensions Optimizer
{16, 32}
Adam
Learning rate
0.001
E Proofs for Section 3
F.1 Proof of Theorem 3.3
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 circuits. Given literal E {u1, u2 Uni 71, -22 Ju, we can obtain its value by
a (V ( w.)) jE(m)
V (-v = -ml)) JE(m]
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 expressed as
r(s, a) 1 (bb(v) A n + 1] 0.5 1 [k + 2].
which further implies that the reward function be implemented by AC circuits.
Transition Kernel. Then, will implement the transition kernel by AC circuits. It is noted that only need to modify the assignment v, k. Given the input v, and a, we have the output as follows:
3 = v
v' [ = (vl A 1 x)) V (a A 1p = k)),
(E.1)
V -
k
2 1| + 1kk A 1] + 2) 1l la k=
is noted that each element in the output is determined by at most O n) bits. Therefore, according to Lemma 1.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 circuits.
Optimal Policy.
We aim to show that, given a state s = (w: v, k) as input, the problem of judging whether (s) = 1 is NP-complete. We give two-step proof.
21

---

Step 2. Mcanwhile, according to the well-known Cook-Levin theorem (Lemma I.1), the 3-SAT problem NP-complete. Thus, our objective to provide 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 most n. Then, we can pad several meaningless clauses such as (ui V -11 V ui) to obtain the 3-CNF Boolean formula vp with n clauses. Then the This provides a desired polynomial 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 E [n] or k = O, vld v
[1], i E [k] and v' +
Notably, when exist such certificates, action a = yields the reward and is consequently optimal. Conversely, when such certificates absent, action a = is the optimal action. Moreover, when = n + 1 or & = n + 2, selecting a = is always optimal. Consequently, given the certificates, we can verify whether mi (v) On. : 0)
leads the reward of 0, and in this case,
Boolean formula & satisfiable if and only n (v/ On: 0)
time reduction.
Optimal Value Function. To show the NP-completeness of computing the optimal value function, formulate the decision version of this problem: given state (v), v. k), an action and number 7 as input, and the goal is to determine whether Qi (s, a) > y. According to the definition of NP-completeness, we need to prove that this problem belongs to the complexity class NP and then provide polynomial-tine 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 = (tb, k), input action and input real number y, we use the assignments v' of di as certificates. When 7 1, the verifier Turing Machine will reject the inputs, and when < O, the verifier Turing Machine will accept the inputs. When y E [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 E [n]. it holds that vii] v' for all i [k].
When y E [0, 0.5), except in the scenario where the aforementioned two conditions are met, the verifier Turing Machine will additionally accept the input when &
0. Then we have
Qi > > if and only if there exists a certificate v' such that the verifier Turing Machine accepts the input containing 8, a, 7, and the assignment v'. Moreover, the verifier Turing Machine runs in 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 polynomial time reduction from the 3-SAT problem to the computation of the optimal value function for the 3-SAT MDP. Given Boolean formula of length n, the number of variables is at most n. Then, we can pad several meaningless clauses such as (uj* V u V "u)) to obtain the 3-CNF Boolean formula ve with n clauses. The Boolean formula e is satisfiable if and only if (( O,, 0), > f. time reduction.
3 which gives us desired polynomial
Combining these two steps, we can conclude that computing the optimal value function is NP- complete.
F.2 Proof of Theorem 3.8
Proof of Theorem 3.8. Following the proof paradigm of Theorem 3.3, we characterize the represen- tation complexity of the reward function, transition kernel, optimal policy, and optimal value function in sequence.
22

---

Reward Function. Given the state s = (MM t, k). the output of the reward
r(s, a) [ Succepe A k ((n) + 0.5 1 2P(n) + 2/.
(E.2)
It is not difficult to that the reward function can be implemented by AC circuits.
Transition Kernel.
We establish the representation complexity the transition kernel by providing the computation formula for each element of the transited state. Our proof hinges the observation that, for state $ = (SMs t, k),, we can extract the content I of the location on the tape by the following formula:
X = A (1i=
(E(P(n)
It is noted that we assume the contents written on the tape are O 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 d' = (s t', 1') defined in (3.4), we observe that
(i) the Turing Machine state ''M is determined by SM, and Xi
(ii) the content of the location I on the tape, t'[4. is determined by 8M, 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 determined by 8M. and X-
Moreover, the number of steps k is determined by k and a. Therefore, each element the output is determined by most Ollog n) bits. According to Lemma I.4, each bit of the output be computed by two-layer circuits of polynomial size, and the output can be computed by the AC circuits.
Optimal Policy. Our objective is to demonstrate the NP-completeness of the problem of determining (t), v, k) as input. We will begin by establishing that this problem falls within the class NP, and from the NP-complete language C to this specific problem.
whether (s) given state subsequently, we will provide a polynomial-time reduction
Step 1. Given sequence of choice of the branch as the certificate, we only need to verify the following two conditions to determine whether the optimal action 1:
The final state of the Turing Machine M is the accepted state.
When e [P(n)], the configuration of the Turing Machine after k-steps exccution under the choice provided by the certificate the same as the configuration in the current state.
When & E [P())). the choice of the k-th step is branch 1.
always get the reward of and is therefore optimal, and otherwise, action a = always gets the reward of 0, and a = 0 is always optimal. Moreover, when & P(n) + or & P(n) + 2, optimal action. So given the certificates, we can verify whether (w) On, 0) 1.
Note that, when exist such certificates, action
always select the action
1 as the
Step Given an input string Simput of length n. We can simply get the initial configuration co of the Turing Machine M on the input Simpul- Then Singut L if and only if x ((Co. 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, consider the decision version of the problem of computing the optimal value function as follows: given a state s = (8M t, k), an action a, and a number y as input, and the goal is determine whether (s, a) > 7
Step 1. We first verify that the problem falls within the class NP. Given the input state we use a sequence choice of the branch as the certificate. When 7 > 1, the verifier Turing Machine will reject the inputs, and when 7 < 0, the verifier Turing Machine will accept the input. When y E [0.5, 1), the Turing Machine accepts the input when there is a certificate that satisfies the following two conditions:
23

---

The final state of the Turing Machine M is Succept-
When E [P(n)], the configuration of the Turing Machine after k-steps execution under the choice provided by the certificate the same as the configuration in the current state.
When 7 E [0, 0.5), the scenario where the aforementioned two conditions are met, the verifier Turing Machine will additionally accept the input when A O. Note that, all these conditions be verified in polynomial time. Therefore, given the appropriate certificates, we can verify whether Qi y 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 Sinput be input string of length n. To obtain the initial configuration c of the Turing Machine M on the input Sinput- 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, Sinput E C if and only if Qi ((co, 0), 1) 4 which provides desired polynomial time.
8
Combining these two steps, we can conclude that computing the optimal value function of NP MDP is compleee
F Proofs for Section 4
F.1 Proof of Theorem 4.2
Proof of Theorem 4.2. We characterize the representation complexity of the reward function, transi- tion kernel, optimal policy, and optimal value function sequence.
Reward Function. First, we prove that the reward function of CVP MDP can be computed by AC circuits. According to the definition, the output is
r(s, a) [v[n]] = 1].
Therefore, the problem of computing the reward function falls within the complexity class AC
Transition Kernel. Then, we prove that the transition kernel of CVP MDP can be computed by AC cireuits. Given the state-action pair (s = (c, v),a). a), denote the next state P(s, a) as s' (c',v'). For any index E [n). we can simply fetch the node c(i] and its value by
clt]
V (cb) A L[i j)), GE(m]
vld
V (vb) A j]), JELm]
(F.I)
where the AND and OR operations are bit-wise operations. Given the node c[a] and its inputs v[c[a][[]] 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 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 o(a] be Unknown when the inputs of the a-th node have not been computed. Specifically, we can compute o(a] as follows:
o[a] (1 = Al A [v]]
v(c]] [2] * Unknown] A (v[c[t][]) v(M1))))
(Ilea = v/ A - [[v] / Unknown] (v]c[]][]) V v((l1121)
[1ua = - 1[vc<]]]]]]]]] Unknown] ^ (-v[c]][1))) (11 E (0, s.) (F2)
(unknown/ A (119g E [V, A A [[nknow E v(d]111
-] ( = Unknown)))
= (c', v²). the output of the transition kernel, as c' c'-c. v [ (osa) A 1[i al) A (v[i) A 1 + a)), which implies that the transition kernel of CVP MDP can be computed by AC circuits.
Furthermore, we can express
24

---

Optimal Policy. Based on our construction of CVP MDP, it is not difficult to see that कं = Tg.. For simplicity, we omit the subscript and use x² to represent the optimal policy. Intuitively. the optimal policy is that given 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 (c. v), denoting c[i] (c[+][], c[i] 9.), let (s)) be a set defined by:
((s)
= =ii [n] gi {A, V), [[] v|c[[|[2] 10. v/i] = Unknown) U UiE 9i - -, [[] E (0. 13, v/] = ]nknown)
(F.3)
[ 9e (0.1), v Unknown).
The set (() defined in (F.3) denotes the indices for which inputs have been computed, and the output has not been computed. Consequently, the optimal policy iT" (s) is expressed as x: =s() min G(s) If the output of the circuit is 1, the policy मं can always get the reward I, establishing its optimality, And if the output of circuit с is the optimal value is and x² is also optimal. Therefore, we have verified that the π min (s)) defined by us is indeed the optimal policy. Subsequently, we aim to demonstrate that the computational complexity of π² resides within AC Let T[i] denote the indicator of whether i ((s). i.c. Ti
signifies that G(s), while T[i] 0 denotes that i & (s)). According to (F.3), we can compute [i as follows:
[ (1 E (A, v)] A [[v[[[[[]]]. v [[[]]]]]]]] E {0, A [ = Unknown])
V (4[ = -] A [[v[[[][[]]] E {0, 13] A [[v[i] = Unknown])
(1[g: E [0, A [[vij] = Unknown|).
Under this notation, we arrive at the subsequent expression for the optimal policy n":
π (s)
V (T))) where T' - V Tbil M[j].
<E(m)
Therefore, the computation complexity of the optimal policy falls in AC
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 I, 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ī a) 1. 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 We first verify the problem is in P. According to the definition, state s (c, v) can get the reward 1 if and only if the output of e is 1. A natural algorithm to compute the value of the circuit 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 space reduction. According to Lemma I.2, the CVP problem P-complete. Thus, our objective 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 e of size n and a vector Vunkown containing n Unknown values, consider s = (c, Vunkown).
Let = x² (s), where the optimal policy T²" is defined in the proof of the "optimal policy function" part. The output of e is if and only if (i,,s) i) = 1. Furthermore, the reduction is accomplished by circuits in AC 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.
F.2 Proof of Theorem 4.5
Proof of Theorem 4.5, We characterize the representation complexity of the reward function, transi- tion 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 circuits. According to the definition, the output
r(s, a) = [[viP(m) = 1].
25

---

So the complexity of the reward function falls within the complexity class AC
Transition Kernel. First, we prove that the transition kernel of MDP can be computed by AC circuits. Given state-action pair (s (x. c, v). we denote the next state P(s, a) by s' = (x', v'). Similar to (F.1) in the proof of Theorem 4.2, we can fetch the node c(i], its value vlil. and the i-th character of the input string x(i]. We need compute the output of the a-th node.
Given the node c/a] and its inputs v/c [1] and [2]]
x/c[a]]]], we can compute the a-th node's value o[a] similar to (F.2), where o 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, o[a] can be computed as:
o[a] = (199. ^] A [[v[c[][[]]] v(] 2]]
Unknown] A [v[c[i][1] A v(cl
[[ v) [ * Unknown
[
[[g -] A 4|v[c[i][[] * Unknown] (-v(c[i][[]))
(F.4
[Lga Input] x|c(i|[l])
(Unknown A ((119 E AH [Unknown E (v]ce[]11)
(1 = -] - = Unknown)))
Then the next state 5 (x' c', v') can be expressed
x'=x, c.
[ (o[a] 1[i = a)) A (v[i) *
which yields that the transition kernel of P MDP can be computed by AC circuits.
Optimal Policy. Given a state (x, 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 (s)) to represent the set of indices of which inputs have been computed and output has not been computed. Given state (x. c, v). denoting c(t] (c|i][1], c[i][2). 9:), the set ((s) is defined by:
(s) -ii e [P(n)] 9i E (A. v[c[i][A], v v/c]+][]]] (0, v Unknown]
Ufie [Pn)] g: -, [[c]][]]] E (0. 1). v(i] Unknown]
(F.5)
Ufie [P(n)] g: = Imput, vii] Unknown].
Under this notation, we can verify that the optimal policy is given by (s)) = min (s)) Here we omit the subscript and use n² to represent the optimal policy since o nラ (i) if the output of the circuit c 1, the policy π can always get the reward and is hence optimal; (ii) if the output of circuit e is O, the optimal value is 0 and x- is also optimal. Therefore, our objective prove that the computation complexity of क falls in AC Let [[] be the indicator of whether i E ((s), i.e. T[]] = indicates that i E (s)) and [[] = 0 indicates & @(s). By the definition of (s)) in (F.5), we can compute [[]] as follows:
TH. Specifically,
i =(1gg {Λ, v}] A [[[e[[]]]] v/c[][2]] E [3, A [[v[i] = Unknown]) v (1[g -| ^ [[v[c|]][]]] (0, 1)] [[v[i] Unknown])
(1[g= Input] 1 [[[ Unknown]).
Then, we can express the optimal policy as
(s)
V
(T))A))
where T'(1]=-(V) Tb:) ^ T/..
(E(P(m)
jes
Therefore, the computational complexity of the optimal policy falls in AC
Optimal Value Function. We prove that the computation of the value function of MDP P- complete under the log-space reduction. Note that the reward of the P MDP can be only 0 or 1, we
26

---

consider the decision version of the problem of computing the optimal value function as follows: given a state (x, c, v) and an action a as input, the goal is determining whether Qi (s, a) 1. we need to prove that this problem belongs to the complexity class P and then provide 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 = (x, c, v) can get the reward 1 if and only if the output of is 1. A natural algorithm to compute the value of the circuit e 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- Spg-space reduction. Under the condition that C is P-complete, our objective is to provide a log- reduction from L to the computation of the optimal value function for the P MDP. By Lemma I.3, a language in P has log- space-uniform circuits of polynomial size. Therefore, there exists Turing Machine that can generate a description of a circuit 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, Vunknown), where Vunknown denotes the vector containing P(n) Unknown values. Let i x² (s). where x² is the optimal policy defined in the "optimal policy" proof part. Then x E C if and only if (i, i)) = 1. This provides 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.
G Proofs for Section 5
G.1 State Embeddings and Action Embeddings
Embeddings for the 3-SAT MDP. The state of the n dimension 3-SAT MDP (v) v, k). We
can use an integer ranging from 1 to 2n to represent a literal from V = {u), -0,, ".. , Uny - ). For example, we can use (i, i + +2) to represent (u4, mu)) for any i [m]. Therefore, we can dimensional vector ey to represent the v E Van and a 4n + 1 dimensional vector e, = (e V, k) to represent the state (v, v, k). And we use a scalar to represent the action a E 10.
3n
Embeddings for the NP MDP. The state of the n-dimension NP MDP is denoted as s = (c, k). A configuration of neteetneriiiistic Turing Machine, represented by c, encompasses the state of the Turing Machine sM, the contents of the tape f, and the pointer on the tape 1. 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, (nn) + 2 dimensional vector e, is employed to represent the configuration, and a P(n) + dimensional vector e, = (e,, k) is used to represent the state (c, k). Additionally, scalar is utilized to represent the action a E {0, 1).
Embeddings for the MDP. The state of the n-dimension CVP MDP is denoted as = (c. v). Utilizing a 3 dimensional vector, represent node c[i] of the circuit. Consequently, a 3n dimensional vector e. is employed to represent the circuit c, and a 4n dimensional vector e, = (ec, v) is used to represent the state to signify the node index, an integer ranging from 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 node. Additionally, scalar is used to represent the action a E [n].
(c. v). In this representation, an integer ranging from 1 to n is used
Embeddings for the P MDP. The state of the n dimensional MDP 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, (iimn-diinnsion vector ce is employed to represent the circuit c. Meanwhile, (n) dimensional vector v is used to represent the value vector of the circuit, and a dimensional vector represents the input string. In this representation, an integer used to denote the character of the input, the index of the circuit, the value of a node, or the type of node. Therefore, a 4 PP)) + n dimensional vector e,- = (x, ee; v) is used to represent the state s = (x, c, v). Additionally, a scalar is used to represent the action e [P(n)].
27

---

G.2 Proof of Theorem 5.2
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 ML.. Denoting the input
Co
(Ca, a) (Cw. V, a).
which embeds the state s (tb, 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 t. Let eb be the formula obtained from v by substituting all variables and containing only Boolean value. Recall that we use [2n] to represent (w1, u, Un; "Wn J. We define 2n dimensional vector V such that, for any
literal T E {u11 -M,," "1 U2s -m V(7 vli if u, and v(r] -v[i] if -y.. Hence,
given a literal [2n], can get its value v[r] by
T ReLU Σ ReLU 1[T u.] kE(n
1)+ Σ ReLU -ul)) viil). VE(M]
According to Lemma 1.5, the function [[ = Us] and [ muy] can be implemented by the constant layer MLP of polynomial size. So we can get the output of Module 1, which is
e (c v, k. o.)
Module 2.
The next module is designed to compute the value of e.. Given the value of each literal 0z,j can compute the value of vl i.e., (v), by the following formula:
(vv)=
ReLU
ReLUU(a, + 0i + 44.3) ReLU(aa,1 a,, + a1,3 - -1)) + +1). (E(M)
Σ
So we can get the output of Module 2, which is
C2 = (v(v),
Module 3. The last module is designed to compute the final output r(s, Given the input e2 = (vi(v,, k, a), we can compute the output r(s, a) by
r(s,a) [[v(v) A = n + 1)] + 0.5 1 2n + 2].
While the input can take polynomial types of values most, according to Lemma I.5, can use the MLP to implement this function. Therefore, we can use a constant layer MLP with polynomial hidden dimension implement the reward function of dimension 3-SAT MDP.
Transition Kernel of 3-SAT MDP. We can use constant layer MLP with polynomial hidden dimension to implement the transition kernel 3-SAT MDP. Denote the input
Co (c,, a) (cp, a,)
which embeds the state s = (1b, v. k) and the action a. We only need to modify the embeddings and k and denote them as v and K. According (E.1) in the proof of the transition kernel of Theorem 3.3, we have the output v' and l of the following form:
d = C
v'i = (v[1] A 1 + R)) V (a A 1[; k)),
(G.1)
= (k: 1)
1 [k 2 + 1 0 A 1]+ (n 2) 1[a ==
In 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 1.5, each output element can be computed by constant-layer MI.P polynomial size, and the overall output can be represented by a constant layer MLP of polynomial size.
28

---

Reward Function of NP MDP. We can use constant layer MLP with polynomial hidden dimension implement the reward function of NP MDP. Denote the input
ep (e a) = (e2s k,
which embeds the state 8 = (c, k) = (s t, 1),,k) k) and the action a. By (E.2) in the proof of Theorem 3.8, the transition function can be computed by the formula
r(s,a) [[(SM Snceept) A (k P(n) + 1)] + 0.5 1 2P(n) 2].
Therefore, the reward r(s, a) is determined by a tuple (s k), which has polynomial value types at most. According Lemma 1.5, we compute this function by constant-layer MLP of polynomial hidden dimension.
Transition Kernel of NP MDP. Finally, we switch to the transition kernel of NP MDP. Denote the input
eo = (e., a) = (ec, a),
which embeds the state s - (c, k) (sar, 1,,,k) and the action and denote the dimension of is P(n). We obtain the final output in three steps. The first step is to extract the content X of the location on the tape by the formula
V <E(P(x))
(t|d A =(==()) I]).
We further convert it to the form in MLP by
X = ReLU Σ
x!) ReLU Σ x Σx- sE[P(m)
11)
where Xr =t]]] 1[
sE(P(n)
Regarding the configuration d' (s t²,1)) defined in (3.4), we notice that
(i) the Turing Machine state s'y is determined by s, a and XG
(ii) the content of the location on the tape, t'll], is determined by sys, and x. whereas the contents of the other locations on the tape remain unaltered, i.e., {' t[i] for i + k;
(iii) the pointer determined by MM a and X-
In addition, the number of steps k is determined by k and Therefore, each output element is determined by an element or a tuple of elements having polynomial value types at most. According to Lemma I.5, constant-layer MLP of polynomial size can compute each output element, and the overall output can be computed by constant-layer MLP of polynomial size.
G.3 Proof Theorem 5.3
Proof of Theorem 5.3. According to Lemma 1.7, the computational complexity of MLP with constant layer, polynomial hidden dimension (in n)), and ReLU as the activation function upper-bounded by TC On the other hand, according to Theorem 3.3 and Theorem 3.8, the computation of the optimal policy and optimal value function for the 3-SAT MDP and NP MDP is NP-complete. Therefore, the theorem holds under the assumption of TC * NP.
G.4 Proof of Theorem 5.4
Proof of Theorem 5.4. We show that the reward function, transition kernel, and optimal policy of both CVP MDPs and MDPs can be individually represented by MLP with constant layers and polynomial hidden dimension.
Reward Function of CVP MDP. We can use a constant layer MLP with polynomial hidden dimension to implement the reward function of CVP MDP. Denote the input
Cp = (c., a) = (Co. .),
29

---

which embeds the state (c, v) and the action According to the definition, we can represent the reward
r(s, a) 1<
By Lemma 1.5, know that [[(nn] 1] can be represented by constant-layer MLP with polynomial hidden dimension. Hence, the reward function of CVP MDP can be represented by constant-layer MLP with polynomial hidden dimension.
Transition Kernel of CVP MDP. We can use constant layer MLP with polynomial hidden dimension to implement the transition kernel CVP MDP. Denote the input
en
(e,, a) (ec, V, aa)
which embeds the state (c, v) and the action Given index i, fetch the node and its value by
Σ
Oiigi
where oi.j = [i 5] v(i).
JE[n]
(G.2)
c
Big:
where Br,j = 1 = j] c[i].
jE(n]
Then, compute the output of node i and denote it as oli]. ofi] is determined by the i-th node e, and its input, therefore, be computed by constant layer MLP with polynomial hidden dimension according to Lemma I.5. Denoting the output as (c's, v'). according to the definition of the transition kernel, we have
=e
v/j - 1 * a] + vlil 1Wi a]
Therefore, we can compute the transition kernel of CVP MDP by 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 the proof of Theorem 4.2 (Appendix F.1). For the convenience of reading, we present the ((s)
optimal policy here again. Given state (c, v). denoting c[t] (c[+][4], e[i] [[i][2].9] gt), we define
((s) -i E [n]
g. V), v/cfi [1]] [2] E {0. 1}, v|i] Unknown)
fie E {-), [[] (0. 1), v[i] = Unknown]
(G.3)
Ufie [n] l E 10, vfil Unknown].
The set (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 x² (s(s) is expressed =*(ss min G(s) Subsequently, we aim to demonstrate that constant-layer ML.P with polynomial hidden dimension compute the optimal policy n² Let [ denote the indicator of whether G(s), i.e., T[
signifies that E (ss), while T 0 denotes that i & ((s). According to (G.3), we can compute T[ depends on the i-th node c[i], its inputs and output, therefore, can be computed by constant-layer MLP with polynomial hidden dimension. Then we can express the optimal policy π as:
(s)
ReLU
E(])
where r' ReL.U11
ΣTT> jdL
iE[m]
Therefore, we can compute the optimal policy by a constant-layer MLP with polynomial size.
Reward Function of P MDP. Denote the input
Cp (e,, a) ((x, Ce, v).a),
which embeds the state (x, v) and the action and denote the size of the circuit as P(n). According to the definition, we have
r(s, a) = [[v[P(n)] = 1].
Owning to Lemma I.5, we can compute the reward function of MDP by constant layer MLP with polynomial hidden dimension.
30

---

Transition Kernel of P MDP. Denote the input
eg = (e,, a) = ((x, ec. v),
which embeds the state 8 (x, C, v) and the action a. We can fetch the node and its value by (G.2). Then we compute the output of node i and denote it as o[i]. where ofi] is determined by the i-th node c[i] and its inputs. Hence, by Lemma I.5, o[i] can be computed by constant-layer MIP with polynomial hidden dimension. Denoting the output (x', e v'), together wths the definition the transition kernel, we have
ec-
[
vii
1 # a] + v(i] 11i = a).
Therefore, we can compute the transition kernel of 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 state (x,c, c, v). denoting c(t] (c/il[1], c[i][]] 9:), let (s) be defined by:
(()) -i [P(n)] 9i E (A, V), v[c[[]]) v E v]]
Unknown
U ff E [P(m] 9: =, v/c[t|[1] E 10. = Unknown]
(G.4)
Ufi E [P(m)] g: Input, vli] Unknown).
The set (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 π r²(s) is expressed as x r²(s) = min ((s) Subsequently, we aim to demonstrate that constant-layer MLP with polynomial hidden dimension can compute the optimal policy n². Let [[] denote the indicator of whether 9(s), i.e. T[
signifies that E (ss). while [[] = 0 denotes that i & ((s). Using (G.4), the computation of T[ depends on the i-th node c,, its inputs, and output. This observation, together with Lemma I.5, allows for the computation through constant-layer MLP with polynomial hidden dimension. Employing this notation, we can formulate the following MLP expression for the optimal policy n²:
(s) ReLU
Σ T(i).
where [' ReLU Σ Tii).
(E(P(m)
jci
Therefore, the optimal policy of P MDP can be represented by constant-layer MLP with polynomial hidden dimension.
G.5 Proof of Theorem 5.5
Proof of Theorem 5.5. By Lemma 1.7, we have that the computational complexity of MLP with constant layer, polynomial hidden dimension (in n), and ReLU as the activation function upper- bounded by TC 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, conclude the proof under the assumption of TC # P.
L
H Discussions on the Extensions of Our Results
H.1 Connections to POMDPs
For the partially observable Markov decision process (POMDP), the agent can only receive the observation E O, generated by the emission function O fO, S + A(O)) one can choose the observation as substring of the state, and the representation complexity of the emission function remains low, similar to the transition kerne.. 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 RI. could be more pronounced.
31

---

H.2 Extension to Stochastic MDPs
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., let V = {ui, uu, Un _u } be the set of literals. An n-diiensional stochastic 3- SAT MDP (S, A, H, M. is defined as follows. The state space defined by S y x {0, 1, Next)" )m (10) U In + 21). where each state can be denoted as s = (vi, V, k). In this representation, & is a 3-CNF formula consisting of n clauses and represented by its 3n literals, v E {0. 1)" can be viewed as an assignment of the n variables and is an integer recording the number of actions performed. The action space is A = {0, 1) and the planning horizon is n² + is defined by:
Given a state s (vù v, k), for any a E A, the reward r(s, a)
If v is satisfiable assignment of v, k + 1 and a Next,
r(s,a) a) = 2
If l: = n² 2n + 2,
(H.1)
Otherwise.
Moreover, the transition kernel is stochastic and takes the following form:
(1b, v,n+
If = = 0,
(1i, 1,
If a = and = 0,
(((..,k)..))
(1,v (1), kk)
If Next, If [n] and (0,
(H.2)
(1,, k.
If > n and a a {0. 1},
where v' is obtained from by setting the k-th bit as with probability 3 and as 1 1-a a with probability 3. and leaving other bits unchanged, i.e.,
[k]
a
with probability
v'(4' = v vik for k' #
[1 1 11-a a with probability
Given a 3-CNF formula sb, the initial state of the 3-SAT MDP is (v), O.. 0).
Theorem H.2 (Representation complexity of Stochastic 3-SAT MDP). Let M, be the n-dimensional stochastic 3-SAT MDP in Definition H.1. The transition kernel P and the reward function of M, can be computed by circuits with polynomial size (in n) and constant depth, falling within the circuit complexity class AC However, computing the optimal value function Qi and the optimal policy x of Mn 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
Transition Kernel. Then, will implement the transition kernel by AC circuits. Slightly different from the deterministic version, in this case, the input of the transition kernel P are two states (w), v, k), s' (v, v', K') and action a, and the output is the probability of transition from to 8'. Given the input v, v,k, vL, k and a, we have the output as follows:
* The output is if the input satisfies the following four equations:
a = Next,
v=
v=v, v.
==
k' =
1k=
2) 1[a k = =0..
32

---

The output is 3 if the input satisfies the following four equations:
E {0, }}:
k= k',
+ =
v' i = (vli) A 1ii + V (a 1 k)).
The output is 3 if the input satisfies the following four equations:
a {0,1},
k ==K,
1p = v²,
v' = (v ^ x) R)).
The output is otherwise.
is noted that each element in the previous equations is determined by at most (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 circuits.
Optimal Value Function. Next, we will prove the -P-hardnsss of computing the optimal value function. Similar to the optimal value function part of the proof of Theorem 3.3, we formulate simpler decision version of this problem: given a state 8 = (4) v. k), an action a and a number y as input, and the goal is to determine whether Q1 (s,aa) > 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 (uy² V uu Vu,) to obtain the 3-CNF Boolean formula vi with n clauses. When the Boolean formula & is not satisfiable, the value of Qi ((0), O,,, 0), 1) is 0. When the Boolean formula is satisfiable, we will prove that the probability of the reward is higher than 1. Note that, when & is satisfiable, we only need to modify the values of the variables at most times to get satisfiable assignment in the deterministic case. In the stochastic case, we have n² chances to modify the value of a variable with a success probability of 2 and to get the reward, compute the probability of getting the reward as
we only need times success. Therefore,
Pr(n times success in n² chances) 2
Pr(one success in n chances))
(1
1 3
1
(H.3)
2n
2
Therefore, & is satisfiable if and only if (( optimal value function is NP-hard.
(20/,,n,. On, 0), 1) > 1. we can conclude that computing the
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 polynomial time reduction from the 3-SAT problem to the problem of computing the optimal policy of 3-SAT MDP. Given Boolean formula of length n, the number of variables is at most n. Then, we can pad several meaningless clauses such as (#, V -m V un) to obtain the 3-CNF Boolean formula v/' with n clauses. When the Boolean formula s is satisfiable, according to (H.3), we have
Optimal Policy.
Ci(('' O,,, 1) 0.7 (ib(", On, 0),
which gives that x" (V' O,, 0) = 1. When the Boolean formula &b is not satisfiable, we have
Qi ((6) O.. 0), 1) = 0 < (i O,,, 0), 0),
which implies that x" (v), O,, 0) = 0. So the Boolean formula vb is satisfiable if and only if x² (v',, O,, 0) 1, which concludes that the problem of computing the optimal policy is NP-hard. O
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 E 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 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. contrast, the computation of the value of i-th node will be correct with the probability of & and will be incorrect with the probability of J.
33

---

And we extend the planning horizon to O(n²) or ((P(n)3). Then we can get similar conclusions as Theorems 4.2 and 4.5. To avoid repetition, we only provide the construction and corresponding theorem of stochastic CVP and omit the proof and the detailed extension to stochastic P MDPs.
Definition H.3 (Stochastic CVP MDP). An n-dimensional Stochastic CVP MDP is defined as follows. Let C be the set of all circuits of size The state space S is defined by S = C x {0, 1, Unknown }" where each state 8 can be represented as 8 = (c. v). Here, с is a circuit consisting of n nodes with cli] (c] [[]][]] 9i) describing the i-th node, where c|i][1] and c[i][2] indicate the input node and gi denotes the type of gate (including A, V, m. 0, 1). When g: E {A, VJ. the outputs of - node and [ node serve as the inputs; and when 9i -, the output of cli] [1]-t node serves as the input and [ is meaningless. Moreover, the node type of 0 or denotes that the corresponding node is leaf node with value of 0 or 1, respectively, and therefore, c]]][1], c[i][2] both meaningless. The vector v E {0, 1, Unknown)" 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 is A = [n] and the planning horizon is H = n + 1. Given a state-action pair (s (c, v), a), its reward r(s,a) a) is given by:
r(s,a)= {
If v contains correct value of the n gates and the value of the output gate v(n] = 1,
Otherwise.
Moreover, the transition kernel is deterministic and can be defined as follows:
P((c, v), = (c, v').
Here, v' is obtained from v by computing and substituting the value of node with the probability of 3. More exactly, if the inputs of node a have been computed, we can compute the output of the node and denote it as ofa]. Let ō[a] be random variable getting value of o(a] with probability of 2/ and getting value of Unknown with probability of 3 Then we have
vb] oaa]
If a * j.
If = and the inputs of node have been computed,
Unknown
If = j and the inputs of node a have not been computed.
Given a circuit c, the initial state of CVP MDP is (c, Vunknoww)) where Vunknown denotes the vector containing n Unknown values.
Theorem H.4 (Representation complexity of Stochastic CVP MDP). Let M, be the n-dimensional stochastic CVP MDP in Definition H.1. The transition kernel P, the reward function r, and the optimal policy n² of M, can be computed by circuits with polynomial size (in n)) and constant depth, falling within the cireuit complexity class AC". However, computing the optimal value function Qi of M, are P-hard under the log space reduction.
I Auxiliary Lemmas
Lemma I.1 (Cook-Levin Theorem [12, The 3-SAT problem is NP-complete.
Lemma 1.2 (P-completeness of CVP [28]). The CVP is P-complete.
Lemma 1.3 (Theorem 6.5 in [3]) A language has log-space-uniform circuits of polynomial size and only if it is in P.
Lemma I.4 (Implement Any Boolean Funetion). For every Boolean function f (0, 1)' (0,
there exists two layer circuit of size O(1 2 such that c(u) fu) for all E (0,
Proof. For every E (0,13%.1m let
(u) A (us), iE[m)
where go (u(i)) -uli and 91 (uli)) = u uii) Then we have cy (u) = if and only if v. When
there exists u E {0, 1} such that f(u) 1, we can construct the two-layer circuit as
c(u) V
(c.(
34

---

By definition, we can verify that f(u) c(u) for any E {0.1H. When f(u) = 0 for all u E (0,1)' we can construct the circuit as c(u) = o. Therefore, for every Boolean function f: {) 1] + {0, 1), there exists a two-layer circuit c of size Oll 2') such that c(u) = (u) for all u (0, 13,, which concludes the proof of Lemma I.4.
Lemma 1,5 (Looking-up Table for MLP). For any function f X' + R. where X' is finite subset of R', there exists constant-layer MLP JMLP with hidden dimension Oll (X) such that fas (x) f(x) for all x E X.
Proof. Denote the minimum gap between each pair of elements in X' by 8mins i.e.,
Ōmin = min ||u
vlloo.
u.ex
For each E X, we can construct an MLP as
[a(x) = ReL.U
Σ
[no(x) - (1 1)- -.min)
iE|!
where
fn.(x) = ReeLeu2200 20min 2 ReLU(x(i] u(i) ReLU(uli] x(i] + +dmin))
We have
6min
If u Ifx fu}
fx(x) (0
Then we can construct the MLP SMIP as
fu(()) f(u))
fMLP(X) Σ
6min
uES
is easy verify that fMLL(x) = fxx for all x X, which concludes the proof of Lemma I.5. 11
Lemma L66 (MLP can Implement Basic Gates in TC²). Given E {0, 1)" input, constant-layer
MLPs can implement the following basic operation functions:
AND: fx) AVE(N] x[i]:
OR: fx)(x) Vie(n) x(i];
NOT: [NOT(x(11) - x(1):
Majority: SMAI(X) = 1[Eie(m x(i] > 7)
Proof. We express the four functions in the MLP forms as follows:
fAND(x) ReLU(E x|i] inn +
Sor(x) = 1 - ReLU(1 EiE(n) x(i)):
[NOT(x(1]) = 1 x(1]:
fMAI(x) = ReLU(2- Ete(n) x|i] n) - ReLU(2 Eie x(1] - 1).
Therefore, the basic gates of TC 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- prepiscciooon MLP with constant layers, polynomial hidden dimension (in the input dimension), and ReLU the activation function can be simulated by L-uniform TC circuits.
35

---

Proof. In the previous work by [36], it was demonstrated that Transformer with logarithmic precision, a fixed number of layers, and a polynomial hidden dimension can be simulated by L-uniform TC 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 submodule of the Transformer, follows that a oog-precision MLP with consistent number of layers, polynomial hidden dimension, and ReLU as the activation function can be simulated by L-uniform TC circuit.
36

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided a proper justification given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] " is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer is often more nuanced, so please just your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sections 3, 4, and 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Appendix C.
37

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are provided in the main paper, and the proof can be found in the Appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
38

---

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 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. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 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 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 NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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 (uttps://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. /tipss.ccppublll/ wttpc//cppcccggguceeeeeoo
sesisssssssosoiii iislcnncycy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
39

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Experiments conducted in 5 seeds, and the statistical significance is reflected in Figure 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
40

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttt://nnei...p.eee cc/public/ httt//iiiaeeeeeeeeeeee etthichuuieeenneee.
Answer: [Yes]
Justification: The research in this work conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
41

---

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

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
43


Reviews:
[{"review_id": "uKkUsVXCje", "reviewer": "Reviewer_eFNz", "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.", "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.\n\n1. 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?\n2. 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": "The authors do not have an explicit limitations section or paragraph.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The study uses time complexity and circuit complexity to theoretically analyze the representation complexity among RL paradigms. It introduces new classes of MDPs (3-SAT MDPs, NP MDPs, CVP MDPs, and P-MDPs) to showcase the differences in complexity. \n2. The paper finds that models and policies can often be effectively represented by MLPs, while optimal value functions face limitations, providing insights that may inform future research.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the Reviewer for the positive feedback and appreciation for our work.\n\n**Q1:** Do the findings regarding the representation complexity hierarchy hold consistently across different task settings, or do they vary significantly with various types of tasks?\n\n**Response:** Yes, our findings on the representation complexity hierarchy demonstrate consistent behavior across a diverse array of task settings. (i) Theoretically, we can encode *any* $\\mathsf{NP}$ or $\\mathsf{P}$ problem into the construction of MDPs and establish the desired representation complexity hierarchy, characterizing a wide range of problems. (ii) Empirically, we have conducted experiments across various simulated environments, each designed to test different aspects of task complexity. These environments range from simple binary classification tasks to more complex structured prediction problems. In all these settings, the hierarchy we have identified remained robust and consistent. Thank you for raising this important question and we will further emphasize this in our revision.\n\n\n\n**Q2:** 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?\n\n**Response:** Thank you for your question. Our research findings indicate that the model typically benefits from the lowest representation complexity, which may explain why model-based reinforcement learning generally achieves better sample efficiency in real-world applications (see Appendix C.1 for more details). Moreover, we'd like to emphasize that our work primarily focuses on providing the first comprehensive theoretical understanding of representation complexity across various reinforcement learning paradigms. We hope this understanding will inspire the following empirical works and lead to practical advancements in sample efficiency.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K4GOU9NfaC", "reviewer": "Reviewer_UVj9", "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.", "questions": "Please answer the points mentioned in the weaknesses.", "limitations": "The paper does not discuss their limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper gives a new understanding and improves RL algorithms by examining RL paradigms through the lens of representation complexity.\n- The paper includes deep RL experiments that align with the theoretical findings, offering practical evidence of the proposed hierarchy.\n-The paper bridges theoretical insights with deep RL by discussing the expressiveness of MLPs.", "weaknesses": "- While the theoretical insights are significant, the paper does not extensively explore their direct implications for real-world RL applications.\n- 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. \n- Could the proposed hierarchy of representation complexity be applied to other types of neural network architectures beyond MLPs, such as transformers?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We appreciate your feedback and will address each of your concerns individually.\n\n**Q1:** While the theoretical insights are significant, the paper does not extensively explore their direct implications for real-world RL applications.\n\n**A1:** Thank you for recognizing the theoretical insights of our work. In fact, our research empirically demonstrates a consistent representation complexity hierarchy, accompanied by a theoretical understanding from the perspective of deep neural networks (a completely new perspective in RL theory!). Our work also has implications for explaining why model-based RL is more sample-efficient. We view our work as the beginning of a comprehensive understanding of representation complexity in RL; therefore, further direct implications for RL algorithms in real-world applications are left for future work.\n\n\n**Q2:** 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.\n\n**A2:** Our theoretical analysis focuses on the **representation complexity** of RL paradigms, explaining the initial sample efficiency of model-based methods. We recognize that as training advances, the direct policy representation in model-free methods may lead to more efficient optimization, potentially outperforming model-based approaches.  This difference primarily stems from the distinct **optimization properties** of various reinforcement learning algorithms.\n\n\nWe emphasize that **representation complexity and optimization properties are two parallel and equally important aspects**. Our work fills a gap in understanding representation complexity in RL theory. We fully agree with the reviewer that integrating optimization efficiency with representation complexity to comprehensively understand the performance differences between various RL algorithms is a promising (and challenging) direction for future research. We appreciate the reviewer highlighting this important area of investigation.\n\n\n**Q3:** Could the proposed hierarchy of representation complexity be applied to other types of neural network architectures beyond MLPs, such as transformers?\n\n**A3:** Our hierarchy of representation complexity **can be applied to the transformer architecture**. Please see the **general response** for the details.\n\n---\nPlease let us know if you have any further questions. If your concern is addressed, we would appreciate it if you would reconsider your score in light of our clarification.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VeRgnnodah", "reviewer": "Reviewer_4u4n", "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.", "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?\n- Maybe you should describe more examples to intuitively understand the representation complexity of the model, optimal policy, and optimal value function.", "limitations": "The paper is mainly theoretical, and no algorithm is implemented. There is no specific potential negative societal impact of this work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written. The problem studied in this paper is well-motivated and very interesting.\n- Analyzing model-based RL, policy-based RL, and value-based RL from the perspective of representation complexity, transitioning from simple scenarios to broader ones, is impressive.", "weaknesses": "- 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.\n- Although it is a theory paper, I would have liked to see more experiments designed to validate the conclusions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We appreciate your feedback and will address each of your concerns individually.\n\n---\n\n**W1:** 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.\n\n**Response:** We appreciate the reviewer's point regarding the complexity of MLPs in modern deep RL. However, our experiments are conducted in Mujoco environments where the approximation challenges are relatively modest. In these settings, MLPs with 3 layers and 256 hidden units each have been shown to perform near the state-of-the-art (SOTA) when utilizing algorithms such as TD3 (and SAC...). This indicates that the complexity of the function approximators required for these environments is not high. Consequently, using simple 2 or 3-layer MLPs as our testbed is a reasonable choice for the scope of our study. Moreover, as Mujoco environments are classic and extensively utilized benchmarks within the deep RL community, insights gained from these experiments hold significant relevance. \n\n**W2:** Although it is a theory paper, I would have liked to see more experiments designed to validate the conclusions.\n\n**Response:** We recognize the value that additional experiments would bring, particularly in complex environments (such as robotics), to reinforce our conclusions. Unfortunately, due to constraints in resources, extensive experimentation in diverse real-world scenarios was not feasible within the scope of this study. However, we selected Mujoco environments for our experiments because they are classic and widely recognized benchmarks in the deep reinforcement learning community. The experiments are conducted in 4 environments and repeated with 5 random seeds, and the results are therefore fairly sufficient to support our theoretical results and contribute to the general understanding of our theoretical claims. If the reviewer has more concrete suggestions to enhance the experiments, we are happy to incorporate them.\n\n**Q1 & Q2:** (1) 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? (2) Maybe you should describe more examples to intuitively understand the representation complexity of the model, optimal policy, and optimal value function.\n\n**Response:** Thank you for your question. The fundamental difference in representation complexity for optimal policies and value functions in Sec. 3 and Sec. 4 stems from the nature of the decision-making process in various reinforcement learning (RL) scenarios.\n\nIn Sec. 3, we consider environments with long-term dependencies where the optimal policy needs to encapsulate complex strategies due to the high branching factor of possible future state trajectories. Here, the representation complexity of both the policy and the value function is high since they must incorporate information about the consequences of actions over many time steps. This is akin to games like chess, where the policy must be sophisticated enough to navigate a vast tree of possible moves.\n\nIn contrast, Sec. 4 addresses environments with shorter planning horizons. The optimal policy in such settings can be less complex because it's more focused on immediate states which is sufficient to make a good decision. However, the optimal value function may still require a complex representation to accurately predict long-term returns from any given state due to the potential variability in future rewards. An example provided is a robotic gripping task where the immediate action (gripping with the correct force) is straightforward, but the long-term implications (successfully gripping various objects without dropping) add complexity to the value function.\n\nIn the [Mujoco environment](https://www.gymlibrary.dev/environments/mujoco/index.html)(e.g. [Ant-v4](https://www.gymlibrary.dev/environments/mujoco/ant/)), the transition kernels and reward functions of these environments are some simple functions containing several rules. However, as for the optimal policy and optimal value function, they are so complex that need a complex neural network to approximate and a well-designed RL algorithm to learn.\n\nIn summary, the complexity of the optimal policy and value function representations is intrinsically linked to the depth of foresight required for decision-making in a given RL scenario. We will add more analysis in our paper to illustrate this distinction and its implications for the design of RL algorithms.\n\n---\n\nPlease let us know if you have any further questions. If your concern is addressed, we would appreciate it if you would reconsider your score in light of our clarification.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4o0vfUQweL", "reviewer": "Reviewer_YjQh", "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\".", "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.\n\nThis 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?\n\nOther, minor issues:\n- All figures are barely legible at a \"reasonable\" zoom level, I would encourage the authors to quickly redesign these.", "limitations": "See above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper dives deep into an established conjecture in reinforcement learning, that learning a model of an environment can be easier than learning a value function. With a clever reduction to a simple exemplary class of MDPs, the authors show that is \"difficulty\" is measured by the complexity of a circuit necessary to represent the respective function, then classes of problems exist in which this is indeed true. \nThe mathematical derivations and proofs are straightforward and seem correct to the extent that I am able to verify them, although my expertise lies in RL and not complexity theory. They provide stronger results than previous work in the same direction [1] and seems like a good follow up work.\n\n[1] ON REPRESENTATION COMPLEXITY OF MODEL-BASED AND MODEL-FREE REINFORCEMENT LEARNING, Hanlin Zhu, Baihe Huan, Stuart Russell, ICLR 2024", "weaknesses": "I have one major confusions which I list under questions since these are hopefully easily addressable in the rebuttal.\n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We appreciate your feedback and will address each of your concerns individually.\n\n---\n\n**Q1:** 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.\n\n\n**A1:** Thank you for your question. We have acknowledged in our paper that our complexity hierarchy does not hold for all MDPs, and provide a detailed discussion in Appendix C.2. For the convenience of the reviewer, we paste Appendix C.2 below:\n\n> 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 $\\mathsf{NP}$ or $\\mathsf{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:\n\n> **Proposition:** Given a Markov Decision Process (MDP) $\\mathcal{M}=(\\mathcal{S}, \\mathcal{A}, H, \\mathcal{P}, r)$, where $\\mathcal{S}\\subset\\{0,1\\}^n$ and $|\\mathcal{A}|=O(\\mathsf{poly}(n))$, the circuit complexity of the optimal value function will not fall below the optimal policy under the $\\mathsf{TC}^0$ reduction.\n\n\n> However, our representation complexity hierarchy is not valid for all MDPs.\nFor 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 (*this aligns with the \"counterexample\" noted by the reviewer*). 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.\n\n\n\n**Q2:** 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?\n\n**A2:** Thank you for your question. It's difficult to argue that Mujoco environments fall into the category of constructed MDPs for theoretical understanding. However, constructed MDPs and Mujoco environments (or more general real-world applications) share similar features: they encode complex decision-making problems into relatively simple models (reward and transition). Our theoretical framework aims to characterize a broad range of real-world problems by incorporating $\\mathsf{P}$ or $\\mathsf{NP}$ problems into the transition. This way of study aligns with the theoretical understanding of deep learning, where researchers typically demonstrate or explain phenomena (such as benign overfitting) in ideal theoretical models (such as linear regression or two-layer neural networks). Moreover, we want to emphasize that our work uses a completely new perspective --- the expressive power of neural networks --- to study RL problems, which is highly related to our experiments and can be considered an important step in bridging the gap between theory and practice. Finally, for the reasons stated above, we believe the demonstrated representation hierarchy, although not universal, characterizes a wide range of RL problems and is definitely not an artifact of the choice of environments.\n\n---\n\nWe sincerely hope the reviewer will reconsider their rating of our work, which is the first comprehensive study of representation complexity. We are also open to further discussion if the reviewer has any concerns about the correctness of our proof or the contribution of our research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate all the reviewers for reviewing our paper. We have provided comprehensive responses separately and demonstrate in our general response that our findings can be extended to deep reinforcement learning with **transformer** architectures.

Here are some informal theorems and proof sketches. We will incorporate these theorems in the next version of this paper.

> **Theorem:** Assuming that $\mathsf{TC}^0\neq\mathsf{NP}$, the optimal policy $\pi_1^*$ and optimal value function $Q_1^*$ of $n$-dimensional 3-SAT MDP and $\mathsf{NP}$ MDP defined with respect to an $\mathsf{NP}$-complete language $\mathcal{L}$ cannot be represented by a Transformer with constant layers, polynomial hidden dimension (in $n$), and ReLU as the activation function.

> **Theorem:** Assuming that $\mathsf{TC}^0\neq\mathsf{P}$, the optimal value function $Q_1^*$ of $n$-dimensional CVP MDP and $\mathsf{P}$ MDP defıned with respect to a $\mathsf{P}$-complete language $\mathcal{L}$ cannot be represented by a Transformer with constant layers, polynomial hidden dimension (in $n$), and ReLU as the activation function.

> **Proof:**  According to Lemma I.7 in our paper, and the previous work[1], a Transformer with logarithmic precision, a fixed number of layers, and a polynomial hidden dimension can be simulated by a  $\mathsf{L}$-uniform $\mathsf{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 $\mathsf{TC}^0\neq\mathsf{NP}$ and $\mathsf{TC}^0\neq\mathsf{P}$.

> **Theorem:** The reward function $r$ and transition kernel $\mathcal{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:** The reward function $r$, transition kernel $\mathcal{P}$, and optimal policy $\pi^*$ 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 Sketch:** It is important to note that the MLP is a submodule of the Transformer. 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 can just use the MLP module to calculate the corresponding functions.

[1] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics.

Meta-review: 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
Decision: Accept (poster)