On Representation Complexity of Model-based and Model-free Reinforcement Learning
Authors: Hanlin Zhu
Baihe Huang
Stuart Russell
Venue: ICLR 2024 poster (2024)
Keywords: model-based and model-free RL
representation complexity
circuit complexity
approximation error
Primary area: learning theory
TL;DR: We study representation complexity of model-based and model-free RL through circuit complexity to provide unique insights into sample efficiency of model-based RL.

Abstract: We study the representation complexity of model-based and model-free reinforcement learning (RL) in the context of circuit complexity. We prove theoretically that there exists a broad class of MDPs such that their underlying transition and reward functions can be represented by constant depth circuits with polynomial size, while the optimal $Q$-function suffers an exponential circuit complexity in constant-depth circuits. By drawing attention to the approximation errors and building connections to complexity theory, our theory provides unique insights into why model-based algorithms usually enjoy better sample complexity than model-free algorithms from a novel representation complexity perspective: in some cases, the ground-truth rule (model) of the environment is simple to represent, while other quantities, such as $Q$-function, appear complex. We empirically corroborate our theory by comparing the approximation error of the transition kernel, reward function, and optimal $Q$-function in various Mujoco environments, which demonstrates that the approximation errors of the transition kernel and reward function are consistently lower than those of the optimal $Q$-function. To the best of our knowledge, this work is the first to study the circuit complexity of RL, which also provides a rigorous framework for future research.

Published as a conference paper at ICLR 2024
ON REPRESENTATION COMPLEXITY OF MODEL-BASED AND MODEL-FREE REINFORCEMENT LEARNING
Hanlin Zhu", Baihe Huang", Stuart Russell
EECS, UC Berkeley [han] inzhu, bai he huang, russell 1 @ edu
ABSTRACT
We study the representation complexity of model-based and model-free reinforce- ment learning (RL) in the context of circuit complexity. We prove theoretically that there exists a broad class of MDPs such that their underlying transition and reward functions can be represented by constant depth circuits with polynomial size, while the optimal Q-function suffers an exponential circuit complexity in constant-depth circuits. By drawing attention the approximation errors and building connections to complexity theory, our theory provides unique insights into why model-based algorithms usually enjoy better sample complexity than model-free algorithms from a novel representation complexity perspective: in some cases, the ground- truth rule (model) of the environment simple to represent, while other quantities, such as Q-function, appear complex. We empirically corroborate our theory by comparing the approximation error of the transition kernel, reward function, and optimal Q-function in various Mujoco environments, which demonstrates that the approximation errors of the transition kernel and reward function are consistently lower than those of the optimal Q- d-fuucttio. To the best of our knowledge, this work is the first to study the circuit complexity of RL, which also provides a rigorous framework for future research.
INTRODUCTIONS
In recent years, reinforcement learning (RL) has seen significant advancements in various real-world
applications (Mnih et al.) 2013; Silver et al., 2016 Moravčík et al. 2017); Shaley-Shwartz et al. 2016
Yurtsever et al. [2020] Yu al., Kober al.
2014). Roughly speaking. the RL algorithms can be
1995 Rawlings 2000 Luo et al. 2018| Chua et al. 2018 Nagabandi et al. 2020; Moerland al.
categorized into two types: model-based algorithms (Draeger et al.
(023) and model-free algorithms (Mnih et al. 2015 Lillicrap et al. 20155] Van Hasselt et al. [016]] Haarnoja et al. (018). Model-based
algorithms typically learn the underlying dynamics of the model (i.c., the transition kernel and the reward function) and then learn the optimal policy utilizing the knowledge of the ground-truth model. On the other hand, model-free algorithms usually derive optimal policies through different quantities, such as Q-function and value function, without directly assimilating the underlying ground-truth models.
In statistical machine learning, the efficiency of an algorithm is usually measured by sample com- plexity. For the comparison of model-based and model-free RI. algorithms, many previous works also focus on their sample efficiency gap, and model-based algorithm usually enjoys better sample complexity than model-free algorihms (Jin et al. [0018] Zanette & Brunskill 2019 Tu & Recht 2019) Sun al. 2019). In general, the error of learning can be decomposed into three parts: optimiza- tion error, statistical error, and approximation error. Many previous efforts focus on optimization
errors (Singh et al., (2000] AAgaraal et al. 2020 Zhhan al. al.] (023) and statistical errors (Kakade)
2003
Strehl et al. (0066] Auer et al. 20088) Azar et al. 2017]] Rashidinejad et al. 2022 Zhu & Zhang
2024
while approximation error has been less explored. Although a line of previous work studies
"qqual contributions.
For example, the performance difference hetween the learned policy and the optimal policy, which can be translated sample complexity.

---

Published as a conference paper at ICLR 2024
the sample complexity additionally caused by the approximation error under the assumption of bounded model misspecification error (Jin et al. [2019] Wang et al. 2020; Zhu et al. [023] Huang et al. 2021; Zhu et al.] 2024). they did not take a further or deeper step to study for what types of function classes (ineluding transition kernel, reward function, Q-function, etc.), it is reasonable to assume small model misspecification error.
In this paper, we study approximation errors through the lens of representation complexities. Intu- itively, if function (transition kernel, reward function, Q-function, etc.) has low representation complexity, it would be relatively easy to learn it within a function class of low complexity and misspecification error, thus implying a better sample complexity. The previous work Dong al.) (2020) studies special class of MDPs with state space S = [0, 1I. action space A = {0, 1 transition kernel piecewise linear with constant pieces and simple reward function. By showing that the optimal Q-function requires an exponential number of linear pieces to approximate, they provide a concrete example that the Q-function has much larger representation complexity than the tran- sition kernel and reward function, which implies that model-based algorithms enjoy better sample complexity. However, the MDP class they study is restrictive. Thus, it is unclear whether it is a universal phenomenon that the underlying models have lower representation complexity than other quantities such as Q- Q-functions. Moreover, their metrics of measuring representation complexity, i.e. the number of pieces of piece-wise linear functions, is not fundamental, rigorous, or applicable to more general functions.
Therefore, we study representation complexity via circuit complexity (Shannon
which is fundamental and rigorous metric that can be applied to arbitrary functions stored in computers. Also, since the circuit complexity has been extensively explored by numerous previous works (Shannon
1949)
1949: Karp 1982. Furst et al. 1984; Razborov 1989 Smolensky 1987; Vollmer 1999 Leighton 2014) and is still actively evolving, could offer us a deep understanding of the representation complexity of RL, and any advancement of circuit complexity might provide new insights into our work. Theoretically, we show that there exists a general class of MDPs called Majority MDP (see more details in Section 3) such that their transition kernels and reward functions have much lower circuit complexity than their optimal Q-functions. This provides a new perspective for the better sample efficiency of model-based algorithms in more general settings. We also empirically validate our results by comparing the approximation errors of the transition kernel, reward function, and optimal Q f-function in various Mujoco environments (see Section for more details).
We briefly summarize our main contributions as follows:
We are the first to study the representation complexity of RL under a circuit complexity framework, which is more fundamental and rigorous than previous works.
We study a more general class of MDPs than previous work, demonstrating that it is common in a broad scope that the underlying models are easier to represent than other quantities such as Q-functions.
We empirically validate our results in real-world environments by comparing the approxima- tion error of the ground-truth models and Q-functions various MuloCo environments.
1.1 RELATED WORK
Model-based v.s. Model-free algorithms. Many previous results imply that there exists the sample
efficiency gap between model-based and model-free algorithms in various settings, including tabular MDPs (Strehl et al., 2006 Azar et al. 2017 Jin et al.) 2018 Zanette & Brunskill] 2019). linear quadratic regulators (Dean al. 2018 Tu & Recht 2018 Dean et al.) (020), contextual decision processes with function approximation (Sun et 2019), etc. The previous work Dong et al. (2020) compares model-based and model-free algorithms through the lens of the expressivity of neural networks. They claim that the expressivity is a different angle from sample efficiency. On the contrary, in our work, we posit the representation complexity as one of the important reasons causing the gap in sample complexity.
Ground-truth dynamics. The main result of our paper is that, in some cases, the underlying ground-trut truth dynamics (including the transition kernels and reward models) are easier to represent and thus learn, which inspires to utilize the knowledge of the ground-truth model to boost the
2

---

Published as a conference paper at ICLR 2024
learning algorithms. This is consistent with the methods of many previous algorithms that exploit
the dynamics to boost model-free quantities (Buckman et al. 20188 Feinberg et 2018:) Luo Luo et al.
2018:
Janner et al. 22019) perform model-basee planning (Oh et al.
2017: Weber et al. 2017: Chua
et al. 2018 Wang & Ba 2019 Piché et al. 2018 Nagabandi et al.
2018 Du & Narasimhan 2019)
improve the learning procedure via various other approaches [evine & Koltun 2013 Heess et al.
2015
Rajeswaran et al. 2016 Silver et al. 2017 Clavera et al.
2018).
Approximation error A line of previous work (Jin et al. 2019; Wang et al. 2020 Zhu et al.
2023) study the sample complexity of RL algorithms in the presence of model misspecification. This bridges the connection between the approximation error and sample efficiency. However, these without further justifying whether it is reasonable. Our results imply that assuming a small error of transition kernel or reward function might be more reasonable than Q-functions. Many other works study the approximation error and expressivity of neural networks (Bao et al. 2014 Lu et al. 2017 Dong et al. 2020 Lu et al. (02TT) Instead, we study approximation error through circuit complexity, which provides a novel perspective and rigorous framework for future research.
works directly assume small model misspecification
Circuit complexity. Circuit complexity is one of the most fundamental concepts in the theory
of computer science (TCS) and has been long and extensively explored (Savage 1972] Valiant
Trakhtenato 1984 Furst ct al. 1984 Hastad 1986 Smolensky 1987 Razborov 1987 1989
Boppana & Sipser 1990, Arora Barak 2009). this work, we first introduce circuit complexity
to reinforcement learning to study the representation complexity of different functions including
transition kernel, reward function and Q-functions, which bridges an important connection between TCS and RL.
1.2 NOTATIONS
Let 1, = (1,..., 1) E &hd denote the all-one vector and let Og (O....., E R denote the all-zero vector. For any set X' and any function f X' - X. (x) is the value of f applied to x after times, i.c., (x) f(x) and (x) f(f(.ff.... f()))...)
Let [x] denote the smallest integer greater than or equal to x, and let [x] denote the greatest integer less than or equal to We use {0, 1]" to denote the set of n-bits binary strings. Let 6, denote the
1, A and use 1()) denote the indicator function. Let [n]]
Dirac measure: (A)
0, &
denote the set (1, (1. n and let {0, 1... denote the set of all natural numbers.
PRELIMINARIES
2.1 MARKOV DECISION PROCESS
episodic Markov Decision Process (MDP) is defined by the tuple M A, where is the state space, AA is the action set, H is the number of time steps in each episode, T the transition kernel from S x to (S)) and r = { is the reward function. When T(-|s, a) = 8,,, i.c., T is deterministic, we also write T(s, a) s'. In each episode, the agent starts at fixed initial state $1 and at each time step h E [H] takes action aj. receives reward (n 0n) and transits to Sh+1 T(-|sk, a.). Typically,
assume (s a,) [0. 1].
policy æ is a length- H sequence of functions т = {TA, + A(A)) Given a policy म. we define the value function Vi as the expected cumulative reward under policy starting from 8 = s (we abbreviate V = Vi
(6)
E
Σ 1=h
re re( az)
3

---

Published as a conference paper at ICLR 2024
and we define the Q-function (s. a) as the the expected cumulative reward taking action in state S). = s and then following x (we abbreviate Q" := Qū):
H
(8, = E
Σ
re ax) ax) 8n 8, a, a,
The Bellman operator Ta applied to Q-function Qu+1 is defined as follow Th ((Q++1) a) (n(ss a) + (x [max Qh+ (s',a')).
There exists optimal policy x² that gives the optimal value function for all states, i.e. V (s) sup, V (s) for all h E [H] and 8 E (see, e.g. Agarwal et al. (2019)) For notation simplicity, we abbreviate V" as V* and correspondingly Q" as Q". Therefore Q" satisfies the following Bellman optimality equations for all s E S, E A and h E [H]:
(s, Th (Q%
2.2 FUNCTION APPROXIMATION
In value-based (model-free) function approximation, the learner is given a function class F Fi x... x FH, where Fr. C (f x A + [0, H] is set of candidate functions to approximate the optimal Q-function Q*
In model-based function approximation, the learner is given function class J = ... Fu. where Fr. C [ S x A + A(S)} is a set of candidate functions to approximate the underlying transition function T. Additionally, the learner might also be given function class R₁ X Ry where EA c {f : S x A + [0, is set of candidate functions to approximate the reward function r. Typically, the reward function would be much easier to learn than the transition function.
To learn function with large representation complexity, one usually needs a function class with a large complexity to ensure that the ground-truth function (approximately) realized in the given class. A larger complexity (e.g.. log size, log covering number, etc.) of the function class would incur a larger sample complexity. Our main result shows that it is common that an MDP has transition kernel and reward function with low representation complexity while the optimal Q-function has much larger representation complexity. This implics that model-based algorithms might enjoy better sample complexity than value-based (model-free) algorithms.
2.3 CIRCUIT COMPLEXITY
To provide a rigorous and fundamental framework for representation complexity, in this paper, we circuit complexity to measure the representation complexity.
Circuit complexity has been extensively explored in depth. In this section, we introduce concepts
related to results. One can refer to Arora & Barak (2009); Vollmer (1999) for more details.
Definition 2.1 (Boolean circuits, adapted from Definition 6.1, (Arora & Barak 2009)). For every m,n E Z.,, Boolean circuit C with inputs and outputs is directed acyclic graph with sources and m sinks (both ordered). All non-source vertices are called gates and are labeled with one of (AND), V (OR) or (NOT). For each gate, its fan-in is the number of incoming edges, and its fan-out is the number of outcoming edges. The size of C' is the number of vertices in it. The depth of C' is the length of the longest directed path in it. A circuit family a sequence {Cn Inn,,,, of Boolean circuits where Cn has inputs.
If C is a Boolean circuit, and x (z)) E {0, 1) its input, then the output of C on x, denoted by C(z), is defined in the following way: for every vertex of C, value val(v) is assigned to such that val(e) is given recursively by applying v's logical operation on the values of the vertices pointed to v; the output C(x) is m-bits binary string y (y,...., Bm), where y; is the value of the i-th sink.
Definition 2.2 (Circuit computation). A circuit family is sequence C (2,,C Cn...... )). where for every n E Lz, C₂ is a Boolean circuit with n inputs. Let fo be the function computed by Cn Then say that C' computes the functiin f 10, 1}" + {0, 1)", which is defined by Cw (w), Vw E {0, 13*
f fw)
4

---

Published as a conference paper at ICLR 2024
where lm| is the bit length of More generally, say that function f N - N can be computed by C' if f can be computed by where the imputs and the outputs are represented by binary numbers. Definition 2.3 ((k, m)-DNF). (ks, m)-DNF is a disjunction of conjuncts, i.e., a formula of the form
V
X
where K; S k for every i E [r]], Ex= k S m, and X1,, is either a primitive Boolean variable or the negation of primitive Boolean variable.
Definition 2.4 (AC"). AC is the class of all boolean functions f 10, - 10, x for which there is circuit family with unbounded fan-in, n (1)) size, and constant depth that computes f.
In this paper, study representation complexity within the class of constant-depth circuits. Our results depend on two "hard" functions, parity and majority functions, which require exponential size circuits to compute and thus are not in AC Below, we formally define these two functions respectively.
Definition 2.5 (Parity). For every n. E Z.,, the n-variable parity function PARITY : {0, 1) > {0, 13 defined by PARITY, (II,..,, Ei= 3z mod 2. The parity function PARITY
[0.1)* 1 - {0, 1) is defined by
PARITY (w) == PARITY |ui (w), Vw E 10.
Proposition 2.6 (Furst et al. 1984 PARITY ACO
THEORETICAL RESULTS
We show our main results in this section that there exists broad class of MDPs that demonstrates separation between the representation complexity of the ground-truth model and that of the value function. This reveals one of the important reasons that model-based algorithms usually enjoy better sample efficiency than value-based (model-free) algorithms.
The previous work Dong al. (2020) also conveyed similar messages. However, they only study a very special MDP while we study a more general class of MDPs. Moreover, Dong et al. (2020) measures the representation complexity of functions by the number of pieces for a piecewise linear function, which is not rigorous and not applicable to more general functions.
To study the representation complexity of MDPs under a more rigorous and fundamental framework. we introduce circuit complexity to facilitate the study of representation complexity. In this work, we focus on circuits with constant-depth. We first show a warm-up example Section 3.T, and then extend our results to a broader class of MDPs in Section 3.2 In Appendix E. we also briefly discuss possible extensions to POMDP and stochastic MDP.
3.1 WARM UP EXAMPLE
In this section we show simple MDP that demonstrates a separation between the circuit complexity of the model function and that of the value function.
Definition 3.1 (Parity MDP). An n-bits parity MDP is defined as follows: the state space is {0, 1 1)"h. the action space is {(t,j) : j E [n]]. and the planning horizon is H Let the reward function be defined by: r(s, a) 1, 8 O.,
Let the transition function be defined as follows: for each 0, otherwise
state s and action a = (i,j), j), transit with probability to where s' given by flipping the i-th and j-th bits of s.
Both T and r can be computed by circuit with polynomial-sine size and constant depth. Indeed, consider the following circuit:
Creward (5) 81 A 82 Sn
5

---

Published as a conference paper at ICLR 2024
Outputs:
@
2m
1(1- Σ
Inputs:
51
ci
cp
S1
Figure 1: Constant-depth circuit of the model transition function in parity MDP. empty node is directly assigned the value of the node pointing to it.
can be verified that Creward = r and it has size n. For the model transition function, we consider the binary representation of the action: for each a (i,j), let (a),..., 4s) denote the binary representation and (16+1,..... a2s)) denote the binary representation of j, where b = [log(n
1)]. Then define the following circuit:
Cmodel a) (sk: 4D &R (a1,....,, .0). @ 8g (06+1, a26))
Σd 20-6 xe mi). We visualize this circuit in Figure D Since the XOR gate and the gate 6ş all be implemented by binary circuits with polynomial size and constant depth (notice that a + = (-a V (a -b) and (z ,,......,,,,,. (b) = (x), k2) ... (z,, V kt) where ko h2 is the binary representation of k), Ciodel also has polynomial size and constant depth.
where (D the XOR gate and & ( mb) =1
However, the optimal Q-function Q' not be computed by a circuit with polynomial size and constant depth. Indeed, it suffices to see that the value function V can not be computed by a circuit with polynomial size and constant depth. To this, notice that ((V* 0) is the parity function, since if there are even numbers I's in ( 8n). then there always exists a sequence of actions to transit to the reward state: otherwise, the number of I's remains odd and will never become O Suppose for the sake of contradiction that there exists a circuit Ovalue with polynomial size and constant depth that computes V* then the circuit
CPARITY(S, a) Cvalue a)1 Cvalue (s, a)2 V .... Cvalue a)n
computes the parity function for and belongs to the class AC This contradicts Proposition 2.6
3.2 A BROADER FAMILY MDPs
In this section, we present our main results, i.e., there exists a general class of MDP, of which nearly all instances of MDP have low representation complexity for the transition model and reward function but suffer an exponential representation complexity for the optimal Q-function.
We consider general class of MDPs called 'majority MDP', where the states are comprised of representation bits that reflect the situation the underlying environment and control bits that determine the transition of the representation bits. We first give the definition of majority MDP and then provide intuitive explanations.

---

Published as a conference paper at ICLR 2024
86-1
$6,+2
8h4n-1
8byn
Control Bits
Representation Bits
Figure 2: Illustration of state for majority MDPs.
Definition 3.2 (Control function). We say that map f from {0, 1) to itself is a control function (0, 13, f(1s) Ib, and
(O)) : k= 1,2, 2 -1,
Definition 3.3 (Majority MDP). An n-bits majority MDP with reward state Sreward E {0, 1)", control function (0, (og(n+1)) {0, 1) []oog(++1)]] and condition C 10, {0, is
defined by the following:
The state space is given by {0, 1)=tb where b Πog(( + 1)]. For convenience, assume = 2 1. Each state is comprised of two subparts = (s[c), s(r]), where s(c] = (si...., (b) E {0, 13 i is called the control bits, and s(r] (sb+1.... Sb4n) {0, 1) is
called the representation bits (see Figure 2):
The action space is {0, 1}: The planning horizon is H 2 m.;
$ a[r] = Breward s(c) = lb.
The reward function is defined by: r(s, a) = 0, otherwise
The transition function is defined follows: define the flipping function g : {0, 13 [n] + 1)" by g(s, i) ($1...., Sis 8n). then T is given by:
[s(c), Ej 20-5. ..)))))).. sf()
C,srr) =1
T( a)
otherwise
that is, if 1 and C(slr) 1, then transit to s' (s|c), g(s(r), where Σ/= 2h-j s $ and (((rr) is given by flipping the i-th bits of s|r] (keep the control bits while flip the i-th coordinate of the representation bits); otherwise transit to s' = (f(s(c)), s(r]) (keep the representation bits and apply the control function f to the control bits).
When C' = 1. we call such an MDP unconditioned.
Although many other MDPs lie outside of the Majority MDP class, most are too random become meaningful (for example, the MDP where the reward state is in a o(n)-sizee connected component). Thus, instead of studying more general class of MDPs, we consider one representative class of MDPs and separate three fundamental notions in RL: control, representation, and condition. We elaborate on these aspects in the following remark.
Remark 3.4 (Control function and control bits). In Majority MDPs, the control bits start Os, and traverse all b-bits binary strings before ending at 1 This means that the agent can can flip every entry of the representation bits, and therefore, the agent able to change the representation bits to any n-bits binary string within 2¹ + time steps in unconditional settings.
The control function is able express any ordering of b-bits strings (starting from On and ending with 13) in which the control bits are taken. With this expressive power, the framework of Majority MDP simplifies the action space to fundamental case of A {0, 1).
Remark 3.5 (Representation bits). In general, the states of any MDP (even for MDP with continuous state spuce) are stored in computer systems in finitely many bit.. Therefore, we allocate n bits the representation bits encapsulate and delineate the various states within an MDP.
"hht is, s|c] binary number equals i.

---

Published as a conference paper at ICLR 2024
Remark 3.6 (Condition function). The condition function simulates and expresses the rules of transition in an MDP. In many real-world applications, the decisions made by an agent only take effect (and therefore cause state transition) under certain underlying conditions, transitions to certain states that satisfy the conditions: for example, an marketing maneuver made by company will only make influence if observes the advertisement law and regulations; move of a piece chess must follow the chess rules; a treatment decision can only affect some of the measurements taken on an individual; a resource allocation subject budget constraints; etc.
only enable
Finally, the following two theorems show the separation result of circuit complexity between the model and the optimal Q-function for Majority MDP in both unconditional and conditional settings. Theorem 3.7 (Separation result of majority MDP, unconditioned setting). For any reward state Sreward E {0. 1 and any control function f {0. 1) {0. 13", the unconditioned n-bits majority MDP with reward state Steward, control function f has the following properties:
The reward function and the transition franctoion.uunctonn can be computed by circuits with polynomial (in n) size and constant depth.
The optimal Q-function (at time step t 0) cannot be computed by circuit with polynomial size and constant depth.
Theorem 3.8 (Separation result of majority MDP, conditioned setting). Fix m n/2.. Let p be uniform distribution over (O(1), DDNFsF of n Boolean variables. Then for any reward state Steward E {0, 13"h and any control function f {0, 1) + {0,1)', with probability at least ()m), the n-bits majority MDP with reward state Sreward, control function f, and condition C sampled p, has the following properties:
The reward function and the transition function can be computed by circuits with polynomial (in n)) size and constant depth.
The optimal Q-function (at time step t = 0) cannot be computed by a circuit with polynomial size and constant depth.
The proof of Theorem 3.7 and Theorem 3.8 are deferred to Appendix [33 and Appendix B.2 In short, they imply that T,r E AC and Q' & AC In fact, we show that the value functions cannot be computed by a circuit with polynomial size and constant depth. Due to the relationship (s,ssa) = r(s. V (T a)), we will treat these two functions synonymously and refer to them collectively as the "value function."
EXPERIMENTS
Theorems 3.7 and 3.8 indicate that there exists broad class of MDPs in which the transition functions and the reward functions have much lower circuit complexity than the optimal Q-functions (actually also value functions according to our proof for Majority MDPs). This observation, therefore, implies that value functions might be harder to approximate than transition functions and the reward functions, and gives rise to the following question:
In general MDPs, are the value functions harder to approximate than transition functions and the reward functions?
In this section, we seek to answer this question via experiments on common simulated environments. Specifically, fix d, m E+, and let F denote the class of d'-epph (i.c., d hidden layers), m-width neural networks (with input and output dimensions tailored to the context). The quantities of interest are the following relative approximation errors
E|| - T(s, 1]
emodel
min PEF
(R(s r(s,))))
Greward
min REF [[(r(s,a))
[[(((s,a)- (x),))))
eQ. (Qnnutction
QEF
min
(((()(s
8

---

Published as a conference paper at ICLR 2024
where the expectation is over the distribution of the optimal policy and the mean squared errors are divided by the second moment so that the scales of different errors will match. Therefore, emodel, Creward EQ function stand for the difficulty for d-depth, m-width neural networks to approximate the transition function, the reward function, and the Q-function, respectively.
HallChotahve
Hopperce
32
realrd
Figure 3: Approximation errors of the optimal Q-functions, reward functions, and transition functions in MuJoCo environments. In each environment, we run 5 independent experiments and report the mean and standard deviation of the approximation errors. All curves (as well as those in Figure displayed with exponential average smoothing with rate 0.2.
For common MuJoCo Gym environments (Brockman et al. 2016), including Ant-v4, Hopper-v4, HalfCheetah-v4, InvertedPendulum-vv4 and Walker2d-v4, we find these objectives by training d- depth, m-width neural networks to fit the corresponding values over the trajectories generated by an SAC-trained agent.
3 In Figure 3 we visualize" the approximation errors under d = 2, w 32. Among the approximation objectives, the reward functions and the model transition functions are accessible, and we use Soft-Actor- consistently observe that the approximation errors the optimal Q-function, in all environments, are much greater than the approximation errors of the transition and reward function. This finding concludes that in the above environments, the optimal Q-functions are more difficult to approximate than the transition functions and the reward function, which partly consolidate our hypothesis. We provide experimental details in Appendix C and additional experiments in Appendix D
(Haarooj et al. (0188) to learn the optimal Q-function. We
CONCLUSIONS
In this paper, we find that in broad class of Markov Decision Processes, the transition function and the reward function can be computed by constant-depth, polynomial-sized circuits, whereas the optimal Q-function requires an exponential size for constant-depth cireuits to compute. This separation reveals a rigorous gap in the representation complexity of the Q-function, the reward, and the transition function. Our experiments further corroborate that this gap prevalent in common real-world environments.
Our theory lays the foundation of studying the representation complexity in RL and raises several open questions:
1. If we randomly sample an MDP, does the separation that the value function & A and the reward and transition function E AC occurs in high probability?
2. For k 2 1, are there broad classes of MDPs such that the value function & A and the reward and transition function AC*?
3. What are the typical circuit complexities of the value function, the reward function, and transition function?
'Our code is available at httphhttt////ttt Setpss//giithie http:://gituub..comree wtt..///eeeooooneeeeeeeeeeeeeeee gourmet/rep_come exi tyrry We used Weights& & Biases (Biewald 2020) for experiment tracking and visualizations.

---

Published as a conference paper at ICLR 2024
REFERENCES
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Alekh Agarwal, Sham M Kakade, Jason Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in Markov decision processes. In Conference Learning Theory, pp. 64-66. PMLR, 2020.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Eetrming-Volumme 70, pp. 263-272. JMLR. org, 2017.
Chenglong Bao, Qianxiao Li, Zuowei Shen, Cheng Tai, Lei Wu, and Xueshuang Xiang. Approxima- tion analysis of convolutional neural networks. work, 65, 2014.
Lukas Biewald. Experiment tracking with weights and biases. Software available from wandb.com com, 2:233, 2020.
Ravi B Boppana and Michael Sipser. The complexity of finite functions. In Algorithms and complexity, pp. 757-804. Elsevier, 1990.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample-efficient reinforcement learning with stochastic ensemble value expansion. Advances in neural information processing systems, 31, 2018.
Kurtland Chua, Roberto Calandra, Rowan McAllister and Sergey Levine Deep reinforcement learning in handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 2018
Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Pieter Abbeel. Model-based reinforcement learning via meta-policy optimization. In Conference on Robot Learning, pp. 617-629. PMLR, 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-679, 2020.
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, pp. 2627-2637. PMLR, 2020.
Andreas Draeger, Sebastian Engell, and Horst Ranke. Model predictive control using neural networks. IEEE Control Systems Magazine, 15(5):61-66, 1995.
Yilun Du and Karthic Narasimhan. Task-agnostic dynamies priors for deep reinforcement learning. In International Conference on Machine Learning, pp. 1696-1705. PMLR, 2019.
Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael Jordan, Joseph E Gonzalez, and Sergey Levine. Model-based value estimation for efficient model-free reinforcement learning. arXiv preprint arXiv: 1803.00000000 2018.
10

---

Published as a conference paper at ICLR 2024
Merrick Furst, James B Saxe, and Michael Sipser. Parity, circuits, and the polynomial -ime hierarchy, Mathematical systems theory, 17(1):13-21) 1984.
Tuomas Haamojj, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pp- 1861-1870. PMLR, 2018.
John Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the eighleenth anmual ACM symposium on Theory of computing, pp. 6-20, 1986.
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap. Tom Erez, and Yuval Tassa. Learn- ing continuous control policies by stochastic value gradients. Advances in neural information processing systems, 28, 2015.
Baihe Huang, Kaixuan Huang, Sham Kakade, Jason Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Going beyond linear rl: Sample efficient neural function approximation. Advances in Neural Information Processing Systems, 118966889833 2021.
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.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learnng provably efficient? In Advances in Neural Information Processing Systems, pp. 4863-4877 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv:1907.05388 2019.
SM Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London, 2003.
Richard Karp. Turing machines that take advice. Enseign. Math., 28:191-209 1982.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.69900 6980, 2014.
Jens Kober, Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. Springer Tracts Advanced Robotics, 97:9-67, 2014.
F Thomssn Leighton. Introduction to parallel algorithms and architectures: Arrays trees- hypercubes. Elsevier, 2014.
Sergey Levine and Vladlen Koltun. Guided policy search. In International conference on machine learning, pp. 1-9. PMLR, 2013.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: (tte::1590009999 2015.
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. SIAM Journal on Mathematical Analysis, 53(5):5465 5506, 2021.
Zhou Lu, Hongming Pu, Feicheng Wang. Zhigiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. Advances neural information processing systems, 30, 2017.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for model-based deep reinforcement learning with theoretical guarantees. arXiv preprint 17Xiv:1807.03858, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 112.502,,,, 2013.
11

---

Published as a conference paper at ICLR 2024
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 5 (187750):529-5555 2015.
Thomas Moerland, Joost Broekens, Aske Plaat, Catholijn M Jonker, al. Model-based rein- forcement learning: A survey. Foundations and Trends@ in Machine Learning, 16(1):1-118, 2023.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no- no-limit poker. Science, 356(6337):508-55 2017.
Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dynam- ics for model-based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE international conference on robotics and automation (ICRA), pp. 7559-7566. IEEE, 2018.
Anusha Nagabandi, Kurt Konolige, Sergey Levine, and Vikash Kumar. Deep dynamics models for learning dexterous manipulation. In Conference on Robot Learning, pp. 1101-1112. PMLR, 2020.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. Advances neural information processing systems, 30, 2017.
Alexandre Piché, Valentin Thomas, Cyril Ibrahim, Yoshua Bengio, and Chris Pal. Probabilistic planning with sequential monte carlo methods. In International Conference on Learning Represen- tations, 2018.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. Epopt: Learning robust neural network policies using model ensembles. arXiv preprint arXiv: 2016.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang. Stuart Russell, and Jiantao Jiao. Optimal conser- vative offline rl with general function approximation via augmented lagrangian. arXiv preprint arXiv:2211.00716, 2022.
James B Rawlings. Tutorial overview of model predictive control. IEEE control systems magazine, 20(3):38-555 02888-52,228 2000.
Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333-338, 1987. URL http:::tt///att strppiisemanttiitioo www.nttcschooaa..cooommm
Alexander A Razborov. On the method of approximations. In Proceedings of the twenty-firs annual ACM symposium on Theory of computing, pp. 167-176, 1989.
John E Savage. Computational work and time on finite machines. Journal of the ACM (JACM), 19 (4):660-61) 674, 1972.
Shai
Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement 2016.
learning for autonomous driving. arXiv preprint
Claude E Shannon. The synthesis of two-terminal switching circuits. The Bell System Technical Journal, 28(1):59-98, 1949.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, and Mare Lanctot. Mastering the game of Go with deep neural networks and tree search. Nature, (7587)4444, 2016.
David Silver, Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac- Arnold, David Reichert, Neil Rabinowitz, Andre Barreto, al. The predictron: End-to-end learning and planning. In Internationaal Conference on Machine Learning, pp. 3191-3199, PMLR, 2017.
Satinder Singh, Tommi Jaakkola, Michael L Littman. and Csaba Szepesvári. Convergence results for single-step on-policy reinforcement-leamingg algorithms. Machine learning, 38:287-308, 2000.
12

---

Published as a conference paper at ICLR 2024
Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pp. 77-82, 1987.
Roman Smolensky. On representations by low-degree polynomials. In Proceedings of 1993 IEEE 34th Anmual Foundations of Computer Science, pp. 130-138. IEEE, 1993.
Alexander Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC model- free reinforcement learning. In Proceedings of the 23rd international conference Machine learning, pp. 881-888, 2006.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements model-free approaches. Conference on learning theory, pp. 2898-2933 PMLR, 2019.
Boris Trakhtenbrot. A survey of russian approaches to perebor (brute-force searches) algorithms. Annals of the History of Computing, 6(4):3844400) 1984.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods the linear quadratic regulator: An asymptotic viewpoint. arXiv preprint arXiv:/8/2..03555, 2018.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference Learning Theory, pp. 3036-3083, 2019.
Leslic Valiant. On non-linear lower bounds in computational complexity. In Proceedings of the seventh annual ACM symposium on Theory of computing, pp. 45-53, 1975.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Heribert Vollmer. Introduction to circuit complexity: a uniform approach. Springer Science & Business Media, 1999.
Ruosong Wang. Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005.10804 2020.
Tingwu Wang and Jimmy Ba. Exploring model-based planning with policy networks. arXiv preprint arXhv:1906.08644 2019.
Théophane Weber, Sébastien Racaniere, David P Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adria Puigdomenech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. Imagination-augneen agents for deep reinforcement learning. arXiv preprint a/Xiv:1707.06203, 2017.
Chao Yu, Jiming Liu, and Shamim Nemati. Reinforcement learning in healthcare: A survey. In arXiv preprint arXiv: /908. 1908.08966 2020.
Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of autonomous driving: Common practices and emerging technologies. IEEE access, 8:58443 554669,, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependee regret bounds in reinforcement learning without domain knowledge using value function bounds, 2019.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejic Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 33(2):1061-100 2023.
Hanlin Zhu and Amy Zhang. Provably efficient offline coal-conditioned reinforcement learning with general function approximation and single-policy concentrability. Advances in Neural Information Processing Systems, 36, 2024.
Hanlin Zhu, Ruosong Wang, and Jason Lee. Provably efficient reinforcement learning via surprise bound. In International Conference on Artificial Intelligence and Statistics, pp. 4032. PMLR, 2023.
13

---

Published as a conference paper at ICLR 2024
Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
14

---

Published as a conference paper at ICLR 2024
A SUPPLEMENTARY BACKGROUND ON CIRCUIT COMPLEXITY
Definition A.1 (Majority). For every 2+, the n-variable majority function MAJORITY,, {0. - 10, is defined by MAJORITY, (Z)...., = 1( Zq > n/2). The majority finction MAJORITY: {0, 10, {0, is defined by
MAJORITY (w) == MAJORITY [oa] (w), Vw E =0,1)².
Proposition A.2 Razborov 1987
Smolensky
1987
1993
MAJORITY & AC
We also introduce another function that can be represented by polynomial-size constant-depth circuits, contrary to the above two "hard" functions.
Definition A.3 (Addition). For every n E Z+, the length-n integer addition function ADDITION, (0, 1)"h x {0, 1] {0, 1} is defined follows: for any binary strings d1, 02 {0, 1)", the value ADDITION, (a) (2) is the (n + 1)-bits binary representation of ai + 02. The integer addition function ADDITION {0, 1) - {0, 13* is defined by
(DD w2) == ADDITION max (1wal) (w0, W2), Ye,, W2 E f0,
Proposition A.4 (Proposition 1.15, Vollmer 1999)). ADDITION E AC
Definition A.5 (Maximum). For every E Z+, the length-n maximum function MAX,, {0, 1)"h x {0, 11mm - {0, 13"h is defined as follows: for any two binary strings a1 02 E {0, 1)", the value MAX,((1: (2) is the n-bits binary representation of max (ax 02)- The maximum function MAX (0, 1) - {0, 1}3 is defined by
MAX(W1, w2) == MAX max f woy. |/ws)) (W1, W2), Vw,, W2 {0, 13
Proposition A.6. MAX AC
Proof of Proposition A.6 Fix any E Z4, and assume wi, W2 {0, 1)". Let
(wi) A (w22) A ( ((w1)) @ (wa))))
V s=1
k
Therefore, [(w] W2). Let the i-th bit of output be
((w1)s A k) V ((w2) A -k),
which is exact the i-th bit of max(wi, w2). This circuit has polynomial size and constant depth, which completes the proof.
B PROOFS OF MAIN RESULTS
B. USEFUL RESULTS
We will use the following results frequently in the proofs.
Claim B.I. If Co, C1.... On are circuits with polynomial (in n) size and constant depth, where C; has ky outputs for each E [r]] and Co has Σn ky inputs, then the circuit
Co (C)( ... (x.())))......
also has polynomial (in n) size and constant depth.
Claim B.2. The XOR gate can be computed by circuit with constant size. Claim B.3. For any integer = poly(n). the gate 5(z1, ... xn) = 1 (A = Σn 2n-i. x;) can be
computed by circuit with polynomial size and constant depth.
15

---

Published as a conference paper at ICLR 2024
B.2 PROOF OF THEOREM 3.7
We need the following lemma. Lemma B,4 (Property of value function in unconditioned Majority MDPs), In an unconditioned n-bits majority MDP with reward state Sreward and control function f, the value function V (at time step t = 0) over {5 E {0, 1,bt" s|c]] = 0b. is given by the following:
(*(s)
Σ (-(96+2 @ Sreward, :))
Proof. To find (s),, it suffices to count the number of time steps optimal agent takes to reach the reward state (1a, $reward).
For the control bits traverse from Og to 1s. it takes 2 time steps. Indeed, by Definition 3.2 (0,) # 1, for any i 2 and f(2 1) (0s) 1. (otherwise, 1, 1,2.... ..... ., 2 1 can
(f(0)0)) k 1, ...... 2 - t} < 2 and as result { { (0,)
not traverse {0, (0.1)) Thus, this corresponds to least 2 time steps in which action a =
is played.
For the representation bits, starting from s[r]. reaching Sreward takes at least
Σ (-6++4 ① Sreward,;))
1=1
number of flipping, because each index such that 8b+i # Sreward, needs to be flipped. This corresponds to at least Ei (-($b++ @ Sreward,s)) time steps in which action a = is played.
In total, the agent needs to take at least 2 + (-=((-(6:: @ Sreward, - times steps before it can receive positive rewards. Since there are 2 + n time steps in total, it follows that the agent gets a positive reward in most -. (-(sb+á Sreward,
time steps. As a consequence,
(*(s) n Σ (-(s0+1 @ Sreward,)) +
On the other hand, consider the following policy:
1, if 8641 + Sreward, where i Σ5 2b-
ा (s))
0, otherwise.
This policy reaches the reward state in 2 "E=I(- control bits takes 2 times steps to reach 1 During these time steps, the control bits (as binary number) traverses o,..., 2
Sreward, time steps. Indeed, the
Thus for any i E [ri] such that 8b+i * 8reward, there exists a time such that the control bits at this time (as binary number) equals and at this time step, the agent flipped the i-th coordinate of the representation bits by playing action 1. Therefore, the representation bits takes C, & Sreward,;)) times steps reach Breward Combining, the agent arrives the state (Op, Sreward) after 2 + D (-(sb+ b Speward,i)) time steps, and then collects reward in each of the remaining
Σt= (86++ Sreward,))) + time steps, resulting in value of
(*) =n Σ (-(86+4 ① Sreward, + 1.
Lemma B.5. Any control function can be computed by a constant depth, polynomial sized (in n) circuit.
Proof. By Claim 2.13 in Arora & Barak 2009), any Boolean function can be computed by CNF
formula, i.e., Boolean circuits of the form
A
V
X1,5
As result, the control function be computed by a depth-2, 2b poly(n) sized circuit.
16

---

Published as a conference paper at ICLR 2024
Now return to the proof of Theorem 3.7
Proof. First, we show that the model transition function can be computed by circuits with polynomial size and constant depth. Consider the following circuit:
modeel (s, a) = (g( (9($1...... Sb. a), ($b+* + (6x (s1,....,
(9,,...,,)). 9b) a=)
where @ the XOR gate, g (0, 1] 1 + {0, 13 such that g(x) Fb. 0); = (f( rb)s A We can verify that Cmodel = T. By Claim B.2 Claim B.3 and Lemma [3.5] the XOR gate, the control function f. and the gate 64 can all be implemented by binary eircuits with polynomial size and constant depth. As result of Claim B.T model also has polynomial size and constant depth.
-a) V (x; A a) for all i E [6]. and 6 , mx) - 1(k
Now, the reward function can be computed by the following simple circuit:
Creward (8) = 81 A... A 8b A (-(86+1 @ Sreward, 1) A .... A (-(86tn ① Sreward,
Finally, show that the value function can not be computed by circuit with constant depth and polynomial size. By Lemma B.4 we have
n n+1- (s) = Σ (-6+++ 1 Sreward,)) {0) U [n] = U2 1],
1=1
which can be represented in binary form with bits. Therefore, the first (most significant) bit of n + +1 (s) is the majority function of (-($6+: @ Sreward, If there exists a circuit Cvalue V with polynomial size and constant depth, then the circuit defined by
CMAJORITY Tx) = n + Cvalue (0s, - + Syeward. "En + Sreward,n)
outputs the majority function in the first bit. By Proposition A.4, CMAJORITY also has polynomial
size and constant depth, which contradicts Proposition 3.8 This means that V can not be computed by circuits with polynomial size and constant depth. Notice that V*(s) max.e (* a) max ( (" (s, 0), (s ((s,)),, 1)}. By Proposition A.6 and Claim BB. we conclude that the optimal Q- function can be computed by circuits with polynomial size and constant depth.
B.3 PROOF OF THEOREM 3.8
We need the following lemmata.
Lemma B.6. With probability least -9(mm, there exists a set A C [m] such that |A|2 n/2 and C(z) = 1 holds for any binary string x E {0, 1) satisfying Speward,s, Vi & A.
Proof. It suffices to show that C'( (frewar)) = with at least - e (0m)) Indeed, in this case, since m < n/2, independent on at least n of the variables Ti,..., Tn. The indices such variables form the set A that we are looking for.
To show that C(seeward) = 1 with at least 1 - c Mmm), we assume WLOG that
V
A
Xis
j=l
where Xig or Xij = -i for some E [m]] Notice
A
Xij = =1
2- 2 2((1)
since each X,y is sampled i...d. from (m), -ar [e]m)m))
uniformly at random. It follows that
PP PCC(#1 ... Fn) = = II
X
i=1
=1
- 2 k-)
[=1
> 1 - 90(m)
17

---

Published as a conference paper at ICLR 2024
Lemma B.7 (Property of value function in conditioned Majority MDPs), In an n-bits majority MDP with reward state Srewards control function f and condition C. if there exists a set A C [n] such that ||= [n/2]] = 2 -1 and C(z)
holds for any binary string E {0, 1] satisfying D; Speward,s; Vi E A, then the value function V over {s (0,1) 1364n : s/c] 0b, Sb+i
8reward, (Vi $ A)} is given by the following:
(*(s) =n
Σ (-( @ Sreward, +1
Proof. To find (s),, it suffices to count the number of actions takes to reach the reward state (1s, Sreward).
For the control bits to travel from 0, to 1s. it takes 2 time steps. Indeed, by 1)
Definition 3.2 (O,) * 1. for any i < 2 - and ( (0,) * 1, (otherwise.
(((() (0.) : = 1, .....
. 2 - 11 < 2
2 - and as a result { I f()((()))))))) (0,) : = 1, 2, ,,,,.,.2 2 ] can
not traverse (0, 10.1)%((0)) (0.)). Thus, this corresponds to at least 2 1 time steps in which action = 0 is played.
For the representation bits, starting from s(r]. reaching Breward takes at least
E(-(54+4 1 Sreward,))
number of flipping, each index i such that 864i # Sreward, needs to be flipped. This corresponds at least Eien( (-6++ @ sreward,)) time steps in which action is played.
In total, the agent needs to take at least 2 + EiEA(-(sb++ ① 3reward.:)) can receive positive rewards. Since there are 2 + time step in total, it follows that the agent gets positive reward in most -ies
times steps before
2 $reward,))) + time steps. As consequence,
(*(s) 5n- E(- @ Sreward,s) +
iEA
On the other hand, consider the following policy:
1, if 8641 F Sreward,5; where i = 2 - .jj
a (s))
0, otherwise.
This policy reaches the reward state in 2 + EiEA(~(<b+s ① 8reward,i)) - time steps. Indeed, the control bits takes 2 times steps to reach 1.. During these time steps, the control bits (as a binary number) traverses O..... 2 1. Thus for any E [ri] such that 8842 * 8reward, there exists a time ( such that the control bits at this time / (as a binary number) equals i, and at this time step, the agent flipped the i-th coordinate of the representation bits by playing action 1 (note that the flipping operation can always be applied since the condition is always satisfied under the current policy). Therefore, the representation bits takes E ① Sreward,i)) a)) times steps to reach Sreward- Combining, the agent arrives the state (0g, Breward) after 2 + +iEA (-66445 @ Sreward,;)) 1 time steps, and then collects reward 1 in each of the remaining EieA (86++ @ Sreward,;) + 1 time steps, resulting in value of
('(s)=n Σ [(-(so+e + Sreward, 1.
Now we return to the proof of Theorem 3.8
Proof. First, we show that the model function can be computed by circuits with polynomial size and constant depth. Consider the following circuit:
Cmodel (s, a) (g(s1,.... sb), (sb+* @ (6x (s........, A ((sr))))
18

---

Published as a conference paper at ICLR 2024
where @ is the XOR gate, 9 {0,1)*+ + {0, 1}th such that g( g( Rb. a); (f mb); A
ma) (x, a) for all [b]. and 6g (.1,..., .........)) .b) ) 1 1 Eン= xz). We can verify that Cmodel T. By Claim B.2 Claim B.3 and Lemma B.5 the XOR gate, the control function f, the function (ss(r]), and the gate 6g can all be implemented by binary circuits with polynomial size and constant depth. As a result of Claim B.1 Cmodel also has polynomial size and constant depth.
Now, the reward function can be computed by the following simple circuit:
Creward (s) 81 A A Ab A (-(s6+1 Sreward,1) )) A ... A (-(56+n Sreward,n)).
Finally, show that with high probability, the value function not be computed by circuit with constant depth and polynomial size. By Lemma B.6 with probability least 1 - e -9(m), there cxists a set A C [m] such that |A| n/2 and C(z) = holds for any binary string x E {0, 1 satisfying 2j i Vi A. We can reduce the size of A by deleting some elements to make |A|= in/2] 2h-1 -11--11 and the above property still holds. Denote A {a(1)
a(L))
where a : [L] + [n]. Define h : 10. + 1]
Sroward.
i A
h ((2,,..., = n V ((ss, s'), where s's
1 + Speward.js
j E
Due to Lemma B.7 h (a:) be represented in binary form with (b bits, and the first (most significant) bit of h(x) is the majority function of x. If there exists a circuit Cvalue polynomial size and constant depth, then the circuit defined by
V with
CMAJORITY ...
FT) n 1 Cvalue (Op: -Fa-'(1 Sreward, -T (m) + Syeward,n)
where a (1) if A, outputs h. By Proposition
A.4 CMAJORITY also has polynomial size
and constant depth. which contradicts Proposition A.2 This means that V can not be computed
by circuits with polynomial size and constant depth. Notice that V*(s) maxac (*(s,, max (Q" 0), (s, By Proposition A.6 and Claim B.1 we conclude that the optimal Q-
function can not be computed by circuits with polynomial size and constant depth.
C EXPERIMENT DETAILS
Table shows the parameters used in SAC training to learn the optimal Q-function Section
Table 2 shows parameters for fitting neural networks the value, reward, and transition functions
Section
Hyperparameter
Value(s)
Optimizer
Adam (Kingma & Ba 2014
Learning Rate
0.0003
Batch Size
1000
Number of Epochs
100000
teip_errtr
0.1
Episode length
1000
Discount factor
0.99
number hidden layers (all networks)
256
number of hidden units per layer
2
target update interval
1
Table I: Hyperparameters in Soft-Actor-Critic
19

---

Published as a conference paper at ICLR 2024
Hyperparameter
Value(s)
Optimizer
Adam (Kingma & Ba 2014)
Learning Rate
0.001
Batch Size
32
Number of Epochs
100
Table 2: Hyperparameters fitting neural networks to the value, reward, and transition functions
D ADDITIONAL EXPERIMENT RESULTS
Under the same experiment settings in Section 4 we conduct further experiments using varying neural network depth and width to approximate the the optimal Q-functions, reward functions, and transition functions. The results are shown in Figure Figure 7 Furthermore, since the optimal Q-function calculated by the critic in the SAC algorithm might be biased due to under-estimation since clipped double Q learning is adopted, we also use critics the Actor-Critic algorithm (Appendix [D.]) and Monte Carlo simulation to evaluate the Q-function of the learned actor (Appendix (.2) to obtain an unbiased estimation of the optimal Q-function.
32
000
Figure 4: Approximation errors of the optimal Q-functions, reward functions, and transition func- tions in MuloCo environments, using 2-(hidden) layer neural networks with width 128. In each environment, we run 5 independent experiments and report the mean and standard deviation of the approximation errors.
D.1 FITTING Q- VALUES LEARNED BY ACTOR-CRITIC
In addition approximating the Q-functions learned from SAC, we also fit the value functions learned in Actor-Critic algorithm. The result, displayed in Figure exhibits that the value functions more difficult to approximate than the reward and the transition functions.
D.2 FITTING Q- VALUES FROM MONTE- MONTE-CARLO SAMPLING
We also consider Monte-Carlo estimate of the Q-values of the actors learned by SAC. In Figure 9 we visualize the approximation errors (in log scale), which confirms the phenomenon found in Section
E EXTENSIONS TO STOCHASTIC MDP AND POMDP
In this section, we briefly discuss possible approaches of generalizing our frameworks to stochastic MDP and partially observable MDP (POMDP).
20

---

Published as a conference paper at ICLR 2024
NitOwisk at
Waleeee
0011
0000
0000
Figure Approximation errors of the optimal Q-functions, reward functions, and transition functions in MuJoCo environments, using 1-(hidden) layer neural networks with width 16. In each environment, we run 5 independent experiments and report the mean and standard deviation of the approximation errors.
Raagerve
33
32
Wileeivvt
1.5
0%
000
Figure 6: Approximation errors of the optimal Q-functions, reward functions, and transition functions in MuJoCo environments, using 3-Chidden) layer neural networks with width 64. In each environment, we run 5 independent experiments and report the mean and standard deviation of the approximation errors.
21

---

Published as a conference paper at ICLR 2024
4.1
Willeroit
02
15
035
05
605
Figure 7: Approximation errors of the optimal Q-functions, reward functions, and transition functions in MuJoCo environments, using 2-(hidden) layer neural networks with width 64. In each environment, we run 5 independent experiments and report the mean and standard deviation of the approximation errors.
Figure 8: Approximation emror of the optimal value functions (learned by actor-critic), reward functions, and transition functions in MuJoCo environments, using 3-(hidden) layer neural networks with width 64. In each environment, we run 5 independent experiments and report the mean and standard deviation of the approximation errors.
22

---

Published as a conference paper at ICLR 2024
deeaa
Figure Approximation errors of the optimal Q-functions, reward functions, and transition functions in MuJoCo environments, using 2-(hidden) layer neural networks with width 128, For each state, we take Monte-Carlo sampling and use the average discounted sum of rewards as the Q-value estimate. The approximation errors are shown in the log scale. In each environment, we run 5 independent experiments and report the mean and standard deviation of the approximation errors.
Stochastic MDP. Although we study the deterministic transition in this paper, it can also be extended to stochastic MDPs. In that case, P(s, a, s') represents the probability of reaching state s' when choosing action on state Since the probability is represented with bounded precision in machine (e.g.. 64-bit floating point), the output of P(s, a, 8') can also be represented by a {0, 13- string.
Now we discuss a natural extension from the deterministic transition kernel to the stochastic transition kernel of our majority MDP. After applying 1, if C(s(r)) (i.c., the condition is satisfied), instead of deterministically flipping the s|c|-th bit of representation bits, in the stochastic version, the sfci-th bit will be flipped with probability 1/2, and nothing happens otherwise. This resembles the real-world scenario where an action might fail with some failure probability. The representation complexity of the transition kernel P remains polynomial. For the optimal Q function, if we change
H = 26_ + 2n, since in expectation, each (effective) flipping will cost two steps, the representation complexity of the Q-function is still lower bounded by the majority function, which is exponentially large. Note that our deterministic majority MDP can be viewed as an embedded chain of a more 'lazy' MDP, and the failure probability can also be arbitrary. Hence, our result (Theorems 3.7 and 3.8 can be generalized to this natural class of stochastic MDPs.
POMDP. For POMDP, we can additionally assume a function ((s) = o (or 0 o), which
maps state (or state-action pair (s, a)) to a corresponding observation One possible choice of (ss) could be a substring of the state 8, which still has low representation complexity. In POMDPs, the Q-function is often defined sequence of past observations certain belief states that reflect the posterior distribution of the hidden state. As a result, the Q-functions in POMDPs often have higher complexity. Since the Q-function proven to possess high eircuit complexity for the majority MDP, the representation complexity for value-based quantities of a partially observable version could be even higher.
23


Reviews:
[{"review_id": "7r5ElJTzfK", "reviewer": "Reviewer_9wTj", "summary": "This paper studies the representation complexity of model-based and model-free reinforcement learning. It proposes to use circuit complexity and proves that for a large class of MDPs, the representation complexity of models is larger than that of Q-values. Furthermore, the paper conducts several experiments showing that the approximation error of the Q-value function class are typically larger than that of the model class, indicating learning Q-value functions is harder than learning models, which coincides with the intuition.", "questions": "1. While the circuit complexity is a good starting point to study the representation complexity, is it possible that there are other quantities or metrics such that the representation complexity might behave differently?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a new perspective of representation complexity in learning MDPs, and the introduction of circuit complexity into this domain seems novel.\n2. Both theoretical and experimental results are solid and sound.", "weaknesses": "1. While the majority MDPs is broad, it fails to see if common MDPs are in this class or close to this class such that in many real life applications the circuit complexity of the Q-value function class is higher than that of the model class.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "L8RrK5qbEX", "reviewer": "Reviewer_zTQ7", "summary": "This work studies the representation complexity of model-based and model-free reinforcement learning (RL). Different from the prior work (Dong et al., 2020b), this paper considers a less restrictive family of MDP and incorporates circuit complexity for more fundamental and rigorous theoretical results. This work introduces the definitions of Parity MDP and Majority MDP and proves that the reward function and the transition function have lower circuit complexity than value functions. Experiments are conducted in MuJoCo continuous control tasks with SAC algorithm, quantitively corroborating the theoretical results.", "questions": "1) What are the approximation errors of the optimal $Q$-function calculated exactly in the experiments? Fitting the $Q$ values given by the learned SAC critics or fitting the monte carlo returns of the learned policy (i.e., the actor)?\n\n2) How will the experimental results change when varying the size of neural network used? I think only one configuration (i.e., $d=2, \\omega = 32$) is insufficient.\n\n3) How can the circuit representation complexity be in visual-input MDPs (or POMDP) and stochastic-transition MDPs?\n\n\n==========Post-Rebuttal Comments============\n\nThe authors' responses have addressed my questions above. I raised the rating score accordingly.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and organized. The presentation is smooth and clear.\n- To my knowledge, the representation complexity study for the MDP family considered in this paper is novel and significant.\n- Both theoretical analysis and empirical investigation are provided.", "weaknesses": "- Although the authors mentioned that the considered MDP family is general, it is not clear how the circuit representation complexity in visual-input MDPs (or POMDP) and stochastic-transition MDPs can be. I think at least some discussions and remarks on these points will be useful.\n- The experiments are not convincing to me. Some important details are missing, e.g., the exact computation of the approximation error of the optimal Q-function. Moreover, I think the variation in terms of the network scale (i.e., $d$ and $\\omega$) and environments (e.g., Atari) is insufficient.\n\n&nbsp;\n\nI would be willing to raise my rating if my concerns are addressed. Please see the concrete questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "7rnFT8FesY", "reviewer": "Reviewer_kBCH", "summary": "This paper studies the representation complexity of model-based and model-free reinforcement learning (RL) algorithms in the context of circuit complexity. The authors introduce a special class of majority MDPs and theoretically demonstrate that while the transition and reward functions of these MDPs have low representation complexity, the optimal Q-function exhibits exponential representation complexity. The paper then extends these findings empirically by examining MuJoCo Gym environments and measuring the relative approximation errors of neural networks in fitting these functions. The results demonstrate that the optimal Q-functions are significantly harder to approximate than the transition and reward functions which supports their theoretical findings.", "questions": "How might these insights inspire the design and development of improvements to RL algorithms?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Novelty: this is the first work to study the representation complexity of RL under a circuit complexity framework. The authors introduced a general class Majority MDPs, such that their transition kernels and reward functions have much lower circuit complexity than their optimal Q-functions. And the authors provides unique insights into why model-based algorithms usually enjoy better sample complexity than model-free algorithms from a novel representation complexity perspective.\n- The theoretical results are supported by empirical demonstrations.", "weaknesses": "- The theoretical nature of the Majority MDP might limit its direct applicability to practical problems. \n- A minor point that the experiment section only includes a limited set of small scale gym environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)