Reinforcement Learning Under Latent Dynamics: Toward Statistical and Algorithmic Modularity
Authors: Philip Amortila
Dylan J Foster
Nan Jiang
Akshay Krishnamurthy
Zakaria Mhammedi
Venue: NeurIPS 2024 oral (2024)
Keywords: Reinforcement Learning
Representation Learning
Latent Dynamics
Function Approximation
Primary area: reinforcement_learning
TL;DR: We study the statistical requirements and algorithmic principles for reinforcement learning under general latent dynamics

Abstract: Real-world applications of reinforcement learning often involve  environments where agents operate on complex, high-dimensional observations, but the underlying (``latent'')  dynamics are comparatively simple. However, beyond restrictive settings
  such as tabular latent dynamics,  the fundamental statistical requirements and algorithmic principles for *reinforcement learning under latent dynamics* are poorly
  understood.

  This paper addresses the question of reinforcement learning under *general latent dynamics* from a
  statistical and algorithmic perspective.  On the statistical side, our main negative
result shows that *most* well-studied settings for reinforcement learning with function approximation become intractable when composed with rich observations; we complement this with a positive result, identifying *latent pushforward coverability* as a
general condition that enables statistical tractability. Algorithmically, we develop provably efficient *observable-to-latent* reductions ---that is, reductions that transform an arbitrary algorithm for the
  latent MDP into an algorithm that can operate on rich observations--- in two settings: one where the agent has access to hindsight
observations of the latent dynamics (Lee et al., 2023) and one
where the agent can estimate *self-predictive* latent models (Schwarzer et al., 2020). Together, our results serve as a
  first step toward a unified statistical and algorithmic theory for
reinforcement learning under latent dynamics.

Reinforcement Learning under Latent Dynamics: Toward Statistical and Algorithmic Modularity
Philip Amortila" philipa4eilliois..coo edu
Dylan J. Foster
Nan Jiang
dyl.nnfosteremiccroofft.ccm com
nanjiang@illine wwwiilliiiiiiiiiiii edu
Akshay Krishnamurthy
Zakaria Mhammedi
akshayykremicrosoft.ccm
mhammedi@google.. com
Abstract
Real-world applications of reinforcement learning often involve environments where agents operate on complex, high-dimensional observations. but the underlying ("latent") dynamics comparatively simple. However, outside restrictive settings such as small latent spaces, the fundamental statistical requirements and algorithmic principles for reinforcement learning under latent dynamics are poorly understood.
This paper addresses the question of reinforcement learning under general latent dynamics from a statistical and algorithmic perspective. On the statistical side, main negative result shows that most well-studied settings for reinforcement learning with function approximation become intractable when composed with rich observations; complement this with positive result, identifying latent pushforward coverability as general condition that enables statistical tractability. Algorithmically, develop provably efficient observable-to-lut latent reductions-that is, reductions that transform an arbitrary algorithm for the latent MDP into an algorithm that can operate on rich observations-in two settings: one where the agent has access to hindsight observations of the latent dynamics [LADZ23], and one where the agent can estimate eeff-predcctive latent models [SAGHCB20]. Together, our results serve as first step toward unified statistical and algorithmic theory for reinforcement learning under latent dynamics.
Introduction
Many application domains for reinforcement learning (RL) require the agent operate rich, high-dimensional observations of the environment, such as images or text [WSD15; LFDA 16; KFPM21; NRKFG22; Bak+22; Bro+22]. However, the environment itself can often be summarized by latent dynamics for a low-dimensional or otherwise simple latent state space. The decoupling of latent dynamics from the complex observation process naturally suggests modular framework for algorithm design: first learn a representation that decodes the latent state from observations, then apply a reinforcement learning algorithm for the latent dynamics on top the learned representation. This paper investigates the algorithmic and statistical foundations of this framework. We ask: Can we take existing algorithms and sample complexity guarantees for reinforcement learning in the latent state space and lift them to the observation space in a modular fashion?
There is a growing body of theoretical and empirical work developing algorithms that combine representation learning and reinforcement learning to develop scalable algorithms. On the empirical side, plethora of representation learning objectives have been deployed to varying degrees of success [PAED17; Tan+ 17; ZMCGL21; LSA20; YFK21; Lam+24; Guo+22; HPBL233, but we lack
"The full (author-recommedded) version of this paper can be found at: http://arki.ooghhl//44400..0
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

mathematical framework to systematically compare these objectives and understand when one might be preferred another. On the theoretical side, all existing approaches suffer from three primary drawbacks: (a) they are tailored to restricted classes of latent dynamics models (tabular MDPs [KAL16; DKJADL,19; MHKI.20; 7SUWAS22; MFR23], LQQR [DR21; Mha+20), or factored MDPs [ML]L) limiting generality; (b) the analyses, despite focusing on restrictive settings, are unwieldy, limiting progress in algorithm development; and (c) they are not modular, in the sense that the representation learning procedures are specialized to specific choices of latent reinforcement learning algorithm, limiting ease of use.
1.1 Contributions
We address the aforementioned limitations by introducing a new framework, reinforcement learning under general latent dynamics.
Reinforcement learning under general latent dynamics (Section 2). In our framework, the agent performs control based on high-dimensional observations, but the dynamics of the environment are governed by unobserved latent state space. Following prior work (particularly the so-called Block MDP formulation [DKJADL 19]), we assume that the latent states can be uniquely decoded from observations, but that the true decoder is unknown and must be Icarned. To aid in the decoding process, we supply the learner with a class of representations that is realizable in the sense that is powerful enough to represent the true decoder. Our point of departure from prior theoretical works is that we do not assume specific structure (e.g., tabular or linear dynamics) on the Markov decision process (MDP) that governs the latent dynamics. Instead, we make the minimal assumption that the latent dynamics belong to base MDP class which is statistically tractable, in the sense that when the latent states directly observed there exists some reinforcement learning algorithm with low sample complexity that is capable of learning a near-optimal policy for every MDP in the class. We take the first steps toward building a unified and modular theory for reinforcement learning in this setting.
Contributions: Statistical modularity (Section 3). A central consideration for reinforcement learning under latent dynamics is that representation learning and exploration must be intertwined: an accurate decoder is required to explore the latent state space, but exploration is required to learn an accurate decoder. To develop provable sample complexity guarantees, one must prevent errors from compounding during this interleaving process, a challenging statistical problem which prior work addresses through strong structural assumptions MHKL200 ZSUWAS22; MFR23; DR21; Mha+20; MIJL211]. For the general latent-dynamies setting we consider, is unclear whether similar techniques can be applied, or whether the setting even statistically tractable, ignoring computational considerations. Thus, our first contribution considers the question of statistical modularity.?
the base MDP [KAL16; DKJADL119;
If base MDP class is tractable when observed directly, is the corresponding latent-dynamies problem tractable?
Statistical modularity adopts a minimax perspective by assuming that the base MDP lies in a given class, and demands that the sample complexity of the latent-dynamics setting is controlled by natural bound on the sample complexity of the base MDP class. We show, perhaps surprisingly, that most well-studied reinforcement learning settings involving function approximation [RVR13; JKALS17; SJKAL19; MJTS20; AJSWY20; Li09; DVRZ19; WSY20; ZGS21; Du+21; JLM21; FKQR21] do not admit statistical modularity (Theorem 3.1). In other words, statistical tractability of an MDP class does not extend to the latent-dynamics setting. We complement these negative findings with a positive result, identifying pushforward coverability as a general structural condition on the latent dynamics that enables sample efficiency (Theorem 3.2).
Beyond developing a modular understanding of the statistical landscape, we investigate modular algorithu design principles for RL under general latent dynamics. Specifically, we consider the question of observable-to-lan RL under latent dynamics can be reduced to the simpler problem of RL. with latent states directly observed:
Contributions:
Algorithmic modularity (Section 4).
reductions, whereby
Can we generically lift algorithms for base MDP class solve the corresponding latent-dynamics problem?
"This question and associated definitions restated formally in Section 3.1.

---

This property, which we refer to as algorituuic modularity, enables modular, greatly simplified algorithm design, allowing one to use an arbitrary base algorithm for the base MDP class to solve the corresponding latent-dynamies problem. Algorithmic modularity is stronger property than mere statistical modularity, and thus is subject to our statistical lower bound. Accordingly, we consider two settings that sidestep the lower bound through additional feedback and modeling assumptions. Our first algorithmic result considers hindsight observability [LADZ23], where latent states are revealed during training, but not at deployment (Theorem 4.1). Our second considers stronger function approximation conditions that enable the estimation of self-predictive latent models [SAGHCB20] through representation learning (Theorem A. Both results are fully modular: they transform any cumple-efficiee algorithm for the base MDP class into a sample-efficiee algorithm for the latent-dy diient-dyaamies setting. Thus, they constitute the first general purpose algorithms for RL under latent dynamics.
Together, we believe our results can serve foundation for further development of practical, general-purpon algorithms for RL under latent dynamics. To this end, we highlight a number of fascinating and challenging open problems for future research (Section 5).
2 Reinforcement Learning under General Latent Dynamies
In this section we formally introduce our framework, reinforcement learning under general latent dynamics.
MDP preliminaries. We consider an episodic finite-horizon online reinforcement learn- ing setting. With H denoting the horizon, a Markov decision process (MDP) M (PP), {12 ) |h! consists of state space X' an action space A, a reward distribution Rí
A[0,, 1I) (with expectation (1r, a)), and transition kernel P X A ( (with the convention that (- 0) is the initial state distribution)."
At the beginning of the episode, the learner selects a randomized, non-stationary policy π ( ,.). where Ta X + A(A); we let Mr denote the set of all such policies. The episode evolves through the following process; beginning from 31 ~ (- (),, the MDP generates a trajec- tory (I1, (1,r))..... (IH, as,, via a₁ Th (3t)), Th ~ (17,, aa). and Fh+1 ( Tn. an). We let par'. - denote the law under this process, and let E denote the corresponding expectation, and likewise let [pa,* and EM denote the analogous laws and expectations in another MDP M. We
assume that Σ/ E [0, 1] almost surely for any trajectory in M
For a policy and MDP M, the expected reward for ı is given by (T((T) = EM [_A and the value functions are given by 2% (x,aa optimal deterministic policy of M, which maximizes VMr. (over T) at all states (and in particular, satisfies TM E arg max JM (T)), and write QM = QMaaa For I X' x A R, write r((x) == mag, f(a, a) as well as Vy(x) = max, f(),a). For MDP M. horizon E [H]. and g X + R. we let Th"" denote the Bellman (optimality) operator defined via (x,, a) E"Irn + g(zn+1) Th z. On = a). and we overload notation by letting We also let Th denote the Bellman evaluation operator defined via [T,M. f](z, a) = EM ['' ( + (5 d')] In x, as a), for any E Tras- We define the occupancy measures for layer h via de.. (x) par.p [3r x]] and dh d (z, a) PM.) [IA x, On a).
kh rn]. V (x) = EM, EE TW Th = x] and al We let TM = (T } denote an
RM, [Ei==h T'e Th x, on a.
(TR. (((,,a)
(*,)
Online reinforcement learning. In online reinforcement learning, the learning algorithm ALG repeatedly interacts with an unknown MDP A/* by executing a policy and observing the resulting trajectory. After 7 rounds of interaction, the algorithm outputs a final policy म. with the goal of minimizing their risk, defined via
Risk ALG, JM (TTr)) JM (T)).
"To simplify presentation, we assume that X' and A are countable; our results extend to handle continuous variables with appropriate measure- theereeet treatment.
3

---

Reinforcement learning under general latent dynamics. In reinforcement learning under general latent dynamics, we consider MDPs M where the dynamics are governed by the evolu- tion of an unobserved latent state 8h, while the agent observes and acts on observations 2hh generated from these latent states. Formally, a latent-dynamice MDP consists of two ingredients: a base MDP Maa {S, A, (aat 1 h= { [Raat,h ) h=1: H) defined over a latent state space S, and decodable emission process 3/ := {ih, S - ((X)) ) h=1- which maps each latent state to distribution over observations. The former is an arbitrary MDP defined over S, while the latter is defined as follows.
Framework:
Definition 2.1 (Emission process). An emission process is any function ub = {vh : S - {(X)] and is said be decodable if
wh, Vs' # supp // (8) 0 supp (n((') = V.
(2)
When & = { Jo is decodable, we let xh :- (1 X + S denote the associated decoder.
With this, we can formally introduce the notion of a latent-dynamics MDP.
Definition 2.2 (Latent-dynamics MDP). For a base MDP Mist
A H} and a decodable emission process v the latent-dynamies MDP (Mast. b6) == A, I h- RRoss, I hm-1, H. is defined as the MDP where the latent dynamics evolve based on the agent's 's action On E A via the process 81+1 ~ Pist, an) and rh Paat, an). The latent state is not observed directly, and instead the agent observes Jh E X generated by the emission process Th ~ 1//+11
{S, A. ( { (Rist,
1/
Note that under these dynamics, the decoder أا² associated with 3b ensures that 1% (xx) sn almost surely for all h E [H] That is, the latent states can be uniquely decoded from the observations. To emphasize the distinction between the latent-dynamics MDP ( (.Mat. 16)) (which operates on the observable state space X) and the MDP Mint (which operates on the latent state space S), we refer to the latter as a base MDP rather than, for example, "latent MDP", and apply similar convention to other latent objects whenever possible.'
Departing from prior work, we do not place any inherent restrictions on the base MDP, and in particular do not assume that the latent space small (i.e., tabular). Rather, we aim to understand- in a unified fashion-what structural assumptions on the base MDP Mist are required to enable learnability under latent dynamics. To this end, will be useful to considers specific classes (i.e.. subsets) of base MDPs Mist and the classes of latent-dynamic MDPs they induce.
Definition 2.3 (Latent-dynamicn MDP class). Given set of base MDPs Miat and a set of decoders $ c (X' + SS, we les
(,Miat, +) = (KMaa, 4/ : Mist E MMat, 1b is decodable, w- E EΦ}
denote the class of induced latent-dynamin MDPs.
Stated another way, (.Miet. b) is the set of all latent-dynamies MDPs (Maat v. where (i) the base MDP Miat lies in MMat. and (ii). the emission process e is decodable, with the corresponding decoder belonging Φ. The class Miat represents our prior knowledge about the underlying MDP Mat: concrete classes considered in prior work include tabular MDPs [KAL16; DKJADL19; MHKI.20; ZSUWAS22; MFR23). linear dynamical systems (DMRY20; DR21; Mha+20], and factored MDPs [MLJL21]. In particular, the class Miat may itself warrant using function approximation. At the same time, the class & represents our prior knowledge inductive bias about the emission process, enabling representation learning. In what follows, we investigate what conditions on Mist make the induced class (.Mist: +) tractable, both statistically (statistical modularity; Section 3) and via reduction (algorithmic modularity; Section 4).
3 Statistical Modularity: Positive and Negative Results
This section presents our main statistical results. We begin by formally defining the notion of statistical modularity introduced in Section 1, present our main impossibility result (lower bound) and its implications (Section 3.2), then give positive results for the general class of pushforwaadd-covraalee MDPs (Section 3.3).
'Equivalently the dynamics can be described via Res., an) = R1 5 (ax)), on) and Poss, (2rx41
3%, aa.) Piat, (V/ (2x44) ) | vir" (mx)), an) +1 (IT641 (+44((0++1) For example, in Section 4 we will be concerned with reductions from observation space algorithms to "base algorithms" that operate the latent state space.

---

3.1 Statistical modularity: A formal definition
We first define the statistical complexity for a MDP class (or, model class) M.
Definition 3.1 (Statistical complexity). We say that an MDP class M can be learned up to optimality using comp(M,,,b) E,6) samples if there exists an algorithm ALG which, for every M M. atlains
Risk(T, ALG, S
with probability at least 5, after = comp(M, e, rounds of online interaction M.
We say that a base MDP class Miat admits statistically modularity if, for any decoder class o. the induced latent-dynamics MDP class (Miat, 4) can be learned with statistical complexity that is polynomial in: (i) the statistical complexity for the base class, and (ii) the capacity of the decoder class.
Definition 3.2 (Statistical modularity). We say the MDP class Miat is statistically modular under complexity comp(Maat. E, 6) if. for every decoder class L, we have
comp(( (I.Maat $)) e, 8) (oly(comp(MMase e, 1og F1).
(4)
We say that Miat admits strong statistical modularity if Eq. (4) holds when comp(Maat e, 0) is the minimax sample complexity for Miat.
In the sequel, we examine well-studied MDP classes Miat (e.g., those which admit low Bellman rank (KALS17J) and choose comp(Miat, 6, based on natural upper bounds on their optimal sample complexity; in this case we will simply say they (or are not) statistical modular, leaving the complexity upper bound comp implicit. Following prior work [KAL16; DKIADL19; MHKL20; ZSUWAS22; MFR23; DR21; Mha+20; MLJL21J, we use log Φ a proxy for the statistical complexity of supervised learning with the decoder class 4.5
The two most notable examples of statistical modularity covered by prior work are: (i) taking Miat as the set of tabular MDPs admits strong statistical modularity [DKJADLI9; MHKL20; MFR23J, and (ii) taking Miat as the set of linear MDPs admits statistical modularity with complexity poly(d, H, |Al, logg ())) [AKKS20; U7S22; MCKJA24; MBFR23). Interestingly, the latter does not admit strong statistical modularity, because the optimal rate for Miat does not scale with [A], but the rate for (Miat. b) necessarily does [LS20;; HLSW21J. The results of Mhammedi et al.; Misra et al.; Song et al. [Mha+20; MIJL21; SWFK24] can also be viewed as instances of statistical modularity for other base MDP classes.
3.2 Lower bounds: Impossibility of statistical modularity
Our main result in this section is to show that for most MDP classes Miat considered in the literature on sample-efficient reinforcement learning with function approximation [RVR13; JKALS17; SJKAL19; MJTS20; AJSWY20, Li09; DVRZ19; WSY20; ZGS21; Du+21; JLM21; FKQR21), statistical modularity (under the natural complexity upper bound for the class of interest) is impossible. Our central technical result is the following lower bound, which shows that statistical modularity can be impossible even when the base MDP known to the learner a-priori. The lower bound is significant generalization of the result from Song et al. [SWFK24];; we first state the lower bound, then discuss implications.
Theorem 3.1 (Impossibility of statistical modularity). For every N 2 4, there exists a decoder class & with [ = N and a family of base MDPs Mist satisfying (i) |Matt 1, (i) H < (log(N)) (iii) SS] = | < N2, (iv) |A| = 2, and such that
1. For all , O, we have comp( 5, 0.
For an absolute constant e O, comp comp(K.Mact 13,c,c) 2 ((N/lo((N)).
In other words, even when the base dynamics are fully known, strong statistical modularity (in this case, poly(log((1) complexity) is impossible; any algorithm will require at least min{ VS, (5,2000/1)) /H, (1/log//1) episodes learn a near-optimal policy for latent-dynamics MDP (Mat, vb) E ([Miatt 2).
"Our main results easily extend infinite classes through standard arguments. "n the latter case, the latent-de dyntmicsssics class (.Miae, ?) may be seen to be set of low-rank MDPs (that is. linear MDPs with unknown features), so that low-rank MDP algorithms may be applied directly on the observations (Appendix E.2).
5

---

Statistical Modularity?
Base MDP class Mist
Tabular Contextual Bandits
Low-Rank MDP
Figure Summary of statistical modularity (SM) results.
Known Deterministic MDP (M =I)
Low State Occupancy (V и S ((A))
/: SM is possible for nat-
Model Class Pushforward Coverability
ural choice of comp(.) (e.g..
Linear CB/MDP
x
poly([S), [A], H, - log (
Model Class + Coverability (V TM M E M)
tabular MDPs).
Known Stochastic MDP (_Maael 1)
X: SM is not possible with natural choices of comp(-).
Bellman Rank (Q-type or V-type)
Eluder Dimension + Bellman Completeness
?: open.
Q" Irreleaattt State Abstraction
SM possible if willing pay for (suboptimal) |.A| complexity. See Appendix E.2 for precise descriptions of each setting and choices for their complexities.
Linear Mixture MDP
Linear /
Low State/State-AAtioon Occupancy mar M M)
Bisimulation
Low State-Action Occupancy (V S A(AA)
Model Class Coverability क A(A))
Intuition for lower bound. The intuition behind the lower bound in Theorem 3.1 is as follows: the unobserved latent state space consists of N |+b binary trees (indexed from to N), each with N the roots of the N trees, and the agent receives leaf nodes. The starting distribution is uniform reward of if and only they navigate to the leaf node that corresponds to the index of their current tree. The observed state space identical the latent state space, but the emission process shifts the index of the tree by an amount which is unknown to the agent. Despite the base MDP being known and the decoder class satisfying realizability,, the agent requires near-exhaustive search identify the value of the shift and recover opar-optimal policy.
taxonomy of statistical modularity. As a corollary, we prove that many (but not all) well-studied function approximation settings do not admit statistical modularity by embedding them into the lower bound construction of Theorem 3.1 (as well as a variant of the result, Theorem E. Our results are summarized in Figure 1. Our impossibility results highlight the following phenomenon: many MDP classes M1at that place structural assumptions via the value functions (e.g.. MDPs with finear-"//Ve [Du+21] or MDPs with Bellman complete value function class of bounded eluder dimension [JLM21; WSY20) become intractable under latent dynamics. Intuitively, this is because it is not possible take advantage of structure in value functions without learning good representation, and, simultaneously. these assumptions are too weak by themselves to enable learning such representation. Meanwhile, MDP classes Mist that place structural assumptions the transition distribution (e.g., MDPs with low state occupancy complexity [Du+21] or low-rank MDPs [AKE] (KKS220) sometimes (but not always) tractable under latent dynamies."
We point to Appendix E.2 for background on all the settings in Figure I and proofs that they are (or are not) statistically modular. We remark that it is fairly straightforward to embed most of the MDP classes of Figure I into the construction of Theorem 3.1 since only uses only single base MDP Maat and we expect that many other base MDP classes can similarly be shown to be intractable. However, proving the positive results in Figure 1 requires establishing several new results showing that certain base classes are tractable under latent dynamics; most notably, we next discuss the case of pushforward coverability.
3.3 Upper bounds: Pushforward-coverable MDPs are statistically modular
Our main postive result concerning statistical modularity is highlight pushforward coverability [XJ21; AFK24; MFR24]- strengthened version of the coverability parameter introduced in Xie et al. [XFBJK23] as a general structural parameter that enables sample-efficient reinforcement learning under latent dynamics.
'If one is willing to pay for suboptimal |A| factors, then more (but not all) classes become statistically tractable (e.g., linear MDPs [JYWJ20] and MDPs with low sate-action occupancy [Du+21]).

---

Definition 3.3 (Pushforward coverability), The pushforward coverability coefficient Cuush for an MDP Mist with transition kernel Piat defined by
Pist.h-1(88 (8,0) pa(5))
(push(Mail = max inf hE|H] RE(H) (ExxxX)
sup
(5)
Concrete examples [AFK24; MFR24] include: (i) tabular MDPs Mist admit (Maat) I [S]: and (ii) Low-Rank MDPs Miat (with or without known features) in dimension admit Cpush(Maat I d. Further examples include analytically sparse Low-Rank MDPs [GMR24] and Exogenous Block MDPs with weakly correlated noise [MFR24]. Our main result is as follows.
Theorem 3.2 (Pushforward-coverale
MDPs are statistically modular). Let Miat be a base MDP class such that each Mat E Miat has pushforward coverability bounded by Cpush (Mat) S Cpush- Then, for any decoder class 4 we have:
1. comp(Maat, 6) - poss(C |A H, Mirl log. (9((8-1)) 1)), and
2. comp((.Man 6) S poly(Cpushh |A,, H, log) M1ael, log/ (b e 1og(6-1), log|s))
Theorem 3.2 shows that, modulo a term that is doubly-logariiee
in |S], latent pushforward cover- ability enables statistical modularity. That is, when the base (latent) dynamics satisfy pushforward coverability, there exists an algorithm for the latent-dynamics setting which scales with the statistical complexity of the base MDP class and logi We suspect that the additional log logiS| factor not essential and can be removed with more sophisticated analysis. We note that the complexity comp chosen above is not the minimax complexity for Miat, since every set of pushforward coverable MDPs is also a set of coverable MDPs with potentially smaller coverability parameter [AFK24].
Let us provide some intuition for this result. We firstly note that when Mi.: has pushforward cover- ability parameter Cussh. it holds that for any emission process v*, the observation-level MDP M == (Mi " also satisfies pushforward coverability with the same parameter Cpush (Lemma D.5). Yet, despite access to realizable base MDP class Mist and decoder class o. it is unclear whether the latent- dynamics MDP Mabs satisfies any of the observation- level function approximation conditions required by existing approaches that provide sample complexity guarantees under pushforward coverability. In particular, known algorithms for this setting either require a Bellman-complete value function class [XFBJK23], a class realizing certain density ratios [AFISX24; AFK24), or realizable model class [AFK24], and it highly nontrivial to construct these for the latent-dynamics MDP Moss = (Mi 1/") () given only the base MDP class Maat and the decoder class t. Intuitively, this is because the former observation-leve function approximation classes capture properties of the observation- level dynamics which cannot be obtained without some knowledge of the emission process.
Our main technical contribution to establish a new structural property for pushforward coverabbee MDPs (Lemma F. F.I): low-dimensional linear embeddings of their latent models can approximate the Bellman updates for an arbitrary set of test functions (as long as the set is not too large). We use this property to construct low- diwdimmnsional linear features that can approximate Bellman backups in observation-ssacee allowing us to (approximately) satisfy the Bellman completeness assumption required to apply GOLF [JLM21] to the latent-dynamics MDP. A fascinating open question is whether a similar approach can be used to establish that standard (as opposed to pushforward) coverable MDPs statistically modular, which would encompass all other known positive cases of statistical modularity (cf. Figure 1). We refer interested readers to a more detailed technical overview in Appendix F.1, as well as the full proof in Appendix F.2.
4
Algorithmic Modularity
We now turn our attention to algorithmic modularity. Specifically, we aim for observable-to-laten reductions, whereby-via representation learning-RL under latent dynamics can be efficiently reduced to the simpler problem of RL with latent states directly observed. Since algorithmic modularity is a stronger property than statistical modularity, we sidestep the previous lower bounds in Section 3 through additional feedback and modeling assumptions. Our main result for this section is a new meta-algorithm, O2L, which, under these assumptions (and when equipped with an appropriately designed representation learning oracle), acts as a universal reduction in the sense that, whenever the representation learning oracle has low risk, the reduction transforms any sample-efficient algorithm for any base MDP class into sample-efficient algorithm for the induced latent-dynamics MDP class.
7

---

Algorithm O2L: Observable-oo-Laten Reduction
1: input: Epochs T. episodes K, decoder set 2, rep. learning oracle REPLEARN, base alg. ALG1at
2: for t-= = 1,2, ... ,T' do
3: REPLEARN chooses a representation 3 X + S E & based on data collected so far.
4: Initialize new instance of AL.Giat.
5: for k = 1,2, K do
11 ALGiac plays K rounds in the "
compressed dynanics."
6: ALG1at chooses policy m S [H] + A(A).
7:
Deploy Taat o 37 to collect trajectory {a/ (t) (6.4) (
-hh ,thh 1h=1-
(6.5) ( 8: Update ALGrat with compressed trajectory (0) (1t
" ah 5
1==1-
9: end for
10: ALGIat returns final policy 70) :Sx [H] A(A), deploy o0 to collect one trajectory.
11:
end for
12: return मे = Unif(7 o T00 ...., 7 B.)).
Setup and 02L meta-algorithm. For the results in this section, we denote the (unknown) latent- dynamics MDP of interest by M == (.Maser ", and use Ø- := (1b*) to denote the true decoder. The O2L meta-algorithm (Algorithm 1) learns near-optimal policy for M by alternating between performing representation learning and executing a black-box "base" RL. algorithm (designed for the base MDP) the learned representation; this approach is inspired by empirical methods that blend representation learning and RL in the latent space (e.g.. [GKBNB19 19; SAGHCB20; Ni+24)).
Concretely, the algorithm takes as input a representation learning oracle REPLEARN and base RL algorithm At that operates in the latent space. In each epoch E [T]. REPLEARN produces a new representation ((t) X + S based on data observed so far (potentially using additional side informa- tion, which we will elaborate on in the sequel). Then, the reduction invokes ALGiat, using T(t) to sim- ulate access to the true latent states. In particular, AI. runs for K episodes, where at each episode k: (i) ALG produces a latent policy Tlat" (t.A) SSx
[H] ((A)., (ii) the latent policy is transformed into an observation level policy via composition with 6 i.e. TTit (t.k) " which is then deployed to produce a trajectory {a/, (1.0) (1.0) (H
a TTh 1k=1, and (iii) the trajectory is compressed through @it))
(t.a) " Jh=1 (ef. Line 8 of Algorithm 1)." After the and used to update ALG via {oh (19) (x)f ah :hh
H
K rounds conclude, ALG produces final latent policy Tiet : :S x [H] - A(A). The final policy ã chosen by the O2L algorithm is a uniform mixture of T o 300 over all the epochs.
The central assumption behind O2I is that the base algorithm ALGlat can achieve low-risk in the underlying base MDP Miat if given access to the true latent states 8h = oi (x%)- Beyond this assumption, we require that the representation learning oracle REPLEARN can learn a sufficiently high-quality representation. In our applications, this will be made possible by assuming access to realizable decoder class & and two distinct assumptions: hindsight observability (Section 4.1) and conditions enabling self-predictive representation learning (Section 4.2). We will show that under these conditions, we can instantiate a representation learning oracle such that O2L inherits the sample complexity guarantee for ALGjst thereby achieving algorithmic modularity.
4.1 Algorithmic modularity via hindsight observability
Our first algorithmic result bypasses the hardness in Section 3 by considering the setting of hindsight observability, which has garnered recent interest in the context of POMDPs [LADZ23; GCWXWB24; SLS23; LXIZV24]. Here, we assume that training time (but not during deployment), the algorithm has access to additional feedback in the form of the true latent states, which are revealed at the end of each episode.
Assumption 4.1 (Hindsight Observability [LADZ23]). The latent states (#1( dh (HH)) are revealed to the learner after each episode (z1, 01, .i,..., оH,TH) concludes.
We emphasize that in the hindsight observability framework, the learner must still exccute observation- space policies Tabs X' x [H] + ((A), as the latent states are only revealed at the end of each episode. Under hindsight observability, we can instantiate the representation learning oracle O2L so that the
Note that, if Φ is inaccurate, the compressed trajectory cannot necessarily be viewed as being generated by a latent MDP, and must instead be viewed as coming from Partially Observed MDP (Appendix I.I.
8

---

reduction achieves low risk for any choice of black-box base algorithm ALGiat. In particular, we make use of online classification oracles, which use the revealed latent states achieve low classification loss with respect to 6' under adaptively generated data. We first state guarantee based on generic classification oracles, then instantiate it to give a concrete end-to-end sample complexity bound.
Formally, at each step 6, the online classification oracle, denoted via REPclass is given the states and hindsight observations collected so far and produces deterministic estimate 2(t) REPelsss ( (=/² of ) (ist,ns))) for the true decoder Φ" We measure the regret of the oracle via the 0/1 loss for classification:
T
H
ET
[10% (xx) + of (#n)
Regclass
h=
where pdd) represents randomization distribution over the policy (()) Our reduction succeeds under the assumption that the oracle has low expected regret.
Assumption 4.2. For any (possibly adaptive) sequence T'0, with ah ~ p the online classification oracle REPelass has expected regret bounded by
EiRegciass (T) S Estcless(T).
where Estalass (T)) is a known upper bound.
We apply such an oracle within O2L as follows: at the end of each iteration / E [7] in O2I, we sample h [K] uniformly, and update the classification oracle with the trajectory (af a rf(.*)), ..... ( (Ck) dg ,T r(
the proof of Theorem 4.1 for details. We let Riskobs (TK) denote the risk of the O2L reduction when run for T epochs of K episodes, and
we let Risk, (K) = [i[isk( K, ALG1at M )] denote the expected risk of ALG1at when executed on Mi. with access to the true latent states 8/2 = o" (Ix) for K episodes.
Theorem 4.1 (Risk bound for O2L under hindsight observability). Let ALG1st be base algorithm with base risk Risk, and REPeLasS a representation learning oracle satisfying Assumption 4.2. Then Algorithm 1, with inputs T, K, 4, REPelass, and ALG1at, has expected risk
2K T
E Riske (TK)) < Risk,(K) + Estelass (T))
This result shows that we can achieve sublinear risk under latent dynamics as long as (i) the base algorithm achieves sublinear risk Risk,(K) given access to the true latent states, and (ii) the classifi- cation oracle achieves sublinear regret Estclaas (T') Notably, the result is fully modular, meaning require no explicit conditions on the latent dynamics or the base algorithm, and computationally efficient whenever the base algorithm and classification oracle are efficient.
To make Theorem 4.1 concrete, we next provide a representation learning oracle (ExPWEiGHT EIGHTS, DR: Algorithm 3 in Appendix G.1) based on a derandomization of the classical exponential weights mechanism, which satisfies Assumption 4.2 with Estelass Z log [ whenever has access to class & that satisfies decoder realizability.
Lemma 4.1 (Online classification via BEFEIIGHS..RRR Under decoder realizability (ø* $), EXPWEIGHTS.DD (Algorithm 3) satisfies Assumption 4.2 with
Estelass (T) Ö(H log]
Instantiating Theorem 4.1 with the above representation learning oracle, we obtain the following algorithmic modularity result.
Corollary 4.1 (Algorithmic modularity under hindsight observability). For any base algorithm ALGiat under decoder realizability (Ø* E ()), O2L with inputs T, K, D. EXPWEIGHTS. and ALGlat achieves
E [Riskasss (TK)) S Risk, + HK log(
T
Consequently, for any ALG setting T Rs KH log / (Kisk,(K) achieves E(Riskabs x Risk, (K) with a number of trajectories TK- Ö logi* /RIsk. (K)).
Inn this section, the notations O, >2, and ignore only constants and logarithmic factors of H.

---

Beyond achieving algorithmic modularity, this result shows that under hindsight observability, we can achieve strong statistical modularity (modulo possible H factors) for every base MDP class Miat. an important result in its own right." " As an example, suppose that Risk, (K) (KK-1/3)) which is satisfied by many standard algorithms of interest [JKALSI7; JYW120; JLM21; FKQR21]. Then, setting I' according to Corollary 4.1 obtains an expected risk bound of using O H log 1//5) trajectories.
Remark 4.1 (Online versus offline oracles). Theorem 4.1 critically uses that assumption that REP satisfies an online classification error bound to handle the fact that data is generated adaptively based it produces, which is by now a relatively standard technique in the design of interactive decision making algorithms [FR20; FKQR21; FR23]. We note that under coverability and other exploration conditions, online oracles for classification can be directly obtained from offfine (i.e. supervised) classification oracles [XFBJK23; BRS24; FHQR24).
on the estimators "i"),__.. ,...., 3
4.2 Algorithmic modularity via self' self-predietive estimation
We complement the above results by studying the general online RI. setting without hindsight observations. To address this more challenging setting, we design an optimistic self-predictive estimation objective (Eq. (7)), which learns a representation by jointly fitting a decoder together with a latent model. We prove that any representation learning oracle that attains low regret with respect to this objective can be used in O2L to obtain eeservable-to-latee reductions for any low-rist base algorithm ALG1at (for formal statement, see Theorem A.1) We provide (computationally inefficient) estimator (SELFPREDICT, OPT; Algorithm 4 in Appendix H.I) which we show attains low optimistic self-regret under certain statistical conditions (namely, coverability of the base MDP and a function approximation condition enabling us to express the self- self-prediction target as a latent model, see Lemma A. for formal statement), thereby obtaining an end-to-end reduction for the general online RL setting. For lack of space, these results are deferred to Appendix A.
5 Discussion
Our work initiates the study of statistical and algorithmic modularity for reinforcement learning under general latent dynamics. Our positive and negative results serve a first step toward unified theory for reinforcement learning in the presence of high- tigh-dimensional observations. To this end, we close with some important future directions and open problems.
Statistical modularity. Can we obtain a unified characterization for the statistical complexity of RL under latent dynamics with a given class of base MDPs Miat? Our results in Section suggest that this will require new tools that go beyond existing notions of statistical complexity. Toward resolving this problem, concrete questions that are not yet understood include: (i) Is coverability [XFBJK23] (as opposed to pushforward coverability) sufficient for learnability under latent dynamics? (ii) Is the Exogenous Block MDP problem [EMKAL22;; MFR24] a special case of our general framework- statistically tractable? Lastly, are there additional types of feedback that are weaker than hindsight observability, yet suffice to bypass the hardness results in Section 3?
Algorithmic modularity. Can we derive a unified representation learning objective that enables algorithmic modularity whenever statistical modularity possible? Ideally, such an objective would be computationally tractable. Alternatively, can we show that algorithmic modularity fundamentally requires stronger modeling assumptions than statistical modularity? Toward addressing the problems above, first step might be to understand: (i) What are the minimal statistical assumptions under which we can minimize the self- predictive objective in Section 4.2? (ii) How can we encourage finding good representations via self- self-prediction beyond the use of optimism over the base (latent) models; and (iii) when can we minimize self self-prediction in a computationally efficient fashion?
Acknowledgements
Nan Jiang acknowledges funding support from NSF IIS-21 12471, NSF CAREER IIS-2141780 Google Scholar Award, and Sloan Fellowship.
" Formally, while we have defined the statistical modularity condition in terms of high-probabiliity risk bounds. it is straightforward to extend it to instead consider expected risk bounds.
10

---

References
[ACK24]
Philip Amortila, Tongyi Cao, and Akshay Krishnamurthy. "Mitigating Covariate Shift in Misspecified Regression With Applications to Reinforcement Learning". In: Conference Learning Theory. 2024.
[AFISX24]
Philip Amortila, Dylan J. Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. "Harnessing Density Ratios for Online Reinforcement Learning". In: International Conference on Learning Representations. 2024.
[AFK24]
Philip Amortila, Dylan J Foster, and Akshay Krishnamurthy. "Scalable Online Exploration via Coverability". In: International Conference Machine Learning. 2024.
[AHKLLS14]
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. "Taming the monster: fast and simple algorithm for contextual bandits". In: International Conference on Machine Learning. 2014.
[AJKS22]
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learn- ing: Theory and algorithms. https: : / r/thhorybbokk github. io/. Version: January 31, 2022. 2022.
[AJSWY20]
Alex Ayoub, Zeyu Jía, Csaba Szepesvari, Mengdi Wang, and Lin Yang. "Model- Based Reinforcement Learning with Value-Targeted Regression". . In: International Conference on Machine Learning. 2020.
[AKKS20]
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. "FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs", In: Neural Information Processing Systems. 2020.
[AOM17]
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. "Minimax Regret Bounds for Reinforcement Learning". In: International Conference Machine Learning. 2017.
[AZ22]
Alekh Agarwal and Tong Zhang. "Model-basee RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity". In: Neural Information Processing Systems. 2022.
[Bak+22]
Bowen Baker, Ilge Akkaya, Peter Zhokov, Joost Huizinga, Jie Tang, Adrien Ecoffet, Brandon Houghton, Raul Sampedro, and Jeff Clune. "Video Pre PreTraining (VPT): Learning to Act by Watching Unlabeled Online Videos". In: Neural Informaion Processing Systems. 2022.
[BLM13]
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequali- ties: A nonasymptotic theory of independence. Oxford university press, 2013.
[Bro+22]
Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog. Jasmine Hsu, Julian Ibarz. Brian Ichter, Alex Irpan, Tomas Jackson, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmniry Kalashnikov, Yuheng Kuang, Isabel Leal, Kuang Huei Lee, Sergey Levine, Yao Lu, Utsav Malla, Deeksha Manjunath, Igor Mordatch, Ofrr Nachum, Carolina Parada, Jodilyn Peralta, Emily Perez, Karl Pertsch, Jornell Quiambao, Kanishka Rao, Michael Ryoo, Grecia Salazar, Pannag Sanketi, Kevin Sayed, Jaspiar Singh, Sumedh Sontakke, Austin Stone, Clayton Tan, Huong Tran, Vincent Vanhoucke, Steve Vega, Quan Vuong, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Tianhe Yu, and Brianna Zitkovich. "RT-1: Roboties Transformer for Real- World Control at Scale". In: arXiv:2212.06817 2022.
[BRS24]
Adam Block, Alexander Rakhlin, and Abhishek Shetty. "On the Performance of Empirical Risk Minimization with Smoothed Data". In: Conference on Learning Theory. 2024.
[CBL06)
Nicolo Basa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cam- bridge university press, 2006.
[CJ19]
Jinglin Chen and Nan Jiang. "Information- Considerations in Batch Reinforcement Learning". In: International Conference on Machine Learning. 2019.
[DKJADLI9]
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. "Provably Efficient RL. With Rich Observations via Latent State Decoding". In: International Conference Machine Learning. 2019.

---

[DMKV21]
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. "Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Re- visited". In: Algorithmic Learning Theory. 2021.
[DMRY20]
Sarah Dean, Nikolai Matni, Benjamin Recht, and Vickie Ye. "Robust Guarantees for Perception- Serception-BBsed Control". In: Learning for Dynamics and Control. 2020.
[DR21]
Sarah Dean and Benjamin Recht. "Certainty Equivalent Perception-Base Control". In: Learning for Dynamics and Control. 2021.
[Du+21]
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. "Bilinear Classes: A Structural Framework for Provable Generalization in RL In: International Conference on Machine Learning. 2021. Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. "Provably Efficient Rein- forcement Learning With Aggregated States". In: arXiv:1912. 063666. 2019.
[DVRZ19]
[EFMKL22]
Yonathan Efroni, Dylan J Foster, Dipendra Misra, Akshay Krishnamurthy, and John Langford. "Sample-Efficien Reinforcement Learning in the Presence of Exogenous Information". " In: Conference on Learning Theory. 2022.
[EMKAL22]
Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. "Provable RL With Exogenous Distractors via Multistep Inverse Dynamics". In: International Conference on Learning Representations, 2022.
[FGH23]
Dylan J Foster, Noah Golowich, and Yanjun Han. "Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient". In: Conference on Learning Theory. 2023.
[FGQRS23]
Dylan J Foster, Noah Golowich, Jian Qian, Alexander Rakhlin, and Ayush Sekhari. "Model-Free Reinforcement Learning with the In: Neural Information Processing Systems. 2023.
Coefficient".
[FHQR24]
Dylan J Foster, Yanjun Han, Jian Qian, and Alexander Rakhlin. "Online Es- timation via Offline Estimation: An Information -hoomation-Theoretic Framework". In: arXiv:2404.10122 2024.
[FKQR21]
Dylan Foster, Sham Kakade, Jian Qian, and Alexander Rakhlin, "The Statisti- cal Complexity of Interactive Decision Making". In: 1rXiv:2112.13480 2021.
[FR20]
Dylan J Foster and Alexander Rakhlin. "Beyond UCB: Optimal and Efficient Contextual Bandits With Regression Oracles". In: International Conference on Machine Learning. 2020.
[FR23]
Dylan Foster and Alexander Rakhlin. "Foundations of Reinforcement Learning and Interactive Decision Making". In: arXiv:2312. 16730. 2023.
[FWYDY20]
Fei Feng, Ruosong Wang, Wotao Yin, Simon S Du, and Lin Yang. "Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning". In: Neural Information Processing Systems. 2020.
[GCWXWB24]
Jiacheng Guo, Minshuo Chen, Huan Wang, Caiming Xiong, Mengdi Wang, and Yu Bai. Caample-Efficient Learning of POMDPs with Multiple Observations In Hindsight". In: International Conference on Learning Representations, 2024.
[Gee00]
S. A. van Geer. Empirical Processes in M-Estimation. Cambridge University Press, 2000.
[GKBNB19]
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Mare G Belle- mare. "DeepMDP: Learning Continuous Latent Space Models for Representation Learning". In: International Conference on Machine Learning. 2019.
[GMR24]
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. "Exploring and Learning in Sparse Linear MDPs Without Computationally Intractable Oracles". In: Symposium on Theory of Computing. 2024.
[Guo+22]
Zhaohan Guo, Shantanu Thakoor, Miruna Pislar, Bernardo Avila Pires, Florent Altché, Corentin Tallec, Alaa Saade, Daniele Calandriello, Lean-Bastien Grill, Yunhao Tang, Michal Valko, Rémi Munos, Mohammad Gheshlaghi Azar, and Bilal Piot. "BYOL-Explore: Exploration by Bootstrapped Prediction". In: Neural Information Processing Systems. 2022.
[Haf+19]
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. "I "Learning Latent Dynamics for Planning From Pixels".
In: International Conference on Machine Learning. 2019.
12

---

[HLBN19]
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. "Dream to Control: Learning Behaviors by Latent Imagination". In: International Conference Learning Representations. 2019.
[HLNB21]
Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. "Master- ing Atari With Discrete World Models". In: International Conference on Learning Representations. 2021.
[HLSW21]
Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. "Online Sparse Reinforcement Learning". In: International Conference on Artificial Intelligence
and Statistics. 2021.
[HPBL23]
Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. "Mastering Diverse Domains Through World Models". In: arXiv:2301.041 2023. Nan Jiang. "A Note on Loss Functions and Error Compounding in Model-based Reinforcement Learning". . In: arXiv:2404.0990 2024.
[Jia24]
[JKALS17]
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. "Contextual Decision Processes With Low Bellman Rank Are PAC- Learnable.. In: International Conference on Machine Learning. 2017.
[JLM21]
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. "Bellman Eluder Dimension: New Rich Classes of RI Problems, and Sample-Ffficient Algorithms". In: Neural Information Processing Systems. 2021.
[JYWJ20]
Chi Jin, Zhuoran Yang. Zhaoran Wang. and Michael Jordan. "Provably Efficient Reinforcement Learning With Linear Function Approximation", In: Conference on Learning Theory. 2020.
[KAL16]
Akshay Krishnamurthy, Alckh Agarwal, and John Langford. "PAC Reinforcement Learning With Rich Observations". In: Neural Information Processing Systems. 2016.
[KFPM21]
Ashish Kumar, Zipeng Fu, Deepak Pathak, and Jitendra Malik. "RMA: Rapid Motor Adaptation for Legged Robots". In: Robotics: Science and Systems. 2021. Jonathan Lee, Alekh Agarwal, Christoph Dann, and Tong Zhang. "Learning in POMPDs Is Sample-Efficient With Hindsight Observability". In: International Conference on Machine Learning. 2023.
[LADZ23]
[Lam+24]
Alex Lamb, Riashat Islam, Yonathan Efroni, Aniket Rajiv Didolkar, Dipendra Misra, Dylan J Foster, Lekan P Molu, Rajan Chari, Akshay Krishnamurthy, and John Langford. "Guaranteed Discovery of Control-EEndogenou Latent States with Multi-Step Inverse Models". In: Transactions on Machine Learning Research. 2024.
[LFDA16]
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. "End-To-Eae Training of Deep Visuomotor Policies". In: The Journal of Machine Learning Research. 2016.
[Li09]
Lihong Li. A Unifying Framework for Computational Reinforcement Learning Theory. Rutgers, The State University of New Jersey, 2009.
[LS20]
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University
Press, 2020.
[LSA20]
Michael Laskin, Aravind Srinivas, and Pieter Abbeel. "CURL: Contrastive Unsu- pervised Representations for Reinforcement Learning". In: International Confer- ence on Machine Learning. 2020.
[LXIZV24]
Michael Lanier, Ying Xu, Nathan Jacobs, Chongjie Zhang, and Yevgeniy Vorobey- chik. "Learning Interpretable Policies in -indsight--bserrablee POMDPs through Partially Supervised Reinforcement Learning". In: arXiv:2402.09290 2024. Zak Mhammedi, Adam Block, Dylan Foster, and Alexander Rakhlin. "Efficient Model-Free Exploration in Low-Rank MDPs". In: Neural Information Processing Systems. 2023.
[MBFR23]
[MCKJA24]
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. "Model-Free Representation Learning and Exploration in Low-Rank Mdps". In:
Journal of Machine Learning Research. 2024.
13

---

[MFR23]
Zakaria Mhammedi, Dylan J Foster, and Alexander Rakhlin. "Representation Learning With Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RI.". In: International Conference on Machine Learning. 2023.
[MFR24]
Zakaria Mhammedi, Dylan Foster, and Alexander Rakhlin. "The Power of Resets in Online Reinforcement Learning". In: arXiv:2404.15417. 2024.
[Mha+20]
Zakaria Mhammedi, Dylan J Foster, Max Simchowitz, Dipendra Misra, Wen Sun, Akshay Krishnamurthy, Alexander Rakhlin, and John Langford. "Learning the Linear Quadratic Regulator From Nonlinear Observations". In: Neural Information Processing Systems. 2020.
[MHKL20]
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. "Kine- matic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning".. In: International Conference on Machine Learning. 2020.
[MJTS20]
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. 2020.
[MLJL2I]
Dipendra Misra, Qinghua Liu, Chi Jin, and John Langford. "Provable Rich Observa- tion Reinforcement Learning With Combinatorial Latent States", In: International Conference on Learning Representations. 2021.
[Ni+24]
Tianeii Ni, Benjamin Eysenbach, Erfan Seyedsalehi, Michel Ma, Clement Gehring, Aditya Mahajan, and Pierre-Luc Bacon. "Bridging State and History Representations:
Understanding Self-Predictive RL". In: arXiv:2401.088%) 2024. Suraj Nair, Aravind Rajeswaran, Vikash Kumar, Chelsea Finn, and Abhinav Gupta. "R3M: A Universal Visual Representation for Robot Manipulation". In: arXiv:2203. /2601 2022.
[NRKFG22]
[OVR16]
Ian Osband and Benjamin Van Roy. "On Lower Bounds for Regret in Reinforce- ment Learning". In: arxiiv16080 02732. 2016.
[PAED17]
Deepak Pathak, Pulkit Agrawal, Alexci A Efros, and Trevor Darrell. "Curiosity- Driven Exploration by Self-Supervised Prediction". In: International Conference on Machine Learning. 2017, pp. 2778-2787.
[RH23]
Philippe Rigollet and Jan- Christian Hütter. dign--dimensional statistics". In: arXiv:2310. 192444 2023.
[RVRI3]
Daniel Russo and Benjamin Van Roy. "Eluder Dimension and the Sample Com- plexity of Optimistic Exploration". In: Neural Information Processing Systems. 2013.
[SAGHCB20]
Max Schwarzer, Ankesh Anand, Rishab Goel, R Devon Hjelm, Aaron Courville, and Philip Bachman. "Data-Efficient Reinforcement Learning with Self-Predictive Representations". In: International Conference Learning Representations, 2020.
[Sch+20]
Julian Schritwieserr, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Lau- rent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. "Mastering Atari, Go, Chess and Shogi by Planning With Learned Model". In: Nature. 2020.
[SJKALI9]
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. "Model-Based RL Contextual Decision Processes: PAC Bounds and Exponential Improvements Over Model-Free Approaches". In: Conference Learning Theory. 2019.
[SLS23]
Ming Shi, Yingbin Liang, and Ness Shroff. "Theoretical Hardness and Tractability of POMDPs in RL with Partial Hindsight State Information". In: 20060:2300.08762. 2023.
[SWFK24]
Yuda Song, Lili Wu, Dylan J Foster, and Akshay Krishnamurthy. "Rich- Observation Reinforcement Learning with Continuous Latent Dynamics". In: International Conference on Machine Learning. 2024.
[SZSBKS23]
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. "Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient". In: International Conference Learning Representations. 2023.
14

---

[Tan+17]
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman. Filip DeTurek, and Pieter Abbeel. "# Exploration: Study of Count-Based Exploration for Deep Reinforcement Learning". In: Neural Information Processing Systems. 2017.
[Tam+23]
Yunhao Tang, Zhaohan Daniel Guo, Pierre Harvey Richemond, Bernardo Avila Pires, Yash Chandak, Remi Munos, Mark Rowland, Mohammad Gheshlaghi Azar, Charline Le Lan, Clare Lyle, András György, Shantanu Thakoor, Will Dabney, Bilal Piot, Daniele Calandriello, and Michal Valko. "Understanding Self-Predictive Learning for Reinforcement Learning".. In: International Conference on Machine Learning. 2023.
[UZS22]
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. "Representation Learning for Online and Offline RL in Low-rank MDPs". In: The Tenth International Conference on Learning Representations. 2022.
[WSD15]
Niklas Wahlström, Thomas B Schön, and Marc Peter Deisenroth. "From Pixels Torques: Policy Learning With Deep Dynamical Models". In: International Conference on Machine Learning. 2015.
[WSY20]
Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. "Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach Bounded Eluder Dimension". In: Neural Information Processing Systems. 2020.
[WYDW21]
Tianhao Wu, Yunchang Yang. Simon Du, and Liwei Wang. "On Reinforcement Learning With Adversarial Corruption and Its Application to Block MDP". In: International Conference Machine Learning. 2021.
[XFBJK23]
Tengyang Xie, Dylan Foster, Yu Bai, Nan Jiang, and Sham M Kakade. "The Role of Coverage in Online Reinforcement Learning". In: International Conference on Learning Representations. 2023.
[X]21]
Tengyang Xie and Nan Jiang. "Batch Value-Function Approximation With Only Realizability". In: International Conference Machine Learning. 2021.
[YFK21]
Denis Yarats, Rob Fergus, and Ilya Kostrikov. "Image Augmentation Is All You Need: Regularizing Deep Reinforcement Learning From Pixels". In: International Conference on Learning Representations. 2021.
[ZGS21]
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. "Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes". In: Conference on Learning Theory. 2021.
[Zha06]
Tong Zhang. "From c-entropy to KL-entropy: Analysis minimum information complexity density estimation" In: The Annals of Statistics. Vol. 34. 5. Institute of Mathematical Statistics, 2006, pp. 2180-2210.
[Zha22]
Tong Zhang. "Feel-Good Thompson Sampling for Contextual Bandits and Rein- forcement Learning". In: SIAM Journal on Mathematics of Data Science. 2022.
[ZMCGL21]
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. "Learning Invariant Representations for Reinforcement Learning Without Recon- struction". In: International Conference on Learning Representations. 2021.
[ZSUWAS22]
Xuezhou Zhang. Yuda Song, Masatoshi Uehara, Mengdi Wang. Alekh Agarwal, and Wen Sun. "Efficient Reinforcement Learning Block MDPs: A Model-Free Representation Learning Approach". In: International Conference on Machine Learning, 2022.
15

---

Contents
Omitted Results from Section 4: Algorithmic Modularity via Self-predictive Estimation
17
A.1 Self-predictive estimation
17
A.2
Main result
18
A.3
Instantiating the self- preddccceitiiee estimation oracle
19
B Additional Discussion of Related Work
22
Technical Tools
23
Structural Properties of Coverability and Mismatch Functions
24
E
Proofs and Additional Results for Section 3.2: Impossibility Results
28
E.1
Additional Lower Bound
28
E.2
Details for Figure
28
E.3
Proofs for Lower Bounds (Theorems 3.1 and E.1)
34
Proofs for Section 3.3: Positive Results
40
F.1 Technical Overview: Low-dimensional embeddings for pushforward-coverable MDPs.
40
F22 Proofs for Latent Model Class Pushforward Coverability (Theorem 3.2)
G Proofs and Additional Information for Section 4.1: Hindsight RL
52
G.1 Pseudocode and Proofs for EXPWEIGHTS, DR (Lemma 4.1)
52
G.2 Proofs for O2L Under Hindsight Observability (Theorem 4.1)
53
H Proofs for Appendix A: Self-Predietive Estimation
56
H.I Pseudocode and Proofs for SELFPREDICT.OPT (Lemma A.I)
56
H.2 Proofs for Main Risk Bound (Theorem A.1)
60
I
Additional Results for Appendix A: Self-Predictive Estimation
63
I.1
O2L with Self-predictive Estimation and CorruptionRobust Base Algorithms
63
1.2
Proofs for Appendix I.1.2 Properties of d-compressed POMDPs
66
1.3
Proofs for Appendix 1.1.3: Risk Bound Under CorruptionRobustnest (Theorem H.1)
1.4
Proofs for Appendix 1.1.4: Examples of CorruptionRobust Algorithms .....
73
16

---

A Omitted Results from Section 4: Algorithmic Modularity via Self-predictive Estimation
In this section, we remove the assumption of hindsight observability used in Section 4. and instantiate O2L in the general online RI. setting. Rather than assume access to additional side-inoormation, we adopt a model-based representation learning approach, and augment our ability to perform representation learning by equipping the representation learning algorithm with set base MDPs Miat in addition to the decoder class Q. We will learn a representation by jointly fitting a decoder and the base (latent) dynamics, which is common approach in practice [GKBNB 19; HLBN19; Haf+19; HLNB21; 2ch+20; SAGHCB20; Guo+22]. We firstly present in Appendix A.1 a new notion of optimistic eeff-reedcctive regret which combines self preddicreetive representation learning with form of optimism over a learned latent model. We then show in Appendix A.2 that any representation learning oracle that attains low regret, when used within 02I (Algorithm 1), leads observable-to- latent reductions that ensure low risk for any base algorithm ALGGit thereby achieving algorithmic modularity. Lastly, in Appendix A.3, we instantiate this oracle under natural structural and function approximation conditions, yielding end-to-end modularity and sample complexity guarantees.
A.1 Self-predictive estimation
Our seff-predictive representation learning oracles learn to fit a representation 6 such that the induced latent transitions (ø) (xx) ) to 0h+1 (2++1)) can be accurately modeled by some base (latent) MDP Mist E .Maat To describe the objective, let us first introduce some notation. For given MDP M over either S (resp. X), we write MA. (rE, 8841 8h, as.) (resp. Mr (rk,, Th++1 Th, (n for the joint conditional distribution over rewards and next states. Next, for any & E & we define the pushforward model for ob induced by & via:
[ Mobos (r, 12, [2.0)= =
Σ
Mass. x' |x,a).
(6)
x':00+1 (=')=s'
The pushforward model for á captures the forward probability of the estimated latent state d(x') given a current observation x. To measure distance between models, we will use squared Hellinger distance (e.g, Foster et al. [FKQR21]), 1), defined via (P,, Q) = S zh v
dQ dv
dv for common
dominating measure v. Then, for a base model Mist and a decoder Φ. the self preddprreictive error of (Mist. Φ), at state-action pair Th, ah, is given by
(M ()) an) = DĀ a (IN). an), ( ( (x).a)))
This term captures the ability of Mur.a (on (In).. ). an) to predict the next latent state Φn+1 (x)+1) which is obtained by the pushforward model M (Ira, ax). Formally, in our model-based representation learning setup, we consider oracles which, for each iteration within O2L, take as input the trajectories collected so far and produce an estimate (Min (09) for the decoder and base model. The representation learning oracle's 's self-predictive regret, for the sequence ( (Min T10), is then defined
H E (9) mptt En [ 3 Me,, an)
Regseir (T))
h=0
where yd represents a randomization distribution over the policy (0)
On its own, minimizing this regret may lead to degenerate solutions, a widely observed phenomenon in practice [Tan+23]. For example, in a standard combination lock MDP (e.g., Agarwal et al.: Misra et al. [AJKS22; MHKL20J), degenerate decoder-model pair that maps all observations to a single latent state will have zero self- ereeicrede loss until we reach the goal, which can take exponentially long." 12 We address this via the notion of optimistic estimation used in Zhang; Foster et al. [Zha22; FGQRS23], which biases the objective towards latent models with high return. This leads to the
This is similar to the observation that naive value function approximation methods, such as Fitted Q- Q-erroatonn, can fail to explore in online RL without optimism. We expect that given access to additional exploratory data (e.g.. in the Hybrid RL setting of Song al. [SZSBKS23J) the latent optimism term can be removed.
17

---

following optimistic self- predictive regret, defined for a parameter y > 0, via
H E plt)
Ea( | (Miat B: (IA,
oeg (I)
t=1 A=
(JAfa (T
We assume going forward that REPself:opt obtains low optimistic self-predictive regret; in Ap- pendix A.3 provide maximun-iikelihood-yyy estimator and conditions under which this holds.
Assumption A.1. For a parameter "y > the online representation learning oracle REPself:on is proper (i.e. outputs Mist E Miat for all I E (T)) and satisfies
and any (possibly adaptive) sequence T(", with T' ~ p'",
E. stt [T, S Estyelf (T,7),
where Es Ege 77 a known upper bound.
We note that only the decoder T is used within O2L; the model Miat is only used for analysis (and possibly within the representation learner RePsetf.opt).
A.2 Main result
We now state the main guarantee for O2L with self-predictive representation learning. Recall that Riskobs (TK) denotes the risk of the O2L reduction. Compared to the hindsight-observable setting, require slightly stronger performance guarantee from the base algorithm ALGiat result scales with the worst-case expected risk for ALG over all Miat E &Maat defined via Riskbase (K) E E[Risk(K, ALG1at Miat))]-
Theorem A.1 (Risk bound for O2I. under self- self-predictive estimation). Suppose REP sePselfo satisfies Assumption A.I with parameter 7 O. Then Algorithm I, with inputs T. K, t, REP RePselfappt and AL.Gat has expected risk
K BiRiskobs (TK) S C1 Riskbase (K) C27 Esteelr.oo (T, + tay KH.,
T
for absolute conslants C12 C2, > 0.
Theorem A.1 achieves sublinear risk as long as (i) the latent algorithm achieves sublinear risk Riskbase (K) given access to the true states, and (ii) the self- self-predictive representation learning oracle achieves sublinear regret Estself:opt (T, 7) for an appropriate choice of y. Intuitively, our result scales with Ri Rkbuee (K) instead of Risk, (K) due to potential symmetries in the self-predictive objective. For example, there might be representation-modd to (Mist Ø²") up to permutations of the latent state space; these cannot be distinguished by a representation learning oracle that does not observe the latent states directly, and thus the base algorithm may be tasked with solving either of these base MDPs. As with Theorem 4.1, this result achieves algorithmic modularity (since O2L inherits the risk of the base algorithm), and is computationally efficient whenever the base algorithm and self- self-predictive representation learning oracle are efficient.
pair (Mat,, Φ) that is identical
Let us provide some intuition behind the proof of Theorem A.1. Recall that, within the inner loop of O2L, the latent algorithm ALG1at interacts with the oo*-compeessed dynamics generated by compressing the observations Ih, dg through the current decoder 6% (Line 8). The crux of the analysis is the following observation: by the self preficceei representation learning guarantee, these dynamics, despite being possibly non-Markovian and generated from POMDP (Definition I.1), are well approximated in squared Hellinger distance by the base model Mi estimated by REPseifooot (cf. Lemma I.2). We can then show that ALG1at when given data from the -om-omppeseedd dynamics, has risk (for solving Mi2) that is proportional to: i) its base risk if it were to observe states from M and ii) the Hellinger distance between M and the process induced by its " compressed
For example, in our estimator of Appendix A.3, we can first set R K HRRiskkass (K) so that the third term matches Riskease (K), and then set 1'' so that the second term does.
18

---

dynamics. The last ingredient is the use of latent optimism in Eq. (7), through which the risk on Mia upper bounded by the risk on M
In the above, showing that Att obtains low risk for M (despite given data from different process) is done by establishing certain form of corruption robustness (Definition I.2). Indeed, Theorem A. I is a special case of more general theorem (Theorem H.1), which provides a bound that adapts to ALGiat 's level of robustness. We obtain Theorem A.I by showing that any algorithm satisfies the property we require (for a suitably slow rate), but we further show that tighter rates can be achieved by analyzing the specifies of various algorithms of interest (Appendix I.1.4).
A.3 Instantiating the self-predictive estimation oracle
We now present an algorithm, SELFPREDICT OPT (Algorithm 4 in Appendix H.I), which satisfies Assumption A.I under additional technical conditions, allowing us instantiate Theorem A.I to give end-to-end guarantees. Before stating the main guarantee, we highlight few technical difficulties regarding obtaining unite-sample guarantees for (online) self seff-predictive estimation, and use them to motivate our statistical assumptions and algorithm design.
The statisties of (online) self- self-predictive estimation. The first challenge a realizability issue: when 6 o*, may not even be able to represent the objective of.Ma latent model using only decoder and latent model realizability. Since we can never guarantee that Ø = 6* exactly in the presence of statistical enrors, must introduce modelling assumption which lets capture the pushforward models @t.Mabs To this end, we introduce the mismatch functions, which are defined as follows.
Definition A.1 (Mismatch functions). For a decodable emission process xp" and decoder E 4 the mismatch function, for d, Is of :S A(S) is defined, for every h E [H]] as the probability kernel
I (sh 8n) = PEA maa (en) (dn(wn) = 81,)
In the context of self- self- prediccediiio we show that the following mismatch completeness assumption suffices to capture the pushforward models et.Mabs
Assumption A.2 (Mismatch completeness). We have model class such that, for each & E 4, and Miat E Miat we have I's Mist E L, where
T Miat], (Phy Sh-1 Sh, an)
Σ 11
(rat, s/41 Sh an) ( I sh11).
In particular, Lemma D.8 establishes that [01+1 xr a) = T Misth 0 (x).
Accordingly, we view this assumption as minimal way to realize the pushforward models dd
The second challenge is a double-sampling issue, which appears because the decoders in Eq. (7) are coupled at different horizons. We address this with novel "debiased" maximum likelihood procedure that subtracts form of excess risk (cf. Eq. (60)) to recover an unbiased estimator [Jia24]. Our debiased estimator and the mismatch completeness assumption can be viewed as analogous to the techniques and assumptions that are required for squared Bellman error minimization in the context of value function approximation [CJ19; JLM21].
The last issue stems from seeking an online estimation guarantee: the policies chosen by the latent algorithm function of the estimated decoders, which precludes the of randomized estimators (e.g. exponential weights). We bypass this issue by appealing to the structural condition of coverability [XFBJK23), which allows us restrict our attention to estimators that achieve low offline estimation error (via Lemma C.7).
Definition A.2 (State Coverability). The state coverability coefficient for an MDP M and policy class II defined over a state space Z, Ccov.st (0,, 11), is given by
Ccov.st at (M, (,.1) 11)
max min max max [E(H] (EA(Z) Fell ZEZ
(8)
(==
14 More generally, expect that results be extended any "decoupling coefficient" [Zha22; AZ22].
19

---

We require coverability in Mahs over the set of (observation-spate policies played by the O2L reduction (cf. Line 7). Again appealing to the mismatch functions, we can express this as an assumption about the base dynamics Mar' we show (Lemma D. that the latter is equivalent to assuming coverability in Mat over the set of stochastic policies
T 1lat
s)) [
Φ, Mast Mlst
(9)
3'ES
where Whst denotes the set of policies that ALG1at may execute. While this set may appear compli- cated, is sufficient to assume coverability over the of all deterministic non-stationary policies on Mist.
Guarantee for our self- ceff-predictive estimation oracle. With these prerequisites, the main guarantee for our estimator, SELFPREDICT.OPE OPT (Algorithm 4), is as follows.
Lemma A.1 (Optimistic self-predictive estimation via SELFPREDICT.OPT) Let 1hat denote the set of policies played by ALGists and Czov,st Ccov.st (Mi && Ihst) be the state coverability parameter on Mi over the set of stochastic policies I& o Haat (Eq. (9)). Then, for any > O, under decoder realizability (ø* E }), base model realizability (Mist Miat), and mismatch function completeness with class Liat (Assumption A.2), the estimator in Algorithm 4 with inputs
Φ, Miats Llat; and y satisfies Assumption A. with
Est (T, = =6( - | (ot.oo/ss/A/Toog(MMMMl
Instantiating Theorem A. with the above representation learning oracle, we obtain the following algorithmic modularity result.
Corollary A.1 (Algorithmic modularity via SELFFREDICT OPT). Under the same conditions as in Lemma I. and for any base algorithm ALGiat, O2L with inputs T, K, $, SELFFREDICT. OPT, and ALG1at achieves
K
(RRisko & 61 Riskbase (K)
/o 1 +c)7 KH, VT
for absolute constants C₁ C2. C3. Consequently, for any ALG with base risk Riskbase (K), setting y and T appropriately gives
E(Risk (TK) Riskbaso (K),
with number of trajectories TK- = O(K* ([K*** "1 H Cam. log ([Mune (amel (Rish)
For example, if ALGiat is base algorithm with Riskbase (K) O(K-1/2), setting ? and T appropriately gives an expected risk of with a number of trajectories TK This result shows that statistical modularity can be achieved up to log((E factors for every base MDP class Mist which subsumed by coverability, in- cluding tabular MDPs and low-rank MDPs.!7 Compared to our positive result for the case of pushforward coverability (Section 3.3), this imposes less dynamics assumptions (since coverability implied by pushforward coverability) but requires more representational assumptions (namely, access to the mismatch-complete class L.st). We further remark that the mismatch completeness assumption always holds for the Block MDP setting, since
Ö( (
always construct List such that List) = ) and ii) every MDP class Miat whenever we also have a realizable set of emission processes (+** E WD), since However, the mismatch completeness assumption may be more general than either of these settings.
construct List such that log( Liat)) log( @ [M||M l|
This follows from Lemma D.3 by noting that each maximum the right hand side of Eq. (13) attained by a deterministic non-stations stn-stationary policy.
In this section, the notations O and $ ignores constants and logarithmic factors of: H, Coon.st [A],, and Lise [[Case|(/))
This provides partial answer the "Model Class Coverability" open question of Figure 1.
20

---

Our results can be viewed providing a theoretical justification for self prediccee representation learning, which has been widely used empirical works [GKBNB 19; SAGHCB20J. We consider self-predictiog is ability to obtain universal chservablleto-llten reductions as strong indicator that it merits further theoretical study. In particular, many empirical works propose heuristics to alleviate the sawnnerrayynonuunnuuneeee
issues inherent with self-prediction [GKBNB19] 19; SAGHCB20; HPBL23; Tan+23J. Our methods provide a principled way to address these, and it would be interesting to investigate whether this is also empirically effective. In general, however, it is unclear whether loss admits computationally efficient implementation, due to the presence of optimism. Towards this, fascinating direction for future work is understanding how self- self-predictive estimation can be used to obtain algorithmic modularity without the addition of optimism over the base (latent) models.
21

---

B Additional Discussion of Related Work
In this section, we discuss aspects of related work not already covered in greater detail.
Reinforcement learning under latent dynamics (or, with rich observations). Reinforcement learning under latent dynamics (or, with rich observations) has received extensive investigation in recent years, however most works have been focused on the Block MDP model in which the latent state space is tabular/finite [KAL16; DKJADLI9; MHKL20; ZSUWAS22: MFR23] (see also the the closely related framework of Low-Rank MDPs [AKKS20; MCKJA24; ZSUWAS22: UZS22; MBFR23]). Beyond tabular spaces, Dean et al.: Dean et al.: Mhammedi et al. [DMRY20; DR21; Mha+20] consider continuous linear dynamies, Misra al. [MLJL.21] considers factored (but discrete) latent dynamics, Efroni et al.; Efroni et al.; Mhammedi et al. [EMKAL22; EFMKL22, MFR24] consider the Exogenous Block MDP problem in which a tabular latent state space is augmented with non-controllable ("exogenous") factor, and Song et al. [SWFK24]] consider Lipshitz continuous dynamics. To our knowledge, our work is the first to: i) explore reinforcement learning under general latent dynamics, in particular in settings where the latent space itself admits function approximation, and ii) take a more modular approach (cf. the taxonomy of Section 3).
On the algorithmii side, the works of Uchara et al. [UZS22] and Zhang et al. [ZSUWAS22], which consider Low-Raad Rank MDPs and Block MDPs respectively, can be viewed as interleaving representation learning with "latent" reinforcement learning algorithms that assume access to good representation, and were an inspiration for this work. However, the algorithmic details and analyses are highly specialized to Block/Low-Rang MDPs, and unlikely to be directly applicable to reinforcement learning under general latent dynamics. Other works with a modular flavor include:
Feng et al. [FWYDY20] solve tabular Block MDPs by combining a black-box latent algorithm with an "unsupervised learning oracle" for representation learning. This approach only leads to guarantees for tabular Block MDPs, and it is unclear whether the unsupervised learning oracle their approach requires can be constructed in natural settings.
Wu et al. [WYDW21] solve tabular block MDPs by combining a corruption-robut latent algorithm with representation learning procedure based on clustering. Again, this work is restricted the tabular setting, and requires a separation condition which may not be satisfied in general.
General complexity measures for reinforcement learning. Another line of research provides general complexity measures that enable sample-efficien reinforcement lcarning, including Bellman rank [JKALS17; SJKAL.19; Du+21; JL12 eluder dimension [RVR13), coverability [23, Coefficient (DEC) [FKQR21; FGH23; FGQRS23). Bellman rank and
and the other complexity measures based on average Bellman error [JKALS17; SJKAL19; Du+21: JLM21] are insufficient to characterize learnability under general latent dynamics, as there classes Miat that are known to be learnable, yet do not have bounded Bellman rank or Bellman-Eluder dimension [EMKAL22; XFBJK23]. Meanwhile, variants of Bellman rank based on squared Bellman error or related notions of error can [XFBJK23; AFJSX24] address this problem for some settings, but satisfying the modeelng/reallizabiliy assumptions (e.g.. Bellman completeness) required by these methods in the latent- -ttant- setting is non- von-trivial. For example, the crux of our sample complexity bounds under latent pushforward coverability in Section 3 (Theorem 3.2) is to prove a rather involved structural result which shows that Bellman completeness can indeed be satisfied under this assumption, but it is unclear whether these techniques be applied more general latent dynamics classes We expect that it is possible to bound the -Estinatttninnooo Coefficient [FKQR21; FGH23; FGQRS23] for the framework, but deriving efficient algorithms using this framework is non-trivial.
22

---

C Technical Tools
Lemma C.1. For any sequence of real-valued random variables (Xt)eST adapted to a filtaation (Fi)eg it holds that with probability at least 1 - 8,
S Σ
log (Bx-1 (B=-((exe))) + log(6=1))
Lemma C.2 (Freedman's inequality (e.g.. Agarwal et al. [AHKLLS14]), Let (Xt)eST be a real- valued martingale difference sequence adapted to filtration (F))gT. Xf S R almost surely, then for any 1i (0, 1/ R). with probability at least
T 1
T
log log(6-) (8-1)
X
E
[
7
Lemma C.3 (Corollary Lemma C.2). Let (Xt).ST be sequence of random variables adapted to filtration (Fi)ETT 1f0 S Xx S B almost surely, then with probability at least - 5,
3
X1
E [X,] 4Rlo looloogg(61)))
and
T
T < Σ X, + 8R 1og
Σ E. [X,]
tml
Lemma C.4 (Lemma D.2 of Foster et [FHQR24]).
(1),8))...... (Rn, Bn) sequence of measurable spaces, and let X = =II X, and 8 = 01=181- For each i, let po) and Q be
probability kernels from (2 1) n Dii")) to (X, 3.). Let P and Q be the laws X x.....y Xn under
X; ~ (.) X1--1) and X, ~ (. X13-1), respectively. Then holds that
D)(P,Q) < 7EP Σ { (1a-1), (-1
Lemma C.5 (Lemma A.11 of Foster et al. [FKQR2IJ). Let and Q be probability measures on (X, 3). For all h X + R with 0 < h(X) < R almost surely under IP and Q we have
Es [x(X] < 3 E4 [X())] (P. Q)
Lemma C.6 (Lemma of Jiang al. [JKALS17). For any f: xxxx [0,1]. :: :Sx[[] + A(A).
have
Ez ([][((()(((()))) J(m)
Σ ET - -T (1,,,
Lemma C.7 (Offine-to-online conversion under coverability [XFBJK23; FHQR24J). Let M be an MDP over state space Z, II be policy set, and Ceov = Ceov (M, II) be the (state-action) coverubility coefficient for M and (Definition D.3). Let "t E (III) be sequence of distributions over II, and gh. Z x A + [0, 1] be sequence of functions. Then we have that
Σ
E m (T(") [gh (Iz, an)]
T
0
11 HC (CC)))
log(T)
Σ
E mp(()
BT(()
[gh [ (Ih, an) + HCoov
1=1
1=1
23

---

D Structural Properties of Coverability and Mismatch Functions
This appendix contains structural results regarding coverability and the mismatch functions. We firstly recall the definition of the mismatch functions.
Definition D.1 (Mismatch functions). For decodable emission process 4*, decoder & o and E [ we define the mismatch function for @, Ton S + (SS), as the probability kernel
I T&,a(sh 5n) = (m)) (On((() = s%,).
also recall the definition state coverability.
Definition D.2 (State Coverability). The coverability coefficient for an MDP M and a policy class II defined over a state space 2, Ceov.st (M, II), is given by
dA
(z)
Ceov.st (M, = max min max max
(10)
he(H] #EA(2) xell sE2
(122
We also define the related notion of state-action coverability.
Definition D.3 -State-Action Coverability). The coverability coefficient for an MDP M and a policy class II defined over state space Z and action space A, Coov Coov(M, II), is given by
dh (z,
Cenv M, IT) = max (E(M] REA(ZXA) sEll 2,EE
min
max
MAX
(11)
((2,a)
In the remainder of the section, let Hlst S x [ A(A) denote an arbitrary set of latent policies, and
{{ - Irommellla () s)= E samaa (') Φ 2 mat E 1hat j. (12)
F3 1hat =
s'ES
Lemma D.1 (State coverability is invariant to rich observations). Let Mabs (M 2y Then, have
Ccov. st M Maat +) Coov,st st (Mist, T That)
Furthermore, letting {piat,h E A(S) denote the distribution which wimnesses the right-hane side, the left-hand-side is witnessed by the distribution
Pobs,h ( | (
The lemma follows from the following two observations.
Lemma D.2. Let (To) denote the mismatch functions for emission v/, and let Moss (Mati ". Then, for any That E Matt &, E [H], x X, we have Maaataa ( 06 (d) Musssommu (x)
Proof of Lemma D.2. Below, we write = 8" (II). We proceed by induction, simply writing
dobs, d Maree ob and diat. = di M The base case (h 1) is obtained by noting that
dhat, (s) = 1 0) while doss,, (I:) = Pobs, (x 0) = v (x 8) P (). For the general case, via the Bellman flow equations, we have
dets,, (xn.)
Σ 2h-110h-ERX'4
Pots, Rh an )dots, 1 ma ((xx=1))
= = (N)
Σ
Pa Sh ah- (
sh-1)
The Fh-119h 1. IXXX
x Taac
=sb(an (8h
Σ
Piot, 8h-1, (ietonnn)ddot---lle
#k-1.0h ESxA
Σ
( 3h ((zh-1)).
3h 1h-1100 110 188-1
24

---

The result is obtained by noting that
T' (aat 1h-1)
Σ
Tols'
(h-1))Ta((an-11 16
E'ES
Σ
Σ
( ( = 8 FTiac(nn 18)
e'ES 2h-
(#h-1)=sh-1
(xh-1 9h-1)TTar (ap-1 ((Ik-1)),
2h :6 (2h-11 =8h-1
where the second line follows from the definition of the mismatch functions.
Lemma D.3 (Equivalence state coverability and cumulative state reachability). Let M be an MDP defined over state space Z. The following definition is equivalent to Definiiion D.2:
Ccov.st (M) (I,
max
Σ
max
M, dh
(,,,,(()) (2).
(13)
he H
xell
sE
Proof of Lemma D.3. [XFBJK23).
Straightforward adaptation of the proof of Lemma 3 from Xie et al.
Proof of Lemma D.I. Using Lemma D.2 and Lemma D.3, we have
Ccov,st (Moss Mat b)
max hE|H]
max d (x) mati
zex
Σ =ex
max 3 (x o² ( PaoTm (x==)) Tatss
max
hE[H]
max 2i (æ s ff (s)
max
be[H]
sES xop (x)==
max hE(M]
max Fla.
Faooie (s)
lat
Σ
2 1 ss
.ES
(x)=
Scov.st (Mar I' llltt).
Lastly, we show that state-action coverability is bounded by state coverability times the size of the action set.
Lemma D.4 (State-action coverability bound). For any MDP M and policy set II, have (M, II) S Ccov,st [, I))
Proof Lemma D.4. Let μs E ((2) witness Ceav.st (M, IT). Fix h E [H]. which we omit below for cleanliness. Then, we have
d
d. 12)
min max max Me TEll 2,0ExA
max max TEll 2,EE
(2,a(2,a)
(2)
dM::(2)
S |A| max max HEll ZEZ
ML((z)
Ccov.st (M,
Lemma D.5 (Pushforward coverability is invariant rich observations). Cpust (M) denote the pushforward coverability parameter for MDP M (Definition 3.3), and Mas := (M Mst 1/ G. Then, we have
Cpush (Mass) Opush (M)
25

---

Furthermore, letting {piat, E he denote the distribution which witnesses the right-huu Bight-hand- side, the left-hand-side is witnessed by the distribution
Mobs, (x) = ( (=)))))a
This follows from analogous equivalence of pushforward coverability and cumulative conditional reachability.
Lemma D.6 (Equivalence of pushforward coverability and cumulative conditional reachability). Let M be an MDP defined over a state space with transition kernel P. The following definition is equivalent to pushforward coverability (Definition 3.3):
Cussh (M) = max
Σ P'EZ
max Pn 12,a).
hE(
2,EZ
Proof of Lemma D.6. Fix h E [H], whose dependence we omit below. For the first direction, letting j denote the pushforward coverability distribution, we have:
P(z' 2, m(=²) S Opush
P(d (2,a)= Z'EZ Z.EEXA
Σ
Σ
Σ
M(=')=
Cpssh
2,aEZxA
m(2")
z'EZ
For the second direction, taking paz') x max; P(z' a). we have
P( (2,0)
P( 2,
mAX MEA(Z) 2, EZxAx2
min
max
Σ
max P( 2,,0)
M(21)
2,0, EZxxxxxx22 maXşa P( / 12 a)
a,
Σ max P(z' a.
2,0
Proof of Lemma D.5. This result follows by Lemma D.6 since,
Opush (Mobs)
Σ
max Pobs
(2') xx,a)
Z.a
x'EX
Σ
Σ
max (x' |s') (6*(x))
3,
E'ES af ya
Σ S'ES
max Piat(s' I [0'(x),)) 2,
Σ
" (x'x1 (s)
='=0"(=))=
Σ S'ES
max Plac(s' (sa)) = Cpush (Maat). 8,a
We next show that the mismatch functions can be used to express the observation-level backups for any function of the decoders. For any g + R. h E [H], we define the function [T ogg S - IR
Ta o (s)
Σ Tona(s s)g(s')..
x'ES
We further overload the Bellman operator notation and define, for any g : S - R and Mist (Fiacy Piat),
Min g](s, a) = (iac(s, a) + Esr=
Lemma D.7. Let Mabs = (Miie,, 3² R, o² = (w+)-1,, Φ E t and T be the mismatch function for emission d/* (Definition D. Then, for any fiat S x A - RR, h E [H), and (x. a) E & A, we have
May (Sia o @n+1) (x, a)
Thelin (To.A4 o V/na) (07()))
26

---

Proof of Lemma D.7. Let f == flat, h [H], and (x,a) E d' x A be given. Then, we have:
[Tuaen (s (oob+1))))) (2)
-0at, (x), + (ottt) (osns//ooooaaaaaaooooooaaoooaaa/
= -
Σ 3 (In+1 (
FN+IEX
Σ Tols' (onn)1((6))
E'
(oa (z), TT (To vj) (z),
where the third line follows from the definition of the mismatch function T'.
We next show that the mismatch functions can be used to realize the pushforward dynamics @t.Mass which we recall are defined as:
[otMMas, ] (r, 22, [2)0)=
E
Mabs, (r, x, x.
(14)
We also recall the notation To.411 o Miatha defined via:
T o Maat), 9h-1 Sh, an)
Σ
(1at, s/ Shs an (oJ04110 1/+1).
Lemma D.8 (Pushforward model realizability via mismatch functions). For all Φ E o (H). we have:
Ton- M k- æ, a) = [[T Mi Φi] (- x.
(15)
Proof of Lemma D.8. Note that I's can alternatively be written as:
(o 8s))
Σ
(xn sz).
==:0(=a)=*k
We have
Φn+ (Th+1, Sh+1 Ihe
Σ
Mo (Th+1, T641
Th. 0n)
Σ
Σ
Mist, 8' (T())) an Wh (x 1 88)
2h41:0n4 (a (#h+1) 1=9h44
Σ
Mr,
(z)),
Σ
(2 s²)
r,s'ERxS
Σ (r,
(1)))) an I To.biiss 1841))
rRR'S
-To Mirh (r, Sh+1 (x))), an).
as desired.
27

---

E Proofs and Additional Results for Section 3.2: Impossibility Results
This section contains additional information and proofs related to our impossibility results regarding statistical modularity (Section 3.2), and is organized follows:
Appendix E. contains the statement for an additional lower bound that is useful for establishing the impossibility results of Figure 1.
Appendix F.2 contains details for each entry of Figure 1.
Appendix E.3 contains for proofs for main lower bound (Theorem 3.1) and the additional lower bound (Theorem E.
E.1
Additional Lower Bound
Theorem E.1 (Alternttiv lower bound). For every N 2 4, there exists an emission class Y and |
-N and a family of latent MDPs Miat satisfying (i) |Maall (ii) H = 1, (iii) SS| = | = N, (iv) N, and such that
decoder class with /
For all e, we have comp(M E, O.
2. For an absolute constant 0, comp [omp(([Merr MMMss T) 2 (VNN/oo((V)
Proof of Theorem E.1. See Appendix E.3.2.
E.2 Details for Figure 1
Below, we provide details on each entry in Figure 1. More precisely, for each latent class Mast. we will give a (brief) description of the MDP class Miats give our choice of latent complexity comp for Miat. and prove that the class is or is not statistically modular for that choice of latent complexity. We view our choices of latent complexities as natural complexities for the respective classes.
Tabular MDPs (V).
Latent class Miati Tabular MDPs Miat = Pla. Riats H). [AOM17]
Latent complexity comp: We take comp E, 8) - poly([S), |A|, H, log 0-1), which is attainable, for example, via the UCB-VI algorithm of Azar al. [AOM17]
Statistical modularity (V): Known Block MDP algorithms (e.g. MUSIK [MFR23), BRIEE
[ZSUWAS22]) have sample complexities of poly([S],, [A], H, log 8-1, log +1).
Contextual Bandits (V).
Latent class MMat: Contextual bandits with context space S, action space A, reward function rist S x A [0, 1] and finite realizable function class satisfying r* E Fiat.
Latent complexity comp: We take comp(Maat, E, 5) logg(//), 11, log 0-1), attain- able via, e.g., the SQUARE-CB algorithm [FR20].
Statistical modularity (V): We note that Fiat o $ = - ff o is a realizable function class for the observation-level reward function ra since rots [ria: oØ] E Fist O. Thus, applying the SQUARE-CB algorithm directly on the observations xh a r(t)) will give complexity poly([AA) log(] (1), e log 5-1) poly(|AA), log [Fitt log |bb log 1-1
Low-rank MDP (V).
Latent class Miat: MDPs Miat (S,A, Plat, rlat) such that there exists Mist. Rd. iiac E Rd, and a known set of features Eist = (fiot = (Eiee : S x A Rd) H
)d) J--1
such that
for all [M]] we have (Sh, an) = (Stat,A (sh, an), (Ta,, n as well as
(st, Sh, an) (Ciot, (sh, an), (iseh44155h11))
(16)
for some Siat Elat-
I Latent complexity comp: We take comp(Mhat,, e, 8) poly(d, [A), log |Eael e -,, log 8-1), which is attainable via the VoX algorithm of Mhammedi et al. [MBFR23].
28

---

Statistical modularity (V): This is obtained by noting that the observation-level dynamics also satisfy the low-rank property with the same dimension. Formally, letting Pabs be the transition kernel for Maat, 1 and @² = (16*)=1, we have
P Pobs, (1n+1 Th, an)
Σ (5t, (Ta),, an) (1 88411)
Sh+rES
Σ Sh41E8
( ( (1%(2), Pia (oan)))) ( 8141)
Sinch (o)
E $h41E8
Thus, the transition kernel Pobs is low-rank MDP
with Mobs, (Fn+1)
Ema Miat, (8h-1) (Tn+1 1844) 1) and feature class
Eist o 2 = ( o = {EΛ On z a + (x()n(r), a)) Elat E Elat, o E $).
Lastly, since Yohs [Mat o 6²), the reward function is also linear with the same unknown feature class. Thus we can apply Vox directly on top of the observations, with the feature class Elat o b, which will achieve complexity poly(d, [A], H, Loa/ log | log(( ())(
Known Deterministic MDP (Miie 1) (n)
Latent class Miac Miat {M1st (S, A. Piat: Riats H)} is set of MDPs of size 1 with both deterministic rewards and deterministic transitions.
Latent complexity comp: We take comp(MMatt,, O, which is attainable as Mist is known and we can simply deploy optimal policy.
Statistical modularity (V): We note that, due to determinism, the latent optimal policy can be chosen to be open-loop without loss of generality, and thus will always experience the same trajectory (si, ai...... st ).z). We can define the observation-level policy which commits to this same sequence of actions, i.c. Tobs, (2x, = aj, for all zy. This will be an optimal policy for any Mobs = Miat, 2b and can also be learned in samples.
Low State Occupancy (V
A(A)) (V).
Latent class Miat: Miat {Mat (S, A. Plat. Riat H)} is set of MDPs for which we have realizable value function class, and such that there exists feature map Slat = [Siat,h S - Rdd) h=1
such that for all - A(A) and for all Mist Mist. we have
4h [H] 30,
d (s) (8), M M
Note that the feature map does not need be known.
Latent complexity comp: We take Comp(Maat,E 5, poly(d, [A], H. log|FFacl, (. which is attainable by the BIIIN-UCR algorithm of Du et al., since i) MDPs with this property have Bilinear rank bounded by A| (see Definition 4.3 and Lemma 4.6 of Du et al. [Du+21]), and ii) can construct the value function class Fiat (Q.M..A
Mist Miat), which is realizable
and has size log] Fiatl = lorl
Statistical modularity (V): We firstly note that one construct realizable value function class for the set (MMia 2). via the set Fabs {Q Mine: & Miat Miat: & E }. This is realizable since, for any Mass == ( (Mas,, v)), letting 6- = - we have Maasi* = Musss oØ", and that this class has size log, log|Matt Mag We can then show that the occupancies da for foss E Fobs- also be expressed as d-dimensional linear function for an appropriate choice of features, which will imply that the BILIN- UCB algorithm run directly on Mobs will attain a complexity of poly(d, (d. [A], H, log Mist, log T el log(5 (eg(5-1) ')). To obtain this, recall the following lemma:
Lemma D.2. Let (Tokee denote the mismatch functions for emission v², and let Mots = { (Mat 3²* Then, for any mat E lhat. &b E 4, h E [H], x E X, we have
M Masmin (2)))0((())))))))))()) (i o%
29

---

Thanks to the above lemma, we have
d-fs* (zn) (an I 0 (x (6'(x1))
(mn 1 (xx))) [Siat, @il((p)) 0n Moo
(warn | ( (7](2p)) Moa.oooo
and so d is linear with feature mapping (x 6" (21) [SSstt. 0% and parameter @ MMee.Teer Recall that the feature map need not be known, so that BILIN- UCB can still be applied despite not knowing & and o²
Model class + Pushforward Coverability (V).
Latent class Miat: Mist = (Mat = (S, Piat, Raat. H)} is a set of MDPs that all satisfy pushforward coverability Cpush (Mat) S Cpush (ef. Eq. (28) for the definition).
Latent
complexity
comp:
We
e,, which is attainable by the GOLF algorithm
take
poly(Cpush: |A|, H, via the results of Xie et al. [XFBJK23] (see also Lemma F.3). We obtain this by noting that i) Coov I pushh AA, where Ceav is defined in Definition 2 of Xie et al. [XFBJK23], and ii) realizable model class can be used to construct a realizable value function class F and a Bellman-complete value function helper class G with sizes log]F] Mgg]M] and log|g] O(log|M)..
logg
Statistical modularity (V): This is obtained via Theorem 3.2.
Linear CB/MDP (X*).
Latent class Miss: MDPs Maa = (S, Piat, Raat, H) that are linear with respect to a known feature map Siat S x A Rd (i.c. such that Eq. (16) holds for Siat).
Latent complexity comp: We take comp(M e, 8, = pd,y(d, H log(o-1)) which is attain- able via the LSVI-UCB algorithm of Jin et al. [JYWJ20]. Note that this guarantee does not depend on the number of actions.
Statistical intractability (X): The latent model used in the construction of Theorem E. is a set (of size 1) of linear MDPs with d = 1. In particular, that construction was contextual bandit only have to realize a reward function, and since there is only one latent model so we can trivially embed this with d = 1 via Eiat (s, a) riat (8, a), where Flat is the reward function of the MDP used in Theorem E.1.
Statistical modularity with additional |A| -deeendeence: As in the Low-rank MDP case above, { (Mat, } is low-rank with unknown feature set &' = {Siat ΦØ }). Thus, by the same conclusion, a the Vox algorithm will have complexity poly(d, [A4, log [b),, which is of the desired form we allow suboptimal dependence on |.A.
Model class + Coverability (V Txx M 2M) (X).
Latent assumption: Mist
[Mat = (S.A, Plat. Riat, H)} is set of MDPs that all satisfy coverability with respect to the policy class II. (Tee M M), i.e we have
MMat E Miat: Ceov (Mat) =
inf sup sup M)E((SxA) bE]H] flllm
< 00
14h
Latent complexity comp: We take comp( 8, = pwlyyyoooouo..ooooooo H, log Mog.MMaste Miatl, e log(5-1) which is attainable by the GOLF algorithm via the results of Xie et al. [XFBJK23] (see also Lemma F.3). We obtain this by noting that a realizable model class can be used to construct realizable value function class F and a complete value function class G of sizes log[F = log and log[g| Olog]MM)..
Statistical intractability (X): The latent models used in the construction of Theorem 3.1 set of coverable MDPs in particular, these are trivially coverable with Ccov = 1 since there is a single latent model and we can take μ "Mrg We remark that an interesting open question whether this impossibility result continues to hold if we require coverability with respect to the class II of all possible latent policies.
30

---

Known Stochastic MDP ([Mi 1) (X).
Latent class Miat: Maat {Maa (S,A, Plat, Pist, H)} is set of MDPs of size 1.
Latent complexity comp: We take comp(MMsst; 6) 0, which is attainable as Miat is known and we can simply deploy its optimal policy.
Statistical intractability (X): This is precisely the setting of Theorem 3.1, which shows that at least D(N/ (IN/log(N)) samples will be needed, where N |+].
Bellman rank (Q-type or V-type) (x)
Latent assumption: Mist {Mist = (S. A. Piat Riat. H)} is a set of latent models such that each Maat Maat has Q-type Bellman rank d or V-type Bellman rank [JLM21]. Letting F be realizable value function class for Miat. in the Q-type case, this means that the [[T=] x [F] matrix
(T, E. (8hs (n) - rh - max Jutz (8)+1, a'
admits a rank d factorization. In the V-type case, the matrix
E/ (m Bas -d o
S (5h, rh max (h+1()h+1,
admits rank-d matrix factorization.
Latent complexity comp: We take comp E, 8) poly(d. H, |A| log| log 1)) for the V-type Bellman rank case, which is achievable by the OLIVE algorithm of Jiang et al. [JKALS17], and comp(Maat: E, 5) = poly(d, H, log| e-1, 1og (o-))- for Q-type Bellman rank, which is achievable by the BILIN- UCB algorithm of Du et al. [Du+21].
Statistical intractability (X): We note that the construction in Theorem 3.1 has [Mar which trivially has Bellman rank equal to 1, so Theorem 3.1 precludes statistical modularity with complexity comp.
Eluder dimension Bellman Completeness (X)
Latent class Miat: Miat = (Mat = (S, Piat: Riat H)} is a set MDPs such that there is a function class Fiat satisfying
Vfiat E Fiat, Mist E Miat: Mix fiat E Fiat.
Furthermore, each Miat E Miat has Gellman-Eluded dimension bounded by (see Definition 8 of [JLM21J).
Latent complexity comp: We take comp E, 6) poly(d, H, log| log log(6-1)), which is attainable by the GOLF algorithm Jin et al. [JLM21].
Statistical intractability (X): As in the Bellman rank case, the construction in Theorem 3.1 has [Mat]] = I, so we can take Fiat = MM+ Miat E MMat) } which is evidently complete for MMe and has Eluder dimension 1, so Theorem 3.1 precludes statistical modularity with complexity comp.
Q' -irrelevant State Abstraction (X)
Latent class Miati Miat (S,A, Riat, Ht) such that there is a known state abstraction function Çaat : + Z such that (s) = (sat(s') implies that QMaar**ss = =Q Qu (8', for all a E A.
Latent complexity comp: We take comp(MMatt 8) poly |,, H, 1og(6-))) which is attainable by the OLIVE algorithm of Jiang et al. [JKALS17].
Statistical intractability (X): We take Miat { {Mat) } as the MDP class from the construction of
Theorem 3.1. 1. Let Qi = Q M Note that we have 1i (s, E {0,1] 1} for all 8, a, so we can take
latent abstract state space 2 {(0. 0), (0, 1), (1, (1, 1)) and state abstraction function Clat
such that (s)
(i,) if Qi 0)
and (s, 1) j. This satisfies the property of a Q"
irrelevant abstraction, since (Tat(s) Clat (1a(('))
(i, implies that (s, 0) Qia (s', 0)
and Qi (s, 1) = (s' = j. This has a constant-sized abstract space [ 4) and [A[ = 2. Theorem 3.1 precludes statistical modularity with complexity comp.
31

---

Linear Mixture MDP (X).
Latent class Mise: MDPs Mist = (S,A, Plat. Rist, H) such that there is known feature map Gaat = (Slat s', 5, + Rd such that
Vh E [M] E IR; Piat (s' s. (Glat, (s' | s, 0n)
Latent complexity comp: We take comp(M e, e, poly(d, H log((-1)) 1)) which is attain- able by the VCRL-VTR' algorithm of Zhou et al. [ZGS21]
Statistical intractability (X): We take Mist = {Miat) to be the construction of Theorem 3.1. Here, there is single latent model, this is trivially embeddable with (1at, s, P (s' 8, a) R', This has dimension complexity comp.
so Theorem 3.1 precludes statistical modularity with
Linear Q' (x).
Latent class Mias: MDPs Maat = (S, Piat, Riat, H) such that there are known features maps Qlat : S x A + Rd and 91st : S + I2 such that for all Miat E _Maat. there exists unknown parameters lq, Bv E IR such that QMun*(ssa (81ac(s),0)) 0v).
(s,st(s,a), 02) and VMaa** (s) =
Latent complexity comp: We take comp e, 8, = poly(d, H,, log((-))). which is attain- able by the BILIN-UCH algorithm of Du et al. [Du+21].
Statistical intractability (X): We take Miat be the latent MDP class from the construction of Theorem 3.1. Since there a single latent model, this is trivially embeddable with dimension 1, i.e. Theorem 3.1 precludes statistical modularity with complexity comp.
take Ciat a) Qiat (s, a) and (1at
(s). This has dimension d = 1,
Low State or State-Action Occupancy (V n. M E M) (X).
Latent class Miat: In the Low State Occupancy model, Miat {Mast = (S, Plats Riat H)}
is of MDPs such that there exists feature map GYat {Siat,h : Rd) S such that for
all π E Mar Miat E MMatt) and for all Miat EMaat> have
Wh [H] 30
dr
Aon. (s) (s), ())
For the State-Action Occupancy model, have that there exists feature map Siet { (Saathh S x A + Rd) k=1 such that for all E MMM | Mist E Mist} and for all Miat
Miats we have
wh E [H] 30 Maii;
df Mun (s (s, Munn
Note that the feature map does need be known in either case.
Latent complexity comp: We take comp(MMat: E, 8) = poly(d, (A), H, log Fiat/.E ,,og(6 (oog()-))
for the state occupancy case and comp(Maatt e, 5) = poly(d, H, logl Miathe loog(-0) Both are attainable by the BILIN-UCB algorithm of Du et al., since i) MDPs with this property have Bilinear rank bounded by d| and respectively (see Definition 4.3 and Lemma 4.6 of [Du+21]). and ii) one can construct the value function class Flat (QMast) realizable and has size log] Fiatl = liglMaat.-
Miat E MMst] which
Intractability: We take the construction of Theorem 3.1, which has [Masel and thus is trivially embeddable with dimension ie. we can take < (s) Mususss (s) and cQ (s, Mass (s, a).
Bisimulation (?)
Latent class Must: MDPs Miat (S, A, Piat. Riat, H) such that there is a known state abstraction
function (1at S - such that Clat = (Ia implies that Rist (8, a) = Riat (1, a) for all a E A as well Ex( (s a) Exieu(())= Pia (s' a) for all z'.
Plalss
32

---

Latent complexity соmp: We take comp comp(Maat,,E, 6) poly(12). H,= ",,,=,,,oggp (0og(()))))))) which is attainable by the OLIVE algorithm of [JKALS17].
Openness (?): x negative result does not follow from existing constructions, since the dynamics from the tree-based construction of Theorem 3.1 are not bisimilar unless | = [S), which allows for the application of tabular methods. the same time, positive result does not follow from existing methods, since it is non-trivial to extend existing Block MDP methods to use the bisimulation state abstraction a way that only pays for |||.
Low State-Action Occupancy (VT S A(A))
Latent class Miat: Mist = {Matt = (S.A, Piat Riat, } a set of MDPs such that there
exists a feature map G {Slat, 8 x A Rd H all Miat E Miat. we have
such that for all π (AA) and for h=1
wh E [H] 30, 30, Mai=
di
(s, (s,, 0
Note that the feature map does not need to be known.
We take BILIN-UCE algorithm of Du al., since i) MDPs with this property have Bilinear rank bounded by d (see Definition 4.3 and Lemma 4.6 of [Du+21]), and ii) one can construct realizable value function class of size log[F] log
6) = poly(d, H, logl Miatl, log (8 (6-1)), which is attainable by the
Openness (?): negative result does not follow from existing constructions, since the dynamics from the tree-based construction of Theorem 3.1 do not have linear occupancies for all S > (AA) unless d = JS], which allows for the application of tabular methods, and the dynamics from the bandit-based construction Theorem E. do not have linear occupancies for all π S - ((A) unless d = [A, At the same time, unlike the low state occupancy case, a positive result does not follow as it is unclear if we can express the observation-space occupancies linearly.
Statistical tractability with additional (suboptimal) -Aledeeenee (V): Note that can reduce to the Low State Occupancy case (V), since
d= (s) Σ (s, 0
CLc (s. EC
Σ
(0
However, this blows up the feature norm bound of the feature map SYa, (s) by a factor of [A], which will appear logarithmically in the bound obtained by BILIN-UCB.
Model class + Coverability (V S ((A)) (?).
Latent class Miat: Miat {Mar (S, A, Piat. Riat H)} is set of MDPs that all satisfy coverability with respect to all policies Tiat S + A(A), i.c we have
MIx.
WMat E MMas:
(cor = inf mEEA(SXA) KE[H] T A(A)
sup
sup
l
<
00
1hh
Latent complexity comp: We take comp 8, polyyCooon H. log Miatl, log 1) which attainable by the GOLF algorithm via the results of Xic, Foster, Bai, Jiang, and Kakade (see also Lemma F.3). We obtain this by noting that a realizable model class can be used to construct realizable value function class F and a complete value function class G sizes log = log|M| and log gl Ologg
Openness (?): A negative result does not follow from the existing constructions. The tree- ree-based construction of Theorem 3.1 satisfies coverability with C.ov exp(I((H) and the bandit-base based construction of Theorem E.1 satisfies coverability with Ceov [A]. In both cases, the lower bounds cannot be used to rule out statistical modularity with the above latent complexity. Similarly, unclear how to obtain positive result for the latent-dynamics class (Mat, 4)-
33

---

E.3 Proofs for Lower Bounds (Theorems 3.1 and E.1)
E.3.1 Main lower bound (Theorem 3.1)
We will prove the following result.
Theorem 3.1 (Impossibility of statistical modularity). For every N 2 there exists decoder class with | = N and a family of base MDPs Mist satisfying (i) [Miatl = 1, (ü) H S (Io)(N)),
(iii) [S] = X S N2, (iv) AA] 2, and such that
1. For all e, O, we have comp(Maat. 6, 6, 6 =.
2. For absolute constant 0, comp ([Maat D), ([(N/og((N))
Proof. Let N be given and assume without loss generality that it is a power of 2. We first construct the class of latent-dynamics MDPs, following Song et al. [SWFK24].
Latent MDP. The construction has single "known" latent MDP Miat so that the only uncertainty in the family of latent-dynamies MDPs we construct arises from the emission processes. We Mist {Maa)). Set H = log2 (Pg2(N) (N) + 1 and A (0, We define the state space and latent transition dynamics as follows.
The state space can be partitioned as S = St,,.,,
standard depth-/f binary tree MDP with deterministic dynamics (e.g., Osband et al.; Domingues et al. [OVR16; DMK )21)). There a single "root" node at layer h = 1, which we denote by ooo and N "leaf" nodes at layer H, which we denote by [Seett I jEjN' For each h ..... H 1, choosing action leads the left successor of the current state deterninistically. and choosing action leads to the right sucessor; this process continues until we reach a leaf node layer H.
Each block S corresponds
The initial state distribution P Unif (s/ott
N
root
Prott)
There are rewards for layers 1, H - 1. For layer H, the reward is
R (s I[j = i).
(17)
This construction summarized as follows. At layer draw the index of one of N binary trees uniformly at random, and initialize into the root of the tree. From here, we receive a reward of successfully navigate to the leaf node whose index agrees with the index of the tree itself, and receive a reward of otherwise.
Note that the total number of latent states in this construction is |S| = N |& N(2N 1)
Observation space and decoder class. Let us introduce some additional notation. For each block S let Sj == {s) jje[2= 1 denote the states in block i that are reachable at layer h, so that Si = / and S = ( (N We define X' so that | < 4NV2 and consider a class of emission processes corresponding to deterministic maps. Let E denote the set of cyclic permutations on N elements, excluding the identity permutation. That is, each o; E Σ takes the form
a; k + + mod for i E (1,...,N].
For each E, we consider the emission process
v (- 8/ (1)) II (o(t))))
That is, th shifts the index the binary tree containing s (1.)) according to a. Let = {vt 180|o 1o E}. Consider the decoder class
(0) ( v).
which has [ N. We consider the class of rich-observation MDPs given by
(Mist, T == {M' == (MMist, ).)) o, E E}.
(18)
is clear that this class of rich-observation MDPs satisfies the decodability assumption for emissions V
34

---

Sample complexity lower bound. To lower bound the sample complexity, we prove a lower bound on the constrained PAC M (defined over the space X)) and [0, 22 define
Coefficient (DEC) of [FGH23]. For an arbitrary MDP
inf sup (Bz~pl (m J²(]]] [ (M(( s ) dec P.TE((T) MEM
where (=) denotes the law over trajectories (æ1, 01, r1)...., (aH, ag, TH) induced by executing the policy in the MDP M, (T) denotes the expected reward for policy under M, and TM denotes the optimal policy for M. We further define
dec,(M) - sup dec (M, MM,
where the supremum ranges over all MDPs defined over X' and A. We now appeal to the following technical lemma.
Lemma E.1. For all e² 2 4/N, we have that dec, ((cc:(( M1a $3)2
In light of Lemma E. it follows from Theorem 2.1 in Foster et al. [FGH23] that any PAC RL algorithm that uses T episodes of interaction for I log(T)) S c-N must have E|J" (Tx)) - ( >
for worst-case MDP in M. where c' > 0 are absolute constants. This implies that any PAC RL which has E[JM (TT) JM (f) S must have T (T) 2 C.NN N and thus T 2 c. N/log((V).
Proof of Lemma F.1. Define Mot as the latent-space MDP that has identical dynamics to Mist but, has zero reward in every state, and define M ([ iat, id]) as the rich-observation MDP obtained by composing Maa with the "identity" emission process id that sets 2 8h- Observe that M and M', induce identical dynamics in observation space if rewards are ignored: For all policies n.
I पT. [(21, 01), .... (zH, ah) = = p=" [111 (IH, an) = -].
(19)
It follows that for each for all policies æ, we have
(T)
Di((( (T)) (1) MM.. id))) (T))
N
[H seaf
(.,0).1)
(41,
N
2
[
Slaaf
(2,0):))
j=1
N
TH
Sleaf
(w.()h)))
Sroot
(W2(0)
(20)
N
j=1
p
TH
Sleaf
G. 1
I1
S
(21)
since the learner receives identical feedback in the MDPs M and M unless they reach the observation
TH = Slea (V15).)) for some j (corresponding latent state s(2,)) in M'), in which case they receiver
reward in M but reward 0 in M. We now claim that for any q AIT)), there exists set of at least N/2 indices I, c [N] such that
E (T), S
(22)
For measures IP and Q. we define squared Hellinger distance by DR Q) = [(V -V) 19hheorem 2.1 in Foster et al. [FGH23] is stated with respect to e dec: (M, M). but the actual proof (Section 2.2) gives stronger result that scales with sup dec. (M, M..
35

---

for all i E Zg. To see this, note that by Eq. (21), we have
[M Bangy
S Bang
2
p
Steaf
0.0% 2
root
N
i=1
N
2
2
N
N
N
where the second inequality uses that Σ;=1 p
leaf
G. (3))
= roct S 1, as the events
in the sum mutually exclusive (and the event condition does not depend on t). We conclude
by Markov's inequality that P. Pi-unif([N]) [E [E [DA (T), M())] 2 4/N] I 1/2, giving Iy Z N/2.
From Eq. (26), we conclude that for all e² 2 4/N.
dec (M, N inf inf sup { (arp (M - (E PEA(IT) iet
Jr JM (T)
To lower bound this quantity, observe that for any index and any policy ni, we have
Jd (TT)) ju (x)
parlo
x
[ *
(wel))))) 8lef
21
Sroot
(#20)))
==1
1
Tpar
15 [2:
(0:0):0)
(w)()))
N
Sleat
Sroot
1p3,,x
ZH = (mpl))9
Sleaf
21 = Sroot
(,))()))
N
1
N
p.H
TH =
leaf
3 ())
I1
U3 root
where the third inequality uses Eq. (19). We conclude that for any distribution p.g A(II..
sup Empp (TTT)) s (
TcT,
Bimunif(TT) ExNp [ (TT..) Jas - (m))
2
Ex-unif(I
put.a
JH
leat
20
8ooot
N
1
RH
Sleaf
(00)
2
[_gl
as long as N 2 4, where the second-to-last inequality uses that for all j, the events {= = leaf
Ji = s (2] are disjoint for all i. Since this lower bound holds uniformly for all q.p E ATI), we
conclude that
1
dec (K,M M) 2
E.3.2 Proof of alternative lower bound (Theorem E.1)
We will prove the following result.
36

---

Theorem E.1 (Alternative lower bound). For every N 2 4, there exists an emission class v and decoder class with / / -N and a family of latent MDPs Miat satisffyng (i) |Maatl (ūi) H = (iii) |S| = | = N, (iv) |A| N, and such that
1. For all e, 5
have comp(M Mat E, 0. For an absolute constant c O, comp (omp(([Moo (MMa 2) c, 2 MNN/ log(
Proof of Theorem E.1. We repeat more or less repeat the same proof as Theorem 3.1, but with the appropriate modifications translate from the contextual tree-based construction in Theorem 3.1 to the contextual without loss of generality that is a power 2.
construction in the theorem statement. Let N be given and assume
Latent MDP. Our construction has single "known" latent MDP Miat; that is, the only uncertainty in the family of rich-observation MDPs we construct arises from the emission processes. Set Mist = (Mat). }. Set H = 1 and A = [M]. We define the state space and latent transition dynamics
as follows.
The state space can be partitioned as S = ,t,,..,,S" SN
Each block St corresponds to single state o with N actions denoted by a², E [N].
The initial state distribution Pl Unif(s' ....,
The reward function is
Rí (s a²) itj = =1].
(23)
Informally, this construction can summarized as a contextual bandit (with uniform context distribu- tion), with reward of 1 if and only if we play the action corresponding the index of the context drawn.
Note that the total number of latent states in this construction is |S| = N and the number of actions |A| = N.
Observation space and decoder class. We define X' = S so that | |S]. and consider class of emission processes corresponding to deterministic maps. Let E denote the set of cyclic permutations on N elements, excluding the identity permutation. That is, each 0, E takes the form
0; : k + k + mod N, for E NJ.
For each a E 2,, we consider the emission process
v/ (. s*) T. (.)
That is, 10 shifts the context s² according to a. Let v = ful a E Σ}. Consider the decoder class
-ー = (s + (0) (1)
w E v),
which has | N. We consider the class of rich-observation MDPs given by
(Mise, t == {M' == (Mist, ) a, E E}.
(24)
It is clear that this class of rich-observation MDPs satisfies the decodability assumption for emissions V.
Sample complexity lower bound. To lower bound the sample complexity, we prove a lower bound on the constrained PAC Decision-Estinn Estimation Coefficient (DEC) of [FGH23]. For an arbitrary MDP X7 (defined over the space X') and E [0, 21/2), 2efine
(e,, = inf sup [Em (Tx)) J (T)) Ex~g (M))) s=?}.
P.IEA(II) MEM
where M denotes the law over observations (I1, a1. .1.))))))))))))) induced by executing the policy in the MDP M, JM (πT) denotes the expected reward for policy æ under M, and Tar denotes the optimal policy for M. We further define
dec, (Mc) sup (M,
where the supremum ranges over all MDPs defined over X' and A. We now appeal to the following technical lemma.
For measures IF and Q, define squared Hellinger distance by DR Q) [(V v
37

---

Lemma E.2. For all E² 2 4/N, we have that 37 dec (M,M) 2 1 2.
In light of Lemma E.2, it follows from Theorem 2.1 in Foster et al. [FGH23] that any PAC RL algo- rithm that uses T' episodes of interaction for T log( S c- -N must have E[J" (Tx) J (+) > d' for a worst-case MDP in M. where e, c' >> 0 are absolute constants. This implies that any PAC RL which has [[J (Tx))
JM (a) S é' must have T (Tg 2 c- N and thus 2 c- NN lN). 0
Proof of Lemma E.2. Define Mat the latent-space MDP that has identical dynamies to Mat but, has zero reward for every state-action pair, and define M := ( id.) as the rich-observation MDP obtained by composing M lat with the identity emission process that sets 2h = 8/. In the rest of the proof, we use the shorthand t = v Observe that M and M1, induce identical dynamics in observation space if rewards are ignored, i.c. for all policies π X + (AA),
Ip- (11 a1) | = par .n ((11,a)) = -
(25)
follows that for each i, for all policies n, we have
Dî (A)
= D2((1 (1at (T)) (1( lat, (T)
p sbh(1), aı = a²) (i,, Io)
j=1
N
D1 = s4:0), 01 = a²)
2
j=1
N
2
p
01 a x1 = s Sw:61]
N
j=1
N
2
p
01 a (7 s
N
since the learner receives identical feedback in the MDPs Mf and M unless they play the action a1 = a² given observation æ = ( (corresponding latent state s¹ in M'), in which case they receiver reward 1 in M' but reward 0 in M. We now claim that for any q E ATI), there exists set of at least N/2 indices I, C [N] such that
4
E (M M())]]
(26)
N
for all i E Iz. To see this, note that by Eq. (21), we have
N
N
2
Ei-uni(([N) Exwg (M) S Exng
a1 =
a
07
(1)
11 =
N
N
j=1
i=1
N
2
2
S Exgnn
N
N
j=1
We conclude by Markov's inequality that P P (M( (F 2 4/N] s 1/2. giving I, 2 N/2. From Eq. (26), conclude that for all e² 2 4/N.
dec; (f 4b M) 2 inf inf sup Bamp ( (Tare) - n (T)
() (II) iET
T'Theorem 2.1 in Foster et al. [FGH23] is stated with respect to scp dec: (MM, My, but the actual proof (Section 2.2) gives stronger result that scales with sup dec: (M, M).
38

---

To lower bound this quantity, observe that for any index and any policy π, we have
N parto
1
Jan (T ( J (xz) =
[a1 a0 | x1 (
N
N
IpM
[a1 = a²)) | x1 = s
N
N
p
a1 = (077) x1 sbn
N
where the third inequality uses Eq. (25). We conclude that for any distribution p.g A(II.,
Emap
Jaa (Tr J -m)
sup 1EZ,
2 Binuni((Z,) ETTD [ (TAri) - a (T)
2 1 BiwUnif(Ig) puT
a1 (11)
I1 )/55
pR..
(00 '00
01 = 800 2
01 =
==1
IEI
as long as N 2 4. Since this lower bound holds uniformly for all q.p E A(II, we conclude that
M) M) 1 2
39

---

F Proofs for Section 3.3: Positive Results
This section dedicated our upper bound establishing that pushforward-coverabe MDPs are statistically modular (Theorem 3.2). We provide a technical overview in Appendix F.1, and provide a full proof in Appendix F.2.
F.1 Technical Overview:
Low-dimensional embeddings for pushforward-coverable MDPs.
The idea behind our positive result is to show that under the conditions of Theorem 3.2, it is possible to construct an (approximately) Bellman-complete value function class for the latent-dynamies MDP Mabs at which point we can apply the GOLF algorithm of Jin et al. [JLM21]. We achieve this via two technical contributions. The first is the introduction of the mismatch functions To, formally defined as follows.
Definition F.1 (Mismatch functions). For a decodable emission process xf* and decoder &. the mismatch function for Φ. I = [T S - ((S) is defined, for every h E [H], as the probability kernel
r (s 8h) = P (P.) (0n(zn) = s.
The mismatch functions allow us to express functions of the decoders latent objects, and we revisit them in the context of self-predictive estimation (Appendix A). For the present result, we show (Lemma D.7) that the mismatch functions can capture the observation-level Bellman backups for any function of the decoders. That is, for any Th ah, letting 8/2 = state, we have that for any fiat S x A + R and Φ E Φ:
denote the true latent
Min (fiat o (b++1)l(aa)) (2,, an) = [Tm (To..t+ V (sh, az).
(27)
That is, the Bellman update of fiat 0h++1 in the latent-dynamies MDP Moos can be expressed as a Bellman update in the base MDP Miat for a different (latent) function I 10,441 a Vya (9h+1) =
Eehn T 24h+11 (6/++1
81+1) max (a,1(%
However, the mismatch functions I& embed some knowledge of the emission process, and (with only
decoder and base model realizability) are unknown to the learner. Our second technical contribution bypasses this by establishing a new structural property for pushforward-coverable MDPs (Lemma F.1): there exist low-dimensional linear embeddings of their transition kernels which can approximate Bellman backups for an arbitrary and potentially unknown set of functions, as long as the set not too large.
Lemma F. (Pushforward-coverabl MDPs admit low-dimensional embeddings). Let M be known MDP with reward function r, transition kernel P, and pushforward coverability parameter Coush. Let μ {ua [ hee[H] denote its pushforward coverability distribution (i.e. the minimizer of Desimition 3.3) and F (S [H] + [0, 1)) be an arbitrary class of functions. Suppose that we sample W E +[1]]xx d as a matrix of independent Rademacher random variables, and define
(s( (s a) + Vd
W (PaC- (P((1ss,)/PM 2/2
E ER4+1
and
WJA = 1 1 Vd
W (1h 1/2 ()S+(())))
RRd+
.E8
Then for any Eapx E (0, 1), as long as we set
d 29 Coush log (16)F)HH-//Eappl
Eapx
we have that for all f E and h E [H), with probability at least 8: (s, a)) S apps TTfh+1
E En (clip th -T
I Cousn (10((( + 11) and ma 12 S 16 log(I + 11. We emphasize that the feature map e (vh h= is oblivious to F, in the sense that it can be computed directly from M without any knowledge F.
as well as max.,a,.llv.s...
We use this property, in conjunction with latent model realizability, to construct linear features that can approximate the right-hand-side Eq. (27), thus yielding an (approximately) Bellman-complete value function class for the latent-dynamics MDP M
40

---

F.2 Proofs for Latent Model Class + Pushforward Coverability (Theorem 3.2)
In this section, we establish positive results under latent MDP classes which satisfy pushforward coverability. We assume that every model in Mist satisfies pushforward coverability, defined as follows:
Definition F22 (Pushforward coverability). The pushforward coverability coefficient Cpush for an MDP M with transition kernel P defined by
Ph-1(s' s, 1(8')
Cussh (M)
max inf HE (EA(S) (
sup
(28)
The pushforward coverability coefficient for an MDP class M is defined by
Cpush (M) max Cpust( (M). MEM
Note that for any MDP M we always have
Ceov Trns) & (cuush(M))
(29)
where Coov is the state-action coverability coefficient (Definition D.3). Thus, an MDP with low pushforward coverability is also an MDP with low state-action coverability for all policies (upto dependence on [A).
We will show the show the following result.
Theorem 3.2 bechforwwar-coverrttee MDPs are statistically modular). Let Miat be a base MDP
class such that each Miat E Miat has pushforward coverability bounded by (uush(MMaa S Cpush Then, for any decoder class D. we have:
1. comp(M1at, e, 8) S poly(Cpush. IA, H. Migl e eoo (loo(0111) (0)88-)),, and
2. comp(K[Maat. $8,,, 6) - poushC [A|, H, Miat log b = (oog(='))) log|S)).
The proof comes in three parts. We will firstly show that MDP that satisfies pushforward coverabil- ity admit low-dimensional feature maps that can approximate Bellman backups (Appendix F.2. 1), then establish that regret bound for the GOLF algorithm [XFBJK23] under misspecification (Ap- pendix F.2.2), and then combine these ingredients (Appendix F.2.3).
F.2.1 A structural result: Pushforward-coverable MDPs are approximately low-rank
Our central technical result for this section is Lemma F.1, which is based on a variant of the Johnson- Lindenstrauss lemma and establishes that under pushforward coverability, feature class which satisfies an approximate form of Bellman completeness. We define the clipping operator via
define linear
clip == max (x, 03.
We prove the following lemma.
Lemma F.1 beinfforward-ooverbbee MDPs admit low-dimensional embeddings). Let M be known MDP with reward function transition kernel P. and pushforward coverability parameter Gpush- Let J = (1a) ( denote its pushforward coverability distribution (i.e. the minimizer of Definition 3.3) and F (S [H] + [0, 1]) be an arbitrary class of functions. Suppose that we sample W E [+1] dxS as matrix of independent Rademacher random variables, and define
(s. (s. Vd
W (Pal-1 (..1s,0)///1 122 cs
E Rd+1
and
1 W (1h (1) ()((())+1())
WfAh = 1 B
E Rd41
Vd
.8
Then for any Eaps E (0, 1), as long as we set
29 Coush log H6 E
Eapx
41

---

we have that for all f E Fadd h E [H] with probability at least 1 - 8:
E (unniiif( (clipualkws,. Vh a))l -Tsh++(ss,s S Eap::
as well as max aa (n I (16 (10( + 11) and max mall,all l1 I 16 H)) + 11. We emphasize that the feature map db (1h ) oblivious to F, in the sense that it can be computed directly from M without any knowledge of F.
Proof of Lemma F.1. Fix h E [1f], whose dependence we omit for cleanliness. We begin by verifying that, in expectation, (wy, ()(s, a)) is equal to T [s, a). For this, note that
(wy, (s))a)
1 d +
P(s' [3,0
= a)(
Σ
Σ EES
Wi.s
Σ W W (12"))"))
d
1l12(8))
i=1
P(s' 18,0)
= = + Σ
P(s' ss))
ΣΣ Σ
Wi.d' 12
W (32")
s'ES
1= s'ESS EEES
8"
Consequently, we have
P(s' 8, W.s''
(Tf(s,a) - (w,, =
ΣΣΣ E=1 FES EE s"ys'
12())) W Ws (s")((")))
(30)
Note that this remaining noise term is zero-mean we will show in the sequel that it can be made small by picking d appropriately. We next examine the norms of the vectors (s, a) and wy. Note that we have
2
1 d i=1
Σ
Σ YES
W.,
P(s ss
22))
Σ
(2 s,a)
1
ΣΣ>
Σ
W W. 10"" 12/2(8²) 2212
P(s' (181) P(s" s,a)
H(s²)
RES
sE E"ES 8'4s'
I Cpush
+
1 'ΣΣD
Σ
W W.s"
P(s' 18,0) P(s" (8,0)
(31)
d 11 S'
12 (2
8"45'
where we have used that
P2 13 s, < Cpush P 19,5(1800) 8, p(8))
Cussh
SEES
s'ES
by definition of pushforward coverability. Further note that we have
d
2
|| 112
1
Σ
Wi. W
d 2m1
s'SS
E Ex-nulffe (((')
ΣΣ Σ
W W. W... (33(61))(()))
S'ES
8"48'
S1 ΣΣΣ 1= EE
Wis W 22 (22(())))))) (2)
(32)
We will now appeal to the following technical lemma to upper bound Eq. (30), Eq. (31), and Eq. (32) by establishing that the Rademacher noise terms concentrate to their expectations. The proof of the lemma will be given in the sequel.
42

---

Lemma F.2. Let u, E R", and let W E {=1] have independent Rademacher entries. Then with probability at least 1-8.
32 log
(26
10011
64 lolog( (l0g((8)))) (33)
+EE :E|d JE[n) kein)
Wuyjer - 1|u112llu122
+ || 1
d
d
Furthermore, for any set of vectors V R we also have
max
ΣEΣ
Way Way
VEV
vEId) jE[N]
kE(N)
kØj
32 12g((20
|o112 64 log (26
s max NEV
(16 log| + 9)
maxluul1 DEV
max NEY
d
Let (s) E S x A and f E F. To bound (1b(s, wy) - -ff(s, (ef. Eq. (30)), we apply the first
bound of Lemma F.2 with u (P(s' s, s,a)/41 WES and = (s') ee which gives
32C push log
log Log(26-)) E(8-1),
(bb(s,)), TTfs,
64C
(34)
d
d
where have again used that l|ul|2 Evres
Cpush and also that || 1 since loo I for all f E F. To bound Eq. (31), we apply the second bound of Lemma F.2 with
(7())))))
m(s))
{
Ph (d Mh (00)
V
which gives
s.ESSAA' hx(M]
EES)
32 1ogg(28-1) + C2
64 log(26-1)
11, ax, z Cuush (1611gg 9 + Cpush
max 5,0ESxAAhEHH
d
push
d
Lastly, to bound Eq. (32), we take V = { (1) SEES
in Lemma F.2, which
JEF AE(H]
establishes that
64 log logooo2 (28-1) 32 1og(25-1)
|1 59+ 16 + SEF
max
+
d
d
Note that Eq. (34) establishes that the Bellman backup TJ(s, a) is well-approximated by (M(s, a), wy) only at single state-action pair (s, We can obtain an T approximmaionn guar- antee by taking union bound over S and A, which would incur a dependence on log SI in the final sample complexity. Here, we bypass this by instead requiring only approximation guarantee under the L2( @ Unif(A)) norm. Via (pushforward) coverability, this will ensure
that E= ((wy, (bs a)) - (s, is well-controlled for all policies म, which will be suffi- cient for our downstream sample-copllextty analysis of GOLF. However, directly establishing an L2(u @ Unif(AA) approximation guarantee is technically challenging since it would require establishing fourth-order (rather than second-order) equivalent of Eq. (33). The remainder of the proof will obtain an L2(μ @ (n)) approximation guarantee by instead sampling a dataset size from @ Uni Unif and taking union bound over that dataset to ensure uniform bound all atate-action pairs in that dataset. Via an additional concentration bound, this will ensure that the error is well-behawe under the L2( & Unifi (AA) norm.
For each h E [H), sample a dataset D = ((0)) a ( i.i.d. from pa @ Unif(A). By a union bound over n, F. and H. we have that
Vi E [m). f E F. & E [A]
(v (1) W.F.A) Te.ht (52, {m|[F)HH-)) (35)
where we recall the definition of e(-) from Eq. (34). Now, let
(x, = kehi a), wynh 2iii-Tofuaiee ())
43

---

Note that ( a)l I and
(8 a) S ((vh((, a), wr,n) ThJn+1 (8, a))²
since Th E [0, and the clipping operator is I-Lipshitz. Note that
((,.)) f, a)] = En ())) (clipjo.z (( (s. a), wy)) To (s. (s))))
where this expectation is only over the sampling of the data point (s, a) (and not the Rademacher matrix W). Let
X. == ( hh
By boundedness of (s, a) and Hoeffding's ' inequality, we have that with probability at least 1-d 6:
12g
X (4 $ 4V
T2
n
Taking another union bound over F and H as well as the event in Eq. (35) gives that
(og(2)F|H8
Vf F [
X E (A) [x),(s,a)]
s 4
(36)
and Vi E [m], EF, Nis. S (m)
(37)
recalling the definition of e(.) from Eq. (34). Then, re-arranging Eq, (36) gives that [clip]o.2 (1 an). wy)) Tnfn+1(sh,an))
E ((
(o((2)F188-))
Xi,f +41
12 F F H8-1)
S
+ +4V
(38)
We now conclude the proof by picking and d appropriately to ensure that the right-hand-side is bounded by Eapx, which will ensure the desired claim that
Ep ( (clip (W on), wy)l Tr.ft+ an)))] S Sapx
For convenience, we introduce absolute constants and c' whose precise values may change from line to line. We pick n 64 (o / Plugging this into (38) gives
(A)unir(A)
an), wy)] Thfa+1 an)) S (m(()1111)))) t (39)
Noting that < 128 F8 c
and plugging this into (Eq. (34)) gives
6o (16 1/aap))
128 log 16 1 / /
{(m|F(H1-1) <
G1/2 push
Cpush
(40)
d
Setting
d2 29 Cpush log (16 /Sapx)
Eapx
ensures that
2 (n. <
Expx
(41)
2
by Eq. (40). Combining Eq. (38) and Eq. (41), we get
(Kn, Bysunir(A) [clip (< un), wr)] To (8h, an))
Saxs
(42)
44

---

as desired. It only remains to establish the concentration results of Lemma F.2.
Proof of Lemma F.2. We establish the first claim. Let E [d] be fixed, and consider the random variable
2 = Σ Σ
WtS
JEM kØj
Note that B[Z,] 0 by independence of Wiy and Wi, for every j k. By Exercise 6.9 of Boucheron et al. [BLM13), we have that
16X²
Blex)(((AZ)) S
|
2(1 64| u 1 (A)
Since Z₁ independent, follows that
16A
log
exp
A
Zz
|ull 1o1
2(1 64 64
Hence, Σ Zi is sub- nam-Gamma random variable with parameters 16||u|
2| and
64||u||||||| 11 and follows from Equation (2.5) on page 29 Boucheron al. [BLM13] that for all e > 0,
d P
Z 2
|ulla|e//2 + 64| 21 Se
Taking a union bound, and using that the random variable is symmetric, we obtain the desired claim. We now establish the second claim. Let V c Ih be subset of vectors. Let i E [d] be fixed, and re-consider the random variable
Z; max VEV
Σ
JE[M]
[EE kØj
Again appealing Exercise 6.9 of Boucheron et al. [BLM13), have that
16X²
(gge(ex(AA22 - -E(Z)) <
E
max DEV
Σ
Σ
W WaN030R
2(1 - 64BA)
JE[N
kE(n)
16X2
< 2(1 - -64BA)
E
max wEV
Σ
j,k=1
16X²
max VEV
max|211
2(1 64BA)
where B = max
Since Z, are independent, it follows that
16X²
log E
exp
(Z. E(Z,1)
<
max weV |1
max/||/|
2(1 - 64BA)
Hence, Σ/= Z, is uub-aamma random variable with parameters c= 64 max,ev//lilllll and follows from Equation (2.5) on page 29 of Boucheron et al. [BLM13] that for all > 0.
16 max,evilullse and
P
1
Z
E[Z
+ max 1012 "E
132 d
+ 64 max "cV 10
se
d
1m1
45

---

To conclude, it remains only to show the bound B|Z,] I max. |ol V + 9). This follows by standard nog-sum-exp approach. Below, we abbreviate Pj == w. We can observe that for any À > 0:
E Z
max WEV
Σ
PiPkyguk
jEIm]
1
log
Σ BEV
E
exp
A E
Σ
PyPkyjju
X
jE(n]
REİN kテj
$
1
log
Σ
TF.
exp
A
Σ 1=1
n
(43)
FEV
Note that x= E, PyUi is subGaussian with parameter
=
||0113, since:
] = II J=1
22
E
exp
A Σ Pg
Elexp(Ap,ey)]
S II
exp
= exp
||
2
2
1=1
Then, it follows (e.g. Lemma 1.12 of Rigollet et al. (RH23)) that X E[x²] satisfies sub- exponential MGF bound with parameter 16/| i.e.
256 2
Elexp (A(X2 < exp
16
We also note that
n
E[ Σ
ven Blevey) 110112-
W/=1
Adding and subtracting E[x²] in Eq. (43) gives
log
B
TTexp(A (A(x² ||=112) + ||o|333]
NEV
log
(A 1 - cxp(Al|
1 log Σ exp cxp 1282 ||0111 \l
4K1a S 16 max, ||1112
log/V/ max 128 1 + max||e| e/
max,
||01
Picking À
16 maxx concludes the proof.
F.2. GOLF with on-policy misspecification
Consider the version of GOLF [JLM21] in Algorithm 2. We have the following guarantee for the regret of GOLF, which extends Jin et al. [JLM21] to allow for on-policy misspecification.
Lemma F.3. Suppose that Masi E and G satisfies Eapx Cap--completeness the sense that for
all h E [H] and f E Futt, there exists E Gn such that ET T/ r)² S 2 all HI = {Tg if F). Let Ceov = Ccov I1) (Definitiin D.3). Then for an appropriate choice of B, Algorithm 2 ensures that
Reg < H. VCoov F + HT / Coov log(T))
46

---

Algorithm 2 GOLF [JLM21]
input: Function classes F and G, confidence width 3 > 0. initialize: F t F, 1/ t wh E [H].
1: for episode - 1,,.....
do
2: Select policy क( x f(t,, where f arg magmaxeerrte f(11, (f11TT/((T1))
3: Execute 7( for one episode and obtain trajectory (x) ai rr")..... (T 18 1 (
(t)) 4: Update dataset: D/ + Dí U {x%² a Tht1) wh E [H]
5: Compute confidence set:
Fm + ={1EF: (Nnn (1tz))
min fin Jat1) S B vh E {m]
where (U,T)
E
-r -r d'EA
VS,l EF. ( -
max
6: end for 7: Output स = Unif(rumm)
Proof of Lemma E3. For each fa+1
E
Futh.
apx[Sa]
arg migming.. ming ggc supren E (gh Tnfn+za* Let
(+-)) x T154 & (1-)) (6 (1)) [px 1
I (c::);
and note that by Jensen's inequality we have that for all n. ET 1 (s <
1
0% (+ + Eapx
We further adopt the shorthand di (zx, a) = dh (z, a) and d (x, Eico di a), As a consequence of realizability (Qas, FR.) and approximate Bellman completeness, standard concentration arguments (proved in the sequel) lead to the following result.
Lemma F.4 (Optimism and small in nample squared Bellman errors). With probability at least by taking 3 F (()/8) + Teapx we have that for all i E (T),
(i) Qoenh E Fio, and (ii Σ 2.0
(z, a) 5/0 ()) 5 50()).
The rest of the proof proceeds similarly the analysis of Section 3.2 in Xie et al. [XFBJK23]. Namely, by optimism (Lemma F.4) and standard Bellman error decomposition (Lemma C.6) we have
H
Reg
B ge
5 (xx,
S TH Eapx
(8) 1
(xx, an)
h=1
Let us defining the burn-in time
Th (2, a) min(t)
di (2, 2 (2))
where μ4 is the coverability distribution for the set of policies I (i.e., the distribution μ4 that achieves the minimum in the coverability definition). Using the same decomposition into "burn-in phase" and "stable phase" in Xie al. [XFBJK23), we have:
T
E A=1
(x,a)
2HCoov +
Σ
Σ
(z, ( a)(
1=1
47

---

Applying a change of measure argument on the second term then gives:
T
H
(T( Th (2. a) ad) (,,, aj)
B
2 (2( SH
dh (x, a)
1=1
:=1 2,50
(A)
dh (z, a) (% ax)
By the same reasoning as in Xie et al. [XFBJK23), we have (A) S O Caov log(T)), and by Lemma F.4 we have (B) I OVBBT) Using that 3 = [o F1/6) + Te? gives the desired result. remains to establish the concentration results of Lemma F.4.
Proof of Lemma F.4. For any function f, define random variable
(h, f) (fn(sh ai - rh ( (ThJu+ - -hh (ntt(s/+22))
Let Bi, = {8f) af 1.....,88 : 0
100 Jict. Note that
B[r + 1n+1(1911 Br,e] = -E= [Tn](sh, an)]
(44)
and thus that
(h, 3r,n] =E (sn Tafa(shh
Next, note that
Var Var (a,h, f) Be,n] S B ((x) B1.
E
(fa(s]2 - (s a () 2 (fn(s) a. (s + 2 - ff+t
13aA
16 E. (Jn(s) / ( ())) B.A 16 (,, f) Br,.]-
By Freedman's 's inequality (Lemma C.2, Lemma C.3), we have that with probability at least - 6:
fx,(h,f) ((o,)->E((AAA E[,, B.n]] S 0 (
1og(1/0) Σ ((, S... + log(1/5)
S-CE
Taking union bound over [T] x [ F, we have that for all e, h, f. with probability at least 1 8:
Σ X,(h, Σ
(T
((f((s)) (s.n(sh,an))
(45)
isct
0
Σ (+)
(Jn(s)) Tafa(sn, Taf)(sn,a)))? +1 +1)
(46)
ist
where (og((F)HH/b)) We now show that
X(hh, s )x(0,_)))+++( + = 0(3),
(47)
K<
which will imply, from Eq. (46), that
Σ E
(Jn(onn and - Th att) =0(++))=0(0)
desired. To see Eq. (47), let
A Σ (apx(TT (s - (() () ,
(9) 1/ 100 (5
48

---

and then note that:
Xi,, = Σ (
(00 - shtl (s
(Thih (5% .2a%) - s (s/11))1))
KE
(hh (5 ( 1
10 11 (s)+1))
Σ [T [T ) T/e - - ( A.
Σ (J 0 - -/ - (+++2))))))
E a Th S ( A. inf on EQA iie
+B+AA.
where the second-to-last line follows from apx [hititll E and the last line follows from the definition of the confidence set. It remains show that A, S O(Te2pp + 4), which we do via similar concentration argument. Namely, let
(h, f) (apx(TTnn++1)00)) aa.)) r/h -Shti (+++)))))))= and note that, as before,
r/- - ( (Taff(Tff ab)) -
E (h,, Ben] = Batit) (apxx(Tnn+t1)(sn: - Thh an))
and
(Yr,,, Sr.n] S (6, f) Bt,k),
by the same calculation as earlier. Thus, by Freedman's inequality and union bound, we have that, with probability at least 8.
Σ ER0
Yi(h, f)
Σ ET ist
(Iap((Tn(++:l(<>)na)) (n
(48)
0o
B (aax([T.hh+1](s), an) Tn an))²] +
(49)
where (og((F) Recalling the misspecification assumption, this implies that
Σ f) S) (1ee +),,
for all h f. f, with high probability. This concludes the result for (tt). For (1), this follows identically to the proof of Lemma 40 in Jin al. [JLM21], since this only the property that Q* F.
F.2.3 Sample-efficient latent-dynamics RL under pushforward coverability
We conclude by combining the previous two results to obtain the main result for this section.
Theorem 3.2 (Pushforward-covertt
MDPs are statistically modular). Let Miat be base MDP class such that each Miat E MMat has pushforward coverability bounded by Cppush(Mapn S pussh- Then, for any decoder class t., have:
1. comp(M M1at, E, 8) S poly(Cpush. [A, H. logl Mistl log (5 (8)))_))))00 and
comp Miat 8,), < poly(Cpushs |A]. H. log log /b. = 1og(6-)), log(S)).
Proof of Theorem 3.2. Let M = (M w* (Maat 4) be the unknown latent-dynamics
MDP. Define observation-level value functions
F Ma o & Miat E Miat: & $).
49

---

so that Q = Min" E FF via decoder and model realizabilityy, and log Frn S log|/Mat Φ Consider any function class S {S + [0. 1]} and MDP Ma (Mat. Paa)). For given value Eapx > 0, setting d according to Lemma F.1 implies that there exists d-dimensional feature map RR++1 such that
de a) E Rd+1 such that for all é E L and h E [H], there exists We,
(cLiproall ( a), we,a -Tr (n= (s)1()
Busa (a))
aapx
(50)
where MMa is the pushforward coverability distribution for Miat- Moreover, the map şh is explicitly computed as a function of Mat by a randomized algorithm with success probability with no knowledge of the class L required. We consider the class
L = Too Mus (s,a)= (s) = Erols' (sQ ø Mist E Mast }
(51)
3'ES
where To S A(8) is the mismatch function for decoder & and emission vh, defined in Definition F.1. Note that L has size log/ CJ S log/Martll || and that we have
Th da Minit o (z, a) = Th Tf (I' (To,h+1 Mu (M)"")((())))))
by Lemma D.7. By Lemma D.1 we have that ( 27 | (1t coverability distribution for MDP Ma and
is the
Enug, ()nif())) (s) Bung, (f
Now, define
Gmanc (1x 1aippo..////mmm...... (0(x), w)] o 2 1w|l2 I 11 + Mog( |
Recall the definition of wy (for f S A 10, 1)) from Lemma F.1, and note that by the norm bound maxrec wy [1 < 11 + 16 log( Mhae |$| H) given by Lemma F.1, we have (x, a)
( (((x), a), We) E Gi for every e L. Next, note that by the norm bound max (l1//1 a)ll S (P
Cushh( 11 + 16 log([o((S)) ( given by Lemma F.I, we have every gA GMaa. satisfies lighll S cC1/2 push M1ae |
A| == B for some absolute constant c. Therefore, GMmr.h has size logl9M...hl S Ö(d log( B) + log| = Öd log((S) + log/ ( where the Ô notation ignores logarithmic factors of Cpush. |A|, MMtl and log / Define Gn, U... 9Man. which has size log Gn. < log] Mhat| + (Ō d log log((S)) + log] ()). Together, these results with Lemma F. imply that for all fn+11 Fn+i, there exists gn Gn such that
(9n an)
[TA fin (I (on,an)) )nn)
E Eysc a (A))
Eapx-
This, in turn, implies that for all Tobs E 1llm we have
E Tote
(on(ZzA an) (n))
[Th Sh+1 (1he, )a))"" Cpushl
since PArg, & Unif(AA satisfies coverability (Definition D.3) with parameter Ceav (Mau Irns) S Opushl |A] (Eq. (29)).
Then, it follows by Lemma F.3 that if we run Algorithm 2 with the classes F and G we will get
Reg S
M1at //Me:///00ooMMii///////////////0 log/ Φ
HT C Coush |A|2 (T)
< H CS Cushh |A|T Miat HTT log(C2 Uuuh M1at 2 /Eapx) log (()(
Eapx
+ HT |A|2 (Tg))
Formally, this requires standard covering number argument; omit the details.
50

---

Choosing Eapx VT to balance leads to
Reg HT VCB Cussh Mog[[[Maaa
log(Cpuss push M1at | log log((S))
+ HT3/4 Push (ogg)((())
S HT | (| | log(TC push Maal| log log(
which gives risk bound of
Risk 2 T1/4 H V (oun logg)//)@@///)))/)oCCCC push Mist ///2 log log([S))
Equating this to gives a sample complexity of
T = Solyy(Custh- A, H, log]/Msdl log// [l. = loo,l,,1111111 log log(
as desired. Note that we have not made much effort to optimize the rate; in particular, a faster rate likely possible by using the GOLF.DBR algorithm of Amortila et al. [ACK24], which improves over the GOLF algorithm under the presence of misspecification.
51

---

G Proofs and Additional Information for Section 4.1: Hindsight RL
This appendix contains additional information and proofs related to algorithmic modularity under hindsight observations (Section 4.1), and is organized follows:
Appendix G.1 contains the pseudocode and proofs related to the online representation learning oracle EXPWEIGITT.. (Lemma 4.1).
Appendix G.2 contains the proof for risk bound of the O2L algorithm under hindsight observ- ability (Theorem 4.1).
G.1 Pseudocode and Proofs for EXPWEIGHTS. (Lemma 4.1)
Algorithm Derandomized Exponential Weights (EXPWEiGHTS..D)
input: Decoder set db for /. 1, T do Get dataset h x (1/h (1)
for h 1, ...., H do For 4, compute
dh (on) x exp
- (((oa(ah)) + [a(
and set
1 (x) arg max IP
S ( (dx)(2)))))))))))))))))))))))))) s).
(52)
sES
end for
Return 2000 = (00h 1h=1-
end for
The main result for this estimator is the following.
Lemma 4.1 (Online classification via EXPWEIGHTS, DR). Under decoder realizability (6" E @), EXPWEIGHTS.DD DR (Algorithm 3) satisfies Assumption 4.2 with
Estelass (T) Ö( log]
Proof of Lemma 4.1. For each h E [H]. consider the realizable online classification problem where (1 dz."). for t0 chosen adversarially, and y 07 (x:")))) Consider the exponential weights estimator
th (Ø) exp
Eιlo( + on (
For every sequence (ar (0 Te these distributions satisfy the deterministic regret bound
Σ
Ego
(x))) + (x < 2 log 2).
by Corollary 2.3 of Cesa-Biande al. (CBL06). Taking conditional expectations over x. dg. and using Lemma C.3 gives that with probability at least 1 - 8:
Σ
E E8
ET
| oh
(xx) A (mn)
< 4 log |b] l2g
Taking a union bound over E [H] and summing over h E [ we obtain that with probability at least 1 8:
r
[ (o
(2)) + [[w]] 4H log 8/1 log 12g(221-1)
In this section, the notations O, 22, and ignore only constants and logarithmic factors of H.
52

---

Now, recall that at each time t, we define the improper decoder 3(e)
Oh via:
hh
(z) = arg max P 600 Sgg
(1) (0% (x) = s)
(53)
#ES
Let (1 (h")
P
10
h
(In) # 0 (2+))
Note that satisfies
T
11
T
H
E 10
E
[I (0 (In) # (Tx)]]
Σ
E
E
[
# 0% (2a)]]
1=1
h=1
(54)
T
H
E
(1)
(an. )1"))1-
(55)
(=1 h=1
By abuse of notation we also denote En (2h. 0b) = [ (3) * の² (x)]
We will show that
Va, t, h (2), 0b0) 20 (In+ 9h "h
(56)
from which we will obtain that with probability at least 1 - 6:
T
H
Regclass (T)
[1,0%
(IN) + o% (2x) < 8H log | + 16/ log 1og(2116-1)
1=1 A=1
Integrating the high-probability regret bound gives
EiRegciass (T) O(H (og(HH)))) ())),
as desired. Towards establishing Eq. (56), let us fix x and let smax denote the argmax in Eq. (53). There are two cases:
P 2000gg wggh" (0i Smax) 2 2.
- If 8max = o= (x), l(x, )/ 0 are done.
+ Otherwise, Smax # (z) and we have f(x, ) = 1. However, since (*(x) # Smax we have
(x)
(1) (x) + o (x) and so
Smax
1 f(x 01
10
Ngh (0) (0) (x) # o (x))
P 1/ ~ohh (9) (x) Smax)
2
2
P a ( (0) (x) (x) Smax) < 1, 2'
If Smax = (2), far, (10)
we are done.
Otherwise, Smax # o² dz(z) and we have f(x, /i0) 1. However, by definition of smax as the mode we also have
1 (x) =mmxx) 2
P e (0 (x) o
( m
so in particular we have
1
((, (2) = P o Agh
co (x) + (x)x))
(xx 11
2
G.2 Proofs for O2L Under Hindsight Observability (Theorem 4.1)
Theorem 4.1 (Risk bound for O2I. under hindsight observability). Let A1.G1st be base algorithm with base risk Risk, (K), and REPcLaSS a representation learning oracle satisfying Assumption 4.2. Then Algorithm I, with inputs T, K, 4, REPelass and ALG1at has expected risk
2K
E Riisk oss (TK) < Risk, (K) + Estelass (T).
T
53

---

Proof of Theorem 4.1. Let (6(0) 'y denote the decoders chosen by REPclass, and let pt) denote the distribution over decoders induced time from the interaction of REPclass: ALG and Mass Let aabs
(1.14) := lat (5.5)) T0th and Pans denote the distribution over (observation-space) policies played
epoch and episode k. induced by the interaction of REsca ALGiat, and Moss We adopt the notation -ia = *lat Piat p(a*+)) for the final policy output by AI.Giat in epoch / and (at, (x),, 0%
(t.K41), .hh p(. for the trajectory collected from that (observation-lever policy aaa o o0
We firstly note that by assumption, we have the guarantee
T K+1
E
ΣΣΣ
(c.) (5,60
(1.4)
I oh
(In) + 2% [c[[))]]
S (K + 1)Esttcaass
2K 2KEstclass(T) (T))
(57)
which follows by applying Assumption 4.2 to the distributions that
Poss
2k=1 (K+1)
K+1 Poos and noting
T
K+1
E
(0,k)
II
300 hh
(xx) + 0% (Zx))
K
pare
k=1
k=1
H
E
II
ph (IR) + 2 (2nn)
S Estelass (T).
(3)
Mas (Taat +) be the random variable denot- ing the risk of the final policy output by ALGist after K rounds of interaction with M when given feature & in any epoch t. For any ő X - S, let Eg denote the law over trajectories (af (8) (00)
Let Risk(K, ALGiat, 12, Mabs) = JM (T
.hh [k((K+ and policies (Mfat o [ generated after K rounds of interaction when ALGiat is given feature & in any epoch. (Recall that, for all of the above definitions, new instance of A is initialized at every epoch, so we do not have to specify which epoch is, only the current feature Φ). Finally, let G, be the "good" event
G. = {vY VK [K + 1), Vh [M] "1 of (1
Recall that, in any round t, ALGIat only observes the latent ("compressed"") trajectories (o) (2 aft m(t as history for choosing policies. We can therefore conclude that, when (ath o² (a)) for all l E [K + 1 E [H], the distribution over final policies Tiac chosen by ALGiat will be identical as if we had chosen o² as our decoder. particular, this implies
E
[T(G.) Ris,)Risk(K, K, ALGist, T00 MMass) Eg
AL.Giat, o" .M )
(K),
(58)
where the second line simply follows by removing the indicator function, recalling that (is E[Risk(K, ALGiat. )l, and using that Risk ALG1at, o², M = Kisk ALGiat Mise).
Then, we have:
1
Risk(K, ALG 80, Mahs)) ]]
E Riiska (TK))
E
E 2
T
pl))
1
T
E
g
E C pp))))
(KsK) 3 M
1=1
1
Bize -ptt)
E F [T--
T
T
T
Σ Risk. (K) + T
Σ P(-Gr))
T
T Σ
= Risk, (K) + T
P P(-G.),
[=1
54

---

where the first equality applies the tower rule for conditional expectation, the second equality applies linearity of conditional expectations and the upper bound Risk(K, ALG1st, z(0) .Mass) S 1. and the third lines applies the upper bound Eq. (58). It remains to bound the last term. Here, note that by union bound,
K+1 Σ
xppttt)) ET T0 # o (xf }
P G SE
Σ h=1
E
where have used that trajectory k in round is sampled from policy g(t,)) which is in turn sampled from p(t.A) Summing over t and using the bound Eq. (57) concludes the proof.
55

---

H Proofs for Appendix A: Self-Predictive Estimation
This appendix contains additional information and proofs related to algorithmic modularity under self self-prrdictive estimation (Appendix A), and is organized follows:
Appendix H.l contains the pseudocode and proofs related to the online representation learning oracle SELFPREDICT.OR OPT (Lemma A.1).
Appendix H.2 contains the proof for our risk bound of the O2L algorithm under self eeff-predictive estimation (Theorem A.1).
H.1 Pseudocode and Proofs for SELFPREDICT.ON (Lemma A.1)
The pseudocode for our self-predictive estimation procedure is given in Algorithm
Algorithm 4 Optimistic Self-Predictive Latent Model Estimation (SELIPREDICT.OPT)
1: input: Decoder set 4, Latent model class Miat. Mismatch-complete class Ciat. Optimism
parameter ?
2: Set / == 3 Con log(T)/T
3: for t= 1, 2, T do
4: Get dataset Di {a az
10. (0) . :
Maell-eeeeee 11
5: Compute
(M (00) arg
(1M8)
log M (1+11 (,(x"(),a
(MM,,))))
h=1 i=1
(59)
log (Ma(1 10 (%(2%))
('))
(M' (E
(60)
6:
Return 300)
(300
7: end for
Our main result concerning the SELFPREDICT. OPT estimator for online optimistic self self-predictiv estimation is the following. We recall our notation for the instantaneous prefiptrii error
A (Maac, (I) an) DA (M (d. (zx), an), ( (an, an)).
Lemma A.1 (Optimistic self- eeff-predietive estimation via SELFFREDDIT..OPT) Let Ihat denote the set of policies played by ALG1at, and Ccov.st Scov,st (M 1' Ilat) be the state coverability parameter on Mi,, over the set of stochastic policies I' o Hhat (Eq. (9)). Then, for any > 0, under decoder realizability (o* E ④), base model realizability (Miat Miat),, and mismatch function completeness with class List (Assumption A.2), the estimator in Algorithm 4 with inputs
&, Miat List, and y satisfies Assumption A.l with.
(VHCCcooss (AT MAnies/ssAA/
Est (T,7) =
Proof of Lemma A.I. We will firstly establish that the algorithm obtains low offline estimation error.
Lemma H.1 (SELFPREDICT. OPT attains low offline estimation error). For any 7 > O, under decoder realizability (&* E Φ), model realizubility (Mia E Miat), and mismatch function completeness with class Liat (Assumption A.2), the estimator in Algorithm 4 with inputs & Maat. Lrats and 7 satisfies
In this section, the notations δ and S ignores constants and logarithmic factors of: H, Ceorst, AA, T', and Mis Cise [|).
56

---

that for all t E [T], with probability at least 1 - 8.
x
Ex ()
[ (TT) and + +x-1 (Jatiniin (TTAS;E) jar (1
Ba 00
S OO (Maat
Liat Liat (HH8-
(61)
Given this result, we can appeal to offline-to-online conversions to establish the final result. Let Ceov C (M aat o 2) denote the (state-action) coverability coefficient in Mass over the set of policies 1hat o Q. Note that by Lemma D.I we have Crov,st (M Mhl o ②) = Ceou,st and therefore by Lemma D.4 we have (Mass Haa o b) I Ceov.st (A]. Let 1 > 0 be parameter (Miee((MMselllsas | |
to be chosen later, and Borr
be the offline estimation error
guaranteed by Lemma H.1. We abbreviate a v CCooH (T), EP H == Ex(0mp(t) E=T [-], and B
-E- E (pptt ET ET []) Then, we have:
Brld [As[M Kon) and +2 1 (TMM)) (
(sT (T))()))
H
T
Tio
+g-
Σ
Jddtir (TT - Jotee
(iT (TT70)))
1= h=1
t=l
c(HCoov)
H
T
Boln
" (00) and
1 + 2n
Σ
(M jor()) (TTT))))
S a
+
h=1
t=1
+ (HCoov)
where in the first inequality we have used Lemma C.7 with gh = AM(Mo, )00 and in the second inequality we have used the AM-GM inequality with parameter 17. Collecting terms, proceed via:
T
H
0n
B
An(M An)MM,,0')ana an) + +1 2220)) ( (MMG ) (11711))
2
2
+
(HCoov)
27
011
TBoot +H(COo)))
21
V log(T)T + HCcov.slAA)
Liat
where in the first inequality we have used Lemma H.1 and the definition of in Algorithm 4 (cf. Eq (59)) and in the second inequality we have chosen 1/vT to balance the terms and used the bound Ccov S Ccov.st Al. We convert to an expected regret bound by picking ó appropriately, which gives the final result. It remains to show Lemma H.I.
Proof of Lemma H.1. Fix an iteration t E [T), and abbreviate M7 = Mo and = 30 We follow the analysis of maximum likelihood estimation from Geer; Zhang; Agarwal et al. [Gee00; Zha06; AKKS20J. In particular, we quote Lemma 24 of [AKKS20], which in an abstract conditional estimation framework with density class states the following.
Lemma H.2 (Lemma 24 of Agarwal et al. [AKKS20]), Let D ((z be dataset collected with I; ~ pd (1 M1--1) and y; ~ f+( xi), L(F, = >i E(f, 9:)) be any loss function
that decomposes additively, f D + F be an estimator, D' be tangent sequence D' {T 7
57

---

sampled independently via I, p' (21:-11 V1--11 and 3s ~ f* (4). Then, with probability at least 1 6, we have
- llog ED exp ((((())D')) - - D) + log (1=(
(62)
For our purposes, we have that F= Mist o D. the data distribution is collected adaptively (for each E [D via T ~ p(),
(1) (0) 2/ 4 dh Man and hh 1 1+1 Maos( (- 1/y a.
For the loss
function L, we take
H
M (r on (4
O)
=
log
[M^ on (r ph+1 (3)
hm0 1=1
Min (TMHH)) -MM(MM)) (TM))
We begin by upper bounding the quantity - -L((M, (D), D) appearing on the right-hand side of Eq. (62), equivalently lower bounding T((M (D), D). Let us abbreviate V = J (म and
V = MM (TTM))) Towards this, note that
H
L( (D), = log M @n ( 0n xh
h=0 ==1
log Mobs(ri) pbh (3/ 2 ab)))
2 (V V*)
h=0 1=1
log [M, कn (rh 1 w/
h=0
H1
log [M o @/ . ) 2/ a
max
oo mi
h=0 0
(V
V*)
2
H
log( [M o (1 (1 1 2x)))
4=0
H
log log([M( 1h aa)))
max
[M od 00
h=0
(V* V*)
2
ΣΣ
log( [Mist,h o
2 a("))
h=0
H1
log((M ohI 0h (x o a).a)))
max Je
h=0
where the second line we have used Lemma D.8 with Assumption A.2 and the third line we have used the ERM property of M & together with decoder and model realizability. We claim that this implies
M(MM (D), D) 2 - Lintt $1H8-1 by concentration. Indeed, for each [H] i [t]. and [M' d' List Q let
(63)
M (r ( 2 a
IM od'l
log
i.h
2
[M o d' (/ 2x (1)
58

---

Applying Lemma C. we have that
Mabs(ri (rh) 9h+1 (2 h+1 [M' o (rh Sh+1 (2htt)) sh , )
2h )xa
log
Mabs (Th 1h+1 (1 1/ ah [M o ( 2 (2/t11 h
2 log Byrtimpee ET (1)
exp
log
i=1
log 15-
(64)
with probability at least - 6, where we have recalled that data is gathered adaptively according to T( plo, We now quote the following lemma from Zhang; Agarwal al. [Zha06; AKKS20J.
Lemma H.3 (Lemma 25 of Agarwal al. [AKKS20]). For any D ((2) and p.q E [X A())).
we have
1 -2 log Bu-D.y--((a)) exp (-2 (ogh 2 EEND [ x).p( =)]]
Proof of Lemma H.3. We include the proof for completeness, The result follows via the following steps.
-2 EEwD DowD.y-g((1) (sy( exp (-2 (-2 log(s(ulz1/ptulet)
-2 log E2 E D. VPlulzl/o(ule)
2 2 y (a) v V
D.
(vx: : log(z) I x - 1)
= EunD 12(1 - ---ye((lle) Vilevi//ie VPllle)//luae)))
EuwD DRi((( g( x))]
By Lemma H.3, we have that the right-hand-side of Eq. (64) is further lower bounded by
Moss (Th² (1 1/h ag.
log
[M ('I(" 1h+1 (2 x/1 )
1=1
E (10
BT
h 1Mooss
(.).
6666 a (2)) log (
1=1
log (5-1).
where the last line follows from the non-negativig of squared Hellinger. Taking a union bound over M' 0' Liat & and & [H] gives the desired lower bound in Eq. (63).
To conclude the proof, it remains to lower bound the left-hand side in Eq. (62). Here, note that:
__ (V-
log ED exp (((MM,)(D))))) +
2
1
M (77 Jntz (T(() 1 (09)
-olog ED
exp
log
Mr @n (1 1 (2 with a.hh
H1
Mobs #2+1 (2 10 a
log mpp(t) Bx(()
exp
log
2
[M Tn (ri)) B (1 2/60² a
1=1
(65)
59

---

where we have used that in the "tangent sequence" D' the current sample ( is independent of (ri) 20/ (++4)) To bound this term, again appeal Lemma H.3, concluding that
H1
1/ -0 ) Mi o 2% (r/ Pn+1 (= 2// an
Mass (rh pn+t (2++
E=
log E (opptt
exp
log
1=
H
Ex DA [M Ōn](En, an), in (I an))
h=1
Combining everything, we have:
2p00)~pp Br Di MM Tn (on, (In, + + -P)
- log [ + log
Taking an additional union bound over E [T], we have that with probability least 8:
( DA Ma Til (wn, an), Ia+ 1iMobs (In, an))
x- (Mi (TTA Jas (TArTO)) s [Mllo[(MMaalll(sss]] ")),
for all t E [T], as desired.
Corollary A.1 (Algorithmic modularity via SELFPREDICT.OPT) Under the same conditions as in Lemma A.I, and for any base algorithm ALGiat O2L with inputs T, K, D, SELFFEEDICTT.OPP and ALGiat achieves
K
E[Riskobs ([Riskos(TKK] S 01 Riskease +c2
sc (1) [1) + KH,
VT
for absolute constants cı, c2, cz. Consequently, for any ALGlat with base risk Riskbase (K), setting 7 and T appropriately gives
EjRiskobs (TK) & Riskbase (K),
with a number of trajectories TK = =Ö(K OkK5 3 sclA) sxlA (MM (|Maallaaall111//issaaaa.a.
Proof of Corollary A.1. The first inequality simply follows by plugging the bound
of Estself:opt from Lemma A.1 into Theorem A.1. For the second inequality, let A v HCCovvst A
The result follows by setting 7 s.t. c KIA332
Riskbase (K)) i.c. 7 C3 Risksce(R)) x²A231" (Riskou [K])= Then the result follows by direct substitution and by noting that 4 < 1 since
KH and T such that ^A Risk i.e. T Risk (Ky
Riskbase (K) -1.
H.2 Proofs for Main Risk Bound (Theorem A.1)
Our main risk bound (Theorem A. follows as a special case of a more general theorem (Theo- rem H))., which holds for algorithm that satisfies property we refer to as CorruptionRobust.co t-ness (Definition 1.2). We now state the more general theorem, postponing its proof (and formal definition of corruption robustness) until Appendix I.
60

---

Theorem H.1 (Risk bound for O2L under self peeficredetivve estimation and CorruptionRbuustness) Assume self satisfies Assumption A. with parameter Y > 0 and that Miat realizable (i.e.
Mat E (. Furthermore, let AI.Gat be CorruptionRobus (Definition 1.2) with parameter Then, O2L (Algorithm 1) with inputs T, K, $, AI.Gitt and sel has expected risk
K T
E bRiis (TK)) S1 Riskbase K) + c27 Est (T,7) + can (a² + H)
(66)
for absolute constants C1, C2, C3 0.
Our main risk bound (Theorem A.I) follows from the following lemma, which establishes that any A1G is CorruptionRobust in the sense of Definition I.2 for a sufficiently large cor- ruption robustness parameter. Below, for any POMDP M over state-action space S A, write (S a1:b.) for the conditional probability over reward Th and 8h-1 given Stsh, 0r:ks i.e. (8 01sh) = (r, 8h+1 = 81sh: 01:h).
Lemma H.4. Let M* be any reference MDP and M be any POMDP with the same state and action space. Then for any algorithm ALGiat we have
BM,.LG RRisk (K)) Sa MMM AAGGi [Riskas (K)
K H
+ C2 E J...M.LLUU
ΣΣ
[DA PR(MM)s (M on), Mr (s (ua)) m
Am
where C1. 02 > 0 are absolute constants. In particular, ALG1at is CorruptionRobust (Definition 1.2)
with H.
Proof of Lemma H.4. Let abbreviate ALG ALGiat For i E [K], let 70 denote the trajectory (of), aj (1)) (1)) OH (1)). Let P = "p'"". denote the law of {(T(), ,7")) under ALG in the true MDP M and Q = P.M. denote the law of { (I"))r(")) )>))) under ALG under the POMDP M. Let us write M*TT) and (TT) for the laws of trajectory t sampled from policy x in M M respectively. Let स denote the policy output by the algorithm after K rounds of interaction with the environment. By Lemma C.5 we have
BM ALG [JM (TM.)) - JM (m) S 3 ALG [TM (TTM)) JMM (T) +4D2 (PM,, ,LG PMM,AA))
By the subadditivity property for squared Hellinger distance (Lemma C.4) applied to the sequence T0, 7()) 118), 7(8), we have
Σ (PP((() ahi 1, your "), Q(7()) Miii mili 1) 7i2k fil f
DR (pM Auo..Ao)) < 7T ALL
(T(((((()) (1ak)) 12), Q(-(1)) (r ( 111)
K Σ
D2 (P(((() sTii -(an ((+(+) (eeaa ylore 1
K
7 M AALG
Σ
Di M ( ( (T((1))
1=1
< 49 49 M,ALG
E M
DiA Mt (sh, an), Mr (n a
h=
where in the second step we have used that (P (1:6)) (( = (w (())), 7(*+-1) since the histories are equivalent, in the third step we have used that the trajectories
gener- ated by the MDP/PODMP M* and M, respectively, in the fourth step we have again applied the subadditivity property of the squared Hellinger distance (Lemma C.4) to the sequence (81, 41, su, TH).
61

---

Theorem A.1 (Risk bound for O2L under self suff-predictie estimation). Suppose RePset satisfies Assumption A.I with parameter ? 0. Then Algorithm with inputs T, K, REP selspppp and Al.Gat has expected risk
K Bl (TK)) S 61 Riskaase (K) 027 T Fot (T,7) + ca7 KH,
for absolute constants çi2 C2 c3 >
Proof of Theorem A.1. This follows from Theorem H.1 as well as Lemma H.4, by taking 02 K2 and simplifying.
62

---

I Additional Results for Appendix A: Self-Predictive Estimation
This section contains more general result for algorithmic modularity under self-predictive estimation (Theorem H.1), from which our main result is derived as special case, along with associated background, applications, and proofs. This section organized as follows.
Appendix 1.1 presents: definitions for the ø-compressed POMDP and CorruptionRobus algo- rithms (Appendix I.1.1), statements for properties of the d-compressed dynamics (Appendix I.1.2). The risk bound for O2L under self self-predictive estimation and CorruptionRobustre (Theo- rem H.1) is given in Appendix 1.1.3, and statement that the GOLF algorithm is CorruptionRobust (Appendix 1.1.4).
Appendix 1.2 presents for the proofs for the properties of the o-compressed POMDPs.
Appendix 1.3 presents proof for the risk bound of O2L under self- seff-predictive estimation and CorruptionRobustnes..
Appendix 1.4 presents a proof that the GOLF algorithm is CorruptionRobust.
L1 O2L with Self-predictive Estimation and CorruptionRobust Base Algorithms
L111 Definitions: d-compressed POMDP and CorruptionRobustnes
Consider iteration k: [K] of epoch
[T] within O2L. Suppose that REPLEARN has chosen decoder @ e(e) X + S. Then, the latent algorithm has observed the data (4.
D
d , (x(((11)) collected from the preceding policies in the epoch: (ith) aat 6i (Line 8). Due possible inaccuracies in the decoder é, the dataset Ditk)) may not be generated from a Markovian process and must instead be viewed as being generated
{0 ), (e.) (1.))
Tat
from PODMP, formally defined follows.
Definition L1 (é- compressed POMDP). The o-compressed POMDP M induced by Mass and defined by:
Latent state space X
2. Action space A
3. Observation state space S
4. Latent reward functions Rabs, X A [0,
5. Latent dynamics Po X A A(X)
6. (Deterministic) observation function O₂ X - S defined by On(z) =dr(2).
7. Horizon H
Initial latent distribution
Pass Pabs(an (zo 0)
Note that the latent space for the POMDP is the observation space of the latent-dynamics MDP M and vice-versa; adopt this terminology because- from the perspective of the base algorithm, the observations 24, can be viewed as a Markovian (yet partially observed process) that generates the learned states d(Ix)) on which the algorithm acts. We write p MM ma for the probability distribution over trajectories (mn, 8b, Oh, Ih (h) in the (>-omppeessd POMDP when playing policy the POMDP's latent states, sn S are the observed states, and ag E A are the actions. We let E = E Mi.Fua denote the corresponding expectation. We write
Tatt Sx [H] (AA), where 24 E
Po.((sH+1 $1:k: a1:h) P $1:h- a1:h) and (r% s1:h. 01:h) PT (r% $14h a1:)) for the conditional distributions of next states and rewards given the first h state-action pairs, which are policy-independent. We also write M3 (rn, 88+1 81:4, a1:a) = Fo, 811,, a1.)) Po,
$1.b. (1:h) for the joint one-step probability. We will abbreviate (S ala)) = M (Tp. Sh+t $1:h, 01:h).
63

---

Note that for any Matt a. (sh+1 | bility kernel, which is equivalent to
sh, ah) is well-defined (Markovian, deeeeddd) proba-
Pmu (sh+1 9.h
8h, ah)
Σ
o. 1111h-1,.:.h S/h an ap.)
$1:h, a1:k)
(67)
Flat ES
PaLA(ON41 81ck, (1:h)) 8h,
(68)
Similarly, aah (rm equivalent to
8h; an) is a Markovian and policy-dependent reward distribution which
po (Th
8h: an)
Σ
Poi 11:k-1,011-- 8h, an) 81th, ama))
(69)
#ish
Es (rnn(rn (1:h:a1)) sh an].
(70)
Finally, we let
Ma (rh. Sh41 18h, an.)
E Mg S1+1 $1sk. a1:h) Sh, ah
(71)
denote the associated one-step model over joint rewards and transitions.
Our CorruptionRobustnee tness condition asserts that the agent-when observing data from the 609 compressed dynamics M -ttains a risk bound for Miat which is proportional to its risk when observing data from Miat itself, plus term that captures the degree of misspecification between M and Miat-
Definition I.2 (CorruptionRobust algorithm). We say that ALG1at is CorruptionRobust with parameters a and Risk if there exists a constant 6 such that, for any (Ø, M1at) E $ x Miat we have
E
My ALG [Risk(K, ALGiat, Maat]] c1 Riskbase (K)
H ΣΣ
+ a AgAALI
(0) (p)())
E
DR
MMat,h (n), M2 (SLA,
where we recall the definition of the random variable Risk(K, ALGiat, Mist) from Eq. (1), the expectation T. A. denotes the interaction protocol of ALGiat in the d-compressed dynamics Mt. and p denotes the randomization distribution over latent policies that ALGIat plays.
I.1. Basic properties of the @>compressed dynamics (Definition I.1)
We establish number of basic properties for the é-compressed POMDP and their relation to the self-prediction guarantee obtained by REPself:opt- These properties are proved in Appendix I.2. Firstly, we have the following change-of-measurr lemma:
Lemma I.1 (Change measure lemma). For any E
[0, 1]]. [H], and
Tiat E SS x [H] - ((A)), we have:
Tin E
[f(sh, an) E x (In, on)l.
(72)
The next lemma states that the kernels of the é-compressed POMDP are well-approximated by the (Markovian) latent model fit by REPseif;opt- We recall the instantaneous self-prediction
A (Maas (z) ax)) D MMa (#n), an)) H.M (n)):))):
Lemma 1.2
of the o-compressed dynamics), For any decoder c, base model MIa. and policy Tiat S x [H] (AA), we have:
8
H
Riot 0
DR Miat on), Ma. (S1sh) (1thh)
E Tia [| (Mas: ()) an)]- (73)
0
h=
64

---

Furthermore, we also have
E
D (MaMa (Sh, an), Ma an))
E oo [An (T,, an)l. (74)
A==
h=0
A corollary is the following lemma establishing errors between expectations under Maat, the model estimated by selfopt and those under the d-compressed POMDP M
Lemma I.3 (Simulation lemma). For any latent model Mist with Markovian transition kernel P latent policy That S [H] 7 A(A), and decoder & 4, we have that for all f: [0, 1]:
[[(sh) an)]
TiM Eg [f(sh, an)ll
Σ
[l[Past (rw,, aw) - P (ow, an levv
(75)
Wehh
and thus for any sequence of policies Tlat latent models M and decoders @ we have:
ΣΣ
E
Mi
[S(S,, an)] [S(8, an)ll
lat
(76)
h=
T
H
HVTH
E ogi())
[An(M (())) an)].
(77)
t=1
h=0
L1.3 Risk bound for O2L under CorruptiinRobustnees
We state the main risk bound for O2L under self self-predictive estimation and the above definition of corruption robustness.
Theorem H.1 (Risk bound for O2L under self- predictive estimation and CorruptionRobustnes)
Assume sePselfeot satisfies Assumption A. with parameter y > O and that Mist realizable (i.e. Mf.t E Miat). Furthermore, let ALG1at be Cor CorruptionRobus (Definition 1.2) with parameter Then, O2L (Algorithm 1) with inputs T, K, Tb, ALG and REP fo has expected risk
E (T S Riskkase (K) + C27
T opt +or (a +
(66)
for absolute constants C1, C2 0.
L..4 Examples of CorruptionRobust algorithms
In this section, we establish that the GOLF algorithm satisfies the (Definition I.2) with parameter a Rv K-1/2, This improves upon the rate that would be obtained by invoking the generic guarantee in Lemma H.4. We expect that several other algorithms can be analyzed a similar way, thereby leading to tight rates in the same fashion. We restate the pseudocode in Algorithm 5 for convenience.
definition
Let Miat = (Tlat: Piat) be given, and we let Qia = Q and Tist,nf a) = -attn Eor (s.aa) (s').. We assume that the algorithm has latent function class Falg which realizes Qi as well as a helper class Gaig which Tist complete for Falg-
Assumption I.1 (Tia completenee.. We have:
Qiat Falg, and TaatFalg S Galg.
For our analysis of GOLF, it is most natural to quantify the corruption levels in the following way.
Assumption 1.2 (Corruption levels of Miat and Mÿ). Let S be such that, for any sequence of policies lat played by the algorithu when interacting with the d-compressed POMDP, have
(1)
K
( an) - 1 (8h, an)) + Pist, (sn, an) ) P-(M) (sh, an) 1120
E
00 Fit
E.
E
(78)
65

---

Algorithm 5 GOLF [JLM21]
input: Function classes F and G, confidence width 3 > 0. initialize: F < F, 1 t wh E [H]
1: for episode 1= 1,,,- T do
2: Select policy कh x f(,, where f == arg magmaxeert- f(11, ((11)T/((zi).
3: Execute 7( for one episode and obtain trajectory (x) ai .f"),, ( 1.) ((1) 4: Update dataset: D/=" + Dí U {1x) a Ih+1) wh E [H]
5: Compute confidence set:
Fm + -[EEF(0H fi (1tz2)))) min fi" Ja+1)) SB vh E {m]
ShEBh
where (U,))=
E
((-,a)-r-mayy d'EA max M('' VS.J EF.
6: end for
7:
Output मे = Unif(rum))
We note that
K
(1)
Mist.n an), Ma (sh+ an) ]
B
DH
rep
A=
h=11
(b)
R
D2 (Mat,, an), Mr. (113) a1sh))
by the data-procedd kata-processing inequality (ef. Eq. (90) and Eq. (80)) and the inequality ||p- S (a 4). and thus CorruptionRobus onnobbsttnss bound in terms of Eeep implies a irrrruppioooobutteeess tness bound in the sense of Definition I.2.
Theorem I.1 (Latent GOLF is CorruptionRobust), Under Assumption I.1 and Assumption 1.2, Algorithm 5 with B = e(log (I 9 KH8-') + Erep), has regret
k
Mus (TM:.)) Mm ()) S o H / K log(
+ +0 KCoov log K K))=pp)
and consequently is CorruptionRobust (Definition 1.2) with parameters H3/22
CCoo log(K) and Ri skbase (K) = 0 CCo (1g((())))))))(((((()1
H VK"
VK
Corollary L1 (GOLF applied in O2L). Let us suppose that the appropriate assump- tions for the estimator in Algorithm 4 to have regret bounded by Estseir(T, (Lemma A.l) hold. Then, we take 7 =2 K K-1/2
O(VHCcouT ToV/HCoTTooCoCCo////// Mial/// and T R K4, and the bound Theorem H.1 gives an expected risk of with number of trajecto- ries TK- = poly (Cov,, H, loglMMatl log log]Lise)) 1/219, improving over the 1/e rate of the universal result (Corollary A.
L.2 Proofs for Appendix L112: Properties of o-compressed POMDPs
Lemma L.1 (Change of measure lemma). For any & E &, I E ($ x x [0, 1]] h E [H], and Tat E (S [H] - A(A)), have:
Tiat B
[f(s,, (8)) = E x (In,, an)].
(72)
Proof of Lemma I.1. Recall that Pr denotes the law of (In, Sh, an an)ne(H] in the e-compressed POMDP when playing policy Tiat For clarity, and to differentiate a random variable from its realiza- tion, in the proofs below we will use upper-case notation such as {SA. 8h, A ab, Xa = xn to indicate realizations of random variables in the POMDP.
66

---

Let ( a) pa (Sp, A, = a) be the marginalized occupancy measure for in the Φ- compressed POMDP My. We write dii dr Tom to:
The left-hand side in Eq. (72) is equal
E
FIe [f(sh, an)
E sES,aEA
in (s, (s)
Meanwhile, the right-hand hand side is equal to:
E [I o (2 an)l =
Σ sES,aEA
f(s,a) Σ
Ti (x,a).
mid(n)
So only remains to show that, for each s E S and a E A. we have (s, Exs(s)== dn d (x,a) a). Firstly, note that it is enough to show that Eanodon ( dn (sh), since dz (sh, an) (se
8%) and Exn on dino (1h. an)
En:ddcn)==s this, we have:
dh duuo (In) Φ(xx)) (as | (hh) Exnoblen)=ss Cha (xn). Toward
Σ
1u (xt)= (x)) = E
Σ
mua (1h-1, Pos,n /
1h-1; (h-1)
un:o(pA)= oo Th 2h-1,0h-1EXx4
Σ
h-1 (I
(Ih-1: a1-1)
Poss. Th-1; an ah-1)
-1 -
Σ
h-1 (Ih-1: a4 1 (Ø(In) = 8h 1h-1, Qh-1)
Th- -1-11
At the same time,
In (8n) = 1p
p (Sh = 5n))
Σ 2,
pru: (Xn-1 = =ē, 10-1=00)00 = P (Sh = 5h. X = T, An-1 = a)
n (N = F. A ū.) Pin (0(xn) = 1h-1, 1h1)
2,0
where in the second equality we have used the definition of the observation function 8). = O(rr) = 6(z)).
To conclude, it remains to show that for all h, we have:
d o (In, an) P (Xn = Ih, an)
We do this by induction. Again, note that it is sufficient establish d PAIM (X,, z1..
The case is clear. For the general case, we have:
go (IL)
Σ
Rin 4-1 (In-1, PPsssa 2h a1-1)
2h Ph-1-.h-11 -. ExX
Σ
Pat (XA, = 24-11 = a4-1) Pins xb- Op-1)
Th 1 IEXXA
Σ
pia (Xn 24 A aa-1)
24-1-4h-1X% 1XXXX
P (Xn. 2h X An-1- an-1)
= T -Xn Ihh-
67

---

Lemma 1.2
of the o-compressed dynamics), For any decoder o, base model Mia and policy Wlat [H] A(A), we have:
11
H
E [ Miat, an), (sin,, (51)))
TIM
5
E max 90 [ (z), an)]- (73)
h=0
h=0
Furthermore, we also have
H
H
Nlat
DH
Maat (sh, and, M (sh, an))
E
uun
[An (2), an)l- (74)
4=0
h=0
Proof of Lemma 1.2. We begin with the first event. Note that, for any Tats the PODMP kernel M a. (Th: Sh+1 = $1:h, (1:h) can be written as:
Ma ( (Th: 8h+1 = s 01:h)
Σ
Prim (rh. Sh+1 =
Th Ohe $1sfs a1:h)
Th EXXXA
PT (2h, an S1ch. a1sh)
Σ
Prta (Th, 8h41 = Ihn
I1n,, un) p (In, an 81:6, (1.));
where we have used M (rh, 81+1 = 81th; 01:h) Pmta (rh, 8h+1 = 81:h, 01:h), the law of total probability, and that 24, is a sufficient statistic for and 81+1- We further note that
pru (Th, Sh++1
Th, an. Mabs, (rh, (11+1)
Fh. an):
(79)
since 8h++1 Oh+1 (In+1) Φ (1++1) is deterministic function of #4+1 and Th Th+1 Ma an). Thus, for a fixed and f, and omitting the indices on the decoder & for cleanliness. the expectation in equation Eq. (73) becomes:
E
Taat
(rh, Da MMatt (sh, (Sh, an), Ma (rh, S4+1= = 81:h: eim))]
Σ
P a1.h)
Σ
pri (xn,
$1:bs a1:h)
2h
x DH
M Maat an), Pain (rh, 8h+1 = = 2b. an))
(Jensen)
Σ
(81hh a1 Prin (wp an (191
$1A.MIN ((SxA)) IN.
D4 Mirt an), Pam (rn,0(##+1)) Ih, 1m,aa))
Σ
patn (In, an) (M(a an), Mabs, (rh, ((1x+1) = 11h, an))
24.04 EXAx
(Simplifying Eq. (79))
ohc D2 (Misr an), M Mors (rh, 6(Fh+1) = Th an)))
(Change of measure (Lemma I.1))
Fu [Di (M ax), M (Zn, ax))]s
(By definition of (D
as desired. Summing over [M] we obtain the desired bound. The bound Eq. (74)
consequence of Eq. (73) and the data- puoc-prrcsssing inequality. Namely, using the definition of M M from Eq. (71) and the joint convexity of the squared Hellinger distance we have:
Di (Mast,h- sh, an), M. MA shy .n))
F
Di
MMattaa I 8h, an), Ma.a (: (11a,aa))) 8h, ah
(80)
68

---

Thus, we have
Thst DA
Mistn( Sh, an), Mohh" s/ sn))
- 1 E (DA Miaathl ( Shh an), Mann( 81sh ara)) s/s az)
E Di MMatih 8h, an), Mo,1( $1 a1))
as desired.
Lemma 1.3 (Simulation lemma). For any latent model Mist with Markovian transition kernel (Pitt,hheetn latent policy Tiat S x [H] + ((A), and decoder & D, we have that for all S:S x A [0, 1]:
[f(s)) an)]
Rlse [f(s), ax)ll E ||[PLst (aw, - out1 Pas, (Dw, aw [ev)
E ouo
(75)
Mich
and thus for any sequence of policies alat latent models M and decoders 6t), have:
B mat ((Sh,an))
E. (sh, an)ll
(76)
h=
T
H
S HVTH
E
(s)
ogt())
[M (xrn)[(
(77)
t=
h=
Proof of Lemma I.3. Firstly note that, from Lemma I.1, the left-hand-side of Eq. (75) is equivalent to
EE Maa [f([), an)] E Plat [f( an)ll IE Maa [f(s), an)] Tu () an all
(81)
For any S x [ - ((A), let d dott = MMa denote the occupancy in Miat and similarly for any Tobs X [ - ((A) let dobs, (1h; an.) dh
Mas Ta (In, an) denote the occupancy in
Mobs We overload notation by letting da (s, a) == ==E Jbss, (z, a). We will establish the stronger result that
Gatn (-) abssh
oe (1)l S
Σ b'ch
[il[Paat (IN,,,))) ddPa and llw]]
(82)
where the tv norm on the left-hand-side is over S A. Note that this implies the desired bound on Eq. (81) by Holder's inequality. We prove this by induction over For the base case (h = 0), we have:
Σ 53
Crua Ca 01) d (s1,
Σ
( (a1 81)
mis on (21.01) obs
$ $1.01
===0(1)) =
Σ
(8 (1) 81)
Pi (2) 0) (a d(x)))
$1 $1.41
Ii =1=0(a))= ==
Σ
(sa 10) di 1 (81 (0)
Σ mat(a1 81)
|| (ia,,(0))
$1 (
=
69

---

For the general case, let us further overload notation by letting doss, (sh) = Eas Labs (sh, an) and (ss æ4-1, ah-1) abs (Sh. 24-1, ah-1) Σzn L (2p Ih-1, ah-1). Let also abbreviate π Tiat Firstly note that it is sufficient to establish the result for C (sn) Joba, dabs, (Sh) since
Σ
da (sh, an) dess an)
Σ
(sn))((p) - Laae (Sw)
( (a sh)
ii ESXA
ah shi ESXA
Σ
Lat (8h)
dooo (sN)
Below, all summations over 9n (resp. TA) with domain unspecified are over S (resp. X), and likewise for summations over 5h, an or Zhy ap. We have:
Σ
(st,)(())) do0ss (sh)
Σ
di (st,
Σ
daraa (Ih)
Sh.
=n:0(zn)=sh
Σ
Σ
Tat, (8h-1, 11t11)1Paaattt (8h 0h-1,
Σ
Σ
Lobs. (In-11 ag Pabss
Ih-1, ak-1)
2h 2h:0(2n) ( =8h
The 18-11
Σ
Σ
( ag 1 Plath 1h-1,ah-11
8h
Fh-1 1h-1
doog (# Oh P Po 1h-1, a1-
2h-1
Σ
Σ
dath (8h-1, ah
Piot, 188 9h-1,an-1)
Sh
5h 1
Σ
goo obs, (0h-1, ah 11-)) 1( an))
24 1.hh1
Σ
Abss (2h-1, oh
((Fa-1).an-))
0h-1
Σ
goo obs 0h-1) ( x 1h-1, an-1)
2h-1 1hhm1
Σ
(Sh-1,
Σ
Lobs. (fh-1, Σ (lo 18-11, 0h-1)
5h- 1h-1
Th 2h-150 1 188
Σ
d obs, (- (h (sn 0h-1, - Pos, (8p (h-11ah--1)
1
dir (itthh-()))
obs (6- (1))
obs, (2 (z4-1, 04-11 Σ
(Plath (5h Fh-1, ah-1)
-r Ponan (Sn 1h-1 an-1)
Th-1 19--1
(1)
+ Too
|| ()(x ap a--1) 64PP abs (2 1 ah-1)
70

---

From which it follows that, for each h, we have:
(Tst.n()))
dooss (+b
(())
ETo
Piat Nl (sws,aw) +w obs (ahr, ax lev)
S
Σ WE(M]
E
||[ o (ow, aw) - -o- P (ZW an aw))lwy |lev]
1.3 Proofs for Appendix I.1.3: Risk Bound Under CorruptionRobustness (Theorem H.1)
Theorem H.1 (Risk bound for O2I. under self- seff-predictive estimation and cnr.uppiiooobuuteesss. with parameter 7 > O and that Mist realizable (i.e. Mist E .Maat). Furthermore, let ALG1at be CorruptionRobust (Definition 1.2) with parameter
Assume sel satisfies Assumption
Then, O2L (Algorithm 1) with inputs T, K, 2, ALG1st. and selselfoopt has expected risk
K
E Bliskabbs (TK) S C1 Riskbase (K) c27
Estsel (I, + can (a +H)
(66)
T
for absolute constants C1, C22 C3 >
Proof of Theorem H.1. Let us write "lst
(t.*+)) Mist and, for any k E [T] x [K + 1]. Tobs
Taat o (tt). Let Pobs denote the distributions of played policies Tobs
(G.))
(t.k)
(t.k) induced by the interaction
of ALGiat and RePselfoopt inside the O2L algorithm. Let write the online sum of self-prediction
errors as
T K-1 11 Σ
Tep
ΣΣΣD
E aas
(t.2)
rptle.k)
(6.k) T
[DR[[MM "h an), 0i S...EMMa.. (Tn, an))] (83)
h=D
Since the final output policy of O2L satisfies Mlst Uni Uni (nif( -.at:..... * (Line 12), we have
E[Riskabs (TK))
1
E Made (Totes)
Máss (f
T
We take the following decomposition on the risk
jM (7
JM (TTM
Ju (TT Mn()) Jo (IT (x())))
J (Tiat)
A.
+ J
(m(s)) (T]st)
Mas (Fobs)
(84)
B.
We will show that E
Ar
S TRegbase (K) + avT E[Erep] and that E
E B
2
VTH E(Erap], then return to the first term J (T J (IT miO) at the end of the proof.
To bound IE E Ar). we note that
E[A,] S C1 TRi TRisee (K)+
K
H
(t.b)
E
( (1,0
E
(000
DH
Mi (sn, an), Mr pon, (8ith, [mm)
M
Piat
1=1
h=
S ej TRi Srassk (K) +
E mupl
(5.k)
Tat (t.k)
ogi(t)
[IAn(Mia dies) (EE, an)]
T
K
H
< cj TRiskaase (K) (K)+avi)
(c.))
(5.6) E
The
[A ((r))
Tass
hm1
< cj TRiskbase (K) + +VVV+E/ss))
71

---

where the first line follows from the CorruptionRobust definition (Definition 1.2), the second line follows from Lemma 1.2, the third line follows by Cauchy- Schwartz, and the last line recalls the definition of rep from Eq. (83).
Maa lat(t) , be the
For the term Ei=1 Br, for any maat :S x [H] - ((A) we let Qiacoo = Th Q function of the latent MDP M Note that
T
-it opte)
[
lat
(lat
(85)
M $10 E
@ ) (s1,),)))1)) an)
E oplt)
[ "1 (
E op(1)
||||P!] (0') - 4P [1])
(by Lemma 1.3)
T
(0)) op((t)
|||[P0 int 1f an) - 6i0 4 (2h, an) an)lley)
1=1 h=0
S Erep:
(by
so it is enough to bound
(0 E og(())
2(t) (0th o (0))(())))))
Ja (#:00
Fix / and h, whose indexing we omit below for cleanliness. Note that, for any Tiat : S - A(A).
have:
(1QTT Φ), (2h, an) - Mid QTr ( an)) ']
(86)
< 2 2a
(Irist o) - rrobs.h) (xr,,, (m)n
(87)
+ 2 1 od
(EPmn(((aas)a)) (o (cs mass Ep. obs (on) [[ @ (1 matt]]
27
(88)
22
an) (Irist o Φ),, -robs.h) (In an) +
an) 11t11P1 s (Ih ar 11)
(89)
( [D (MMa..t i (#n, ax))]
(90)
where the final line follows from applications of the data-processing inequality (since Mist (Th, 8h+1 | (2x. an) = (ra Φn (2n), an) Piat,
@h. (a)())) 0%) and oh+1 HMM HMM (Th, 5h-1 The an) 13 The an (0)) i obs.A (Sh41 2h, ax)) as well as
the bound lpp gllev < (a(p.a) q). Summing this over t, h and using standard decomposition for
72

---

regret (Lemma C.6) gives:
20 E ogit))
Q2 Q Lorles
x0 h1(01,)1)) - I -a (F
H
2(1) tse
2 "1 (Inn, an) % Th Mass 2002 og11)
2(0
1Q Laste
" ( an)
o
(Lemma C.6)
T
H
(10 lart) o @p11)) (xn, an) - Th Tyylfan 212
27
S <VTH
E balloo(1) opl()
(Q o x00) ( (oh,, anh)
h=1
T
H
S <VTHH,
E the ogl(
Di ([ [Miet o o (oh, az),
1 1..1 obs, (1h,,
an))
(By Eq. (90))
I H4THErep
Returning the decomposition of Eq. (84) and combining everything gives:
E E[Riskobs]
S
1
Min (TMia))
J (IT (MM
|]
1 1 T
(avT +AVTH ElErep]
T
c1 Riskbase (K)
1
[(TTT) - - Juhil (ITA() + g0rp
7- 3 (OVT (oVT++VTH)) +
T
+ c1 Riskbase (K)
2K S Est (T,7) + 27 2- (a² + 16H) + c1 Riskkaase (K),
T
where the second inequality follows by AM-GM applied to the middle term and the third inequality follows from: i) Jensen's 's inequality, ii) Assumption A.l applied the distributions
Pobs K E (t.2), iii) the bound K K+1 S 2K, and iv) the inequality (x++)) < 2(x2+ O
1.4 Proofs for Appendix I.14: Examples of CorruptionRobust Algorithms
Theorem I.1 (Latent GOLF is CorruptionRobust). Under Assumption 1.1 and Assumption 1.2, Algorithm 5 with B c(log (i GHH- + Erep), has regret
K
J (M J Mua (T (T)) < 0 H /Cov K log log( (01((119)H/55)
+ O V KCeovv log(K)) K) Kppppp
and consequently is CorruptionRobust (Definition 1.2) with parameters H3/2 V log( and Ri Rksase (K) o (11
H VK
loo
Proof of Theorem I.1. Recall that the agent is observing data from the d-compressed POMDP M and thus the datasets of the form ((A)) ((4)) (db(2) a r (2259 M= For any
(
Tiat E That we define
Ten f(h,, an)) a. (sh, an) + +E,,, E (f an) [f(')], 8, (a)
where The t. and As consequence, we observe the following misspecification guarantee for Tiat
Tm are the policy-dependent Markov operators defined in Eq. (67) and Eq. (69).
73

---

Lemma 1.4 (Misspecification guarantee for Tiat).
E !!!
[Tiachh((ss on) T fsh )n)) S (E)p))
Vf: -x [0
Proof of Lemma 14. Follows from Assumption I.2 and the definitions of (
d.h and Tlttk-
We begin with the following lemmas, which will be proved in the sequel.
Lemma L,5 (Optimism), For the choice of 3 in Theorem 1.1, with probability at least - 6, we have for all & E [K]:
Qiat E FF())
Lemma I6 (Small in-sample squared Bellman errors). With probability at least 6, we have that for all k E [K], h E [H], and f E F(W;
k
(1) Es
27 (s(sn) (n) - -Toh [8h, and) ) 5O(B).
Let us write d == (N) Φ. Let us introduce the shorthand abs,k the occupancy for M and also the burn-in time
Ek= obs,h where dobs is
1 p (x, a) 2 (e,
(x a) = min
Let us recall, from the analysis of [XFBJK23], that for any h [H] and : x A - [0, 1] we have
K
E
(N)
an)(k < (sn, an)M $ 20cov
(91)
as well as
(1 (x. ()T(k 2 a)(
< OHHH
(92)
700 (z, (z,a)
74

---

K
1f
Σ Min (TT) JMn (T)
Julaa (6)
(sh, an) f an)l
k=
b=1
(Optimism (Lemmaa I.5))
K
H
())
Es
(f T an) + 3 Ke
Jm
(Simulation Lemma Lemma L3)
K
E
(
[[ T @) a,)] + 3 Keepp
(Change of measure Lemma I.1)
K
H
E [[ - ( o (
an [ 2 Kn (x 4HH
k=
h=1
+ +2H cov + H2/22 V KKepp
(Burn-in time Eq. (91))
K
H
Ex (f(t)) Tan f( @ (In, an IIkk 2 KN (2h, an)
k= h=
(1)
K
H
E (1)
[ f(h
[ (4)
Titt o o (I (In. an)
1=1
(1I)
2HC + H3322
V
Keepp
Note that, by change of measure (Lemma I.I) and the misspecification guarantee (Lemma I.4), the second term is bounded by:
(To. f(v ( an) S KHe
E
Turning to the first term, we have:
E
(k) ahe
[[rFu]
dhh f(m) o6) (on, Ink 2 (n(
(93)
1
Amm
H
K
(df
(K) te
(I, a)lk 2 a))
H K
(110) -F fro) o o) (In, an)
E
gay
(x,
4=1 ==1k=11 2,
h=1k=1
(94)
H K
(fFm)
Tnlts) - p(a) o )) (xn, an) 0.
< HC (K)
E (bt)
A=1
(coverability potential Eq. (92))
H
K k-1
xx()) Es
27 (Foo(s) - -50000 (00 ans) )"]
HC log(K),
Σ
(change of measure, Lemma I.1)
<0 H1 CcoyKlogg
V log(K)3)
(95)
75

---

where we have used that, from Lemma 1.6, we have:
ΣΣΣ
Bs (
(sh < ((HHK).
This gives an upper bound on the regret of
K
J Mux (IT
John (T(*)) S ((H H3/2 / KETp
Using that 0 [[10)1K) Erep and simplifying gives
J Maa (TTm)) Muc (x (x) S o Ceev log(K) log(( H + +0 ((111 V |KCool 1og(
as desired. It only remains to establish the concentrations results.
Concentration analysis. We establish the concentration results of Lemma 1.5 and Lemma I.6.
Proof of Lemma I.6. Let
(R (h, f) (fh a
k/ fn+1((h44)) -(T fn . -r (1+1(6
Let Sa. {s (6) r ....,
j0 (2) ( Note that
H TH
E [r (n) + f1+11(hh411
[a.A] = r/ (2) + fa+11 (/t1)) [50]
E [ + fn+1(s ($11)
(4)
sh a
(6) (2)
(0) [00]
E Tox (M) f(sh tm (x)) T(
Es
To f(sh,
and thus that
(+(
(n)) -Fx an)
1 3x.N] = Es's
Next, note that
Xar|Xu(h,,)) f) Ba,n] S (Xx(,, B3.A
$ 16E (fu(s (1))
aa) (a)))) -oal fn(s%h fn(o/",.f))) ) Bunn
16 (h, f) Bk.n)-
By Freedman's inequality (Lemma C.2, Lemma C.3), we have that with probability at least 5:
I xx((h,) Σ E(,,(,, Ba.N] $0
(1B5(100)
Σ E[, f) Br.a] + log(1/5)
ESC
tck
t<c
Taking union bound over [K] [H] x F, we have that for all ki h, S. with probability at least 1-
(1))
[faaen 7x(0)) fn fn an)) 21
Σ
X,
(96)
ick
t<
0
Σ
T Es
[faloh (oi)-Try -Tx(h)
- fn(sn; / +1)
(97)
where log([ log((F)HK/8), We now show that
Ex,h, f(0) < 3 S Cevepp+2 +1)
O(3),
(98)
76

---

which will imply, from Eq. (96), that
[Fa(ssh, an) - - fn an))) =0(++))=
Σ E
tck
as desired. To see Eq. (98), let
A [ (sh2 a - - fhit (2) -Tx"" 1h ( an r/ Sh (s
and then note that:
(6 2/ r- Jh41 (6
(To
J/ (s 0/ r/ 5h -
tic
(8h
(2)
S141 (1141))
tck
Thath
(1))
(8
0
(1)
10 1ht (ntt(((+1)) +
( (8h 0h - Sh41 (
(1)
t<c
inf g
E(g(s
a
10 ((t) 1 (1 )) A
SB+ AK.
where the second-to-las line follows from F C G and the last line follows from the definition of the confidence set. remains to show that A S (Erep + t), which we do via a similar concentration argument. Namely, let
(h, f) = (Tin a - rhh - -h -h
(s/+11) 2- (Tx
(Tr) (0) fn(s% ag rh 1 (=2((8(22)
and note that, as before,
J( Bcnk] = F (TaTaaaa) -/"0" sa(sn, ((a"nnn )
and
Var[Y:(h,,]) Sr,n] (6, Se,,),
by the same calculation as earlier. Thus, by Freedman's 's inequality and union bound, we have that, with probability at least 8,
1 (Tist (n)) -Fx an)
Σ
f((
ES tck
(99)
x(4) E
27 + +1) (Trech(oo, an) -F(e)) fh a an) anl))
S
Σ
(100)
tCk
where = (HKK)) Recalling the misspecification assumption Lemma I.4, this implies that
vohh, (Erep + 1),
tsk
for all h, J, k, with high probability. Applying this to f = (0) concludes the result.
Proof of Lemma I.5. We use similar arguments to the preceding lemma. Let Qiat. = Vidaan The aim is to show that, for all h E [H] [K], g E G, we have:
Σ (g(3 (1 r/e
Qist.A41 (s
(Qisun(sh) a (0) (5 -9,
77

---

from which the conclusion will follow. We show that
Σ bck
(g(sh (2) a22) Th - Qiat,hhi ( (8h+1))² - (TØ (0)
(0h )) -rhh (iat,o()/11) 22- -3/2,
We(ho))
(101)
and also that
(o - -hh - Qiath (ohtz))² (
(Qine, ( r/ Qiet, Qiec, (x)+1)) 2 -3/2.
ACk
(((A))
(102)
For Eq. (101), note that
x((")) (snns)) an) -Toih Vist, (ise
gh, Fi,N) EE
(103)
and that Var (h, g) FL,N - 16, Fuul- By Freedman, this gives
Wi(h,g) >
B[W.(k,,) Be,n 00
Σ ElW.(k,g) [Fa.l] +
1<k
$ 2
B[W,(h, FF + -O)),
or in other words
Σ Wh(h, 9) 2 tek
Σ B(Wa(h.g) 3..A - -0() t<k
2
using the non-negativity of Eq. (103). For Eq. (102), note that
(Tua.nlist. - -ooh Viath
27
((V Se,nl = EEg
2 Erepp
(104)
and that Var[Va(h) Br,n] < 16 (*((1))
(Tatth - -Tat Qisth))
By Freedman, this gives
Vihh
Σ (V) Bann]
(105)
Σ tck
(
Re
x())
(Tastiistnn (n) -T 0. Vi (8h: (B).))))))))))))))) ) +
(106)
= OErep + 1),
(107)
or in other words
Σ v1(1)
Σ B(Va(h) St,A] OlErep + -O (),
tck
where we have used Eq. (104).
78

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All results this paper are of a theoretical nature, and the stated contributions the abstract and introduction are given in precise, formal language.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All results in this paper of theoretical nature precisely state the conditions under which our results hold.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't I acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
79

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Each theoretical result is stated with all necessary assumptions and is accompanied by complete (and correct) proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (c.g., with open-source dataset instructions for how to construct the dataset).
80

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.- to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines guides/CodeSubmis ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurlPS code and data submission guidelines (https: cctppppssccpbpcc/////cccc guides/Codeeubmii ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
81

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1 I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [NA]
Justification:
The paper does include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics /tteui//neurips... http:///s.cppoooo///ccciiiiieele
Question:
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of Etichs.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
82

---

Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Question:
Answer: [NA]
Justification: This a primarily theoretical work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point that
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
This is purely theoretical work, and as such poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not existing assets.
83

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g.. CC-BY 4.0) should included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papersw thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does involve crowdsouring nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
84

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
85


Reviews:
[{"review_id": "j9uNAQD6MP", "reviewer": "Reviewer_U7JX", "summary": "This paper considers theoretical aspects of reinforcement learning in a certain class of MDPs whose observations are governed by a separate, potentially smaller, MDP. They formalize this class of MDPs and denote them latent MDPs. The authors then consider when such MDPs are statistically learnable, beginning with a negative result: they show that in general, even with known latent dynamics, statistical modularity is impossible. They then highlight that statistical modularity in this setting is in some sense distinct from previous works which assume regularity in the value function, and mention that this is because this structure might be useless without a good learnt representation. The authors then go through a laundry list of MDP formalisms in previous work, and provide for most a result on whether or not they are statistically modular. They finally consider algorithmic results, and introduce a 'meta-algorithm' which balances representation and RL learning (where the underlying RL algorithm is arbitrary). Under some additional assumptions, they prove that the additional representation learning adds sublinear risk.", "questions": "- Do you believe there are any toy experiments which can be done to illustrate any of your results?", "limitations": "They discuss avenues for future work, and are clear on the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- I believe that this is an important step in bridging RL theory and the issues of RL in practice. \n- Balancing representation learning and standard RL learning is an important issue many RL practitioners need to balance. This work paves the way for theoretically-guided answers to those questions. \n- I found it rather interesting how the authors demonstrated that much of the structure used in previous work is not amenable to this setting, and that in those cases statistical modularity is not possible.", "weaknesses": "- Assuming that latent states can be uniquely decoded from the observations is a rather strong observation.\n- There are no experiments in the paper. Of course the contribution of this work is theoretical, but theoretical work can still benefit greatly from some simple experiments which illustrate results in their paper. In particular, doing this allows some readers to better understand the result, and importantly, shows that the results obtained (which are often under unrealistic assumptions) do not break down in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n > Assuming that latent states can be uniquely decoded from the observations is a rather strong observation.\n\nIt is true that this imposes stronger assumptions on the observation-space MDP (i.e., there is no partial observability). However, this assumption is well-established in the line of research on Block MDPs and RL with rich observations and permits the design of computationally/statistically efficient algorithms in various cases (e.g. tabular latent MDPs), whereas the analogous POMDP setting would otherwise be intractable (see, e.g., the lower bound in [Krishnamurthy et al., 2016]). Our work addresses the question of generalizing the aforementioned positive results to general latent dynamics, which had remained largely unaddressed, and one of our main contributions is to show that, despite the seemingly nice structure of decodability, strong *negative results* are present. These also imply negative results for the setting *without* decodability. Thus, for many interesting classes of latent dynamics, one cannot hope to remove even this decodability assumption (without placing alternative assumptions). Nonetheless, we hope that by addressing the decodable setting, our work can serve as a starting point toward building a similar understanding for partially observed settings.\n\n> There are no experiments in the paper. Of course the contribution of this work is theoretical, but theoretical work can still benefit greatly from some simple experiments which illustrate results in their paper. [...] Do you believe there are any toy experiments which can be done to illustrate any of your results?\n\nWe acknowledge that experiments are an important next step for our results. However, let us emphasize that we believe our theoretical contributions alone are sufficient for publication, and stand on their own merits. Indeed, as is typically the case with theoretically motivated algorithms, developing practical implementations will require non-trivial adaptations and significant implementation effort; given the scope of our theoretical results, we believe it is appropriate to leave a full-scale empirical evaluation for future work. \n\nRegarding toy experiments: a classical toy experiment considered in prior works (for the latent tabular setting) is the “diabolical combination lock”  [Misra et al. ‘20, Zhang et al. ‘22, Mhammedi et al. ‘23], which consists of a small latent combination lock with very high-dimensional observations and which traditional deep RL algorithms fail to solve. For future experiments, since our representation learning oracle allow for sample-efficiency under much more complicated latent dynamics (beyond tabular), it would be interesting to design and test our algorithms on a more complicated version of this domain, which would be unsolvable by both deep RL algorithms as well as prior theoretical latent-dynamics algorithms.\n\n**Refs**\n\n1. Krishnamurthy A, Agarwal A, Langford J. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems. 2016;29.\n\n2. Misra D, Henaff M, Krishnamurthy A, Langford J. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. InInternational conference on machine learning 2020 Nov 21 (pp. 6961-6971). PMLR.\n\n3. Zhang X, Song Y, Uehara M, Wang M, Agarwal A, Sun W. Efficient reinforcement learning in block mdps: A model-free representation learning approach. InInternational Conference on Machine Learning 2022 Jun 28 (pp. 26517-26547). PMLR.\n\n4. Mhammedi Z, Foster DJ, Rakhlin A. Representation learning with multi-step inverse kinematics: An efficient and optimal approach to rich-observation rl. InInternational Conference on Machine Learning 2023 Jul 3 (pp. 24659-24700). PMLR.", "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": "", "extra_scores": {}}, {"review_id": "CMc28AHsO7", "reviewer": "Reviewer_669T", "summary": "This paper provides a theoretical analysis of statistical and algorithmic modularity for RL with latent dynamics. Specifically, it offers conditions and theoretical analysis under which RL with latents is tractable. For statistical modularity, both lower and upper bounds are presented. For algorithmic modularity, observation-to-latent reductions are analyzed under two conditions: hindsight observability and self-predictive estimation. Overall, the theory and proofs are technically solid, addressing a critical problem in RL, especially in scenarios where only high-dimensional pixels are observed. Although I am not an expert in RL theory (my focus is more on algorithms and applications), I would give an acceptance rating for this initial review and will be engaged in the discussion.", "questions": "I listed my questions in the above section.", "limitations": "Limitations and discussions are given in the paper. As this is a theoretical work, I do not think it will pose any negative societal impact.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- [**Motivation and Significance**]: The problem of learning from observation for RL is important, and this paper provides fundamental theory on this topic. The statistical and algorithmic guarantees are critical contributions to the field. The theoretical findings, particularly on algorithmic modularity, have the potential to encourage more empirical work on efficiently identifying self-predictive latent states that facilitate RL policy learning.\n- [**Technical Soundness**]: Although I am not an expert in RL theory, I reviewed the main paper thoroughly and found the theoretical foundations and proofs to be solid.\n- [**Presentation**]: The presentation is clear and accessible, even for readers outside the theory domain.", "weaknesses": "Since I am not an expert on RL theory, I have listed most of my questions in this section. The major question from an empirical point of view is how to leverage some of these theoretical results to enhance RL learning from latent dynamics.\n\nQ1: The authors mentioned that block MDP or factored MDP would be a special case of this general framework. Suppose we narrow down the problem to block MDP or factored MDP, can the statistical or algorithmic modularity be easier to achieve?\n\nQ2: Similar to the previous question, what kind of structure (e.g., symmetry, disentanglement) or distribution assumptions in the latent space could mostly benefit the current theoretical framework?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their thoughtful questions. We address each of the individual questions below.\n\n> The authors mentioned that block MDP or factored MDP would be a special case of this general framework. Suppose we narrow down the problem to block MDP or factored MDP, can the statistical or algorithmic modularity be easier to achieve?\n\nModularity is indeed easier to achieve for Block MDPs (note that Block MDPs correspond to the case where  $\\mathcal{M}_{\\mathrm{lat}}$ is tabular, and we indicate that this setting is modular in Figure 1). In particular, for statistical modularity, there are many prior algorithms which achieve the desired sample complexity of $\\mathrm{poly}(S,A,H,\\log\\Phi)$ [Zhang et al., 2022, Mhammedi et al., 2023], which is statistically modular by our definition. Regarding factored MDPs, statistical modularity can be achieved under additional assumptions on the emission process [Misra et al., 21], but the general case remains an interesting open question. \nAs for algorithmic modularity, no prior works had studied this desiderata. However our reduction based on self-predictive representation learning (Theorem A.1) can be applied in the tabular (Block MDP) setting to achieve algorithmic modularity, as all the assumptions required by the self-predictive representation learning oracle are satisfied when the latent state space is tabular.\n\n> Similar to the previous question, what kind of structure (e.g., symmetry, disentanglement) or distribution assumptions in the latent space could mostly benefit the current theoretical framework?\n\nWe agree that this is an interesting question, and have tackled it in the paper – for example, we have identified that latent pushforward coverability is a general structural condition on the latent space which allows for statistical and algorithmic modularity (this subsumes, for example, the block MDP and latent low-rank MDP results). However, we do not yet have a complete picture of which latent structures or additional parameters are necessary and sufficient, and have posed this as an open question in the conclusion of the paper. We view the introduction of this question, along with partial steps towards addressing it, as one of our main contributions. \n\n**References**\n\n1. Zhang X, Song Y, Uehara M, Wang M, Agarwal A, Sun W. Efficient reinforcement learning in block mdps: A model-free representation learning approach. InInternational Conference on Machine Learning 2022 Jun 28 (pp. 26517-26547). PMLR.\n\n2. Mhammedi Z, Foster DJ, Rakhlin A. Representation learning with multi-step inverse kinematics: An efficient and optimal approach to rich-observation rl. InInternational Conference on Machine Learning 2023 Jul 3 (pp. 24659-24700). PMLR.\n\n3. Misra D, Liu Q, Jin C, Langford J. Provable rich observation reinforcement learning with combinatorial latent states. InInternational Conference on Learning Representations 2021.", "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": "", "extra_scores": {}}, {"review_id": "to48G88x5J", "reviewer": "Reviewer_qRgr", "summary": "This work investigates representation learning for decision-making in episodic MDPs. They consider a problem setting in which the goal is to through interactive decision-making learn a good policy. The task involves learning a good \"decoder\", i.e., function that maps the observations to \"state\" representations. They define a notion of \"statistical modularity\" in this problem which means that there exists an algorithm that can learn the optimal policy (with $\\epsilon$ error) with high probability with a number of episodes that is polynomial in the base MDP and the capacity of the decoder function class. They then prove an impossibility result regarding statistical modularity in this problem in general and prove statistical modularity in MDPs under some condition. They also define a notion of \"algorithmic modularity\" by introducing an algorithm in a hindsight observability setting in which one can use any decoder of interest and any standard episodic MDP algorithm for decision-making; they prove a regret bound in terms of the quality of the quality of the base MDP algorithm and the quality of the decoder.", "questions": "- Could you clarify if you are using the term \"latent states\" in the sense of partially observed MDPs. Or if you really mean the state is \"latent\" in the sense that the best representation of the state is unknown? If this is the case, it seems like this is more a representation learning problem rather than a \"latent state\" problem. Could you add further discussion of how your formulation relates to POMDPs?\n- It would be helpful to provide an intuitive definition of decoder earlier in the paper, as it is used in the intro without much context.", "limitations": "- There is no empirical evaluation of the algorithm.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- I thought the problem the authors worked on was interesting and meaningful. Overall the ideas of introducing the concepts of statistical and algorithmic modularity was interesting.\n- The authors provide many theoretical results and the result, especially regarding the algorithmic modularity result in 4.1 seems interesting, intuitive, and rather elegant.", "weaknesses": "- I found the notation and terminology used in this paper to be very dense. (I put specific questions / notes about this in the next section). I think I would prefer that the authors to have fewer theoretical results, but more thorough discussion of the results. (E.g., the self-predictive estimation idea seems interesting, but is literally 1 paragraph in the paper.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper and for their positive review. We address questions/weaknesses below. \n\n> I found the notation and terminology used in this paper to be very dense. [...]I think I would prefer that the authors to have fewer theoretical results, but more thorough discussion of the results. (E.g., the self-predictive estimation idea seems interesting, but is literally 1 paragraph in the paper.)\n\nWe apologize that the reviewer found the paper to be dense, and will strive to revise the text to improve readability. Towards this, we will happily accept any specific recommendations that the reviewer has for which content should be emphasized. In addition, we are happy to use the extra page available for the camera-ready version to expand the discussion around topics like self-predictive estimation.\n> Could you clarify if you are using the term \"latent states\" in the sense of partially observed MDPs. Or if you really mean the state is \"latent\" in the sense that the best representation of the state is unknown? If this is the case, it seems like this is more a representation learning problem rather than a \"latent state\" problem. Could you add further discussion of how your formulation relates to POMDPs?\n\nIt is best to think of our use of the term “latent state” as in the sense of the second definition you mention (finding the best representation which remains unknown). However, our use of the term “latent state” is consistent with both of the definitions you mention—in fact, they are the same under the decodability assumption we consider. In detail, our problem formulation studies a restricted class of POMDPs where the emission processes are assumed to be decodable (Definition 2.1 and 2.2). This means that the dynamics are governed by the latent state (which is unobserved, as in POMDPs), but it also means that there exists a representation which can decode the unknown latent state. The decodability assumption also removes any partial observability issues. Thus, we are in the representation learning problem, where the aim is to recover the underlying latent state (of course, as we discuss in the paper, representation learning and exploration must be interleaved in our setting). We are happy to add more discussion to emphasize how our formulation relates to POMDPs, and we thank the author for this suggestion.\n\n>It would be helpful to provide an intuitive definition of decoder earlier in the paper, as it is used in the intro without much context.\n\nWe agree that this would be helpful, and thank the reviewer for the suggestion. We will revise the introduction to include a more intuitive explanation.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This manuscript focused on the function approximation under the context of the reinforcement learning with latent dynamics. The authors discussed on the statistical requirements and algorithmic principals of learning within such scenarios, specifically on the modularities. Here modularities describe if we can decouple the representation learning steps and reinforcement learning under latent dynamics steps from both a statistical and algorithmic perspectives. Statistically, the authors show that if we don’t have a stronger complexity notions (e.g. pushforward coverability in this manuscript), then even we know the exact latent dynamics, we still cannot benefit from it. Algorithmically, the authors show that as long as we have a realizable decoder function class and we have a low-regret reinforcement learning algorithm for the latent MDP, we can have a generic observation-to-latent conversion to decouple the representation learning and reinforcement learning. All reviewers agree this manuscript can be a milestone on bridging the theory and practice of reinforcement learning. I would personally suggest the authors add a discussion on pushforward coverability, especially how it scale on the lower bound instance, to provide more intuition on the statistical modularity.
Decision: Accept (oral)