A limitation on black-box dynamics approaches to Reinforcement Learning
Authors: Brieuc Pinon
Raphael Jungers
Jean-Charles Delvenne
Venue: Accepted by TMLR ()

Abstract: We prove a fundamental limitation on the computational efficiency of a large class of Reinforcement Learning (RL) methods. This limitation applies to model-free RL methods as well as some model-based methods, such as AlphaZero. We provide a formalism that describes this class and present a family of RL problems provably intractable for these methods. Conversely, the problems in the family can be efficiently solved by toy methods. We identify several types of algorithms proposed in the literature that can avoid our limitation, including algorithms that construct an inverse dynamics model, and planning algorithms that leverage an explicit model of the dynamics.

Published in Transactions on Machine Learning Research (03/2025)
A limitation on black-box dynamics approaches to Reinforce- ment Learning
Brieuc Pinon
brienc.pinnon@@ullouooo...
Deportment of Mathematical Engineering
U'Couwain
Raphaël Jungers
Department Mathematical Engineering UCLowain
Jean- Charles Delvenne
Department of Mathematical Engineering
UCLowain
Reviewed on OpenReview: https: //pp:re//pperevveeee net/ forum? id- J
Abstract
We prove fundamental limitation on the computational efficiency of a large class of Rein- forcement Learning (RL) methods. This limitation applies model-free RL methods well some model-based methods, such as AlphaZero. We provide formalism that describes this class and present family of RL problems provably intractable for these methods. Con- versely, the problems in the family can be efficiently solved by toy methods. We identify several types of algorithms proposed in the literature that can avoid our limitation, including algorithms that construct an inverse dynamics model, and planning algorithms that leverage an explicit model of the dynamics.
1 Introduction
An important research avenue in Artificial Intelligence is dedicated to creating, analyzing, and evaluating Reinforcement Learning (RL) methods (Russell & Norvig 2010). One goal to understand when and why some methods perform better than others from a statistical and computational point of view. Explaining such differences is central to guiding the design of new efficient algorithms.
A first step in understanding the differences between methods is to abstract them into classes. Two of the main classes of RL methods are model-based and model-free methods. Model-based methods are algorithms that leverage known or learned model of the environment dynamics (Mordatch & Hamrick 2020 In contrast, model-free methods, such as Q-learning and Policy Optimization algorithms (Sutton & Barto 2018), do not use such a model.
Although the distinction between model-free and modcl-based classes commonly accepted (Sutton & Barto 2018), there
agreed-upon general formal definitions of these classes. Authors resort proposing their definitions (Sun et al. 2019) to proving their results on classical algorithms representative of these classes
Tu & Recht 2019h.
Several works have studied the relative performance of these classes from theoretical point of view, and it is cited as an open problem in the survey Levine et al. (2020). For tabular Markov Decision Process, Tu & Recht (2019) review the existing literature that studied the model-free or model-based methods. They find no clear conclusion favor of one class over another. In the specific problem family of the Linear Quadratic Regulator, Tu & Recht (219) remonstrate polynomial separation result in favor of model-based method.

---

Published in Transactions on Machine Learning Research (03/2025)
To our knowledge, Sun et all (0199) provide the only result with a gap in the efficiency that is exponential in relevant parameter of the problems. They offer definition for the class of model-free methods and then present a family of problems intractable for model-free methods but easy for a specific model-based method.
In this work, we define the class of black-box dynamics RL methods containing model-free RL (Q-learning, Policy Optimization,.. ...) and several RT. methods considered to be model-based such as AlphaZero (Silver et al. 2017). These methods do not leverage (learned) knowledge of the dynamics or except possibly by
generating simulations of transitions. Our paper unravels explicitly a limitation this class of black-box dynamics methods and reviews potential ideas in the literature to circumvent this limitation.
To establish our result, we formalize the class of black-box dynamics methods in Definition 3.2 The definition aims to achieve two objectives: (1) to capture a large class of methods encompassing model-free and some model-based RL methods, and (2) to allow the proof of a limitation on these methods. Our definition relies on the fact that black-box dynamics methods can be formulated interact with problems through an interface, a novel concept we introduce (pictured in Figure D. An RL method will fit our definition if the method can still be implemented when our interface is placed between the method and the problem. This interface allows us to formulate and check conditions on the information that flows from the problems to the black-box dynamics methods. In particular, states are not directly fully observable to the method through the interface but only partial information that allows to get (Q-)value and policy functions evaluations.
Next, we introduce a family of problems provably intractable for black-box dynamics methods. However, this family of problems is easy to solve and can be provably efficiently solved by a toy method that identifies rewarding state and learns to reach it. Moreover, we perform numerical experiments and show that planning algorithm leveraging learned model of the dynamics also efficicntly solves the problems in the lamily.
Our work differs from the result of Sun et al. 2019) in two ways. First, we broaden the class of methods with a limitation to some model-based methods such as AlphaZero. We obtain this result by leveraging our concept of interface to formalize this larger class of methods.
Our second contribution with respect to the result of Sun et al. (211 is that our family of problems can be efficiently solved without strong specific priors about it. In contrast, in their result, the success of the model-based method crucially relies on an priori known state to reach. They encode this knowledge into the model-based method to its advantage. In general, such knowledge cannot be assumed to be known in practice and impairs the practical applicability and generality of their claim.
In summaar, our work identifies failure-case for a broad range of general-purpose RL methods. Moreover, we review potential solutions to this flaw in the literature.
This article is structured as follows. Section defines the notation and formalizes the problems address. Section characterizes the black-box dynamics RL methods with our definition and linked interface. Section states our main thcoretical result. Section i demonstrates numerically the performance of several RL
methods. Finally, Section G discusses ideas in the literature that could overcome the limitation presented in
this paper, and Section provides a summary of our findings.
Appendix B presents an alternative formalization choice with its implications, and Appendix C discusses the differences with the work of Sun al. (219 in more detail.
2 Preliminaries
Notation We use A(2) to denote the set of probability measures sample space Ω with an implicitly associated o-algebra. We define the function 1(.) to output 1 if the condition in its argument is respected, else O. For a set A, we note A" === A the set of all finite sequences of elements in A.
In this paper an RL problem a finite horizon Markov Decision Process (MDP), which is defined by a horizon H E N, state space S, an action space and an operator P. which determines an initial state distribution with Po(so) E A(S) and a dynamics with s' s,a) S A(R S), where r is the reward and s' is the next state.
2

---

Published in Transactions on Machine Learning Research (03/2025)
Throughout the paper, the rewards are in the interval [0, 1], the set of actions is binary A= = {0, 1), and the sets of states S are of the form [(1,x) E {O...., H x Rn) for some E N, where t is the time step. Initial states have t = 0, and t is incremented at each transition by Payn- When the time step H is reached, we say that the state is final and the trajectory ends. Our formalization is a particular case of the general framework of Contextual Decision Processes (Jiang et al. 2017).
We note (so, do, To: $1, (....,,55) 5H) p" a trajectory sampled according to the operator P and policy S + A(A). We use nu to denote the policy which outputs uniform distribution over actions.
The objective is to find H-1 re]. An RL method is an algorithm that outputs policy given access to P. We note that the policy returned by the RL method might not be optimal. The method solves the MDP if it outputs an optimal policy.
policy that maximizes the expected cumulative rewards
E (lo.aa.........).....
3 Formalization of black-box dynamics RL methods
In this section, we define the class of black-bor dynamics RL methods (Definition 3.2 and then state a limitation on their efficiency in the next section.
The formalism We defined in the last section RL method algorithm that outputs policy given P (the operator describing the dynamics of an RL problem), but did not formally specify how P is accessed by the method. In the literature, it is common to assume that P can be used to sample trajectories from a chosen policy. Here instead, black-box dynamics RL methods access P through an interface. An algorithm for RL problems is considered black-bos dynamics if it can be implemented in an RL method interacting only with the interface (Definition 3.2l.
The interface, defined in Algorithm 2 is a set of algorithms (oracles) that can be called to get information about the RL problem. The interface is thus placed between the RL problem and the RL method as pictured in Figure 1 This setup allows us to formulate and check conditions on the information that can flow from the RL problem to the black-box dynamics RL method.
To build intuition on the information that we impose the interface to filter, consider deep Q-learning methods as an example. In these methods, the Bellman equation might be enforced by minimizing an empirical average of (Q(s,a) (r + max.' Q(s', a')]² for some sampled transitions (8, r, s') and where Q is an old estimate of the Q-values. We observe that in the Bellman equation, the state s is not directly needed but only its evaluation through Q
More generally, across a broad range of RL methods relying on the Bellman equation, given a transition (s, rs,aa,,s),, the state s' is only used through evaluations of learned ML models such as value or Q-value functions.
With the help of the interface, our Definition 3.2 formulates an abstract condition that these indirect accesses to s' satisfy in black-box dynamics methods, More precisely, when a transition s, r, is sampled from P. the interface does not directly return s' to the calling method, but F(s', D) where D is dataset and F is a function chosen by the calling algorithm. The dataset D is a list of partial information (s, a, f) about past sampled transitions (s, (s,a,r,s)) where f the evaluation of s' by F with an old version of the dataset.
The function F is chosen by the RL method and can be selected to be a Machine Learning (ML) algorithm to learn and use (Q- (Q-)value and/or policy functions. In that case, D can play the role of replay buffer, with it, Fss, D) can learn a neural network according to the Bellman equation and evaluate the state to extract Q-values. This allows the method to choose an action based on estimated Q-values.
We ask F to respect a constraint on its output without obstructing the implementation our methods with the interface. Specifically, we demand that F is invariant to shufflings of the coordinates in the states. This condition is naturally satisfied by ML algorithms since, without a priori, a learning process is expected to treat the features symmetrically. This condition allows to model the reliance of methods on rewards
3

---

Published in Transactions on Machine Learning Research (03/2025)
to extract information from states. This is leveraged in our Theorem 4.1 to prove that some states are indistinguishable from the point of view of a black-box dynamics RI. method.
To implement an RL method with the interface, the RL method should also be able to ask new transitions to generate trajectories or to do local planning by testing several possible actions from a given state. To permit these with the interface without revealing the state 8', the interface returns a number 8 that the RI. method can use to ask for new transitions. In particular, we choose s' be equal to the iteration number at which the state is sampled since the start. For example, at the start, the RL method can ask new initial state; the interface mumbers that state 0 and provide this number to the RL method; the RL method can ask for new transitions to the interface that leads to succossive states numbered 1, ...,, at that point, the RL method could ask the interface to sample a new transition from the 12th state with action a a= 1; the interface then responds to the method with the obtained reward, 18(= and F(s', D) where the dataset D contains information about the 17th first sampled transitions. Simultancously, the dataset augmented with the transition from the 12th to the 18th state for future (improved) state evaluations with F.
In some algorithms, transitions model of the dynamics with the interface under our Definition 3.2 However, it is possible to perfectly simulate the dynamics using calls to the interface that interacts directly with P (describing the true underlying dynamics).
simulated with learned model. It is not generally possible to learn
Black-box dynamics RL methods Our Definition 3.2 below encompasses large set of classical RL methods that includes model-free RL approaches such as Policy Optimization and Q-learning. The defini- tion also includes some model-based RL methods that only use model of the dynamics to generate new transitions such as AlphaZero (Silver et al., 2017). These methods treat a model of the dynamics as an input-output black-box function and do not leverage its internal computations.
On the other hand, there are several examples of algorithmic schemes that our definition does not allow. We defer to Section 0 a discussion on RL methods from the literature that are excluded from definition but describe shortly here some examples.
Learning a model of the dynamics is not allowed, except if it is only used to sample transitions since in that case these transitions can directly be generated with the interface. Thus, the definition does not allow taking a gradient through a learned model or looking inside a learned model of the dynamics.
Also, learning a model of the inverse dynamics not allowed, such as learning to predict the action to take given the current state and a wanted future state.
Definitions As explained above, a black-box dynamics RL method interacts with an interface linked to an RL problem, Algorithm 2 pictured in Figure [ The interface is a set of algorithms with an internal state maintained between calls made by the RL method. Through the interface, the RL method can ask for new transitions, the interface then returns two objects for any sampled state s'. The first object is a number s' computed by an encoder-decoder described below. The interface also returns real vector f: the evaluation of a constrained function F on s' and an internal dataset D. This second mode of state access allows the RL methods to train and evaluate ML models on states, such as learning value functions using neural networks.
At each call for a new transition, the interface computes á and f= F(s', D) then returns these values to the RL method. Simultancously, the interface builds incrementally its internal dataset D with this information. Similarly to RL methods when ML algorithms are used, the ML models are trained from the data, and the data is generated with the help of the ML models. This cyclical dependency is represented by the curved arrows in Figure]]
The state reference 3 is computed by an encoder-decoder of states defined in Algorithm The encoder and decoder translate the states to numbers, and numbers to states respectively. The algorithm numbers the encountered states in the order of their visit (potentially associating several numbers to one state if it is visited several times). This numbering ensures that no information about the state is revealed to the calling method. We use to denote computed number corresponding to some state 8.
4

---

Published in Transactions on Machine Learning Research (03/2025)
Env step
Interface
decode
8,0,F
8,0
RL problem
eacode
s
RL method
1,8.1
B2 2%
Dataset
D
Figure 1: Representation of an RL method that handles the interface linked to an RL problem. The interface allows filtering the information that can flow from the RL problem to the RL method by design. In this Figure, the Env step algorithm of the interface pictured. This algorithm allows the RL algorithm draw transition from the RL problem. The encountered state s' is passed to the RL algorithm through a reference mumber to the state, s', computed by encoder-decodes defined in Algorithm [1 The state is also passed to the method through function evaluation, = F(s', F(s',D), D), defined by dataset D, and chosen function F. This dataset is internal to the interface and incrementally constructed from previous transitions. The function JF can be chosen to implement learning algorithm that uses the dataset to train a Machine Learning model and evaluate it on the generated state s', the result can be used as a value function for example.

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm Encoder and decoder of states.
last idx --
list 11
function ENCODE STATE(s)
list plst.puush(s)
$ $+-aastidxx+1
output
function DECODE POINTER(5)
output list[s]
Algorithm Env: an interface linked to an RL problem defined by the transition operator P. The interface is set of algorithms with a common internal state. The interface has access to an initialized encoder-decoder of states as defined in Algorithm 1
D D+1)
D internal dalaset
function Env init(FF)
Su ~ Pa
So eencode state(so)
output $p. F(so: D)
function Env__tepile 4- decode decodde_pointer({) pointer(8)
F, append_ to data True)
if s is not final then
r, ~ (r, s,a) s' encode state(s') f F('(') if append to data then
number linked to the state revealing no information allows to train and evaluate (Q-)value and policy functions
b set to False to not add the transition to the dataset
+ Dappend((s.a.r.f)
output r, 3, else if is terminal then output 1
function Env eval state(s, F) output D) function Env eecodd(sc
output prcode_state(f
Our Definition 3.2 requires that the function F respects special symmetry condition under permutations
of the input coordinates. We define such permutations here in Definiton 3.1
Definition 3.1. permutation of coordinates p IR" + R" a function such that for E RR" p(z).()) = 24 for some bijective function u from (1...n) n) to itself.
We also interchangeably p' N R N RD defined as p((()=))) ((x)).
From these definitions, we can express Definition 3.2 of black-box dynamics RL methods.
Definition 3.2. A black-bor dynamics RL method interacts only with the interface (Algorithm) 2 linked to the RL problem. The function F given in argument to the algorithms of the interface must have the following form F: SF + N where N a natural number and E Ax AX is dataset. Moreover, for any permutation of the coordinates p, we must have F(s, ((su, ag, Fo. fo)....) = F(p(s), ((((s)) an, ros .)) for any state S and (so, ao, ro, fo) E A R R
Interpretation and examples This formulation of the Delinition 3.2 reaches two objectives:
1. To allow large class of common RI. methods to fit the definition.

---

Published in Transactions on Machine Learning Research (03/2025)
2. To constrain the information that can pass from the RL problem to the RL method, allowing us to prove the limitation in the next section.
The definition reaches the first objective by allowing to encode common patterns in RL methods. We provide several examples of this flexibility.
The first step in converting an RL. method to fit the interface is to replace any generation of transition (s, a, r, s') by a call to the interface defined in Algorithm 2 in particular, the Env_ _tep algorithm pictured in Figure T
The reward r is directly observable and thus the Definition 3.2 poses no limit on his manipulations by the calling method. The state s' is not directly observable but the RL method can use sf and f F(s', D) (still defined in Algorithm 2)
The first element, s can be used to draw new transitions with new calls to Env step. With this ability, we can sample complete trajectorics (so, du, To: 81, a1....,,g11. something which is essential to RL methods. We can also leverage the generation of transitions to simulate common local planning procedures by calling the interface several times with s and different actions (c.g. tree search).
Another step in converting an RL method using ML models to fit the interface is to code the manipulation of these ML models. To accomplish this, the function F(s', D) can: first, apply learning algorithm applied on the internal datasct D (composed of old transitions and ML models evaluation) to produce a trained ML model; second, evaluate this model on the state s', giving J, to add information to D and be manipulated by the RL method, as a value function evaluation for example.
For instance, in the case of a doep Q-lcarning method: D has the role of a replay buffer of past experience; F is a learning algorithm that given the replay busfer D and state s, learns Q-value function then applies it on s. We show in Appendix D that this construction allows for modeling the training of deep (Q-)value and policy functions.
The function F is thus used as a learning algorithm in our translation of existing RL mods to use this interface. The symmetry restriction on F posed in Definition 3.2 can be intuitively understood as a restriction on the learning algorithm. Specifically, our restriction demands that the learning algorithm treats the coordinates of the input state vectors symmetrically. This restriction is natural since, without a specific prior about the task at hand, we do not wish to process the different coordinates in particular ways. However, we note that in practical sctting with neural networks, the weights are initialized randomly, which can create asymmetries. Nevertheless, prove in Appendix D that the distribution of trained neural networks has the demanded symmetries under a natural assumption on their architecture.
We stress that the symmetry restriction imposed on F docs not imply that the learned ML model is invariant to permutations of its input coordinates. Instead, the restriction imposes a symmetry between ween the learned ML model and the dataset used for its training. For example, when learning a linear model, if we permute the first two coordinates in the training data, then the resulting model will also have the values of its first two parameters permuted.
In the special case where there is known prior information about the RL problem, the practitioner might want to use a Machine Learning algorithm that does not fit this restriction. For example, in Image Vision tasks Convolutional Neural Networks (CNNs) are commonly used and those do not respect our symmetry restriction. However, in the case of CNNs, these architectures usually produce a latent space over which an agnostic neural network architecture applied. Our results will apply this latent space. More generally, we believe that results can apply under any sufficiently broad prior.
In Appendix D. as an example of our formalization, we show how classical RL. methods can be translated to use the interface as constrained in Definition 3.2 We give four complete examples: a fitted Q-iteration method; a model-free policy gradient algorithm (Actor-Critic method); a local tree search model-based method; and a combination of tree- based planning and value function à la AlphaZeero (Silver et al. 2017).
These examples are archetypes of the main categories of RL methods and cover Q-learming with the Bellman equation, Policy Optimization with policy gradients combined with a critic, and black-box model predictive
7

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 3 A goal-conditioned algorithm.
Paramcters: N: number of samples, a: parameter the learning algorithm (number of active features)
Input: P: the transition operator corresponding to the RL problem
D - 0 for - 1....N do
+ D 4o $1, 01, (I....,511) .H) ~ p
9 + argmax;; r s.t. (...,, T, T,HH) E
1] do for E (O...... (e)))alllel) ( ...,,, St, , 8t) ) D)
Doc + (p)
f' the result of the optimization program in Equation [ with dataset oo and parameter
output x(als)) = =f g))
control with tree-based search. The last example also covers a mix of model-based tree-based search and model-free RL. We refer to the documentation of AAchiam 2018 for a taxonomy of RL methods. These examples also illustrate how several commonly used exploration methods fit our framework: e-greddy, on- policy, and optimism under uncertainly with UCB. Our prools for these examples depict how other methods be translated to fit Definition 3.2
4 Main theorem: limitation of black-box dynamics RL methods
We just characterized the class of black-box dynamics RL methods through the Definition 3.2 We prove this section that these methods suffer from a computational efficiency limitation on a family of RL problems. In contrast, these problems efficiently solved by toy method. The toy method learns to map future states to actions and then applies that mapping to reach detected rewarding state.
We define here this efficient toy method based on Hindsight Experience Replay (Andrychowicz et al. 2017
The toy method, Algorithm 3 first samples a dataset of trajectories by drawing actions uniformly. From this dataset, it extracts a final state that gives maximal reward when entering it and poses this state as its goal. From the same dataset, function is learned predict the action taken from any state given the reached final state. Finally, the algorithm constructs policy that follows the action predictor conditioned on the goal as the final state.
The learning algorithm for the action prediction minimizes the empirical rate of errors the dataset. The space of functions in which we learn is composition of a feature selection, linear function, and a threshold (to output a binary prediction). The formal mathematical program is
arg min fwEF
Σ
1(f
St 8H
) * a)
(a)
(1)
s.t. ||l]oo S a,
where 8t denotes the states concatenated in vector in 2 dataset Doc is defined in Algorithm F [ is the set of linear functions with threshold, F = {ir E 2 + 1((w,x) > 0) R?",, and w E R is the parameter associated to fa- The condition ||w||| < bounds the number of non-zero weights in the lincar function by a E N.
This method is elementary and limited: exploration is performed with a uniform policy; F is a restricted set of functions; the method is only trying to reach final rewarding state to maximize expected returns; and the scheme is not sound in stochastic dynamics. Thus, this method does not address the general problem of RL. Nevertheless, the method is sufficient to support the claims of this paper:
8

---

Published in Transactions on Machine Learning Research (03/2025)
The RL problems in Theorem 4.1 are easy to solve and not efficiently solving them is limitation since any RL. method that cannot efficiently solve these problems is beaten by Algorithm B toy method that merely predicts actions to reach a detected rewarding state.
A method that constructs model of the inverse dynamics (such as Algorithm 3 can help to avoid the issue identified in this paper.
We have now defined everything needed to state our main result. Theorem 4.1. There erists a family of RL problems such that
1. For any RL problem in the family and ō E (0,1), 1), with probability at least 1 (over the sampled tra- jectories), Algorithm 3 outputs an optimal policy with number of samples and number of operations upper bounded by polynomial in horizon H and 1/8.
2. For any algorithm satisfying Definition 3.2 and using o(2 calls to the interface (Algorithm 2). there crists problem in the family for which it outputs suboptimal policy with probability at least 1/3.
The second affirmation bounds from below the computational complexity of black- dynamics RL methods to solve the problems, thus for those methods the family of problems is intractable. Conversely, the first claim ensures that Algorithu 3 efficiently solves the family of problems. Thus, the Theorem proves separation in efficiency to the vastavantage of black-box dynamics methods, implying a limitation on a large class of methods (which includes, as seen in Section 3 Q-learning, Actor-Critic methods, AlphaZero, ...). Another consequence of the Theorem that the toy method basod on Hindsight Experience Replay (Algorithm cannot be formulated as black-box dynamics method.
The complete proof is given in Appendix A It is partially inspired by some of the proofs in Sun et al. (019 We provide sketch here with the main intuitions.
We explicitly construct a family of RL. problems satisfying the requirements in Theorem 4.1 The problems in our family are defined by two parameters: a horizon H/ E N; a hidden binary word b E {0, 1 that represents a sequence of actions that solves the task. A representation of one clement of the family for a small horizon is given in Figure 2
The dynamics starts at unique initial state from which two possible states are drawn randomly. The first state starts the left-hand dynamics, unique trajectory that ends up in a rewarding state. The second state starts the right-hand dynamics, in it the number of possible trajectories grows exponentially with the horizon. At the end of these trajectorics, the dynamics transitions to a final state that represents the differences between the history of actions taken and the hidden binary word b. If there are no differences between the binary actions taken and b, we arrive at the same state as the left-hand dynamics, and a reward is obtained.
The right-hand dynamics has a number of possible final states that grows exponentially in the horizon, and the unique rewarding state is hard to reach by purely random actions independent of the hidden binary word b. Information about b is only present in the final states, and we show in the proof that the information in the final states of the right-hand dynamics is hidden under the Definition 3.2 More precisely, Definition filter through evaluations of F(., D), and any F(., D) is
3.2 only allows information about these states provably constant on these states due to the symmetry restriction. Methods satisfying Definition 3.2 will thus not do better than enumerating all the possible behaviors since they do not have access to relevant information to orient the search in the right- hand dynamics.
We illustrate the reasoning with the example of a Q-lcarning algorithm implemented with the interface applied to the problem in Figure 2 When sampling some final state 8и; the only information filtering through the interface to the method is the obtained reward, the encoding sH, and Q = F(sH, D). The encoding R is simply the number of states encoded up to now and revcals no information about sh and the problem. The output Q,, represents the Q-value estimates at that state built from the dataset D composed of tuples (8, a, r, Qu)), where these tuples based on previously sampled transitions (s,a,r, r')))) and an old
9

---

Published in Transactions on Machine Learning Research (03/2025)
00
010.0 0'0
1/2
4/2
1 0000
11000.000
0.-0
0 20000 0'0
0 0,0,
0
0'0"
2 0'0"
00 0000000000
300000000
00
3
0 3,0 000
3/ 3
11
11
40.00 00000
11
4 10.0000
41000 0
0 4.000 PT
4/0.0. 1
Figure 2: Example of the family of RL problems for horizon and hidden binary word b = 01. On the lent-hand dynamics, the agent can easily discover the unique rewarding state. In comparison, a reward is hard to get the right-hand dynamics using random exploration but by exploiting the dynamics and a discovered relevant goal, an algorithm can uncover an optimal path (such as toy method Algorithm
estimation Q2 of the Q-values at s'. The dataset can only contain non-final states by construction of the interface. Also, by construction of the problem, the (non-final) states in the dataset and final states have different coordinates with non-zero elements. Given these elements, an analysis with the symmetry condition on in Definition 3.2 reveals that Q., F(sn, D) is constant with respect to 8n- Thus, this case, only the obtained reward exposes information about the problem for black-box dynamics method.
In this analysis, the symmetry condition asked F is crucial. It allows us to prove that the outputs of F are equal for different states in our problems. These states are thus indistinguishable, and imply that the algorithm fails to leverage the crucial information in them.
For Algorithm 3 the left-hand dynamics allows the RL method to discover the rewarding state easily and set as its goal. The right-hand dynamics is sufficiently simple for the learning procodure reliably predict the necessary sequence of actions to reach this goal. With high probability, the returned policy will thus reach the rewarding state in the rinht-hand dynamics.
10

---

Published in Transactions on Machine Learning Research (03/2025)
Generalization Our result defines an example family of problems but does not provide general conditions problems upon which the limitation on black-box dynamics methods appears. Nevertheless, from this family, we can extract some key elements to our proof of the limitation:
the dynamics have several actions to take and each is critical to the success;
each action has a positive or negative effect depending on the initially unknown dynamics;
the dynamics aggregate the effects of all the actions into one binary reward, thus hiding the effects of each action to a method relying on reward feedback.
At the same time, these problems are tractable for our toy methods because:
rewarding state reachable with the above actions can be inferred from random exploration;
the effect of each action is revealed in the state-to-state transitions.
These core characteristics informally define sufficient conditions to show a limitation. An improvement over our result could be to formally define sufficient. conditions as general as possible on problems for the occurrence of limitation. This would require several generalizations over Theorem [.1 More precisely, it would be necessary to generalize the bound on the performance of black-box dynamics methods to broader range of problems. Additionally, more universal algorithm should be proposed than our loy met hod (Algorithm 3), supported by an equally universal guarantee of its performance. These generalizations and their scope will determine the breadth of any obtained limitation.
Domination A corollary of Theorem 4.1 is that for any black- box dynamics RL method, another method exists that always performs least as well and sometimes better on RL problems. This result can be obtained by constructing new method that executes in parallel both the black-box dynamics method and Algorithm g Appendix A contains formal statement and associated derivation of this fact.
5 Numerical experiments
We illustrate and confirm numerically how practical deep RL methods perform the family of RL problems constructed in the proof of Theorem 4.1 We also test the gosl-conditioned method from the last section. Moreover, we introduce another method that performs well on our set of problems. This method leverages non-black-box model of the dynamics for planning.
We test model-free methods such as fitted Q-iteration (Riedmileer 2005): We implement and run a classical Actor-Critic method, Proximal Policy Optimization (PPO) (Schulman et al. (017). Moreover, we test AlphaZero, model-based method leveraging learning and local planning (Silver al. 2017). We refer to Appendix G for details on the implementations.
We test Algorithm 3 but with neural networks trained by gradient descent as learning procedure instead of the function space defined in Equation [
In addition, we propose and test a second algorithm that empirically performs well on the family of RL problems. A more detailed description of this algorithm is available Appendix
This algorithm iteratively alternates between two computations. One, learning model of the dynamics from sampled trajectories. Two, sample trajectories by using planning algorithm to determine the actions. The planning algorithm converts the current state and the learned model of the dynamics into a mathematical program that maximizes the sum of future rewards. Then, an off-the-shelf solver solves the mathematical program and outputs a plan with the action to take. The algorithm iterates this procedure until perfor- mance threshold is obtained, then the training stops and the method outputs the planning procedure as its policy.
We propose this algorithm support two claims.
11

---

Published in Transactions on Machine Learning Research (03/2025)
1.0
0.8
Fraction of successes
Conditioned
Planning Solver
Fitted Q-iteration
0.4
Proximal Policy Optimization
AlphaZero
0.2
Random Heuristic
0.0
10
20
30
40
50
Horizon H
Figure 3: Fraction of successes function of the horizon for each method the RL problem family illustrated in Figure We performed 45 runs for each point on the Figure. An upper bound on the standard deviation is displayed. The Cond-Conddtione denotes Algorithm 3 with neural networks and Planning Solver is the planning method presented in this section. The Random Heuristic denotes the analytically computed performance of a method that samples random actions until reaching a rewarding state on the right-hand dynamics of the problems, then copies that behavior. This method assumes access to 50.000 sampled trajectorics.
Firstly, we illustrate in second way that our RL problems are tractable. This method relies on the fact that the dynamics of our MDPs are easy to learn and an off-the-shelf solver can plan efficiently in these dynamics. Those general properties that an efficient general method should be able to take advantage of.
Secondly, this algorithm illustrates another idea in the literature than the goal-conditioned Algorithm 3 Algorithm 8 learns a link from future states to present actions directly, while here we propose an algorithm that lcarns a model of the forward dynamics. This algorithm is also interesting to compare with other model-based RL methods on which the limitation applies (e.g- based on tree search). This new planning algorithm distinctively leverages an explicit model of the dynamics by decomposing this model into structured constraints, instead of only using the model as black-box generator of samples.
We apply these methods to problems of the family constructed in the proof of Theorem 4.1 with increasing horizon. For the fitted Q-iteration and PPO methods, we sample 50 times 1000 trajectories during one train- ing run. The AlphaZero method accesses 3 times 1000 trajectories, where for each state in these trajectories, the planning procedure leverages 50 simulation of transitions. Thus, the method leverages an equivalent total of 150 000 sampled trajectories. We sample a dataset of 1000 trajectories for the goal-conditioned method. The new planning algorithm takes 1000 randomly sampled trajectories for its initialization, and then at most 1000 additional trajectories sampled in the alternations between learning and planning for any run.
To mcasure the success of method, we check if its returned policy reaches the rewarding state in the right- hand dynamics with 1000 sampled trajectories, this allows the goal-conditioned algorithm to do minimal exploration.
The results are presented Figure The model-free methods quickly fail solve the task when the horizon is increased, their performance is bounded by simple heuristic method that randomly explores the environment and then copies the best-performing behavior. This is in line with our theoretical results.
12

---

Published in Transactions on Machine Learning Research (03/2025)
Despite being allowed fewer samples and not more computing time, the goal-conditioned and planning methods successfully solve the tasks for much longer horizons.
6 RL methods avoiding the limitation
There exist several types of methods that do not fall in the class described by Definition 3.2 and are thus potentially free of the flaw highlighted in this paper. We identify the following algorithmic approaches with that property in the RL literature.
Backpropagation through a learned model. The algorithms learn a smooth model of the dynamics then use backpropagation through the learned model (Nguyen & Widrow 1990 Jordan & Rumelhart, 2013 Deisenroth Rasmussen 2011; Grondman 2015 Heess et al. 2015)) These methods elude our definition because the learned model is not treated as a black-box by the algorithm. We note that these methods are mostly used in environments where the dynamics approximately smooth, such as low-level control in robotics.
Csymbicil/symbolicc planning. The algorithms construct a symbolic or semi-parametric model of the dynamics and then apply classical planning algorithm (Russell & Norvig 2010 Konidaris et al. 2018: Kurutach al.) 2018 Asai et al., 2022). This example is related to the previous one, it evades the proved limitation when the symbolic planner does not treat the model only as black-box generator of transitions but leverages insights in it. The method presented in the numerical experiment section is an implementation of this idea since it decomposes its learned model of the dynamics into structured constraints for planning.
Universal value functions. Universal value functions (Sutton et al. 2011 Schaul et al. 2015 Andrychow- icz et al. 2017) can be learned to decide which states can be efficiently reached from which states. These algorithrs bypass our definition because the value functions take as input the states in the future of the trajectory, and the quantities they learn cannot be replaced trivially by a generator of transitions.
Inverse model and goal-conditioned. A wide variety of algorithms learn link from the future to the past of a trajectory. An example is learning an inverse dynamics model (Mordatch & Hamrick 2020). These algorithms avoid the limitation for the same reason as the universal value functions: the future of the trajectory is directly used learn the relevant functions, and there is no trivial efficient. way to replace the computed quantitics with a gencrator of transitions.
Inverse dynamics models goal-conditioned methods learn to predict the action to take given the current state and state to reach in the future (Ghosh et al. 2019). There exist variants of this idea, Janner et al. h proposc to learn mapping from a current and future state to full sequence of intermediary states.
These different functions can be efficiently learned with Hindsight. Experience Replay, where what is reached in a trajectory is relabelled as a goal in hindsight for training (Kelbling 1993 Andrychowicz et al. 2017
We note however that not all these methods are sound in the presence of uncertainty, as described (and
alleviated) in Paster et al. (002)) Eysenbach et al. (2022) Yang et al. 2002 Villaflor al. 2022).
Exploration methods We refer to Ladosz et al. 2022 for survey on exploration RT methods and follow their taxonomy. Our class of black-box dynamics methods covers some commonly used exploration techniques such as e-greedy and optimism under uncertainty with UCB, as shown in Appendix [ Other exploration techniques do not necessarily fit our class. Methods based maximizing intrinsic rewards, state
or behavior diversity, do not solely focus on the task-reward and are thus not covered by Definition 3.2 Also,
methods based on exploratory goals might use universal value functions and Hindsight Experience Replay approaches which are also out of our class, as discussed above.
Not all of these algorithms necessarily solve efficiently the family of RL problems we defined. Our theoretical and numerical results suggest that some ideas present in them could help solve problems otherwise intractable for large class of classical RT. methods.
13

---

Published in Transactions on Machine Learning Research (03/2025)
7 Conclusion
We introduced the class of black-box dynamics RL methods with Definition 3.2 and its linked interface. This class encompasses model-free methods such as Q-learning and Policy Optimization, as well as several model-based methods such as AlphaZero. For this broad range of methods, we proved a computational efficiency limitation on a family of problems in Theorem 4.1 However, we described two toy methods that can efficiently solve these problems.
The problems used in the proof of Theorem 4.1 feature two different dynamics randomly chosen at the start of the trajectory. The first dynamics is simple and allows an algorithm to easily discover rewarding state, In the second dynamics, finding a behavior that reaches a rewarding state is hard. However, these two dynamics have a common unique rewarding state. An efficient method is able to discover the rewarding state in the first dynamics and then plan to reach that state with learned knowledge of the second dynamics.
To summarize our findings intuitively, a large class of RL methods will unnecessarily struggle in environments where following rewards alone is not informative enough. Our results reveal an incapacity of black-box dynamics methods to leverage essential information from some RL problem dynamics. In Section G we list several ideas in the literature that could help lo construct general-purpose RL methods without the identified flaw.
Acknowledgements
RJ is a FNRS honorary Research Associate. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program under grant agreement No 864017 - L,2C, from the Horizon Europe program under grant agreement No101177842 Unimaas, and from the ARC (French Community of Belgium)- project name: SIDDARTA.
References
Joshua Achiam. Spinning Up in Deep Reinforcement Learning, 2018. Accessed: 2023-11-31.
Marcin Andrychowiez, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Thomas Authony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. Advances in neural information processing systems, 30, 2017.
Masataro Asai, Hiroshi Kajino, Alex Fukunaga, and Christian Muise. Classical planning in deep latent space. Journal of Artificial Intelligence Research, 74:1599- 1686, 2022.
Mare Deisenroth and Carl E Rasmussen. Pilco: A model-based and data-efficient approach to policy search. In Proceedings of the 28th International Conference on machine learning (ICMI-11), pp. 465-472, 2011.
Benjamin Fysenbach, Soumith Udatha, Russ R Salakhutdinov, and Sergey Levine. Imitating past successes can be very suboptimal. Advances in Neural Information Processing Systems, 35:6047 6059, 2022.
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 0rXiw:1803.00100 2018.
Dibya Ghosh, Abhishek Gupta, Ashwin Reddy, Justin Fu, Coline Devin, Benjamin Eysenbach, and Sergey Levine. Learning reach goals via iterated supervised learning. arXiv preprint 191:i:1112.0000 2019.
I Grondman. Online model learning algorithms for actor-critic control, PhD thesis, Delft University of Technology, 2015.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https: http::///www... http://wwwwbb..ooo
14

---

Published in Transactions on Machine Learning Research (03/2025)
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicra,, Tom Erez, and Yuval Tassa. Learning con- tinuous control policies by stochastic value gradients. Advances in neural informalion processing systems. 28, 2015.
Michael Janner, Yilun Du, Joshua B Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. arXiv preprint arXiv:2205. 299992995.99 2022.
Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Michael Jordan and David E Rumelhart. Forward models: Supervised learning with distal teacher. In Backpropagation, pp. 189 236. Psychology Press, 2013.
Leslie Pack Kaelbling. Learning achieve goals. In IJCAI, volume 2, pp. 1094 Citeseer, 1993.
George Konidaris, Leslie Pack Kaelbling, and Tomas Lezano-Perez. From skills to symbols: Learning sym- bolic reprosentations for abstract high-level planning. Journal of Artificial Intelligence Research, 61: 215 289, 2018.
Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart J Russell, and Pieter Abbeel. Learning plannable repre- sentations with causal infogan. Advances in Newral Information Processing Systems, 31, 2018.
Pawel Ladosz, Lilian Weng, Minwoo Kim, and Hyondong Oh. Exploration deep reinforcement learning: A survey. Information Fusion, 85:1-22, 22, 2022.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiu:2005.01643 2020.
Tya Loshchilov and Frank Hutter. Decoupled weight decay regularization. Xr preprint 1r11::7711.05101. 2017.
Igor Mordatch and Jessica Hamrick. Tutorial on model-based methods in reinforcement learning. https:
//sies google. com//view//brl--tutrriaa 2020. Accessed: 2023-07-31.
Derrick H. Nguyen and Bernard Widrow. Neural networks for self-learning control systems. IEEE Control systems magazine, 10(3):18 23, 1990.
Keiran Paster, Sheila Mcllraith, and Jimmy Ba. You can't count on luck: Why decision transformers and rvs fail in stochastic environments. Advances in Neural Information. Processing Systems, 0-33966-38977 2022.
Martin Riedmiller, Neural fitted q iteration first experiences with a data efficient neural reinforcement learning method, In Machine Learning: ECML 2005: 16th European Conference on Machine Learning, Porto, Portugal, October 3-7, 2005. Proceedings 16, pp. 317-328. Springer, 2005.
Stuart J Russell and Peter Norvig, Artificial intelligence modern approach. Prentice Hall, 2010.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. International conference on machine learning, pp.
PMTR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithms. arXiv preprint arXiv: MxXi:1707.0633 06347, 2017.
Shai Shalev-Shwartz and Shai Bav-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Dricssche, Julian Schrittwieser, Ioannis Antonoglou, Veda Pannoershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural notworks and tree search. nature, 529(755)):484-488) 2016.
15

---

Published in Transactions on Machine Learning Research (03/2025)
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXie preprint arXiv:1712.01815, 2017.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in textual decision processes: Pac bounds and exponential improvements over modcl-free approaches. In Conference learning theory, pp. 2898 2933. PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsupervised sensori- motor interaction. In The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume 2, pp. 761-768, 2011.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference on Learning Theory, pp. 3036 3083. PMLR, 2019.
Adain R Villaflor, Zhe Huang, Swapnil Pande, John M Dolan, and Jeff Schneider. Addressing optimism bias in sequence modeling for reinforcement learning. In international conference on machine learning, pp. 22270 22283. PMLR, 2022.
Sherry Yang, Dale Schuurmans, Pieter Abbeel, and Ofir Nachum. Dichotomy of control: Separating what you control from what you cannot, In The Eleventh International Conference Learning Representations, 2022.
16

---

Published in Transactions on Machine Learning Research (03/2025)
A Main Theorem proof
In this section, provide the main Theorem proof, then compare it with the proof in Sun ct al. (0099 Finally, we state and prove domination result inferred from our main Theorem. Theorem 4.1. There erists a family of RL problems such that
1. For any RL problem in the family and ô E (0, 1), with probability at least 1 1-ô 8 (over the sampled tra- jectories), Algorithm 3 outputs an optimal policy with number of samples and number of operations upper bounded by polyuomial in horizon H and 1/5.
Por any algorithem salisfying Definition 3.2 and using o(2 calls the interface (Algorilhmm 2). there crists a problem in the family for which outputs suboptimal policy with probability least 1/3.
Proof. We define the family of RL problems. The problems in the family parametrized by horizon H and by hidden binary word b of length H 2. Each state is defined by 3(H - 2) + real variables. The action space is binary. An example in this family for H = 4 and b = 01 is represented in Figure 2
We pose some notations to describe the states. Each state is decomposed into three parts a, b, and e, the part further decomposed into parts and d. The time step to which the state belongs kept implicit in our description. For between and -:
sad the ith variable in the first part of the state vector;
b//d, if u, the up ith variable in the second part of the state vector, d, the down ith variable in the second part of the state vector;
sf the variable of the third part of the state vector.
Example of the notation for state vector s:
gall a.2 8 ...., , n-2 ghall sh,u2 shoat b. hhddl ghdd2 bod H. 8
ai
Now we describe the dynamics. At step 0, whatever action taken, with probability 1/2, we reach either a state full of zeros, or state full of zeros except for s" which equals one.
If we have sf = 0, then for the steps t = 1 to t H 1, the state vector stays zero. At the last step it gives reward of and the state with 5 = 0 - b,u
- gdd 02 and of ===0 0.
If 8 == then from time step f = 1 to = H - 2, the transition from / to + encodes the binary action taken into a. with zero reward (the other variables keep their values from the previous time step). At the last step, the dynamics fixes 8f = 0, all the variables that encode a past action to zero 8 = 0 and s
()) with respect to a fixed optimal trajectory given by or not ())
express if each action taken was correct
b,u. = 1 = 6.) and sH A.d,i = 1(s a. # 6.). the binary word parametrizing the problem. In other words, SH b.v At that step, if 8 2 then a reward of is given. Such that, reward is obtained only if all the actions taken follow the hidden binary word b.
We prove the first claim of the Theorem.
Take Algorithm
3 and fix any E 10.
There exists lower-bound polynomial in log 1/8 on the number of sampled trajectorics, K, such that for any horizon, H, with probability least 6/2 the rewarding state is discovered with the left-hand dynamics (s = 0)-
17

---

Published in Transactions on Machine Learning Research (03/2025)
Moreover, we demonstrate in Lemma A.6 that Algorithm 3 obtains, for 1 and any K larger than some polynomial in H and 1/8, with probability at least. 1 - 6/2 over the sampled dataset, goal-conditioned function which predicts correctly the action to take on the right-hand dynamics (when sf =).
By choosing K sufficienlly large and applying the union bound, the probability that one these events fails is bounded by 5. With high probability, the policy (a]s+) = (aaa), 9) will reach the rewarding state (and thus act optimally) when sf 1. When of = 0, the policy does not influence the expected return. The policy is thus optimal.
Moreover, this method can be efficiently implemented from a computational complexity point of view.
Now we prove the second claim. We will prove that the part of the problem where of equals one is equivalent to an armed-bandit problem family (Definition A.7) with 2 arms where only one arm gives a reward. Following Proposition A.8 any algorithm using o(2 calls will fail to identify the best arm with probability at least 1/3 on some problem in the ammed-bandit problems family. This entails the Thcorem.
In the rest of the proof, assume that across the family for fixed H and thus provides no information on b.
the branch where sf 1, the branch sf 0 is constant
We prove that all the states at the last steps which have zero-reward are indistinguishable. Due to Definition 3.2 information on these states can only be obtained through evaluations of a function FF with one of these states as the first argument (since these states are final, they cannot be added as direct input in the dataset D).
We prove that these evaluations are identical for all those states. These states only contain non-zero elements in coordinates which are always zero in the states present in the dataset. Moreover, they have exactly the same number of ones in those coordinates. Thus, F, which is symmetric on permutations of the coordinates, cannot distinguish them. Formally, let be two final states on the right-hand side 2, there exists a permu- tation of the coordinates such that w = =(2) and s = p(s) for all states present in the dataset D. This implies, for any F, by the symmetry constraint on F,
F(z, ((s0, Co ro. fo).... )) F(p(z), ((p(so), ao To, fo)....) = F(w, ((so, ao, fo).
Thus, non-rewarding final states on the right-hand dynamics are indistinguishable for RL methods satisfying Definition 3.2 The family of right-hand dynamics is hard the family of armed-bandit problems for those methods.
Similarly to Sun et al. (2019). we prove that for the studied class of methods, the problem family is indis- tinguishable from a hard family of black-box problems, implying the limitation. We adapt the proof to our class of black-box dynamics methods, by changing how information is hidden to prove the indistinguisha- bility. Instead of hiding some states behind their evaluations with optimal value functions as in (un et al. (2019), we hide them behind function evaluations corresponding to learned ML model outputs. We leverage the symmetries these models satisfy with respect to their constrained dataset to prove that some states are treated equivalently. Our interface also outputs pointers to states 3 but those do not disclose any information on the states.
Another point comparison with the proof of Sun et al. 20119 is the addition of a trajectory allowing a method to discover a rewarding state. This is critical to get a method that can efficiently solve the presented family without an a priori goal-state. In parallel this addition, the efficient method and the guarantee of its performance are also new this proof. We refer to the introduction and Appendix C for summary of what our results gain from these differences.
The following definitions and affirmations are classical results from VC dimension theory and can be found in the reference Shalev-Shwarde & Ben-David (011)).
Definition A.1. Hypothesis class.
A set H is hypothesis class if H is set composed of functions from some domain X' to (0, 1}.
18

---

Published in Transactions on Machine Learning Research (03/2025)
Definition A.2. Shattering.
A finite set S S X is shattered by hypothesis class H if for any function ʃ from S to {0, 1), there exists h E H. such that for all a E S we have f(x) = h(z).
Definition A.3. VC-dimension.
Given set X, the VC-dimension of hypothesis class defined on domain X' is the maximal integer d such that there exists subset of X' of size d which is shattered by H.
Proposition A.4. VC-dimension of the union.
Given r lypothesss classes of VC-dimension al most d sharing the same domain, the VC-dimension of the union of these classes is at most 4d log(2d) + log(r))
Proposition A.5. Agnostic PAC-learnabiltty from bounded VC-dimension.
There erists a constant C1 E IR such that for any 8, E 1), given a hypothesis class of VC-dimension d, and a dataset C x {0,1} of size at least C1 d+Hog(1/6) composed of identically and independently drawn et
samples (I, 4) according a probability measure P on x {0, {0,1}, we have, with probability at least (over the sampled dalaset),
Lp(arg min Ls(h)) S min Lp(h') te, NEH
where Lp(h) is the error rale of classification according to measure P, P((()))(((((()) # v),, and Ls(h) is the ervor rate on the dataset, Σ ExE I(h(x:) + v).
Lemma A.6. For Algorithm 5 with parameter = 1 and any 8 E (0.1) on the fomily presented in the proof of Theorem 4.7, there erists m. a polynomial in H and 1/a, such that with a dataset of trajectories larger than m mH, 188 obtained by nh with probability at least 1 1- ô over the sampled dataset, for all time steps S H and with oi 1, the learned function (a) 9) perfeclly predicts the action reach the gool 9, if the state g is reachable from St.
Proof. The proof can be decomposed in 4 main affirmations:
1. The classes of learning hypotheses have a VC-dimension upper-bounded by polynomial in H.
For all the problems in the family, there exists a hypothesis with low rate of errors.
3. A sufficiently low error rate implies a perfect accuracy on the predicted action to reach when
sf = 1.
4. Set the last three points together to entail the Lemma.
We pose 9t as the current state, sh the state at the end of the trajectory after observing st. Thus, the Icarnod function takes as input the vector (concatenation of the real parts of the states without the time steps).
SH
1. For a 1, at any time step, the class of hypotheses is the union of O(H) sets of linear functions over real-valued variable composed with a threshold. Those linear functions with a threshold have thus VC- dimension 2. Using Proposition A.4 we infer that, for any time step, the VC-dimension of our hypothesis class in Ollog H)).
2. Take the hypothesis that selects the variable batt and uses the linear identity function composed with a threshold 1 (x) b.u,t > 0).
Both sides of the environment (s or 1) have 1/2 probability. Since all the samples on the right- hand dynamics are correctly predicted by this hypothesis and the samples on the left-hand side have 1/2 probability to have either action, this hypothesis has average error rate of 1/4 the distribution induced by ".
19

---

Published in Transactions on Machine Learning Research (03/2025)
3. For all the possible feature selections, there is finite set of possible inputs, for example, {0,1} for feature 8H buu, or {0} for feature st sb.d.,, Conditioned on si = these inputs all have a constant probability of being sampled by =², thus the probability is independent of H and b the family parameters. We note the minimum on these probabilities Pmin
input which is thus also independent of the family parameters H and b.
Similarly, we note Pminu the minimal non-zero probability under n² of any of the two actions conditioned on the selected feature from a state in the right-hand dynamics.
Suppose that the error rate under the distribution induced by n of hypothesis h for the goal-conditioned prediction problem is +/1+e. e. If E < 1/2 paput output then the hypothesis does not make any errors in the right-hand dynamies. By contradiction, suppose that it does make mistake on a pair of input-oulpul, then take the value of the imput of the variable selected by the hypothesis. There is at least 1/2 Pintu samples with that input and Pmin Pmit proportion of them with the same output. The hypothesis will thus make a mistake on a set of inputs of probability at least 1/2 input Pmmin under Th on the right-hand dynamics. To which we have to add a 1/2 error rate on the trajectories on the left-hand dynamics that have probability 1/2.
4. To gencralize the result to all the time steps at the same time, we use union bound over the probability of failure of each time step.
Using Proposition A.5 and the affirmations just proven, with any constant pinpat gostgaa /2 and 8 = 6/8, there exists m H. 5) O(log H 8) such that the algorithm will output a hypothesis which makes no mistake on the right-hand dynamics.
Definition A.7. A deterministic armed-bandit problem is composed of a finite set of arms A and a function f : AA - [0, 1] which associates an arm to a deterministic reward.
Proposition A.8. Let be a fomily of deterministic armeid-bandil problems defined by A E N and S A. The determénástic armed- armed-bandit problem defined by A and i has A arms, the arm i gives a reward of 1, and the others give reward of O.
For any randomized algorithm that tries to identify the arm with the maximal associated reward with of A) calls to the reward associating function, there erists an A large enough and a such that the algorithm fails with probability at least 1/3 on the problem defined by A and i-
Proof. By contradiction, let's suppose that there exists randomized algorithm Alg that solves any problem in the family with probability at least 1- 8 for some E (0, 1) using K E o(A) samples. Let us note R the random variable following some probability distribution R upon which the algorithm depends, p the problem in input that it solves, and Alg(p,r) the output of the algorithm with p and in input. For any A, let U(A) be the uniform probability distribution upon {l,..., A} and pp- the bandit problem defined by A and i We have for any A
R = (`) 2 1-
(2)
Which implies
(AllE-- i1) 2 6. 5.
(3)
There must exist some which performs at least as well as the mean. Thus there exists a deterministic algorithm Alg, such that Ex- (Alg, 1 8.
We suppose w.L.o.g. that this algorithm uses its K E o(4) tries in the set of the K first arms. Then 7 it only receives 0 rewards and must guess the best arm with no information for the A - K left untested arms. Thus the deterministic algorithm has a probability of failure lower bounded by
with probability 1 1- K
K
- A-K
4
Since K E oA),, there exists A large enough such that this quantity is larger than 8. Thus we have a contradiction.
20

---

Published in Transactions on Machine Learning Research (03/2025)
A.1 Domination result
Here derive from Theorem
4.1 result the domination of black-box dynamics RL methods.
We define u(π, m) (a (o Ei= re] the expected cumulative reward of some policy я on RL problem m with associated operator P. Additionally, we define U'A, m) the average expected cumulative reward of (randomized) RL method on RL problem m. More formally, with i the (random) output of A on problem m, (A, m) Egg (o(z,m))
Corollary A.9. For any RL method A taking at most polynomial time in the horizon of the problem and satisfying Definition 3.2 there erists an RL method that takes at most polynomial time in the horizon and 3/4 with e E 10, such that
1. For any RL problem m, UAA m) S (UB m) + +,;
2. There erists RL problem such that (A, m) S SU(Bm)) m) 1/12.
Conversely, there exists some e E (0,1) and an RL method B taking at most polynomial time in the horizon of the problem such that there does not exist melhod salisfying Definition 3.2 and that for aney RT. problem m satisfies U(B, m) < m) +
Proof. For any RL method A satisfying the conditions of the statement, construct the RL method B per- forming the following computations for an RL problem horizon H:
1. Find policy aGe by executing Algorithm with parameters = and N sufficiently large to have maximal failure probability of 60 1/24 for problems in the family in the proof of Theorem 4. with horizon H.
2. Evaluate the performance of TGC with an accuracy of min 1/20} with success probability of at least - 6/2 with = min(f//n1 1/24).
3. Execute method A on the RL problem, take output policy JA.
4. Evaluate the performance of RA with an accuracy of min min(+/4, 1/20} with a success probability of at least 1 - 6/2 with = min(s/2n, 1/23.
5. Return the policy with the largest estimated performance, call it TB-
Step 1 takes polynomial time in the relevant quantities, we refer the proof of Theorem 4.1 efficient by the condition method A. Steps 2 and 4 be performed in polynomial time in the relevant quantities using Hoeffding's inequality. Thus the whole method is efficient (polynomial in the horizon and 1/c).
Step also
For the first claim, consider m an input problem. By construction the policy returned by method B has expected cumulative rewards at least of max{u(TGes m), ((TA,))) - s/2 with probability - 8. Thus we have the following lower-bound on the performance
u(TB. m)
2 (1 - ( momaxfu(TGC.NO) m), uLTAA m)} 1/2) 5-0
2 (1 ()((TA,))))) m) -/2)
u(TTA, m) Ōu((TA, m) + 80/2 6/2
(4)
u(TTA, m) - 811 1/2
u c
We used the fact that the rewards are constrained in the interval [0, 1] and thus the expected cumulative rewards upper-bounded by H and lower-bounded by 0.
21

---

Published in Transactions on Machine Learning Research (03/2025)
Since the probability distribution of na produced in method B is the same the output of method A, we have
((Bm))= 2 Exg [u( L (M(AA(AA)) - U m))
(5)
This concludes the proof of the first claim.
For the second claim, method satisfies Definition 3.2 and has computational complexity o(2#). Thus method A satisfies the conditions of the second claim in Theorem 4.1 From the proof of Theorem 4.1 we can extract the fact that ((A, m) at most 9/6 for some RL problem in the family we defined
While, by construction #eo outputs an optimal policy with probability 1 - dg- Morcover, if ToC is optimal, it is chosen as output with probability at least - since the asked accuracy 1/20 is below half the difference expected returns for TEC and T (lower-bouneed by 1/12).
Thus the expected returns of πв satisfies, taking into account that for the problems in the family is the optimal expected return achievable,
u( m) 2 - 5 50) +6)+
60)
(6)
1 - 1/12.
Thus,
m) 1/122 Enzlu [u m)] 2 - 1-11--11600 U(A
(7)
The converse and last statement is a direct consequence of Theorem 4.1 proof by taking Algorithm B.
g as
Parallel result with a different assumption
This section presents another formalism than the main text, this formalism is closer to the paper of Sun et al. (2019). We derive parallel version of our theoretical result this new formalism. Then, we discuss the advantages and inconveniences of this formalism in contrast the one used in our main text.
This section aims to clarify the characteristics of different formalization choices. A second goal is to show that the ideas presented in this paper hold in the two formalisms; thus, their consequences are broader than what the main text formally presents.
B.1 The formalism and result of Sun et al. (2019)
We provide here briefly the result of Sun al. 2019
The following definition of a model-free method is given by Sun et al. 2019
Definition B.1. Model-free algorithm, Sun et al. (2019). Given (finite) function class 9 (S x A) - RR define the G-profile Φg RI (Al by (g(x)) 19(a, a))gE9..E4 An RL method model-free using G if it accesses x exclusively through dg for all during its entire execution.
The definition of a model-free method depends on a set of functions G. For their theorem, they assume G (P(M), where OP stands for optimal planning, it is defined as the set of optimal Q-functions and policy functions for given family of RL problems M. In other words, the set OP(M) contains any policy and Q-function that is optimal for some problem in M.
Depending on the family M, this assumption implies a barrier to the information that can go from the encountered states to the model-free method. This loss of information allows them to prove their theorem on the gap in statistical complexity between a model-based method and model-free RI. methods.
The work of Sun et al. (2099) proves that there exists family of RL problems M such that:
TTee method A has than 2/3 probability produce an optimal sequence actions the right-hand dynamics. Taking into account. the sides of the dynamics, the average expected cumulative rewards thus 1/2 1/2 2/3 5/6
22

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 4 Env: an interface linked to RL problem defined by the transition operator P and G-profile 0g (Definition B.1. The interface is set of functions with an internal state. The interface has access to an initialized encoder encoder/decoder /dcoder of pointers and states as defined in Algorithm
function Env Env__nitt [_]
80 Po Su --ncode_state(s)
output 80, (80) function Env_steple a)
4- decode 1rroode_pointe((5
if is not terminal then ry,'~~ Pr, a) s' +- encode *+enoode_state(s] state(s') output 8" (s')') else if 8 is terminal then output 1
function Env Env_eval statoss FF)
output (5())
function Env_ cnc__cccs(s)
output encode encode_state(s)
These problems are intractable the horizon for RL methods that are model-free using OP(M) following Definition B.1
These problems are solved efficiently in the horizon by an RL method that takes the family M as input.
B.2 An extension of the formalism
We extend their definition of a model-free method with an interface. Similarly to the first interface defined in Algorithm 2 this interface uses the encoder-decoder (Algorithm I to hide the content of states while still allowing their manipulation. Thus, as for the previously defined interface, the methods can generate transitions and do local planning, such as tree-search.
Definition B.2. A black-box dynamics RT. method interacts only with the interface defined in Algorithm 4 linked with the RL problem to solve and G = OP(M for M a given set of problems containing the problem to solve.
B.3 New result
We derive new version of our theorem in this formalism. The structure of the result is the same: we provide a family of RL problems which are both hard to solve for the class of RL methods that satisfies our definition, but is efficiently solved by another algorithm.
First, we define Algorithm 5 This method is similar to Algorithm with two differences. One, the goal-state can be anywhere in the trajectory, while Algorithm 3 required it one of the final states. Two, the reward that decides the goal-state is not gained when entering the state, but when leaving it.
These changes are made to adapt to the new family of problems that will be used in the proof. Notice that Algorithms 3 and both simply assign a state that appeared next to a high reward as goal to reach.
Theorem B.3. There crists fomily M of RL problems such that
For any problem in the fomily and 8 E (0, 1), with probability at least (over the sampled trajec- tories), Algorithm 6 outputs an optimal policy with number of samples and number of operotions upper bounded by polynomial in horizon H and 1/8.
23

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 5 A second goal-conditioned algorithun.
Paramcters: N: number of samples, a: parameter the learning algorithm (number of active features)
Input: P: the operator corresponding to the RL problem to solve
D - 0 for - 1....No. do
D t D 4o, To: $1, , ~ p
9T - arg 1ggmaxppe PT s.t. (..., ST, QT, ST: .T..... E E for E (O....., - do
D3 f' result of the optimization program with dataset oo and parameter output x(als)) = (()
( (r) (..., 0t, ,t,...,, ST. .
Por any algorithm salisfying Defivitionn B. with the family M and using o(2 calls the interface (Algorithm (4, there erists a problem in the family for which outputs suboptimal policy with probability at least 2/3.
Proof. The family of RL problems we construct is the same as for the proof of Theorem last steps of the dynamics. An example of a problem in the family is represented in Figure
except in the
We describe the changes comparison with the previous family of RL problems.
The rewards before entering the final states of the previous dynamics are all set zero. A new step added at the end of the dynamics where all states and actions lead to the same state full of zeros. The unique state that got reward in the previous dynamics, leads now to unitary reward in this last transition (the other states still lead to no reward).
For the first claim, the Algorithm 5 solves efficiently in the horizon the RL problems the family, since the proof of Theorem 4.1 applies straightforwardyy in this case. With high probability, the same goal state will be selected, and the same policy will then be learned.
We now prove the second claim. The left-hand dynamics is independent of b the hidden binary word defining the RL problem. Thus, the only information the method will receive is from the right-hand dynamics. This dynamics is the same as the problems in the work of Sun et al. (2019) and their proof applies.
We repeat the clements of the proof here for completeness.
For an algorithm satisfying Definition B.2 the possible right-hand dynamics are equivalent to the family of problems defined in Proposition A.8 with a set of 2 actions, and the proposition implies exactly the claim to prove.
We prove the equivalence. First, we note that any states encountered before the / = H - 2 time step provide no information on the hidden binary word 6. The same holds for the last state. Such that only the states at time step / = H - 1 are relevant to discover b.
Let us describe dg with g = OP(M), applied on these states. For a fixed horizon H, there exists as many different dynamics M, as the number of possible binary words b. Each of these dynamics entails both an optimal Q-value function and an optimal policy function. The outputs of policy functions contain no information since the dynamics are independent of the action at time step t H -1. 1. The outputs of Qavalue functions will evaluate to zero for all couples of states and actions at time step t = H 1, except for the unique state leading to a reward, for which they will all evaluate to one.
Such that the output of (s(s) will always be only zeros for all suboptimal states encountered at time step H 2, and only be different for the unique rewarding state. All the suboptimal states will thus be indistinguishable for method satisfying Definition B.2 This is equivalent the armed bandit problem described in Proposition A.8
24

---

Published in Transactions on Machine Learning Research (03/2025)
00
010.0 0'0
1/2
1/2
0.00 110.00
100,0 0000
0'0'
0 20000 0'0
0 0,0,
0
0'0"
2 0'00
00 0,00000000
00 300000000
010.1-00001
0 1,0 000
3/ 3
11 40000 0000
4 10.00.00
10
00.00.0000 0
4.000 rr.
0
4/0.0, 1
+1
0 5,0,0 0'00
Figure 4: Example of the family of RL problems for horizon 5 and hidden binary word 01.
B.4 Discussion
The result obtained this appendix is very similar to the one presented in the main text. This new parallel version of our thcoretical result offers a new trado-off between the assumption made and the conclusion. We explain this trade-off.
We compare Definition B.2 and linked Theorem B.3 of this appendix section with Definition 3.2 and linked Theorem 4.1 presented in the main text.
As we explain and show the main text and Appendix the Definition covers many common RL methods.
In contrast, the original assumption of Sun et al. 2019 (Definition B.1 and the discussion below it) and our extension in Definition B.2 pose conditions that do not to fit. straightforwardly classical RL methods.
25

---

Published in Transactions on Machine Learning Research (03/2025)
These assumptions rely looking states through set of functions defined by OP(M), the set of optimal O-functions and policy functions for family M of RI. problems. However, classical algorithms will use and evaluate encountered states using functions that cannot be linked to any arbitrary set of problems M. For example, an algorithm could evaluate states with lincar value functions but OP(M) might not contain these depending on the lamily M chosen.
Despite this problem, the assumption of Sun et al. (2019) and of this appendix still seemn relevant. It seems counter-intuitive that Q-learning methods needs to rely sub-optimal Q-value functions to solve problem.
If one accepts this argument, there is a gain on what can be proved. We believe that the family of RL problems used in the proof of Theorem B.3 are easier lo generalize than the ones in the proof of Theorem
4.1 The family of problems defined in this appendix sets the rewards after the states of interest not only just before, as pictured in Figure | This allows possible generalization, which to extend the dynamics beyond the current last states and delay the gain in rewards. Thus, the goal-state used in our proof could become an intermediary sub- sub-goal in a larger dynamics.
C Comparison with the work of Sun et al. (2019)
The result in the main text and its parallel version in the previous section differ in two main ways from the result of Sun et al. (2019).
First, we redefine and broaden the class of methods with a limitation. Instead of proving limitation on model-free methods only, we broaden the result of intractability to some methods that are usually considered model-based (such as AlphaZero). We obtain this by analyzing the computational complexity instead of the statistical complexity of the methods and by using an interface with an encoder-docoder of states. The interface allows more flexibility in the interactions between the method and the problem at hand, allowing to abstract larger class of methods. In particular, the interface allows to generate different potential future trajectories from given state, something which is essential for several planning algorithms with a known or learned model of the dynamics.
Our second contribution with respect to the result Sun et al. 2019 is that our family of problems can be efficiently solved without strong specific priors about it. In contrast, their result crucially relies on an a priori known goal-state to reach. They encode this knowledge into a model-based method to its advantage and show that their model-free methods cannot. leverage that prior information. In general, such knowledge cannot be assumed to be known in practice and impairs the practical applicability and generality of their claim.
Whereas in our result, no goal-state needs to be known a priori but it is discovered autonomously from obtained rewards. Thus, our result applies without needing to know and engineer strong a priori knowledge into an algorithm to get an advantage.
This leads to a new claim specific to our work: numerous classical RL methods of the literature have fundamental limitation on problems that should be solvable by efficient general-purpose RL method.
D Classical RL methods implemented with the interface
In this Appendix, reformulate common RL methods to use the interface defined in m2 instead of directly interacting with the RI problem dynamics. We thus demonstrate that these methods can be cast in the conditions of Definition and suffer an upper bound on their performance provided by Theorem 4.
To clarify the presentation, we use methods as simplified as possible. For example, we only work with one-step RL methods, which use only onc-step transition, (s, a, s"),, instcad of longer sequences to make updates. The presented formalism can however be extended to include these multi-step methods. Our results are robust to such changes.
26

---

Published in Transactions on Machine Learning Research (03/2025)
Neural network initialization refers to the initialization of multilayer perceptron (MLP), a classical neural network architecture that composes iteratively linear operators and non-linear point-wise activation fune- tions. We keep implicit the input dimension, output dimension, and number of layers with their respective numbers of hidden units.
In Algorithm G we define the fitted Q-iteration algorithm with Deep Learning, a common variant of model- free deep Q-learning methods Riedmiller (2005). The algorithm trains at each iteration a new Q-function based the Bellman equation
new dataset and the previously trained Q-function.
In Algorithm 7 we translate the original algorithm to use the interface defined in Algorithm 2 As explained in the main text, calls to draw trajectories from the RL problem are replaced by calls to Env _ssp..... Instead of directly manipulating states and updating the neural networks, the call to Env step uses function F. to do these computations. The function F is used to learn and evaluate the neural networks (Q-value functions).
Following the argument formalized Appendix E about the symmetries existing neural networks training by gradient descent, the functions defined in J practically satisfy the symmelry condition of Definition 3.2
We also implement an Actor-Critic method, defined in Algorithm g with the interface in Algorithm This demonstrates the use of value and policy functions.
In Algorithm T0 we implement a local planning tree search procedure relying on the capacity of the interface
to generate transitions at any given state.
It is possible to combine tree search and model-free methods to fit methods that leverage feedback from results of tree search procedures to train neural networks Feinberg al. (2018), then possibly improve the tree search procedure with these neural networks in a virtuous cycle Anthony et al. (2017) Silver et al. (2017).
We fit. the AlphaZero algorithm to our Definition 3.2 in Algorithms described in Algorithuns II and 12
13 and 14 the initial algorithm is
The original algorithm was described for 2 players zero-sum deterministic games with the use of self self-play, but is straightforwardly appliable to deterministic RL problems. In addition, note the following minor modifications with respect to the original AlphaZero described in Silver et al. 2016 2017):
We evaluate the neural networks at cach new node in the scarch-tree that is created, and not only at each leaf-node expanded. This incurs only fixed factor more computations.
Instead of using the final return of a full trajectory to learn the value function, we use one-step temporal differences. We do this because our Definition 3.2 does not support multi-steps temporal difference in the presented form. We note that multi-steps methods could be added to the formalism but at the cost of readability.
To simplify the algorithm, we describe an online training version. We apply stochastic gradient descent directly with each new data sample, and do not construct datasets to leverage experience replay.
E Symmetries in neural networks learning
We provide here a formal argument that classical neural network training procedures satisfy the condition in Definition 3.2 put function F.
We prove that the distribution of outputted functions by gradient descent procedure respects such symmetry.
In Definition we construct a symmetry condition that will help us to state and to prove our result. In Theorem E.2 we state the main result of this section on the symmetry of the learning procodure. Corollary restate the Theorem, but in a form which can directly be compared with the condition on JF stated in
Definition 3.2
27

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 6 Fitted Q-iteration (with e-greedy exploration)
Paramcters: H: horizon of the MDP, S: state space, A: action space, K: number of itcrations, 7) > 0:
scalar factor for gradient descent, I: number of samples by iteration (divisible by H), exploration parameter Input: P: the operator corresponding to the MDP to solve
Initialize a neural network Qo : + ||
Te (a) 8, Q) < (1 ea = arg max Q(s, + 4/21(a = 0) + (a/2
for + ,,...,, K do
Q Q+
Initialize a neural network Qa for i ......., I/H do s Po for t + 0... D...H-- - do
a ~ (. 9, Q)
r t (ry s, a)
0 Vo (Q((s.)) max a()
8 s
x(a| s) To (al s, Qe)
output π
Algorithm 7 Fitted Q-iteration implemented with the interface defined in Algorithm 2 The function chunk(D, 1) partitions the data sequence D into contiguous subsequences of length 1 until there is less than clements left which are put in the last subsequence.
Parameters: H: horizon of the MDP, S: state space, A: action space, K: number of iterations, >> 0: scalar factor for gradient descent, I: number of samples by iteration, exploration paramcter Input: Env: the MDP interface with its methods defined in Algorithm
n. (al Q.) + (1 () arg max (a(a)) + s/21(a 0) 1/2 =)
function learnQ(s, D)
Initialize a neural network Qo: + RRAI Ba....Dn-1yy 1, + chunk D, for (sa. Td, 2x2 + Dn-1 do
b Only use Dn-1 with the most recently fixed Q-values
- 0 - Q0(ss, aa) - Td max (
output [Q0(s, a) RRAA learnQ
for +- l,..., K I/H do
8,Q, t- Env init(F) for 1 + 0,..., H - do
a a~ (al( r, +- Env stepst 0, F)
[[a]s) 1(a arg max Env_eval Lvaleevsaaaaaaaael state(s, learnQ))
output π
For the clarity of the exposition, we will abusively refer to the probability of function instcad of the probability of events in the related implicit o-algebra.
Definition E.1. Symmetry condition.
Let I be a function from a sequence of data points in (R" x RRN for some natural number N, to a set of distributions over functions A([R" + I.).
For any sequence ((xo, .o).... of data points and for any permutation of the coordinates p over F. (Definition 3.1 define dp ((p(2o), vo), (p(#)).11)...
28

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 8 Deep Policy Gradient with Value function learning (Actor-Critic)
Paramcters: H: the horizon the MDP, S: state space, A: action space, K: number of sampled trajectories, > 0: scalar lactor for gradient descent, I: number of iterations by initialization of the value function (should be divisible by H)
Input: P: the operator corresponding to the MDP to solve Initialize a neural network To, : S - ((A) Initialize a neural network Vo, + for +-1 1... do if k И mod I = then V Vo, Initialize neural network Vo, S R
8 +- Po for t t O...., H do
am TT, [a] 8)
r, Pry s a)
81 - 81 7(( + V(s')) Vo, log no, (a|
0g - 02 nV,, (e) - -Vs)
$ st s'
output T
Algorithm 9 Deep Policy Gradient with Value function learning AActor-Critic) implemented with the interface defined in Algorithm 2 The function chunk D, I) partitions the data sequence D into contiguous subsequences of length I until there is less than I elements left which are put in the last subsequence. We simplify the learning of V, the value function, following the discussion in Section
Parameters: H: horizon of the MDP, S: state space, A: action space, K: number of sampled trajectories, > O: scalar factor for gradient descent, I: number of iterations by initialization of the value function
Input: Env: the MDP interface with its methods defined in Algorithm function learning VandT D)
Initialize neural network Vo, S -+ R
DI...., Dn-1, Dn +- chunk(D) D, I) for as (Va, TT) t D do
82 + 82 Ve. e., [Ve, (s) Initialize a neural network To, S + (= ((4))
V
for (s, (a, r, VVr.TT)) + do
+ 0 7/( + V Ve, log ne, (a|s)
output (Vo, (s), to, (s))
F + learningVands for 4- 1... do 5, (V,,, TT) f- Env init(F) for t + 0...
do
n. (a)
5,5, (V.: Tz) +- Env Env_step(3,, a, F)
T (a] s) + [V πT) + Env__val state(s, F); output [a)
output π
The function L satisfics the symmotry condition if, for any permutation of the coordinates p. we have L(d) = L(dp) pt other words, for any function h R" - RR the output with must give the same probability on as the output with dp on h hop.
29

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 10 Tree-search implementation using the interface defined in Algorithm This algorithm can be combined with the other methods presented, to use value function estimates instead of rewards for example. Paramcters: H: horizon of the MDP, A: action space, Hş 0: scarch horizon of the tree
Input: Env: the MDP interface with its methods defined in Algorithm function TREE SEARCU($, h)
if then output 0
for a E A do
r, r, - Env_stepps, a,
if r then
output a, 1
else
d' R Tree search(s'' h 1)
if R = then
output a, 1
output
function TREE SEARCH((:)
0,7 <
min - -]))
output
* (al < Tree search((s)
output π
Theorem E.2. The output of the randomized Algorithu 15 dataset, follows a distribution defined by the dataset. The function between the dataset and the distribution of learned functions respects the symmetry condition.
which produces a learned function given
Proof. We prove by induction that for any permutation of the coordinates both the process that constructs the linear operator represented by and the processes that produce all the other functions of the input in the neural networks (output, gradients) satisfy the symmetry condition.
Let P be the permutation matrix corresponding to p.
At initialization, the symmetry condition is satisfied everywhere. The matrix W is probable as W p-1 and is independent of the dataset. All the other functions computed in the neural network depend on the input only through the lincar operator that satisfies the condition, such that they also satisfy the symmetry condition.
Now we look the updates. Let g be the gradient the output of the linear operator for some input Then the update of W is
W ngz"..
(8)
On the transformed dataset, with WP-1 the matrix of the linear operator, Px the new input, and h the new gradient, the update becomes
WP-1 - - -
(9)
which reduces to (W- (Wnhh=")P-1 By the inductive hypothesis, we know that the processes that produce h respect the symmetry condition, thus the gradient h is sampled from the same distribution g. Also, by the inductive hypothesis, the previous WP-1 is as probable the previous W under their respective distributions. Consequently, the updated W is as probable as the updated WP-!
Similarly to the initialization, the processes that produce the rest. of the network functions of the input respect the symmetry condition because they depend on the input only through the output of the linear operator since the start of the algorithm.
30

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 11 AlphaZero planning functions.
Parameters: H: the horizon of the MDP, S: state space, A: action space Input: P: the operator corresponding to the deterministic MDP to solve Node: N, W, Q: P, v, children, parent, parent_action, leaf, function PLANNING h, ma, Va,, C,T)
nodes t
nodes.append( Nodo(O<A,o) A 100.00.m..l.. mulll, mmwl mull, mull, Truc.h))
for 1 do
last Sedee-SSeeec(ooddss c)
node, no, Vo,))
Backup(last_nnon cecis__oddeppee pareet, last_ nose.)
output root mode.N[a] / node.N[a|1/s
function SELECT(node, c)
if lede node.h equal H then output node
<- arg n node. node.Q[a] + node. Enees Ne node.N(b]
1+node.N(a)
output sedecctnnde.cciiddreeeiiill
function ExPAND(node, To, Vo,)
node.leafe- False
if node.h equal H then stop node.children + for E do r,s't Payn (r, (r,s'|node.ss, a)
v'+ Vo' wode.cilldenappenn(Maaeee
,uullyy', mull, node.hode.h+-)
node.Pt- Te, (node.s)
output node.children
function BACKUP(node, a, v) if node is mull then
stop
node.N(ct < noae.N(()++ +1
node. W[a] f node. W[a]= +
node. Q[a] + node. W[al/Wade.WW
beokkup/oode.pareeee parent action, v)
Corollary E.3. The expectation of the distribution of the output of nearal networks applied on some imput RR produced by randomised Algorithm 15 for some sequence of points d can written as f(z, ((0o, vo)...)) for some function that is invariant to a permutation of the coordinates applied to z and To....
Proof. By construction, f exists and is simply the function representing the process producing the distri- bution learned functions composed with the expectation of their evaluations. Since the distribution of Icarned functions respects the symmetry condition by Theorem E.2 we know that for any permutation of the coordinates p, we have Enn-Alg(() [2]] Enn-Alg(d (n((())) where is the neural network trained by the am Alg.
31

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 12 AlphaZero.
Parameters: H: the horizon of the MDP, S: state space, A: action space, 1: number of iterations of the procedure, K: number of expansions in the scarch, 0: scalar factor for gradicnt descent, temperature for action selection, exploration parameter of the search
Input: P: the operator corresponding to the deterministic MDP to solve
Initialize a neural network TØ, : ((4) Tnitialize neural network Voz 8 + IR for i +-+ 1...I do 1--10 Po for + O.... H - do
+ planning(s h, To, Vo,, T)
01 + 81 + VVe. EmEAP(a) log To, (al
~~ p r, Payn(r, s' s' a)
02 + 02 - (s) r ivs''
s' s'
7 {a 8) + Ip + planning(s, (8, s.h, To Voz, K,c, T); output
output π
F A planning method
In this appendix, we describe the planning method introduced in the numerical experiments section of the main text.
The method follows these steps:
1. Sample an initial dataset of trajectories using a uniform policy.
Learn a model of the forward dynamics by fitting the dataset with Decisions Trees regreseegyysyvely assuming a deterministic transition dynamics. If a Iearned model of the dynamics already existed from previous iterations combine the previously learned and new Decision Trees predicting rewards to produce pessimistic prediction of obtained rewards. In other words, the method combines additively the constraints predicting zero rewards in the trees.
3. Sample trajectories following policy that plans each step using the learned model of the dynamics. The planning is done by solving a Mixed-Integar Lincar Programming (MILP) optimization problem. The main variables in this program represent the future trajectory (states, actions, rewards), there are also auxiliary variables that help encode the constraints coming from the learned dynamics. The constraints of the MILP are given by: the current state and the model of the dynamics defined by Decision Trees. The objective is to maximize the total return of the trajectory. To solve the MILP, use the off-the-shelf solver Gurobi Gurobi Optimization, LLC (2023)
4. If the sampled trajectories reach reach a threshold in average returns, the method outputs the policy that plans each action by solving a MILP encoding the learned dynamics (as in the last stop). Elsc, the performance not sufficient, add the trajectories to the dat dataset and the method goes back step
An algorithmic description of the method that represents the loops and branching statements more clearly is provided in Algorithm 16
The method requires a sufficiently deterministic dynamics. The dynamics should also be simple enough for Decision Trees to be able to efficiently model it with a datasct of trajectorics produced with uniform policy, followed by low exploration with several trajectories that are promising according the dynamics model. This low exploration comes from the compromise of choosing pessimistic prediction of the rewards.
32

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 13 AlphaZero planning functions implemented with the interface defined in Algorithm 2 Definition 3.2
fitting
Parameters: H: the horizon the MDP, S: state space, A: action space
Input: Env: the MDP interface defined in Algorithm 2
Node: N, W, Q. P, v, 8, children, parent, parent action, leaf, h
function PLANNING F,,
nodes 6 []
(Us, Ts. p) < _nv__val state(s,F)
vodes..ppend(Node((( .04 0 R. mull, mull Tru..
for 1.....K do
last (oooe=-Select(nodes(()) c)
node, F))
Backupplast node.parent, last node.v)
output root_ root_nodc.N[a] rot nodc.N
function (noec if node.leaf node.h equal then output node
<- arg mag node. Q/a] + node. SEa node.N(b] output Select cedecctll)d.. function ExPAND(node,, F)
Honde.N((c
node.leaft- False
if node.h equal H then stop node.children for a E A do
r, Ps) +- Env step(node.3, a, F, append to _d_attta False) aele.children..apedd///
10,00 30, node,, n)1),
output
function Backup(node, a, v) if node is mull then
stop
node.N [[] + node.N(aj]
node. no] <- node. W/a]
node.W[a] +
mode.Q(a) +- mode.W[a]/nodde
Backkup(node.pareeee norenparent action, v)
As for Algorithm 3 this method makes several assumptions about the simplicity of the problems it solves. Similarly, those assumptions are not specific to the problems in this paper, but prevent the method from being general-purpose RI. method. The method only illustrates an algorithmic approach to RL on our problems and shows that these problems are easy to solve.
G Numerical experiments details
We describe the implementation of the different methods test: goal-conditioned method in Algorithm
17 fitted Q-iteration Riedmiller (2005) in Algorithm 18 Proximal Policy Optimization (PPO) Schulman
12 We refer to the previous section for details on the planning method introduced in the numerical experiments section of the main text.
et al. 2017), and AlphaZero Silver et al. (2017) in Algorithm
We test all these algorithms with MLP neural networks. Any state in input to neural network s = (t, x) E S [(t,x) E (o....,H) H} R") will be represented with a onc-hot encoding of the time step t concatenated to the real part
33

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 14 AlphaZero implemented with the interface defined in Algorithm 2 fitting Definition 3.2 Parameters: H: the horizon of the MDP, S: state space, A: action space, 7: number of iterations of the 0: scalar factor for gradicnt descent, temperature
procedure, K: number of expansions in the scarch, for action selection, exploration parameter of the search
Input: Env: the MDP interface with its methods defined in Algorithm function LEARN VANDIT (s; Dip)
Initialize a neural network Ve, -+ R
for (s, (Vo', Tha Ps') D do
8 82 V,, [Ve, (s) r- V
Initialize a neural network no, S + R (1 A(A))
for as a, r, (Vo, P.)) + D do
01 + 01 + Vo, EncA Po (a) log no, (al output (Vo, (s), ne, (s),
p +
F + learnVand77...11
for i 1-1 I do
8, (V.,, ss) +- Eav (F)
for + 0.... -1110 do - planning($, h, r)
a ~
F + learnVand
8, Env step(s, a, F)
xaa|s) () + p + (anginggEE__ncooeefefee s.h, leanVanddr...10).K K,, r) output p(a)]
output π
Algorithm 15 Neural network training for neural network with parameters 0 (W Rmmx O' E RR)) for some n, m., k E N, which is interpreted in (x) qo (Wx) for q that outputs real and is smooth w.r.t. 0' and its input.
Parameters: 1) 0: scalar factor for gradient descent, loss: E x R I: smooth loss function w.r.t its inputs
Input: D: a sequence of couples (x E IRR,,
Initialize and matrix W. The elements of the matrix W are initialized i.id.
for (z, 3) E do 0 с 0 7) Vgloss( (Wa),y)
output nn,-(
Some notations, the function CE A(X) x X - R (Cross-Entropp) computes CE(g, x)) - log q(x) for some set X. The function clip(æ E RR E IR, b R) computes min minxmax(2a a}. b). The method copy copies the object, it allows to fix its state.
The optimizations are performed with bini-batches estimation of the gradient, and AdamW, a regularized version of Adam Loshchilov & Hutter (2017). Hyper-parameter optimization was performed with Bayesian Optimization maximize success probability on problems with horizon H/ 45 for the goal-conditioned algorithm, H 12 for the fitted Q-iteration algorithm, and H = 17 for the PPO algorithm. For AlphaZero, performed coordinate ascent optimization to tune the local search parameters for H 15.
The goal-conditioned algorithm was run with 2 hidden layers of 256 units each, parameter = 1000, 30000 steps of AdamW with learning rate 2 10-2, weight. decay 10-3, and 100 batches.
The fitted Q-iteration algorithm was run with hidden layers of 512 units cach, for K 50 iterations, with I 1000 sampled trajectories by iteration, < 0.2, 1000 steps of AdamW by iteration, learning rate 1 1-10-3 weigh decay 10-2 each 1000 trajectories samples were divided into 20 batches.
34

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 16 A planning algorithm.
Parameters: N: number of initial samples.
Input: P: the transition operator corresponding to the RL problem to solve.
Create dataset D by sampling N trajectories from the uniform policy pr function planning(s, DTs)
Build Mixed-Integer Linear Program (MILP) that maximizes the future rewards given the current state s and the learned dynamics given by Decision Trees DTs.
Solve the mathematical program using an off-tho-shelf MILP solver.
output plan, consisting in a sequence of actions, states and rewards.
while True do
Fit autoregressively Decision Tree classifiers DTs on the trajectories in D. Accumulate previously trained Decision Trees for the reward predictions (pessimistic prediction).
Draw trajectories with P by computing at cach step a plan with planning(s, DTs) and using the planned next. action.
If the computed plans reach sufficient performance threshold break.
Add the sampled trajectories to D.
output a policy that computes a plan each step given the learned dynamics model: planning(-. DTs)
The PPO algorithm was rum with 2 hidden layers of 512 units each, for K 50 iterations, with / 1000 trajectories sampled by iterations, clipping paramcter 0.1, , 10-3 3, 500 steps of AdamW by iteration, learning rate of 2 10-4, weight decay 10 and 10 batches of the sampled trajectories.
The AlphaZero algorithm was run with 2 layers of 256 neurons each, AdamW with learning rate 2-10-3 and weight decay 1 10-3 The algorithm performed the following operation three times: sampling a dataset of 1000 trajectories, then optimize an actor-critic for 30.000 steps with AdamW. For the local search procedure, we fixed a budget of 50 search node per dccision and tuned the e and parameters (see Algorithm 12
We measured that it lakes less than two days with single GPU to reproduce the results provided in the numerical section with only one test by experiment (pair of horizon and method).
Algorithm 17 Neural goal-conditioned algorithm.
Paramcters: S: state space, A: action space, I: number of samples Input: P: the operator corresponding to the MDP to solve
D+ 0 for 1..... do
D+ DU ((5g, ao, To: 81, a1 .......,511. ~ p=")
D D+ { a, sH)l (..., .......... .8. D}. Initialize neural network fo 5 x S - A(A) s.t. (,..,,,81) D.
g arg max,
0 + argmin [D Σ E( ([(fo((s,sH]))
6 output π (als) = fo(als.g)
35

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 18 Fitted Q-iteration
Parameters: H: horizon of the MDP, S: state-space, A: action space, K: number of iterations, I: number of trajectory samples by iteration, e: exploration parameter
Input: P: the operator corresponding to the MDP to solve
(a)ss) + (1 - e) arg max Q(s, a)) + s/21(a 0) + 1/21aa= 1) Initialize a neural network Qo IR [R
D D+ f
for +- 1,...., K do
D' + 0
for + I..... do
D' + D' U {(s0 ao, $1. s1........888 ~ p=:0}
- DU (...s..r..)).................... E D}
Q - (Qp)
0 t arg min [D]
E
[Q((s,a- - max A Q(
(s.a,ns")D
output Q0 (a|
Algorithm 19 Proximal Policy Optimization
Parameters: H: horizon of the MDP, S: state-space, A: action space, K; number of iterations, 1: number of trajectory samples by itcration, clipping paramcter, 8: weight of the entropy regularization Input: P: the operator corresponding to the MDP to solve function PPO loss(s, a, R Ta, n, F)
A < R (s)
Ne, (ala)
7(a(s) output min(r=4, clip(r 1 c, + +cAA + B entropy(To, (-[s))
Initialize neural network ne. S + A(4)
Initialize a neural network Vg, S + RR
for h + 1.....K K do +-- 0 for i +- l...../ 1 do
D DU {(u, ag Po. 81, $1. 8H) p=.
D + ((sE, at,
Ej=t ry)l (..., 01 .)...)) E D}
H--
# +- CopY(TA))
V + copy(Ve.)
0. + arg max e,
Σ
PPO Loss(s,
Los00loss(s a, R Te, n., V)
DD]
(z)
02 f arg min 82
Σ
(Vo, R)2
[
(s,D,
output n0, (a|
36


Reviews:
[{"review_id": "zJVvCCvcYu", "reviewer": "Reviewer_NLQh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I'm am confused about the contribution of that paper. \n\nIt is possible that I missed a fundamental detail and completely misunderstood, but any MDP with a sparse reward will be easier to solve with a smart exploration-based approach. So I don't get the point of the introduced class of MDPs. And I don't get the point of the paper.\n\nAnother important confusion:\nHER does respects the assumptions from def 3.2: just take f(s, D) := f(a | s, g), where f is trained just as described in Algo 15 (which is a gradient descent on a perceptron by the way). So according to Theorem 4.1, even HER should fail. \n\nIn practice it does not, because the assumption of the permutation used to prove Theorem 4.1 is actually incompatible with any classical neural network, which are position-dependent. But like HER, all RL algorithms (DQN, PPO, etc) use such networks and so don't respect the assumption 3.2. And the reason a simple PPO will fail is just because there is no exploration method implemented.\n\nFinally, I found that paper particularly difficult to read, with a lot of weirdly composed sentences, and references to definitions / theorem before introducing them. A lot of introduced algorithms are extremely complexified to finally describe very simple process, like numeroting states for the encoder-decoder.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a formalism that encompasses RL algorithms that use neural networks and a reply buffer. It then shows a class of MDP where a simple random exploration will fail to solve, while smarter exploration (in this case, Hindsight Experience Replay) will easily handle.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I don't think simple changes would improve this paper. \n\nMy advice would be to take a larger look to the exploration in RL literature, and study what are the best existing methods to solving the introduced class of MDPs (not necessarily goal-based, like Direct and Diffuse or Max entropy approaches), compare them and eventually derive a new approach that works best on that particular class of problems.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TB4nZQmFys", "reviewer": "Reviewer_UYVb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The class of methods to which the limitation applies is wide and thus the finding is likely to be of wide interest. The paper is generally written well in the outset, but could be more user friendly in some key aspects (around the encoding of states and construction of the problem which provides the intuition for the main theoretical result.\n\nThe empirical results validate the theoretical finding, and I was unable to find issue with the proof. I do feel that it would be nice to give some sense of how one might go about deciding if a given problem is of the class for which black-box algorithms fail, as I understand it, at the moment, the proof shows the existence of problems for which black-box algorithms are limited, but not general conditions under which problems create the limiting behaviour. I appreciate this may be challenging, and necessitate further work, but some reflection on the feasibility of this would be welcome.\n\nThe other point where I feel some additional clarity would be beneficial is around in which ways the proof of Theorem 4.1 in Appendix A is similar to the proofs of Sun et al. (2019) as stated. I appreciate that in Appendix B, an alternative analysis is presented which connects the two, but the main paper says that the proofs are similar to those of Sun et al. (2019) and it is not clear from Appendix A where (if anywhere) the theoretical novelty may lie.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper highlights a class of RL problems which many popular RL methods fail to solve, while there exist fairly simple methods to solve it efficiently.\n\nTo state this finding, the authors define a class of algorithms which is neither solely model-free or model-based but contains those said to take a 'black-box' view of the dynamics of the underlying MDPs. This concept is formalised by introducing a class of algorithms which can be posed as interacting with the problem through an 'interface' which masks true state transitions. This includes many popular and notable algorithms. Particular attention is given to AlphaZero.\n\nThe most similar work is that of Sun et al. (2019), which also separates classes of algorithm in terms of performance, but the present work differs as it a) encompasses some model-based algorithms within the class which suffers the limitations, and b) the problems in which the limitation is encountered can be specified without strong prior assumptions.\n\nThe paper carefully derives the class suffering the limitation, and gives an existence-based proof of problems such that methods in the class can be out-performed. An empirical example shows that RL algorithms within the class are dramatically outperformed by a planning solver, especially as the problem horizon increases. The paper concludes by identifying methods for which the limitation is not present.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As per discussions above, there are three additions I feel could be made to improve the paper:\n\n1. Granting a bit more detail towards the end of p3 and in the discussion of Fig 2 (p9) to support the reader in understanding the encoding process, and in particular what this looks like for the problem in Fig 2. This is quite a key aspect for a more casual reader to understand and I found I needed to re-read several times to get to grips with things in both cases.\n2. A discussion of the feasibility of theory explaining which problems generate the limitation, as an extension to the result that there exists a family of problems for which the limitation presents itself.\n3. Comments in Appendix A or the main text to explain where the differences in the theoretical contribution there and in the 'similar proofs' of Sun et al. (2019) are.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sgnWuvip2C", "reviewer": "Reviewer_kyzM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- This paper is well presented and organized. \n- The problem is quite interesting, as understanding the limitations of RL methods will help in designing new RL algorithms.\n- The paper presented the connections to the previous work clearly. \n\n### Weaknesses\n- RL generally assumes that the environment is Markovian, where the observed state contains all the necessary information to predict the future state. But in the proposed formulation, states are not directly provided to the RL methods but only partial information about the state is provided.  As a result, the environment are not Markovian for the RL method. In this case, common RL methods do not fit the proposed definition. I would be grateful if the authors could provide explanation about it.\n- The authors argue that the identified limitation is applied to model-free RL methods and some model-based methods treating dynamics models as a black-box. The experimental results in Fig.3 only show that model-free methods fail to solve the problem but lack evaluations of the existing model-based methods. Can the authors explain why you don't consider the model-based baseline in the experiment?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper formulates a novel class of RL methods, containing model-free and model-based RL methods. A limitation of this class is discussed in this paper. The authors provided experimental results to show that such limitations can be solved by using learned dynamics models. \n\nContributions and new knowledge of this paper are:\n- formulating a class of black-box dynamics methods, which assumes that RL algorithms access environment dynamics only by an interface.   \n- identifying a limitation of this class of methods, and providing the corresponding solution.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the Weaknesses part above.", "broader_impact_concerns": "No concerns on the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that the problem studied by this paper is important, did not find any major issue with the proofs and appreciated how the empirical results validate the theoretical findings. Some issues of clarity were already addressed by the authors.

The main issue that remains is on the scope of the class of RL algorithms studied in the paper (Definition 3.2.).
Improving the clarity of this point is crucial to convincingly support the claims of the paper, that are dependent on the scope of this definition.

I would like to stress that the minor revision I'm requesting is an important one: improving clarity, providing more examples, and thoroughly discussing the cases suggested by the reviewers is within reach, but fundamental to make the paper ready for publication.

In particular, I suggest to provide more intuition on why permutation invariance is so important.
Decision: Accept (poster)