Bootstrapping the Expressivity with Model-based Planning
Authors: Kefan Dong
Yuping Luo
Tengyu Ma
Venue:  (2020)
Keywords: reinforcement learning theory
model-based reinforcement learning
planning
expressivity
approximation theory
deep reinforcement learning theory

Abstract: We compare the model-free reinforcement learning with the model-based approaches through the lens of the expressive power of neural networks for policies, $Q$-functions, and dynamics.  We show, theoretically and empirically, that even for one-dimensional continuous state space, there are many MDPs whose optimal $Q$-functions and policies are much more complex than the dynamics. We hypothesize many real-world MDPs also have a similar property. For these MDPs, model-based planning is a favorable algorithm, because the resulting policies can approximate the optimal policy significantly better than a neural network parameterization can, and model-free or model-based policy optimization rely on policy parameterization. Motivated by the theory, we apply a simple multi-step model-based bootstrapping planner (BOOTS) to bootstrap a weak $Q$-function into a stronger policy. Empirical results show that applying BOOTS on top of model-based or model-free policy optimization algorithms at the test time improves the performance on MuJoCo benchmark tasks. 

Under review as a conference paper at ICLR 2020
BOOTSTRAPPING THE EXPRESSIVITY WITH MODEL- BASED PLANNING
Anonymous authors Paper under double-bling review
ABSTRACT
We compare the model-free reinforcement learning with the model-based ap- proaches through the lens of the expressive power of neural networks for poli- cies, Q-functions, and dynamics. We show, theoretically and empirically, that even for one-dimensional continuous state space, there are many MDPs whose optimal Q-functions and policies are much more complex than the dynamics. We hypothesize many real-world MDPs also have similar property. For these MDPs, mooell-baeed planning is favorable algorithm, because the resulting poli- cies can approximate the optimal policy significantly better than a neural network parameterization can, and model-free or model-based policy optimization rely on policy parameterization. Motivated by the theory, we apply simple multi-ster steti model-based bootstrapping planner (BOOTS) to bootstrap a weak Q Q-function into a stronger policy. Empirical results show that applying BOOTS on top model- based or model-free policy optimization algorithms at the test time improves the performance on MuJoCo benchmark tasks.
INTRODUCTION
Model-based deep reinforcement learning (RL) algorithms offer lot of potentials in achieving sig- nificantly better sample efficiency than the model-free algorithms for continuous control tasks. We can largely categorize the model-based deep RL algorithms into two types: model-based policy optimization algorithms which learn policies or QQ-functions, parameterized by neural networks, on the estimated dynamics, using off shelf model-free algorithms or their variants (Luo al. 2019 Janner et al., 2019;] Kaiser et al.) 2019 Kurutach et al., (2018) Feinberg et al.) 2018 Buckman et al., 2018), and 2. model-based planning algorithms. which plan with the estimated dynamics Nagabandi
et al. 201 8); Chua et al. 2018); Wang & Ba (2019).
deeper theoretical understanding of the pros and cons of model-based and the model-free algo- rithms in the continuous state space will provide guiding principles for designing and applying new sample-efficient methods. The prior work on the comparisons of moodel-based and model-free algorithms mostly focuses their sample efficiency gap, in the of tabular MDPs (Zanette & Brunskill] 2019: Jin et al., (018), linear quadratic regulator (Tu & Recht 2018), and contextual decision process with sparse reward (Sun al., 2019).
In this paper, we theoretically compare model-based RL and model-free RL in the continuous state space through the lens of approximability by neural networks, and then use the insight design practical algorithms. What is the representation power of neural networks for expressing the Q- function, the policy, and the dynamics? How do the model-based and model-free algorithms utilize the expressivity of neural networks?
Our main finding that even for the case of one-dimensional continuous state space, there can be massive gap between the approximability of Q-function and the policy and that of the dynamics:
The optimal Q-function and policy can significantly more complex than the dynamics.
We construct environments where the dynamics are simply piecewise linear functions with constant pieces, but the optimal fufuccions and the optimal policy require an exponential (in the horizon)
indicates equal contribution

---

Under review as a conference paper at ICLR 2020
Dynamics (RAND)
O-function (RANI))
Action Action
state
Qualue
Figure 1: Left: The dynam- ics of two randomly gener- ated MDPs (from the RAND, and SEMI-RAND methods outlined in Section 4.3 and
3.0
curnent
current state
detailed in Appendix D.I). Right: The corresponding Q-functions which are more complex than the dynamics (more details in Section 4.3
Dynamics, (SEMI-RAND)
O-function
0.35
state
Qualue
0.4
2.5
3.0
curment
state
number of linear pieces, or exponentially wide neural networks, to approximate The approximabil- ity gap can also be observed empirically on (semi-) randomly generated piecewise linear dynamics with decent chance. (See Figure [ for two examples.)
When the approximability gap occurs, any deep RL. algorithms with policies parameterized by neural networks will suffer from a sub-optimal performance. These algorithms include both model-free algorithms such as DQN (Mnih et al. 2015) and SAC (Haarnoja et al. 2018). and model-based policy optimization algorithms such as SLBO (Luo et al.) (209)) and MBPO (Janner et al. 2019). To validate the intuition, we empirically apply these algorithms to the constructed or the randomly generated MDPs. Indeed, they fail to converge to the optimal rewards even with sufficient samples, which suggests that they suffer from the lack of expressivity.
However, in such cases, model-based planning algorithms should not suffer from the lack of ex- pressivity, because they only use the leareed, parameterized dynamics, which are easy to express. The policy obtained from the planning is the maximizer of the total future reward on the learned dynamics, and can have an exponential (in the horizon) number of pieces even if the dynamics has only a constant number of pieces. In fact, even a partial planner can help improve the expressivity of the policy. If we plan for l steps and then resort some Q-function for estimating the total reward of the remaining steps, we can obtain a policy with 2 more pieces than what Q-function has.
We hypothesize that the real-world continuous control tasks also have a more complex optimal Q- function and a policy than the dynamics. The theoretical analysis of the synthetic dynamics suggests that model-based few-steps planner on top of parameterized Q-function will outperform the orig- inal Q-function because of the addtional expressivity introduced by the planning. We empirically verify the intuition on MuloCo benchmark tasks. We show that applying a model-based planner on top of Q-functions learned from model-based or model-free policy optimization algorithms in the test time leads to significant gains over the original Q-function or policy.
In summary, our contributions are:
1. We construct continuous state space MDPs whose Q-functions and policies are proved to be more complex than the dynamics (Sections and 4.2)
2. We empirically show that with a decent chance, (semi- Dradomly generated piecewise lin- ear MDPs also have complex Q-functions (Section 4.3
3. We show theoretically and empirically that the model-free RL or model-based policy op- timization algorithms suffer from the lack of expressivity for the constructed MDPs (Sec- tions whereas model-based planning solve the problem efficiently (Section 5.2
4. Inspired by the theory, we propose a simple model- -ased bootstrapping planner (BOOTS), which can be applied on top of any model-free or model- Q-learning algorithms at
In turn, the dynamics can also be much more complex than the Q-function. Consider the following situa- tion: subset of the coordinates of the state space can be arbitrarily difficult to express by neural networks, hut the reward function can only depend on the rest of the coordinates and remain simple.
2

---

Under review as a conference paper at ICLR 2020
the test time. Empirical results show that BOOTS improves the performance MuJoCo benchmark tasks, and outperforms previous state-of-the the-hrt on MuJoCo humanoid environ- ment.
ADDITIONAL RELATED WORK
Comparisons with Prior Theoretical Work. Model-based RL has been extensively studied in the tabular case (see (Zanette & Brunskill 2019; Azar et al. (017)) and the references therein), but much less so the context of deep neural networks approximators and continuous state space. (Luo) et al. 2019) give sample complexity and convergence guarantees suing principle of optimism in the face of uncertainty for non-linear dynamics.
Below we review several prior results regarding model-based versus model-free dichotomy in var- ious settings. We note that our work focuses on the angle of expressivity, whereas the work below focuses the sample efficiency.
Tabular MDPs. The extensive study in tabular MDP setting leaves little gap in their sample com- plexity of model-based and model-free algorithms, whereas the space complexity seems to be the main difference. (Strehl et al. 2006). The best sample complexity bounds for model-based tabular RL (Azar et al. 2017 Zanette & Brunskill 2019) and model-free tabular RL (Jin al. 2018) only differ by a poly(H) multiplicative factor (where is the horizon.)
Linear Quadratic Regulator. Dean et al. (2018) and Dean al. (2017) provided sample complexity bound for model-bases LQR. Recently, Tu & Recht (2018) analyzed sample efficiency of the model- based and model-free problem in the setting of Linear Quadratic Regulator, and proved an ((d) gap in sample complexity, where d is the dimension of state space. Unlike tabular MDP case, the space complexity of model-based and model-free algorithms has little difference. The sample-efficiency gap mostly comes from that dynamics learning has d-dimensional supervisions, whereas Q Q-learning has only mieddimeniional supervision.
Contextual Decision Process (with function approximator). Sun et al. (0019) prove an ex- ponential intommation-hhoreticc... gap between mode-based and model-free algorithms in the fac- tored MDP setting. Their definition of model-free algorithms requires an exact parameterization: the fuuee-fnntionn hypothesis class should be exactly the family of optimal falue-functions in- duced by the MDP family. This limits the application to deep reinforcement learning where over- parameterized neural networks are frequently used. Moreover, a crucial reason for the failure of the model-free algorithms is that the reward is designed to be sparse.
Related Empirical Work. A large family of model-based RL algorithms uses existing model-free algorithms of its variant on the learned dynamics. MBPO (Janner et al. 2019). STEVE (Buckman al. 2018). and MVE (Feinberg et al. 2018) are model-based Q-learning based policy optimization algorithms, which can be viewed modern extensions and improvements of the early model-based based Q-learning framework, Dyna (Sutton 1990). SLBO (Luo et al. 2019) is a model-based policy optimization algorithm using TRPO as the algorithm in the learned environment.
Another way to exploit the dynamics is to use it to perform model-based planning. Racanière et al. (2117) and Du & Narasimhan (2019) use the model to generated additional extra data do plan- ning implicitly. [Chua et al. (2018) study how to combine an ensemble of probabilistic models and planning, which is followed by Wang & Ba (019), which introduces policy network distill knowledge from a planner and provides prior for the planner. Piché et al. (2018) uses methods in Sequential Monte Carlo the context of control as inference. Ohh et al. (2017) trains Q-function and then perform lookahead planning. Nagabandi et al. (2018) uses random shooting the plan- ning algorithm. Lowrey al. (2018) uses the dynamics to improve the performance of model-free algorithms.
Heess et al.] (2015) backprops through a stochastic computation graph with a stochastic gradient to optimize the policy under the learned dynamics. Levine & Koltun (2013) distills policy from trajectory optimization. Rajeswaran et al. (2016) trains a policy adversarially robust to the worst dy- namics in the ensemble. Clavera al, (2018) reformulates the problem meta-learning problem and using meta- letaallarnnig algorithms. Predictron (Silver et al.] (017)) learns a dynamics and value function and then use them predict the future reward sequences.
3

---

Under review as a conference paper at ICLR 2020
Another line of work focus how to improve the learned dynamics model. Many of them ensemble of models (Kurutach et al. 2018 Rajeswaran et al. 2016; Clavera et al. 2018). which
further extended
ensemble of probabilistie models (Chua et al. 2018 Wang & Ba 2019).
Luo et al.] 2019) designs a discrepancy bound for learning the dynamies model. Talvitie (2014)
augments the data for model training in way that the model can output real observation from its own prediction. Malik et al. (2019) calibrates the model's uncertainty so that the model's output distribution should match the frequeney of predicted states. Oh et al. (2017) learns representation of states by predicting rewards and future returns using representation.
PRELIMINARIES
Markov Decision Process. A Markov Decision Process (MDP) is tuple AS J, r,r, 7), where S the state space, A the action space, f S + (SS) the transition dynamics that maps a state action pair to probability distribution of the next state, the discount factor, and E RSxA the reward function. Throughout this paper, we will consider deterministic dynamics, which, with slight abuse of notation, will be denoted by f
A
A deterministic policy π : :S A maps a state to an action. The value function for the policy is defined is defined (s) def Σ T== r ah). where as x(s)), 81 and 8h+1
(s), ap).
An RL agent aims to find policy ı that maximizes the expected total reward defined as
(T)) det Bara (81)),),,
where y is the distribution of the initial state.
Bellman Equation. Let n- be the optimal policy, and V the optimal value function (that is, the value function for policy x*). The value function V for policy and optimal value function V*
satisfy the Bellman equation and Bellman optimality equation, respectively. Let Q" and Q' defines the state-action value function for policy and optimal state-action value function. Then, for deterministic dynamics f, we have
{ VT = (s, (s)). (= = r(s, (f and {
V*(s) max (8,
(I)
(" = r(s,a) + -VV*(((s
Denote the Bellman operator for dynamics f by By: (8)())(s,a) = r(s,a) + max, ())
Neural Networks. We focus on fully-connected neural nets with ReLU function as activations. A one-dimensional input and one-dimensional output ReLU neural net represents piecewise linear function. A two-layer ReLU neural net with hidden neurons represents a piecewise linear function with most (d 1) pieces. Similarly, an H-layer neural net with d hidden neurons in each layer represents a piecewise linear function with at most (d + 1) pieces (Pascanu et al. 2013).
Problem Setting and Notations. In this paper, focus continuous state space, discrete action space MDPs with S C IR. We assume the dynamics is deterministic (that is, 8:+1 f(st, az)), and the reward is known the agent. Let [x] denote the floor function of x, that is, the greatest integer less than or equal to x. We use [I[-] to denote the indicator function.
4 APPROXIMABILITY OF Q-FUNCTIONS AND DYNAMICS
We show that there exist MDPs in one-dimensional continuous state space that have simple dynam- ics but complex Q-functions and policies. Moreover, any polynomial-size neural network function approximator of the Q-function policy will result in a sub-optimal expected total reward, and learning Q Q-functions parameterized by neural networks requires fundamentally an exponential num- ber of samples (Section 4.2) Section 4.3 illlsstrates the phenomena that Q 2-fuuctiin is more complex than the dynamics occurring firequetly and naturally even with random MDP, beyond the theoretical construction.

---

Under review as a conference paper at ICLR 2020
dynamics
function
optimal Q function (s, Qts.31
1.0
Action -
1.00
0.8
Action
0.6
0 function
0.4
0.25
0.2
0.00
Action
Action a
0.0
0.0
0.2
0.4
0.6
0.8
1.0
-0.25
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
current state
ourrent state 5
current state
(a) Visualization of dynamics for
(b) The reward function r(s, 0) and r(s, 1).
(c) Approximation of optimal Q- function (ssssa)
action = 0, 1.
Figure 2: A visualization of the dynamics, the reward function in the MDP defined in Definition 4.1 and the approximation of its optimal Q-function for the effective horizon H 4. We can also construct slightly more involved construction with Lipschitz dynamics and very similar properties. Please see Appendix C
4.1 A PROVABLE CONSTRUCTION OF MDPs WITH COMPLEX Q
Recall that we consider the infinite horizon case and 0 < Y < 1 is the discount factor. Let H (1 (1-7))- be the "effective horizon" the rewards after >> H steps become negligible due the discount factor. For simplicity, we assume that H > 3 and it is an integer. (Otherwise we take just take H [[1 -) Throughout this section, we assume that the state space S [0. 1) and the action space A- = 10.
Definition 4.1. Given the effective horizon H (1 - -001--)-,,
, we define an MDP Mu as follows. Let k 2- The dynamics f by the following piecewise linear functions with at most three pieces.
f(s,0) - {
1 2s -
28
i < 1/2
f(s,1) =
2s + K -
2s
if <1 k))
k)/2
if 2 1/2
25 + K
otherwise.
The reward function is defined as
r(s, 0) = [[11//$<<]] 8
r(s, 1) = 1 5 <] -
The initial state distribution i is uniform distribution over the state space [0. 1).
The dynamics and the reward function for H are visualized in Figures 2a 2b Note that by the definition, the transition function for fixed action is piecewise linear function with at most 3 pieces. Our construction can modified so that the dynamics is Lipschitz and the same conclusion holds (see Appendix CC.
Attentive readers may also realize that the dynamics can be also be written succinetly as [(s 0) 28 mod 1 and [(x, = 28 + K mod F which are key properties that we use in the proof of Theorem below.
Optimal Q-function Q" and the optimal policy n.. Even though the dynamics of the MDP constructed Definition 4.1 has only a constant number of pieces, the Q-function and policy are very complex: (1) the policy is piecewise linear function with exponentially number of pieces, (2) the optimal Q-function Q' and the optimal value function V* are actually fractals that are not continuous anywhere. These are formalized in the theorem below.
Theorem 4.2. For E [0, 1), let s(k) denotes the k-th bit of s in the binary representation The optimal policy x² for the MDP defined in Desinition 4.1 has 2 number of pieces. In particular,
n (s) (H+) 0j.
"The mod function is defined as: mod 2 [x]. More generally, for positive real k we define mod & A x - le b[=/k].
*Or more precisely, define (b)) A [2ta] mod 2.
5

---

Under review as a conference paper at ICLR 2020
And the optimal value function is a fractal with the expression:
V*(6)=
(())
Σ> (1 (1+ - ,(h1)) + =1 -2--1(20(044))) (20(141)22) (3)
OC
h=H+1
The close-form expression of Q' can be computed by (* r(8,a) + ()(ss,)))), which is also a fractal.
We approximate the optimal Q-function by truncating the infinite sum to 2H terms, and visualize it in Figure 2c] We discuss the main intuitions behind the construction in the following proof sketch of the Theorem. A rigorous proof of Theorem (.2 deferred to Appendix
B.I B.1
Proof Sketch. The key observation is that the dynamics f essentially shift the binary representation of the states with some addition. We can verify that the dynamies satisfies [(x 0) = 2s mod 1 and
1s,, = 2s + A. mod 1 where x = 2- H other words, suppose = 02) ... the binary representation of s, and let left-shift(s)) = g
f(s, 0) = left-shift(s)
(4)
f(s, 1) = (left-shift(s) + 2-2") mod 1
(5)
Moreover, the reward function is approximately equal to the first bit of the binary representation
r(s 0) ,0) r(s, a) Rs (1)
(Here the small negative drift of reward for action 1, -2(7"-1--110) ", is only mostly designed for the convenience of the proof, and casual readers can ignore for simplicity.) Ignoring carries, the policy pretty much can only affect the H-th bit of the next state s' [(ss, a): the H-th bit of 8 is either equal to (H + 1) bit of s when action is O, or equal its flip when action is 1. Because the bits will eventually be shifted left and the reward is higher if the first bit of future state is 1, towards getting higher future reward, the policy should aim to create more I's. Therefore, the optimal policy should choose action 0 if the (H + 1)-th bit of is already and otherwise choose to flip the (H + 1)-th bit by taking action 1.
more delicate calculation that addresses the carries properly would lead us the form of the optimal policy (Equation (2)) Computing the total reward by executing the optimal policy will lead us to the form the optimal value function (equation (3).) (This step does require some elementary but sophisticated algebraic manipulation.)
With the form of the V*, a shortcut to formal, rigorous proof would be to verify that it satisfies the Bellman equation, and verify x² is consistent with it. We follow this route in the formal proof of Theorem 4.2 in Appendix B.I
4.2 THE APPROXIMABILITY OF Q-FUNCTION
A priori, the complexity of Q' or x² does not rule out the possibility that there exists an approxi- mation of them that do an equally good job in terms of maximizing the rewards. However, we show that in this section, indeed, there is no neural network approximation of Q* or x² with a polynomial width. We prove this by showing any piecewise linear function with a sub-exponential number of pieces cannot approximate either Q* or πt with near-optimal total reward.
Theorem 4.3. Let Mu be the MDP constructed in Definition 4.1, Suppose a piecewise linear policy π has near optimal reward in the sense that n)(T) Z 0.92 q(T"), then it has have at least Ω (exp(cH)/ H) pieces for some universal constant > O. As a corollary, no constant depth neural networks with polynomial width (in H) can approximate the optimal policy with near optimal rewards.
Consider policy x induced by a value function Q that is, (()) = arg max.E.A Q(s, a). Then, when there are two actions, the number of pieces of the policy is bounded by twice the number of pieces of Q. This observation and the theorem above implics the following inapproximability result of Q". Corollary 4.4. In the setting of Theorem 4.3 let be the policy induced by some Q. If is near- optimal in sense that r7(T) 2 0.92 m)( then Q has at least Q (exp(cH)) H) pieces for some universal constant 0.

---

Under review as a conference paper at ICLR 2020
The intuition behind the proof of Theorem
4 is as follows. Recall that the optimal policy has the form x² (s) = ([x(H+1) = 0j. One can expect that any polynomial-picees policy æ behaves subopti-
mally in most of the states, which leads to the suboptimality of π. Detailed proof of Theorem
deferred to Appendix B.2
Beyond the expressivity lower bound, we also provide an exponential sample complexity lower bound for Q-learning algorithms parameterized with neural networks (see Appendix B.4).
4.3 THE APPROXIMABILITY OF Q-FUNCTIONS OF RANDOMLY GENERATED MDPs
In this section, we show the phenomena that the Q-function not only occurs in the crafted cases as in the previous subsection, but also occurs more robustly with a decent chance for (semi-) randomly generated MDPs. (Mathematically, this says that the family of MDPs with such property is not degenerate measure-zero set.)
It is challenging and perhaps requires deep math to characterize the fractal structure of Q-functions for random dynamics, which is beyond the scope of this paper. Instead, we take an empirical ap- proach here. We generate random piecewise linear and Lipschitz dynamics, and compute their Q- o-functions for the finite horizon, and then visualize the Q-functions or count the number of pieces in the Q f-ffucttoon.. We also use DQN algorithm (Mnih et al. 2013) with finite-size neural network to learn the Q Q-function.
We set horizon H 10 for simplicity and computational feasibility. The state and action space are [o, and {0, 1} respectively. We design two methods to generate random or semi-random piecewise dynamics with most four pieces. First, we have uniformly random method, called RAND, where we independently generate two piecewise linear functions for f(s 0) and f(s, 1). by generating random positions for the kinks, generating random outputs for the kinks, and connecting the kinks by linear lines (See Appendix [. a detailed description.)
In the second method, called SEMI-RAND, we introduce a bit more structure in the generation process, towards increasing the chance to see the phenomenon. The functions f(s 0) and f(s 1) have 3 pieces with shared kinks. We also design the generating process of the outputs the kinks so that the functions have more fluctuations. The reward for both of the two methods is r(s,a) = 8, Va E A. (See Appendix D.I for a detailed description.)
Figure Dillustrates the dynamics of the generated MDPs from SEMI-RAND. More details of empir- ical settings can be found Appendix [.T] The optimal policy and Q can have a large number of pieces. Because the state space has one dimension, and the horizon is 10, we can compute the exact Q-functions by recursively applying Bellman operators, and count the number of pieces. We found that, 8.6% fraction of the 1000 MDPs independently generated from the RAND method has policies with more than 100 pieces, much larger than the number of pieces in the dynamics (which is 4). Using the SEMI-RAND method, a 68. 7% fraction of the MDPs has polices with more than 10x pieces. In Section D.I. we plot the histogram of the number of pieces of the Q-functions. Figure I visualize the Q-functions and dynamics of two MDPs generated from RAND and SEMI-RAND method. These results suggest that the phenomenon that Q-function is more complex than dynamics not a degenerate phenomenon and can occur with non-zero measure. For more empirical results, see Appendix D.2]
Model-based policy optimization methods also suffer from a lack of expressivity. As an impli- cation of our theory in the previous section, when the Q-function or the policy are too complex to be approximated by a reasonable size neural network, both model-free algorithms or model-based policy optimization algorithms will suffer from the lack of expressivity, and as consequence, the sub-optimal rewards. We verify this claim on the randomly generated MDPs discussed in Sec- tion 4.3 by running DQN (Mnih et al. 2015), SLBO (Luo et al. 2019), and MBPO (Janner et al.) 2019) with various architecture size.
For the ease of exposition, we the MDP visualized in the bottom half of Figure T The optimal policy for this specific MDP has 765 pieces, and the optimal Q-function has about x 10 number of pieces, and we can compute the optimal total rewards.
First, we apply DQN to this environment by using a two-layer neural network with various widths to parameterize the Q-function. The training curve is shown in Figure (Lef).. Model-free algorithms
7

---

Under review as a conference paper at ICLR 2020
Policy Optimization Algorithms
Model-based Bootstrap Planner (BOOTS)
7.0
0.3
optimal
6.5
6.0
DON-128
DON-32
6.0-
optimal
5.5
DON-16384
SL3D-512
MBP3-512
50K
100K 150K 200K 250C trajectories
300K
4.5
0
2X
4KC
6K
8K
10K
orajectortes
Figure 3: (Left): The performance of DQN, SLBO, and MBPO the bottom dynamics in Figure 1 The number after the acronym is the width the neural network used in the parameterization of Q We that even with sufficiently large neural networks and sufficiently many steps, these algorithms still suffers from bad approximability and cannot achieve optimal reward. (Right): Performance of BOOTS DQN with various planning steps. near-optimal reward is achieved with even k 3, indicating that the bootstrapping with the learned dynamics improves the expressivity of the policy significantly.
Algorithm Model-based Bootstrapping Planner (BOOTS) RL Algorithm X
1: training: run Algorithm X. store the all samples in the set R, store the learned Q-function Q and the learned dynamics if it is available in Algorithm X.
2: testing:
3: if ff is not available, learn f from the data R
4: execute the policy BOOTS(s) at every state
5:
1: function BOOTS(s)
2: Given: query oracle for function Q and f
3: Compute
boots π ".Q. (8) (5) arg max max r(s, a) +... + - + Q ax) el....a
using zero-th order optimization algorithm (which only requires oracle query of the function value) such as cross-entropy method or random shooting.
can not find near-optimal policy even with 24 hidden neurons and 1M trajectories, which suggests that there a fundamental approximation issue. This result consistent with Fu et al. (2019). in sense that enlarging Q-network improves the performance of DQN algorithm at convergence.
Second, we apply SLBO and MBPO in the same environment. Because the policy network and Q-function in SLOBO and MBPO cannot approximate the optimal policy and value function, we see that they fail to achieve near-optimal rewards, as shown in Figure (Left).
5 MODEL-BASED BOOTSTRAPPING PLANNER
Our theory and experiments in Section and demonstrate that when the Q-function or the policy is complex, model-free or model masel policy optimization algorithms will suffer from the lack of expressivity. The intuition suggests that model- planning algorithms will not suffer from the lack of expressivity because the final policy is not represented by neural network. For the construction Section 4.1 we can actually prove that even few-steps planner can bootstrap the expressivity of the Q-function (formalized in Theorem 5. below).
Inspired the theoretical result, we apply simple k-step model- bootstrapping planner on top of existing Q-functions (trained from either model-based or model-free approach) in the test time, on either the one-dimensional MDPs considered in Section 4 or the continuous control benchmark tasks in MuJoCo. The bootstrapping planner is reminiscent of MCTS using in AlphaGo (Silver jet al. 2016 2018). However, here, we use the learned dynamics and deal with the continuous state space.
8

---

Under review as a conference paper at ICLR 2020
Humanold-v2
4.000
BOOTS MBSAC
MBSMC
3000
4000
2000
2000
1.00
10000
100K
200
300K
420K
100K
230K
300K
400K
steds
xtaps
Figure 4: Comparison of PROOTS-MBAGE MBSAC and BOOTS-SAC SAC Ant and Hu- manoid. Particularly on the Humanoid environment, BOOTS improves the performance signifi- cantly. The test policies for MBSAC and SAC are the deterministic policy that takes the mean of the output of the policy network, because the deterministic policy performs better than the stochastic policy in the test time.
5.1 BOOTSTRAPPING THE Q-FUNCTION
Given function Q that is potentially not expressive enough approximate the optimal Q-function, can apply the Bellman operator with learned dynamies for times to get a bootstrapped version of Q:
ByQQ1 (..1)-B(...1B1000000
or (x, = max r(50, 0n) ....... k-1 - ak-1) + * as) a1,-, _0t
(8)
where su = S, Gg = and $1+1 = f(sn, an).
Given the bootstrapped version, can derive greedy policy w.r.t
π *kQ.. (8) max ()0
boots
(9)
Algorithm D called BOOTS summarizes how to apply the planner on top of any RL algorithm with Q-function (straightforwardly),
For the MDPs constructed in Section we can prove that representing the optimal Q Q-function by [4] requires fewer pieces in Q than representing the optimal Q-function by Q directly.
Theorem 5.1. Consider the MDP MH defined in Definition 4.1 There exists a constant- -iecce piece-
wise linear dynamics f and a 2- 2 -piece piecewise linear function Q, such that the bootstrapped policy n hoots
(s) achieves the optimal total rewards.
k.Q.f
By contrast, recall that in Theorem 4.3 we show that approximating the optimal Q-function directly with a piecewise linear function requires 2 piecewise. Thus have multiplicative factor of 2 gain in the expressivity by using the bootstrapped policy. Here the exponential gain is only magnificent enough when k is close H because the gap of approximability is huge. However, in more realistic settings the randomly-generated generated MDPs and the MuJoCo environment - the bootstrapping planner improvs the performance significantly shown in the next subsection.
5.2 EXPERIMENTS
BOOTS on random piecewise linear MDPs. We implement BOOTS (Algorithm T with various steps planning and with the learned dynamics The planner an exponential-ting planner which enumerates all the possible future sequence of actions. We also implement bootstrapping with partial planner with varying planning horizon. As shown in Figure 3 BOOTS + DQN not only has the best sample-effiiiency, but also achieves the optimal reward. In the meantime, even partial planner helps to improve both the sample-efficiency and performance. More details this experiment are deferred to Appendix D.3
*Our code is available at http:////ggihbb...o//ooo////////

---

Under review as a conference paper at ICLR 2020
Humanoid-v2
Figure 5: BOOTS-MBSAC or BOOTS- MBPO outperforms previous state-of-the-art algorithms on Humanoid. The results are av- eraged over 5 random sceds and shadow area indicates single standard deviation from the mean.
5000
4000
BOOTS MESAC
2000
SAC
1000
MEPO
BOOTS MBPO
50K
100K
150K
200K
250K
300K
350K 40CK
steps
BOOTS on MuJoCo environments. We work with the OpenAl Gym environments (Brockman
et al. 2016) based on the Mujoco simulator (Toorov et (0122) with maximum horizon 1000 and discount factor 1. We apply BOOTS on top of three algorithms: (a) SAC (Haarnoja et al. 2018),
the state-of-the-art model-free RL algorithm: (b) MBPO (Janer et al.) 2019), model- Q- learning algorithm, and an extension of Dyna (Sutton 1990); (c) a computationally efficient variant of MBPO that we develop using ideas from SLBO (Lo et al. 2019). which is called MBSAC. The main difference here from MBPO and other works such as (Wang Ba 2019; Kurutach et al. 2018) is that we don't 't use model ensemble. Instead, we occasionally optimize the dynamics by one step of Adam to introduce stochasticity in the dynamics, following the technique in SLBO Luo et al. (2019). Our algorithm is few times faster than MBPO in wall-clock time. It performs similarly to MBPO on Humanoid, but generally worse than MBPO on other environments. See Appendix A. for details.
We use l = steps of planning unless explicitly mentioned otherwise in the ablation study (Sec- tion A.2). In Figure we compare BOOTS+SAC with SAC, and BOOTS + MBSAC with MBSAC on Gym Ant and Humanoid environments, and demonstrate that BOOTS can be used on top of ex- isting strong baselines. We found that BOOTS has little help for other simpler environments, and we suspect that those environments have much less complex Q-functions so that our theory and intuitions do not necessarily apply. (See Section A.2 for more ablation study.)
In Figure 5
we compare BOOTS+MBSAC and BOOTS+MBPO with other MBPO, SAC, and STEVE (Buckman et al., 2018 on the humanoid environment. We see strong performance sur- passing the previous state-of of-t--of-the-at ahe MBPO.
6 CONCLUSION
Our study suggests that there exists a significant representation power gap of neural networks be- tween for expressing Q-function, the policy, and the dynamics both constructed examples and em- pirical benchmarking environments. We show that our model-basee bootstrapping planner BOOTS helps to overcome the approximation issue and improves the performance in synthetic settings and in the difficult MuJoCo environments. We raise some interesting open questions.
Can we theoretically generalize our results to high-dimensiones state space, or continuous actions space? Can we theoretically analyze the number of pieces of the optimal Q-function of a stochastic dynamics?
In this paper, we measure the complexity by the size of the neural networks. It's conceivable that for real-life problems, the complexity of neural network can be better measured by its weights norm. Could we build a more realistic theory with another measure of complexity?
The BOOTS planner comes with a cost of longer test time, How do we efficiently plan in high-dimensional dynamics with long planning horizon?
The dynamics can also be more complex (perhaps in another sense) than the Q-function in certain cases. How do we efficiently identify the complexity of the optimal Q-function, policy, and the dynamics, and how do we deploy the best algorithms for problems with different characteristics?
For STEVE, the official code at master/research/tte.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Mohammad Gheshlaghi Azar, lan Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 263-272. JMLR. org, 2017.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. In Advances in Neural 2018.
Information Processing Systems, pp.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learn- ing in handful of trials using probabilistic dynamics models. In Advances Neural Information Processing Systems, pp. 4754-4765, 2018.
Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Pieter Abbeel. Model-based reinforcement learning via meta-policy optimization. In Conference Robot Learning. pp. 617-629, 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. CoRR, abs/1710.01688, 2017. URL http:
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: Annual Conference on Neural Information P Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada., pp. 4192-4201, 2018.
Yilun Du and Karthik Narasimhan. Task-agnostic dynamics priors for deep reinforcement learning. arXiv preprint
2019.
V Feinberg, A Wan, I Stoica, MI Jordan, JE Gonzalez, and S Levine Model-based value expan- sion for efficient model-free reinforcement learning. In Proceedings of the 35th International Conference Machine Learning (ICML 2018), 2018.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine Diagnosing bottlenecks in deep q- learning algorithms. In International Conference Machine Learning, pp. 2021-2030, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, pp. 1856-1865, 2018.
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learn- ing continuous control policies by stochastic value gradients. In Advances in Neural Information Processing Systems, pp. 2944 2952, 2015.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- based policy optimization. ArXiv,
2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? In Advances Neural Information Processing Systems, pp. 4863-4873, 2018
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model-based reinforcement learning for atari. ArXiv, abs/ /ttx/193300374, 2019.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 267-274. Morgan Kaufmann Publishers Inc., 2002.

---

Under review as a conference paper at ICLR 2020
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint arXiv:1802.10592 2018.
Sergey Levine and Vladlen Koltun. Guided policy search. In International Conference on Machine Learning. pp. 1-9, 2013.
Kendall Lowrey Aravind Rajeswaran, Sham M. Kakade, Emanuel Todorov, and Igor Mordatch. Plan online, learn offline: Efficient learning and exploration via model-based control. ArXiv, abs/1811.01844 2018
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for model-basee deep reinforcement learning with theoretical guarantees. In 7th In- ternational Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Ali Malik, Volodymyr Kuleshov, Jiaming Song, Danny Nemer, Harlan Seymour, and Stefano Er- mon. Calibrated model-bases deep reinforcement learning. arXiv preprint arXiv:1906.000 0831,, 2019.
Volodymyr Mnih, Koray Kavukcuoglu. David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning.
Nature, 518:529-533, 2015.
Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dynamics for model-basee deep reinforcement learning with model-free fine-tuning. In 2018 IEEE Interna- tional Conference on Robotics and Automation (ICRA), pp. 7559-7566. IEEE, 2018.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In Advances in Neural Information Processing Systems, pp. 6118-6128 2017.
Razvan Pascanu, Guido F Montufar, and Yoshua Bengio. On the number of inference regions of deep feed forward networks with piece-wise linear activations. 2013.
Alexandre Piché, Valentin Thomas, Cyril Ibrahim, Yoshua Bengio, and Chris Pal. Probabilistic planning with sequential monte carlo methods. 2018.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adria Puigdomenech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, agents for deep reinforcement learning. In Advances in neural
et al. information processing systems, pp. 5690-5701, 2017.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. Epopt: Learning robust neural network policies using model ensembles. arXiv preprint 1rXiv:1610.01283 2016.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization, In International conference on machine learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, loannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489999494448 2016.
David Silver, Hado van Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac-Amold, David Reichert, Neil Rabinowitz, Andre Barreto, et al. The predictron: End-to- end learning and planning. In Proceedings of the 34th International Conference on Machine Learming- Volume 70, pp. 3191-3199. JMLR. org, 2017.
12

---

Under review as a conference paper at ICLR 2020
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel. Timothy Lillicrap, Karen Si- monyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 140-1144, 2018. ISSN 0036-8075. doi: 10.1 2..126//ciennee.ar6440..
Alexander Strehl, Lihong Li, Eric Wiewiora, John Langford. and Michael L Littman. Pac model- free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pp. 881-888. ACM, 2006.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements model-free approaches. Conference on Learning Theory, pp. 2898-2933 2019.
Richard S. Sutton. Dyna, an integrated architecture for learning, planning, and reacting. SIGART Bulletin, 2: 2:160-163, 1990.
Erik Talvitie. Model regularization for stable sample rollouts. In UAI, pp. 780-789, 2014.
Emanuel Todorov, Tom Frez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In 2012 IEEE/RSJ International Conference Intelligent Robots and Systems, pp. 5026-5023 IEEE, 2012.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. arXiv preprint arXiv: 18X2.33///. 2018.
Tingwu Wang and Jimmy Ba. Exploring model-based planning with policy networks. arXiv preprint arXiv:/906.0 08649, 2019.
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, pp. 7304-7343 7312, 2019.
Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. arXiv preprint arXiv:1901.09321, 2019.
13

---

Under review as a conference paper at ICLR 2020
A EXPERIMENT DETAILS IN SECTION 5.2
A.1 MODEL-BASED SAC (MBSAC)
Here we describe our MBSAC algorithm in Algorithm 2 which a model-based policy optimization and is used in BOOTS-MBSAC As mentioned in Section 5.2 the main difference from MBPO and other works such as Wang & Ba 2019 Kurutach et al. 2018 is that we don't 't use model ensemble. Instead, we occasionally optimize the dynamics by one step of Adam to introduce stochasticity in the dynamics, following the technique in SLBO (Luo et al., 2019). As argued in (Luo et al., 2019). the stochasticity in the dynamics can play a similar role as the model ensemble. Our algorithm is a few times faster than MBPO wall-clock time. performs similarity to MBPO on Humanoid, but a bit worse than MBPO in other environments. In MBSAC, T and the Q Q-function a. We choose SAC due to its samplc-efiiiencyy simplicity and offlpolliy nature. We mix the real data from the environment and the virtual data which are always fresh and generated by our learned dynamics model fo
SAC to optimize the policy
Algorithm 2 MBSAC
1: Parameterize the policy тg, dynamics fe. and the Q-function Qp by neural networks. Initialize replay buffer B with Rait steps of interactions with the environments by random policy, and pretrain the dynamics on the data in the replay buffer.
2: 0, and sample so from the initial state distribution.
3: for Aiter iterations do
4: Perform action a₂ ~ (=(ss))) in the environment, obtain s' the next state from the envi- ronment.
5: St-1 t s and add the transition (st, ae, St+1, rτ) to
6: t + If = T or the trajectory is done, reset to t = 0 and sample from the initial
state distribution.
7:
for Rpolicy iterations do
8: for moodel iterations do
9:
Optimize fe with a mini- of data from by one step of Adam.
10:
Sample Tireal data Breat and Patart data Bann from B.
11:
Perform q steps of virtual rollouts using fe and policy starting from states in Bstari
obtain Brintal-
12:
Update T and Qu using the mini-batch of data in Byeat U Biinual by SAC.
For Ant, we modify the environment by adding the x and y axis to the observation space to make it possible to compute the reward from observations and actions. For Humanoid, we add the position of center of mass. We don't 't have any other modifications. All environments have maximum horizon 1000.
For the policy network, we use an MLP with ReLU activation function and two hidden layers, each of which contains 256 hidden units. For the dynamics model, we use a network with 2 Fixup blocks (Zhang et al.) 2019), with convolution layers replaced by a fully connected layer. We found out that with similar number of parameters, fixup blocks leads to more accurate model in terms of validation loss. Each fixup block has 500 hidden units. We follow the model training algorithm in Luo et al. 2019) in which non non-squared & loss is used instead of the standard MSE loss.
A.2 ABLATION STUDY
Planning with oracle dynamics and more environments. We found that BOOTS has smaller improvements on top of MBSAC and SAC for the environment Cheetah and Walker. To diagnose the issue, we also plan with an oracle dynamics (the true dynamics). This tells us whether the lack of improvement comes from inaccurate learned dynamics. The results are presented in two ways in Figure and Figure 7 In Figure 6 we plot the mean rewards and the standard deviation of various methods across the randomness of multiple seeds. However, the randomness from the seeds
In the paper of MBPO Janner et al. 2019), the authors don't explicitly state their usage of real data in SAC; the released code seems make such use of real data, though.
14

---

Under review as a conference paper at ICLR 2020
3003
4003
54-
Scota MC EPEEA
BCota MC Syanns
hellChoush
Hurranedd
5003
1000
3000
LCOTS MiSi insce
3900
2003
LOOTS
Figure 6: BOOTS with oracle dynamics on top of SAC (top) and MBSAC (bottom) on HalfCheetah, Walker, Ant and Humanoid. The solid lines are average 5 runs, and the shadow areas indicate the standard deviation.
2743
2009
20x4
12kc
A-B
Hur aneal
4003
1000
2000
200
2014
4564
1006
200C
120c
Figure 7: The relative gains of BOOTS over SAC (top) and MBSAC (bottom) on HalfCheetah, Walker, Ant and Humanoid. The solid lines are average over 5 runs, and the shadow areas indicate the standard deviation.
somewhat obscures the gains of BOOTS each individual run. Therefore, for completeness, also plot the relative gain of BOOTS on top of MBSAC and SAC, and the standard deviation of the gains in Figure
From Figure 7 we can see planning with the oracle dynamics improves the performance in most of the cases (but with various amount of improvements). However, the learned dynamics sometimes not always can give an improvement similar to the oracle dynamics. This suggests the learned dynamics not perfect, but oftentimes can lead to good planning. This suggests the expressivity of the Q-functions varies depending on the particular environment. How and when to learn and use learned dynamics for planning a very interesting future open question.
Horizon
Hortzon
5000
5000
Noraage Neture
4000
Aoarag Setum
4000
3000
palicy
2000
deel Iel-piiicy
2000
del-pelicy
1000
1000
LOOK
200K
300K
400K
100K
200K:
300K
400K
22pp
200p
Figure 8: Different BOOTS planning horizon & top of SAC (left) and MBSAC (right) Hu- manoid. The solid lines are average over runs, and the shadow areas indicate the standard devia- tion.
15

---

Under review as a conference paper at ICLR 2020
The effect of planning horizon. We experimented with different planning horizons in Figure By planning with longer horizon, we can carn slightly higher total rewards for both MBSAC and SAC. Planning horizon & 16, however, does not work well. We suspect that it's caused by the compounding effect of the errors in the dynamics.
B OMITTED PROOFS IN SECTION
In this section provide the proofs omitted in Section
B.1 PROOF OF THEOREM 4.2
Proof of Theorem 4.2 Since the solution to Bellman optimal equations is unique, we only need to verify that V and n defined in equation ① satisfy the following.
(*()) = r(s, (8) + (=) ((*, (*(s) 2 r(s,a) + + +
(10)
(11)
Recall that g(9) is the i-th bit in the binary representation of 8, that is, g(0) [2*s] mod 2. Let
$ = f(s, x² xs)).. Since nT" (s) [[s(H+1) = O). which ensures the H-bit of the next state is 1, we have
(8(+1),
i H i = H.
8(1)
(12)
1,
For simplicity, define H1 - H) The definition of r(8, a) implies that
n = 1[1/2 S < (s) = 1|s = (()) (1 - (1- E.
By elementary manipulation, Eq.
3 is equivalent to
20
(p-11-((7" - (1 -
(s)
(13)
Now, we verify Eq. 110 by plugging in the proposed solution (namely, Eq. 13)). As a result,
r(3, (s)) (s)
H 0 - (1 -1- 8 + 7
(1((0) =
+7
Σ
(x-11 - (1 -
)(1) (1-3(0)
1-2--111)
i=1
i=#+1
=0 (1 (1- ((H-11)
1- 1g(() H
( +-1 - (1 (1-)(0) 2(7t - -(-)))
+
1=2
H+2
Σ x i-1 (+)
(x--1 (1 (1- 2( - -
1=1
#+
(s).
which verifies Eq.
10
16

---

Under review as a conference paper at ICLR 2020
In the following we verify Eq. (II). Consider any # (s). Let f(s,a) for shorthand. Note that 5(0) g(i+3) for H. As result,
(*))) - (5)
(
+
Σ
( - (1- 2(7 - -
H++
H1
7 ( (1-
z(1) (1=)(0) 2(17-2 - -177-2-1111 ,
t=1
+=#+1
H-1
(1(
(((tt) - -(())
n ((H) + g - (1 1-
?
For the case where ((H+1) = 0, we have x'' (8) = 1. For a = 0, g(1) = s(++1) for all i 2 1. Consequently,
-V*)) s(1) + + - s(2)
r(s,
where the last inequality holds when 7" > or equivalently, ? > 2/3.
For the case where g(H+1) 1, we have 7* (s) 0. For 1, we have ( and (( 0. Let p = max < H g() 0}, where we define the max of empty set is 0. The dynamics [(s 1) implies that
(((+1)
i 1 pr H, i+1 p,
g(0)
1,
0,
p ri++ssH+1.
Therefore,
H 1-1
(V))) +
+
?
(((H4) (9:1))=(1)) (5(1))))((1) > s(L) - = rr((ss,))
In both cases, we have V* V* > r(s,a) for a + x- (s), which proves Eq.
I1
B.2 PROOF OF THEOREM 4.3
For a fixed parameter H, let =(x) be the number of pieces æ. For a policy n, define the state distribution when acting policy at step h μrp
In order to prove Theorem 4.3 we show that if 1/2 2Hz(2)/2H < 0.3, then 77))) < 0.92))(**).
The proof is based on the advantage decomposition lemma.
Lemma B.1 (Advantage Decomposition Lemma (Schulman al. 2015
Kakade & Langford
).02 Define (s a) = r().a) + VV (f(s,a) (*()) (s
V (8). Given poli-
cies n and it, we have
(TT)= = nT+)=
+
h A E Esnun [A (s,
(14)
#=1
Corollary B.2. For any policy ग,, we have
20
((*T) - (T(T)) Σ
h
Exnny - ((),))))
(15)
h=1
Intuitively speaking, since x* (1+1) 0). the policy with polynomial pieces behaves suboptimally in most of the states. Lemma Bh3 that the single-step suboptimality gap V*(s) Q* (s, (s)) is large for constant portion of the states. On the other hand, Lemma B.4 proves that
17

---

Under review as a conference paper at ICLR 2020
the state distribution μü is near uniform, which means that suboptimal states can not be avoided. Combining with Corollary B.2 the suboptimal gap of policy π is large.
The next lemma shows that, if does not change its action for states from certain interval, the average ad advantage term (*) - Q (s, x (s)) in this interval is large. Proof of this lemma is deferred of Section [B.]]
Lemma B.3. Let lx Ik/2", (k + ))/2"), and K {0 < 2 k mod 13. Then for k E K. if policy does not change its action at interval Eg (that is, (+((s) 8 E & = 1), we have
1
(V* (s,,)((s)) ds 0.183
(16)
[4 SEC.
for H > 500.
Next lemma shows that when the number of pieces in π is not too large, the distribution μ. is close to uniform distribution for step 1 S h I H. Proof of this lemma is deferred of Section [B.3
Lemma B.4. Let z(T) be the number of pieces of policy x. For E [2"]. define interval
la [k/2H (k + )) Let (k)
infset, (8), the initial state distribution μ is uni-
form distribution, then for any h 2 1,
2 2- V (k) 2 1- 2h 2(TT) 2H
Σ
(17)
0<k<2"
Now we present the proof for Theorem
4.3
Proof of Theorem 4.3 For any k E [2*]. consider the interval & = 1k/2" (k + 11/22H) Let KC
{k E [A [ mod 2 = 1}. If π does not change at interval & (that is, [=((s) : 4 1), by
Lemma B.3 we have
[
ds 0.183 2-
(18)
Let pa (k) = inf (s),, then by advantage decomposition lemma (namely, Corollary B.2 we
have
7(TT) (7())
(V" (*"))- dpp(s)
10H
El KEK SELL
d/%((s)
10H
Σ
un (k)(((((s) (=(s ds
h=1
KEK sEL
10H
Σ 0.183 2- vn(k))
kEX
By Lemma B.4 and union bound, we get
-2h 2(m²
Σ vn (k( 2 2
(19)
211
kek
For the sake of contradiction, assume =(x)== o (exp(ce)) H), then for large enough H we have, 20H+=(T)
1/2
2 0.49,
2H
which means that ΣbEK 2-H "/. (k) 2 0.49 for all h < 10H. Consequently, for H > 500, we have
10
(0.183 x 0.49) ^-1 2 0.089 1 - 101 0.088
1((=)) 1 (T))
1 1-y 1-7"
Now, since nTTT)) < 1/(1 7), we have (T)) < 0.92n)(**) Therefore for near-optimal policy I,
=(T)) Ω (exp(cH)//H)
18

---

Under review as a conference paper at ICLR 2020
B.3
PROOFS OF LEMMA B.3 AND LEMMA B.4
In this section, we present the proofs of two lemmas used in Section B.1
Proof of Lemmal B.3 Note that for any k E K, g(H) = 1, V8 E lg- Now fix a parameter E K. Suppose T(s) = 0; for E lk- Then for any such that s(H+1) + o 1, we have
(s) (*, 2 7" E. do 2 0.366-I|( (H+1) (H+1) +1-1] ds 0.366-2 #-1 -018832-
For H > 500, we have 7" -E 0.366. Therefore,
SEE
seC
Proof of Lemmal B.4 Now let us fix parameter H and policy For every h, we prove by induction that there exists a function (s), such that
(a) 0 & (8) & min (14, 1):
(b) infsee (s) sup,et, (s), Vk E [A*],
(c) Saeta1) (s) 2 h =( /H
For the base case 1, we define (s( = 1. (s) for E (0, 1). Now we construct Ek+1 from En-
For fixed E [2"], define l k 2- Fx + 1) 2- as the left and right endpoints of (6)12 interval lx. Let {ar Timi be the set of 2 solutions of equation
2x + 2- = 4 mod 1
= x + 2- mod 1. By definition, only states from the set 1 yk (1) can reach states in interval & by a single transition. We define set Is = {i 1 < i < 2. (s()) Consequently, for Ix. the set {s E [ (1) fs, (())) E bx is an interval of length 2 H and has the form
where 0 < x < 1, and we define y
(0)
(1)
[a]] (. )())) 1). That is, the intervals where policy acts unanimously.
L + ww
H-1 ( + (w) + + +1)-2-
for some integer w (
{0, 1}. By statement (b) of induction hypothesis,
inf (x()) = sup (x(s)
(20)
sEu
< (
Now, the density (s) for E ly is defined as,
Σ1 2 (x( + 10. NELt
(s))(s)
The intuition of the construction that, we discard those density that cause non-uniform behavior (that is, the density in intervals [ar(() (())) where & Iz). When the number of pieces of is small, we can keep most the density. Now, statement (b) is naturally satisfied by definition of & We
verify statement (a) and (c) below.
19

---

Under review as a conference paper at ICLR 2020
For any set B C lk, let (B)) {s 8 f(s, B} be the inverse of Markov transition T Then we have,
(7 (B) - Eb (T*)- (E(1,2)
Σ En ((TT)) (B) 1 )
Σ 5h
(TT) ( (B) [ 1 )0))
iET
Σ iET
(T") (B)
Latk Uk (1)) En (
(1)
+ wi 2-
(By Eq. 20
|
(1) w/ 2 2-
Eh
Tkk
2
iEI
where is the shorthand for standard Lehesgue measure.
By definition, we have
B
(A+I(B) = Σ
Eh
+ (()
22 2-1 s (B) & (TTA)( = (B),
2
SElt
which verifies statement a
For statement (c) recall that [0, 1) the state space. Note that 7 preserve the overall density. That is (T (S) &n (S). We only need to prove that
(T*) (S) Ex+1(S) s h 2H1
(21)
and statement (c) follows by induction.
By definition of (s) and the induction hypothesis that (s))s) S 1, have
(T (x) (6+) Ex+1 (fx) S (2 [x1)22
On the other hand, for any E S, the set (k [2#] 0 [= (())) has cardinality 2, which means that one intermittent point of ı can correspond to at most intervals that are not in Ig for some k. Thus, have
Σ 0SR<24
1 2
Σ
[ SE 12 1/ 2 2 - 2- 2(T).
(f) (a)
Consequently
(8) (8+
Σ ((T (4x) Ex+1(e)) (000))((mm)))) (x())2-H1)
O5k<2#
which proves statement
B.4 SAMPLE COMPLEXITY LOWER BOUND OF Q-LEARNING
Recall that corollary 4.4 says that in order find near-optimal policy by Q-learning algorithm, an exponentially large Q-network is required. In this subsection, we show that even if an exponentially large Q-network is applied for Q learning, still we need collect an exponentially large number of samples, ruling out the possibility of efficiently solving the constructed MDPs with Q-learning algorithms.
Towards proving the sample complexity lower bound, we consider stronger family of Q-learning algorithm, Q-learning with Oracle (Algorithm 3. We assume that the algorithm has access to Q-ORACLE, which returns the optimal Q-function upon querying any pair (s, a) during the training process. Q-learning with Oracle is conceptually a stronger computation model than the vanilla Q-learning algorithm, because it can directly fit the Q functions with supervised learning, without relying on the rollouts or the previous Q function to estimate the target Q value. Theorem[B.5 sample complexity lower bound for Q-learing algorithm the constructed example.
20

---

Under review as a conference paper at ICLR 2020
Algorithm 3 Q-LEARNING WITH ORACLE
Require: A hypothesis space Q of Q- Q-function parameterization.
1: Sample 80 ~ μ from the initial state distribution 1
2: for 1,2,..... do
3: Decide whether to restart the trajectory by setting 8; ~ fa based on historical information
4: Query Q-ORACLE to get the function Q* (s..)..
5: Apply any action a, (according to any rule) and sample 84+1 f(s.,
6: Learn the Q-function that fit all the data the best:
n
Q - arg min QEQ T
Σ (Q(s;, Q*(s, AR(Q)
7: Return the greedy policy according to Q.
Theorem B.5 (Informal Version of Theorem B.7]. Suppose Q is an infinitel-wwide two-layer neural networks, and R(Q) ( norm of the parameters and serves as a tiebreaker. Then, any instantiation of the Q-LEARNING WITH ORACLE algorithm requires exponentially many samples to find a policy T such that (T)) > (79
Formal proof of Theorem B.5 is given in Appendix B.5 The proof of Theorem B.5 is to exploit the sparsity of the solution found by minimal-norm tie- brebbre It can be proven that there are at most ((n) non-zero neurons in the minimal-norm solution, where n is the number of data points. The proof is completed by combining with Theorem 4.3
B.5 PROOF THEOREM B.5
A two-layer ReLU neural net ((s,) with input is of the following form,
((s Σ wao [kis + bil. + Ca
(22)
where d is the number of hidden neurons. Wi,a; Caz ki, b; are parameters of this neural net, where G,a, by are bias terms. [x]+ is shorthand for ReL.U activation T[x > OJæ. Now we define the norm of neural net.
Definition B.6 (Norm of a Neural Net). The norm of a two-layer ReLU neural net is defined as,
J + [kyl.
(23)
Recall that the Q-learning with oracle algorithm finds the solution by the following supervised learning problem,
n
min QE2 VA
Σ
oz) Q* at)
a.))
(24)
Then, we present the formal version of theorem B.5
Theorem B.7. Let Q be the minimal É norm solution to Eq. (24). and the greedy policy according to Q. When n ((exp(cH)/BB H), we have (]()) < 0.99m(7T*
The proof of Theorem B.5 is by characterizing the minimal-norm solution, namely the sparsity of the minimal-norm solution as stated in the next lemma.
Lemma B.8. The minimal-nomm solution Eq. (24) has at most 32n + 1 non-zero neurons. That
is, [i: K2 & 0}| < 32n + 1.
We first present the proof of Theorem
B.7 followed by the proof of Theorem B.8
Proof of Theorem B.7 Recall that the policy is given by (ss) = arg max.e.4 Q(s, a). For a Q- function with 32n + pieces, the greedy policy according to Q(s,, a) has most 64n + 4 pieces. Combining with Theorem 4.3 in order to find policy π such that (7()) > 0.99m((7*), n needs to be exponentially large (in effective horizon H).
21

---

Under review as a conference paper at ICLR 2020
Proof of Lemma B.8 is based merging neurons. Let 2; -b,/ks w; (Wa,1, 10,2),, and c = (c1,02). In vector form, neural net defined in Eq. (22 can be written as,
((+,))
Σ w, (1 x4)4
First we show that neurons with the same v; can be merged together. Lemma B.9. Consider the following neurons,
k1 [s x1 WI,
ka (s x2]+ W2-
with k 122 xf
T2, then we can replace them with one single neuron of the form k' (r x1]+ w' without changing the oulput of the network. Furthermore, if w # O, W2 # 0, the norm strictly decreases after replacement.
Proof. We set k' = w//1 k2 and w' = (1i W1 + kgw2)/K' where |w/1 represents the 1-norm of vector Then, for all E R,
k' 211 w' (k1w1 k2w2) Is x114 k1 2114 W1 k2 x114 W2. The norm of the new neuron is | + w/ By calculation we have,
W + | = 2 kkww k2 S 2v 1s w1l1 + 122
Vkiih + v [22w2211 - k1 |w/p + [ + w2/1-
Note that the incquality (a) is strictly less when k will * and w22 ل
Next consider merging two neurons with different intercepts between data points. Without loss of generality, assume the data points are listed in ascending order. That is, S 85-1- Lemma B.10. Consider two neurons
k |s - xol+ WT: ko [s z0 5]+ W2.
with by > 0, > sf I zo < xo + S 8;+1 for some S i I n. then the two neurons can replaced by a of three neurons,
k' [s xol4 w', si] w, 11414 (-w)
such that for S or 2 8 the output of the network is unchanged. Furthermore, if ($L+1 - 5:)/ 16 and |w1l # |221 + 0, the norm decreases strictly.
Proof. For simplicity, define A 8i+1 8;- We set
k' / kiiwi + 1:22211
w' (k|Wi + k2222)/k
Î V/kawall0/A w = 2k22200
Note that for S 8;, all of the neurons are inactive. For 2 8:41, all of the neurons are active, and
k'w'( (s - mn) + lew(s si) lew(s Si+1) (ki k2w2) ro) - k2
(1 )o) + k2(s - Do 5) W2
which means that the output of the network is unchanged. Now consider the norm of the two networks. Without loss of generality, assume k/wil1 1 The original network has norm [ka + +|w/l + [ka + [wzl1- And the new network has norm
k [w|] 2| + 2/w //kw + k2 + 4 w2////2/28//
1 (1k2) [Ikal+|wal)))
kal
|
W2/1
(4 122/2/1////
22

---

Under review as a conference paper at ICLR 2020
where the inequality (a) is result of Lemma E.1 and is strictly less when |w1/1 1a * /w2/1 * O.
(1/2 + (wwll)) < O, which implies that When 8/4 < 1/16, we have (4v k2 1
|k' + |w/l + 2/k| + 2/w/ < |4s + |wi + Aca + | /1.
Similarly, two neurons with 1 < 0 and 22 < can be merged together.
Now are ready to prove Lemma B.8 As hinted by previous lemmas, show that between two data points, there are at most 34 non-zeru neurons in the minimal norm solution.
Proof of Lemma B.8 Consider the solution Eq. (4).. Without loss of generality, assume that S 81+1- In the minimal norm solution, it is obvious that |wi]1 = 0 if and only if k; = 0. Therefore we only consider those neurons with k; * O, denoted by index 1 ssisc d'.
Let Br = [-b/// 1 < is d', < bb//k < k; > OJ. Next we prove that in the minimal norm solution, |B,]| S 15. For the sake of contradiction, suppse [B, 15. Then there exists i, such that,
< bb:k; < 81-1, 8t < /by < St+1, lb;/k; b /kyl < ($++1 s;)/16, /6, and k; > 0, ky > 0. By Lemma 1.10 we can obtain neural net with smaller norm by merging neurons
i together without violating Eq. (24). which leads to contradiction.
By Lemma B.9
Byl S 15 implies that there are at most 15 non-zero neurons with 8, < bbi/k <
8++1 and k 0. For the same reason, there are at most 15 non-zero neurons with < - by
8141 and h; < 0.
On the other hand, there are at most 2 non-zero neurons with s; -b./k; for all n, and there are at most non-zero neurons with bb,k: kk < s1. Therefore, we have d' S 32n +
B.6 PROOF OF THEOREM
In this section present the full proof of Theorem 5.1
Proof. First we define the true trajectory estimator
k-1
(s,, ao 01, .x) End(s,aa)+ ak),
j=0
the true optimal action sequence
agj aj.
aj arg max 17(0, ao a1, ... (kk))
ap.a1,-7,
and the true optimal trajectory
s su, = f(8))11
1.
It follows from the definition of optimal policy that, aj TT" (s)). Consequently we have
$k (H-k+1)
8/ (H-k+2)
sk (H) 1.
Define the set {s (++) = -
(H)
1}. We claim that the following
function satisfies the statement of Theorem 5.1
2
((s,a) I[s E G
I-
Since st G, and 8 & G for sa generated by non-optimal action sequence, have
Q( a) ("(st, (* a) Q(sk, a),
where the second inequality comes from the optimality of action sequence ag. As consequence, for any (No, ai, .4a) * (aj, aj ... ,ai) is ag. aj ... at) 17500 og aj .1) 2 n ao o., ..,)))))))))))))){)) n ao, 00,01,""... "..". ,ak). Therefore, (āg. at, at) (a aj,... ... at)
23

---

Under review as a conference paper at ICLR 2020
C EXTENSION OF THE CONSTRUCTED FAMILY
In this section, we present an extension to our construction such that the dynamics is Lipschitz. The action space is {0, 1,2,3, 4]. We define CLIP(()) = max(min(2: 1}.0). Definition C.1. Given effective horizon H (1 7)- , we define an MDP M'1 as follows. Let
2- The dynamics is defined
f(s, 0) CLIP(2s), f(s 1) CLIP(2s 1),
f(8. CIIP(2s + k), (8,33) = C1IP(25 + +K= k- [(8,4) = +
Reward function given by
r(s, = r(s) = - = = =| -( 20-
-
The intuition behind the extension is that, we perform the mod operation manually. The following theorem is an analog to Theorem 4.2
Theorem C.2. The optimal policy xt" for Mn is defined by,
0, [|s(H+1) = 0] and 2s < 1,
1, [[g(H+1) 0] and < 28 < 2,
(s))
x
2, [[((++1) 1] and 2s + 1,
(25)
3, [[((H+1) 1] and 2s + 0 < <2,
4, [|s(H+1) = and 2 < 2s 0.
And the corresponding optimal value function is,
H (1)
(*(s) Shn-1g(1
Σ 2h 1 (1+ -(())) + =-= (70-11(((0))))) (26(H+1) (26)
hm H+1
We can obtain similar upper bound on the performance of policies with polynomial pieces.
Theorem C.3. Let Ми be the MDP constructed Definition C.I Suppose a piecewise linear policy π has near optimal reward in the sense that ()T)) 2 0.99 77(m"(("" then it has to have at least Q (exp(cH)) H) pieces for some universal constant e > 0.
The proof is very similar that for Theorem One of the difference here is to consider the case where f(s, a) = 0 or f(s. fss.
separately. Attentive readers may notice that the dynamics where may destroy the "near uniform" behavior of state distribution μr,, (see Lemma B.4). Here we show that such destroy comes with high cost. Formally speaking, if the clip triggered in an interval, then the averaged single-step suboptimality gap 0.1/(1-7))
f(s, a)
Lemma CA. Let Ea 2/2 (k + 12/2 For k E |2 if policy и does not change its action interval l (that is, ((T(S) SE fx 1) and f(s, (()) =. Vs E lg or f(s, ((s)
1, vs E lg. We have
1
/ (V* -
0.1
ds
(27)
[eN JER
1-7
for large enough H.
Proof. Without loss of generality, we consider the case where f(s 0. The proof for f(s. (s)) = 1 is essentially the same.
By elementary manipulation, we have
" i 1 10
V*(8)-
2
i=1
24

---

Under review as a conference paper at ICLR 2020
Let 8 f(s, TT" (s)). It follows from Bellman equation ① that (*(s) r(s, (s)) + +8)"
(*(s, r(.. ((.. +
Recall that we define = (-
2 -7 As a consequence,
(V* Q" (s, (T,
r(s, (8) r(s, (()) + (V) (*)
11 2 - 7
Plugging into Eq 27 we have
1
(V* - (s,, ds -Et 1
g ds
WENN
Tea
JEP
1/2 71
2
Σ
8(t) ds
-
Ekl
Jec
1-7
Lemma 27 is proved by noticing for large enough H,
112 7
0.1
1 1-
Let D {0, 1] for simplicity. For any policy ग, we define transition operator 7T, such that (T') 1 (fs: p(s,a) E 2, f(s xs)) & D),
and the state distribution induced by it, defined recursively by (s) =
p = -= 1
We also define the density function for states that are truncated as follows,
(s) = I[f (()) D]A (s).
Following advantage decomposition lemma (Corollary B.2).
the key step for proving Theorem C.3
((TT)) (TTT) 2 Es-ag
- (V* ((ss,, +
EEspp (V*(s) (s, ग (s))
h
(28)
Similar to Lemma B.4| the following lemma shows that the density for most of the small intervals is either uniformly clipped, or uniformly spread over this interval.
Lemma C.5. Let 2TT) be the number of pieces of policy æ. For E [2"/2], define interval & [k/2 (I + 1)/2 Let (k) = inf (s) and w/ (k) = inf (T.(s). If the initial state distribution μ is uniform distribution, then any h > 1,
2/22
h-1 2//2
ww (k) 2 2h 2(xx) + 10
Σ 2 H/2 (k) +
2-H/2
2 H/2
(29)
2
O=
Proof. Omitted. The proof is similar to Lemma B.4
Now present the proof for Theorem
25

---

Under review as a conference paper at ICLR 2020
Proof of Theorem C.3 For any [2 consider the interval 4 |k/2*// (A: + 1)/2 If
π does not change at interva lx (that is, (s)(s) E &+Hl = 1), by Lemma B.3 we have
/
(V*
Q (s, क (+))) ds 0.075 2 -/2
(30)
SER,
By Eq
28
Eq
300 and Lemma 27 we have
71(TT)
(T(T))
H
2//2
H 2/
2
Σ
0.075 2 H/2 vn (x)
2-H/2
+
ΣΣΣ
2 H/2 (k) 1-7
(31)
h=1
1=1 k=0
By Lemma C.5
we get
2/22
h-1 1 2/2
2 H/2 (k) 2 1 - 2h ² + 10
2 H/2
(k) +
(32)
2H/2
k=0
h==l k=0
For the sake of contradiction, we assume =(xx)= = 0 (exp(cH)) H), then for large enough H we have,
1 2 Hz(T)) + 10
> 0.8.
2H/2
Consequently,
2/12
2//2
Σ
2-
H/2
un (k) > 0.8
Σ
Σ
2
H/2
ww (k).
(33)
k=
M=1
Plugging in Eq (3..
get
(TT)
H
2
H 2//2
2
0.075 A-1
Σ
2 112 (1())
+ Σ
Σ
7 2- 112 wn(k)
0.1
1-
1=1
1=
1=1
k=0
H Σ 0.075^
1-1 2/22
H 2/2
0.1
A-1
0.8
2 H/2 (k)
+
7 2-H12 w/(())
H12
(k))
1-7
h=1
km
hm
1m
0.06
1
H
+
2/12
2 112 --122 (k)
0.11ah 1-
0..055
Σ
x
1 1-7
k=0
2/2
2 0.06
1
H
+
2 112 (k)
x-
1-7 (0.17 0.075 (1 11
1 1-7
1=1 k=0
When 7 > 1/4, we have 0.1y 0..751 - - > 0. As consequence,
<( (T()) > 0.06 1 1 >
0.01
1- 1-7
Now, since n((T) < 1/(1 - 7), we have TT)) 0.991)(**).. Therefore for near-optimal policy m
2(T)) Ω (exp(cH) H))
D OMITTED DETAILS OF EMPIRICAL RESULTS IN THE TOy EXAMPLE
D.1 TWO METHODS TO GENERATE MDPs
In this section we present two methods of generating MDPs. In both methods, the dynamics p(s, a) has three pieces and is Lipschitz. The dynamics is generated by connecting kinks by linear lines.
26

---

Under review as a conference paper at ICLR 2020
As stated in Section 4.3 the RAND method generates kinks {2;) and the corre- sponding values { randomly. In this method, the generated MDPs are with less structure. The details are shown follows.
RAND method.
State space [0, 1).
Action space A {0, 13.
Number of pieces is fixed to 3. The positions of the kinks are generated by, #; ~ (0, for i 1, and 2h
x1 1. The values generated by x U(0, 1).
The reward function is given by r(s, = s, vs E S,a S.ae4 A.
The horizon fixed as 10.
Initial state distribution is (0,
Figure visualizes one the RAND-generated MDPs with complex Q-functions.
SEMI-RAND method. In this method, we add some structures to the dynamics, resulting more significant probability that the optimal policy is complex. We generate dynamics with fix and shared kinks. generate the output at the kinks to make the functions fluctuating. The details are shown as follows.
State space S = [0, 1).
Action space A = 1).
Number of pieces is fixed to 3. The positions of the kinks are generated by, x; = i/3, YA s S And the values are generated by z! 0.65 I[: mod 2 0.35 U0, 1).
The reward function is r(s, a) for all A.
The horizon fixed as 10.
Initial state distribution is (O, 1).
Figure visualizes one MDPs generated by SEMI-RAND method.
D.2 THE COMPLEXITY OF OPTIMAL POLICIES RANDOMLY GENERATED MDPs
We randomly generate 10t l-dimensional MDPs whose dynamics has constant number of pieces. The histogram number of pieces in optimal policy x² is plotted. As shown in Figure 9 even for horizon H 10, the optimal policy tends to have much more pieces than the dynamics.
Random method
Pseudo-random method
number of MDP5
number of MDPs
150
100
50
0 10
10a
10
10"
10
102
number of pieces
number of pieces
Figure 9: The histogram of number of pieces in optimal policy x² in random method (left) and semi-random might.
D.3 IMPLEMENTATION DETAILS OF ALGORITHMS IN RANDOMLY GENERATED MDP
SEMI-RAND MDP The MDP where we run the experiment is given by the SEMI-RAND method, described in Section D.I We list the dynamics of this MDP in the following.
7(8, a) =8, S.
27

---

Under review as a conference paper at ICLR 2020
(0.131 - 0.690) 2/0.333 + 0.690,
0 x < 0.333,
(s,
(0.907 0.131) (z 0.333) (.5333/0.333. 00.334 + 0.131,
0.333 0.667,
(0.079 0.907) (x 0.667) /..333 0.907,
0.667 S 2,
(0.134 0.865) z/0.333 + 0.865,
0 2 < 0.333,
1(s,1)
(0.750 0.134) (æ 0.333) (333))003344 0..34 + 0.134,
0.333 0.667,
(0.053 0.750) (x 0.667) 0..33 0.750,
0.667 S 2,
Implementation details of DQN algorithm We present the hyper-parameters of DQN algorithm. Our implementation based on PyTorch tutorial
The Q-network is a fully connected neural net with one hidden-layer. The width of the hidden-layer is varying.
The optimizer is SGD with learning rate 0.001 and momentum 0.9.
The size of replay buffer 10
Target-net update frequency is 50.
Batch size in policy optimization 128.
The behavior policy is greedy policy according to the current Q-network with e-greedy. exponentially decays from 0.9 0.01. Specifically, 0.01 0.89 exp(-1/200) the t-th episode.
Implementation details of MBPO algorithm For the model-leaming step, use Eg loss train our model, and we use Soft Actor-Critic (SAC) (Haarnoja et al. 2018) in the policy optimization step. The parameters are set as,
number of hidden neurons in model-net: 32,
number of hidden neurons in value-net: 512,
optimizer for model-learning: Adam with learning rate 0.001.
temperature: 0.01,
the model rollout steps: . = 5,
the length of the rollout: k= == 5,
number of policy optimization step: G 5.
Other hyper-parameters are kept the same DQN algorithm.
Implementation details of TRPO algorithm For the model-learning step. we use & loss to train model. Instead of TRPO (Schulman et al. 2015), PPO (Schulman et al. 2017) policy optimizer. The parameters are set as,
number of hidden neurons in model-net: 32,
number of hidden neurons in policy-net: 512,
number of hidden neurons in value-net: 512,
optimizer: Adam with learning rate 0.001,
number of policy optimization step: 5.
The behavior policy e-greedy policy according to the current policy network. expo- nential decays from 0.9 to 0.01. Specifically, 0.01 + 0.89 (088eepp(1/2000 at the 1-th episode.
ng.
html
28

---

Under review as a conference paper at ICLR 2020
Implementation details of Model-based Planning algorithm The perfect model-based planning algorithm iterates between learning the dynamics from sampled trajectories, and planning with the learned dynamics (with exponential time algorithm which enumerates all the possible future sequence actions). The parameters are set as,
number of hidden neurons in model-net: 32,
optimizer for model-learning: Adam with learning rate 0.001.
Implementation details of bootstrapping The training time behavior of the algorithm is exactly like DQN algorithm, except that the number of hidden neurons in the Q-net set to 64. Other parameters are set as,
number of hidden neurons in model-net: 32,
optimizer for model-learning: Adam with learning rate 0.001.
planning horizon varies.
E TECHNICAL LEMMAS
In this section, we present the technical lemmas used in this paper. Lemma E.1. For A, C,C,D.D and AC 2 BD, we have
A C +
2 (B D) 2022VACE BD.
Furthermore, when BD > 0, the inequality strict.
Proof. Note that A + B+ (C + D) 2VAC + VBD And we have,
(2VAC+ VVD (2VAC+ BD)² AVAC: BD 3BD 2 BD 2 0.
And when BD > 0, the inequality is strict.
29


Reviews:
[{"review_id": "SygSmcvaKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper highlights an interesting issue regarding approximability of function approximators (neural networks). The paper provides cases where the action value function is difficult to approximate and is much more difficult than the dynamics of a model. The author conducts some experiments to claim that even with a large NN, DQN still finds a suboptimal policy. Theorems regarding the appoximability of the action value function are presented. Then the paper proposes that rollout-based search should be preferred for planning and conducts some experiments to verify this. Although the paper points out interesting issues of approximating action-value function, both the motivation and the suggestion regarding MBRL are not convincing.\n\n1. In term of the motivation, those cases listed in the paper are interesting, but they are not representative. In fact, the Dynamics can be far more complicated and it is still an open problem regarding how to learn the Dynamics. Furthermore, the proposed method is to simply combine MCTS and bootstrap value estimates. The method itself is not novel and it basically down weights the bootstrap estimate. It is very intuitive that some appropriate combination between the two can yield better performance. However, in model-based setting, the reward sequence can be highly variant and non-stationary, there is no solid reason to believe this can be always better. The motivating experiments in figure 3 are not persuasive. There can be many reasons for a deep RL algorithm to find a suboptimal policy: boostrap target interference, overestimation, difficulty of optimization, etc. It is quite confusing which factor leads to suboptimal performance of DQN.\n \n2. Theorem 4.3 does not make sense to me. What does it mean by “no constant depth NN can approximate the optimal policy with near optimal rewards?” Notice that, in machine learning community, people rarely pursue perfect approximation (equality). As long as the approximation error can be reasonably small, the approximator should be still useful. Does “no constant depth NN can approximate the optimal policy” mean the approximation error is unbounded? I believe we can still expect a large NN to approximate the action-value function very well. \n\nA minor issue. In page 2, the paper writes “model-free RL or MB policy optimization suffer from …, whereas MB planning … ”. MB planning is not a separate category of MB policy optimization. Such statement is not accurate. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJg89NBeqB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper studies a theoretical aspect of the expressivity of policy, Q functions and dynamics. Based on theoretical and empirical analysis, the authors propose a new model-based RL algorithm that said to improve task performance. Final evaluations are demonstrated on MuJoCo benchmark tasks. \n\nOverall, the paper pursues an interesting and ambitious problem on the interplay between model-based and model-free approaches, and the expressivity of the representation of dynamics, policy and value functions. However, the results in the theory part is drawn based on analysis on a very simple and special task. Therefore the theoretical results can not be considered general for all MDP cases. In addition, these results are not surprising.\n\n- Theorem 4.3 states a general theoretical result that holds for neural networks, the proof does not look like it can hold with a universal representation power of a neural network. \n\n- The idea of using Q-functions estimate as Boostrapping is just an idea of using on-planning to improve action selection at every decision step. This is just a recurring idea of many model-based RL approaches. BOOTS consumes more computations as planning, hence would perform better than the baselines. BOOTS should be compared to other model-based approaches that also use planning at Testing, assume all are given the same budget of testing time.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byx0j9KoKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a mainly theoretical argument comparing the expressivity of model-free and model-based RL methods contrary to analysis in the past which usually relies on sample complexity. They construct a family of MDPs, where the true dynamics belong to a simple function class (in terms of the number of linear pieces needed to define the function), but the corresponding optimal Q-function belongs to a function class not necessarily expressible by a simple function. The paper then builds a similar case for randomly/semi-randomly generated MDPs. Finally, they propose to bootstrap the Q-function with n-step returns to boost the expressivity exponentially. \n\nI would lean towards accepting this paper, as this paper looks at an interesting problem and their analysis seems to be rigorous and valuable for the community to build upon. My questions/comments are as follows:\n\n1. Previous work, for example [1], also talks about bootstrapping a neural net Q-function using an n-step approximation so as to improve the efficiency of a pure model-free algorithm. I think this paper should be cited.\n\n2. In terms of the experiments, it is hard to understand the significance and connection to the theory. The theory talks about the expressive power of Q-functions, which suggests that we should look at only the asymptotic performance on these tasks, but most of the results are similar to MBPO or SAC in terms of asymptotic performance, although with a different learning speed, which could have to do with different factors.\n\n3. This paper shows the existence and provides a constructive proof for a family of MDPs where expressing optimal Q-functions is exponentially harder than expressing dynamics. But how likely is such a setting to arise in MDPs in practice? For example, on the gym benchmarks, we would expect fairly not so complicated Q-functions -- although they might take longer to learn. \n\n4. There is also a divide between learning Q*, and learning a policy that optimizes Q* reasonably well. Further, the requirement for the Q-function is only to get relative ordering between Q-values for different actions at states visited by the optimal policy right, which might not be the same as the Q-function landscape across state-action pairs. So, I am not sure if the expressivity of the optimal Q-function, in general, is the right metric to answer this question, but I also completely agree that this is a good starting point. \n\n5. I think when applying RL to the current benchmarks or problems we have, the main problem could be linked to optimization of a neural-net Q-function via bootstrapping (in the sense of approximate dynamic programming) as compared to the expressive power of optimal Q-functions. But I agree that the problem being looked at in the paper would also exist.\n\nReferences:\n[1] Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control, Lowrey et.al.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides some insight why model-based RL might be more efficient than model-free methods. It provides an example that even though the dynamics is simple, the value function is quite complicated (it is in a fractal). Even though the particular example might be novel and the construction interesting, this relation between dynamics and value function is not surprising, and perhaps part of the folklore. The paper also suggests a model-based RL methods and provides some empirical results.

The reviewers find the paper interesting, but they expressed several concerns about the relevance of the particular example, the relation of the theory to empirical results, etc. The authors provided a rebuttal, but the reviewers were not convinced. Given that we have two Weak Rejects and the reviewer who is Weak Accept is not completely convinced, unfortunately I can only recommend rejection of this paper at this stage.
Decision: Reject