An Analysis of Abstracted Model-Based Reinforcement Learning
Authors: Rolf A. N. Starre
Marco Loog
Frans A Oliehoek
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Exploration
state abstraction
model-based reinforcement learning

Abstract: Many methods for Model-based Reinforcement Learning (MBRL) provide guarantees for the accuracy of the Markov decision process (MDP) model they can deliver. At the same time, state abstraction techniques allow for a reduction of the size of an MDP while maintaining a bounded loss with respect to the original problem. It may come as a surprise, therefore, that no such guarantees are available when combining both techniques, i.e., where MBRL merely observes abstract states. Our theoretical analysis shows that abstraction can introduce a dependence between samples collected online (i.e., in the real world), which invalidates most results for MBRL in this setting. Collecting samples using a simulator can avoid this problem. We conclude that we should be careful when applying MBRL methods to abstracted real-world data.

An Analysis of Abstracted Model-Based Reinforcement Learning
Anonymous Author(s)
Affiliation Address
email
Abstract
Many methods for Model-based Reinforcement Learning (MBRL) provide guaran- tees for the accuracy of the Markov decision process (MDP) model they can deliver. At the same time, state abstraction techniques allow for reduction of the size of an MDP while maintaining bounded loss with respect to the original problem. It may come surprise, therefore, that no such guarantees are available when combining both techniques, i.e., where MBRL merely observes abstract states. Our theoretical analysis shows that abstraction samples collected online (i.e., in the real world), which invalidates most results for MBRLs in this setting. Collecting samples using simulator avoid this problem. We conclude that we should be careful when applying MBRL methods abstracted real-world data.
2
6
introduce dependence between
10
Introduction
12
13 When trying to find good solutions to MDPs using Reinforcement Learning (RL) fundamental problem is the exploration-exploitaiie dilemma: when to take actions to obtain more information, 15 and when take actions that maximize reward based on the current knowledge. Tabular MBRL methods have found good ways to deal with this dilemma [7, 28, 14).
14
16
However, MDPs be very large, which can be problematic for these methods. One way to deal 18 with this is to reduce the size of the MDP. State abstractions are one way to do this [17, 1]. We interested in approximate state abstractions since they allow for greater reductions of the MDP, though there is a trade-off with solution quality [1]. Specifically, we assume we have an approximate model similarity abstraction function é [1] that maps states abstract states. The environment returns states s, but the agent receives ((s), )) see Figure This setting, which was considered before
20
21
22
23
[22, 2], what we call Abstracted RL, and is the topic of this paper.
24
Abstracted RL corresponds to RL in a Partially Observable MDP (POMDP), previously de- scribed [5]. well known that policies for POMDPs that only base their action the last observation Φ(8) could be arbitrarily bad [26].
MDP
Agent
26
((8)
27
28
However, when assume that & is approx-
Figure 1: Abstracted RL, the agent observes
30 imate model similarity abstraction [1] this worst
(0s) instead s. Image based on Abel et al. [2]
31 case may not apply: Based on the observed ab-
32 stract states the agent learns an (empirical) abstract model. If we could show that this learned model
33 close to 'abstract MDP' (details in Section 2.2), could give finite-sample guarantees on the
34
performance in the original MDP by combining results from MBRL and abstraction.
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

35
However, in MBRL, to guarantee (with high probability) that the learned model is close to the actual 36 environment model, typical (e.g.. [28, 14]) to use concentration inequalities such as Theorem
37 2 from Weissman et al. [30]. But this theorem relies on independent and identically distributed
38 (i.i.d.) samples for each state-action pair, In this paper, we analyze online collection of such samples
39 in Abstracted RI. and show that they are not independent', which means that most guarantees for
40 existing MBRL methods do not hold in the online Abstracted RL setting."
41 On the positive side, when we have access to simulator, we show how this can be used to collect the data such that the typical MBRL guarantees hold and we can learn an accurate model. We discuss that emulating this in the real world is possible, but extremely sample inefficient, thus highlighting the difficulty of assuming that we would have access to an i.i.d. dataset, as in some earlier works.
42
43
44
45
2
Preliminaries
46
We assume the environment the agent is acting in can be represented by an infinite horizon MDP S, A finite set of actions a transition function T(''ss, a) = Pr(s"|s (s a), R a reward function R(s, a) which gives the reward received when the agent executes action in state 8, and y the discount factor (0 S 7 < 1).
47
M = (8, A, T, r), Where S is finite set of states
A, T
48
49
50
In RL the goal of the agent is to find an optimal policy n² : S + A which maximizes the expectation
51 of the discounted cumulative reward. (T) denotes the expected value of the discounted cumulative
52 reward under policy т starting from state s. Similarly, Q* a) denotes the expected value of the
53
discounted cumulative reward when first taking action from state s and then following policy æ.
54
2.1
Model-Based RL
55
MBRL methods learn a model from the experiences, these are obtained by the agent acting in the MDP. The learned model is usually the empirical model, directly based on the experience the agent obtains [7, 28, 14]. Per state-action pair the agent stores the next-states reached after taking action from state s in sequence Y. Ys,a {s((1), g ..... s((m).. }. We use Y to refer to the collection of
58
57
58
59 all Y. From this the empirical, or learned, model Ty is constructed, that just counts how often we
60
have seen the transition next-state, and normalizes this:
VEEs Ty a) A Σ
10:10 8,0 = =s),
(1)
where } denotes the indicator function of the specified event, i.e., it is 1 if (() 3,0 = s' and 0 otherwise.
81
62
63
To give finite-sample guarantees on the accuracy of the estimate Ty, concentration bounds such as Theorem 2.1 from Weissman et al. [30] are often used, e.g. in Strehl and Littman [28], Jaksch et al. [14]. However, these typically make use of the fact that samples are i.i.d. In most MBRL settings this 65
66 is not a problem under some assumptions, e.g. when the MDP is communicating [25]. In this case due to the Markov property the obtained samples are i.i.d.
67
In general, of course the hope is that with enough samples the learned model Ty becomes accurate.
69 With accurate we mean that the distance between Ty a) and T(-1s, a) will be small, where the distance is measured using the L1 norm, defined as:
ITT (-|s, a) T(-ls, a)ll & [sTr(s'ss - T(s'Is,a))
(2)
S'ES
71 Part of theorem 2.1 from Weissman et al. [30], slightly reworded, then gives guarantee of accuracy:
We also show that samples are not identically distributed, but demonstrate that that problem would be resolvable.
"The reader might be puzzled by this statement, since certain guarantees on the combination of abstraction and RL. are known. This can be explained by the generality of Abstracted RL: in this setting there is a non- stationarity caused by the clustering of states with different dynamics. There is a lot of related work in other abstraction settings (e.g.. state aggregation) where this complication does occur due the particularities of their setting [24, 11, 19. 20. 23, 10]. In section 4 we give details back up our claim for individual papers. 'This is a crucial element in being able to guarantee good performance, where performance can be measured in different ways, e.g. in PAC-MDP& terms [28] or in terms of regret [14]. We focus the model quality.

---

72 Lemma 1 (L1 inequality [30]) Let Y.a = (2),, ..., , be i..dd random variables
73
distributed according to T(-ss,a) a). Then, for all e Pr(([Ty(1ss,a) - T( a)Il 2 S (2 2)e 2)e mm?"
(3)
74 In this way, MBRL can upper bound the probability that the learned model, based on m samples, for
75 a state-action pair (s, a) Ty (-Is, a) will be far away (2 <) from the true model (-|ss,0) a).
The situation is more subtle if the MDP is not communicating, i.c., if there exists $1, 82 S for which 77 there is no deterministic policy that eventually leads from 81 to 82- This can create a dependence between the samples [28]. Intuitively this happens because, if we look at one particular state-action
79 pair (s, a), there might be a transition to state s' such that the probability to return to s is O. Thus would have outcomes of (s, a) would immediately know that at least
outcomes were not state s'. Since as soon as we observe s', we know the agent would not be able to return to state s. Strehl and Littman [28] show that in this setting it still possible to use Lemma an upper bound.
81
82
8s
2.2
State abstraction for given models
In the planning setting, where the model is known a priori, state abstraction can be formulated as a grouping or mapping from ground states to abstract states [18]. This is done with an abstraction function Ø, surjective function that maps from ground states,
85
S. to abstract states ø E S: (()): 5 > S. Here $ is defined as $ = {Ø{*)]s E S.. We use the notation to refer to the abstract space. We slightly overload notation and let both denote an abstract state well the set of
87
89
ground states that map to the abstract state 8, i.e., 8 = {g E S ((g) 8), if E S. The use should
be clear from the context. We define the probability transition to abstract state Pr(s'|s, (s, a) as
81 follows:
Pr( &
Σ T(s S'ES'
(4)
This is very general form of state abstraction, that clusters together states with different dynamics 93 into abstract states. Note that we assume that the given state abstraction deterministically maps states to abstract state. This in contrast to some related work problems with block structure [10], where a Markov state can lead to multiple observations (abstract states in our terminology) that need to be aggregated appropriatcly result in small MDP [4, 10].
95
Approximate model similarity abstraction Many different abstraction criteria exist [17], here we focus on approximate model similarity abstraction [1]. In this abstraction two states can map to the same abstract state if their behavior is similar, i.e., when the reward function and the transitions to 99
97
96
100
abstract states are close. Approximate model-similann
defined as follows:
101
Definition 1. An approximate model similarii abstraction, Prnode. for fixed n, satisfies:
@modee.nn = -model.n (82)
Va [R(81, a) - R(82, a)l S 1)
V VeERa Pr(s'(s1,a) Pr(s' 52, a)l S n.
(5)
102
From now on we will just refer mmodel.n Φ.
103
We note that the abstraction we consider, approximate model-similarity abstraction, is still quite generic. It can cluster together states that have different transition and reward functions. However, in the online Abstracted RL setting, the differences in dynamics can cause a dependence between the samples,
105
will show in detail in section 3. E.g. looking at (8, a), the probability that reach state s' depends both on the probability that we reach a particular state & E 8 and then state from 8.
106
107
Returning to abstraction of given model, it is possible to construct an abstract MDP My, from the model of an MDP M and an abstraction function Φ, where w is an action-specific" weighting function, defined follows:
109
"The action specific weighting function is a more general weighting function than is typically used, e.g. by Li et al. [18). which is not speciffc,,,,,cc, i.e., it only depends on the state s. More formally it is the case where Ve EA, ls w(s a) wo))
3

---

Definition 2. We refer to the weight associated with ground state, s E S, and action, a E A, by 112 w(s,a), a). We have: VeES, aE 0 S w(s a) 1 and Ever(s) w(s', 1.
113 The weighting function can be used to create abstract transition and reward functions, which are 114 weighted average of the ground function. this way, from M, & and any w we can construct an abstract MDP Mw::
116 Definition 3. Given an MDP M, 6, and us M (8, A, Tw,, Ru, 7) is constructed as:
8 = (8()) 8 E 5), A A, 7
(6)
FES AEA R8) = Σ R(s,a))
(7)
SES
3, aEA Tu(6')5,a) = Σ
Σ
w(s,
(5)
(8)
SES S'E
117 An abstract MDP Mw. is just an MDP. This means we can use any planning method we like to find an optimal policy #* for Mw.
118
119
What we are interested in is the performance a policy on the abstract space, when applied on the original problem M. Any policy the abstract space गं can be used in M as follows #(s) = (()()), leading to V* It has been shown that we can upper bound the loss in performance due using an optimal policy for My, Æt in M instead of using the optimal solution for M [8, 1, 29]:
122
123
Lemma 2 (Lemma 4 [29]). An approximate model similarity abstraction (Definition 1). has sub- optimality bounded in m Yaes V*(s) V (s) 2n 21-2:((11-119
124
(1-7))
Abstracted MBRL and the problem of online data collection
125
126
As explained, we are interested in Abstracted RL, where we have an approximate model similarity abstraction function & and an MDP M. The agent acts in M but only observes Ø(s) using abstraction function é, as in Figure 1. This setting can also be seen as a POMDP, where the states are hidden and there is deterministic observation function, settings, we look for a myopic (memoryless) policy. While we know that in general this can lead to arbitrarily bad results [26], in this case the value loss would be bounded in the planning setting by Lemma 2. However, now we assume we are the Abstracted RI. setting, and the result for planning may not hold for the learned model.
128
d(s). However, in contrast to the usual POMDP
130
132
133
134
We assume we know S, A, R, 7, and ø (and thus 5), but do not know the transition function. Since we do not know the transition function we neither simply do planning on M nor we construct an abstract MDP, using Definition 3, and solve that. Instead, we let the agent interact with M but o to let the agent observe dss), instead of s, and build learned (abstract) model from the observations it obtains. We show the general Abstracted MBRL procedure in Algorithm 1.
136
138
The agent collects data for every abstract state-action pair (8, a), which is stored as sequences Vs,a:
139
Ys.a+ : (5(11) (2)
(m)).
140 Similar to before in (1), we construct learned model Ty, now looking at the abstract next-states that were reached:
(8'
8.
1( B.0 = =
(10)
142 If this model would be equal, or close, to the transition function T,, of an abstract MDP M.,, for
143 some valid w, we could upper bound the loss in performance due to applying learned policy म" to M instead of the optimal policy x² [1, 29].
'The assumption that the reward function is known simplities arguments but can be relaxed.

---

145
Algorithm 1 Procedure: Abstracted MBRL
Algorithm 2 COLLECTSAMPLES Online
Input: M, C
Input:
M, ④, c,
Y COLLECTSAMPLESSS
Φ, T,
8
initial state
The sampling results in sequences Ya,as for every pair (8,a):
// The number of samples m is based on the simulator analysis, Theorem 1.
Ya = ((8(1))) ).. ((((())
8/(S||
= 500) (((m)
3((mm
- 3 - -2)-1((k)
for all (3. 5) E S A S do
for all S do
(5'15,
E= 1 3,a =
Y = =[1
end for
end for while min Yaz < m do
A. My = A. A. Tÿ Value Iteration(My) Apply xy to M
3 = o(s)
(3)
8' = Step(s, a)
Y a
end while
Return: Return all Ys,0
146
Our main question the finite-sample model learning guarantees of MBRL algorithms still hold in the Abstracted RL setting?
148
3.1
Online data collection
149
In this section we follow the MBRL method from Algorithm 1, collecting samples online using Algorithm 2. Starting from an imitial state the agent follows a policy я. Instead of observing the
150
151
states s, the agent observes abstract states ((s). see Figure
152 We make two important assumptions order to make analysis possible. We assume that the MDP ergodic [25] and that the policy assigns positive probability to every action in every abstract state. Together this can guarantee that Algorithm 2 can obtain any finite number of samples for every abstract state-action pair within finite time.
154
155
156
Our question is, can we still use Lemma to guarantee that we learn an accurate model?
157
Since we learn an abstract transition model Ty, we want to be able to guarantee that this learned model will be close to the transition model some abstract MDP. To define this transition model, we first look at how the data is collected.
158
159
In the online data collection, sample in Ys,a is drawn when the agent takes action when it is in a ground state 3. Specifically the i-th abstract y-(0) 3,a = s' is drawn from (ground) state 161
182
X 2.0 = s s:
V Pr s,a).
(11)
Let Xa.a = ( denote the sequence of ground states s 3 from which the agent took action
183
164
a. Each ground state gets weight according to how often was sampled from, which we formalize
185 with the weighting function wx: V(S,a),0E3 ax(s,a) = En 1(x = =s}. We use wix to define
166 To analogous to (8):
((E,)), (5'15,a)) Σ wx(s,a) T(s'sss,)).
(12)
'The order of m in Algorithm 2, the number of samples want to collect, is based the analysis of Model-base based Interval Estimation (MBIE) [28].
An ergodic. or recurrent, MDP is MDP where, under every stationary policy, every state is recurrent (i.e., asymptotically every state will be visited infinitely often) [25].
5

---

187 We want to have a concentration inequality to provide bounds on the deviation of the learned model Ty from Tux. we refer this inequality as the abstract LI inequality, similar in form (3):
188
(-|3y a) - -wwx (-15, a)l2 2 c) - 6,
(13)
169
where (-15,, a) is defined according to (10) and Twx according to (12).
170
we could directly obtain i...d. samples from Tux and base our learned model Ty on the obtained samples, then would be able to show that the abstract L1 inequality holds by applying Lemma 1.
172
Since in this case, we would have m ii.d. samples per abstract state-action pair, distributed according to Twx (-15,a) a).
174
However, the samples are not guaranteed to be i.i.d. when the agent follows Algorithm 2 to collect
the samples. Since every sample ( was obtained after taking action from state x = 8 E 8, as
175
(() in (11). These can have different distributions if x 8,a 6,a
176
177
Non Identically Distributed While Lemma I assumes i.i.d. random variables, we show that it also holds when the random variables are independent but not (necessarily) identically distributed.
178
Lemma 3. Let Xs.a
$1."." 8m be sequence of states Y S. ((1), (12)... ,.(mm) be independent random variables distributed according to Pr(11s1, a), .. Pr((1smm (Eqn. 4). Then, for all <> 0,
and let
181
Pr[1ITy a) - -Twx ((3,a)]l: 2 2)) S ((218) 1 mme.
(14)
182
The proof can be found in Appendix B. It mostly follows the proof by Weissman et al. [30], which uses Hoeffding's 's inequality [12] and the union bound [6]. 8 Lemma shows that the fact that Hoeffding's inequality does not need identically distributed data can be carried over to the setting from Lemma 1.
183
184
185
Independence
We may be tempted assume the samples are independent, i.e.,
Vi E()m Pr(Y $1,-" y((m) 5m) Pr(((( = ... P(Y((m) 8m)
(15)
186
however, this may not be the case:
187
Observation 1. When collecting samples online, ie., based on Algorithm 2, the samples cannot be assumed to be independent.
188
189
The following counterexample illustrates this.
To show that the samples may not be indepen- dent, we will give a counterexample. We use the example MDP and abstraction in Figure 2, where we have 4 (ground) states, 3 abstract states and only action. We look at the transition probability from abstract state A, Ty (-IA).
Counterexample
181
0.6
182
0.4
193
194
0.4
195
We will consider two samples and show that for at least one com- bination of 5 and 82 the samples are not independent. Consider 1 = $2 = B. That is, the first two times that we experience a
2
196
0.6
197
198
transition from the abstract state A, end up in B.
Figure 2: Simple MDP, with only action, and abstraction. The small circles are ground states (1,2,3,4). A, B and C are the abstract states. The num- bers along the arrows show (16) the transition probabilities, e.g.
Let state be the starting state. Then we have Pr(Y B) 1r(B = 0.6 and
199
200
(r((((2) A
B)
Σ Pr(P BIF = =2 Pr(D = x)
BES
0 0.6 0.6 + 0.4 0.4 0.52.
(17) P(311) = 0.6.
So then we end up with: Pr(((()) = Pr(( = B) = 0.6 0.52 = 0.321. And for the joint
201
202 probability: PI( B, = B) Pr(P B) PrY BY B) 0.6 0.6
203
0.36.
Hoetfdiings inequality and the union bound can be found in Appendix A.

---

Thus we have that - + =) Pr) B), the samples are not independent. Leading us to the second observation:
205
206
Observation 2. As independence cannot be guaranteed, Lemmas andd 3 cannot be readily applied to show that the abstract LI inequality holds.
207
208
3.2
Simulator data collection
Here we also want to give a guarantee in the form of the abstract LI inequality from (13). While in the previous section we found this was not possible because the samples were dependent, here we assume that we have access to a simulator. To some extent this is not surprising, but to the best of our knowledge, this is the first work that explicitly shows how to combine MBRL and abstraction, using simulator. We assume that this allows to select (or move to) any state and draw sample from its transition function. This we call the independent samples assumption:
210
212
214
215
Assumption (Independent samples). We assume we can obtain independent samples, e.g. for any state-action pair (s, a) we can draw samples directly from its transition finction T(-|s, a).
216
217
In case simulator of the MDP available this is a reasonable assumption. For every (3,0) the simulator sampling procedure (Algorithm 3 in Appendix B) selects prototype zz,a E $ to sample from. We define a weighting function Wi a) that has weight if is the prototype Ts,a and otherwise:
218
219
220
((S.)),EE (z a) A 1
(18)
Then we use this wi to define the abstract transition function Tux according to (8). Tu., (811 a) =
221
EveR T(s'ls= -s,a,a) a). This way the samples that we collect for one pair (5, a) are i.i.d., they are independent because of our assumption of independent samples and identically distributed because sample from the prototype. This means we can use Lemma 1. We show that with the simulator we can combine MBRL and abstraction, and still learn an accurate model, that is, we can guarantee that Ty will be close to Twg with high probability:
222
223
225
227
Theorem 1. Under assumption 1, and following the procedure in Algorithm 1, with the data collection from Algorithm (Appendix B), with inputs [S), A, e and 6. For Ty constructed by the algorithm we have that with probability 1 - 8, the following holds:
228
229
((s,a) (-)5, - Tu., (-18, a)ll S.
(19)
230 By Assumption we can obtain any number of independent samples for each abstract state action pair (5, a). Using Lemma we can then derive the number of samples m that is required for each 232 pair (3, a) such that, after applying a union bound, we obtain the bounds in (19). The full proof can be found in Appendix B.
4 Related work
234
235
There is a lot of work that considers the combination of abstraction with either planning or (online) RL. In lot of these works the dependence of samples that arises in Abstracted RL is not issue due to various assumptions, similarly to how in MBRL dependence of samples is often not an issue because of the Markov property and the assumption that the MDP is communicating [25]. Often
237
239
this is either due the assumption that data has been obtained i.i.d., the specific type of abstraction, or because access to MDP model is assumed.
240
241
One paper that does give a result for the Abstracted RL setting is the work by Abel et al. [2]. They show that in this setting R-MAX [7] no longer maintains its guarantees when paired with any type of state-abstraction function, though their example is specifically for approximate Q-function abstractions. They also show that the expected trajectory of learning agent in constructed abstract MDP (Definition 3) is not the same as in Abstracted RL. Their work makes clear there is a complication when combining MBRL and abstraction, here further investigated the cause of this complication, the dependence between samples.
243
245
247
For planning in constructed abstract MDPs, some main results for exact tate-abstractions come from Li et al. [18] and for approximate state-abstractions from Abel et al. [1]. The results from Abel et al. [1] allow for quantifying upper bound on performance for policies found in constructed
249
7

---

251
abstract MDP, as in section 2.2. Taiga et al. [29] build on this by giving a result for performing RL on top of the constructed abstract MDP. They provide upper bounds for this setting when using MBIE with exploratory bonus (MBIE-EB) [28]. In addition, they give an example to show that in
252
253
254
this combination you cannot guarantee optimal performance in the original MDP. Still, they show
255
that an upper bound on the loss in value can be given.
256
Both Paduraru et al. [24] and Jiang et al. [15] deal with the issue of dependence by making the explicit assumption that samples are obtained i.i.d. Paduraru et al. [24] consider the setting where we are given dataset for continuous domain and then use discretization to aggregate states into abstract states. They then give PAC-style guarantees on the learned abstract model and the value that
257
258
259
260
a policy based on this model can achieve the real MDP. Instead of using the L1 deviation bound from Weissman et al. [30]. Paduraru et al. [24] use a similar bound for i.i.d. samples by Devroye and
261
262
Gyorfi [9], which requires a minimum amount of samples. Another difference is that their results calculate the probability that the model will be r-accurate given fixed dataset. They assume that the
263
264
data has been gathered i.i.d., but our Lemma shows that merely independent data would be enough.
At the same time, our results show that when we collect data online in the Abstracted RL setting, their guarantees will not hold.
266
257
Jiang et al. [15] operate in the abstraction selection setting, where the agent is provided with a set of abstraction functions (state representations). They do not assume that any of the abstraction functions results in Markov model, but they do assume given dataset, with data that was collected i.i.d. They give a bound directly on how accurate the Q-values based on the (implicitly) learned model will be, rather than on the accuracy of the model itself. As we showed, the assumption that the data is i.i.d. not a trivial assumption, since it means the data cannot just have been collected online. They do mention that samples will not be strictly independent if fixed exploration policy is used to collect
268
289
270
272
273
274
data but do not mention what the implications are.
275
There are quite a few other papers in the abstraction selection setting, several of these assume that the given set of state representations contains a Markov model [11, 19, 23]. Hallak et al. [11] give asymptotic guarantees for selecting the correct model and on building an exact MDP model. The assumption that there is an MDP model in the given set of representations is crucial in their analysis since for this 'true model' the samples are i.idd Similarly, both Maillard et al. [19] and Ortner et al. [23] also assume that the given set of state representations contains Markov model. They create an algorithm for which they obtain regret bounds, their analysis also makes use of the Markov representation.
276
277
278
279
280
281
282
283
Other work in the abstraction selection setting does not assume that the set of abstraction functions contains a Markov model [16, 22]. However, Ortner et al. [22] use Theorem 2.1 from Weissman et al. [30] that requires i.i.d. samples, which we have shown here cannot be guaranteed in this setting. Lattimore et al. [16] operate in a setting more general than MDPs, where the dynamics of the true environment depend arbitrarily on a history of actions, rewards, and observations. The agent gets as input a finite set of environments, one of which is the true environment. Since the input includes the full model of each environment, the agent does not have to learn a transition model. Instead, to obtain regret bounds, they directly compare the rewards the agent obtains to the expected rewards of the given environments and eliminate environments that are implausible given the observed rewards.
284
285
206
287
288
289
290
291
282
Another way deal with the issue of dependence is by looking at convergence in the limit [27, 13, 20]. Singh et al. [27] give an asymptotic result for the convergence of Q-learning and TD(0) in MDPs with soft state aggregation. Soft state aggregation means that state 8 belongs to cluster x with
293
294
295
some probability ((x s), this means a state s can belong to several clusters. The absteaabsttattion functions we consider are a special case of this, where each state is part of exactly one abstract state (or cluster). Their result relies on having stationary policy that assigns non-zero probability to every action in every state and the assumption that the MDP ergodic. Together these imply there is a limiting state distribution, and using this they show convergence asymptotically. Our main interest in finite-samples guarantees with policies that change due to exploration, whereas this work gives convergence guarantees in the limit using fixed policy.
296
297
298
299
300
301
302
Hutter [13] gives variety of results focusing on both approximate and exact abstractions in envi-
ronments without MDP assumptions. Several of these are in the planning setting, similar to those of
303
304
Abel et al. [1]. Most relevant for us their Theorem 12, which for online RL shows convergence in the limit of the empirical transition function under weak conditions, e.g. if the abstract process itself
305
8

---

306
is an MDP. Under this condition however the problem reduces to RL in an (abstract) MDP, rather than Abstracted RL.
307
308
Majeed and Hutter [20] build on the work by Hutter [13] and focus on the combination of model- RL and exact abstraction. They show that, under the condition of state uniformity, q-learning can be shown to converge in the limit to the optimal solution. State uniformity means that histories that are grouped together have the same optimal q-values. In contrast to our setting, they look an exact abstraction, extending it to approximate aggregation was left as an open question.
309
310
311
312
Other related work is in the area of MDPs with rich observations block structure [4, 10]. However, in that setting each observation can be generated only from a single hidden state, which means that the issue of non-i.i.d data due to abstraction does not arise. In contrast, in our setting multiple (hidden) states generate the same observation. Azizzadenesheli et al. [4] state their setting can be be aggregated to form small (latent) MDP. But in our case, we do not try to learn the MDP (as it is not small). Du et al. [10] describe
314
316
seen an aggregation problem, where the observations
318
319
that their setting is similar to exact model similarity (or bisimulation), but we focus on approximate
320
model similarity which is what introduces the problems as described here.
5
Discussion
322
When collecting samples online in Abstracted RL, there is a potential dependence between samples, meaning we cannot use the typically used concentration results that assume i.i.d. samples, e.g. Theorem 2.1 from Weissman et al. [30], the empirical Bernstein inequality [3. 21] or the Chernoff' bound. In case the samples are only weakly dependent, it may be that concentration inequalities for (weakly) dependent variables are viable alternative through which we can come to guarantees on the learned model. Alternatively. it may be possible to change the sampling process to ensure independent samples. One way to ensure independent samples is to, as in the simulator setting, select a prototype state and only use the samples collected from this state. Though in this case, we will be discarding information when we reach state E ø that is not the prototype.
323
324
325
328
327
328
329
330
Our assumption on the simulator that relaxed, though it may mean that the procedure takes considerably more time. Consider the case where we cannot just reset the simulator to the state s from which we want to sample, and instead,
go/reset to any state to draw samples from it can be
332
333
334
would behave like the MDP. In this case, we would have to take the right actions to arrive at the state
335
from which we would like sample. Since we assume we do not know T, this may take a long
338
time. This also shows the difficulty of assuming that in the MBRL setting somehow have access to an
337
i.d dataset, as has been assumed in some earlier work [24, 15].
Conclusion
338
339
We analyzed Abstracted RL: the combination of MBRL and state abstraction when the model of the MDP is not available. We have shown that in Abstracted RL samples obtained online cannot be assumed to be independent. Since many current guarantees from MBRL methods rely on this assumption, their guarantees do not hold in this setting. And in fact, no current methods exist that
340
341
342
343
give (correct) snitle quality guarantees for the models learned in this setting. This also means that current results that rely on an i.i.d. assumption cannot be readily transferred to the Abstracted RL setting.
344
345
346
In addition, we show that with a simulator, since we can draw independent samples, it is still possible give guarantees the accuracy of the model. However, having access to simulator may often not be possible. An important step is to see if the MBRL guarantees can be adapted to Abstracted RL for online sample collection.
347
348
319
References
350
351
[1] David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state abstraction. In International Conference Machine Learning, pages 2915-2923, 2016.

---

353
[2] David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. In International Conference on Machine Learning, pages 10-19, 2018.
354
355
[3] Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In International conference on algorithmic learning theory, pages 150-165. Springer, 2007.
357
359
[4] Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning in rich-observation mdps using spectral methods. arXiv preprint 1XX1v90611.03001 2016.
380
361
362
[5] Aijun Bai, Siddharth Srivastava, and Stuart Russell. Markovian state and action abstractions for mdps via hierarchical mets. In IJCAI, pages 3029-3039, 2016.
[6] George Boole. An investigation of the laws of thought: on which are founded the mathematical theories of logic and probabilities. Dover Publications, 1854.
385
366
7 Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, (1022)223,-31, 2002.
367
368
88] Richard Dearden and Craig Boutilier. Abstraction and approximate decision-theoretic planning. Artificial Intelligence, 89(1-2)) 39(1-2):219-283 1997.
370
371
[9] L. Devroye and L. Gyorfi. Nonparametric Density Estimation: The LI View. Wiley Interscience Series in Discrete Mathematics. Wiley, 1985.
372
373
[10] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Muchine Leurning, pages 1665-1674. PMLR, 2019.
375
376
[1]] Assaf Hallak, Dotan Di-Castro, and Shie Mannor. Model selection in markovian processes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 374-382, 2013.
377
378
379
[12] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30 1963.
380
381
[13] Marcus Hutter. Extreme state aggregation beyond markov decision processes. Theoretical Computer Science, 650:73-91, 2016.
382
383
[14] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1533-1100, 2010.
384
[15] Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforce- ment learning. International Conference on Machine Learning, pages 179-188, 2015.
386
387
[66] Tor Lattimore, Marcus Hutter, Peter Sunehag, et al. The comple-co of general rein- forcement learning. In Proceedings of the 30th International Conference on Machine Learning. Journal of Machine Learning Research, 2013.
388
389
380
[17] Lihong Li. A unifying framework for computational reinforcement learning theory. PhD thesis, Rutgers Sniversit-Grraduar School-New Brunswick, 2009.
391
392
[18] Lihong Li, Thomas J Walsh, and Michael L Littman. Towards a unified theory of state abstraction for mdps. In ISAIM, 2006.
394
[19] Odmrric-Ambrym Maillard, Phuong Nguyen, Ronald Ortner, and Daniil Ryabko. Optimal regret bounds for selecting the state representation in reinforcement learning. In International Conference on Machine Learning, pages 543-551. PMLR, 2013.
385
396
397
[20] Sultan Javed Majeed and Mareus Hutter. On q-learning convergence for non-markov decision processes. In IJCAI, pages 2546-2552, 2018
10

---

389
[21]
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740, 2009.
400
401
[22] Ronald Ortner, Odalric-Ambrym Maillard, and Daniil Ryabko. Selecting near-optimal ap- proximate state representations in reinforcement learning. In International Conference Algorithmic Learning Theory, pages 140-154. Springer, 2014.
403
404
[23]
Ronald Ortner, Matteo Pirotta, Alessandro Lazaric, Ronan Fruit, and Odalric-Ambrym Maillard. Regret bounds for learning state representations in reinforcement learning. In Advances in Neural Information Processing Systems, pages 12738-12744 12748, 2019.
406
407
[24]
Cosmin Paduraru, Robert Kaplow, Doina Precup, and Joelle Pineau. Model-based reinforcement learning with state aggregation. In 8th European Workshop on Reinforcement Learning, 2008.
408
409
[25]
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
410
[26] Satinder P Singh, Tommi Jaakkola, and Michael Jordan. Learning without state-estimation in partially observable markovian decision processes. In Machine Learning Proceedings 1994, pages 284-292. Elsevier, 1994.
412
[27] Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Reinforcement learning with soft state aggregation. In Advances in neural information processing systems, pages 361-368, 1995.
415
416
[28] Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 3398311009-131,, 2008.
417
418
[29]
Adrien Ali Taīga, Aaron Courville, and Marc G Bellemare. Approximate exploration through state abstraction. arXiv preprint arXiv: 1808. 19, 2018.
[30]
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the deviation of the empirical distribution. Newleu--Puckane Labs, Tech. Rep, 2003.
421
Checklist
423
1. For all authors...
425
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
426
contributions and scope? [Yes]
427
(b) Did you describe the limitations of your work? [Yes] In Section we describe one the limitations of our work.
429
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
430
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
432
2. If you are including theoretical results...
433
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We state our general assumptions the environment in Section 2 and more specific assumptions in Section 3, Section 3.1 and Section 3.2.
435
438
(b) Did you include complete proofs of all theoretical results? [Yes] In the Appendix.
437
3. If you ran experiments..
438
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
439
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
441
442
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
443
444
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [N/A]
11

---

448
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
447
(a) If your work uses existing assets, did you cite the creators? [N/A]
448
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
450
451
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
452
453
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
455
5.
If you used crowdsourcing or conducted research with human subjects...
456
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
458
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
459
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
461
12


Reviews:
[{"review_id": "z4QOiyA4ZHq", "reviewer": "Reviewer_a7tq", "summary": "The paper identifies a technical issue when integrating state abstraction and model-based reinforcement learning, namely that obtaining iid samples for the next-state distribution may not be feasible in general. To resolve this issue, the paper suggest, unsurprisingly, that a simulator could be employed.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper explores the space in the intersection of model-based RL and abstraction, two key ideas for sample efficiency in RL. A model-based algorithm is defined as one that constructs a transition model of the MDP (could be base or abstracted MDP), and state abstraction is defined, as far as I can say, as an aggregation function.\n\nIn order to apply existing model-based RL machinery, it is imperative to get iid samples of the next-state distribution. The nice insight of the paper is to show, concretely, and via a counter example, that such a luxury may not always be available. Intuitively, the fact that the first transition into an abstract state has occurred may give us some clue about the probability of the next transition into the said abstract state, which highlights a dependence between the two samples.\n\nEven though I really value the observation made here, I have two concerns which I list below:\n\n1- The negative result is very narrow. First, it is debatable if the concept of abstraction should just be restricted to state aggregation. It seems to me that the counter example could have been presented for a broader definition of \"abstraction\", for example, at least get extended to those that probabilistically map to abstract states. Now, even when restricting to the aggregation class, the presented result seems to have a narrow scope. For example, the kind of state abstraction chosen here is obviously not the one and only abstraction function used for RL, or model-based RL for that matter. This particular state abstraction function is, for example, not transitive. Having a low L1 loss is also unnecessarily specific, and could really be generalized to arbitrary f-divergences and/or IPMs, which facilitate the generalization of this result to continuous state spaces (not just tabular problems).\n\n2- The provided remedy, i.e., using a simulator is quite anticlimactic. Notice that the sample efficiency analysis of model-based RL with abstraction may fail for reasons other than iid issue, but if the iid issue is the only hurdle, i believe there are ways to work around the independent samples and still get concentration inequalities using martingales. So I feel like the first half of the paper, namely identifying the problem is nicely done and complete, but a more advanced analysis using independent samples could have really nicely complement the first half.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "q590b506_O", "reviewer": "Reviewer_qhw2", "summary": "This paper deals with model learning when given access to a specific type of abstraction, model-irrelevance (or bisimulation). It states the when the data is collected online, learning an accurate model in the abstract MDP is not possible since the samples are no longer independent (as required by MBRL methods that use concentration inequalities to bound the error of the estimated model). It then shows that given simulator access, this problem no longer exists as samples can be collected from anywhere in the state space. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: I really like the motivation of this work, but I think the writing eventually ends up confusing the reader more than highlighting the main problem. To me, the motivation seems to be to show why/when model learning guarantees can fail when using function approximation (a general state abstraction technique). That, I think is a good question to ask. And it in the context of independence of samples, it would then lead to the following question: Even in the case of iid data, can function approximation (or state abstraction) induce dependence in the samples and thus rule out guarantees for methods that learn a model in the abstracted space? However, the authors stick to the case of online data collection, which in and of itself leads to dependence in samples. Therefore, I believe the working of the paper from that point on does not shed much insight. In other words, now irrespective of whether we are in the original MDP or in the abstract MDP, the samples are dependent in both cases. I don't think the authors' motivation stems from this setting. Rather, the setting should be about the dependence in samples induced by abstraction even when the data is iid. \n\nQuality and Clarity: Unfortunately, the paper lacks massively in these two regards. It is hard to follow, sometimes due to bad/nonintuitive notation and sometimes due to sloppy writing. I think improving in this regard can help bring out the right motivation of the paper, which I think holds good value.\n\nSignificance: In it's current state, I do not think the paper is significant enough. However, if the authors can clarify the motivation, improve the writing, and slightly change the main question they try to ask (as detailed above), I think the paper and the negative result could be extremely valuable to both the theoretical and empirical RL communities. \n\nQuestions/Clarifications:\n\nMy main question is regarding the following statement + on the above comments:\n\n\"Other related work is in the area of MDPs with rich observations or block structure [4, 10]. However, in that setting each observation can be generated only from a single hidden state, which means that the issue of non-i.i.d. data due to abstraction does not arise.\"\n\nIt seems to me that here the authors are trying to say that the abstraction property is key to dependence in samples. However, I cannot gather what exactly they are referring to. Why is the state abstraction non-stationary? Why do the authors call the abstract MDP as a POMDP? What is so special about bisimulation that results in dependence? Looking at the counter examples given in the paper, it seems like the dependence is simply because of the online data collection procedure, and not due to the state abstraction itself. I think clarifying this really holds the key to the contributions of this paper. \n\n\n--------------- Score updated from 4 to 7 after multiple discussions with the authors ---------------", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Suggestions: My suggestion would be to bend the main problem the authors try to answer here. This is again pointed to in my comments in the 'originality' section. I think doing that can push this paper towards a clear acceptance. \n\nI do not think there any explicit negative societal impacts of this work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "I do not think there any explicit ethical concerns raised by this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hrs"}, "extra_text": {}}, {"review_id": "lduD4_DjLO", "reviewer": "Reviewer_drVs", "summary": "In this work the authors present a theoretical analysis of the problems which arise when applying model based RL methods to abstracted MDPs. An abstracted MDP is obtained by mapping each state of the original MDP to a new abstract state. Subsequently, a model of the\ntransition dynamics of this abstracted MDP can be learned. This learned model can be used to solve the abstracted MDP and the resulting policy can be applied to the original MDP. The authors,  examine whether there are any theoretical guarantees regarding the quality of the learned model of the abstracted MDP and of the produced policy. They conclude that collecting data in an online fashion can break the independence assumption made by most MBRL methods in the abstracted case. ", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper examines the interesting problem of learning models of abstracted MDPs. Many popular MBRL methods use deep neural network function approximators to learn models of the MDP dynamics, and can be considered as models of abstracted MDPs. \n\nThe analysis presented in the paper separates the abstraction and model learning parts, which is not the case in most real world methods. Moreover, it is not clear how the conclusions drawn by the paper can be used to inform the design of better MBRL algorithms in abstracted MDPs.  The authors show that having access to a perfect simulator to sample independent transitions is necessary in order to have theoretical guarantees, but do not propose any methods for achieving the same effect in the online setting which is mostly used in real-world problems. \n\nThere is room for improvement in terms of how the ideas are presented in the paper.\n\nMinor comments:\nline 57, 58: Could be rephrased\nline 78 - 82: Could be rephrased\nWhole paper: Fix the notation of the for every symbol so that the arguments are not subscripts.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "0J_X_H9gjg", "reviewer": "Reviewer_9nCd", "summary": "In this paper, the transition model accuracy guarantee in model-based RL on abstract (tabular) MDP is discussed. \n\nThe problem that the sample independence assumption, which is important for guaranteeing meaningful model accuracy bound, is not always valid when the state is abstracted by approximate model similarity abstraction.  \n\nTo address this problem (to realize i.i.d sampling), \nthe use of a simulator, which can re-start from arbitral state-action pair, is proposed. \n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Key strength:  \nThe key insight \"the simulator in which the agent can restart from any state-action pair\" is interesting.  \nIn the general RL setting (even if the simulators are used), the agent collects trajectory starting from the initial states, and the use of the \"restart\" function is not focused on.  \nThe insight of this paper promotes utilizing the restart function. \n(For now, the insight is for MBRL setting on certain abstract MDP, but the insight of the paper motivates post cursors to conduct a discussion about the benefit of the simulator equipped with the restart function.)  \n\nKey weakness:  \nNo empirical result is provided. I understand the paper is a theoretical one, but the quality of the paper should be much improved if the empirical result (even in a simple grid-world case) to support the authors claim or insight is provided (e.g., is Algorithm 3 actually works well?).  \n\nTypo: \nLine 374: rl -> RL  \nLine 397: q-learning -> Q-leanring  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper discusses the issue of independence of samples when abstractions are used with online exploration in RL, and the central result is a negative result, that these samples cannot be treated simply as iid and concentration bounds designed for such settings such as Hoeffding's (with union bound to handle L1 error) do not apply. 

The authors are noted, however, that formal negative results take the form of impossibility results and/or lower bounds which *do not depend on a specific approach to analysis*. Even better, they should be algorithm independent, or at least apply to a wide range of algorithms. In fact, such negative results in RL are frequently published in top conferences in recent years, and the authors can consult the works of authors like Andrea Zanette, Ruosong Wang, Gellert Weisz, etc., as examples. In contrast, the "negative result" of the current paper is specific to an algorithm (model-based, which is fine as it is simple and representative) and a specific type of approaches to analysis (assuming iid and applying concentration bounds when the conditions are violated). This makes the negative result relatively weak and informal. (Sometimes these informal negative results can be useful and insightful, but they usually appear as a side discussion and cannot serve as the main result of a paper, particularly because the insights they offer are often speculative due to the informal nature of the results.)

Besides, there is a plethora of positive results and analysis techniques that potentially apply to the setting studied in the paper, which the paper fails to discuss. In particular, martingale concentration bounds, law of iterated logs, and a few other techniques come to mind when there is dependence between samples (e.g., when the number of samples is a stopping time that depends on the outcomes of random state transitions); https://arxiv.org/pdf/1708.07367.pdf has used quite a few of such techniques and can be a good reference to study. While it is true that few of existing works consider abstractions, the complication introduced by the abstraction is that different samples from the same abstract state are not identically distributed (the second "i" in "iid"), but advanced concentration bounds (e.g., Freedman's) usually don't assume identically distributed variables and can readily handle them. (Authors also made a similar point in Lemma 3, which directly follows from Hoeffding + union bound.) 

Furthermore, one can also think of abstractions as a special case of function approximation: for example, on a given dataset, model-based RL with an abstraction is exactly equivalent to Fitted-Q using a corresponding "piecewise constant" function space. To this end, existing analyses that handle generic function approximation need to be discussed. Instead of proving concentration for each abstract state, you would use uniform convergence argument over the entire function space to handle concentration; a good reference is Antos et al (https://link.springer.com/content/pdf/10.1007/s10994-007-5038-2.pdf) which assumes beta-mixing data. It is true that this paper assumes a fixed behavior policy and does not consider changing policies (the authors emphasized this in post-rebuttal discussions), but there are other more recent results that consider specifically online exploration with generic function approximation; see https://arxiv.org/pdf/1610.09512.pdf and follow-up works.

Finally, a reviewer mentioned the lack of experiments. While that is certainly not a weakness of the paper, the authors can consider this as a way to strengthen their negative result. As of now, it is unclear what happens if one uses the "wrong" algorithm in practice, even if we know it is not theoretically sound. It may perform very well in practice and can be a hard-to-beat baseline compared to more sophisticated techniques that are theoretically sound. If degenerate empirical performance can be demonstrated, the issue will draw more attention and convince the community to treat the problem more seriously. 
Decision: Reject