Provably sample-efficient RL with side information about latent dynamics
Authors: Yao Liu
Dipendra Misra
Miroslav Dudík
Robert E. Schapire
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
Reinforcement Learning Theory
Transfer RL
Sim-to-real

Abstract: We study reinforcement learning (RL) in settings where observations are high-dimensional, but where an RL agent has access to abstract knowledge about the structure of the state space, as is the case, for example, when a robot is tasked to go to a specific room in a building using observations from its own camera, while having access to the floor plan. We formalize this setting as transfer reinforcement learning from an "abstract simulator," which we assume is deterministic (such as a simple model of moving around the floor plan), but which is only required to capture the target domain's latent-state dynamics approximately up to unknown (bounded) perturbations (to account for environment stochasticity). Crucially, we assume no prior knowledge about the structure of observations in the target domain except that they can be used to identify the latent states (but the decoding map is unknown). Under these assumptions, we present an algorithm, called TASID, that learns a robust policy in the target domain, with sample complexity that is polynomial in the horizon, and independent of the number of states, which is not possible without access to some prior knowledge. In synthetic experiments, we verify various properties of our algorithm and show that it empirically outperforms transfer RL algorithms that require access to "full simulators" (i.e., those that also simulate observations).

Provably sample-efficient RL with side information about latent dynamics
Yao Liu" Amazon Web Services yaol Camazon. com
Dipendra Misra Microsoft Research
dipendra. www.mmiiiiiiimmm.mmmmmm.mmmii www.w/iwwccoo.....oo..oooooooo.m com
Miroslav Dudík Microsoft Research aduuiik@iccoooofee com
Robert E. Schapire
Microsoft Research
schapireemmicroooft com
Abstract
We study reinforcement learning (RL) in settings where observations high- dimensional, but where an RL agent has access to abstract knowledge about the structure of the state space, to a specific room in a building using observations from its camera, while having access to the floor plan. We formalize this setting as transfer reinforcement learning from an abstract simulator, which we assume is deterministic (such as simple model of moving around the floor plan), but which only required to capture the target domain's 's latent-state dynamics approximately up unknown (bounded) perturbations (to account for environment stochasticity). Crucially, we assume no prior knowledge about the structure of observations in the target domain except that they can be used to identify the latent states (but the decoding map unknown).. Under these assumptions, we present an algorithm, called TASID, that learns a robust policy in the target domain, with sample complexity that polynomial the horizon, and independent of the number of states, which is not possible without access to some prior knowledge. In synthetic experiments, we verify various properties of our algorithm and compare it with several transfer RL algorithms that require access to "full simulators" (i.c., those that also simulate observations).
the case, for example, when robot is tasked go
Introduction
When learning from scratch, reinforcement learning (RL) in the real world be very expensive. For example, robot learning to navigate in building might need to explore every possible state or location, which can be painstakingly costly and time-consuming. Sometimes, however, is not necessary to begin such a learning process from scratch. For instance, in the robot example, we might have access to a general floor map of the building. How can this kind of high-level but imprecise information be used to learn how to operate in the environment more quickly and more effectively?
In this paper, we study how to effectively leverage prior information in the form of such "abstract" descriptions of the environment. We formalize this abstract description as an "abstract simulator," which, like map, can be used imperfect model. Importantly, from more standard simulators in that they only focus on the "latent structure" of the environment dynamics, on the observations that might be experienced by an agent in the environment.
abstract simulators differ
In general, fully faithful simulators of even the latent dynamics might be hard to build, for instance, due to the difficulty of exactly modeling all probabilistic outcomes, when the robot's actions do
'The work was done while the author was an intern at Microsoft Research and graduate student at Stanford.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

robust abstract policy
target environment policy
P
π
robust dynamic programming p arg max min .M
f1
inverse dynamic models
fn
M
high-dlimensional observations
perturbed transitions
stochastic target environment
deterministic abstract simulator
Figure I: Overview of our setup. We propose an algorithm TASID that learns robust policy я in the target environment using side information in the form of fully specified deterministic model, called an "abstract simulator." Abstract simulator approximates (possibly stochastic) latent dynamics of the target environment and thus serves as an idealized description of the the environment. The policy i selects its actions according to the robust abstract policy p. but the latent states need to be inferred from high-dimensional observations using learned inverse dynamics models.
not have exactly their intended effect. More complex simulators might be more faithful, but simpler simulators might be easier build and also more computationally tractable.
In this paper, we address this trade-off with a particular design choice: First, we assume that the abstract simulator is deterministic. Indeed, ordinary map, which implicitly represents what new position will be reached by a particular action, is such a deterministic model. Compared to fully probabilistic models, deterministic ones are especially simple build and work with.
On the other hand, deterministic model will not in general capture the "noise" of real-world dynam- ics. Therefore, we seek algorithms that will learn policies that robust errors or "perturbations" in the model represented by the abstract simulator. To this end, in Section we present a new algorithm called TASID that provably finds policy achieving a certain level of performance for any target environment whose dynamics can be reasonably approximated by given abstract simulator, up to some quantifiable perturbation level, and with arbitrarily different observations. (Figure ] visualizes our setup and approach.)
In the robot example, although map is intuitively helpful for reducing the need for exploration, there is still much to be inferred, for instance, how locations on the map correspond to locations in the building, and, even more challenging, how they correspond to rich, high-dimensional observations experienced via cameras or other sensors. Our algorithm solves these challenges, building on prior work on learning from such observations (Krishnamurthy al. 2016 Jiang et al.) 2017).
Furthermore, our theoretical guarantees show that we do indeed save dramatically on sample com- plexity (measured by the required number of interactions with the target environment) by not having to explore the entire environment, and instead focusing the task of learning observations just to the states that lead towards accomplishing the task. Indeed, our algorithm's 's sample complexity is entirely independent of the size of the state space, assuring efficiency even when the state space is extremely large, as is often the case. We are able to achieve this result because of specific assumptions and criteria for success, as outlined above, namely, detemmmteriiiiiccc latent dynamics, knowledge of the abstract simulator, and the benchmark of robust policy rather than optimal policy.
In Section 5 we empirically evaluate TASID in two domains. The first represents a challenging prob- lem requiring strategic exploration. We show that TASID is able to efficiently achieve the robust policy value while the PPO algorithm (Schulman et al. 2017 augmented with exploration bonus [Burdd et al. 2019b) and domain randomization [Tbin et al. 2017] does not solve the problem. The second domain is a visual grid world that tests the robustness TASID to dynamies perturbation and the change of state-space size. We show that TASID succeeds empirically in agreement with our theory.

---

2 Related Work
Transfer RL. The goal of transfer RL is to speed up learning in a target environment by leveraging model (or some other form of knowledge) learnt in source environment (Taylor and Stone 2009 Lazaric| 2012]. For our setting, the most relevant are the methods that can transfer between environments with different observation spaces. The dominant line of research requires access to hand-coded inter-task mapping, which is used to introduce constraints, shape rewards, or warm-start learning the target environment [Taylor and Stone, 2005| Taylor et al., [2007]] Fernández et al.)
2010, Mann and Choe 2013 Brys et al. [015]] Instead of hand hand-coding, several works seek to learn inter-task mappings using structural information such as factorization [Liu and Stone, 2006 Taylor et al. 2007b Soni and Singh 2006]. Van Driessel and Francois- Maancois-LLveet [2021] and [Sun et al. [022 do not require such structural information, and only posit assumptions similar to our block MDP assumption, but without requiring near-deterte wear-deterministicc latent dynamics. Latent dynamics learnt in the source domain is used to create auxiliary tasks that regularize learning in the target domain.
These methods show empirical promise of transferring information about latent dynamics. Their focus is mainly on modeling and experiments, whereas our work also seeks to derive theoretical guarantees that showcase the benefits of transfer. We derive sample complexity that is independent of the size of the state space and observation space, which would be impossible without transfer. Among the cited works, Mann and Choc [2013) also show benefits of transfer, but their sample complexity generally scales linearly with the size of the target observation space. The strong bound that we derive requires a metr-deteriiiistic latent dynamics, and so it is not as broadly applicable.
Provably efficient RL with rich observations. Our modeling setup and theoretical analysis build on the prior work that considers large-dimensional "rich" observations, but simpler (tabular) latent al., 2016 Jiang et al., 2017 Du et al. 2019]. To circumvent the hardness of learning in general pabterel MDPs (POMDPs), these methods impose structural assumptions, such as the block MDP assumption used here These methods, like ours, learn with sample complexity that is independent of the size of the observation space. but, unlike ours, that is polynomial in the size of the latent state space. Using existing MDP lower bounds (Kakade] [003). this dependence is unavoidable for general latent dynamics, even when the decoding function of observations latent states is known. We overcome this fundamental obstacle by assuming that the latent dynamics is near hear-deterministic, and the deterministic approximation is known.
dynamies [Krishnamurthy
Robust RL. Our solution concept and the underlying algorithm build on robust dynamic programming methods [yynngar] 2005 |Bagnell et al. 2001]. However, we are using this concept in a fundamentally new way achieve sample complexity improvements in transfer learning. This is one of the key conceptual innovations of our work.
3 Problem Setting
We next formalize our modeling setup and assumptions. As running example, we consider navigation problem on floor of a building, where the goal is to reach a certain location by a robot that can turn left and right and move forward. The robot senses the environment via lidar readings and/or a camera, but it does not have access to its position or orientation. We use the notation ((S) for the set of probability distributions over set S, and [n]] denote the set {1.2.....
3.1 Target environment
We assume that the target environment is a block MDP (see, e.g., D.g.,Du Du ct al. 2019 Misra et al. 2020
Zhang et al. 2020). In a block MDP, observations are high-dimensional (c.g.. lidar and camera readings), but emitted by a finite number of latent states (c.g.. location and orientation of a robot); latent states are not directly observed, but they can be determined from the observations they emit.
Formally, block MDP a triple M (M. q). The first component of the triple is a standard episodic MDP M = A, Smi, T, R). referred to as the latent MDP, with a finite state space S, referred to as the latent state spuce, a finite action space A, initial latent state Sinits horizon H, transition function T [H] x S x A + ASS), and reward function R [H] x S x A - [0, 1]: transition probabilities and reward function values are written as Tx(s' 8, a) and RA(s, a). The second component of the block MDP triple is observation space X, which is typically large and
3

---

possibly infinite. The final component is an emission function q S - A which describes the conditional distribution over observations given any latent state; its values are written as q(s) x)).
We assume that satisfies the block MDP assumption, meaning that there exist disjoint sets (2, sES such that if x ~ q(- s) then Xr with probability 1. This means that there exists perfect decoder ØM: X' + S that maps an observation x to the unique state (M()) that emits it.
An agent interacts with block MDP in a sequence of episodes, each generated follows: Initially, $1 = Simit At each step = I,..., H, the agent observes Iy ~ g(. 8n), then takes action dg. accrues reward th R2, (s), a4) ) after which the MDP transitions to state 84+1 ~ (- [ 8%, 04). The
agent does not observe the latent states 8h, only the observations Th and rewards Th. Observations and actions up to step h are denoted X1:h and a1:h-
We denote the block MDP describing the target environment by M (M",X,g")) where Rt)
M = (SS,A, Simit; H, "** is the target latent MDP. The perfect decoder for M is denoted as o²
mnon-Markovian) practicable policy. A practicable policy prescribes which action to take given any sequence of observations, i.e., is mapping X + A. where X = 0 2 The action taken by on X1:h is written ny (X1:)). The expected sum of rewards in M, when actions an are chosen according practicable policy π, i.., when a₁ n (X1=i.). ), is referred as the value of π in M and denoted VM= EM.=/r; + +.......... ra]; the subscript in the expectation signifies the probability distribution over episode realizations when the environment follows M, and actions are chosen according to æ.
Practicable policy. Behavior of an agent in a target environment is formalized
We also allow practicable policies to be (Markovian) mappings π [H] x X + A which choose every action according the last observation, so that a, Ta (T(aa for all h. Whether particular practicable policy is Markovian or not will generally be clear from context.
3.2 Abstract simulator
Our learning algorithm can interact with the target environment, but it additionally has access to an abstract simulator, which provides an idealized and abstracted version of the target environment. Formally, an abstract simulator is an episodic MDP denoted M = (S. A. Sintt H, T R³), with the same state space, action space, start state and horizon as the latent MDP M but not necessarily the same transition and reward functions. Furthermore, we assume that abstract simulator is deterministic:
Assumption 1. The abstract simulator M is deterministic, ie.,, Th (8h+11 8h, as) {0, 1}.
In order for the abstract simulator to be useful, it must approximate target environment. In this paper we assume that the target environment can be viewed as a "perturbed" version of the abstract simulator, using a notion of perturbation inspired by the concept of trembling-ham equilibria from extensive-form games [Selten 1975). Specifically, we say that an MDP M' is an pertuuurbbttion of another MDP M if its dynamics can be realized by following M's 's dynamics while distorting agent actions according to some (unknown) "noise" distribution, referred as & in the definition below, which keeps actions unchanged with probability at least 1 r7.
Definition (n--perturbation). We say that an MDP M' =SS, A, Simit, H. H.T', Rt) is an r/-eeruurbation of an MDP M. (S, A, Smits H, T, R2 if there exists a function E [H] x S x + A(A) that satisfies &n (a| 8, x,a) 2 1 for all h, and such that
(5 (s,a) EW'e (n'ss [s d''E (a' ss)a)
Ry (ss a) =o'es d' a)
for all h, s, a, s'; thus MDP M' can be viewed as following the dynamics of M in which each action is stochastically replaced (" ("perturbed") according E.
The set of all n-perturbations of M is denoted C(M, 17)-
We assume that the target environment is an r-perturbation of the abstract simulator for value of
7) < 0.5. Thus, most of the time the target environment transitions after each action "as intended" (i.e., following known dynamics of the abstract simulator), but with probability at most y it may depart from the intended action due to an inherent, but unknown stochasticity:
Assumption 2. M is an ny-errturaation of the abstract simulator M for some 7 < 0.5.

---

Abstract policy. Behavior of an idealized agent that can directly access latent state is formalized as a (Markovian) abstract policy. An abstract policy prescribes what action take in each state at given step h. i.e., it is a mapping v [H] x S - A; we write (s)(s) for the action taken by sb in step and state 8. The expected sum of rewards an episodic MDP M = (S, A, Sinit: H, T, R), when
following v is called the value of Ab in M and denoted VM = MM [ri + +... +r]]
Robust abstract policy. Since the latent MDP in the target domain is perturbation of the abstract simulator, we will seek to obtain policies that are robust to any allowed perturbation. For given abstract simulator M and the perturbation level 77, define robust abstract policy p to be policy that achieves the largest possible value under the worst-case choice of perturbation:
argmax min NEW MEC(M9,)
V
where v is the set of all mappings from [H] x A.
In natural way, robust abstract policy p can be composed with the perfect decoder O' to obtain (Markovian) practicable policy poo" [M] X - A mapping observations in the enviromment to actions while still maximizing the worst-case reward among perturbations of M We aim for algorithms that find practicable policies that perform almost as well as this robust practicable policy.
3.3 The learning setting
We can now formally define our learning setting. A learning algorithm Alg in this setting receives input a deterministic abstract simulator (episodic MDP) M = A, Smit H, RR), meaning it receives the entire MDP represented in tabular form (or some other computationally convenient form). The algorithm is also provided with oracle access target environment (block MDP), M = (M*, (")) This means that the algorithm cannot directly access M* itself, but can interact with it as agent would, executing actions as and receiving back observations Fh and rewards rh in sequence of episodes, as described above. Finally, Alg is given parameters e >> 0, 6 > 0, and " 0.5. It is assumed that M* is 7-perturbation of M The assumption that we know the value of 1) is not essential and we discuss in Section 4.4 how it can be removed.
After interacting with M the algorithm outputs practicable policy x. The goal of learning is for æ to have value almost as good as the robust practicable policy with high probability, that is, for VM. 2 Vi randomization as well as randomness in the interactions with the target environment). Furthermore, we require the number of episodes executed by the algorithm before outputting a policy to be bounded by a polynomial in the number of actions [A], the horizon H, 1/e, 1/5, and 1/ 2n). Note importantly that this polynomial must have no explicit dependence or observations | in the target environment. An algorithm that satisfies these criteria (given the stated assumptions) said to achieve an efficient transfer from abstract simulator.
with probability at least - (where probability is over the algorithm's 's
the number of states [8]
4
Main Algorithm
Our main contribution is an algorithm TASID, which achieves efficient transfer from an abstract simulator. The algorithm operates in two stages. In the first stage, it determines the robust abstract policy p for the provided abstract simulator via robust dynamic programming (Algorithm 1}. In the second stage, it interacts with the target environment (via oracle access) in order to learn to predict the current latent state based on the history of observations and actions. The learnt decoding map is then composed with the robust abstract policy to obtain the practicable policy that is returned by the algorithm (see Algorithm 2).
4.1 Robust dynamic programming for abstract simulator
We obtain the robust abstract policy by instatiating the robust dynamic programming algorithm of Bagnell al. [2001) and [yengar (2005) to our specific notion of perturbation. The algorithm proceeds by filling out values of the robust value function V. which quantifies the largest sum of rewards achievable starting any step h and state s, when assuming the worst-case perturbation of the input MDP M Specifically,
(s) max min EM [Tn + Th+1 +... + TH sh = s].
New McC(MP,))
5

---

Algorithm I Robust Dynamic Programming. RDP(M", ,1)
Input: An episodic MDP M A, Sinits H, T R perturbation level n
1: V (8) <- 0 for all E
2: for h H,
do
3: for all E S, A:
(n(s,a) t- a)) E. (s' 88, (n) (s(() + (1 7) max, Qn(s, a) + mmin, (s(
4: for all E
5: Return defined by (s()) = argmax, (s,
Algorithm 2 Transfer from Abstract Simulator using Inverse Dynamics. TA'. MM,F, FF.F.,n,, (,,
Input: Oracle access to target environment M', deterministic abstract simulator M optimization-oracle access to function class JF { + A(A)),
perturbation level < 0.5, target accuracy > 0, failure probability 6.
1: Let p be the robust policy returned by RDP(M
2: Let RD = bn
<(1-2n)²
3: Let क (x) = P1 (iinit) for all E X
I/ Define practicable policy in step h 1
4:
for h = -1,...., H do
5:
Dí
Gather dataset Dr, for learning "inverse dynamics" in step
6:
for nD times do
7:
Follow Ti:h-1 for 1 steps observe 3h Take action aд uniformly at random and observe F/+11
8:
9:
DA -D, {(I,, 0h. Th+1]}
10:
fn == arg max E (E In f(an Th, Th+1)
I/ Learn "inverse dynamics" // Define "shadow action" decoder
11:
Define os x² A as
On (1h, ) = argmax aEA [a(: Th+1)
12:
Define Φh+1 1 x + S such that Φh+1 (x1++1) is the state 8h+1 reached in M when starting in Snit and executing aj = 01 (#1, (2), ... az = an (2 Th+1)
Define state decoder
13:
Define Th+1 2++1 - A as Wh+1 (1:h++) = Ph+1 (0h+1 (x1)441)
Define practicable policy
14:
return = (T),..,,TI) TH)
Similar to standard dynamic programming, the value function in robust dynamic programming can be filled out beginning with h = H + 1, where we have (s(s) = O, and proceeding backward. In our case, the values (s) can be obtained from Vh+ (s) using closed-form expression (line 4), which leverages intermediate values Qn (s, a). Note that Q is not quite the robust state-action value function, because it assumes that the action at step h is left unperturbed (and only considers the worst-case perturbation in the following steps). The function Q is used to derive the robust policy (line 5).
Theorem 1. For any abstract simulator M and any perturbation level r). Algorithm returns the robust policy p = argmax w min m) V
(The proof of this theorem and all other proof's in this paper are deferred to the appendix.)
4.2 Learning decoder in the target environment
We cannot directly apply the robust abstract policy in the target environment, because the latent states are not observable, Therefore, we construct a "state decoder" the target environment, which uses the history of observation in an episode to predict the current latent state; the state decoder is combined with the robust abstract policy to obtain the practicable policy. Formally, decoder is mapping Φ X + S. In step h of episode, the history of previous observations Xich is used as an input, and the decoder predicts the latent state 84. To construct such a state decoder, crucially leverage the abstract simulator M
mon-Markovvann state

---

The abstract simulator M is deterministic, so specific sequence of actions ai,.... a₁ always leads to the same state. The latent MDP in the target environment a perturbation of the abstract simulator. This means that when an agent takes action Oa in step h, most of the time the environment transitions according to (- 8h, (b)) ). but sometimes (with probability at most 7) transitions according to some other action. The action ag gets replaced with some "shadow" action df, according to an unknown noise distribution ç. and the latent state then transitions according to T (: sh, dy)) If we knew shadow actions ........ d we could then recover the current latent state by simulating that same sequence of actions in the abstract simulator.
To obtain shadow actions, we learn an "inverse dynamics" model, which predicts dj from the observations 2/ and T/+1 (an approach also used in previous work on block MDPs). We learn a separate inverse dynamics model for each step of an episode. In step h, we sample triplets of the form (ITA, (h, (h,,%))) across multiple episodes in the target environment, and then fit model fa for the conditional probability of as given 24 and s/, The model fr (ax (r,, (1, is referred to as an inverse dynamics model, because it "inverts" the dynamics represented by the transition function. We show that if we were able to obtain an exact model f%, of the conditional probability, then the action a with the largest probability f (a Tb, xx,)) would be the correct shadow action.
As is standard in the block MDP literature, in order to fit an inverse dynamics model, we assume access an optimization algorithm capable of fitting functions from some class C (X² + A(4) to data; we call this algorithm an optimization oracle for F. The class F should be sufficiently expressive to approximate the required conditional probability distribution.
We now have all the pieces required to describe our algorithm. The algorithm first constructs the robust abstract policy (line T}. and defines the practicable policy æ1 the initial step h 1, where the latent state is known to be Sinit [[ine 3). The algorithm then proceeds iteratively to fill in T2..... HH. H. In iteration h, the algorithm first learns the inverse dynamics model fr. with the help of the optimization oracle (line SH The inverse dynamics model is then used to obtain the shadow action decoder 0n qline IT.. which predicts which action caused the transition from Iy, to I- Using the shadow action decoders up to step h, we can construct a state decoder Φh+1 (line 12), which for given history of observations X1:h+1, first predicts their corresponding shadow actions d' ....... of and then uses the abstract simulator to determine the state St+11 that they lead to. Finally, using the state decoder 1 we define the practicable policy at the step h + 1 to return the same action as the abstract robust policy would return on the decoded state (line 13).
4.3 Sample Complexity of TASID
We next provide the sample complexity analysis of TASID, showing that it indeed achieves efficient transfer from an abstract simulator. In addition to Assumptions [ and we also need to ensure that the function class F is expressive enough to approximate the conditional probability distribution being fitted by the inverse dynamics model. It turns out that this target probubility distribution can be expressed in terms of the transition function of the block MDP M which is the function T HH] x X' x A + ( equal to
T (2') x. = q¹
(''))) = 6z (x') 8= (x).
Using T we can write the exact inverse dynamics model as fi xI,'' = En'es Tz
(='12.)))
To state our assumption, let Pr. denote the distribution over triples (xh, az. th+1) sampled in line 7
and let Sr. be the maximizer (in F) of the expected log likelihood under Ph:
Jn := argmax E' (In f(a xx)))))
fEF
Assumption 3 (Approximate realizability). There exists e 2 0 such that for every h E [M], for all triples (x, a, x²) in the support of Ps.
(a x. S (1 + ex) (x)
Exact realizability assumptions (with Ex = 0) are standard in the block MDP literature [Du et al. 2019 Agarwal et al., 2020). Here we only assume approximate realizability, which can be assured for any e > 0 by choosing sufficiently expressive class such as deep neural networks. In practice, we choose classes that express some inductive biases (such as feature invariance, factorization, etc.).
We are now ready state main theoretical result-samle complexity of TASID.
7

---

Theorem 2. Let M be a deterministic abstract simulator. Let M be target environment for which M is an n-perturbation of M for some 1 < 0.5. Let F be class of functions that satisfies Assumption 3 with E S (1-2n)² . Then for any e O and å E (0, 1), Algorithm 2 with oracle access to M optimization-on oracle access to F, and inputs M Q, c/2, and ò, executes
( ( [|(
episodes and returns a practicable policy that with probability at least
<11221]
1 å satisfies
M 2
V-000" M
Thus. Algorithm 2achieess efficient transfer from an abstract simulator, meaning that its sample complexity is independent of the sizes of [S] and [2). We also achieve fast rate, ((1/e), with respect to the sub-optimality e. The assumption on ez is not restrictive, because we can always choose
sufficiently expressive class. Note that previous works simply assume e [e.g.- Duu et al. 2019
Agarwal et al. 2020 Misra et al. (000]- The dependence on In [F] is standard; for neural networks proportional to the number of bits store the network weights. For example, if the neural network
has 1000 weights represented by doubles (i.e.. with 64 bits) then In [F] = (In 2) 64000. There may be room to improve dependence on the horizon H and action space size |A], but these were not our
focus here.
4.4 Extensions
In the appendix, we show how TASID, under additional assumptions, can be extended to settings where the abstract simulator has stochastic start state (but deterministic transitions).
The assumption that 7) is known is not necessary. If 17 not known, is possible carry out form of binary search as follows: Run the algorithm with = 1/4 and verify whether it achieves the performance guarantee. If it does, continue with 17 1/8 (splitting the interval (0, 1/4)), otherwise continue with 1 3/8 (splitting the interval (1/4, 1/2)), and run the algorithm again. If the goal is to recover 7) up to the precision Ex, then we just need to repeat this loga (1/2 (22),)) times.
Although our focus here is on transfer from an abstract simulator, and we emphasize the relative ease of constructing abstract simulators, our approach could also be used for transfer learning between two block MDP environments that share latent space structure. In the source domain, we could use an existing block MDP approach [c.g..[Misra Misra et al.) [2200] infer latent structure, which could then be used as an abstract simulator to speed up learning in the target domain using TASID.
5 Experiments
We evaluate TASID in two simulation environments, focusing on four of its properties: sample complexity independent of state-space size; scalability to complex visual observations; robustness of the policy it learns; and scalability to large state spaces. We summarize the results here and defer the details, including hyperparameter selection, detailed environment descriptions, algorithm and baselines implementation and full description of results under various setups to the appendix.
Can TASID solve problems that require strategic exploration? We theoretically showed that TASID can solve problems that require performing strategic exploration using a small number of episodes. We test this empirically on a challenging environment called combination lock.
Combination lock. We first describe the abstract simulator M visualized in Figure 2a It has an action space A. horizon H, and a state space {h,,)) h {0] U [H], E [3]]. with the initial state (0, 1). As we will see, states {h, 1), (h, 2) h E [ are good states from which optimal return is possible, while states {(h, 3) h [W]] are bad states. In state (h, 1), one good action leads state (h + 1, 1), and all other [A| 1 actions lead to state (h + 1, 2). In state (h, 2), one good action leads to state (h + 1, 1,)), another good action leads to state (h + 1, 1), and all other |A|| actions lead to (h + 3). All actions in state 3) lead to state (h + 1,3.. The identities of good actions are unknown and are different for different states. Any transition to state (H, 1) gives a reward of 9.5, whereas transition to state (H, 2) gives reward of 10, and transition to state (H, gives a reward of 0. To "mislead" the agent, transitions from (h, 2) to (h + 1,3) give a reward of and transitions from (h, 1) to (h + 1, 1) give reward of -1/H H. All other transitions give reward of 0.
8

---

Pno
PPO FPO RND
PDG
TAS
12.3)
10000 200000 302033 400000 590000
0
100000 20000E S00000 400000 5000C0
(a) Combination lock environment
(b) Horizon solved vs episodes
(c) Reward curve for H = 40
Figure 2: (a): Latent MDP in the combination lock. (b): The largest problem (expressed as horizon H) that each algorithm can solve (defined as reaching 95% of the value of the robust policy) within 500 000 episodes; we consider = 5, 10, 15, 20, 25, 40 and |A] = 10. We report median number of episodes across five trials with different seeds (see the appendix for full details). (c): Total reward per episode for the problem size H 40. TASID is a batch algorithm trained on the first 100 000 episodes, thus its performance before the end of training is very low and after the end of training stays constant. Shaded bands correspond to the 95% Student's L confidence intervals (here and elsewhere in paper).
The latent MDP M of the target environment is constructed by taking a random 1) 7-perturbattin of M for v = 0.1. Exploration both M* and M can be difficult due to misleading rewards and challenging dynamics, where most actions lead to bad states. The optimal policy in M finishes in the state (H, and achieves the value of 10. However, the robust policy will attempt to visit the state (H, 1) which lies a more stable trajectory. Mcanwhile, the optimal policy in M will fail in M because perturbations are likely to move the agent into a bad state.
Observations in the target environment are real-valued vectors of dimension 2 ( For latent state (h, i), the observation is generated by first creating an (H + 4)-dimensional vector by concatenating one-hot encodings of h and i, element-wise adding Gaussian noise, applying fixed coordinate permutation, and finally multiplying the vector with a Hadamard matrix.
We compare TASID with four baselines. The first is PPO (Schulman et al. 2017). policy- -gradient- based algorithm. The second is PPO-RND, which augments PPO with an exploration bonus based on prediction error (Burda al. 2019b]. These two baselines do not use abstract simulator and run on the target environment from scratch. The other two baselines, PPO+DR and PPO+RND+DR, enhance PPO and PPO+RND with domain randomization (DR), where the policy is pre-trained set of randomized block MDPs (Tobin et al.) [017]] PPO+DR and PPO+RND+DR are designed for transfer RL, but unlike our work, they rely on Abservation-baaee similarity. During the pre-training phase of domain randomization, we generate block MDPs by following a similar process as the one used generate the target environment. However, when generating the emission function, we only generate a random permutation matrix and the other components are kept the same as in the target environment. This randomization set includes the true emission function and transition dynamics.
For baseline algorithms, we run grid search over hyperparameters listed in Table 3 in Appendix D separately for each environment specification (each value of H), and report the best results of (+O)+ For TASID, we consider only one hyperparameter, the number of training episodes per time step no, and search over three possible values: 1000, 2500, 10000.
Figure 2b plots the size of the problem (expressed as horizon H) that each algorithm can solve (defined as reaching at least 95% of the value of the robust policy) within a given number of episodes; we considered H = 5, 10, 15, 20, 25, 40. The plot shows that PPO and PPO+DR fail to solve the problem beyond the smallest size (H 5), which is not surprising they not designed to perform strategic exploration. PPO+RND can solve the problem until H = 20, but fails for H 25, showing that RND bonus helps to extent but cannot solve harder problems. Interestingly, PPO+RND+DR underperforms compared to PPO+RND even though it has access to pre- training. We believe this is because RND reward bonus does not work well with domain randomization which can mislead the RND bonus by randomizing the observation. Finally, TASID can solve the problem for all values of H and is more sample efficient than the baselines.
Can TASID scale to complex observation spaces? We evaluate TASID in the visual MiniGrid environment (Chevalier-Boiseet Boisvert et al. 2018 with noisy observations. We test on the grid world

---

1.0
0.8
0.8
Pokyyaus
0.6
Pakcyauu
0.6
0.4
TASID 2000
0.4
Robust Valu
TASID (n=200.003)
0.2
Optimal policy
0.2
Robust Valu 22bt0112"
Optimal policy
0.0
0.1
0.2
0.3
0.4
0.5
20
40
60
80
100
Perturbation Upper Bound (sta)
Height of the Grid Map
(a) Minigrid
(b) Noise
(c) Performance perturbation
(d) Performance state space size
Figure 3: (a,b): Map of 7 x 11 MiniGrid environment with noisy observations and five actions: for- ward, turn left, turn right, turn left + forward, turn right + forward. (c): The performance of TASID with different amount of perturbation 1). (d): The performance of TASID with different heights of the map.
map shown in Figure 3a The green square represents the goal and orange squares are lava that should be avoided. The agent's position and direction is shown by the red triangle. The agent gets a reward of 1 reaching the goal, -1 for reaching the lava, and -0.01 for every other step. The state encodes the position and direction the agent and the current time step. There are actions: move forward, turn left, turn right, and combinations of turning and moving. The abstract simulator M models the deterministic transitions on the grid. The target environment is an 7-perturbation of M for 17 0.1. The agent cannot observe the whole map in Figure 3al but only image of the 7 x 7 grids (56 x 56 pixels) in the direction it is facing, with i.i.d. random noise added to all black pixels as shown in Figure 3b This type of random noise has been studied in the literature and has been shown to pose challenge for RL algorithms [Burda et al. 2019a]
In this grid world, the agent can either use the top route to reach the goal, or bottom route. The top route is shorter but the agent is more likely to visit the lava due to perturbations. Therefore, the robust policy prefers the bottom route which is longer but more robust.
How robust is TASID different 17? Our theoretical analysis suggests that the suboptimality scales as (11((1 - 2). We evaluate this error empirically in the grid world environment for various values of r) in (0.1, 0.5) and show the results in Figure 3c The performance matches the theoretical prediction 1-0o=" O(1((1 11-21 2n))) until 7 0.3, and becomes even better for larger n) Interestingly, even though the theoretical guarantee is vacuous at 17 = 0.5, the algorithm still learns a non-trivial policy with the value greater than that a random policy. Note that we tune the value of n.p rather than use the value suggested by our theory.
How does TASID's performance scale with |S|? We showed theoretically that TASID's sample complexity to learn near-optimal robust policy is independent of the size of the state space. We empirically test this by varying the height of the grid world environment while keeping the width and the horizon H, and overall layout the same. Results are presented in Figure 3d As height changes from 10 to 100, the size of the state space increases ten times; however, we do not see significant drop in the performance of TASID when using fixed number of episodes in the target environment.
Conclusion and Future Work
We presented a new algorithm TASID for transfer RL in block MDPs that quickly learns robust policy in the target environment by leveraging an abstract simulator. We have also proved a sample complexity bound, which does not scale with the size of the state space the observation space. Finally, we demonstrated theoretical properties by empirical evaluation in two domains.
Our work raises many important questions. Our theoretical analysis depends on the assumption that possible
the abstract simulator deterministic and the the target environment its perturbation. to relax these requirements and still obtain sample bounds that do not scale with the state space size? One direction might be to leverage "full simulators" (including observations), and incorporate observation similarity between the simulator and the real environment, along with similarity in the latent dynamics. Another important question is how to extend the presented approach to continuous control problems in robotics, which are natural domains for sim-to-real transfer.
10

---

References
Alckh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural com- plexity and representation learning of low rank MDPs. In NeurIPS, pages 20095-201000 2020.
J Andrew Bagnell, Andrew Y Ng. and Jeff G Schneider. Solving uncertain Markov decision processes. Technical report, Carnegie Mellon University, 2001.
Tim Brys, Anna Harutyunyan, Matthew E. Taylor, and Ann Nowé. Policy transfer using reward shaping. In AAMAS, pages 181-188, 2015.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driven learning. In ICLR, 2019a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. ICLR, 2019b.
Maxime Cheislier-Boisvert, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for OpenAl gym. h/tpt/////ttbbbb// www.///xxmmmb///
mm/ http://wwwww.aaammmmm/maiiiiagga gym-biiigimmmmmiidmmi... 2018.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In ICML, pages 1665-1674. PMLR, 2019.
Fernando Fernández, Javier Garcfa, and Manuela Veloso. Probabilistic policy reuse for inter-task transfer learning. Robot. Auton. Syst., 5867):866-871,2000
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low Bellman rank are PAC-learnable. In ICMI., pages 1704-1713. PMLR, 2017.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University College London, 2003.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. NeurlPS, 2016.
Alessandro Lazaric. Transfer in reinforcement learning: A framework and a survey. In Marco Wiering and Martijn van Otterlo, editors, Reinforcement Learning: the pages 143- 173. Springer, 2012.
Yaxin Liu and Peter Stone. Value-function-basee transfer for reinforcement learning using structure mapping. In AAAI, pages 415-420, 2006.
Timothy A Mann and Yoonsuck Choe. Directed exploration in reinforcement learning with transferred knowledge. In EWRL, pages 59-76. PMLR, 2013.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In ICMI, pages 6961- PMLR, 2020.
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. EPOpt: Learning robust neural network policies using model ensembles. ICLR. 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. arXiv preprint a7Xiv:1707.06347, 2017.
Reinhard Selten. A reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4(1):25 55, 1975.
Vishal Soni and Satinder Singh. Using homomorphisms to transfer options across continuous reinforcement learning domains. In AAAI, pages 494-499, 2006.

---

Yanchao Sun, Ruijie Zheng, Xiyao Wang, Andrew Cohen, and Furong Huang. Transfer RL across observation feature spaces via model-based regularization. ICLR, 2022.
Matthew Taylor and Peter Stone. Behavior transfer for value-funcction-asee reinforcement learning. In AAMAS, pages 53-59, 2005.
Matthew E. Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. JMLR, 10: 10:1633-1688, 2009.
Matthew E Taylor, Peter Stone, and Yaxin Liu. Transfer learning via inter-task mappings for temporal difference learning. JMLR, 2007a.
Matthew E. Taylor, Shimon Whiteson, and Peter Stone. Transfer via task mappings in policy search reinforcement learning. In AAMAS, 2007b.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation the real world. In IROS, pages 23-30. IEEE, 2017.
Geoffrey Van Driessel and Vincent Francois- Component transfer learning for deep RL based on abstract representations. arXiv preprint arXiv:2/11.11525, 2021.
Amy Zhang, Clare Lyle, Shagun Sodhani, Angelos Filos, Marta Kwiatkowska, Joelle Pineau, Yarin Gal, and Doina Precup. Invariant causal prediction for block MDPs. In ICML, pages 11214-11224. PMLR, 2020.
12


Reviews:
[{"review_id": "jG5sAt2dOgT", "reviewer": "Reviewer_Jw57", "summary": "The authors present TASID, an algorithm which leverages knowledge of an abstract MDP (through an abstract simulator) to efficiently solve a more difficult MDP, using standard assumptions in the block MDP framework. They illustrate the benefits of their method in a synthetic toy problem and a slightly more challenging MiniGrid environment.", "questions": "In Section 2.1, two things could be done to help the reader better understand the level of difficulty of the approach.\n- from one side, it must be made clear why solving block MDPs is less daunting than solving full POMDPs. If I understoos correctly the literature, block MDPs are \"one-step decodable POMDPs\", so a memory of size one is enough. Still if I'm correct, this is why learning an inverse dynamics model with x_h and x_{h+1} is enough to efficiently decode the latent state. I think making this relationship to POMDPs would help non-expert readers like me.\n- from the other side,  it must be made clear why solving block MDPs is not trivial. From the current description one may understand that, since two states cannot emit the same observation, one can trivially recover the state from the observation. I think it should be made clear that the \"perfect decoder\" needs some memory (actually, one-step memory if I'm correct).\n\nAnother unclear point is related to exploration and the difficulties it raises in the framework. In particular, lines 268-269 state \"We theoretically showed that TASID can solve problems that require performing strategic exploration using a small number of episodes.\" but the word exploration does not appear at all in the methods. So somehting is not explicit enough here. More precisely, it is unclear to me whether considerations on the perturbation level \\eta is related to exploration or more to environment noise.\n", "limitations": "Does not apply", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the paper addresses a relevant problem, for instance when a robot but navigate a complex environment but is given a simplified map.\n- it looks technically sound (I'm not expert enough of the domain to spot potential flaws)\n\nWeaknesses:\n- although the target application is complex robotics navigation problems, the method is demonstrated with toy environments that are not representative of the targeted complexity. We would like to see something closer to the \"running example\" put forward at the beginning of the problem statement...\n- being naive on block MDPs, I had to read other papers to better understand the relationship to POMDPs. A few points could be clarified, see below.\n- rejecting part of the related work in appendices is not a good practice. I understand that it is difficult to fit this paper into 9 pages. Maybe the authors could rather move Algorithm 2 to the appendix? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "h0yd5cwFlj9", "reviewer": "Reviewer_Wg3g", "summary": "This paper proposes an offline control algorithm for finite-horizon time-inhomogeneous block MDPs. The agent is given observations at each state and an approximate deterministic simulator is available. The agent first infers a nearly-optimal policy the simulator that is robust to perturbations (and so is nearly optimal for the underlying MDP as well) and then, through interaction with the environment, learns a decoder that maps histories of observations to states. Sample complexity of the algorithm is studied and experiments on a synthetic MDP and a gridworld are provided.", "questions": "See weaknesses section", "limitations": "For horizon H the current algorithm needs H^4 episodes (H^5 steps) but this is stated in the paper. I do not find fixing this limitation within the scope of the current paper.\n\nThe current algorithm also has large memory requirements which should be stated.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is clearly written and well organized. It studies a novel setting (to the best of my knowledge) and provides a sound algorithm along with theoretical and empirical results. Altogether I am in favor of acceptance.\n\nThe most interesting contribution is the use of eta-perturbation to model the simulator's inaccuracies. Robust dynamic programming with this perturbation and the guarantees in this paper may have other applications in reinforcement learning in the future. The discussion on this perturbation is however limited and it is not clear how strong or practical this measure of perturbation is.\n\nWeaknesses:\n\n1. The paper would greatly benefit from situating its sample complexity against related settings or algorithms. Some questions that such discussion could answer are: (a) If other algorithms have been proposed for this setting, what is their sample complexity? (b) What lower bounds and upper bounds for other types of perturbations and how does eta-perturbation make the problem simpler or harder? (c) If we knew that such deterministic approximate simulator exists for the MDP but it was not available, how would the bounds change?\n\n2. The paper mentions multiple times that the sample complexity of the proposed algorithm is independent of the size of the state space. While this is true, it is mostly a result of restrictive assumptions on the problem rather than the algorithmic contributions of the paper and the statements can be misleading. The problem is assumed to have a fixed start state, a finite horizon, and transition dynamics that are close to a deterministic simulator. These three conditions limit the number of states that often appear in trajectories, which is independent of the size of the total state space. In fact replacing the fixed start state with a set of possible start states (in the appendix) brings the cardinality of this starting set into the sample complexity. More generally if the starting distribution is over all the states then the size of the state space will appear in the sample complexity.\n\n3. One of the functions approximators is assumed to be large enough to satisfy a realizability assumption (Assumption 3). It is said that the assumption can be satisfied with a deep neural network but the size of this function class appears as a logarithmic factor in the sample complexity. Is this factor finite for a deep neural network and does it depend on the size of the state space or the space of observations?\n\nTypos:\n- line 93: q(s|x) -> q(x|s)\n- line 134: \"at eta-perturbation\" -> \"an eta-perturbation\"\n- line 179: instantiating\n\n--------------------------------------\nUpdate after discussions:\n\nThanks for the clarifications. I increased the score to 7 as the comments 1 and 3 are addressed. I'll elaborate on the second comment:\n\nThe problem setting in this paper has two important properties. First, the environment is nearly deterministic in terms of eta-perturbation so that a nearly accurate deterministic simulator exists in the first place. Second, this simulator is available to the agent. The algorithm achieves sample complexity independent of |S| in this problem setting (which is great). Now the reader may want to know if both of these properties are essential to this sample complexity or if the first one is enough. That is, if the environment is nearly deterministic in terms of eta-perturbation, can an algorithm without access to a simulator or without learning a simulator achieve this sample complexity in a non-transfer setting? I understand that achieving this low sample complexity in a general stochastic problem is impossible, but is it also impossible in this _nearly_ deterministic environment? Also I think running some model-free baselines on the mini-grid experiment and seeing if their sample complexity grows with |S| is a good idea.\n\nAnother minor comment: Other reviews initially raised doubt about the significance of this result. I suggest referencing or bringing a lower bound from previous work that grows with |S| without the assumptions in this paper. This should better motivate this result and highlight that requiring some assumptions is inevitable for achieving this sample complexity. I can think of Theorem 2 in [1] right now but the authors have a better grasp on this topic and may find a more relevant bound.\n\n[1] Dann, Christoph, and Emma Brunskill. \"Sample complexity of episodic fixed-horizon reinforcement learning.\" Advances in Neural Information Processing Systems 28 (2015).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ciQruWiSBp", "reviewer": "Reviewer_Rkjz", "summary": "This paper studies a transfer learning setting, where the agent wishes to learn in a block MDP target environment with the help of an approximated latent simulator. This paper proposed an algorithm that achieves sample efficient learning in such a setting given that\n(1) the latent simulator is deterministic while still achieving a small approximation error. In other words, the target environment is nearly deterministic.\n(2) the learner must know the approximation error of the simulator or at least a tight upper bound.\n(3) the learner has access to a realizable function class of the block MDP non-latent dynamics.", "questions": "1. What is the technical barrier that requires the deterministic latent transition assumption? Overall I feel the proposed approach can sometimes be very suboptimal. If the real environment has high stochasticity, forcing a deterministic approximation and then looking for a robust policy to the approximation error doesn't seem to be a good idea, since the resulting suboptimality gap will be very large.\n\n2. The learner requires the knowledge of the approximation error of the simulator, which further weakens the problem setting and makes it even less practical.\n\n3. Why does the algorithm attempt to learn a non-Markovian decoder when the ground-truth decoder is in fact Markovian?\n\n4. While the paper is only concerned with block MDPs, it makes a rather strong model-based realizability assumption (Assum. 3) which has been shown to be unnecessary for block MDPs, e.g. [1]. This assumption seems to be needed mainly to use the inverse dynamics model techniques. It's not obvious to me whether such an assumption, along with (1) deterministic simulator and (2) known approximation error are necessary or not for the particular setting this paper considers. For example, one could potentially apply the representation learning subroutine in [1] and then call the robust latent policy on top of the learned representation for exploration, which is a much simpler approach both conceptually and computationally.\n\n[1] Zhang, Xuezhou, Yuda Song, Masatoshi Uehara, Mengdi Wang, Wen Sun, and Alekh Agarwal. \"Efficient reinforcement learning in block mdps: A model-free representation learning approach.\"\n\nOverall, I am most concerned with the strong assumptions required for the proposed approach to work. Without further justification, e.g. lower bounds, it's hard to appreciate the theoretical contribution of this paper.\n", "limitations": "the assumptions are not adequately discussed and justified.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The setting studied in this paper appears to be new, at least in the theoretical literature, and has some practical motivation. However, the assumptions required by the proposed algorithm to work is too strong comparing to recent literature on sample efficient learning in block MDPs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Kf1nJH4qu9M", "reviewer": "Reviewer_3VEr", "summary": "Paper 4378 proposes an algorithm to solve Block MDP when imperfect prior knowledge about the dynamics is available.\nThey encode this information in a deterministic abstract simulator, assuming the target environment to be a perturbation of it.\nThe optimal policy in the abstract simulator is used in the target environment with an inverse dynamic model to decode observations to latent states.\nThe authors provide a PAC analysis of the algorithm's sample complexity which does not depend on the size of the state and observation space.\nThe algorithm is tested in two environments to evaluate performance and scalability.", "questions": "- Mainly addressing the doubts stated in the *Quality* paragraph. \n- The sample complexity considers only the interaction with the target environment. However, what is the impact of the robust dynamic programming algorithm used to learn a policy in the abstract simulator in the overall bound? Is it still independent of the size of the state space?\n- The experiment on the scalability of TASID is defined only with respect to $|S|$. However, in line $343 you claim independence on the size of the observation space. Could you provide empirical evidence of it, for example running the Visual Grid task with larger observations?", "limitations": "- It would be useful to extend the discussion on how the assumptions of a deterministic abstract simulator and perturbed target environment are realistic.\n\n- Improvement on reproducibility: \n\t- Include instruction on installation requirements. I set up the environment by my own, looking at the missing dependencies and appropriate versions. A simple file \"requirements.txt\" would make the installation straightforward.\n\t- Include instructions on how to run the code. A readme file with a few commands to reproduce the main experiments is essential. In the current status, I run the scripts in the \"experiments\" directory without any knowledge of any input parameters.\n\t- Include information on expected computing time. Comments on the expected time (and associated platform) to complete each experiment is helpful. For example, running the mini-grid experiments does not show any progress after 15 minutes of execution. Since there is no further information on the current status of the run, I killed the process.\n\t- Include parameter configuration. Use configuration files to exactly reproduce each experiment. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Main comment\n- *Significance*: The analysis of sample complexity is interesting and the design of algorithms with guaranteed sample complexity is a highly-relevant topic for the RL community. This result relies on the assumption of a deterministic abstract simulator and perturbed target environment which is interesting as well. However, it is unclear if this assumption is realistic enough and its feasibility in more complex problems.\n- *Clarity*: The paper is well written and organized, with the exception of the related work section that is too short. An extended version of it is included in the appendix. Moreover, some parts of the proofs are not clear, such as the definitions of the various probability distributions at the beginning of Algorithm 2's proof, line 577.\n\n- *Originality*: The main criticism of this work is about novelty. In fact, it builds on top of prior works (adequately cited in the related works) and uses standard techniques, such as optimizing the policy in the abstract simulator and learning a decoder to map observations to latent states. The proof also adapts existing results (Agarwal 2020) to this work.\n- *Quality*: There are some flaws and inaccuracies that make it difficult to follow some of the proofs and raise doubts about the validity of the overall claims. In particular:\n\t- It is not clear what are the assumptions on the function class $F$ which approximates the decoder, and if the bound holds for finite or infinite hypothesis classes.\n\t- In the proof of Lemma 1 (Appendix, line 497) ends with a disequality. However, in the following line (498), equivalence is stated and it is not clear why.\n\t- In the proof of Algorithm 2 (Appendix, line 577), the distribution $P_h(x)$ is defined referring to Algorithm 2, Line 9. However, these definitions are not formally defined.\n\t- In the proof of Algorithm 2 (Appendix, lines 576 and 582), the distribution $Unf(A)$ is first defined as a uniform distribution over action space, and later as uniform conditional distribution of $a$ given $x$.\n\n### Other remarks\n- *Reproducibility*: The authors provide an appendix and code as supplementary material. However, the code presents several flaws and requires a certain effort from the readers to reproduce the results. I have been able to run the code for the combination-lock, while the mini-grid gets stuck in the first iteration. It could depend on computation time but no further information is provided in the log, so it is difficult to judge. Then, I have not been able to reproduce the results. I will include hints to improve on that later on.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept