Provably Filtering Exogenous Distractors using Multistep Inverse Dynamics
Authors: Yonathan Efroni
Dipendra Misra
Akshay Krishnamurthy
Alekh Agarwal
John Langford
Venue: ICLR 2022 Oral (2022)
Keywords: Reinforcement Learning Theory
Invariant Representation
Rich Observation Reinforcement Learning
Exogenous Noise
Inverse Dynamics

Abstract: Many real-world applications of reinforcement learning (RL) require the agent to deal with high-dimensional observations such as those generated from a megapixel camera. Prior work has addressed such problems with representation learning, through which the agent can provably extract endogenous, latent state information from raw observations and subsequently plan efficiently. However, such approaches can fail in the presence of temporally correlated noise in the observations, a phenomenon that is common in practice. We initiate the formal study of latent state discovery in the presence of such exogenous noise sources by proposing a new model, the Exogenous Block MDP (EX-BMDP), for rich observation RL. We start by establishing several negative results, by highlighting failure cases of prior representation learning based approaches. Then, we introduce the Predictive Path Elimination (PPE) algorithm, that learns a generalization of inverse dynamics and is provably sample and computationally efficient in EX-BMDPs when the endogenous state dynamics are near deterministic. The sample complexity of PPE depends polynomially on the size of the latent endogenous state space while not directly depending on the size of the observation space, nor the exogenous state space. We provide experiments on challenging exploration problems which show that our approach works empirically. 

Published as a conference paper at ICLR 2022
PROVABLE RL WITH EXOGENOUS DISTRACTORS VIA MULTISTEP INVERSE DYNAMICS
,leeaa Yonathan Efroni', Dipendra Misra', Akshay Krishnamurthy', Alekh Agarwal John Langford' Microsoft Research, New York, NY Google
ABSTRACT
Many real-world applications of reinforcement learning (RL) require the agent to deal with high-dimensional observations such as those generated from megapixel camera. Prior work has addressed such problems with representation learning, through which the agent can provably extract endogenous, latent state information from raw observations and subsequently plan efficiently. However, such approaches can fail in the presence of temporally correlated noise in the observations, a phenomenon that is common in practice. We initiate the formal study of latent state discovery in the presence of such exogenous noise sources by proposing a new model, the Exogenous Block MDP (EX-BMDP) for rich observation RL. We start by establishing several negative results, by highlighting failure cases of prior representation learning based approaches. Then, we introduce the Predictive Path Flimination (PPE) algorithm, that learns generalization of inverse dynamies and is provably sample and computationally efficient in EX-BMDPs when the endogenous state dynamics are near deterministic. The sample complexity PPE depends polynomially on the size of the latent endogenous state space while not directly depending on the size of the observation space, nor the exogenous state space. We provide experiments challenging exploration problems which show that our approach works empirically.
INTRODUCTION
In many real-world applications such robotics there be large disparities in the size of agent's observation space (for example, the image generated by agent's camera), and a much smaller latent state space (for example, the agent's location and orientation) governing the rewards and dynamics. This size disparity offers an opportunity: how can we construct reinforcement learning (RL) algorithms which can learn an optimal policy using samples that scale with the size of the latent state space rather than the size of the observation space? Several families of approaches have been proposed based on solving various ancillary prediction problems including autoencoding (Tang et al. 2017 Hafner et al. 2019), inverse modeling (Pathak et al.) 2017] Burda et al.) 2018)) and contrastive learning (Laskin et al,, 2020) based approaches. These works have generated some significant empirical successes, but there provable (and hence more reliable) foundations for their success? More generally, what are the right principles for learning with latent state spaces?
In real-world applications, key issue is robustness to noise in the observation space. When noise comes from the observation process itself, such as due to measurement error, several approaches have been recently developed to either explicitly identify (Du et al. 2019 Misra et al.) 2020 Agarwal et al. 2020a) or implicitly leverage (Jiang et al.) 2017) the presence of latent state structure for provably sample-efficient RI. However, in many real-world scenarios, the observations consist of many elements (c.g. weather. lighting conditions, etc.) with temporally correlated dynamics (see c.g. Figure I and the example below) that are entirely independent of the agent's actions and rewards. The temporal dynamics of these elements precludes us from treating them as uncorrelated noise, and as such, most previous approaches resort to modeling their dynamies. However, this is clearly wasteful as these elements have no bearing on the RL problem being solved.
Work was done while the author Microsoft Research. (yefroni, dimisra, akshaykr, jel] @imerosoft.com eaachaggrwal@ggogglee

---

Published as a conference paper at ICLR 2022
Environment with Exogenous State
Observation
Generalized Inverse Dynamics
T
Agent
Train a model to predict the index of roll-in path
Endogenous state
Action
fo(idx (v a) x')
a
s'
V MM a
Exogenous
state
S
E'
Uniforml @ 11-
Uniform(A)
Policy cover for the time stop
Action space
Figure 1: Left: An agent is walking next to pond in a park and observes the world as an image. The world consists of latent endogenous state, containing variable such as agent's position, and much larger latent exogenous state containing variables such motion of ducks, ripples in the water, etc. Center: Graphical model the EX-BMDP. Right: PPE learns a generalized form inverse dynamics that recovers the endogenous state.
As an example, consider the setting in Figure 1 An agent is walking in a park on a lonely sidewalk next pond. The agent's observation space is the image generated by its camera, the latent endogenous state is its position on the sidewalk, and the exogenous noise is provided by motion of ducks, swaying of trees and changes in lighting conditions, typically unaffected by the agent's actions. While there is a line of recent empirical work that aims to remove causally irrelevant aspects of the observation (Gelada et al.) 2019 Zhang al.) 22200, theoretical treatment is quite limited (Dietterich) et al. 2018) and no prior works address sample-efficient learning with provable guarantees. Given this, the key question here is:
How can we learn using an amount of data scaling with just the size of the endogenous latent state, while ignoring the temporally correlated exogenous observation noise?
We initiate a formal treatment of RL settings where the learner's 's observations are jointly generated by a latent endogenous state and an uncontrolled exogenous state, which unaffected by the agent's 's actions and does not affect the agent's 'ss task. We study subset of such problems called Exogenous Block MDPs -BXD), where the endogenous state is discrete and decodable from the observations. We first highlight the challenges in solving EX- BMDPs by illustrating the failures of many prior representation learning approaches (Pathak et al., 2017 Misra et al. 2020; Jiang et al., 2017, Agarwal et al.) 2020a Zhang al. (2020). These failure happen either due creating too many latent states, such as one for each combination of ducks and passers-by in the example above leading to sample inefficiency in exploration, or due lack of exhaustive exploration.
We identify one recent approach developed by Du et al. (2019) with favorable properties for EX- BMDPs with wear-deterministic latent state dynamics. In Section 4 and [Section S] we develop variation of their algorithm and analyze its performance. The algorithm, called Path Prediction and Elimination (PPE), learns a form of multi-ster step inverse dynamics by predicting the identity of the path that generates an observation. For near-deterministic EX-BMDPs, we prove that PPE successfully explores the environment using A((S))² H log((Fl/5)) samples where endogenous state space, A is the number of actions, H is the horizon and F is function class employed to solve a maximum likelihood problem. Several prior works (Gregor et al., 2016 Paster et al. 2020) have also considered multi-ster step inverse dynamics approach to learn near optimal policy. Yet, these works do not consider the EX-BMDP model. Further, is unknown whether these algorithms have provable guarantees, PPE. Theoretical analysis of the performance of these algorithms in the presence of exogenous noise is an interesting future work direction.
the size of the latent
demonstrate the performance of PPE and various prior baselines in challenging exploration problem with exogenous noise. We show that baselines fail to decode the endogenous state as well learning a good policy. We further, show that PPE is able to recover the latent endogenous model in a visually complex navigation problem. in accordance with the theory.
Empirically, in /eectinn 6
2 EXOGENOUS BLOCK MDP SETTING
We introduce a novel Exogenous Block Markov Decision Process (EX-BMDP) setting to model systems with exogenous noise. We describe notations before formalizing the EX-BMDD model.
2

---

Published as a conference paper at ICLR 2022
Notations. For given set 21 we use A(U) to denote the set of all probability distributions over U. For a given natural number E N. we use the notation [N] to denote the set (1. .N). Lastly, for a probability distribution p A(U), we define its support supp(p) {u p(u) > 0, u U
We start with describing the Block Markov Decision Process (BMDP) Du et al. (2019). This process consists of finite set of observations X, set of latent states 2 with cardinality Z, finite set of actions A with cardinality A, a transition function T : 2 x A + A an emission function q: 2 x A- + ( reward function R: : X A + [0. horizon H N, and a start state distribution μ E ( The agent interacts with the environment by repeatedly generating H-step trajectories (21, 21 01, F1, ... 2H: HH. H. aH. TH) where 21 ~ =x-)) and for every h E [H] we have Ta g(: 2,), rh = R( an), and if h < H, then EΛ+1 ~ T( 2h, as). The agent does not observe the states (21, ... ,2H) instead receiving only the observations (#11... ... 3 and rewards (r1,'.. , .TH). We assume that the emission distributions of any two latent states are disjoint, usually referred as the block assumption: supp(q(- 21)) n supp(y( (22)) 0 when 2 * 22. The agent chooses actions using a policy : XX + A(A). We also define the set of non-stationary policies Ilss = 11 as a H-length tuple, with (TI..... ,TH) E Ins denoting that the action at time step is taken 0g TT 24)). The value ((T) of policy is the expected episodic sum of rewards ((x) == E. Σ h= R( ). The optimal policy is given by x² arg m V(x). We denote by Pr. (z) (T)
H
the probability distribution over observations x at time step h when following a policy q. Lastly, we refer to an open loop policy as an element in all A sequences of actions. An open loop policy follows a pre-determined sequence of actions {a,, a for H time steps, unaffected by state information.
Given the aforementioned definitions, we define an EX-BMDP as follows:
Definition 1 (Exogenous Block Markov Decision Processes). An EX-BM --BMDP is a BMDP such that the latent state can be decoupled into two parts & = (s. where s E 8 the endogenous state and & E E is the exogenous state. For z E Z the initial distribution and transition functions are decoupled, that is: p(z)= = (()) and T(2' 22 = T(s' 8, T55) [E).
The observation space X can be arbitrarily large model which could be high- -igh--imensional real vector denoting an image, sound, or haptic data in an EX-BMDP. The endogenous state s captures the information that can be manipulated by the agent. Figure center, visualizes the transition dynamics factorization. We assume that the set of all endogenous states S is finite with cardinality S. The exogenous state & captures all the other information that the agent cannot control and does not affect the information it can manipulate. Again, we make no assumptions on the exogenous dynamics nor on its cardinality | which may be arbitrarily large. We note that the block assumption of the EX-BMDP implies the existence of two inverse mappings: ø² : X + S to map an observation to its endogenous state, and oe X - to map it to its exogenous state.
Justification of assumptions. The block assumption has been made by prior work (e.g.. Du et al. (2019). [Zhang et al. (2020) to model many real-world settings where the observation is rich, i.e., it contains enough information to decode the latent state. The decoupled dynamics assumption made in the EX-BMDP setting is natural way to characterize exogenous noise; the type of noise that is not affected by our actions nor affects the endogenous state but may have non-trivial dynamic. This decoupling captures the movement of ducks, captured in the visual field of the agent in Figure and many additional exogenous processes (e.g., movement of clouds in a navigation task).
Goal. Our formal objective is reward-free learning. We wish find set of policies, we call a policy cover, that can be used to explore the entire state space. Given a policy cover, and for any reward function, we can find near optimal policy by applying dynamic programming (e.g.. [Bagnell
et al. 2004)), policy optimization (e.g.. Kakade and Langford ( Agarwal et al. (2020b): Shani itt al. 2020)) or value (e.g.. Antos et al. (2008) based methods.
Definition 2 (a-policy cover). Let Vn be a finite set of non-stationary policies. We say Vn is an a-policy cover for the hth time step if for all 2 E Z it holds that max (2(T)) 2 max (2(2)) - a. af 0 we call V a policy cover.
For standard BMDPs the policy cover is simply the set of policies that reaches each latent state of the BMDP (Du et al., 2019 Misra et al. 22200 Agarwal et al. (020a)). Thus, for a BMDP, the cardinality of the policy cover scales with [/. The structure of EX-BMDPs allows to reduce the size of the
3

---

Published as a conference paper at ICLR 2022
when the size of the exogenous state space is large. Specifically, we show that the set of policies that reach each endogenous state, and do not depend on the exogenous part of the state is also policy cover (see Appendixx B Proposition 4).
policy cover significantly to |S| 2
|
||
3 FAILURES OF PRIOR APPROACHES
We now describe the limitation of prior RL approaches in the presence of exogenous noise. We provide an intuitive analysis over here, and defer a formal statement and proof to Apppediix A
Limitation of Noise-Contrastive learning. Noise-contrastive learning has been used RL to learn state abstraction by exploiting temporal information. Specifically, the HOMER algorithm (Misra jet al. 2020) trains model to distinguish between real and imposter transitions. This is done by collecting dataset of quads (zz a, x', y) where y == 1 means the transition was (x, 2') was observed and y = 0 means that (z, a, x') was not observed. HOMER then trains a model (1 x, a, (x)))) with parameters 8, the dataset, by predicting whether given pair of transition was observed or not. This provides a state abstraction dy X + N for exploring the environment. HOMER can provably solve Block MDPs. Unfortunately, in the presence of exogenous noise, HOMER distinguishes between two transitions that represent transition between the same latent endogenous states but different exogenous states. In our walk in the park example, even if the agent moves between same points in two transitions, the model maybe able to tell these transitions apart by looking the position of ducks which may have different behaviour the two transitions. This results the HOMER creating ([))) many abstract states. We call this the under-abstraction problem.
Limitation of Inverse Dynamics. Another common approach in empirical works is based on modeling the inverse dynamics of the system, such the ICM module of Pathak et al. (2017). In such approaches, we learn a representation by using consecutive observations to predict the action that was taken between them. Such representation can ignore all information that is not relevant for action prediction, which includes all boogenous/unncottrllaabl ignore controllable information. This may result in failure sufficiently explore the environment. In this sense, inverse dynamics approaches result in an over-abstraction problem where observations from different endogenous states can be mapped to the same abstract state. The over-abstraction problem was described at Misra et al. (2020), when the starting state is random. In (pppeeddxx A.3 we show inverse dynamics may over-abstract when the initial starting state is deterministic.
information. However, it can also
Limitation of Bisimulation. Zhang et al. 20200) proposed learning bisimulation metric to learn a representation which is invariant to exogenous noise. Unfortunately. it is known that bisimulation metric cannot be learned in samplc-efficient manner (Modi al. (2020), Proposition B. Intuitively, when the reward is same everywhere, then bisimulation merges all states into single abstract state. This creates an over-abstraction problem in sparse reward settings, since the agent can falsely merge all states into a single abstract state until it receives a non-trivial reward.
Bellman rank might depend on []. The Bellman rank was introduced in Jiang et al. (0117) as a complexity measure for the learnability of an RL problem with function approximations. To date, most of the learnable RL problems have a small Bellman rank. However, we show in Apppnddx Ahtt Bellman rank for EX-BMDP can scale as O(E)). This shows that EX-BMDP is highly non-trivial setting as we don't I even have sample-efficiem algorithms regardless of computationalll--ffiiiii
In Apppnddii A we also describe the failures of FLAMBE (Agarwal al. 2020a)) and autoencoding
based approaches (Tang et al. 2017).
4 REINFORCEMENT LEARNING FOR EX- EX-BMDPS
In this section, we present an algorithm Predictive Path Elimination (PPE) that we later show can provably solve any EX-BMDP with nearly deterministic dynamics and start state distribution of the endogenous state, while making no assumptions on the dynamics or start state distribution of the exogenous state (Algorithm 1). Before describing PPE, we highlight that PPE can be thought of as
4

---

Published as a conference paper at ICLR 2022
Algorithm PPE(6, n): Predictive Path Elimination
1: Set V = {1), stochasticity level v S 4SH
I/1. denotes an empty path
2: for h = 2...... H do
3: Set N 16 (1 o A log
4: Collect dataset D of N i.i.d. tuples (z, v) where v Unf A) and I ~ P(znn v).
5: Solve multi-class classification problem: fn = arg max (x,,))D In ((ixx(v) x).
6: for S <i< j - 1 7 Al do
7:
Calculate the path prediction gap: (ii,)) = N ((E,)EDD [i]x) fx
8:
(i.)) S | then eliminate path v with idx(v)=j. //u, and V/ visit same state
3/8
9: v is defined as the set of all paths in v o A that have not been eliminated in line 8
a cumpuutationally-effiicie and simpler alternative to Algorithm 4 of Du et al. 2019) who studied rich-observation setting without exogenous noise
PPE performs iterations over the time steps h E (,....,,H, In the ht iteration, it learns a policy cover VA for time step containing open-loop policies. This is done by first augmenting the policy cover for previous time step by one step. Formally, we define Y,, ; o A = { a x E and then takes
nn a E A} where o is an open-loop policy that follows r till time step action Since assume the transition dynamics to be near-deterministic, therefore, we know that there exists a policy cover for time step that is a subset of Yr and whose size equal to the number of reachable states at time step h. Further, as the transitions are cear-deterministicc, we refer to an open-loop policy as a path, as we can view the policy as tracing a path in the latent transition model. PPE works by eliminating paths in T, that we are left with just single path for each reachable state. This is done by collecting a dataset 'D of tuples (r, v) where y is a uniformly sampled from Tr and x ~ PA [z) v) (line 4b. We train classifier fr. using D by predicting the index idx(v) of the path v from the observation x (line 5). Index of paths in Y, are computed with respect to Y and remain fixed throughout training. Intuitively, if fi (i x) is sufficiently large, then we can hope that the path U, visits the state (z).. Further, multistep inverse dynamics model since the open-loop policy contains information about all previous actions and not just the last action. For every pair of paths in Yn, first compute path prediction
view this prediction problem as learning
gap Å line 7/. If the gap too small, we show implies that these paths reach the same endogenous state, hence we can climinate a single redundant path from this pair (line 8). Finally, V/, is defined as the set of all paths in Y, which were not eliminated. PPE reduces RL to performing H standard classification problems. Further, the algorithm is very simple and in practice requires just a single hyperparameter (N). We believe these properties will make it well-suited for many problems.
Recovering an endogenous state decoder. We can recover a endogenous state decoder dr for each time step h (2,3. HH} directly from fo as shown below:
dn (x) = min {i f1 max fuli x) 00/ma)))) [[TAl]
Intuitively, this assigns the observation to the path with smallest index that has the highest chance of visiting x, and therefore, x" (x:). We are implicitly using the decoder for exploring, since we rely on using fr. for making planning decisions. We will evaluate the accuracy of this decoder in Section 6
Recovering the latent transition dynamics. PPE can also be used to recover a latent endogenous transition dynamics. The direct way is to use the learned decoder Φi along with episodes collected by PPE during the course of training and do count-based estimation. However, for most problems, recovering an approximate deterministic transition dynamics suffices, which can be directly read
Alg. 4 has time complexity of (S A A'H) compared to OSS A H) for PPE. Furthermore, Alg. 4 requires upper hound on S, whereas PPE is adaptive to it. Lastly, Du et al. 2019) assumed deterministic setting while we provide generalization near-deter..nism.
5

---

Published as a conference paper at ICLR 2022
from the path elimination data. We accomplish this by recovering a partition of paths in 1n-1 x A where two paths in the same partition set are said to be merged with each other. In the beginning. each path is only merged with itself. When we eliminate path vj on comparison with v; in line 8 then all paths currently merged with Uj get merged with vi. We then define an abstract state space
S, for time step h that contains an abstract state j for each path Vy V. Further, recover latent deterministic transition dynamics for time step h as pn-1 : S x A -> Sn where we set o j j if the path Vy E U h gets merged with path uy o a E V where ey E 1--1-
Learning near optimal policy given policy cover. PPE runs in reward setting. However, the recovered policy cover and dynamics can be directly used to optimize any given reward function with existing methods. If the reward function depends the exogenous state then we can the PSDP algorithm (Bagnell et al. (004) to learn a mear-optimal policy. PSDP is a model-free dynamic programming method that only requires policy cover as input (see Appendix D.1 for details). If the reward function only depends on the endogenous state, we can use computationally cheaper value-iteration VI that uses the recovered transition dynamics. is a model- algorithm that estimates the reward for each state and action, and performs dynamic programming on the model (see (Appendix D.2 for details). In each case, the sample complexity of learning a near-optimal policy, given the output of PPE, scales with the size of endogenous and not the exogenous state space.
THEORETICAL ANALYSIS AND DISCUSSION
We provide the main sample complexity guarantee for PPE as well as additional intuition for why it works. We analyze the algorithm in determiieeiiiiiccc MDPs defined as follows: Two transition
functions Ti and T2 are n-close if for all h [H] a E A, s E S, it holds that [-T s.a) - T2(-) 8, a]]lı S 7/- Analogously, two starting distribution Ja and jl2 are ry-close if [| (2( S n.
We emphasize that bear-deterministic dynamics are common in real-world applications like robotics.
Assumption (Near deterministic endogenous dynamics). We assume the endogenous dynamics is --llose to deterministic model (UDD. TD.1) where 1) S 1/(4HH).
We make a realizability assumption for the regression problem solved by PPE (line 5). We assume that F is expressive enough to represent the Bayes optimal classifier of the regression problems created by PPE.
Assumption 2 (Realizabilitt). For any h E [H), and any set of paths T S A with [M] S SA and where A denotes the sei of all paths of length h, there exists Ji,, E F such that: ft,, (idx(v)
(z)))) 2)) Ev'er (a( (w)))ur for all u E "f and x E X with Ever Pn (x)) v') >
Realizability assumptions are common in theoretical analysis (c.g., Misra et al. 2020). Agarwal ct al. (2020a). In practice, we use expressive neural networks to solve the regression problem, so we expect the realizability assumption hold. Note that there most (H Bayes classifiers for different prediction problems. However, this is acceptable since our guarantees will scale as In [F] and, therefore, the function class F can be exponentially large accommodate all of them.
We now state the formal sample complexity guarantees for PPE below.
Theorem (Sample Complexity). Fix d E (0, 1). Then, with probability greater than 1 8, PPE II such that for any h E [H], V is a n/H aoo-ipolcy cover for time step
returns a policy cover ( and 1 < S, which gives the total number of episodes used by PPE as O (52 (5 In LFSAH
We defer the proof to Appendix C. Our sample complexity guarantees do not depend directly on the size of observation space or the exogenous space. Further, since our analysis only uses standard uniform convergence arguments, it extends straightforwardly to infinitely large function classes by replacing In [F] with other suitable complexity measures such as Rademacher complexity.
Why does PPE work? We provide an asymptotic analysis to explain why PPE works. Consider deterministic setting and the hh iteration of PPE. Assume by induction that V is an exact policy cover for time step h - 1. Therefore, Y,, V - A is also a policy cover for time step h. However, it may contain redundancies; it may contain several paths that reach the same endogenous state. We now show how generalized inverse dynamics objective can eliminate such redundant paths.

---

Published as a conference paper at ICLR 2022
Modian number of opicoles
SC0000
Piu
102
Decodho accurszy
200000
$1
82h
120000
1000
82
836
1000
50
65 1.0
1.5 35
35
580
2.50
3.55
Ponionn
training
(a) Combination lock (H 2).
(b) Regret plot
(c) Decoding accuracy
Figure 2: Results combination lock. Left: We show the latent transition dynamics of combination lock. shown for brevity. Center: Shows minimal number of episodes needed to achieve mean regret of at most V(x*) 1/22. Right: State decoding accuracy (in percent) decoders learned by different methods. Solid lines implies no exogenous dimension while dashed lines imply an exogenous dimension of 100.
Observations
Let PA (E) denote the distribution over exogenous states at time step h which is independent of agent's policy. The Bayes optimal classifier (fA = STA.) of the prediction problem can be derived as:
fit (idx(v) x) = PA(u
(a v)P(p)
Pa(2 v)
(b)
(=))
EV'r, Pa( P')P("))
EVET, PA
EVET (n(
where (a) holds since all paths in Tr chosen uniformly, and (b) critically uses the fact that for any open-loop policy we have a factorization property,
Fn v) = q (x (x),, (x)) (a(o (o)(()
Let v1 U2 T be two paths with indices i and respectively. We define their exact path prediction gap as (i, = En, [[ xx)) - (i xx)]]. Assume that visits an endogenous state at time step h and denote w()) the number of paths in Y that reaches Then fū w.) 1/a(s) if 6* (Ix) = s, and 0 otherwise. If U2 also visits at time step h, then fī (i) 2hh = fi .y) for all Ty. This implies j) and PPE will filter out the path with higher index since detected both paths reach to the same endogenous state. Conversely, let U2 visit different state at time step h. If x is an observation that maps s, then (i z) 1/w(s) and f x) = O. This gives ( x) M7 x) 1/w(a) 2 2/|mul and, consequently, A(i,j) > 0. In fact, we ((.)) 2 ((/IT,,) Thus, PPE will not eliminate these paths upon comparison. Our complete analysis in the Appendix generalizes the above reasoning to finite sample setting where we can only approximate fū and A, as well as to EX-BMDP- with near sear-dtterminisicc dynamics.
show
As evident, the analysis critically relies on the factorization property that holds for open-loop policies but not for arbitrary ones. This is the reason why we build a policy cover with open-loop policies.
6 EXPERIMENTS
We evaluate PPE on two domains: a challenging exploration problem called combination lock to test whether PPE learn an optimal policy and an accurate state decoder, and visual-grid world with complex visual representations to test whether PPE is able to recover the latent dynamics.
Combination Lock Experiments. The combination lock problem is defined for a given horizon H by an endogenous state space S = {si.a) U {sh.a: Sh,b, * an exogenous state space E= { 1)" " an action space A with 10 actions, and deterministic endogenous start state of $ For any state 8h.g we call y as its type which can a, b c. States with type a and are considered good states and those with type are considered bad states. Each instance of this problem is defined by two good action sequences (an) (a/))
with on * ah, which are chosen uniformly randomly and kept fixed throughout. At h = 1, the agent is in $1.a and action aj leads to 82,a, dj leads to $2,6. and all other actions lead to $2,c- For h > 2, taking action aj in $h,a leads to 84+1,a and taking action a' in Sh.b leads to $1+1 In all other cases involving taking action in state Sh.g. transition to the next bad state $441.0- We visualize the latent endogenous dynamics in Figure 2b. The exogenous
state evolves as follows. We set & E {0, 10 where (i) ~ Unf (f0, I}) for each i E [H]. At time step h, En is generated from E by uniformly flipping each bit in Ea-1 independently with
7

---

Published as a conference paper at ICLR 2022
probability 0.1. There is reward of 1.0 taking the good action H, a in HH and reward of 0.1 on taking action aHe in sH.b. Otherwise, the agent gets a reward of O. This gives a V(x*) = 1, and the probability that a random open loop policy gets this optimal return is 10-H H
An observation x is generated stochastically from latent state = (s, E). We map s to vector w encoding the identity of the state. We concatenate (w, E), add Gaussian noise to each dimension, and multiply the result by a Hadamard matrix to generate x. See Appendix Forr full details. Our construction is inspired by prior work (Du et al. 2019 Misra et al. 22220).
Baseline. We compare PPE with five baselines on the combination lock problem. These include PPO (Schulman et al. 2017) which is an actor-critic algorithm, PPO + RND (Burda et al. 2019) which adds an exploration bonus to PPO using prediction errors, Homer that uses contrastive learning (Misra et al. 2020), and another algorithm ID which is similar to Homer but instead of contrastive learning it learns an inverse dynamics model to recover the state abstraction. Lastly, we also compare with
Bisim that learns bisimulation metric along with an actor-critic agent (Zhang et al. (2020)). We use existing publicly available codebases for these baselines. Our implementation of PPE very closely follows the pseudo-code in [Algorithm
We model F using a two-layer feed-forward network with ReLU non-linearity. We train J. with Adam optimization and use a validation set to do model selection. We refer readers to Appendix F for additional experimental details.
Results. Figure 2 shows results for values of H in {5, 10, 20, 40). For each value of H, we plot the minimal number of episodes n needed to achieve a mean regret of at most 1/=0 = 0.5. We run each algorithm 5 times with different seeds and report the median performance. If an algorithm is unable to achieve the desired regret in 5 x 10s episodes we set n = co. We observe that PPO unable to solve the problem at H 5. PPO + RND is able to solve the problem at H 5 and exploration H = 10, showing the exploration bonus induced by random network distillation helps. However,
it is unable to solve the problem for larger values of H. We observe that Homer and ID are also unable to solve the problem for any value of H. Bisim also fails to solve the problem for any H 2 5. This agrees with the theoretical prediction that Bisim provides no learning signal when running in sparse-reward settings. In the absence of any reward, the bisimulation objective incentivizes mapping all observations to the same representation which is not helpful for further exploration. Lastly, PPE is able to solve the problem for all values of H and is significantly more sample efficient than baselines. Since the reward function of the combination-lock problem depends only on the endogenous state, we run PPE and then value-iteration like algorithm (see Appendix 1.2 learn near optimal policy.
In order to understand the failure of Homer and ID, we investigate the accuracy of the state abstraction learned by these methods and compare that with PPE. We focus the combination lock setting with H = 2 and evaluate the learned decoder for the last time step. As the state abstraction models are invariant to label permutation we use the following evaluation metric: given a learned abstraction 1()(r,,) = 6(2,,2) + o² (2,,1)= = o² (xx.2)) where {Ir,,, ( h are drawn independently from a fixed distribution D with good support over all states. We report the percentage accuracy in FFigure 2/. When there is no exogenous noise, Homer is able to Iearn good state decoder with enough samples while ID fails to learn, in accordance with the theory. On inspection, we found that ID suffers from the under-abstraction issue highlighted earlier it has difficulty separating observations from 83a and 836. On adding exogenous noise, the accuracy of Homer plummets significantly. The accuracy of ID also drops but this drop is mild since unlike Homer, the ID objective able to filter exogenous noise. Lastly, we observe that PPE is always able to learn a good decoder and is more sample efficient than baselines.
for the endogenous state & X + [N] we compute 1/m E 1
Visual Grid World Experiments. We test the ability of PPE to recover the latent endogenous transition dynamics in visual grid-world problem The agent navigates in a N x N grid world where each grid can contain a stationary object, the goal, or the agent. The agent's 's endogenous state is given by its position in the grid and its direction amongst four possible canonical directions. The agent can take five different actions for navigation. The world is visible to the agent as a 8N x 8N sized RGB image. We add exogenous noise follows: at the beginning of each episode, we independently sample position, size and color of 5 ellipses. The position and size of these ellipses is perturbed after each time step independent of the action. We project these ellipses on top of the world's image. Figure 3 shows sampled observations from the 7 x 7 gridworld that we experiment on. The
"We use the following popular gridworld codebase: http:///iihh...mmmmmsiimocyyymmm
8

---

Published as a conference paper at ICLR 2022
Numbor ehnisdinn
23332
Dvccehe AEIAN
enar of
20033
5932
Chance
300033 230000 300038 43500e 500690 Number apisades
Siz saiking sata
(a) Grid World h = 1. (b) Grid World h 2.
(c) Model Errors
(d) State decoding accuracy
Figure 3: Results on visual grid world. Left two: Shows sampled observations for the first two steps from the visual gridworld domain. The agent is depicted red-triangle, lava in orange, walls in grey, and the goal in green. Center Right: Shows errors of type and type 2 made by the PPE in recovering the latent endogenous dynamics. Right: State decoding accuracy of PPE, Homer and a random uniform decoder. (see SeeeStccionn 6)
exogenous state is given by the position, size and color of ellipses and is much larger than |S] S 4N2, We model F using a two-layer convolutional neural network and train it using Adam optimization. We defer the full details of setup to Appendix F
Since the problem has deterministic dynamics, we evaluate the accuracy of the learned transition model by measuring it in terms of accuracy of the elimination step (Algorithm I line 8). since this step induces our algorithm's 's mapping from observations to endogenous latent states. For a fixed h (2..... H). let is and vj be two paths in 1 A. We compute error computes whether PPE merged these paths, i.e., predicted them as mapping to the same abstract state, when they go to different endogenous states. Type 2 error computes whether PPE predicted the paths as mapping to different abstract states, when they map to the same endogenous state. We report the total number of errors of both types by summing over all values of h and all pairs of different paths in , A. Type errors are more harmful, since they can lead to exploration failure. Specifically, merging paths going to different states may result in the algorithm avoiding one of the two states when exploring at the next time step. Type errors are less serious but lead to inefficiency due to using redundant paths for exploration.
type of errors. Type 1
Results. We report results learning the model in in Figuree 3p. We see that PPE is able to reduce the number of type errors down to O using 2 x 10a episodes per time step. This is important since even single type error can cause exploration failures. Similarly, PPE is able to reduce type errors and is able to get them down to 56 with 5 x 10t episodes. This is acceptable since type 2 errors do not cause exploration failures but only cause redundancy. Therefore, 2 x 10t samples, the algorithm makes ( type 1 errors and just handful type 2 errors. This is remarkable considering that PPE compares roughly x 10 pairs of paths in the entire run. Hence, makes only S 0.03% type 2 errors. Further, the agent is able to plan using the learned transition model and receive the optimal return. We also evaluate the accuracy of state decoding on this problem. We compare the state decoding accuracy of PPE and Homer at H = 2 using an identical evaluation setup to the one we used for combination lock. Figure 31 shows the results. As expected, PPE rapidly learns a highly accurate decoder while Homer performs only well as random uniform decoder.
CONCLUSION
In this work, we introduce the EX-BMDP setting, an RL setting that models exogenous noise, ubiquitous many real-world systems. We show that many existing RL algorithms fail in the presence of exogenous noise. We present PPE that learns multi-step inverse dynamics to filter exogenous noise and successfully explores. We derive theoretical guarantees for PPE near-deterministic setting and provide encouraging experimental evidence in support of our arguments. To our knowledge, this is the first such algorithm with guarantees for settings with exogenous noise. Our work also raises interesting future questions such how to address the general setting with stochastic transitions, or handle more complex endogenous state representations. Another interesting line of future work direction is the analysis of other approaches that learn multi-step inverse dynamics (Gregor et al.) 2016, Paster et al. 2020) and understanding whether these approaches can also provably solve EX-BMDDS.

---

Published as a conference paper at ICLR 2022
ACKNOWLEGMENTS
We would like to thank the reviewers for their suggestions and comments. We acknowledge the help of Microsoft's GCR team for helping with the compute. YE is partially supported by the Viterbi scholarship, Technion.
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, 2014.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in Neural Information Processing Systems, 2020a.
Alekh Agarwal, Sham M Kakade, Jason Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference Learning Theory, 2020b.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning. 2008.
J Andrew Bagnell, Sham M Kakade, Jeff G Schneider, and Andrew Y Ng. Policy search by dynamic programming. In Advances in Neural Information Processing Systems, 2004.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large- scale study of curiosity-driven learning. In International Conference on Learning Representations, 2018.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, 2017.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert Schapire. On oracle-efficient PAC RL with rich observations. In Advances in Neural Information Processing Systems, 2018.
Thomas Dietterich, George Trimponias, and Zhitang Chen. Discovering and removing exogenous state variables and rewards for reinforcement learning. arXiv preprint arXiv:1806.00 584, 2018.
Simon S Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, 2019.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Mare G Bellemare. Deepmdp: Learning continuous latent space models for representation learning. In International Conference on Machine Learning, 2019.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 2003.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint /61 1005077 2016.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In International Conference on Machine Learning, 2019.
10

---

Published as a conference paper at ICLR 2022
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low Bellman rank are PAC-leamable. In International Conference on Machine Learning, 2017.
Sham M Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, 2002.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems, 2008.
Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Curl: Contrastive unsupervised representations for reinforcement learning. In International Conference on Machine Learning. PMLR, 2020.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning. pages 6961-6971. PMLR, 2020.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics. PMIR, 2020.
Keiran Paster, Sheila Mcllraith, and Jimmy Ba. Planning from pixels using inverse dynamics models. In International Conference Learning Representations. 2020.
Deepak Pathak, Pulkit Agrawal, Alexei Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, 2017.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy
optimization algorithms. arXiv:1707.06344 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. #Exploration: A study of count-based exploration for deep reinforcement learning. In Advances Neural Information Processing Systems, 2017.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. arXiv preprint arXiv:2006. 10742, 2020.
Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. International Conference on Learning Representations, 2021. URL Stlhttps: http:::tttpppot/io/e http:///pppreeeee.eeeeeeeeeeeeee 2d==2FCWDKRRBU


Reviews:
[{"review_id": "tWeV_s7iDdW", "reviewer": "Reviewer_Zamv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- EX-BMDPs seem to capture several popular simulated distractors that are currently being used in applied RL papers, such as random video backgrounds in MuJoCo tasks. I suspect the fact that the exogenous dynamics are relatively unconstrained will also make them a good model for practical tasks. The requirement for near-determinism in the endogenous dynamics is unfortunate, particularly given that it applies to the initial state distribution as well (often you want to perform well over a distribution of similar-but-not-identical tasks). However, I think this is not a major concern for exploration methods: so long as the possible initial states are reachable from some common starting state within $H$ steps, PPE will eventually explore them.\n- The fact that it is possible to obtain a sample complexity bound completely independent of the complexity of $\\Xi$ was surprising to me given the relatively complex form of exogenous noise in an EX-BMDP, and shows that the EX-BMDP class is at least tractable.\n- The clarity of writing was appreciated, particularly when stating assumptions and comparing against past algorithms.\n\nWeaknesses:\n\n- I noticed that RND is missing from Section 3/Appendix A (shortcomings of existing methods), but does surprisingly well on the combination lock problem. Is it possible to give some intuition for where RND fails in general?\n- The visual gridworld experiments are a little confusing. The takeaway seems to be that PPE drives accuracy to \\~100% eventually on a less-toy problem. However, there are no baselines, so it is hard to determine how significant this achievement is. It would be useful to see how the baselines from Figure 2 fare in this setting, particularly in terms of sample efficiency.", "summary_of_the_paper": "This paper proposes a new class of decision problems, the exogenous block-MDP (EX-BMDP), and an algorithm for acquiring minimal state representations for EX-BMDPs. EX-BMDPs are an extension of block MDPs that allows for additional \"exogenous\" state components that may have arbitrary Markovian dynamics, but cannot be influenced by actions, including through the actions' effects on \"endogenous\" state. The proposed algorithm, PPE, is able to recover a mapping from observed states to endogenous states (i.e. ignoring the latent distractor variables) in the setting where the endogenous state dynamics and initial state distribution are near-deterministic. It does this by comparing the set of policies that can reach each pair of states: informally, if $p(\\pi \\mid s_1) = p(\\pi \\mid s_2)$ for all policies $\\pi$ (assuming a uniform $p(\\pi)$), then $s_1$ and $s_2$ are treated as equivalent. In the deterministic case, policies reduce to action sequences (\"paths\"). Illustrative experiments on simple domains show that the proposed approach is able to quickly recover a state representation that depends mostly on the endogeneous component.", "summary_of_the_review": "This paper proposes a general but tractable class of MDPs with exogenous distractors, and proposes a novel algorithm which provably obtains representations that exclude the spurious latent dimensions of the state. Given the technical significance of the work, I am in favour of acceptance.\n\n-----\n\n**Update:** the author response resolves the issue with visual gridworld experiments. I'm still in favour of acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "mGKnzIzkL-Y", "reviewer": "Reviewer_yfQT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- The problem setting is important and seems to be relevant to many real-world problems.\n- While the idea of using inverse dynamics and even multi-step inverse dynamics [1] to learn representations in these types of environments to learn controllable representations is not novel, this paper provides a theoretical basis for this choice, which I think is valuable.\n- I found sections 1 through 5 to be very well written.\n\nWeaknesses:\n\n- In the experiment section, it seems as though you are testing the planning/policy learning abilities with PPE in both of the environments. However, as far as I can tell, there is no indication of how you perform this planning in PPE in the main text. The paper simply switches from talking about learning policy covers to showing regret for environments with only a small mention of the fact that you could plan using the data collected with PPE. The way the experiments are run and the choice to test the planning performance / how the state representations are obtained in experiments should be explained in more detail in my opinion.\n- The paper discusses prior works with inverse dynamics seemingly only in the context of their applications in representation learning in two prior works on exploration. I think the application of multi-step inverse dynamics in goal-conditioned environments described in [1] is worth mentioning, since for a fixed goal this algorithm seems like it is doing something similar to PPL. Related is the lack of a \"related works\" section in the paper, which would be helpful for framing PPL in the context of prior works.\n- There is no conclusion section, which I feel would improve the paper.\n\nMy major questions are:\n\n1. How is the policy learning done in the experiment section? How are representations found in the decoding accuracy plot?\n2. How does this paper relate to prior works on inverse dynamics?\n\n[1] Paster, Keiran, et al. Planning from Pixels Using Inverse Dynamics Models. 2020. openreview.net, https://openreview.net/forum?id=V6BjBgku7Ro.", "summary_of_the_paper": "This paper introduces a model called the Exogenous Block MDP (EX-BMDP) where the latent state contains both controllable (endogenous) and uncontrollable (exogenous) elements. The paper proposes an algorithm to find a policy cover with sample complexity that depends only on the size of the endogenous state rather than the observation or exogenous state. The algorithm works by training a classifier to predict the actions that were taken to get to a state. Since the exogenous state is not affected by actions, states for which the classifier returns similar results are likely the same endogenous state. The algorithm builds up a set of policies (sequences of actions are sufficient in the near-deterministic setting) which visit unique endogenous states by using the classifier to deduplicate redundant action sequences. Besides proving the sample efficiency of their approach, experiments are provided which show that this algorithm performs better than baseline approaches in terms of performance as well as in ability to decode the state from its representation in a simple combination lock environment as well as a grid world with distractors.", "summary_of_the_review": "In my opinion, the contribution of the paper is strong since it analyzes an important problem setting, presents an analysis of representations learned using inverse dynamics, and shows that it works in practice. The weaknesses, specifically little discussion of prior work and problems with the experiment section seem fixable, and under the condition that these points improve, I will recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VQW1iO293p", "reviewer": "Reviewer_fNfe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well motivated. It has convinced me that being invariant to exogenous noise is important and that the EX-BMDP is useful abstraction for making this problem concrete. It is also very clearly presented. The argumentation is clear, and the flow of the paper is quite natural. Even the lengthy appendix is fairly easy to parse, with straightforward proofs and relevant details (e.g. specific claims about the unsuitability of alternative approaches).\n\nOne shortcoming is potential impact / applicability. I'm not convinced that environments with single starting states and near-deterministic dynamics is a very rich problem class. Or more specifically, I'm not convinced that restricting myself to this class would be preferable to working in the full space of MDPs with e.g. the possibility of aliasing a few states with a single-step inverse-dynamics approach. I am aware that impact is very hard to predict in advance, so I won't let this aspect unduly affect my scoring. And I'm convinced that even if PPE is never used in practice, this paper should still be accepted for its useful problem formulation and theoretical results. But a quick read would leave one with the impression that the alternatives (e.g. contrastive learning, inverse dynamics, bisimulation metrics) flaws outweigh their considerable advantages (e.g. applicability with stochastic dynamics) --  explicitly noting where alternative approaches are preferable would be appreciated.\n\nI also noticed what I believe to be an omission in your related works: mutual information / empowerment based methods. \"Variational Information Maximisation for Intrinsically Motivated Reinforcement Learning\" seems particularly related in its search for predicable action sequences. And the follow-up work \"Variational Intrinsic Control\" appears to be a multi-step inverse dynamics analog that doesn't require open-loop policies. If you can show that these approaches are flawed in a way that PPE is not, then that would considerably raise my assessment of this work. And even if not, I believe this field (if not these specific works) should be acknowledged, as they similarly attempt to learn what in the environment is controllable.\n\nWhile I agree that PPE is applicable in no-reward situations whereas bi-simulation metrics are not, your experiments all involve rewards, so I'm surprised a bi-simulation metric method was not included as a baseline.\n\nWhile this isn't necessary for acceptance, it is worth noting that prior work has established much more challenging benchmarks for evaluating the representation of exogenous noise, and utilizing a pre-existing benchmark would make your empirical results considerably more impressive.\n\nThis is a small point, but it is not initially obvious why inverse dynamics fails on the combination lock problem. Does alliasing occur just when e.g. s_2a --> s_3a and s_2b-->s_3b have the same action?", "summary_of_the_paper": "The authors propose a novel algorithm PPE, which they prove efficiently eliminates exogenous noise under certain assumptions (e.g. near deterministic dynamics). PPE works by growing a set of open-loop policies (action sequences) sufficient to reach all possible states for an increasing horizon. This is done by predicting the index of the policy from its final state, and eliminating states that are not sufficiently predictable. They show that both in theory and in practice that popular alternatives (noise contrastive and inverse-dynamics approaches) either fail to ignore exogenous noise or fail to distinguish between actually different states.", "summary_of_the_review": "A well-argued paper that sets up an important problem and introduces a novel algorithm (PPE) to solve it. This is somewhat undercut by PPE only working in a restrictive setting. Empirical results would benefit from an additional baseline (bisimulation) and (optionally) a previously published benchmark. Some discussion of mutual information approaches should be made. But some reasonable attempt is made towards these improvements, I'd happily see this work accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EGQFMOseoV", "reviewer": "Reviewer_B1Cs", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "STRENGTHS\n\n(S1) The problem of efficiently learning in high-dimensional observation spaces is a good one, and the authors provided an excellent discussion of the technical components of this problem in the early parts of the paper. I thought the definition and presentation of the EX-BMDP was particularly good.\n\n(S2) I appreciate the authors providing experimental results to show that PPE performs well in some regards.\n\nWEAKNESSES\n\n(W1) I'm afraid I found the discussion of PPE to be a bit difficult to decode. Even looking at Algorithm 1, I find myself with a number of important questions unanswered, chief among them being \"what about $\\phi^*_e$\"? It strikes me as odd that nowhere in this algorithm are the inverse mappings from observation to exogenous/endogenous state represented or used. Why is this?\n\n(W2) I'm a little concerned with the computational tractability of the algorithm. My understanding from the paper is that one seeks some sort of \"covering\" of the state space--in what sense is it practical to obtain and/or store this covering? If the problem setting consists of high-dimensional observations this seems especially challenging.\n\n(W3) From my naive perspective, it seems that the ultimate goal here is to use PPE and then actually perform reinforcement learning. However, I didn't understand from the brief discussion at the end of Section 4 (or, frankly, from reading the Appendix) how exactly that would be accomplished. I feel this is important enough that it should appear in the main paper.\n\nPOST-DISCUSSION COMMENTS\n\nDuring the discussion, I feel as though the authors adequately addressed each of the issues I raised above, and so I'm happy to raise my score to accept.", "summary_of_the_paper": "The authors consider the problem of reinforcement learning using high-dimensional observations (eg, images) that may contain both exogenous and endogenous state information. Seeking to remedy the issues with learning that arise due to the exogenous state information, the authors propose a new model called an Exogenous Block MDP (EX-BMDP) and a new algorithm called Predictive Path Elimination (PPE) to learn a generalization of the inverse dynamics of the EX-BMDP. Additionally, the authors present some experimental evidence that PPE performs well in the EX-BMDP setting compared to alternatives.", "summary_of_the_review": "While I appreciate the importance of the problem setting and think I understand the general thrust of the paper here, I overall left the paper with a lot of confusion. I'm hoping the authors can provide clarity here--both in their response and by revising the manuscript--during the discussion phase. Indeed, after some discussion and edits to the paper, I feel that the paper is much more clear and recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new technique that infers the endogenous states of an RL problem, as well as the corresponding model and optimal policy.  A bound is derived that shows that the amount of data needed depends only on the number of endogenous states, while being independent of the number of exogenous states and the complexity of the observation space.  This is remarkable since this is the first technique that is shown to have a complexity that depends only on the number of endogenous states.  Furthermore, the bound derived is not just a theoretical bound.  It is a practical bound in the sense that it is used in the associated algorithm, which is demonstrated effectively on two problems.  Perhaps the main weakness of the paper is that no intuition is provided in the main paper to explain why the sample complexity can be made independent of the number of exogenous states and the complexity of the observation space.  The reader has to look at the proof in the supplementary material.  Nevertheless, this is remarkable work.
Decision: Accept (Oral)