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.

heading: 1 INTRODUCTION
text: In many real-world applications such as robotics there can 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 are 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, a 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 RL. However, in many real-world scenarios, the observations consist of many elements (e.g. weather, lighting conditions, etc.) with temporally correlated dynamics (see e.g. Figure 1 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 dynamics. However, this is clearly wasteful as these elements have no bearing on the RL problem being solved.
As an example, consider the setting in Figure 1. An agent is walking in a park on a lonely sidewalk next to a pond. The agent’s observation space is the image generated by its camera, the latent
{yefroni, dimisra, akshaykr, jcl}@microsoft.com, alekhagarwal@google.com
endogenous state is its position on the sidewalk, and the exogenous noise is provided by motion of ducks or people in the background, 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 et al., 2020), 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 observations are jointly generated by a latent endogenous state and an uncontrolled exogenous state, which is unaffected by the agent’s actions and does not affect the agent’s task. We study a subset of such problems called Exogenous Block MDPs (EX-BMDPs), 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 et al., 2020). These failure happen either due to 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 to lack of exhaustive exploration.
We identify one recent approach developed by Du et al. (2019) with favorable properties for a class of EX-BMDPs with near-deterministic latent state dynamics. In Section 4 and Section 5, we develop a variation of their algorithm and analyze its performance for near-deterministic EX-BMDPs. The algorithm, called Path Prediction and Elimination (PPE), learns a form of multi-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 O((SA)2H log(|F|/δ)) samples where S is the size of the latent endogenous state space, A is the number of actions, H is the horizon and F is a function class employed to solve a maximum likelihood problem of inferring the path which generated an observation. Several prior works (Gregor et al., 2016; Paster et al., 2020) have also considered a multi-step inverse dynamics approach to learn a near optimal policy. However, these works do not consider the EX-BMDP model. Further, it is unknown whether these algorithms have guarantees for EX-BMDP similar to what we present for PPE. Theoretical analysis of the performance of these algorithms in the presence of exogenous noise is an interesting future work direction.
Empirically, in Section 6, we demonstrate the performance of PPE and various prior baselines in a challenging exploration problem with exogenous noise. We show that baselines fail to decode the endogenous state and either end up over-abstracting (creating an abstract state which aliases essentially-different states) or under-abstracting (creating essentially the same clones of states). We further, show that PPE is able to recover the latent endogenous model in a visually complex navigation problem, in accordance with the theory.

heading: 2 EXOGENOUS BLOCK MDP SETTING
text: We introduce a novel Exogenous Block Markov Decision Process (EX-BMDP) setting to model environments with exogenous noise. We briefly describe notations before presenting a formal treatment of EX-BMDP.
Notations. For a given set U , we use ∆(U) to denote the set of all probability distributions over U . For a given natural number N ∈ N, we use the notation [N ] to denote the set {1, 2, · · · , N}. Lastly, for a probability distribution p ∈ ∆(U), we define its support as 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 a finite set of observations X , a set of latent states Z with cardinality Z, a finite set of actions A with cardinality A, a transition function T : Z × A → ∆(Z), an emission function q : Z × A → ∆(X ), a reward function R : X × A → [0, 1], a horizon H ∈ N, and a start state distribution µ ∈ ∆(Z). The agent interacts with the environment by repeatedly generating H-step trajectories (z1, x1, a1, r1, · · · , zH , xH , aH , rH) where z1 ∼ µ(·) and for every h ∈ [H] we have xh ∼ q(· | zh), rh = R(xh, ah), and if h < H , then zh+1 ∼ T (· | zh, ah). The agent does not observe the states (z1, · · · , zH), instead receiving only the observations (x1, · · · , xH) and rewards (r1, · · · , rH). We assume that the emission distributions of any two latent states are disjoint, usually referred as the block assumption:
supp(q(· | z1)) ∩ supp(q(·|z2)) = ∅ when z1 6= z2.
The agent chooses actions using a policy π : X → ∆(A). We also define the set of non-stationary policies ΠNS = ΠH as a H-length tuple, with (π1, · · · , πH) ∈ ΠNS denoting that the action at time step h is taken as ah ∼ πh(· | xh). The value V (π) of a policy π is the expected episodic sum of rewards V (π) := Eπ[ ∑H h=1R(xh, ah)]. The optimal policy is given by π
? = arg maxπ∈ΠNS V (π). We denote by Ph(x|π) the probability distribution over observations x at time step h when following a policy π. Lastly, we refer to an open loop policy as an element in all AH sequences of actions. An open loop policy follows a pre-determined sequence of actions {a1, .., aH} 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-BMDP is a BMDP such that the latent state can be decoupled into two parts z = (s, ξ) where s ∈ S is the endogenous state and ξ ∈ Ξ is the exogenous state. For z ∈ Z the initial distribution and transition functions are decoupled, that is: µ(z) = µ(s)µξ(ξ), and T (z′ | z, a) = T (s′ | s, a)Tξ(ξ′ | ξ).
The observation space X can be arbitrarily large to model which could be a high-dimensional 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 1, 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: φ?e : X → S to map an observation to its endogenous state, and φ?g : 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 a 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 1, and many additional exogenous processes (e.g., movement of clouds in a navigation task).
Goal. Our formal objective is reward-free learning. We wish to find a 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 a near optimal policy by applying dynamic programming (e.g., Bagnell et al. (2004)), policy optimization (e.g., Kakade and Langford (2002); Agarwal et al. (2020b); Shani et al. (2020)) or value (e.g., Antos et al. (2008)) based methods.
Definition 2 (α-policy cover). Let Ψh be a finite set of non-stationary policies. We say Ψh is an α-policy cover for the hth time step if for all z ∈ Z it holds that maxπ∈Ψh Ph(z|π) ≥ maxπ∈ΠNS Ph(z|π)− α. If α = 0 we call Ψh 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., 2020; Agarwal et al., 2020a). Thus, for a BMDP, the cardinality of the policy cover scales with |Z|. The structure of EX-BMDPs allows to reduce the size of the policy cover significantly to |S| |Z| = |S| |Ξ| 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 a policy cover (see Appendix B, Proposition 4). Further, the proposed algorithm PPE, learns such a policy cover and requires number of samples that depends polynomially on |S| instead of |Z| or |X |.

heading: 3 FAILURES OF PRIOR APPROACHES
text: 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 Appendix A.
Limitation of Noise-Contrastive learning. Noise-contrastive learning has been used in RL to learn a state abstraction by exploiting the temporal information available to the agent. Specifically, the HOMER algorithm (Misra et al., 2020) trains a model to distinguish between real and imposter transitions. This is done by collecting a dataset of quads (x, a, x′, y) where y = 1 means the transition was (x, a, x′) was observed and y = 0 means that (x, a, x′) was not observed. HOMER then trains a model pθ(y | x, a, φθ(x′)) with parameters θ, on the dataset, by predicting whether a given pair of transition was observed or not. This provides a state abstraction φθ : 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 at the position of ducks which may have different behaviour in the two transitions. This results in the HOMER creating O(|Z|) 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, where a representative example is 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 a representation can ignore all information that is not relevant for action prediction, which includes all exogenous/uncontrollable information. However, it can also ignore some controllable information, which may result in a failure to 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 Appendix A.3 we show inverse dynamics may over-abstract even when the initial starting state is deterministic.
Limitation of Bisimulation. Zhang et al. (2020) proposed learning a bisimulation metric to learn a representation which is invariant to exogenous noise. Unfortunately, it is known that bisimulation metric cannot be learned in a sample-efficient manner (Modi et al. (2020), Proposition B.1). Intuitively, when the reward is same everywhere, then bisimulation merges all states into a single abstract state. This creates exploration issue in sparse reward settings, since the agent can merge all states into a single abstract state until it receives a non-trivial reward. Hence, the learned abstract states provide no help in exploring the environment.
Bellman rank might depend on |Ξ|. The Bellman rank was introduced in Jiang et al. (2017) 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 Appendix A that Bellman rank for EX-BMDP can scale as O(|Ξ|). This shows that EX-BMDP is a highly non-trivial setting as we don’t even have sample-efficient algorithms that can solve it without being computationally-efficient.
In Appendix A we also describe the failures of FLAMBE (Agarwal et al., 2020a)) and autoencoding based approaches (Tang et al., 2017).
Algorithm 1 PPE(δ, η): Predictive Path Elimination 1: Set Ψ1 = {⊥}, stochasticity level η ≤ 14SH //⊥ denotes an empty path 2: for h = 2, . . . ,H do 3: Set N = 16 (|Ψh−1|A)2 log ( |F||Ψh−1|AH
δ ) 4: Collect a dataset D of N i.i.d. tuples (x, υ) where υ ∼ Unf(Ψh−1 ◦ A) and x ∼ P(xh | υ). 5: Solve multi-class classification problem: f̂h = arg maxf∈F ∑ (x,υ)∈D ln f(idx(υ) | x). 6: for 1 ≤ i < j ≤ |Ψh−1 ◦ A| do 7: Calculate the path prediction gap: ∆̂(i, j) = 1N ∑ (x,υ)∈D
∣∣∣f̂h(i|x)− f̂h(j|x)∣∣∣ . 8: If ∆̂(i, j) ≤ 5/8|Υh| , then eliminate path υ with idx(υ) = j. //υi and υj visit the same state 9: Ψh is defined as the set of all paths in Ψh−1 ◦ A that have not been eliminated in line 10.

heading: 4 REINFORCEMENT LEARNING FOR EX-BMDPS
text: 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 a computationally-efficient and simpler alternative to Algorithm 4 of Du et al. (2019) who studied rich-observation setting without exogenous noise.1 Due to the apparent difference of the algorithms we keep the presentation of our algorithm fully self-contained.
PPE performs iterations over the time steps h ∈ {2, · · · , H}. In the hth iteration, it learns a policy cover Ψh for time step h containing open-loop policies. This is done by first augmenting the policy cover for previous time step by one step. Formally, we define Υh = Ψh−1 ◦ A = {π ◦ a | π ∈ Ψh−1, a ∈ A} where π ◦ a is an open-loop policy that follows π till time step h− 1 and then takes action a. Since we assume the transition dynamics to be near-deterministic, therefore, we know that there exists a policy cover for time step h that is a subset of Υh and whose size is equal to the number of reachable states at time step h. Further, as the transitions are near-deterministic, 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 Υh so that we are left with just a single path for each reachable state. This is done by collecting a dataset D of tuples (x, υ) where υ is a uniformly sampled from Υh and x ∼ Ph(x | υ) (line 3). We train a classifier f̂h using D by predicting the index idx(υ) of the path υ from the observation x (line 5). Intuitively, if f̂h(i | x) is sufficiently large, then we can hope that the path υi visits the state φ?e(x). Further, we can view this prediction problem as learning a 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 Υh, we first compute a path prediction gap ∆̂(line 7). If the gap is too small, we show it implies that these paths reach the same endogenous state, hence we can eliminate a single redundant path from this pair (line 10). Finally, Ψh is defined as the set of all paths in Υh 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 φ̂e,h for each time step h ∈ {2, 3, · · · , H} directly from f̂h as shown below:
φ̂e,h(x) = min { i | f̂h(i | x) ≥ max
j f̂h(j | x)−O(1/|Υh|), i ∈ [|Υh|]
} .
Intuitively, this assigns the observation to the path with smallest index that has the highest chance of visiting x, and therefore, φ?e(x). We are implicitly using the decoder for exploring, since we rely on using f̂h for making planning decisions. We will evaluate the accuracy of this decoder in Section 6.
1Alg. 4 has time complexity of O(S4A4H) compared to O(S3A3H) for PPE. Furthermore, Alg. 4 requires an upper bound on S, whereas PPE is adaptive to it. Lastly, Du et al. (2019) assumed deterministic setting while we provide a generalization to near-determinism.
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 φ̂e,h 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 from the path elimination data. We accomplish this by recovering a partition of paths in Ψh−1 ×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 a path υj on comparison with υi in line 10, then all paths currently merged with υj get merged with υi. We then define an abstract state space Ŝh for time step h that contains an abstract state j for each path υj ∈ Ψh. Further, we recover a latent deterministic transition dynamics for time step h− 1 as T̂h−1 : Ŝh−1 ×A → Ŝh where we set T̂h−1(i, a) = j if the path υj ∈ Ψh gets merged with path υ′i ◦ a ∈ Ψh where υ′i ∈ Ψh−1. Learning a near optimal policy given a policy cover. PPE runs in a reward-free 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 on the exogenous state then we can use the PSDP algorithm (Bagnell et al., 2004) to learn a near-optimal policy. PSDP is a model-free dynamic programming method that only requires policy cover as input (see Appendix D.1 for details). However, if the reward function only depends on the endogenous state, then we can use a computationally cheaper value-iteration algorithm VI that uses the policy cover and recovered transition dynamics. VI is a model-based 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 the PPE algorithm, scales with the size of endogenous and not the exogenous state space or the size of observation space.

heading: 5 THEORETICAL ANALYSIS AND DISCUSSION
text: We provide the main sample complexity guarantee for PPE as well as additional intuition for why it works. We analyze the algorithm in near-deterministic MDPs defined as follows: Two transition functions T1 and T2 are η-close if for all h ∈ [H], a ∈ A, s ∈ Sh it holds that ||T1(· | s, a)− T2(· | s, a)||1 ≤ η. Analogously, two starting distribution µ1 and µ2 are η-close if ||µ1(·)− µ2(·)||1 ≤ η. We emphasize that near-deterministic dynamics are common in real-world applications like robotics.
Assumption 1 (Near deterministic endogenous dynamics). We assume the endogenous dynamics is η-close to a deterministic model (µD,η, TD,η) where η ≤ 1/(4SH).
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 (Realizability). For any h ∈ [H], and any set of paths Υ ⊆ Ah with |Υ| ≤ SA and where Ah denotes the set of all paths of length h, there exists fΥ,h ∈ F such that: fΥ,h(idx(υ) | x) =
P(φ?e(x))|υ)∑ υ′∈Υ P(φ?e(x))|υ′) , for all υ ∈ Υ and x ∈ X with∑υ′∈Υ P(φ?e(x)) | υ′) > 0. In this assumption, the function fΥ,h(υ | x) denotes the Bayes optimal classifier for the regression problem in the hth iteration when Υh = Υ. Realizability assumptions are common in theoretical analysis (e.g., Misra et al. (2020), Agarwal et al. (2020a)). In practice, we use expressive neural networks to solve the regression problem, so we expect the realizability assumption to hold. Note that there are at most AS(H+1) Bayes classifiers for different prediction problems. However, this is acceptable since our guarantees will scale as ln |F| and, therefore, the function class F can be exponentially large to accommodate all of them.
We now state the formal sample complexity guarantees for PPE below.
Theorem 1 (Sample Complexity). Fix δ ∈ (0, 1). Then, with probability greater than 1 − δ, PPE returns a policy cover {Ψh}Hh=1 such that for any h ∈ [H], Ψh is a ηH-policy cover for time step h and |Ψh| ≤ S, which gives the total number of episodes used by PPE as O ( S2A2H ln |F|SAHδ ) .
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 ln |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 a deterministic setting and the hth iteration. Assume by induction that Ψh−1 is an exact policy cover and has exactly one policy for every endogenous state reachable at time step h − 1. The Bayes optimal classifier of the prediction problem can be derived as:
f?(idx(υ) | x) = P(υ | x) = P(x | υ)P(υ)∑ υ∈Υh P(x | υ′)P(υ′) = P(x | υ)∑ υ∈Υh P(x | υ′) = P(φ?e(x)) | υ)∑ υ∈Υh P(φ?e(x)) | υ′) ,
where the third equality uses the fact that all paths are chosen uniformly, and the last equality critically uses that for any open-loop policy υ we have: P(x | υ) = q(x | φ?e(x), φ?g(x))P(φ?e(x) | υ)P(φ?g(x)). Thus, the Bayes optimal classifier only depends on the endogenous state φ?e(x) of the observation, and there is no signal available to separate observations from the same endogenous state. Therefore, there is no over-abstraction issue. In addition, we can show that there is signal available to separate any two endogenous states. Intuitively, no path can visit two different endogenous states. Hence, for two observations x1 and x2 coming from different endogenous states, if υ1 visits φ?e(x1) then f?(idx(υ1) | x1) would be non-zero, in fact we can show it to be at least 1/|Υh| and f?(idx(υ1) | x2) would 0. This gap provides a signal to separate observations from different endogenous states. Hence, there is no under-abstraction issue like in inverse dynamics approaches.
The above factorization relies heavily on the use of open-loop policies and does not hold for an arbitrary policy class. This is the main reason why we use a policy cover with open-loop policies.

heading: 6 EXPERIMENTS
text: We evaluate PPE on two domains: a challenging exploration problem called combination lock to test whether PPE can learn an optimal policy and an accurate state decoder, and a 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 = {s1,a} ∪ {sh,a, sh,b, sh,c}Hh=2, an exogenous state space Ξ = {0, 1}H , an action space A with 10 actions, and a deterministic endogenous start state of s1,a. For any state sh,g we call g as its type which can be a, b or c. States with type a and b are considered good states and those with type c are considered bad states. Each instance of this problem is defined by two good action sequences (ah)Hh=2, (a ′ h) H h=2 with ah 6= a′h, which are chosen uniformly randomly and kept fixed throughout training. At h = 1, the agent is in s1,a and action a1 leads to s2,a, a′h leads to s2,b, and all other actions lead to s2,c. For h > 2, taking action ah in sh,a leads to sh+1,a and taking action a′h in sh,b leads to sh+1,b. In all other cases involving taking an action in a state sh,g, we transition to the next bad state sh+1,c. We visualize the latent endogenous dynamics in Figure 2a. The exogenous state evolves as follows: we sample ξ1 as a vector in {0, 1}H by selecting the value of each dimension independently uniformly in {0, 1}. At time step h, ξh is generated from ξh−1 by uniformly flipping each bit in ξh−1 independently with probability 0.1. There is a reward of 1.0 on taking the good action aH,a in sH,a and a reward of 0.1 on taking action aH,b in sH,b, and in all other
cases the agent gets a reward of 0. This gives a V (π?) = 1, and the probability that a random open loop policy gets this optimal return is 10−H .
An observation x is generated stochastically from a latent state z = (s, ξ). We map s to a vector w encoding the identity of the state. We concatenate (w, ξ), add Gaussian noise to each dimension, and multiply the result with a Hadamard matrix to generate x. See Appendix F for full details. Our construction is inspired by similar combination lock problems in prior work (Du et al., 2019; Misra et al., 2020) (which did not consider exogenous distractors).
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 a 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 1. We model F using a two-layer feed-forward network with ReLU non-linearity. We train F with Adam optimization and use a validation set to do model selection. We refer readers to Appendix F for additional experimental details.
Results. Figure 2b 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 V (π?)/2 = 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 × 105 episodes then we set n = ∞. We observe that PPO is unable to solve the problem at H = 5. PPO + RND is able to solve the problem at H = 5 and 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 ≥ 5. This agrees with the theoretical prediction that Bisim provides no learning signal when running in sparse-reward settings. In such settings, there can be many episodes before any reward is received. 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 a value-iteration like algorithm (see Appendix D.2) to learn a 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 on 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 state abstraction φ̂ : X → [N ] we compute 1/m∑mi=1 1{φ̂(xi,1) = φ̂(xi,2) ⇔ φ?e(xi,1) = φ?e(xi,2)}, where {xi,1, xi,2}mi=1 are drawn independently from a fixed distribution D with good support over all states. We report the percentage accuracy in Figure 2c. When there is no exogenous noise, Homer is able to learn a 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 as it has difficulty separating observations from s3a and s3b. 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 is 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.
Visual Grid World Experiments. We test the ability of PPE to recover the latent endogenous transition dynamics in visual grid-world problem.2 The agent navigates in a N ×N grid world where each grid can contain a stationary object, the goal, or the agent. The agent’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 × 8N sized RGB image. We add exogenous noise as 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× 7 gridworld that we experiment on. The
2We use the following popular gridworld codebase: https://github.com/maximecb/gym-minigrid
exogenous state is given by the position, size and color of ellipses and is much larger than |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 can evaluate the accuracy of the learned transition model by measuring it in terms of accuracy of the elimination step (Algorithm 1, line 10), since this step induces our algorithm’s mapping from observations to endogenous latent states. For a fixed h ∈ {2, · · · , H}, let νi and νj be two paths in Ψh−1 ◦ A. We compute two type of errors. Type 1 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 Ψh−1 ◦ A. Type 1 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 2 errors are less serious but lead to inefficiency due to using redundant paths for exploration. When both errors are 0, then the model recovers the exact latent model up to relabeling.
Results. We report results on learning the model in in Figure 3c. We see that PPE is able to reduce the number of type 1 errors down to 0 using 2× 105 episodes per time step. This is important since even a single type 1 error can cause exploration failures. Similarly, PPE is able to reduce type 2 errors and is able to get them down to 56 with 5 × 105 episodes. This is acceptable since type 2 errors do not cause exploration failures but only cause redundancy. Therefore, at 2× 105 samples, the algorithm makes 0 type 1 errors and just a handful type 2 errors. This is remarkable considering that PPE compares roughly 2× 105 pairs of paths in the entire run. Hence, it makes only ≤ 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 3d shows the results. As expected, PPE rapidly learns a highly accurate decoder while Homer performs only as well as a random uniform decoder.

heading: 7 CONCLUSION
text: In this work, we introduce the EX-BMDP setting, an RL setting, that models exogenous noise which is ubiquitous in many real-world systems. We show that many existing RL algorithms fail in the presence of exogenous noise. We present PPE that learns a multi-step inverse dynamics to filter exogenous noise and successfully explores. We derive theoretical guarantees for PPE in neardeterministic 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 as 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-BMDPs.

Review summaries:
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.

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.

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.

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.