An Analysis of Model-Based Reinforcement Learning From Abstracted Observations
Authors: Rolf A. N. Starre
Marco Loog
Elena Congeduti
Frans A Oliehoek
Venue: Accepted by TMLR ()

Abstract: Many methods for Model-based Reinforcement learning (MBRL) in Markov decision processes (MDPs) provide guarantees for both the accuracy of the model they can deliver and the learning efficiency. 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. Therefore, it may come as a surprise 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 (e.g., in the real world). That means that, without taking this dependence into
account, results for MBRL do not directly extend to this setting. Our result shows that we can use concentration inequalities for martingales to overcome this problem. This result makes it possible to extend the guarantees of existing MBRL algorithms to the setting with abstraction. We illustrate this by combining R-MAX, a prototypical MBRL algorithm, with abstraction, thus producing the first performance guarantees for model-based ‘RL from Abstracted Observations’: model-based reinforcement learning with an abstract model.

Published in Transactions on Machine Learning Research (09/2023)
An Analysis of Model-Based Reinforcement Learning From Abstracted Observations
Rolf A. N. Starre
r.a.nstarre@Suddelf..tt
Delft University of Technology
Marco Loog Radboud University
morco.looggru..v
Elena Congeduti
e.congddutifuudelff.tt ml
Delft University of Technology
Frans A. Oliehoek
f.a. oliehooek@uudefeeeee
Delft University of Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id- YQWOazSMPp
Abstract
Many methods for Model-based Reinforcement learning (MBRL) in Markov decision pro- cosses (MDPs) provide guarantees for both the accuracy of the model they can deliver and the learning efficiency. At the same time, state abstraction techniques allow for reduc- tion the size of an MDP while maintaining a bounded loss with respect to the original problem. Therefore, it may come as a surprise that no such guarantees are available when combining both techniques, ie., where MBRL merely observes abstract states. Our theoret- ical analysis shows that abstraction can introduce dependence between samples collected online (c.g., in the real world). That means that, without taking this dependence into account, results for MBRL do not directly extend to this setting. Our result shows that we can use concentration inequalities for martingales to overcome this problem. This re- sult makes it possible to extend the guarantees of cxisting MBRL algorithms to the setting with abstraction. We illustrate this by combining R-MAX, a prototypical MBRL algorithm, with abstraction, thus producing the first performance guarantees for model-based 'RT. from A bsstracted Observations': model-based reinforcement learning with an abstract model.
1 Introduction
Tabular Model-based Reinforcement Learning (MBRL) methods provide guarantees that show they can learn efficiently in Markov decision processs (MDPs) (Brafman & Tennenholtz, 2002; Strehl & Littman, 2008; Jaksch et al., 2010; Fruit et al., 2018; Talebi Maillard, 2018; Zhang & Ji, 2019; Bourel et al., 2020). They do this by finding solutions a fundamental problem for Reinforcement Learning (RI), the exploration-cxplottatioo dilemma: when to take actions to obtaín more information (explore) and when take actions that maximize reward based on the current. knowledge (exploit). However, MDPs can be huge, which can be problematic for tabular methods. One way to deal with large problems is by using abstractions, such as the mainstream state abstractions (Li, 2009; Abel et al., 2016). State abstractions reduce the size of the problem by aggregating her states according to different criteria, depending on the specific type of abstraction. We can view state abstraction as a special case of funct ion approximation, where every state maps to its abstract state (Mahadevan, 2010), and we can roughly divide them into exact and approzimate abstractions (Li, 2009; Abel al., 2016).

---

Published in Transactions on Machine Learning Research (09/2023)
Approximate abstractions relax the criteria of exact ab- stractions, and therefore allow for a larger reduction in the state space. Typically, this approximation leads to a trade-off between performance and the amount of required data (Paduraru et al., 2008; Jiang et al., 2015). In this pa- per, we will assume the use of abstraction as a given, e.g. because the complete state space is too large to deal with. Nevertheless, explore the trade-off in Section 4, where we compare the performance of the prototypical R-MAX al- gorithm (Brafman & Tennenholtz, 2002) with and without rastraction.
a
MDP
Agent
((s)
+
Figure 1: RL from Abstracted Observations,
the agent receives the abstract state s = o(s)
as an obscrvation instead of the state s. Image based on Abel et al. (2018).
In our setting, the agent acts an MDP that returns states 8, but instead of observing the true state s, the agent only observes abstract states d(s) (sce Figure 1). This setting, which has been considered before (Ortner et al., 2014a; Abel et al., 2018), is what we call RL from Abstracted Obsercalions (RLAO). Surprisingly, there are relatively few results for RLAO, even though many results for the planning setting are available (Li et al., 2006; Abel et al., 2016). The main difference between these two settings is that in planning with abstraction the resulting problem can still be considered an MDP, but in RLAO, while the underlying problem is still an MDP, the observed problem is not.
The observation that the observed problem is not an MDP can be understood when we realize that RLAO corresponds to RL in Partially Observable MDP (POMDP) (Kaelbling et al., 1998), as previously described (Bai et al., 2016)- Specifically, the abstraction function serves an observation function. Rather than observing its true state 5, the agent observes the abstract state (bs) and its policy chooses action based on this abstract state. It is well known that policies for POMDPs that only base their action on the last observation can be arbitrarily bad (Singh et al., 1994). Fortunately, there is also good news, as this worst- case docs not apply when & is an eract model similarity abstraction 2 (Li, 2009), because the resulting problem can be considered an MDP; this abst raction maps states to the same abstract state only when their reward and transition functions in the abstract space are the same (Li et al., 2006). We focus on the related approzimate model similarity abstraction (Abel et al., 2016), which maps states to the same abstract state only when their reward and transition functions in the abstract space are close. Intuitively, because of its connection to the exact model similarity, one could expect that for this abstraction the worst-case also does not apply. However, as we discuss in detail in Section 2.2, MBRL methods typically use results that rely on the assumption of independent and identically distributed (i.id.) samples to prove efficient lcarning (Strehl & Littman, 2008; Jaksch et al., 2010; Fruit et al., 2018; Bourel et al., 2020). This is not appropriate in RLAO: with abstraction, the transitions between abstract states need not be Markov, and the samples may depend on the history.
We analyze collecting samples in RLAO and prove that, with abstraction, samples are not guaranteed to be independent. This means that most guarantees of enisting MBRL methods do not hold in the RLAO selling. 3 The primary technical result in this work shows that we can still learn an accurate model in RLAO by replacing concentration inequalities that rely on independent samples with a well-known concentration inequality for martingales (Azuma, 1967). This result allows us to extend the guarantees of MBRL methods to RLAO. We illustrate such an extension for the prototypical R-MAX algorithm (Brafman & Tennenholtz, 2002), thus producing the first performance guarantees for model-based methods in RLAO. These results are important for the often adopted state abstraction framework, as they allow us to conclude under what cases performance guarantecs in MBRL can be transferred to settings with state abstraction.
We refer to Section 5 for comparison with the related work.
2 Also known stochastic bisimulation (Givan al., 2003). "Of course, certain guaranteus on the combination of abstraction and RL known. However, in most related work in abstraction settings (e.g. abstraction selection), the complication of samples not being independent does not occur due to particular assumptions (Paduraru al., 2008; Hallak et al., 2013; Maillard et al., 2013; Majeed Hutter, 2018; Ortner al., 2019; Du al., 2019). Section& 5 gives details for individual papers.
2

---

Published in Transactions on Machine Learning Research (09/2023)
2
Background
Section 3 will cover the combination of MBRL and abstraction in MDPs, in this section we introduce the required background.
2.1 Model-Based RL
As is typical for RL problems, we assume the environment the agent is acting in can be reprosented by an infinite horizon MDP M (,, (Puterman, 2014). Here is finite set of states 8 E S, A a finite set of actions a E A, T a transition function T(s' s, a) = Pr(s'[s, a), reward function R(s, a) which gives the reward received when the agent executes action a in state 8, and y discount. factor with I 7 S that determines the importance of future rewards. We use Bmax denote the maximum reward the agent can oblain in one step. The agent's goal is to find an optimal policy n² S A, i.e., policy that maximizes the expectation of the cumulative reward in the MDP. VT denotes the expected value of the cumulative reward under policy starting from state s. Similarly, (s, a) denotes the expected value of the cumulative reward when first taking action a from state 8 and then following policy afterward.
MBRL methods learn a model from the experience that the agent gains by taking actions and observing the rewards it gets and the states reaches. For fixed state-action pair (s,a), a), we let TI, T2. .TN(s,a) be the first. N(s, a) time steps at which the agent look action in state 8. The first N(s,a) states s' that the agent reached after taking action in state We use Y to refer to the collection of all Y.a. Typically, in MBRL, the obtained experience is used to construct the empirical model Ty (Brafman & Tennenholtz, 2002: Strehl & Littman, 2008; Jaksch et al., 2010; Fruit et al., 2018; Talebi & Maillard, 2018; Zhang & Ji, 2019; Bourel et al., 2020). This model is constructed simply by counting how often the agent reached a particular next state and normalizing the obtained quantity by the total count:
stored the sequence Ys.a & (s((n+1), 8((ra-1), ... +1)))...)+
M(s.a)
Vs' E S: Ty(s'(s,a) A
Σ
1(y((-11) = = 6,0
(1)
N(s,a)
Here }{-} denotes the indicator function of the specified event, ie., 1(y = s'} is 1 if ((+1)) otherwisc.
=s}}
= and
2.2 Guarantees for MBRL
The quality of the empirical model Ty crucial for performance guarantees, irrespective of the form of the guarantee, e.g., PAC-MDP (Strehl & Littman, 2008) or regret (Jaksch et al., 2010). The quality of the empirical model is high when the distance between (-ls, a) and the ground truth T(- a) is small. We can, for instance, measure this distance with the Ln norm, defined as follows:
aT T(-Is, a)ll A Σ [T -(s''s,,))
(2)
s'eS
Concentration inequalities are often used to guarantee that, with enough samples, this distance will be small, e.g.:
Lemma 1 (L, inequality (Weissman et al., 2003)). Let Y., y(l) v:l).. (N(ao) be iid.d random variables distributed according to T(-ss,)) Then, for all > 0,
(-(s,) - T(+ss,))ll 2 2) (2 2)e N(sajee
(3)
These incqualities typically make use of the fact that samples are i.i.d. It is not necessarily evident that these bounds can be applied without problem. Let us explore the transitions from particular state, say state 42, in Markov chain (we can ignore actions for this argument). Let k and denote the time steps of
3

---

Published in Transactions on Machine Learning Research (09/2023)
two different visits to state 42. Without abstraction, the conditional distributions from which next states are sampled are identical. So the question now is if these are independent. That. is, is it the case that:
S41 = S; = 42) P(S 18 = =2) P(S = 42)?
(4)
We have that
S 4: 42)
42, 42) 15.
42, + 1, = 42)
(5)
P(SS = 42, - 42) = 42) (due to the Markov property)
(6)
So the question is if P(Sx+1|S; = 42, - 42) P(S++1 Sss 42)? In general, this is not the case, since the information that S = gives information about what Sk+1 was.
However, as shown for instance by Strehl & Littman (2008), concentration inequalities for i.i.d samples, such as Hoeffding's Inequality, can still be used as an upper bound in this case, because of the Markov property and the identical distributions of the samples. In this way, MBRL can upper bound the probability that the empirical model (-1s, a) will be far away (2 e) from the actual model a() When the empirical model is accurate, policy based on this model leads to near-optimal performance in the MDP M (Brafman & Tennenholtz, 2002; Strehl & Littman, 2008; Jaksch et al., 2010; Bourel et al., 2020).
2.3 State Abstraction for Known Models
We can formulate state abstraction as mapping from states to abstract states (Li et al., 2006). This mapping is done with an abstraction function 6, surjective function that maps from states E S to abstract states E S: d(s) S + S.. We use the notation to refer to the abstract space and define $ as 3 = [o{o]s E 5}. We slightly overload the definition of s to be able to write E 8. this case, the set of states that map s, i.e., s {s E S ((s) s}. This form of state abstraction is general, and clusters states with different dynamics into abstract states. We assume that the state abstraction deterministically maps states to abstract state. Since each state maps to preciscly one abstract state and multiple states can map to the same abstract state, the abstract state space is typically (much) smaller than the original state space, |5| S SS).
We focus on a type of abstraction approzimate model similarity abstraction (Abel et al., 2016), also known as approximate stochastic bisimulation (Dean et al., 1997; Givan et al., 2003). In this abstraction, two states can map to the same abstract state only if their behavior is similar in the abstract space, ie., when the reward function and the transitions abstract states are close. We can determine the transition probability to abstract state T(s'|s, a) as:
T() = Σ T(s'ss,a).
8'E3'
Then, we can use equation 7 to define approximate model similarity abstraction:
Definition 1. An approrimate model similarity abstraction, @model.ng.wr. for fixe yR, lr, satisfies
@model.n @model
= Va E A: [R(s,, a) R(82, a)l 1/m,
39 E S A [Ts' (.. T(s /6/$s2.11 a)l $ nr.
(8)
From now on, we will refer @model as Φ. We note that this abstraction still quite generic. It can cluster together states that have different transition and reward functions.
2.4 Planning With Abstract MDPs
In the planning setting, where the model is known a priori, we can use the abstraction function construct abstract MDP. An ract MDP can be helpful because it is smaller, making it easier to find solution,
4

---

Published in Transactions on Machine Learning Research (09/2023)
and a solution for the abstract MDP can work well in the original MDP (Li et al., 2006; Abel et al., 2016). We construct an abstract MDP Ma from the model of an MDP M, an abstraction function o, and an action-specific weighting function w. 4 The weighting function w gives a weight to every state-action pair: Vs E S. a E 0 S w(s.a) - 1. The weights of the statc-action pairs associated with an abstract state & sum up to Ev(o(e)) a(s',a) 1. We can use the weighting function to create an abst transition and reward function, which are weighted averages of the original transition and reward functions. In this way, from M, O, and any w, we can construct an abstract MDP Ma:
Definition 2 (Abstract MDP). Given an MDP M, Ø, and w, an abstract MDP M (5, A, Tw, Rw) is constructed as: S = {Ō(s) s E A)
E E R (3) = (u(ssa)R(ss.)
(9)
SE3
v a A: (= = Σ Σ w(s, (s'(ss))
(10)
aEs s'Es'
Note that the abstract MDP Ma itself is an MDP. So optimal policy H' for Mw- A desirable property of the approximate model similarity abstraction is that we can upper bound the difference between the optimal value V in M and the value V obtained when following the policy #* in M. These bounds exists in different forms (Dearden & Boutílier, 1997; Abel et al., 2016; Taīga et al., 2018). For completeness, we give these bounds for both the undiscounted finite horizon and the discounted infinite horizon:
use planning methods for MDPs to find an
Theorem 1. Let M = A,, R) be an MDP and M = (S, R) an abstract MDP, for some defined abstract transitions and rewards. We assume that
V5, ES SE A: (T(')
(r(3'(s,0) S 1/
(11)
and [R(3,a) a) - R(s, I nR-
(12)
Then, for a finite horizon problem with horizon we have: (*(s) V (s) < 2hTR + (h - 1)haT R|
(13)
And for a discounted infinite horizon problem with discount y we have:
2nn 2y Rmax
('(s)- v (s) 1 1-7 (1 71-
(14)
The proof of Theorem 1 is in Appendix A.3. These bounds show that an optimal abstract policy म* for M can also perform well in the original problem M when the approximate errors na and for small. They hold for any abstract MDP M created from approximate model similarity abstraction & and any valid weighting function w.
3 MBRL From Abstracted Observations
In RLAO, we have an abstraction function & and instead of observing the true state 8, the agent observes the abstract state ((s). In contrast to the planning setting in Section 2.3, here we act in an MDP M of which we do not know the transition and reward functions. As mentioned in the introduction, there are surprisingly few results for the REAO setting (Section 5 discusses special cases people have considered). Specifically, results of MBRL from Abstracted Observations (MBRLAO) are lacking. Section 3.2 explains why this is by analyzing how abstraction leads to dependence between samples, which means that the methods for dealing with Markov transitions, as covered in Section 2.2, no longer suffice. Then, in Section 3.4, we show how concentration inequalities for martingales can be used to still learn an accurate model in RLAO. To illustrate how this result can be used to extend the results of MBRL methods to RLAO, we extend the results of the R-MAX algorithm (Brafman & Tennenholtz, 2002). R-MAX is well-known and straightforward method that guarantees sample efficient learning.
4The action-specific weighting function is more general than the typically used weighting function, which is action-specifie and only depends on the state (Iá et al., 2006). More formally, it is the case where Va, a' A, 8 E S w(s,a) w(s,a')
5

---

Published in Transactions on Machine Learning Research (09/2023)
3.1
The General MBRL From Abstracted Observations Approach
In RLAO, the agent collects data for every abstract slate-action pair (3,4), stored as sequences Psa:
Yz : ( g'(mzt1),. .... +1)
(15)
Like in equation 1, we construct an empirical model Ty, now looking at the abstract next-states that the agent reached:
N(E.)
(s ((s.a)
Σ
1[ 3,0 =57
(16)
Suppose could guarantee that the empirical model Ty was equal, or close, to the transition function Tw of an abstract MDP Mr constructed from the true MDP with @ and a valid w. In that case, we could bound the loss in performance due to applying the learned policy म* to M instead of applying the optimal policy nt (Abel et al., 2016; Taiga et al., 2018). Our main question is: do the sinite-sample model learning guarantees of MBRL algorithms still hold in the RLAO setting?
3.2 Requirements for guarantees for MBRL From Abstracted Observations
order to give guarantees, we need to show that the empirical model Ty is close to the transition model of an abstract MDP Ms. Before defining this transition model of Mas we examine the data collection. In the online data collection, the agent obtains sample for Y5,a when it is in state Specifically, the agent obtains the i-th sample
and takes action
y-t 3,a
= from state x(1) S E s: B.a
y
T(IX a,0 s)),a).
(17)
Let Xz = (x( N(s.0) denote the sequence states from which the agent took action a. Each state gets a weight according how often it appears in X3 which we formalize with the weighting function wx:
==1
N().0)
A:
Σ
1(x 5,a
= s}.
(18)
N(5,a)
We use wxx to define Tax analogous to equation 10:
Vτ,5 SE A Tax (3'13,0) Σ wx(8,a) Σ T()lss,))
(19)
s'E3'
To highlight the close connection between Twx and Ty (build of samples from T(- 5.a = = a)), we give a second, but equivalent, definition of Tax:
N(Ea) T(E a).
V(3,a), 8': Tax ()) 2 N(
(20)
Note that wx and thus Tax are not fixed priori. Instcad, like Ty, they are empirical quantitics that change at every time step and depend on the policy and the (stochastic) outcomes. Importantly, by its definition, wx is valid at every timestep. It is not problem that wx and Tax change over time, long as the empirical model Ty can be shown to be close Twx For this, we want concentration inequality to provide bounds on the deviation of the empirical model Ty from Tex: we refer to this inequality as the abstract L1 inequality, similar in form to equation 3:
(117r - Twy (-13,a)1 a)l 2 5
(21)
where Ty a) is defined according to equation 16 and Tax according to equation 19.
Tn the proof of Theorem show that these two definitions are equivalent.

---

Published in Transactions on Machine Learning Research (09/2023)
3.3 Why the Previous Strategy Fails: Dependent Samples That Are Not Identically Distributed
Suppose we could directly obtain i..dd samples from Twx and base our empirical model Ty the obtained samples. In that case, we could show that the abstract L1 inequality holds by applying Lemma 1. This lemma would be applicable because we could obtain number N(s, of i.i.d. samples per abstract state-action pair, distributed according to Twx (-15, a). However, the samples are not ii.d in RLAO: the samples are neither identically distributed nor independent, and this combination means that previous techniques fail. We will first cover the distribution of the samples and show that samples not being identically distributed is not problem. Then prove that samples not guaranteed to be independent. Afterward, Section 3.4 shows that we can still learn when the samples are dependent.
3.3.1 Why We Can Not Use Lemma 1: Dependent Samples.
The samples are not necessarily identically distributed in RLAO since the agent obtains a sample y when taking action from state (1) E s, as in equation 17. If x
F.a * x these states can have different transition distributions. This implics that in general we might not be able to apply Lemma 1, becanse it assumes identically distributed random variables. However, different distributions by themselves need not be a problem; we show that the result also holds when the random variables are not identically distributed:
Lemma 2.
( Let Xs.a = $1. sm be a sequence of states s E 8 and let Ys,a = (()), ((2), ,...,... ()))))))m)))))))) be independent random voriables distributed according to Pr(-)si,a),- a), ,Pr(-)sm sm: a) (equation 7). Then, for all
Pr([ITy(-15,a) - Tux
Twx (13, e)) S (2 - 2)e 2)e mm=""
(22)
The proof can be found in Appendix B. Therefore, if the samples in RLAO were independent, then we could apply Lemma 2 to guarantee an accurate model.
Independence. One could be tempted to assume the samples are independent, i.e.
VS 5' (S) Pr(Y-()) 8.0 = ... fr(m) = = Pr(Y 8.0. f1) P(Y(mm) =mm)
(23)
However, this is not true in general in RLAO:
Observation 1. When collecting sumples online using an abstraction function, such samples are not nee- essarily independent.
Samples can be dependent when 1) samples are collected online in the real environment, of which we do not know the transitions, and 2) the samples are collected for abstract states 5. Observation 1 can be under- stood from the perspective that the RLAO problem corresponds to RL in a POMDP (Bai et al., 2016). The corrosponding POMDP uses the abstraction function as the observation function and the abstract states as observations. Since the transitions between observations need not be Markov in POMDPs, the samples from abstract states can depend on the history. While this observation may be clear from the POMDP per-
0.6
B
0.4
A
0.4
spective, work in RLAO regularly assumes (explicitly implicitly) that independent samples can somchow be obtained (Paduraru
0.6
al., 2008; Ortner el al., 2014a; Jiang el al., 2015; Orlner et al., 2019). In the follow- ing counterexample, we rigorously show that samples are not necessarily independent.
1
Figure 2: Simple MDP, with only action, and abstrac- tion. The small circles are states (1,2,3,4). A, B and C are the ab- stract states. The arrows show the transition probabilities, e.g. P(3 = 0.6.
Counterexample. We use the example MDP and abstraction in Fig- ure 2, where we have four states, three abstract states, and only one action. Since the example MDP has only one action, we omit the action from the notation. We examine the transition function of abstract state
7

---

Published in Transactions on Machine Learning Research (09/2023)
A, Ty (+14) and consider the first two times transition from A. These two transition samples, & and $2 are the first two entries in YA- We show that the samples are not independent for at least one combination of 81 and 5/2
Let 8 = = i.e. the first two times we experience a transition from the abstract state A, we end up in B. We denote the i-th experienced transition from abstract state A ( Let state 1 be the starting state.
We start with the product of the probabilities:
B) =
(24)
We have Pr(y B) 1r(B[1) = 0.6 for the first term since state is the starting statc. The second term is more complex since it includes the probability of starting the transition from state 1 and state 2.
We have:
Pr(PA) B) PP((P BI B3 PT(PA =3)
(25)
SES
= =Pr(V(() BI PrPr( = A) + Pr((P) BIV B)P
+Pr(PA)) BIP C) Pr(P CC).
(26)
-Pr(V = BI = B) P) B) Pr(())) = B = -C) Pr O).
(27)
= -Pr(Y = -3114 = 3) Pr(MA 3) + Pr(Y) =3 = Pr =4)
(28)
= 0.6 0.6 + 0.4 0.4 = 0.52.
(29)
For the step from equation 26 to equation 27, Pr(Y. = A) is 0 because there is no transition from a state
(1)
in A to a state in A. Then, from equation 27 to equation 28, we use that both abstract states and C
consist of exactly 1 state. So, e.g., Pr(F((2) B B| = B) = Pr(Y(2) = 3/ = =3.. So, for the product of
the probabilities, we end up with: Pr(P(() A = B) Pr(YA) A
= B) = 0.6 0.52 = 0.321.
For the joint probability, we have:
Pr(V B, (2) B = B) = Pr(P(() = B) Pr((B))(P((B1)) (r(()))) Pr(1
= B B)
(30)
(31)
0.6 (0.6-1) 1)
(32)
-066-0.6
(33)
0.36.
(34)
Here, (r -I = B) Pr((I) because the first transition ends in state and we always
transition to state 1 from state B. Hence, Pr(V B| B) = Pr(B(1) Pr(1 B) = 0.6 1.
Combining the joint probability and the product of probabilities, we end up with:
0.36 Pr(P =B = B) P P) B) 0.52..
(35)
Thus, the samples are not independent. Leading us to the second obscrvation.
Observation 2. As independence cannot be guaranteed, Lemmas 1 and 2 cannot be readily applied to show that the abslvact L1 inequality holds.
This claim follows from the fact that Lemmas 1 and both use the assumption of independence in their proofs. It would still be possible to obtain independent samples if we could, for example, have access to a simulator of the problem. In that case, is still possible to give guarantees on the accuracy of the model, which show in Appendix F. However, we consider the setting where simulator is not available.
8

---

Published in Transactions on Machine Learning Research (09/2023)
3.3.2 Why the Approach by Strehl & Littman (2008) Fails
While the counterexample above is informative as to why Lemmas 1 and 2 cannot be applied, the failure to apply these lemmas may not come as a surprise: in the end, as shown by Strehl & Littman (2008), more work is needed. They are able to use these concentration inequalities due to an additional proof that shows that even though the samples are drawn from a Markov chain, and thus not fully independent, the inoquality still serves an upper bound. This raises the question whether we could not follow the same approach, and show that Lemma 1 (or 2) is still upper bound in the RLAO setting.
It turns out that this is not possible, as that result uses the Markov property and requires each sample to be identically distributed. Without abstraction, only (s, a) and the next states s' ~ P(-|s, a) are considered, which indeed have the same distribution. In RLAO, the outcomes of multiple states are grouped together and for a pair (3 both the state 8 8 that we reach and the resulting next state 5' need to be considered. Since the distributions ~ P(-ss,, a) and s' ~ P(-|s2, a) of two states $1, $2 E do not have to be the same, these samples are not guaranteed to be identically distributed.
3.3.3 Summary: Why Previous Strategies Fail
Summarizing, we have seen that previous strategies fail due to the combination samples neither being independent, nor being identically distributed. We showed that the samples would only be non-identically distributed (but independent) we could modify the proof of Lemma 1, leading to Lemma 2, that could be directly used. On the other hand, if the samples were only dependent (but still identically distributed), it would be possible to follow the strategy of Strehl & Littman (2008). However, given that we are dealing with the dependent non-identically distributed setting, neither of these previous strategies work, and new approach is needed, as we present next.
3.4 Guarantees for Abstract Model Learning Using Martingales
Now we want to give a guarantee in the form of the abstract L1 inequality from equation 21. 6 In Section 3.2, we found this was not possible with concentration inequalities such as Hoeffding's inequality because the samples are not guarantced to be independent. Here we consider a related bound for weakly dependent samples, the Azuma- Hoema--o inequality. This inequality makes use of the properties of martingale difference sequence, which are slightly weaker than independence:
Definition 3 (Martingale difference sequence (Azuma, 1967)). The sequence Zı, Zz, .., is a martingale difference sequence if, Vi, it salisfies the following conditions:
E Z1, Zz,
Z =
[ < 00.
The properties of the martingale difference sequence can be used to obtain the following concentration inequality:
Lemma 3 (Aemma-Hoffdding Incquality (Hocffding, 1963; Azuma, 1967)). If the random variables Z1, Zz,
form a martingale difference sequence (Def. 3), with |2,] < b, then
Pr(
2 > e) < W0.
(36)
Our main result, Theorem 2, shows that we can use Lemma to obtain a concentration incquality for the abstract transition function in RLAO (as in equation 21). Specifieally, we show that, with high probability, the empirical abstract transition function Ty will be close to the abstract transition function Twx
We focus the transition function, for the reward function make some simplifying assumptions Section 4. We discuss in Section how these assumptions can relaxed and the result. extended for the reward function.
9

---

Published in Transactions on Machine Learning Research (09/2023)
Theorem 2 (Abstract L1 inequality). If agent has access to a state abstraction function and uses this to collect data for any abstract state-action pair (z,a) by acting in an MDP M according to a policy R, we have that the following holds with a probability of at least 1 1- 8 for fized value of ((,a)):
[|Ty(-13, a) -Tx
Se
(37)
where 8 = -
Here use the definitions of T-),,,, (equation 16) and Tux (-15, a) (equation 19). This theorem shows that the empirical model constructed by MBRLAO is close to an Abstract MDP Max and here Theorem 1 gives performance loss guarantees. By assuming that Mwx is the results of an approximate model irrelevance abstraction, we can give end to end guarantees. In simpler words: our result just shows that whatever Ty you might end up with (indeed, regardless of changing policies, etc.), it was generated by some underlying states X, and the implied Twx will concentrate on Ty-
Note that, unlike in planning with abstract MDPs (Section 2.4), there is no fixed set of weights Tax that can be used as ground truth that needs to be estimated. As illustrated in Section 3.3.1, the RIAO setting corresponds to a POMDP, which means that depending on the history there would be different distribution over the states (and thus different weights) in each abstract state (called 'the belief in POMDP). Instead, both Tax and Ty change over time. We show in the proof of Theorem 2 (in Appendix C) that Ty will concentrate on Twx as they are intimately connected. This is possible because Lemma can be applied as long as the Zi form a martingale difference sequence, with |2,] S b. In the proof, we define a suitable Ze and show that Ty will thus concentrate on Twx: with high probability.
4 An Illustration: R-MAX From Abstracted Observations
Here we give an illustration of how we can use Theorem 2 to provide guarantees for MBRL methods in RLAO with an approzimate model similority abstraction. We illustrate this using the R-MAX algorithm (Brafman & Tennenholtz, 2002). We start with a short description of R-MAX and how it operates with abstraction.
The R-MAX algorithm maintains model of the environment. It uses this model to compute policy periodically and then follows this policy for several steps. Initially, all the state-action pairs are unknown and the algorithm optimistically initializes their reward and transition functions: R(s,a) = Ryax (the maximum reward), T(ssss,) a) = 1, and Vs # s: T(s'(s,, a) = O. This initialization means that, in the model the algorithm maintains, these unknown (s.a) lead to the maximum reward, hence the name R-MAX. A state-action ion pair's transition and reward function are only updated once they have been visited sufficiently often, at which point the state-action pair is considered known. Together, this ensures that the algorithm explores sufficiently. During execution, the algorithm operates in episodes of n-steps. At the start of every episode it calculates an optimal n-step policy and follows this for timesteps, until state-action pair becomes known. Once all the state-action pairs are known it calculates the optimal policy for the final model and then runs this indefinitely. The algorithm has the following guarantee:
Theorem 3 (R-MAX in MDPs without abstraction (Brafman & Tennenholtz, 2002)). Given MDP M, with [S] states and |A] actions, and imputs e and 8. With probability of at least 1 5 the R-MAX algorithm will attain an expected average return of Opt(IIn((TTTT)) 11
within a number of steps polynomial in (S). |A, c 8 Te. Where Te is the c-return mixing time of the optimal policy, the policies for M whose c- reburn miring time is Te are denoted by II (e, Te), the oplimal expected Te-slep undiscounted average return achievable by such policies are denoted by Opt(Iar(e,T.))
Here T. is the e-return mixing time of a policy т, it is the minimum number of steps needed to guarantee that the expected average return is within of the optimal expected average return (Kearns & Singh, 2002).
For R-MAX from Abstracted Observations, we make the following assumptions that stem from the original analysis: we assume that the MDP is ergodic (Puterman, 2014), that we know S and A, that the reward
7 An ergodic, or recurrent, MDP is an MDP where every state recurrent under every stationary policy, iee. asymptotically, every state will he visited infinitely often (Puterman, 2014).
10

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm Procedure: R-MAX from Abstracted Observations
Input: o,
for all (5,0) E S x A do
( =1
(3, = Rmax
Y..- -11
end for
My (5, A, Ry)
Select m, the number of samples required per (abstract) state-action pair to make them known. // While there is still an unknown state-action pair. while mi, aa,l m do Compute optimal Te-step policy in My for the current abstract state.
for T. timesteps do
o(s)
(5))
s', r = Step(s, a)
8 = s'
if Ye,al <m then
a. append(((((())) if Y2,a m then
//St Statc-action pair has become known. for all 5' S do
(s'l's,, (155|ssa) a) = E 1[Y s,a
= 5'}
end for Ry (s,a)= r break
end if end if
end for
end while
Compute optimal policy म* for M and run indefinitely.
function is deterministic, and that we know the minimum and maximum reward. W.Loog,, we assume the rewards are between O and Rmax, with 0 < Rmax < co. We add the assumption that the agent has access to an approximate model similarity abstraction function & and that each state in an abstract state has the same reward function.
Algorithm 1 shows the procedure for R-MAX from Abstracted Observations. It follows the same steps as the original algorithm, except that it makes of an abstraction function and maintains abstract model. As in the original, the input lo the algorithm is the allowed failure probability 5, the error bound and the e-return mixing time T. of an optimal policy. We add the abstraction function & as new input. The algorithm uses this function to observe Ø(s), as in Figure 1, and it builds an empirical (abstract) model from the observations it obtains.
Because the algorithm uses an abstraction function Φ, we cannot guarantee the error bound. However, with Theorem 4 we can still guarantee an error bound that function of and the error n of the abstraction, thus providing the first finite-sample guarantees for RLAO:
Theorem Given an MDP M, an approzimate model similarity abstraction Φ; with yJn and ryr and impuls (). [A], e, 8, Te. With probability of at least 1 1-8 the R-MAX algoritim adapted to abstraction (Algorithm 1) will attain expected average return of Opt[II (7)))-39(mm 78) within number of steps polynomial in [S), ||, i T.. Where T. is the e-return miring time of the optimal policy, the policies for M whose e-
Note that this is just a slight simplification any empirical estimate R is guaranteed be within on any Rw, under the assumption that the rewards deterministic.
11

---

Published in Transactions on Machine Learning Research (09/2023)
return mixing time is Te are denoted by II Te), the optimal expected T. Ttep undiscounted average return achievable by such policies are denoted by Op T.)); and
Aum:nnn Taya (Te 1)T.
2 1T S)
The proof can be found in Appendix D.2 and follows the line of the original R-MAX proof, using the assumptions mentioned at the start of Section 3. To translate the results to the RLAO setting, we first use the Abstract L1 inequality (Theorem 2) to show that the empirical abstract model is accurate with high probability. Then the performance bounds from Theorem 1 can be used to bound the loss in performance by using an abstract policy based on the empirical abstract model in the MDP M instead of the optimal (ground) policy x¹. These bounds hold for any wx as long as wx is a valid weighting function. That wx will be a valid weighting function follows from its definition in equation 18. Because Theorem 1 allows us to directly bound the loss in performance for using an abstract policy, based on an abstract empirical model, in the original problem M, the amount of steps is polynomial only in |S] instead of [S].
As is typical with abstraction, there is a trade-off between the performance and the required number of steps: a coarser abstract model can potentially learn much faster but could sacrifice optimality, while a non-abstract model might have the best performance in the limit of infinite experience. We can see this trade-off in the results of Theorems 3 and 4. When we directly model M without abstraction, Theorem 3 shows that the algorithm will attain an expected return of Opt (Il,aa(e,, - 2e within a number of steps polynomial in (S), |A]. 11 Te. Theorem 4 shows that, when we use an approximate model similarity abstraction to learn abstract model, this leads to an additional performance loss of 3g("r- MR) due to the approximation. However, the advantage of using the abstraction is that the number of steps within which this is achieved is polynomial only in the size of the abstract space [S] rather than the (larger) original stale space |S]. Thus, these results show that the performance is not arbitrarily bad with approximate model similarity abstraction. Morcover, when the abstraction errors (Nr and na) are small and the reduction in state space is large, abstraction helps to reach near-oplimal performance siguificantly faster.
E
5 Related Work
The problem we resolved in this paper may seem intuitive, but as we will make clear here, it is a funda- mental problem in rich literature. Many studies have considered the combination of abstraction with either planning RL. Some studies avoid, or ignore, the issue of dependency by simply assuming that samples are independent (Paduraru et al., 2008; Ortner et al., 2014b; Jiang et al., 2015; Badings et al., 2022). Others avoid it by looking at convergence in the limit (Singh et al., 1995; Hutter, 2016; Majeed & Hutter, 2018) or by assuming access to an MDP model (Hallak et al., 2013; Maillard et al., 2013; Ortner et al., 2019).
RL With Abstraction. A negative result has been provided in the RIAO setting, showing that R- MAX (Brafman & Tennenholtz, 2002) no longer maintains its guarantees when paired with any state ab- straction function (Abel et al., 2018). For this negative result, they give an example that uses approximate Q" similarity abst (Abel et al., 2016). Our counterexample is more powerful: indicating problems with the analysis even for approximate model similarity abstractions (an approximate model similarity ab- straction is also an approximate Q' abstraction, but not the other way around). Nevertheless, our second result shows that it is still possible to give guarantees in RLAO for R-MAX-like algorithms when we use an approximate model similarity abstraction and take the yn and fr inaccuracies into account.
Another study considered setting related to abstraction, where the transition and reward functions can change over time, either abruptly or gradually (Ortner et al., 2020). The reward and transition probabilities depend on the timestep t, so T(s'ls, a, instcad of T(s'ls,)), a). They bound the variation in the reward and transition functions over time. By taking the variation over time into account they are able to give results. In their setting, the MDP is fixed given the timestep. However, in RLAO this is not fixed. Each time the transition function at a timestep could be different.
Recently regret guarantees have been found for the episodic (continuous) RL setting (Sinclair al., 2022). Their abstraction method learns an abstraction adaptively. The model-based version of their algorithm
12

---

Published in Transactions on Machine Learning Research (09/2023)
requires that the state and actions spaces are embedded in compact metric spaces. In this way, they can define a measure of the difference between state-action pairs in these metric spaces. However, they require oracle access to this metric. In our setting this would require knowing the transition and reward functions, which we assume we do not.
A Abstraction Selection. There are quite a few studies in the area of abstruction selection, where the agent has access to set of abstraction functions (state representations) 2013; Lattimore et al., 2013; Ortner et al., 2014a; 2019). Several studies assume that the given set of state representations contains at least one Markov model (Hallak et al., 2013; Maillard et al., 2013; Ortner et al., 2019). One study gives asymptotic guarantees for selecting the correct model and building an exact MDP model (Hallak et al., 2013). The assumption that an MDP model exists in the given set of representations is crucial in their analysis since the samples are i.id. for this MDP model. Similarly, other studies also assume that the given set of state representations contains a Markov model (Maillrdd et al., 2013; Ortner et al., 2019). They create an algorithm for which they obtain regret bounds, and their analysis also uses the Markov representation.
et al., 2013; Maillard et al,,
Some studies in abstraction selection do not assume the given abstraction functions contain a Markov model (Lattimore et al., 2013; Ortner et al., 2014a). Lattimore et al. (2013) deal with a more general setting where the problem may be non-Markovian. Instead of assuming access to a set of abstractions, they assume access to a set of models, including a model of the true environment. Since they are given models, they do not focus on learning them, making it very different from our setting. By observing the rewards obtained while executing a policy they are able to exclude unlikely models, and eventually find the true model of the environment. The other study (Ortner et al., 2014a) uses Theorem 2.1 from Weissman et al. (2003), which requires i..d. samples. We have shown that independent samples cannot be guaranteed in RLAO.
MDPs With Rich Observations. Other related work is in MDPs with rich observations or block struc- ture (Azizzaennsshlli et al., 2016; Du et al., 2019; Allen et al., 2021). In that setting, each observation can only be generated from a single hidden state, which means that the issue of non-i.i.d. data due to abstraction does not arise. We can view the rich observation setting as an aggregation problem, where the observations can be aggregated to form small (latent) MDP (Azizaaennshelli et al., 2016). Their setting is related to exact model similarity (or bisimulation) (Du et al., 2019). In contrast, in RLAO, each observation can be generated from multiple hidden stales, and we do not try to learn the MDP, as it is not small. Furthermore, we focus on approximate model similarity, which introduces the problems as described in Section 3.2.
L.ID. Samples. One way to avoid the issuc of dependent samples is by assuming that samples are obtained independently (Paduraru et al., 2008; Ortner et al., 2014b; Jiang et al., 2015; Badings et al., 2022). One study considers the setting with a continuous domain where we are given a data set with i.i.d. samples (Paduraru et al., 2008). They use discretization to aggregate states into abstract states and give guarantee that, with high probability, the model will be c-accurate given fixed data set. While they assume that the data has been gathered i.i.d., our results show that martingale concentration inequalities could be used to extend their results to the online data collection in the RLAO setting. Discretization has been used in another study in a continuous space (Badings et al., 2022). They search for a solution for a linear dynamical system, where the transitions are deterministic, except for an additive noise component. They assume this noise is distributed i.i.d. and try to learn the resulting abstract transition functions by iteratively sampling N samples per abstract-state action pair until a threshold is reached. They assume that samples can be obtained cheaply, e.g., through simulator, whereas we focus the exploration problem where data has to be collected online and is expensive. Another study operates in the abstraction selection setting (Jiang et al., 2015). While they do not assume that a Markov model exists in the given set of abstraction functions, they assume given data set, with i.i.d. data. They give a bound on how accurale 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 trivial since it mcans the data cannot just be collected ouline. Another study's primary focus is on bandits but also gives results for MDPs with a coloring function (Ortner et al., 2014b). We can view state aggregation as special case of this coloring. They extend the results from UCRL2 (Jaksch et al.,
13

---

Published in Transactions on Machine Learning Research (09/2023)
2010) to the setting with coloring function. They use the Azuma- inequality for the transition function, which holds for weakly dependent samples. However, they assume the samples are independent and do not show the martingale difference sequence property for the (actually dependent) samples.
Asymptotic Results. Another way to deal with dependence between samples is by looking at convergence in the limit (Singh et al., 1995; Hutter, 2016; Majeed & Hutter, 2018). One study gives an asymptotic result for convergence of Q-learning and (0) in MDPs with soft state aggregation (Singh et al., 1995). Tn soft state aggregation, a state s belongs to a cluster x with some probability P(z]s), which means a state s can belong to several clusters. Their result requires an ergodic MDP and a stationary policy that assigns a non-zero probability to every action. Together these imply a limiting state distribution, and they use this to show convergence asymptotically. Another study gives multiple results focusing on approximate and exact abstractions in environments without MDP assumptions (Hutter, 2016). Several of these results are in the planning setting, similar to other planning results for approximate abstractions (Abel et al., 2016). Most relevant for us is their Theorem 12, which for online RL shows convergence in the limit of the empirical transition function under weak conditions, c.g., when the abstract process is an MDP. Under this condition, however, the problem reduces to RL in an (abstract) MDP rather than RLAO. Follow-up work builds on some of these results and focuses on the combination of model-free RL and exact abstraction, also without MDP assumptions (Majeed & Hutter, 2018). They define and operate in a Q- Valuu Uniform Decision Process, with a mapping from histories to (non-Markorian) states and a "state-unine uniformiiy condition". The state-uniformity means that if two histories map to the same state 8, their optimal Q-values are also the same. They show that, under state-unfformity. Q-learning converges in the limit to the optimal solution. In contrast to our setting, they used an exact abstraction and left extending the results to approximate abstraction as an open question.
Planning and Abstraction. For planning in abstract MDPs, there are results for exact state abstrac- tions (Li et al., 2006) and approximate state abstractions (Abel et al., 2016). The results for approximate state abstractions allow for quantifying an upper bound on performance for the optimal policy of an abstract MDP, e.g., as in Theorem 1 for approximate model similarity in Section 2.3. A study built on these results by giving a result for performing RL interacting with an explicitly constructed abstract MDP (Taïga et al., 2018); since the abstract MDP is still an MDP, this is different from RLAO.
MBRL Using I.I.D. Bounds. Concentration inequalities for i... samples, such as the result from Weiss- man et al. (2003), are often directly applied to the empirical transition function (Brafman & Tennenholtz, 2002; Jaksch et al., 2010; Fruit et al., 2018; Bourel et al., 2020), without mentioning that these samples in a simple RL trajectory may not be independent as shown for instance by Strehl & Littman (2008) in a non-communicating MDP. 9 Strehl & Littman (2008) show that there dependence is not a problem because it is still possible to use a concentration inequality for independent samples, e.g., Hoeffding's inequality, as an upper bound, which implies that derived performance loss bounds are valid. However, their proof uses that transitions and rewards are identically distributed, which is not guaranteed in RLAO.
RL Using Martingale Bounds. Martingale concentration inequalities have been used regularly in online RL analysis (Strehl & Littman, 2008; Li, 2009; Jaksch et al., 2010; Lattimore et al., 2013; Maillard et al., 2013; Ortner et al., 2014b; Azizzadenesheli et al., 2016; Ortner et al., 2019; 2020). Our novelty is in using it in RLAO, where use it to show that we can learn accurate model and provide performance guarantees in this setting. Several works that employ martingale concentration inequalities are not in the RLAO setting or do not use them for the transition model, and instcad apply them to other parts of the analysis such as bounding the difference between the actual and expected returns (Strehl & Littman, 2008; Jaksch et al., 2010; Lattimore et al., 2013; Maillard et al., 2013; Ortner et al., 2014a; 2019). Other works do use martingales for a transition model (Li, 2009; Ortner et al., 2014b; Azizaaencshelii et al., 2016; Ortner et al., 2020). However, these either (implicitly or explicitly) assume samples be independent (Ortner et al., 2014b; 2020) or identically distributed (Li, 2009; Aviwadeneshelii et al., 2016), unlike our analysis. Since, we 2014).
9 An MDP is communicating if, for all 81, 82 E S, deterministic policy exists that eventually leads from 81 to 82 (Puterman,
14

---

Published in Transactions on Machine Learning Research (09/2023)
detailed in Section 3, independent nor identically distributed samples cannot be guaranteed in RLAO, their analyses do not extend to this setting.
6 Discussion and Future Work
Some assumptions we made, i.e., that the reward function is deterministic and each state in abstract state has the same reward function, can be relaxed. To accurately learn an abstract reward function, one should definne a suitable martingale difference sequence, after which Lemma 3 can be used. We considered approximate model similarity abstraction and used the properties of this abstraction to establish an upper bound on the difference in value between the original MDP and an abstract MDP under any abstract policy. This bound was imperative for our results. We established this bound by proof of induction on the difference in value for horizon n. This technique could be used to establish similar bounds and extend our results for other abstractions, e.g., approximate Q' similarity abstractions (Abel et al., 2016).
Our analysis showed how to extend the results of R-MAX (Brafman & Tennenholtz, 2002) to RLAO. Ex- lending results of other algorithms, e.g,, MBIE (Strehl& & Litlman, 2008) and UCRL2 (Jaksch et al., 2010), requires adapting to slightly different assumptions. For instance, R-MAX assumes ergodicity, while UCRL2 and MBIE assume the problem is communicating and non-communicating, respectively. Other algorithms sometimes use concentration inequalities other than Hoeffding's Inequality, e.g., the empirical Bernstein in- equality (Audibert al., 2007; Maurer & Pontil, 2009) or the Chernoff bound. To adapt these, we could, for instance, use Bernstein-type inequalities for martingales (Dzhaparidze & Van Zanten, 2001).
Theorem 4 shows that, despite problems with dependence, we can give finite-sample guarantees when com- bining approximate model similarity abstractions with MBRL. For good abstraction functions, i.e., when ijn and 'T are small and |S] > ($), this leads to near-optimal solutions while needing fewer samples, compared to learning without abstraction. Practically, for tabular methods, these results mostly mean that concen- tration inqqualities for independent samples have to be replaced in RLAO, for example by concentration incqualities based on martingales, we have shown here. In deep modcl-based RL, several recent empirical works have shown promising results by focusing learning exact abstractions (Biza & Platt, 2019; van der Pol et al., 2020). An interesting direction is adapting these methods to learn approximate abstractions instead of exact abstractions. Since, compared to exact model similarity abstractions, approximate model similarity abstraction generally results in a smaller (abstract) state space; this could lead to faster learning.
Our results shed further light on the observation from Abel et al. (2018) that RLAO is different from per- forming RL in an MDP constructed with abstraction. As our observations show, in RLAO the transition functions are not static, the samples are not identically distributed, and cannot be guaranteed to be inde- pendent. This could mean that in situations where we want to learn an abstraction, the behavior is also not quite as expected. In such situations, similar approaches that we applied here may prove useful, as many situations in RL have already been shown to not be independent processes. While our results hold for approximate model similarity models, there could be even more compact representations for which our techniques could lead to similar results. One clear example would be abstractions that focus not on state abstraction, but rather on state-action abstraction, of which state abstraction is simply a special case.
People have been applying MDPs and RL to all kinds of problems, even though we know that the Markov property very rarely holds. Given that almost all theory of RL critically depends on this property, one could wonder why these things even work? Intuitively, we expect that the states in these successful applications are somehow "Markovian enough". In this work, we provide an understanding of this vague concept. Specifically, we show that an existing criterion of state representations (approximate model similarity) in fact is a formal notion of "Markovian enough" in MBRL. Thus, provides critical insight into under what circumstances (and therefore in what applications) MBRL methods are expected to work.
7 Conclusion
We analyzed RLAO: online MBRL combined with state abstraction when the model of the MDP is unavail- able. Via counterexample, we showed that it cannot be guaranteed that samples obtained online in RLAQ
15

---

Published in Transactions on Machine Learning Research (09/2023)
are independent. Many current guarantees from MBRL methods concentration results that assume i.i.d. samples, e-g., Theorem 2.1 from Weissman et al. (2003), the empirical Bernstein inequality (Audibert et al., 2007; Maurer & Pontil, 2009), or the Chernoff bound. Because they use these concentration inequalities, their guarantees do not hold in RLAO. In fact, none of the cxisting analyses of MBRL apply to RLAO. We showed that samples RLAO are only weakly dependent and that concentration inequalities for (weakly) dependent variables, such as Lemma 3, are a viable alternative through which we can come to guarantoes the empirical model. We used this result to present the first sample efficient learning results for RLAO, thus showing it is possible to combine the benefits of abstraction and MBRL. These results showcase under what circumstances performance guarantees in MBRL can be transferred to settings with abstraction.
Acknowledgments
This project received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agree- ment No. 758824 INFLUENCE).
erc
Campust Dassser Count
References
David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state ab- straction. In International Conference on Machine Learning, 2016.
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong rein- forcement learning. In International Conference on Machine Learning, 2018.
Cameron Allen, Neev Parikh, Omer Gottesman, and George Konidaris. Learning markov state abstractions for deep reinforcement learning. Advances in Neural Information Processing Systems, 2021.
Jean- Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environ- ments. In International conference on algorithmic learning theory, 2007.
Kamyar Asizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning in rich-observation mdps using spectral methods. arXiv preprint arXi::1611.0399 2016.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 1967.
Thom S Badings, Alessandro Abate, Nils Jansen, David Parker, Hasan A Poonawala, and Marielle Stoclinga. Sampling- robust control of autonomous systems with non-gaussian noise. AAAI, 2022.
Aijun Bai, Siddharth Srivastava, and Stuart J Russell. Markovian state and action abstractions for mdps via hierarchical mets. In IJCAI, 2016.
Ondrej Biza and Robert Platt. Online abstraction with mdp homomorphisms for deep learning. In AAMAS, 2019.
George Boole. An investigation of the laws of thought: on which are founded the mothematical theories of logic and probabilities. Dover Publications, 1854.
Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening exploration in upper confi- dence reinforcement learning. In International Conference on Machine Learning, 2020.
Ronen I Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for ncar-optimal reinforcement learning. Journal of Machine Learningg Research, 2002.
Thomas Dean, Robert Givan, and Sonia Leach. Model reduction techniques for computing approximately optimal solutions for markov decision processes. In Proceedings of the Thirleenth conference on Uncertainly in artificial intelligence, 1997.
Richard Dearden and Craig Boutilier, Abstraction and approximate decision- planning. Artificial Intelligence, 1997.
16

---

Published in Transactions on Machine Learning Research (09/2023)
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 Machine Learning, 2019.
Kacha Dzhaparidze and JH Van Zanten. On bernstein-type inequalities for martingales. Stochastic processes and their applications, 2001.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span- exploration-eepllttaionn reinforcement learning. In International Conference on Machine Learning, 2018.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 2003.
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, 2013.
Wassily Hoeffding. Probability incqualities for sums of bounded random variables. Journal of the American Statislical Associalion, 1963.
Marcus Hutter. Extreme state aggregation beyond markov decision processes. Theoretical Computer Science, 2016.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 2010.
Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based reinforcement learning. In International Conference Machine Learning, 2015.
Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Arlificial inlelligence, 1998.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 2002.
Tor Lattimore, Marcus Hutter, Peter Sunchag, et al. The sample-comploxity of general reinforcement learn- ing. In Proceedings of the 30th International Conference on Machine Leurning, 2013.
David Levin and Yuval Peres. Markoe chains and mising limes. American Mathematical Soc., 2017.
Lihong Li. unifying framework for computational reinforcement learning theory. PhD thesis, Rutgers
University- Graitttte School-New Brunswick, 2009.
Lihong Li, Thomas J Walsh, and Michael L Littman. Towards a unified theory of state abstraction for mdps. In ISAIM, 2006.
Sridhar Mahadevan. Representation discovery in sequential decision making, In Proceedings of the AAAI Conference on Artificial Intelligence, 2010.
Odalric-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, 2013.
Sultan Javed Majeed and Marcus Hutter. On Q-learning convergence for non-markor decision processes. IJCAI, 2018.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint ar xrXic:0907.37400 2009.
17

---

Published in Transactions on Machine Learning Research (09/2023)
Ronald Ortner, Odalric-Ambrym Maillard, and Daniil Ryabko. Selecting near-optimal approximate state representations ions in reinforcement learning. In International Conference on Algorithmic Learning Theory, 2014a.
Ronald Ortner, Daniil Ryabko, Peter Auer, and Rémi Munos. Regret bounds for restless markov bandits. Theoretical Computer Science, 2014b.
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, 2019.
Ronald Orlner, Pratik Gajane, and Peter Auer. Variational regret bounds for reinforcement learning. In
Uncertainty in Artificial Intelligence, 2020.
Cosmin Paduraru, Robert Kaplow, Doina Precup, and Joelle Pineau. Model-based reinforcement learning with state aggregation. In 8th European Workshop on Reinforcement Learning, 2008.
Martin L Puterman. Markow decision processes: discrete stochastic dynomic programming. John Wiley & Sons, 2014.
Sean R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization in online reinforcement learning. Operations Research, 2022.
Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Learning without state-cstimation in partially observable markovian decision processes. In Machine Learning Proceedings, 1994.
Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Reinforcement learning with soft state aggregation. In Advances in neural information processing systems, 1995.
Alexander Strehl and Michael L Liltman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 2008.
Adrien Ali Taiga, Aaron Courville, and Mare G Bellemare. Approximate exploration through state abstrac- tion. arXiv preprint arXiv: 1aa11888.911111 2018.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undiscounted reinforcement learning in mdps. In Algorithmic Learning Theory, 2018.
Elise van der Pol, Thomas Kipf, Frans A Olichock, and Max Welling. Plannable approximations to mdp homomorphisms: Equivariance under actions. In AAMAS, 2020.
Tsachy Weissman, Erik Ordentlich, Gadiel Scroussi, Sergio Verdu, and Marcolo J Weinberger. Incqualities for the deviation of the empirical distribution. Hewlell- Hewlell-Puckard Labs, Tech. Rep, 2003.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. Advances in Newral Information Processing Systems, 2019.
18

---

Published in Transactions on Machine Learning Research (09/2023)
A
Well Known Results
We restate some well-known results that we use in the proofs in the other sections.
A.1 Hoeffding's Inequality
Hoeffding's 's inequality tell us the probability that the average of m random independent (but not neces- sarily identically distributed) samples deviates more than from its expectation.
Let 7 2222)..... ... (m)) be bounded independent random variables, and let and j be defined as
((m)
Z
(38)
m
E B + .... + Z(m))
(39)
Then Hoeffding's inequality states:
Lemma (Hoeffding's inequality (Hoeffding, 1963)) If (1) z(0) .... Z(m) are independent and 0 < z I
for 1,... m, then for <<<1- μ we have the following incqualities
Pr(Z - μ 2 e) 2me
(40)
Pr(IZ μ4 2 E) 2e 2mn
(41)
Pr
(2 n)) 2 e) S 2
(42)
i=1
Pr(
Σ (z μ1 2 é) $ 2e 2
(43)
1=1
A.2 Union Bound
Given that we have set of events, the union bound allows us to upper bound the probability that at least one of the events happens, even when these events are not independent.
Lemma 5 (Union Bound (Boole, 1854)). For a countable set of events A, A2, 'g, we have
Pr(U:A) & Σ Pr(AA))
(44)
Lee., the probability that at least one of the events happens is, at most the sum of the probabilities of the individual events.
A.3
Value Bounds for Abstract and True Models
Here we give upper bounds on the difference in value between the real MDP and an abstract MDP under various policies. We will use these bounds in Appendix D to adapt the results of R-MAX (Brafman & Tennenholtz, 2002) to RLAO. These bounds and proofs are very similar to existing bounds (Brafman & Tennenholtz, 2002; Strehl & Littman, 2008; Abel al., 2016; Taīga al., 2018). Here we repeat these for abstract models in the undiscounted finite horizon and in the discounted infinite horizon.
We define the finile horizon value function Vs E S:
(T. =
+ T(s'ss, (s)) (s).
(45)
Vol = R(s, T())).
(46)
We F to denote the value in M under policy म and aan. to denote the value in M under policy म.
19

---

Published in Transactions on Machine Learning Research (09/2023)
Theorem 1. Let M = AS, R) be MDP and M (S,A,T, R) on obstract MDP, for some defined abstract transilions and rewards. We assume that
V5,5's E, SES, :: (T5 s a) Pr(ss|ss ss a)l S nr
(47)
and [(s,a) - R(s, a)l - 7R.
Then, for a fivile horizon problem with horizon we have:
(*() - V (6) < 2 + (h - 1) BSma
(48)
And for a discounted infinite horizon problem with discount we have:
(*) - V (8) S 2UR 2
(49)
1-7 (1 (1-
We will use the following two Lemmas to proof the Theorem.
Lemma 6. Under the assumption of equation 47 and for every abstract policy म and for every state 8, we have: for fonile horizon problem with horizon h:
(F) - (s) S hmn + (h- - 1)h
Tr [S] Rimax:
(50)
2
and for a discounted infinite horizon problem with discount q:
V -s)
(+)1
7R S 1-7
mer |S| |m)
(51)
7)2
Proof. The proof follows the same steps for both the discounted infinite horizon and the undiscounted finite horizon. For completeness, we show them both here.
First, for the undiscounted finite horizon. By induction, will show that for
V3 E 5,8E8, (T))(s) [=**(s)] S mn + (n 1)m
Mr 15 RmRax
(52)
2
For n = 1, we have
(s) - (=.1 = [R(s, (8)) R(s, a())) & n--
(53)
Now assume that the induction hypothesis, equation 52, holds for n - 1, then
[V (*) (R(s,=(()) R(3,
Σ
T(s (66 ((s)) (6') Σ 7615
8'ES
(54)
< |R(s, - R(s,
Σ Σ (() (5') Σ 133
(55)
E'S
F'E3
< 1R Σ Σ T() (5') Σ ((mn-(()
T(51|s,7(3))
S'ES S'EF'
EEES
Σ VR. (x)) Σ T(5 - Σ (33) (3')
(56)
S'E8
S'Es'
< 1R +1
Σ Σ
((s)
- y (..m
Σ
Σ
FES
3'ER!
(57)
(n- - 1 () 1) 1/T S1 Bmax m (5 1) Rmax
1JR + (n
1)7 +
(58)
(n- 2)(n
1/R
T/T S) Bmax + m 1T 1)Rmax
(59)
2
(n- 1jn
nmj
Sr Ruuxx
(60)
2
20

---

Published in Transactions on Machine Learning Research (09/2023)
For the step from equation 55 to equation 56, we subtract and add Exes (8'= T(s' (()).
and from equation 57 to equation 58, we use the inductive hypothesis and the fact that (n 1) Rmax is an upper bound on (=*"= since the maximum reward per timestep is Amax-
Now, for the discounted infinite horizon. By induction, we will show that for n 2 1
(VT()) (B) (s)
7R7
Σ (nR
(61)
1-7
For 1, we have
(18)-vv- F.. (s) (s) = [R(s, r()) R(3, a())) & n--
(62)
Now assume that the induction hypothesis, equation 61, holds for 1, then
- = - (()) + 7(
T (()) (8) - Σ
18, (3))
EEES
E'ES
(63)
< [(s) - (()) + Σ Σ
T(s s (,) (5') Σ (()
(64)
FESSEER
S 1R +1 Σ Σ
T (())) (5))
Σ
(=. Σ T(3)s,,(33)1
FES 8'8
3'E8
EE'
+7| Σ
VT.a-
T(8'(s,(()) - Σ (5) (5')
(65)
S'ES
8'8
< nR +1 Σ
Σ
Tis'ss (s)) V 1 + Σ
(((')s,=(8))
Σ
T(s'ss, +()))
FES NES
F'E8
s'ES'
(66)
R-3
r (nn + M1r 11 (ar|S|Rmax, )) + tpp IS
Rinx
$ na + 1/107" 2
Σ
(67)
1
1-7
1=0
yd (nR + M/rl |5| + 5 Rmax
= TJ + 187"
+
(68)
1 1-7
1=1
7/ Rmax
"RY"" n-1
(1
+
(69)
1 1-7
For the step from equation 64 to equation 65, we subtract and add Eves (8)) Ever T(s'ls, (()).
and from equation 66 to equation 67, we use the inductive hypothosis and the fact that Rmax is an upper bound on (s").
1-y
Finally, taking the limit for + 0o, get:
Me |S|Rmax
(7))) < nn x 0 +
1 1-y (n +
7-7
a8 + 1 Riax
1-9 (1 7)2
Lemma 7. Under the assumption of equation 47 and for every state 8 E 8, we have: for a finite horizon problem with horizon h;
[x* (**((s)) S hnR + (h-1)h
m/ 11 Rmann
(70)
2
21

---

Published in Transactions on Machine Learning Research (09/2023)
and for discounted infinite horizon problem with discount Y.:
UR + Y/T Rmor
(V*(s) - (s) _ 1-7 (1 71-
(71)
Proof. First, we define
Aä V (s) max [(s,a) +7 Σ a aEA
(72)
e'ES
V**(s)
max aEA
[[(,,)) +7
Σ
T( (5')
(73)
#EE
For the undiscounted case ? 1, we can drop y from the notation.
The proof follows the same steps as the proof of Lemma 6. We start again with the undiscounted finite horizon.
By induction, we will show that for n 2
VE S 8: (s) - (3) S nnR + (n- - 1)m
mr mr| Rmax.
(74)
2
Making use of the fact that mmxx max gl < max |s g), we have for 1=1
IV* - [s)]
|| = max R(s, a) max R(5 a)) S max (R(s,a) R(3 a)l S SR.. aEA
(75)
aEA
Now assume that the induction hypothesis, equation 74, holds for 1, then
[V (8) [5) max aeA
((s,
R(5,a) + Σ T() (s') Σ T(
(76)
s'ES
< max aEd
|R(s, a) - R(s, a)l + max
Σ Σ
T(s' s ((s'|ss ( Σ
T(s T(s
(77)
3'ES'EES
3E8
< 1JR
max
Σ
Σ
T(d'(s,)) (5)
(on-l(8) Σ T(s|ss,))
aEA
F'E E'EB
E'ES
+ max
Σ v-m-1
T(E Σ
T(8'18, a) (-mm)((1)))
(78)
A
s'Eš
E'E
288
< 1J
max
Σ Σ
T(s'\s, - 1 + max
[T(''ss Σ
T(s' ((ss|s,a))) V
PES
S'ER
(79)
1R + (n - 1) + (n- (n-1- 1)
1/T |
Rmaax + ( 1)
(80)
(n
1jn
=1/JR
1/ Rmax.
(81)
2
For the step from equation 77 to equation 78, subtract and add EvES V= Eueg ((s'(ss,)) a), and from equation 79 to equation 80, we use the inductive hypothesis and again the fact that (n 1) Rmax is an upper bound on (3') since the maximum reward per timestep is Rmax-
Now, for the discounted infinite horizon. By induction, we will show that for n 2 1
22
(m + 7url 55r|51 Rmax
V8 W.ESS (V.M(s) - (R. S nnn "-1
(82)
1 1-7
For 1, we have
(s) (s)l mmx R(s, a) max R(5, a) < max [R(s, a) - R(s, & nn-
(83)
aEA
A
aEA
22

---

Published in Transactions on Machine Learning Research (09/2023)
Now assume that the induction hypothesis, equation 82, holds for 1, then
(s) - [5)] max a
[R(s,a) a) a)( +
Σ
(5) -y Σ
T(s ((5')3,0)) 0('' (84)
EE
SES
S max [R(5, a) - R(3, a)5 + max 7 aEA
Σ Σ
T (10'),a) ((615
(5') - Σ (3
(85)
aEA
FES
3E$
I nR + max 7
Σ
T(s'ls, |s, aV)
Σ
(3)m Σ T(s'|s,a)
AEA
V'E
RE8
N'EN'
maxx a
7|
V+
T(s'ss,)) Σ
T(s s0o5)\n
(86)
F'E3
S 1RR + max 7
Σ Σ
a)dlssa)( (5) - (p,m-1(8)) + max 7 Σ
[T
- Σ
ET(''s
T(s'ss,
A
dEA
H'E9 E'ER'
K'ES
8:E8'
(87)
3-3
r'(nR + mp | Rmax }) + mmrl S
Rmax
< + +
n
+
(88)
1
1
6=0
7 (nn + Mrr |5 |maxx
+ 1pr(( Rmax
njn =RRT""
Σ 1=1
(89)
1 7
1 1-7
n-2
(1 + u |S] Rmax
= n-1
(90)
For the step from equation 85 to equation 86, we subtract and add Eves V*.n- Ever T (())).
and from equation 87 to equation 88, we use the inductive hypothesis and the fact that RRax is an upper bound (3").
1-y
Finally, taking the limit for n + oo, we get:
1 MT |S| Rmmax
(+'6)- V-)) s X x0+ 1-7 (1R +
1 -
UR
+ 1S Rmmx
1 7-7 (1 7)
Proof of Theorem 1. We can now proof Theorem 1, by using the triangle inequality and the results of Lemmas and 7. For the undiscounted finite horizon:
(s) V (s)) S (s) (+*((s)] + (s) (s))
[s) - -s)( + 1 (0) - Va (s))
hmp + (h-1)h ur S Rmax + hnR + 2
1)h
mr |5) Rmax
2hnR + (h- - 1) 1)hrr |S| Rmax.
For the discounted infinite horizon:
(s) - v** (s)] S (s) - +*(s)++|V*G
+ (V'(s)
- V=" (s)
(s) V'((s] + 1 (s) V* v*((s)
RR + MPr (S| Rmax
1- + Mpr |S| Rmax
7R
1-7
(1 - 7)
(1 7)2
1-7 + 2ypr .S| Rmuxx
2na
(1 - 7)2
23

---

Published in Transactions on Machine Learning Research (09/2023)
A.3.1 Value Difference for Similar MDPs
Finally, we give a simulation lemma for two MDPs on the same state-action space. Lemma 8. Let M and M' be two MDPs on the same state-action space, with
Vs, E S x A: ( (M (8, a)l S 1R. Vs,a, & ES x A x S: (s'(('((s,)) -TM s, a)l S 1/2-
(91)
(92)
Then, for every policy a and for every state E S we have:
(n 1)n
MM Ms' (s) S wiR +
I [S] Rmor.
(93)
2
Proof. By induction, we will show that for n 2 1
(n- 1)m 1/T (S| Rmma.
S ( (s) (s)) S RnR +
(94)
For 1, we have
V ( (8) - VMr (s)l = (8, (s)) - RM (8, π [+)) S nn-
(95)
Now assume that the induction hypothesis, equation 94, holds for n - 1, then
VV (s) Vir (s) = (())) - RM (s, (())) + Σ (s)
(s
(s)) - Σ
The n.m
(s')l
M'
3'ES
S'ES
(96)
< (s, (8, +1 Σ [m (8) e'ES
(97)
#'ES
S AR Σ (n -M (s') Σ IMM (5')
SES
''ES
TM (s)) (5) Σ
- (s')l
(98)
SE
F'ES
< 1J
(5 (8) - VTr V Σ [TM(((1s=(5))
(s'1, (s))] vann-
(s')
EES
s'ES
(99)
(n 1 1)n11)nnn 1) M/ (rr|S1 Rmaax + mr (n- 1) Rmax
S MR + (n 1)1R=* +
(100)
(n 2)(nn -1-1
n/J
+
M/T S Rmax + nn(n - R)Js|
(101)
2
(n 1)m
= .JJR
Mrl [S) R
(102)
2
For the step from equation 97 to equation 98, we add and subtract Eves (s'lss,, (s)) (s'), and from equation 99 to equation 100, we use the inductive hypothesis and the fact that (n 1) Riax is an upper bound on yan-- As' (s') since the maximum reward per timestep is Rmax.
This shows that the values under any policy are similar for similar MDPs
B L1 Inequality for Independent but Not Identically Distributed Variables
We show that we can adapt the proof of Weissman et al. (2003) for independent, but not identically dis- tributed, samples to obtain the following result:
Lemma 2. Lel Xaa $1,".., 88m be sequence of states E & and let Yr,a = F(1), ((2).... (m)) be independent random variables distributed according to Pr(-)s1,a),.-. Pr(-Ism a). Then, Ve > 0,
Pr([[Tv(-13,)) a) -Tuy (15, a)ll e) s (21 2)e !mme
(103)
24

---

Published in Transactions on Machine Learning Research (09/2023)
Proof of Lemma 2. The proof mostly follows the steps by Weissman et al. (2003).
To shorten the notation, we define Py & (-(s,,,)) a) and Pax & Twx ())
We will make use of the following result (Proposition 4.2 in (Levin & Peres, 2017)), that for any distribution Q on 5
|1Q - Pwx 111 2 m Pax (5)),
SC8
where S is subset of S, and Pax (S) = -Eves Pux (5'). Thus, we have that
|p Pwx 111 2m2x (S) Paxx (S)).
(104)
SC8
Using this, we can write
2))= Pr - Paxlll 111 2) = Pr
2 max
(P((S) - Pax (8) _
(105)
SC8
(P Pax (8)] 2 c
Pr
max SCB
2
(106)
= Pr Usgs [Pr(5) Pax (8) 2 C
2
(107)
- Σ Pr ( (5)
(108)
SC$
where the last step follows from the union bound (Lemmn 5).
Assuming > 0, we have that Pr(Py Pax (S) 2 5) when S S= S or S = 0. For every other subset S, we can define a random binary variable that is 1 when y E and 0 otherwise. Here Pax (S) acts as μ (equation 39) from Lemma and (5) as Z (equation 38). Thus, by applying Lemma to this random variable, we have
PS(Py(S) - Pax (8) 2 6 S e 2m =e mmm?
(109)
2
Then it follows that
Pr( Pax 111 20) <
Σ Pr(Pv(S) (w)( ?
(110)
$gB
Σ
Pr(Pr(5) Pwx (8) 2 2
(111)
Sc
< (2) 2) im?
(112)
where S c. 5 + S,0 0 denotes that the empty set 0 and the complete set S are excluded.
C Proof of Main Result
Here we show how we can use a concentration inequality for martingales to learn an accurate transition model RLAO. Specifically, the following result shows that, with a high probability, the empirical abstract transition function Ty will be close to the abstract transition function Twx- In the proof, which follows the general approach of Ortner et al. (2020), define suitable martingale difference sequence for the abstract transition function and use this to obtain the following result for learning transition function in RLAO:
Theorem 2 (Abstract LI inequality). If an agent has access to a state abstraction fanction & and uses this to collect data for any abstract state-action pair (s, a) by acting in an MDP M according to a policy n, we have that the following holds with a probability of at least 1 - for a fized value of N(5
[|Tr(-|3, Tex (13,, a)ll S Se,
(113)
where 8 6= 21 22581-EENBB.))
25

---

Published in Transactions on Machine Learning Research (09/2023)
Proof of Theorem 2. We first define an abstract transition function based on X3,a as
N(a.0)
V(5.a), 8' Twx (51 a
Σ T($ a).
(114)
N(s,a)
where T(31X!00 s.. a) _ EVER ((s') x s.a We write Tax because this definition equivalent to using a
weighting function as in equation 19:
a(,, Tux (5)1,,a)
Σ
ax
Σ T()))s,a)
(Eq. 19)
(115)
SES
e'Ea'
N(E.a)
Σ
1 s.a =s} Σ a()
(116)
a(s,a)
SES
==1
s'EN'
N(s.a)
1
Σ
E1(x!0 8} Σ T(
(117)
a(5,a)
i=1
WE#
S'EF'
N(s.a)
1
Σ
Σ
T(sl[x a)
(118)
N(5, a)
==1
E'ER'
((s.a)
1
Σ
T(3ix a.)
(Eq. 114)
(119)
a(
Now we use z to denote a vector of size |S| with entries +1, and we write z(5) for the entry in z with index s. Then we have
[13,()),,) -wx (13, = Σ [T Tux (8)1,aa)
(120)
5¹
((Tr(E(1,,) -wux (8115,0))((3)
max
(121)
=c
1-1,8
N(3.a)
N(aa))
E( [(raa
Σ
118(0 = =57 a)
Σ
T(31X10)
(.a0 a) 2(3²) )1)2)))
max
a(
(122)
N(3,a
= =3)2(8') - Σ N(ā.))
1 3.0
N(s Σ
T
5,a1 a)2(3')
(
max zE( =E(-1,1)
a()
3
(123)
N(s.)
N(saa)
=E(-1,1)8 N(5,a)
max
(
(1)
F,a
N(3,a)
1
Σ
T(s x((
E.a a)2(3')
(124)
1=1
1=1
g
N(s.a)
max
(x(Y!.)) Σ ((3
(125)
=E(-1,1) N(F,a)
N(E.a)
max
Zy, (z. x(1)
2.a0 a, Y!ii
(126)
=E(-1,1) a(s,a)
where we set.
Zr, (z,
(10 (()
s.a: Or. 5.a
-(1)) 2 2(Y((0))
- ET('IIx00 g
5,a1 )2(8))
To show that Σ ((..0) Zy, (z, x-(3 8,a1 a,,, x((i)) is a martingale difference sequence, we should follow Definition
3 and show that Vi: F[Z.,, (z, x16)
5,a0 ar, 4((6) 1,,, Tmny" 7r.-1) 0 and |7,| < oc. For the second part, we
26

---

Published in Transactions on Machine Learning Research (09/2023)
have that Vi : 12,, (z, 8,07 Org vaa)) S 2, since (=(Y;a)) S 1 and E> T( g ar;) a,,))((3)| S part, use the following Lemma, the proof of which follows after the current proof.
For the first
Lemma 9. Let π be policy, and suppose the sequence $1,01 11.01... 11-1, 01-1, 8t is to be generated by x. If 1 < 12 < T--1 < Ti tt, then ElZ,, (z, X aa Or Y(.0 Zr, -, -
Lemma 9 shows that Σ (3,aa) Zr, (z, X (1) X
8, O ( is martingale difference sequence with Vi
12,, (2, s.a1 ar, v50) s 2 for any fixed and fixed N a) so that by the Azuma- Hoefa-ng inequality (Lemma 3):
N(s,a)
Pr Σ
2 Zy > c) Se SNGG,)
(127)
Similarly, Σ ((,aa)
N(s.jj Zr (z, X a, )2.0) is martingale difference sequence with Vi
(N(..o) Zr. x(i) inequality (Lemma 3), the following holds:
sias a7, Y!!) S N(a.0) for any fixed and N(5,a) n so that, by the Azuma- nooma-Ho
N(s.a)
Pr( ((5 0)
Σ
Zy > Se
S N(R.n)a ((,a))
(128)
N(5,0)
(129)
(N,,a))
(130)
From equation 120 and equation 126, we then obtain
1 M(s.a)
(-(()Ty(113,a) -Tx (-13, a)l2 t) PPr( max 2E{-1,11
Σ
Z > e).
(131)
N(5, a)
s=1
A union bound (Lemma 5) over all 21 vectors x for a fixed value of N(s, a) shows
1 N(sa)
N(s.0)
Pr( max xE(-1.1) ((s,a) a)
Σ Zr >))
Σ Pr(
Σ
Ur E).
(132)
N(5,a)
xE(-1118
1=1
So, using equation 130, we have that the following holds with probability 21 - N3..aee
[[Ty(113, Tax (-15, a)ll S. c.
(133)
Now we give the proof of Lemma 9:
Proof of Lemma 9. We follow the general structure of the proof of Lemma by Strehl & Littman (2008).
We have
X1) (1) (z,
ar,, y(0) = Σ Pr(er+1)) (z, (i) Cr,, Y
(134)
Cru+1
Pr(Cr.
Pr(Y s.a CT, ar, ) (z, x() a,, v.(0)
(135)
Ct.
p(0)
-Pr((e)) Pr(c..)
Pr(Y 3.a 1x
(1) 5,53 a, )Z x
Or. (.a).
(136)
Cri
5,0
27

---

Published in Transactions on Machine Learning Research (09/2023)
The sum Le,,+ is over all possible sequences Cr++1 that end in state +1,+1, resulting from T2 actions chosen by an agent following policy и. Conditioning on the sequence of random variables ZTi Z Z can make some sequences cr, more likely and others less likely, that is
EiZ (z, x(() s,00 aT Vo.0)) ZTi ZTs.".. Z
(137)
Σ Pr(cr, IZn, Z.z (T__,)
Σ
Pr(P x a,, Z,, (2, ar, Y.a)
(138)
Cr2
a, [r, a7,), fixed values of 2, 7:zi' " do not influence the innermost sum of equation 138. For this innermost sum, we have
Significantly, since P(V Br, a7;, 7 ",,,,,,,))) -1 = P(V..)
s.a
Σ
Pr(P x 8, 2,01 ar ) s.a An 810)
x!0
(139)
500
Σ
Pr(P
2,00 (T,))
x(P!(0) Σ
T s,a az))3))))
(140)
p(
Σ
Pr(y (1)
2,00 Cr, )ox)=((V))))
Σ
Pr(Y..d (0)
X ari) Σ
T(5'Ix ar )2(8))
(141)
p(0)
p(a
Σ
Pr(P(tt (1) (i)
s,a 8,0: Cr, )=(((()))
T(3 X (i)
8,0 Cr, )z(3)
(142)
2,0
0.
(143)
we conclude
El (z, ( are [(00) Bazz" ... ,2; ,1
(144)
Σ Pr(CT.] 1,7 2,z ... 7T(_)) Σ
Pr( (()
8:0 ar, (2, x10) xlaa,ar, az V(o))
(145)
Brct1
Pr(cT, 1Z, ".zg'... .. ,,,,,,r,) -TT-.))
(146)
(147)
D R-MAX From Abstracted Observations
Here we use the result of Theorem 2 to show that we can provide efficient learning guarantecs for R- MAX (Brafman Tennenholtz, 2002) RLAO. Appendix D.1, we use Theorem 2 and the value bounds in Appendix A.3 to establish two supporting Lemmas. Then, in Appendix D.2, we adapt one lemma and the guarantees of R-MAX to RLAO.
D.1 Supporting Lemmas
We can use Theorem 2 to determine the number of samples required to guarantee that the distance [-T,()),,)) - Twx (-Is, a)llı will be smaller than with probability 1 -- 8:
Lemma 10. For inputs and (0 < 1,0 2), the following holds for ramber of samples 21a(2151122) 1122)) mn)-l
Pr([ a) Tax (-15, a)lli 2 26)
S 26)5
(148)
28

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. To shorten the notation, use the definitions Py (-(1,,, and Pux Twx (-18, d). It follows
from Theorem 2 that
Pr(IlPy - - 111 2 t) S 21 me?
(149)
We need to select m such that x 2 e
K 2 2 51 E mmm?
(150)
h
2 E me?
(151)
2|S
me²
In(s) - In(2))))
2 8
(152)
me²
2 In - 1n(x)
(153)
([In(215) In(k)]
m
(154)
e²
Thus if 2 8[nn(2 (l)w)]) have
2
Pr(I Pax 2 2) S K.
7
We want to give results for an empirical abstract model M the abstract space from é, whose transition probabilities and rewards are within ir and n)n respectively, from those of an abstract MDP M. We use Van to denote the value in M under the n-step optimal policy and y to denote the value in M under the n-step optimal policy ** for M. The following lemma shows that we can upper bound the loss in value when applying A to M:
Lemma 11. Let M be on MDP, M an abstract MDP constructed using an approzimate model similarity abstraction 6, with nn and Wi, and M an MDP in the abstract space from & with
(T(3')3.)) - f(8'1,, a)l s s,, RR (((5,)))))))
(155)
Then
(s) - /$ "() S 2n1R + (n - 1)n(Tr + e)| Rmaz.
(156)
Proof. Note that assume that (/((5aa) i((3,a) a)l = 0 because assume deterministic reward. Then, we have
S |R(s, a) R(3, a)l S nR.
(157)
V5, E
Σ T(s'ss,)) ((s'(s,)) [,) S का + E.
(158)
S'E3'
We use f* (s) to denote the n-step value under the n-step optimal policy a .n n for the empirical abstract MDP M. Then, by Theorem 1, we have Vs 8,5555 5:
(s) - a (ss) = 2nmn + (n 1) ()r( + e) Rmaxx
(159)
D.2 Proof of Theorem 4
First, we restale an Implicit Explore or Exploit Lemma that is used in the proof of R-MAX. We are interested in the event AM, the event that we encounter an unknown state-action pair during an n-step trail in M. For two MDPs with different dynamics only in the unknown stato-action pairs, the probability that we encounter an unknown state-action pair in an n-step trial tiny if the difference in the n-step value between the two MDPs is slight. The proof follows the steps the proof of Lemma 3 from Strehl & Littman (2008).
29

---

Published in Transactions on Machine Learning Research (09/2023)
Lemma 12 (Implicit Explore Exploit). Let M be MDP. Let L be the set of known abstract state-action pairs, and let Mt be on MDP that is the same M on the known pairs (3,0) E L,, but different on the unknown pairs (3, a) & L. Let s be some state, and AM the event that an unknown abstract state action pair is encountered in a trial generated by starting from state 81 and following a for n steps in M. Then,
(x1) 2 V (81) - nnmaa Pr(AM). Pr(m)
(160)
Proof. For a fixed path pt = 81, a T1, :. 8t, at, ft, we define PrM (Pr) as the probability that Ps occurs when rumning policy x in M starting from state 81. We let Le be the set of paths pt such that there is at least one unknown state st in Pt (()(s)), a) L.). We further let (t) be the reward received at time t and ras (pe. t)
the reward at time & in the path Pt- We have the following:
B[ras (t) E[ra((t)
= Σ
(p()) (pr,t) (p(
(161)
ML
P.E
+
Σ
(prp)rra (pt,) M (pe,
Pr
(162)
Mz
PiLLe
E P.EL
(Pr (P)
(p..tt
(163)
ML
<
Σ P.ET,
Pr Pr(p)rm,, (pr, S Rmaa Pr(AM). Mr
(164)
Here Ep,e,, (PMM, (p.) MM (pt,t) (P:)(P)MM(() t)) because, by definition, M and Mr behave iden- tically the known statc-action pairs, and Ep.eL, Pras, (pe)ra, (pt,t) I Rmax Pr(AM is true because TMr (pr,t) 1) is at most Rmax Finally we can write
11
V Mr.
(s1) VM""(s)
= Σ (E [r (t) ((ras(()))
(165)
S Rmmxx Pr(Aas).
(166)
Thus, V7." 2 (s1) nBRmax Pr(AAs)
Now we are ready prove the theorem.
Thcorem 4. Given MDP M, approrimate model similarity abstraction o, with na and nr, and inputs [8), |ll,A,,,, e, Te. With probabilily of al least 1 1 8 the R-MAX algoritim adapled to abstraction (Algorithm 1) will attain an expected return of (c, in |S), 2::77 Te.
3 3 2c within a number of steps polynomial T.
Te. Here Te is the c-return mixing time of the optimal policy, the policies for M whose c-
return mixing time is Te are denoted by TT Te), the optimal expected -ssep undiscounted average return achievable by such policies are denoled by Opt[Iar(s (e)), and
11T- mr Rmaz.
g(m,, nR) = Tons +
Proof of Theorem 4. The proof uses clements of the Thcorem from Brafman & Tennenholtz (2002). The proof follows the following steps:
We show that the expected average reward of the algorithm is at least as stated the algorithm does not fail.
2. The probability of failing is at most 6. We can decompose this probability into three elements.
(a) Probability that the transition function estimates are not within the desired bounds.
(b) The probability that we do not allain the number of required visits in polynomial time.
(c) The probability that the actual return is lower than the expected return.
30

---

Published in Transactions on Machine Learning Research (09/2023)
Now first assume the algorithm does not fail. We define an abstract MDP Max constructed from ø with yr and nn- Similar to Mr., Max. is the same as Mwx on the known abstract state-action pairs, but with a self-loop and the maximum reward (Rmax) on the unknown abstract state-action pairs, i.e., V(s, a) $ L Twx [ = Rwy. R. = Rmax- We also define an empirical abstract MDP My, of which transition probabilities (y a) are within some 62 (defined later) of those Max and with Rex (5, a) = (5, a) because of the assumption that the rewards are deterministic. Then, My is the abstract MDP that is the same as My on the known abstract state-action pairs and the same Mwx.E on the unknown abstract state-action pairs. We denote the R-MAX policy with म.
Let As be the event that, following R, we encounter unknown abstract state-action pair (o(s), a) $ L in Te steps. From Lemma 12, we have that:
(6) VTr(() T, Rmax Pr(Aas). RA S: (
(167)
Now suppose that Rmax Pr(Ass) < c1, for some 6 (defined later), then we have
VT.T. (8)
V..
(8) T, Rmax Pr(Aar)
(168)
ML
V.R. (8) -Toc1
(169)
RRT.
Muxic (8) - -T2E1 - g(1T, 11R)
(170)
V (s) -Tcc g(E2) g(Tr. nR)
(171)
My.L
re (s) -TEE1 g(E2) - 9 1R)
(172)
My
M (s) -T.E1 g(E2) - 9( TR) - 2g( + E2, nR).
(173)
Here the step from equation 168 to equation 169 follows because of the assumption that Rmax Pr(AM)
G1 The step from equation 169 to equation 170 follows from Lemma 6, where g(Tr, na) Tenn
(T. -T-T mr Rmax- The step from equation 170 to equation 171 follows from Lemma 8, where g(t2)
(1: 11:311: e2 Rmax- The step from equation 171 to equation 172 follows because the R-MAX policy म is the optimal policy for My. and My. the same as My on the known statc-action pairs and overestimates the value of the unknown state-action pairs (to the maximum value). Finally, the step from equation 172 equation 173 follows from Lemma 11.
31

---

Published in Transactions on Machine Learning Research (09/2023)
In equation 173 the results are for the undiscounted T.-step sum of rewards, to obtain the result for the average reward per step, we have to divide equation 173 by Te. We get
Opt (c M
- ( nn)/TT 2g(nr (2, TT)
(174)
(T. 1)Ie
Opt( (pp(([((e)T)))) -1
EQ //axx//
2
(Te - (T)T
(Te 1)Te
(T.RR+ +
1/ ( )/Tx 2(I
(rr e2) Rmax)/L
(175)
2
Opt((] II (c) -1 (Te 1)
(2| Rmnax
'jn (Tc 11 A//l (rr|5] Rmax
2nn - (Te - 1) + (2) Rmax
(176)
II (c,T.) - -1 (Te [2) Rmax
Opt(
M
(Te 1)
37R
1/ Rmax - (Te |) - (Te - 1-)rr/ R|aax
(177)
2
(c,T.) - -1 (Te - 1)
(T. 2
1)
= Opt( II
62 c2|SS |m|x - 37n
Mr R
(178)
2
M
(Te - 1)
3 g (R)
Opt Op (e,
- 61 3
62 Rmax
(179)
2
Te
M
3
(Te - 1)
3 g(n m1)
Opt(
(e. T.)
3
(2 Rmax
(180)
8
2
Te
M
3
(Te
- 1)
3c
3 2 ma)
= Opt(
(c,T))
E
3
S) Rmax
(181)
8
2
S Rmax (Te 1)
T.
M
3
9
g(r MR)
Opt(] II
(c, T.))
E
c
3
(182)
8
8
T.
M
3
[ AR)
Opt[[ (c. T.)
Opt[
(183)
2
T.
M
In the step from equation 178 to equation 179 we use that g(Tr, TR) = TeuR (T.-1)Te mp |S| | Then, in the last steps, we define 6 and 62. In the step from equation 179 to equation 180 we set ei gec And in the step from equation 180 to equation 181 we set 62 = 3c/(4|5) Reaxs) 1)).
The above assumed that the algorithm did not fail, but we cannot guarantee this with probability 1 within number of steps that polynomial in the input. We will show that we can upper bound the probability of failure by 8. There are three reasons why the algorithm could fail.
First, we need show that the transition functions of My are within ?rr t of the transition func- tions of Maxi with high probability. This is to ensure that, once all the abstract state-action pairs are known, the loss of value because of an inaccurate transition model, V V is within 29(1r + 62, TR) 2T. (T. 1)T,(mr + (2) by Lemma 11. We can use the martingale concentration inequality to choose number of samples K₃ that the probability that 4 for every abstract state-
our transition estimate is outside the desired bound is less than 3|5|e|] action pair if we sample each pair K1 times. By Lemma 10, we can guarantee this by using K1 22|n -2) (n(5/(3)5) ADM 32]9[" R2 (T. (T.-1) (1) -1) Ln( 92a
Then, by applying the Union Bound on all AS|A pairs, we have that the total probability that any transition function is outside the desired bound is less than 8/3.
32

---

Published in Transactions on Machine Learning Research (09/2023)
2. Before assumed that Rmax Pr(AM) <a(= )) Here we can show that after K₂ Te-step trials where Rmax Pr(Aar) 2 3r all the abstract state-action pains are visited at least K1 times (become known) with probability of at least 1 - 8/3 by using Hoeffding's s Inequality. Let X; be the indicator variable that is if we visit an unknown abstract state-action pair in a trial, and otherwise. For the trials where
8
3c
Rmax Pr(X; = 1) 2
8
3c
Pr(X; = =) 8
|Rmax
use Hoeffding's Inequality to establish upper bound, we have:
K2
36 Rmaxx - -x)) 2 K2(3)
Pr
(184)
8
Pr(
3r K2
Σ Xi K2 2/33 Se
K2
21x
Se
2
R2
-2K
1/3
(185)
8
Rinax
1=1
K2
Pr( 8 Rinax
3r
K2
K2
Σ
Xi) SE < 2K
(186)
After K2 exploring episodes we want Σ X,, the number of visits to unknown state-action pairs, to be |||5||| A|. So we can choose K₂ such that 3e K guarantee that the probability of failing to explore enough is most 8/3.
3 Rmax K2/3 2 K||Š||A|, and e 22 S 5/3 to
3. Finally, the actual return may be lower than the expected return when we perform a T-sstep trial where we do not explore. We use Hoeffding's Inequality to determine the number of steps K3 needed to ensure that the actual average return is within c/2 of Opt(IIa (c, - e T. to choose K3 so that the probability of obtaining an actual return that smaller than the desired (c, T2)) - 2c - 3 gor..nn) is at most 6/3 within K3 = S exploitation stops, with some number > 0. Let X, denole the average return the i-th exploitation step and μ the average expected return in an exploitation step so that j is at least Opt([Inr(s T.)) - 3g(vr-na) Then 2,
( We need
Xi ---ix
2/3,2
Pr
K2/3)
Kg
c -2K
(187)
Rinax
This means that, with a probability of at most e 2K1/3 the average return for K3 exploitation steps is more than Bmax lower than K2
Ka
Pr
k2/31 'se"" -2K
(188)
Renax
K₂
Pr(K K3
X;
2 k2213]
(213){$ S -2K
(189)
Rmax
Rmax
i=
Kg
Pr(KsM
Σ
X, 2 Rmax K213) < -2K
(190)
2m1
Ka
Pr(u-
X;
Rmax
S -2K
(191)
K3
K 1/3
We can now choose Z, 80 that e/2 <
Rmax (
and e 222
S 8//3, to gel the desired result:
with probability at most 5/3 the obtained value will be more than c/2 lower than the expected value.
33

---

Published in Transactions on Machine Learning Research (09/2023)
The probability of failure is thus at most 3 6/3
= 6, and an average return at most 2e 3 30(0r.n)) ma) than Opt(IT (s,T)) will be obtained with probability of at least 1 - 6.
lower
T.
E Simulator Data Collection
Here we assume that we have access to simulator and use this in our procedure to give a guarantee in the form of the abstract L1 inequality from equation 21. To some extent, this is not surprising, but to the best of our knowledge, this is the first work that explicitly shows how lo combine MBRL and abstraction using a simulator. We assume that the simulator allows us to select (or move to) any state and draw a sample from its transition function, which we call the independent samples assumption:
Assumption 1 (Independent samples). We assume we cnn obtuin independent samples, e.g., for any state- action pair (s,a), we can drow somples directly from its transition function T(-ss,a).
Algorithm Procedure: MBRLAO
Algorithm 3 COLLECTSAMPLES with Simulator
Input: M, o, 8, T,
Input: M, 6, K
y = COILECTSAMPIRS( M,, d, 6,
A
The sampling results in soquences Ys,a; one for every
m 211 81 -2 ln(a]]
pair (3)
Ys.o 6(s())
,( ((s((m))
for all (3, E S x A do
= =²(11) (m)) ((m)
ys.- = []
for all (3,0,8) 8) E x A 3 do
Va.a = select a protolype state & E 8
(3' = L. m Σ. 1 1 8,0 55} end for
for = 1:m m do
s' Samplo(T(()Jã.ar a))
Y (pp.nd(d
My (5, A, 7)
end for end for Return: all Ys.a
ạ Value Myy)
Apply मÿ to M
If a simulator of the MDP is available, this is a reasonable assumption. For every pair (8, a), the simulator sampling procedure (Algorithm 3) selects prototype Iz,a E s from which to sample. We define a weighting function wx (s, a) that has a weight of 1 if s is the prototype V5,a and 0 otherwisc:
((SA))e (x( 1(s Tz,a
(192)
Then we use this wx to define the abstract transition function Tux according to equation 10. Tax (3) Ever' T(s'ls Is.a. a). This way, the samples collect for one pair (5.a) are i.i.d. They are independent because of Assumption and identically distributed because we sample from the prototype. Because the samples are i.i.d., we can use Lemma 1. We show that, with the simulator we can combine MBRL with abstraction and still learn an accurate model. We can guarantee that Ty will be close to Twx with a high probability:
Theorem 5. Under assumption 1, following the procedure in Algorithem 1, with the data collection from Algorithm 3 and inputs [8), A, e, and 8. For Ty constructed by the algorithm, we have that with probability 8, the following holds:
(a,) [T)(,)) - Tax (13,,))112 Sc
(193)
E.1 Proof of Theorem 5
Before starting with the actual proof, we first go over Algorithu 3 and give two lemmas the proof uses.
The agent will draw samples using the simulator as described in Algorithm 3. Since we assume we can sample directly from the transition functions T(-|s, a), this algorithm loops over all pairs (5, a) and samples m times 10
10 value of m in A Algorithmm 3 chosen based on the results further along this section.
34

---

Published in Transactions on Machine Learning Research (09/2023)
from each transition function. More formally, for every pair (s, the algorithm selects one prototype state Fs.a E 8. Then, it loops over every pair (5, a) and samples m transitions from T(- a). The set of collected experiences for each abstract state-action pair (s, a) is represented by Ys as defined by equation 15.
Given Ye,a, we define the learned model Ty (-Is, a) according to equation 16, Tux according to equation 19, and wx according to equation 192. Tt follows from Lemma ttatt we can derive number of samples that we require to guarantee that P (-13, a) -wwx (-15, a)lli 2 2e)
true for inputs K and
Lemma 4. For inputs and (0 < < 1,0 < 2), we have that the following holds for -22)
Pr[ a) Tux (-13, a)ll 2 c) S k.
(194)
Proof. To shorten the notation, we use the definitions Py a)3, and Pax & Twx (13,,). From
Lemma 1, we have that
Pr(IIPy Pax 111 20) (218) 2)e mm²?
(195)
We need to select m such that x 2 (21 - - mm²²
K (2) -2) me?
(196)
mm?
(197)
2 2
In(ss) (n(2
2) >
me²
(198)
2
mc²
2 1n(2151 -2) 1 In(x)
(199)
2
2 21
2) In()))
m
(200)
22
Thus, if m 2 (11(2))1-2)--mdt we have
Pr(plpy - Puxl11 s S
Using the Union bound, we can give lower bound the probability that Ty (-1,, a) and Tax (115,a) close for every (3)
Lemma 5. If
5
(((a) (+15) - -wa (13,, a)ll2 20) s |
(201)
then the following holds with probability of at least 1 8:
max (11,y( Tax (-13, se. (8,a)
(202)
Proof. We define
A.. A Ty a) - TTu (113, (11.0)
(203)
Then (x,) 2 e}) is the probability that Az, 2 E for at least one abstract state-action pair. From the union bound, follows that Pr(mmxx (As 2 2(])= S::
Pr(max Ar. 2 2 S Σ (3,0)
Pr( ( 2 c)
(204)
3,4
8
(205)
|
3.4
8.
(206)
35

---

Published in Transactions on Machine Learning Research (09/2023)
It follows that ar <)) 2 1- 8 since Pr(max AA,,a S <c)) (r(mmxx {As,a e)). Thus the probability that equation 202 holds is at least 1 - 8.
7
Now we are ready to proof Theorem 5:
Proof of Theorem 5. By Assumption 1, and the earlier assumption that [S] and |A] are finite, we have that we can obtain m samples in finite time for every abstract state-action pair and any m > 0. Given the inputs [5], A, e, and 6, Algorithm sets m = 2 2) [ where x [S||A] Then, for every (3,4), a prototype state Iz,a = = is selected. We use equation 192 to define wx and equation 19 to define Twx.
For all (8, a), Algorithm 3 obtains sequence Ys,a by sampling from the transition function from the prototype state Ts,a and Algorithm constructs the empirical transition functions as in equation 16.
Given our choice of and the inputs [a||a]
and e, it follows from Lemma 10 that
8
((,0))
Pr((ITy(155, Tax (,13, a)ll S
(207)
|
By the union bound, we have that the following holds with a probability of least - ō:
(s,0) (-(5,)), Twx (15,a))l1 S.
(208)
36


Reviews:
[{"review_id": "izHdZmXxfE", "reviewer": "Reviewer_gAF9", "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 was a reviewer on a previous version of this paper, and maintain a similarly positive outlook on the work. Additionally, many of the low-level suggestions from my earlier review have been addressed. As such, I still believe in what I had earlier identified as strengths. At the same time, some of the weaknesses of the work have since been addressed, and I believe the present work is a strong contribution that some among the TMLR community will find valuable.\n\n[STRENGTHS]\n\nOverall, this paper is clean, focused, and delivers a new result combining two prominent ideas in RL. While variations of some of the pieces of these ideas have appeared in the literature, I believe what is offered in this paper is novel and could be of interest to the community. Moreover, the survey of literature is sufficiently both broad and deep. Most relevant work is cited and discussed.\n\nClarity: First, a note on clarity. The work takes care in developing its main ideas, and is thorough in laying out the important definitions. Each definition is precisely stated with clean notation. I found the whole paper easy to follow.\n\nNovelty: To my knowledge, the main results (Theorem 3/4) are novel, and I believe are nice results for the community in tabular MBRL and state abstraction to be aware of. Some of the underlying ideas (moving from i.i.d. to martingales) have been explored before in similar analysis, and naturally a big focus of MBRL is in \"planning in latent space\" (Hafner et al. 2019), but this particular set of insights and results are new.\n\nThe primary TMLR criteria are: (1) \"Are the claims made in the submission supported by accurate, convincing and clear evidence?\", and (2) \"Would some individuals in TMLR's audience be interested in the findings of this paper?\". I find the answer to both questions, \"yes\", and consequently, I recommend acceptance.\n\n\n[WEAKNESSES]\n\nThe scope of the results is potentially limited. Aggregation functions capture only a small subset of possible ways to model state representation, and as such, it is not immediately clear what kind of applied algorithmic insight we might gain from the work. In light of this, I still find the main ideas and analysis useful and interesting. I do appreciate Section 5 that hints at possible future directions, but I still believe further expanding this section to present a broader consideration of how the work might yield new insights could be useful. For instance, how might the shift from the i.i.d. assumption to the martingale assumption impact algorithm designers that are interested in developing deep MBRL approaches? A few words in this direction could be useful. Are there any practical considerations, guidelines, or new predictions we can draw? This is not strictly necessary for publication, but I believe could strengthen the work.", "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 studies state abstraction in model-based reinforcement learning (MBRL). The primary focus of the work is on combining the dimensionality reduction offered by state abstraction with model-based planning into a learning algorithm (typically those that rely on  exploration strategies that center around planning, such as R-Max). However, the work highlights the fact that in MBRL with state abstraction, i.i.d. sampling of the appropriate data cannot be assumed, contrary to the assumptions required to make use of standard concentration inequalities like Heoffding's and Wiessman et al.'s. In light of this, the paper draws on more general concentration inequalities for martingales that yield the same kinds of simulation-lemma like results we would expect in tabular MBRL. The first result, in my opinion, are observations 1, 2, and the counterexample. While similar issues have been identified in the past, I believe it is quite useful to have a clear counterexample such as this. Then, Section 3.2 explores abstracted MBRL beyond the i.i.d. assumption: martingales are introduced alongside Azuma's inequality, which is then used for a concentration inequality on model accuracy. These ideas are combined to produce Abstracted R-Max (Algorithm 1), along with its analysis, which together constitute the main results of the work (Theorems 3 and 4).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My only high-level comment and suggested change is to carefully rethink the term \"Abstracted RL\". I am not sure that the name \"Abstracted RL\" is buying you that much at the moment. Personally, I find it slightly confusing, as it is unclear whether it is describing a _problem_, or a class of _solution_ to the RL problem. It is introduced as a \"setting\", but I find this slightly vague. I do find the figure helpful (Figure 1). I suggest either dropping the term, or defining the term more precisely. For instance, when you say \" In fact, none of the existing analyses of MBRL apply to Abstracted RL\", is this suggesting that guarantees for existing algorithms do not hold under a specific set of conditions? If so, what exactly are these conditions? I could charitably interpret Figure 1 to include the RL problem when $\\phi$ is the identity function, for instance. Is it specifically the case when $|\\bar{S}| << |S|$? This still wont quite fully specify the problem as distinct from the RL problem when the underlying MDP is uncompressed.\n\nSecond, I include a small number low-level writing suggestions below that I believe will strengthen the paper:\n\n_1. Introduction_:\n- \"((e.g., ...)\": You can remove the double parenthetical and the \"e.g.\" here, and just state \"...typically (Strehl & Littman...\".\n- \"The outline is as follows:...\": Since it is only a 12 page paper, I am not sure the outline is strictly necessary. If you need space, I would encourage removing this paragraph, as well as the first paragraph of the Background section.\n\n_2. Background_:\n- You might introduce $R_{max}$ explicitly alongside the MDP and reward function since it will appear later.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CqrJGFjwUo", "reviewer": "Reviewer_DDAA", "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 main strength of this submission is that the paper is fairly well written. The prose is easy to follow. \n\nThe main weakness in my opinion is that it is really unclear how deriving a simple martingale bound is a novel or useful thing. Lots of existing analysis of online PAC and regret algorithms for Reinforcement Learning (see algorithms like UCBVI and others) already rely on martingale bounds for their analysis. This is in my opinion not really a surprising or new contribution. For example (Near-optimal Regret Bounds for Reinforcement Learning) already heavily uses martingale arguments in their analysis. \n\nAn extra concern is that it is unclear in definition 2 what is the nature of the $\\omega$ function. This is a concern because then it is argued that $\\omega_X$ will be an estimator of this quantity. It is unclear what this $\\omega_X$ quantity will converge to because it depends on the sampling policies that will be used to explore the MDP. If at different points in time there are different ways of arriving to different (non-abstract) states, then the empirical estimators of $\\omega_X$ will converge to different quantities. Because of this I find it very suspect that Theorem 4 does not have a dependence on $S$. ", "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 work studies the setting of Abstracted Model-Based Reinforcement Learning. The authors introduce an analysis of the RMAX algorithm for this setting based on a martingale analysis.The authors claim the previous analyses relied on independence of samples and thus were not suitable for modification in the abstracted model based setting. The authors main contribution is to instead derive a martingale bound for abstracted MDPs that can be plugged in seamlessly into the analysis of algorithms such as RMAx to obtain PAC-like bounds for RL.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The issues specified above are important. Responding to these would be paramount to decide wether this work should be admitted or not into TMLR.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9PnuS4pNKS", "reviewer": "Reviewer_6VFG", "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 paper is written-well and discusses prior work well. The problem is setup is fairly well motivated.\n\nI think the paper deals with a very narrow setting, i.e. the negative result presented in the paper corresponds to a particular method category (model-based RL in this case) as well as a specific analysis. Furthermore, the main issue of concern is shown to be the sample independence when collecting data online, but that has little to do with the kind of state abstraction considered but more around the observation that the state abstaction (when not exact) leads to a POMDP setting. The actual issue with the model-irrelevance state abstraction seems to be the samples not being identical, but (as the authors show), that can be easily remedied. Therefore, overall I think the insights from the paper are too narrow and do not benefit a larger audience.", "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": "The paper discusses model-based RL over abstracted states, specifically using a model-similarity/model-irrelevance state abstraction. The authors show that when the data is collected online, we cannot learn an accurate model of the abstract MDP because the samples from a given abstract state are not iid. They then show that samples being identically distributed is not required, and resolve for the indepence issue using martingale bounds. Finally, they use this insight to prove convergence for the abstracted version of the R-Max algorithm. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The primary issue raised in the discussion repeatedly about the main theorem of the paper was that it proves convergence of a certain estimator to a quantity defined by the algorithm presented in the paper and the reviewer was not convinced that this result in particular would be of significant use in the community. I agree with this review and the full significance of this result is not clear. The authors have not been able to convince the reviewer about this point despite a revision.

My recommendation for this paper is based on the TMLR evaluation criteria and further discussion with the TMLR chief editors -

1. Are the claims made in the submission supported by accurate, convincing and clear evidence?
2. Would at least some individuals in TMLR's audience be interested in knowing the findings of this paper?

Criteria 1 is clear from the reviews and discussion. All the reviewers understand the main result in the paper and agree on its correctness. Criteria 2 remains unclear. The main question is whether the main result of the paper is itself of value and has the paper done enough to bring that out. The topic of the paper is clearly relevant to the community. Upon consideration of all the reviews, discussion and revision and upon conferring with the chief editors, I believe that while the paper is not completely upto the mark on point 2 of the criteria, there will be some members of the community who might be interested in the result (eg one of the reviewers). Therefore I am recommending a borderline Accept.

I suggest the authors take into account the suggestions made by the reviewer regarding the significance of the result and understanding how to further elaborate and strengthen the usefulness of their result.
Decision: Accept (poster)