To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable RL
Authors: Yuda Song
Dhruv Rohatgi
Aarti Singh
Drew Bagnell
Venue: NeurIPS 2025 spotlight ()
Keywords: Partially Observable MDP
privileged expert distillation
learning to cheat
image-based RL
RL theory
Primary area: reinforcement_learning
TL;DR: Through theoretical models and empirical testbeds, we characterize the algorithmic tradeoff between privileged expert distillation and RL, and better options for expert distillation.

Abstract: Partial observability is a notorious challenge in reinforcement learning (RL), due to the need to learn complex, history-dependent 
policies. Recent empirical successes have used *privileged expert distillation* -- which leverages availability of latent state information during training (e.g., from a simulator) to learn and imitate the optimal latent, Markovian policy -- to disentangle the task of ''learning to see'' from ''learning to act''. While expert distillation is more computationally efficient than RL without latent state information, it also has well-documented failure modes. In this paper -- through a simple but instructive theoretical model called the *perturbed Block MDP*, and controlled experiments on challenging simulated locomotion tasks -- we investigate the algorithmic trade-off between privileged expert distillation and standard RL without privileged information. Our main findings are: **(1)** The trade-off empirically hinges on the *stochasticity* of the latent dynamics, as theoretically predicted by contrasting *approximate decodability* with *belief contraction* in the perturbed Block MDP; and **(2)** The optimal latent policy is not always the best latent policy to distill. 
Our results suggest new guidelines for effectively exploiting privileged information, potentially advancing the efficiency of policy learning across many practical partially observable domains.

To Distill or Decide? The Algorithmic Trade-off in Partially Observable Reinforcement Learning
Yuda Song
Dhruv Rohatgi MIT
Aarti Singh CMU
J. Andrew Bagnell Aurora Innovation, CMU dbagnelleaurora.. tech
CMU
yudasêcs. cmu edu
drohatgi@min @mi f edu
aar bartiecs. cmu edu
Abstract
Partial observability is notorious challenge in reinforcement learning (RL), due the need to learn complex, history-dependent policies. Recent empirical successes have used privileged expert distillation which leverages availability of latent state information during training (e.g.. from simulator) to learn and imitate the op- timal latent, Markovian policy - to disentangle the task of "learning to see" from "learning to act" [56, 12, 9]. While expert distillation is more computationally effi- cient than RL without latent state information, it also has well-documented failure modes. In this paper - through a simple but instructive theoretical model called the perturbed Block MDP, and controlled experiments on challenging simulated locomotion tasks we investigate the algorithmic trade-off between privileged expert distillation and standard RL without privileged information. Our main findings are: (1) The trade-off empirically hinges the stochasticity of the latent dynamics, as theoretically predicted by contrasting approximate decodability with belief contraction in the perturbed Block MDP; and (2) The optimal latent policy is not always the best latent policy to distill. Our results suggest new guidelines for effectively exploiting privileged information, potentially advancing the efficiency policy learning across many practical partially observable domains.
Introduction
Partial observability is a common challenge in applied reinforcement learning: the decision-makee agent may not the true state of the environment all time-steps, whose information might only be probabilistically inferred from the history of observations. An illustrative task is robot learning for robots with image-based perception [58, 68]. A single image of the robot (or, in first-person perspective, of the environment) will not capture important elements of the state such as the robot's velocity, and may miss other features due to e.g. occlusion or limited view.
The canonical theoretical model for such tasks is Partially Observable Markov Decision Process (POMDP). Unfortunately, there are well-documented computational [57] and statistical [28] barriers to planning and learning in POMDPs, which have motivated many theoretical works that seek to bypass these barriers by making additional structural assumptions [28, 33, 19, 24, 23, 42]. On the empirical side, the standard technique for mitigating partial observability is frame-stacking which enabled notable successes for learning play Atari games [50, 51]. The idea is to treat the short window of L recent observations, and
"state" of the environment as the concatenation apply standard algorithm for fully-observed reinforcement learning (RL). This technique inspired theoretical developments such as L-step decodability [19], and has some theoretical underpinnings for 7-observable POMDPs [24]. Yet frame-stacking not silver bullet for partially observable decision-making: sometimes effective planning requires long memory [18]. Also, high-dimensional observations (such stacks of images) can confound learning complex behaviors [58, 78].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Learning from latent state information. A common heuristic for planning in known POMDPs to use the optimal latent policy (also known as the state-based policy or privileged policy) i.e., the optimal policy that is allowed to "cheat" and see the underlying state of the environment as a starting point for computing an executable policy - i.e. policy that only depends on the observable history [40, 65, 12]. More recent works have brought this ansatz. to the learning task, where the description of the POMDP is a priori unknown. In the standard theoretical formalization of this task [31], the latent states of the POMDP are never observed (nor even identifiable); however, for applications such as robotics, it is often practically reasonable to construct a simulator of the environment [13], from which the learning agent may draw trajectories that include both the observations as well as the latent states - "privileged" information that is only available at training time, not at test time.
The most prominent paradigm for exploiting this additional information is called privileged expert distillation, which applies methods from imitation learning and structured prediction [15, 62, 64, 8] to learning POMDPs. Expert distillation has two steps: (1) learn an optimal latent policy, using a standard RL algorithm with the latent state information provided by the simulator; and (2) distill the latent policy to an executable policy, using an imitation learning algorithm such as DAgger [64]. This paradigm has achieved impressive success in applications such as autonomous driving [9], robotics [37, 48, 85] and LLMs [11].
These successes suggest fundamental question: when does expert distillation help in realistic decision-making tasks? On the one hand, in controlled experiments, expert distillation uniformly converges faster and more stably than RI. without latent state information [53], likely because it disentangles representation learning from decision makinn [9]. Moreover, expert distillation enjoys a provable computational advantage in decodable POMDPs2 [7]. On the other hand, there are well- documented failure modes of expert distillation - most notably, due to its inability to encourage purely gaaaatai actions [2. 79] where more expensive hybrid methods such as Asymmetrie Actor-Critic [58] are fundamentally required.
In this paper, motivated by image-based based locomotion tasks, we focus on the middle ground where (perfect) decodability may fail, yet the observations are still highly informative of the latent state. In this regime, we ask: (i) when and how is expert distillation as performant as standard RL with frame-stacking, and (ii) are there lightweight improvements to expert distillation? We use simple theoretical models in tandem with controlled experiments to address the preceding questions.
Our contributions.
1. The prior theoretical model for understanding the benefits of latent state information was a perfectly decodable POMDP [7]. We begin by empirically demonstrating that this model is too restrictive for image-based locomotion tasks.
2. We then introduce approximate decodability, and connect to the success of expert distillation in analogy with the connection between belief contraction and the success of standard rein- forcement learning with frame-stacking. But when are these conditions satisfied? As a theoretical testbed, we introduce the perturbed Block MDP.
3. We show both theoretically (by analyzing the perturbed Block MDP model) and experimentally that the performance of expert distillation compared to standard reinforcement learning depends crucially on the stochasticity of the model dynamics: for deterministic dynamics, distillation is competitive with RL, but as the stochasticity increases, its performance comparatively degrades.
4. Finally, we show that distillation of the optimal latent policy is often sub-optimal use of latent state information: the simple modification of adding stochasticity to the latent MDP before computing the optimal policy yields robust performance benefits via improved smoothness.
2 Preliminaries
A ffnite-horizon layered) Partially Observable Markov Decision Process (POMDP) is a tuple H S. S, 0, R), where H E N is the horizon, X' ( is the observa-
P
'The same paradigm is sometimes called Learning by Cheating or Teacher to Student Learning. 'Decodable POMDPs without any prefix refer to H step decodable POMDPs, where H is the horizon of the POMDPs.
2

---

tion space, S = (S is the latent state space, A = {Ar is the action space, IP {IA, : - x An-1 - A(S,) ((S)))=== د describes the latent transitions, O {O,, : S + A(X)) describes the emission distributions, and R = {R, Sh x An + [0. 1|} describes the rewards. We write == max; [A, S == max, Sul. and X == max x Xn. and similarly for A"-Loh, with the shorthand h I= max m1 h - L.) Then an I-step executable policy is a collection т = (mp L x A L + (AA)):: we let IT denote the class of such policies. Given any executable policy E II == 11",,,, trajectory T ($1, 11,,21,11 P1..... SH, HH aH TH) is gen- erated by Sh. ~ (sh-5 on-1), 24 ~ (sn). ag ~ π [ 01:h-1), Th = RA (S), ax)- We use px and E" denote the law and expectation under this process. Following convention, we assume
Given any timestep
and I. E [M]. we denote Xh-L:h = Xn- x -
E Th I almost surely under all policies. The value of a policy т is J(m) := E"
Eh=1Th Th
Note that the POMDP P also defines an underlying Markov Decision Process (MDP) M = (,, (which we call the latent MDP) where the state is fully observable. A latent (Markovian) policy is a collection π latent ( latent
Sn - ((An)), and we let I|latent denote the class of latent policies. A latent trajectory 7 platent (81, (81,01,.... 811 a.) is generated and ET ther accordingly.
by 8/2- (5h-11, 11-1), ag ~ Th =lttent(s))) and we define Fx arane
Learning with/without latent state information. In the standard theoretical RL access model (i.e without latent state information) [30, 27], at training time, the learning agent can repeatedly interact with the POMDP P by playing an executable policy и and observing the partial trajectory (II.H, 01:81 Fi.H). ). In contrast, in the learning with latent state information model [7], at training time, the learning agent can play any policy, and observes the full trajectory ($1.H T1:H 41:H, T1:H In both settings, the goal is to eventually produce an executable policy ā that minimizes J(x*) ( (where x² is the optimal executable policy).
Belief states. A belief state is a distribution over latent states. For a prior b on the latent state at step 1, let (b; an-1, Zn.) ) be the posterior on the latent state at step h after taking action a₁-1 and then observing 24 (see Definition B.I for the formal algebraic definition).
Definition 2.1. For any observation/action sequence (111:h @1:h-1), the true belief state (1 01:h-1) is defined as follows. For h = 1 with observation T₁, let (y()) (PF).)). For any 2 < h S H1, let
by bx a11-11 == (F1A-
For any executable policy म, step h. and history (Iish, 41:h-1), (a 01 1) is the distribution of the latent state 8n under Pa conditioned on (Zish, a1:h-1) (Lemma C.2).
Many methods for efficient planning in POMDPs are based on approximate belief states that only de- pend on a short window of recent actions and observations [29, 24]. Informally, the approximate belief state b apx (#N-L+1:h+ 44:L:h-1: D) is the posterior on state 8) after observing (#h-L+1:h, 0%- -:h-1) with prior DD on state sh-L- See Definition B.2 for the formal definition (analogous Definition 2.1).
Additional notation. For distributions b,U' E A(S)). the density ratio is ||b//81|| =
sup,es, ((s)) oo), with the convention that 0/0- 1. For belief state b E A(S)) and conditional distribution TA Sn + A(Ax), we let TA b denote the distribution over A, obtained as
(mA o b)(n) = Eoyes, b(sn)Ta(an sp).
(2)
Experimental Setup. We use three tasks in the Deepmind control suite [73]: walker-run, dog-walk and the challenging humanoid-walle To implement online (resp., offline) expert distillation, we (1) train an expert on the latent state information using MrQ [22], and (2) imitate the expert via DAgger [64] (resp., Behavior Cloning (BC)) on L-step executable policies. Unless otherwise specified, we use the standard choice of L 3, and we use mean squared eгror (MSE) as the /=1 loss function: give input X [ and target Y = (v² E Rd) the loss of a function S is (f,,XY) N M. ΣS ))-(((()); -² To implement reinforcement learning (RL), we use MrQ [22] on L-step executable policies. In experiments. we follow the common empirical practice of only stacking observations (rather than both observations and actions).
Appendices. See Appendix A for additional related work, and Appendix H for experimental details.
3

---

3
Approximate Decodability and Belief Contraction
Even with access latent state information during training, the problem of learning near-optimal policy in POMDP is as hard as the planning task (where a description of the POMDP is already known), which is well-known to be computationally intractable in the worst case [57]. However, POMDPs encountered in practice will often satisfy additional structural properties that may mitigate this hardness. Some of the most widely-studies properties are decodability [19, and belief contraction (also known as filter stability) [29, 24].
Privileged information is known to yield provable computational benefit in decodable POMDPs [7]. However, as we empirically demonstrate in Section 3.1, perfect decodability is an unrealistic assumption in motivating tasks. For this reason, in Section 3.2 introduce the notion of approximate decodability. Heuristically, this property governs the success of expert distillation with L-step framestacking, whereas belief contraction governs the success of standard RL (also with L-step framestacking). But when are these properties satisfied? As a clean theoretical testbed for studying this question, Section 3.3 we introduce the 8 5-perturbed Block MDP.
3.1 Prior Work: Perfectly Decodable POMDPs
In some applications, such as video games, it is plausible that the agent can deduce the latent state from small number of recent observations. This empirically substantiated by the success of DQN [50] and its variants, which only use the most recent four observations as policy inputs. Theoretically, this motivated the study of the L-step decodable model [19], which posits that the most recent L observations and actions suffice to fully disambiguate the latent state (Definition B.3).
Without latent state information (i.e. in the standard RL access model), learning a near-optimal policy in an L-step decodable POMDPs requires (2 samples [19]. However, with latent state information, [7] show that the sample and time complexity of learning near-optimal policy ā e II such that J(+) 2 arg max+en J -a e with high probability is only A, H, 1/2). Thus, for large I., there is a clear theoretical benefit of latent state information (both statistically and computationally). However, unfortunately, L-step decodability is not always a realistic assumption:
Empirical test: does perfect decodability hold? Through controlled experiments on our three chosen locomotion tasks (Section 2), we observe that latent states are not perfectly decodable in practice, especially in early timesteps. We defer details of this experiment to Appendix H.l.
3.2 Errors in POMDPs
The above empirical result motivates the following theoretical definition of decodability error: Definition 3.1 (Decodability Error). Fix a POMDP P. The decodability error for an executable policy n. and timestep h E [M]
decode (T) = E (rrsh, 41:-1))l..
Intuitively, decodability error quantifies stochasticity of the true belief. Below, we show that upper bounds the misspecification of any latent policy platent with respect to the class of executable policies.
Lemma 3.1 (See Lemma E.3). Let latent E l1latent be a latent policy and let b be a collection of functions by xh x n + A(S)). Define executable policies ग, by ( a1:h-1) = p latent o by (Z1sh, a1:h-1) and (EEI a1:h-1) == maatent (5 (tri:ha1ish111 a1:h-1) 1) (see Eq. (2)). Then
H
TV
P
<
25
decode (T)
||| |
- Ba -
(3)
Am
Low decodability error is not strictly required for low misspecification (see Section 6). but some such assumption is needed to rule out models requiring active information-gatherne [79]. As a special case, Lemma 3.1 implies that x. latent is 2 h- >" edecode (rr--e to the executable policy и,, which evaluates x. latent at random state s/, sampled from the true belief by (Ti: (1:A-1 1); this is because if by (arish, 01:4-1 is highly concentrated, then 8/, likely matches the true latent state. The second error term in Eq. (3) quantifies error in learning the true belief e.g., due to using only L-step histories.

---

Next, it is instructive to contrast decodability error with belief contraction error, the discrepancy between the true belief and the approximate belief induced by the L most recent observationssacciion:: Definition 3.2 (Belief Contraction Error [24]), Fix POMDP P. For an executable policy n, and rimestep h E [ the L-step belief contraction enror (L E [h 1) is
contract (T: L) E" (1 (1 b,,, ( (4-L unif (f E/
In the absence of latent state information, bounding the belief contraction error is the standard method of analyzing provably efficient algorithms for RL POMDPs [29, 75, 24]. Indeed, belief contraction implies that the POMDP with L-step frame-stacking is approximately Markovian, which heuristically suggests that a standard RL algorithm [30, 5] with frame-stacking should achieve low error time (AX) (()), Due to technical issues with error compounding, this is not formally true, but under an additional observability condition, there is an algorithm that provably achieves that guarantee:
Theorem 3.1 (Informal; see Theorem B.1; due to [23]). Suppose the POMDP is 7-observable (Definition B.4), and satisfies L-step belief contraction with error e. There exists reinforcement learning algorithu that achieves the sub-optimality bound
(( ( (+=") S (oly(S,X,H,y)
in time (XA))(L) S,
S,y ,
Technically, the explicit result in [23] fixes L ~ log' (SH/e)/7 (in which case the desired belief contraction bound is implied by 7-observability, but the algorithm requires guasi-polynomial time), but we observe that the proof extends to the result above see Theorem B.1. Notably, Theorem 3.1 gives a polynomial-time algorithm if belief contraction holds for = O(1)
3.3 The Perturbed Block MDP
Approximate decodability and belief contraction are conditions under which expert distillation and standard RL with frame-stacking, respectively, may be reasonably expected to succeed. But when are these conditions satisfied, and how do they compare? As theoretical testbed, we introduce the perturbed Block MDP model. Block MDPs [16] are a well-studied abstraction of environments with rich observations yet simple latent dynamics. However, they assume that the latent state is fully determined by the current observation. Below, we generalize Block MDPs by allowing for d probability that the observation sampled from an arbitrary conditional distribution.' 4
Definition 3.3. Fix a parameter 8 >> O. A POMDP P is 6-perturbed Block MDP if, for each h [H], there are On, En : Sn + (x)) such that On : S₁ + ((K)) satisfies the block property [17], i.e. (- sn). Ox(- 5%,) have disjoint supports for all Sh. + sh and moreover the emission distribution On step h can be decomposed as follows: On (x 8n) (1 ( sb)) + (xr.)))) sn)-
A simple example is the noisy sensor model where S = X' and the true state is observed with probability at least 8. Later, we will examine the empirical validity of this model; for now we study its theoretical implications. Below, we prove that for any 5-perturbed Block MDP, the belief contraction error decays exponentially as the frame-stack increases, by a factor of O()) per frame.
a 6-perturbed Block MDP. There universal constant CD.1 >> 1 with the following property. Fix an executable policy n, indices 1 < h- I. h < H, and a distribution D E (SS)-L)) Then for any partial history (F1:h- L, a1:h LL 1),
Theorem 3.2 (See Theorem D.I). Suppose that the POMDP
by I. 01:h L-
Ea [|| by (Tish, (1:h-) b,, apr (#h- L aA- 1:; D) & (CD.0)2/9
D
where the expectation is over trajectories drawn from policy x conditioned on the partial history (e.h-L.91hh-a Thus, in particular, e ccontract (T; L) < (CD.16)4/95.
Tecchicaally, the result requires slightly generalizing Definition 3.2; see Theorem B.1 for the formal statement. "To be clear, our theoretical focus is on issues arising from partial observability, not on representation learning. The size of the observation space is conceptually tangential, so we omit introducing technical complications such function approximation, which are central to theory for fully-observed Block MDPs [82, 47, 61].
5

---

was Icar
dog
humanoid
1000
Reward
Reward
750
400
Behastor Cloning
400
Diigger
revoorrmment Learning (PL)
250
200
20
40 Training Time thours)
Training Time (hours)
Training Time (hours)
The performance of (oftline/online) expert distillation and RL with respect to wall-clock time. We repeat each experiment 5 times and plot the mean and standard deviation. For the time complexity of BC, we include the data collection time, and amortize it over the training steps. For both BC and DAgger, we include the time train the latent expert (also amortized).
Figure 1:
While prior belief contraction results [24] apply to this model, they only yield contraction by 1 (1 25)/C per frame, for a large constant C > 1 (Remark D.1), and so are vacuous for ==o(lo S), even in the regime ā < 1 (i.e. low observation noise). Theorem 3.2 remedies this limitation; e.g. for = 1/S yields & efontract (T; L) S (11SS) with only L = ((1) To prove Theorem 3.2, one might hope that each new observation contracts the TV-distance by poly (6) in expectation. This false (Example D.1), but in such cases, turns out that the density ratio decays, yielding win- win argument.
Heuristically, Theorem 3.2 suggests that standard RL with L-step frame-stacking should progressively improve L increases. Formally, Theorem 3.2 and Theorem 3.1 imply the following end-to-end learning guarantee for the RL algorithm of [23] (which does not use latent state information):
Corollary 3.1 (Informal; see Corollary F.I). There is method that, for any 8-perturbed Block MDP, time
learns a policy से with J(x²) - (() < (C3.6)) 1/9 (SX
From a theoretical view, it remains to understand the decodability error for the perturbed Block MDP. As we will show, this qualitatively depends on the stochasticity of the transition dynamics.
4 Distillation is Competitive for Deterministic Dynamics
In some environments, it is reasonable to assume that the latent transition dynamics are deterministic (c.g., if the dynamics governed by simple Newtonian mechanics). Simulation benchmarks with this property include some Atari games as well as MuJoCo tasks. In this section, we theoretically and empirically study the performance of expert distillation, versus standard RL with frame-stacking, in such environments (with deterministic latent transitions, but stochastic initial state and observations).
4.1 Theoretical Analysis under Deterministie Dynamies
Below, we show that for perturbed Block MDPs with deterministic dynamics, the decodability error decays exponentially as the step [H]] increases. Intuitively, each observation concentrates the true belief state further, and the deterministic transitions cannot "spread out" the belief state. While this intuition is not quite rigorous, it can be proven that most observations concentrate the belief state; the result follows from an appropriate martingale analysis (Lemma C.5).
so that the following holds. Suppose that P is a 5-perturbed Block MDP with deterministic transitions. For any executable
Proposition 4.1 (See Proposition D.1). There is a universal constant C1.1
policy π and index h E [H]. it holds that e decode (TT) < min(ō, (C4.1))(-1)19)
From Lemma 3.1, the "ideal" distillation of latent expert g is _iiittatinn == x latent b, i.e., given any history, query the latent expert based on the true belief. Combining Lemma 3. and Proposition 4. immediately yields strong, horizon-independent guarantee for this policy: if a is the optimal latent policy, then
H
J(TT) J imiitation < latent)) - J imiitattonn < 2
Σ min(6,
< (6)),
h=1
where the first inequality by Lemma C.4. Of course, exactly learning the true belief state may be unrealistic, since this would require conditioning the entire history. However, prove that (a

---

Suboptimalty Horizon wakker Inau
Subopdimalty Horizon .dog
Subeptimmally by Hor humansid
Merrabee Serepme
Shal a2
Plrtto
DAgger Scboptimaliy Hertzon Walker
Drggger Suboptimally Heraan
DAgger Subostimoitt Harteon Hamannn
Harioon
The normalized suboptimality of the expert distillation algorithms (top: behavior cloning; bottom: DAgger) with respect to the horizon. We repeat 5 runs for each horizon and task, and perform linear regression the results from each task. Note that the trajectory rewards for this plot have been normalized by horizon (and by creion-prediction error), so linear scaling indicates compounding errors.
Figure 2:
slight modification of) the Forward algorithm [62] (the non-stationary version of DAgger) on L-step executable policies learns the following approximation of iimitation 5 in the anfinite-sampee limit:
latentt by, (IN-L+1:h, ah L.h Th
if h L otherwise
Forward/ (- Th- F. l:b; L.h- Kh
1h maaeent (1, (1:k-)
See Appendix E.2 for the algorithm and proof. Applying this derivation to Lemma 3.1, then using Proposition 4.1 to bound the decodability error and Theorem 3.2 to bound the error in approximate beliefs, gives the following guarantee for expert distillation under deterministic latent dynamics:
Theorem 4.1 (See Theorem E.I). Suppose that the POMDP P is a 6-perturbed Block MDP with deterministic transitions, and fix L E N. Let я glatent E Illatent be the optimal latent policy, and let no Forward be the policy computed by Forward with policy class II~ (i.e, all L-step executable policies) and expert TI llateet, the infinite-sampley limit. Then
[(r)) [ Porvard) S J(xllatent Forrardd TV(IPT
P S 068) + (LD.1
Comparison with RL. While Theorem 4.1 is presented in the infinite-sample limit, the effective sample complexity is only R (X (X)))(1), since the optimization is over L-step executable policies. More concretely, up to additional error Sopt. the above guarantee can achieved by the same algorithm with only poly((AXX) H, tog) time and samples (Theorem E.2). Thus, the guarantee for Forward qualitatively matches the guarantee for RL (Corollary 3.1), aside from the additional horizon-independent term of O()) incurred above (due to poor decodability in initial steps).
4.2 Empirical Analysis under Deterministic Dynamics
Theorem 4. gives a strong performance guarantee for expert distillation under deterministic latent dynamics. nearly matching that of RL. This suggests that expert distillation may be preferred over standard RL due to its (practical) efficiency. Also, Theorem 4.1 suggests that error may compound with the horizon H. However, the result is only an upper bound, and only for stylized setting. We now investigate whether these two theoretical implications hold up empirically.
Expert distillation outperforms RL under deterministic dynamics. In this experiment, compare the (a) asymptotic performance and (b) computational efficiency of expert distillation and
*Note that behavior cloning will not learn the same policy, due to the latching effect [72] (i.e. conditioning on past actions of the latent expert). It may nevertheless achieve the same regret bound as Forward in our setting: theoretically separating these algorithms likely requires assuming e.g. recoverability [20].
7

---

humanoid noise-0.1
humanoid noise-0.2
humanoid noise=0.3
N0)
200
Wast-Clock Time thours) dog noise=0.2
Whit-Ciack Time
West-Clade Time
dog
dog
"Wati-llek Time (houms)
Walt-Cleck Time (hours)
Wall-Clodk Time thoums)
Figure 3: Performance of DAgger and RL with different frame-stacks on humanoid-wall and dog-walk with motor noise. We repeat each experiment 5 times and plot the mean and standard deviation. Note that in general, the improvement of RL over DAgger increases with the motor noise.
standard RL. We train each method until convergence, and we plot the episodic return with respect to the wall clock time in Figure 1. We see that offline expert distillation (i.e., behavior cloning) is competitive in easier tasks such walker, but is suboptimal in harder tasks such as humanoid and dog. However, online imitation learning (i.e., DAgger) is able to achieve the best performance in all tasks, and with better computational efficiency (i.e., faster convergence) than RL. This supports our theory that under deterministic dynamics, expert distillation can be close to optimal.
Empirical vignette: the source of error compounding? The horizon dependence of the error in imitation learning has received intensive empirical [62, 35, 3] and theoretical [59, 20, 60) study, both from the perspective of sample complexity [59, 20] and misspecification [60]. It is widely believed that behavior cloning suffers error compounding over the horizon, which is avoided by online methods such DAgger that are able to recover from mistakes [63, 59]. Does this compounding manifest in expert distillation for POMDPs, and is the cause sampling error or misspecification? In Figure we vary the horizon H [50, 450), and measure the sub-optimality of offline and online expert distillation. We normalize rewards so that trajectory reward lies in [0, 1]. We further normalize by mean action- preeiittoniiiioon MSE (averaged over choice of H). We see strong horizon dependence for behavior cloning (and weaker for DAgger, likely due to recoverability). ). This contrasts with empirical results of [20]: they perform well-specified behavior cloning in similar tasks, and find little horizon dependence. Together, our results therefore suggest that misspecification, rather than sampling error, may be the more fundamental source of horizon dependence for behavior cloning.
RL Outperforms Distillation for Stochastic Dynamics
While deterministic dynamics are plausible in some applications, there are also many potential sources of stochasticity; real-world robotics, stochasticity may be required to model e.g. internal motor noise or unknowable features of the external environment. Some robotics simulators [44] also have stochasticity arising from a PDE solver. How does the stochasticity of the environment affect the performance of expert distillation and RL?
5.1 Theoretical Analysis under Stochastic Dynamics
We show negative result in the perturbed Block MDP model: for general dynamics, the misspecifi- cation of the optimal latent policy with respect to the class of L-step executable policies does not necessarily decay as L increases, in contrast with the case of deterministic dynamics (Lemma 3.1).
Proposition 5.1 (See Proposition D.2). Let 8 > 0 and H E N. There is 5-perturbed Block MDP P with horizon H such that for all L E [H), the optimal latent policy πe latent satisfies the following bound, where I is the class of L-step executable policies:
min TV TEllL
latent
p 2 (0(min(1,8H)
8

---

This result also highlights the difference between decodability error and belief contraction error, which does decay as increases, regardless of the transition dynamics (Theorem 3.2). The intuition for Proposition 5.1 is simple: in the extreme case where the dynamics are uniformly mixing at every step, prior observations yield no information about the current state, so the á error incurred by trying to decode the current observation is irreducible. This decodability error compounds over timesteps, and means that executable policies are unable to simulate the latent policy that plays an action uniquely indexed by the latent state. In contrast, POMDPs with uniform mixing are easy for standard RL, precisely because they reduce to H independent horizon-1 subproblems.
Comparison with RL. The above result, compared with Corollary 3.1, suggests a potential empirical benefit of standard RL over expert distillation: the former may generically able to trade increased computation (by increasing L) for improved performance (by mitigating observation noise), whereas the latter- - at least in the worst case incurs irreducible error due to stochasticity in the dynam- ics. To be sure, the uniformly-mxxing construction from Proposition 5.1 is practically unrealistic; nevertheless, below we verify that this benefit occurs more realistic environments.
5.2 Experimental Analysis under Stochastic Dynamics
RL with more computation eventually outperforms distillation. To simulate a POMDP with stochastic latent dynamics, we apply motor noise in the humanoid-walk task. We add O-mean isotropic Gaussian noise with std-dev E {0.1, 0.2, 0.3) to each action. We compare DAgger and RL with frame-stack L E (2, 3, 4). We run each method until convergence (with the same number of episodes for all runs with fixed algorithm/noise level) and plot episodic return against wall-clock time (Figure 3). We observe that expert distillation does not benefit from larger L, whereas the performance of RL sometimes benefits (at the cost of longer wall-clock time). This improvement is not as dramatic as the theory predicts, perhaps suggesting that there is theoretically unaccounted-for for dependence between observation errors. Nevertheless, the results do corroborate the main prediction: RL robustly outperforms expert distillation for higher noise levels.
Empirical vignette: does belief contraction error track RL sub-optimality? We empirically estimate belief contraction error for each task with no motor noise, and for humanoid-walk with std-dev= 0.2. We approximate the (unknown) ground truth belief by training model 6 that takes L' 10 input frames. We compare against models 6d. with E [2, 5] input frames. Each model's output belief is parametrized as a multivariate Gaussian distribution with diagonal covariance. All models are trained on the same 2000 trajectories collected by the latent expert policy. For each we compute the KL-divergence (a tractable proxy for TV-distance) between outputs of 6² and 6 and average across 100 episodes of validation data, also collected by the same latent expert policy. We find that the empirical error decreases slightly as L increases (Figure 7), though not as fast as the theory predicts. Adding motor noise has little noticeable effect (Figure 8). Interestingly, the error is not predictive across tasks: dog-walk has highest empirical error among the three tasks, yet RL achieves the lowest sub-optimality on it (Figure 1), indicating theoretically-unexpiiii confounder.
6 Towards Better Distillation: Imitating a Smoother Expert
In this section, we discuss how the bounds via approximate decodability (e.g.. Lemma 3.1) are loose since they fail to capture the smoothness of the latent expert. A tighter bound with smoothness suggests potential benefits of artificially smoothing the latent expert before distillation. We then propose a broadly-applicable method for improving the smoothness, and show that yields empirical benefits. We view these results as largely proof-of-concept and leave more detailed investigation to future work.
Smoothness of the latent policy. Suppose that the true belief state at some step is always uniform over two particular states s'). Then decodability error is large, and worst-case latent policy latent namely, one that plays different actions these states is unavoidably misspecified with respect to the class of executable policies. However, ambiguity between 8 and s' is most likely to occur if these states are somehow similar (e.g., close w.r.t. metric). If latent is smooth in the sense that it plays similar action distributions for nearby states, then the misspecification should be mitigated.
NNte that for observabble POMDPs, KL-divergence also predicted to decay L increases [24].

---

Expert Smoothing Noise 0.2 humanoid
Expert Smoothing Noise 0.2 dog
Reseants
1000
Trelcturr Howweds
600
600
400
200
220
Expott
Expast
50.000
3000000
150000
200200
250,00
Training Steps
Figure 4: Performance of DAgger the validation dataset for the humanoid-walk and dog-wa environments with motor noise o = 0.2, as the noise level for the training environment (i.e. the environment in which the latent expert was trained) varies over {0.1, 0.2, 0.3, 0.4, 0.5).
This phenomenon can be captured more generally by the following variant of Definition 3.1, which measures decodability error of the actions (and hence is adaptive to the latent expert): Definition 6.1 (Action-prediction error). Fix a latent policy n latentt For fixed executable policy n, and timestep hi the action-predictee preddicrrdiiiinn error is defined as
act: heeeee
(T))
E"
latent b2 (1:b-1))l
In Lemma 3.1, the decodability error can indeed be replaced by the action-prediction error see Lemma E.4. Note that so long as platent is deterministic (which is without loss of generality for the act;
optimal latent policy), it generically holds that 5% (T) S - edccode (TT).
Algorithmic intervention: smoothing experts with motor noise. One way to construct a smoother expert policy pre- or post-compose the optimal latent policy at each step with c.g. a Gaussian convolution kernel (on the state or action space, respectively). However, such approaches ignore the sequential nature of decision-makinn may no longer be optimal. We propose instead computing the optimal policy for modified latent MDP with additional motor noise. This encourages robustness to motor noise, as a tractable proxy for robustness to observation noise-se see Appendix G for an example of one potential mechanism by which the former may lead to the latter.
smoothing the policy later steps means that earlier actions
For both humanoid-walk and dog-walk, for each E (0.1, 0.2, 0.3, 0.4, 0.5]. we train an expert latent policy x" in the environment with mean-0, std. dev.-o, Gaussian motor noise on each action. We distill each expert to an executable policy via DAgger in an environment with a = 0.2. We observe that 0.2 incurs worse estimated action- prediction error than some higher-noise experts (Figure 9). Moreover, despite being the optimal latent policy for this environment, it is not the best expert distill (Figure 4): the distillations of policies with lower action- periin-preiittin error achieve higher reward (substantially for humano i d-walk and modestly for dog-walk). We also observe that the effect disappears when the true environment has deterministic dynamics (Appendix H.2), likely since it is near-decodable.
Experimental results.
Related methods. We view this method as a lightweight version of asymmetric RL methods that iteratively refine the expert [78]. It is also closely related to the principle of noise injection in imitation learning [35, 4], which has been shown robustify Behavior Cloning-to match the performance of DAgger- by mitigating out-of-distributie uses online data collection to mitigate -iitt-i-iitiitttion effects, noise injection can still improve its performance in challenging mmage-based tasks thus suggesting that there may be qualitatively different phenomenon at play highly misspecified settings.
effects.? Figure 4 demonstrates that even though DAgger
I Limitations and future work. Our theoretical results are for discrete tabular models with independent observation noise; weakening these assumptions could yield more precise understanding of the fundamental challenges that arise in applications with rich partial observations. Our experiments use synthetic injected motor noise; extending to more natural sources of stochasticity could be valuable. Also, there is a vast design space of algorithmic interventions for smoothing, of which we have only touched the surface. Finally, our work is motivated by applications like robot learning where decoddecooabllity is plausible, but important problem which we did not explore - is to understand the algorithmic trade-offs in applications that require active information -athoriig....gg....
We remark that DÁgger saturates most of the benchmarks used by [35].
10

---

Acknowledgements
The authors are grateful Noah Golowich, Audrey Huang, Nan Jiang, Akshay Krishnamurthy, Ankur Moitra, Wen Sun, Gokul Swamy, and Kaiqing Zhang for their insightful discussion. AS and YS acknowledge and thank the support ONR grant N000142212363 and NSF Al Institute for Societal Decision Making AI-SDM grant IIS2229881. DR is supported by NSF awards CCF- ICF-2430381 I and DMS-2022448, and ONR grant N00014-22-1-2339.
References
[1] A. Agarwal, A. Kumar, J. Malik, and D. Pathak. Legged locomotion in challenging terrains using egocentric vision. In Conference on robot learning, pages 403-415. PMLR, 2023,
[2] S. Arora, S. Choudhury, and S. Scherer. Hindsight is only 50/50: Unsuitability of mdp based approximate pomdp solvers for multi-resolution information gathering. arXiv preprint 1804.:88040022
2018.
[3] A. Block, D. J. Foster, A. Krishnamurthy, M. Simchowitz, and C. Zhang. Butterfly effects of sgd noise: Error amplification in behavior cloning and autoregression. arXiv preprint arXiv:2310.11428, 2023.
[4] A. Block, A. Jadbabaie, D. Pfrommer, M. Simchowitz, and R. Tedrake. Provable guarantees for generative hehavior cloning: Bridging low-level stability and high-level behavior. Advances in Neural Information Processing Systems, 36:48534 48547, 2023.
[5] R. I. Brafman and M. Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(0ct):2 2002.
[6] D. Burago, M. De Rougemont, and A. Slissenko. On the complexity of partially observed markov decision processes. Theoretical Computer Science, 157(2):161-183, 1996.
[7] Y. Cai, X. Liu, A. Oikonomou, and K. Zhang. Provable partially observable reinforcement learning with privileged information. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[8] K.-W. Chang, A. Krishnamurthy, A. Agarwal, H. Daumé III, and J. Langford. Learning to search better than your teacher. In International Conference Machine Learning, pages 2858-2066. PMLR, 2015.
[9] D. Chen, B. Zhou, V. Koltun, and P. Krähenbühhl. Learning by cheating. In Conference on Robot Learning (CoRL), 2019.
[10] X. Cheng, K. Shi. A. Agarwal, and Pathak. Extreme parkour with legged robots. 2024 IEEE International Conference on Robotics and Automation (ICRA), pages 11443-11450 IEEE, 2024.
[11] Choudhury. Process reward models for 1lm agents: Practical framework and directions. arXiv preprint arXiv:2502. 10325, 2025.
[12] S. Choudhury, M. Bhardwaj. S. Arora, A. Kapoor, G. Ranade, S. Scherer, and D. Dey. Data- driven planning via imitation learning. The International Journal of Robotics Research, 37(13- 14):1632-108 2018.
[13] Christiano, Z. Shah, Mordatch, J. Schneider, T. Blackwell, J. Tobin, P. Abbeel, and W. Zaremba. Transfer from simulation to real world through learning deep inverse dynamics model. arXiv preprint 1rXiv:1610.003:
2016.
[14] C. Dann, N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. On oracle-efficient PAC RL with rich observations. In Advances in Neural Information Processing Systems, 2018.
[15] H. Daumé, J. Langford, and Marcu. Search-based structured prediction. Machine learning, 75:297-325, 2009.

---

[16] S. Du, A. Krishnamurthy, N. Jiang, A. Agarwal, M. Dudik, and J. Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, 2019.
[17] S. Du, A. Krishnamurthy, N. Jiang, A. Agarwal, M. Dudik, and J. Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2019.
[18] O. Eberhard, M. Muehlebach, and C. Vernade. Partially observable reinforcement learning with memory traces. arXiv preprint arXiv:2503.15200, 2025.
[19] Y. Efroni, C. Jin, A. Krishnamurthy, and S. Miryoosefi. Provable reinforcement learning with a short-term memory. In International Conference Machine Leurning, pages 5832-5850. PMLR, 2022.
[20] J. Foster, A. Block, and D. Misra. Is behavior cloning all you need? understanding horizon in imitation learning. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[21] Fu, Y. Song, Y. Wu, F. Yu, and D. Scaramuzza. Learning deep sensorimotor policies for vision- based autonomous drone racing. In 2023 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5243-5250. IEEE, 2023.
[22] S. Fujimoto, P. D'Oro, A. Zhang, Y. Tian, and M. Rabbat. Towards general- purpose model-free reinforcement learning. In The Thirteenth International Conference on Learning Representa- tions, 2025.
[23] N. Golowich, A. Moitra, and D. Rohatgi. Learning in observable pomdps, without computa- tionally intractable oracles. Advances in neural information processing systems, 35:1458-1473, 2022.
[24] N. Golowich, A. Moitra, and D. Rohatgi. Planning and learning in partially observable systems via filter stability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pages 349-362, 2023.
[25] N. Golowich, A. Moitra, and D. Rohatgi. Exploration is harder than prediction: Cryptographi- cally separating reinforcement learning from supervised learning. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1953-1967. IEEE, 2024.
[26] D. Hoeller, N. Rudin, D. Sako, and M. Hutter. Anymal parkour: Learning agile navigation for quadrupedal robots. Science Robotics, 9(8))cad:77566 2024.
[27] N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable In International Conference on Machine Leurning, 2017.
[28] C. Jin, S. Kakade, A. Krishnamurthy, and Q. Liu. Sample-efficient reinforcement learning of undercomplete POMDPs. Advances in Neural Information Processing Systems, 33, 2020.
[29] A. Kara and S. Yuksel. Near optimality of finite memory feedback policies in partially observed markov decision processes. Journal of Machine Learning Research, 23(11):1-44 2022.
[30] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49:209-232, 2002.
[31] A. Krishnamurthy, A. Agarwal, and J. Langford. PAC reinforcement learning with rich observa- tions. In Advances in Neural Information Processing Systems, 2016
[32] A. Kumar, Z. Fu, D. Pathak, and J. Malik. Rma: Rapid motor adaptation for legged robots. arXiv preprint arXiv:2 04444444444 2021.
[33] Kwon, Y. Efroni, C. Caramanis, and Mannor, RL for latent MDPs: Regret guarantees and
a lower bound. Advances in Neural Information Processing Systems, 34, 2021.
12

---

[34] J. Kwon, S. Mannor, C. Caramanis, and Y. Efroni. RL in latent MDPs is tractable: Online guarantees via off off-policy evaluation. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[35] M. Laskey, J. Lee, R. Fox, A. Dragan, and K. Goldberg. Dart: Noise injection for robust imitation learning. In Conference on robot learning. pages 143-156. PMLR, 2017.
[36] J. Lee, A. Agarwal, C. Dann, and T. Zhang. Learning in pomdps is sample-efficies with hindsight observability. In International Conference on Machine Learning, pages 18733-18773. PMLR, 2023.
[37] J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter. Learning quadrupedal locomotion over challenging terrain. Science Robotics, 5, 2020.
[38] Y. Li, G. Xie, and 7. Lu. Guided policy optimization under partial observability. arXiv preprint arXiv:2505.15418, 2025.
[39] M. L. Littman. Memoryless policies: Theoretical limitations and practical results. In From Animals to Animats 3: Proceedings of the third international conference on simulation of adaptive behavior, volume 3, page 238. MIT Press Cambridge, MA, USA, 1994.
[40] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling. Learning policies for partially observable environments: Scaling up. In Machine Learning Proceedings 1995, pages 362-370. Elsevier, 1995.
[41] Q. Liu, A. Chung, C. Szepesvári, and C. Jin. When partially observable reinforcement learning not scary? In Conference on Learning Theory, pages 5175-5220. PMLR, 2022.
[42] Q Liu, P. Netrapalli, C. Szepesvari, and C. Jin. Optimistic mle: A generic model-based algorithm for partially observable sequential decision making. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 363-376, 2023.
[43] Z. Luo, J. Cao, K. Kitani, W. Xu, et al. Perpetual humanoid control for real-time simulated avatars. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10895-10904, 2023.
[44] V. Makoviychuk, I.. Wawrzyniak, Guo, M. Lu, K. Storey, M. Macklin, D. Hoeller, N. Rudin, A. Allshire, A. Handa, and G. State. Isaac gym: High performance gpu-based physics simulation for robot learning. ArXiv, abs/2108. 2021.
[45] N. Messikommer, J. Xing, E. Aljalbout, and D. Scaramuzza. student-informed teacher training. arXiv preprint 241009241, 2024.
[46] Z. Mhammedi, A. Block, D. J. Foster, and A. Rakhlin. Efficient model-free exploration in low-rank MDPs. Advances in Neural Information Processing Systems, 2023.
[47] Z. Mhammedi, J. Foster, and A. Rakhlin. Representation learning with multi-step inverse kinematics: An efficient and optimal approach rich-observation rl. In International Confer- ence on Machine Learning. 2023.
[48] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter. Learning robust perceptive locomotion for quadrupedal robots in the wild. Science Robotics, 7(62)eebb22222, 2022.
[49] D. Misra, M. Henaff, A. Krishnamurthy, and J. Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International conference on machine learning, 2020.
[50] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 2013.
[51] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. Nature, 518(7540):529, 2015.
13

---

[52] A. Mousa, N. Karavis, M. Caprio, W. Pan, and R. Allmendinger. Tar: Teacher-alignee represen- tations via contrastive learning for quadrupedal locomotion. arXiv preprint arXiv:2503.20819, 2025.
[53] Mu, Z. Li, S. W. Strzelecki, X. Yuan, Y. Yao, L. Liang, and H. Su. When should we prefer state-to- -o-vulual dagger over visual reinforcement learning? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 14637-14645, 2025.
[54] M. Mundhenk, J. Goldsmith, C. Lusena, and E. Allender. Complexity of finite horizon markov decision process problems. Journal of the ACM (JACM), 47(4):681-720, 2000.
[55] H. Nguyen, A. Baisero, D. Wang. C. Amato, and R. Platt. Leveraging fully observable policies for learning under partial observability. arXiv preprint arXiv:2211.01991, 2022.
[56] Y. Pan, C.-A. Cheng, K. Saigol, K. Lee, X. Yan, E. Theodorou, and B. Boots. Agile autonomous driving using end-to-end deep imitation learning. arXiv preprint (rXX::/709.07144: 2017.
[57] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of markov decision processes. Mathe- matics of operations research, 12(3):441-450, 1987.
[58] I.. Pinto, M. Andrychowicz, Welinder, W. Zaremba, and P. Abbeel. Asymmetric actor critic for image-based robot learning. ArXiv, abs/17 10.06542, 2017.
[59] N. Rajaraman, Yang, J. Jiao, and K. Ramchandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 33:2914-2924, 2020.
[60] D. Rohatgi, A. Block, A. Huang. A. Krishnamurthy, and J. Foster. Computational-stanl -ssatissiial tradeoffs at the next-token prediction barrier: Autoregressive and imitation learning under misspecification. arXiv preprint arXiv:2502. 12465, 2025.
[61] D. Rohatgi and D. J. Foster. Necessary and sufficient oracles: Toward computational taxonomy for reinforcement learning. arXiv preprint arXiv:2502.08632 08632, 2025.
[62] S. Ross and D. Bagnell, Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
[63] S. Ross and A. Bagnell, Reinforcement and imitation learning via interactive no-regret learning, arXiv preprint 44Xiv:1406.5979, 2014.
[64] S. Ross, G. Gordon, and D. Bagnell. reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference artifi- cial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
[65] S. Ross, J. Pineau, S. Paquet, and B. Chaib-Draa. Online planning algorithms for pomdps. Journal of Artificial Intelligence Research, 32:663-704, 2008
[66] S. Seo, H. Hwang, H. Yang, and K.-E. Kim. Regularized behavior cloning for blocking the leakage of past action information. Advances in Neural Information Processing Systems, 11-2128-2153, 2023.
[67] Shenfeld, Z.-W. Hong. A. Tamar, and P. Agrawal. Tgrl: An algorithm for teacher guided reinforcement learning. In International Conference on Machine Learning, pages 31077-31093, PMLR, 2023.
[68] M. Shridhar, L. Manuelli, and D. Fox. Cliport: What and where pathways for robotic manipula- tion. ArXiv, 10w//119.11. 12098, 2021.
[69] Y. Song, K. Shi, R. Penicka, and D. Scaramuzza. Learning perception aware agile flight in cluttered environments. 2023 IEFE International Conference on Robotics and Automation (ICRA), pages 1989-1995. IEEE, 2023.
14

---

[70] Y. Song, L. Wu, J. Foster, and A. Krishnamurthy. Rich-observation reinforcement learning with continuous latent dynamics. In Forty-first International Conference on Machine Learning. 2024.
[71] W. Sun, A. Venkatraman, G. J. Gordon, B. Boots, and J. A. Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International conference on machine learning, pages -309-3318. PMLR, 2017.
[72] G. Swamy, S. Choudhury, J. Bagnell, and S. Z. Wu. Sequence model imitation learning with unobserved contexts. Advances in Neural Information Processing Systems, 35:17665-17676 2022.
[73] Y. Tassa, Y. Doron, A. Muldal, T. Erez, Y. Li, D. de Las Casas, Budden, A. Abdolmaleki, J. Merel, A. Lefrancq. T. P. Lillicrap, and M. A. Riedmiller. Deepmind control suite. ArXiv, abs/1801. 1118.0060000 2018.
[74] M. Uehara, H. Kiyohara, A. Bennett, V. Chernozhukov, N. Jiang, N. Kallus, Shi, and W. Sun. Future-dependent value-based off-policy evaluation in pomdps. Advances in neural information processing systems, 36: 1999111600,,, 2023.
[75] M. Uchara, A. Sekhari, J. D. Lec, N. Kallus, and W. Sun. Provably efficient reinforcement learning in partially observable dynamical systems. Advances in Neural Information Processing Systems, 35:578-599 592, 2022.
[76] M. Uehara, A. Sekhari, J. D. Lee, N. Kallus, and W. Sun. Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings. In International Conference on Machine Learning, pages 34615-34641. PMLR, 2023.
[77] A. Walsman, M. Zhang, S. Choudhury, D. Fox, and A. Farhadi. Impossibly good experts and how to follow them. In The Eleventh International Conference on Learning Representations, 2022.
[78] A. Warrington, J. W. Lavington, A. Scibior, M. Schmidt, and F. Wood. Robust asymmetric learning in pomdps. In International Conference on Machine Learning, pages 11013-11023. PMLR, 2021.
[79] L. Weihs, U. Jain, I.J. Liu, J. Salvador, S. Lazebnik, A. Kembhavi, and A. Schwing. Bridging the imitation gap by adaptive insubordination. Advances in Neural Information Processing 2021.
Systems, $4:19134-19144
[80] R. Yang, G. Yang, and Wang. Neural volumetric memory for visual locomotion control. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1430-1444 1440, 2023.
[81] W. Zhan, M. Uchara, W. Sun, and D. Lee. PAC reinforcement learning for predictive state representations. In The Eleventh International Conference Learning Representations, 2023.
[82] X. Zhang, Y. Song. M. Uchara, M. Wang, A. Agarwal, and W. Sun. Efficient reinforcement learning in block MDPs: A model-free representation learning approach. In International Conference Machine Learning, 2022.
[83] Y. Zhang and N. Jiang. Statistical tractability of off off-policy evaluation of history-dependent policies in pomdps. arXiv preprint arXiv:2503.01134, 2025.
[84] R. Zhou, R. Wang, and S. S. Du. Horizon- frre reinforcement learning for latent markov decision processes. 2022.
[85] Z. Zhuang, Z. Fu, J. Wang, C. Atkeson, S. Schwertfeger, C. Finn, and H. Zhao. Robot parkour learning. In Conference Robot Learning (CoRL), 2023,
15

---

Contents of Appendix
A Additional Related Work
16
A.I
Theoretical literature
16
A.2
Empirical literature
17
B Additional Preliminaries
18
B.1
Belief states
18
B.2
Decodability and y Observabbiliity
18
C Technical Lemmas
19
D Omitted Proofs for Perturbed Block MDP
23
D.I Belief Contraction
................................
D.2
Approximate Decodability
28
D.3
Misspecification Lower Bound for Stochastic Dynamics ................................
Omitted Proof' for Expert Distillation
31
E.I
Misspecification Bounds for Composed Policies
E.2
Analysis of Forward for L-step Bee.............................
Policies
E.3
Finite-sample guarantee...
35
Omitted Proofs for Reinforcement Learning
36
A Motivating Toy Model for Smoothing
37
Supplemental Materials for Experiments
37
H.1 Misspecification of Decodability in Practice
37
H.2
Imitating a Smoother Expert under Deterministic Latent Dynamics
38
H.3
Omitted Figures.
40
H.4
Experiment Details
A
Additional Related Work
A.1 Theoretical literature
Planning and learning POMDPs. well-known that the planning problem POMDPs (i.e. finding near-optimal policy given the description of the POMDP) is computationally intractable [57, 39, 6, 54], and the harder learning problem (i.e. finding near-optimal policy given interactive sample access to the POMDP) is also statistically intractable [31], without additional assumptions. In light of these results, there has been recent interest uncovering natural assumptions that allow statistically computationally efficient algorithms. On the computational side, [19] introduced the L-step decodability assumption, and under this assumption derived learning algorithm with time complexity poly(X' (X', A', H) via frame-stacking Additionally, [24, 23] derived quasi-polynomile time algorithm for learning in n-observable POMDPs. Computationally efficient learning algorithms also known for certain classes of POMDPs with deterministic dynamics [28, 76] and certain latent MDPs [33, 34], which are special case of POMDPs with fixed latent information.
On the statistical side, [28] derived statistically efficient algorithm for POMDPs satisfying a weak observability condition. Recently, [41, 75, 42, 81] proposed statistically efficient algorithms for POMDPs Predictive State Representations (PSR) satisfying certain low-rank conditions. More tangential to our work, there has also been increasing interest in off polloolcc evaluation POMDPs [74, 83].
Learning with privileged information POMDPs. The most relevant theoretical works ours are recent works that study the problem of learning POMDPs with latent state information (also called hindsight observability) [33, 84, 36, 7]. Of these, [33, 84] are focused on a narrow yet interesting special case of POMDPs called latent MDPs, where the unobserved data is fixed and low- dimensional. [36] show that learning in general POMDPs with latent state information is statistically tractable, in contrast with the situation without latent state information. [7] show that with latent
16

---

state information the sample complexity of the algorithm for learning 7-obeervable POMDPs [23] can be improved from qulsi-polynomial to polynomial. though it is an open question whether this is possible without latent state information. Finally, as mentioned earlier, [7] showed that in perfectly decodable POMDPs (Definition B.3), expert distillation yields fully polynomial time algorithm for learning (for arbitrarily large window size L). Since there is statistical lower bound of 9 2(44) in the absence of latent state information [19], this yields a provable computational benefit of latent state information (and, in particular, for expert distillation), but only for perfectly decodable POMDPs.
Compared to the preceding theoretical works, our work seeks both theoretically and empirically grounded understanding of the relative merits of expert distillation versus standard reinforcement learning. Among works with similar motivations or results, [12] derive expressions for the output of expert distillation (analogous to Lemma 3.1, except they use a slightly different value- based distillation procedure rather than policy-based) and establish sub-optimality bounds for several imitation learning algorithms. However, they do not instantiate these bounds for concrete models, or theoretically contrast with reinforcement learning. [71] establish provable benefits of imitating the optimal policy in a fully-observed MDP (versus learning it via reinforcement learning), but they do not consider partial observability nor the ensuing error due to misspecification. [72] discuss a failure mode of expert distillation in POMDPs when using offline imitation learning to distill the latent expert. The "latching" effect that they discuss is due to conditioning on previous actions (see also [66]) a technical issue that corresponds to why we analyze Forward with L random actions- though it is not clear whether this effect is related to the performance gaps between behavior cloning and DAgger in our locomotion experiments. Finally, several works [2, 79] give examples of more fundamental failure mode of expert distillation: in general POMDPs, the optimal policy may need to take inftommation-aatherriii actions. The classical "Tiger Door" exemplifies this failure mode [40].
Learning with rich observations. There has been extensive recent interest in reinforcement learning with rich observations [31], i.e. where the observation space is too large to enumerate. This line of work has developed largely in parallel with the literature on partial observability, but it is motivated by similar applications as our work (e.g. robotics with image-based perception), and these works formalize the fundamental empirical challenge of representation learning, i.e. "learning to see" [9]. The most well-studied model is the Block MDP [14, 17], which corresponds to perfect decodability with L = I, but is studied in function approximation settings where the observation space is extremely large or infinite, since the problem is computationally easy if the observation space has polynomially- bounded cardinality. While the task of learning in Block MDPs is typically computationally intractable as it inherits the intractable of PAC learning [25], there is by now precise understanding of the computational complexity relative to supervised learning oracles [49, 82, 46, 70, 61].
As observed by [7], there is also provable computational benefit of latent state information in Block MDPs. Recent works [23, 61] showed that the absence of latent state information, learning in @-decodable Block MDPs (where & is the function approximation class) is strictly harder than the supervised learning task of dd-ecodable one-context regression. In contrast, is straightforward to see that with latent state information and a one-context regression oracle, the true decoding function o² E t can be learned up to inverse-poly poolsoapoly error (on average over any exploratory policy). This function, composed with the optimal latent policy, yields the optimal executable policy. [7] formally proved this result with a slightly different (multi-class classification rather than regression) supervised learning oracle.
A.2 Empirical literature
Applied methods that learn with privileged information. Privileged information has been widely used in training policies for real-world POMDPs, such as in robotics and autonomous driving. The most prominent and successful method is expert distillation [56, 9. 37, 48, 32, 85, 80, 69, 21, 26, 10]. First, one trains an expert policy with access to privileged information
either the latent state in simulator [9], or observation data from more expensive sensors that will not be available at deployment [56]. Second, one trains an executable policy by performing offline or online imitation learning with respect to the latent policy. [56] also observe empirical benefits of online imitation learning compared to offline, which is corroborated by our results. While there are also notable successes of using RL without privileged information [1, 43), some of the works observed that RL without privileged information failed to learn locomotion in their environment [37].
17

---

Motivated by the theoretical failure modes of expert distillation in the prequel, there is also a line of work in the middle ground between expert distillation and RL without privileged information. that seeks to avoid these failure modes while also improving the convergence of standard RI.. These hybrid methods include Asymmetric Actor-Critic [58], and more broadly are described as asymmetric learning [58, 79, 78, 55, 77, 67, 45, 52, 38). While there is some evidence that an algorithm inspired by Asymmetric Actor-Critic may enjoy an improved Latisticalcoompuaationall trade-off for poobserablle POMDPs [7] (compared to the best-known algorithm that does not use privileged information [23]), the theoretical foundations for these methods remain otherwise largely unexplored.
Learning with and without privileged information. In addition to the previously- mentiondd ablation experiments [37], recent work of [53] conducted controlled comparisons between expert dis- tillation and standard RL on simulated locomotion and manipulation tasks, with the goal of providing heuristic guidance on when to prefer expert distillation over RI. without privileged information. They found that expert distillation converges faster. They also classified tasks as "easy" or "hard" based on the convergence speed of standard RI., and suggested that expert distillation performed better on the "hard" tasks.
Improvements to expert distillation. Recall that a key benefit of expert distillation for POMDPs with rich observations (e.g. as found in robotics with image-based perception) was that it avoids performing reinforcement learning on the digh-dimensional and complex observation space. In contrast, most of the meriiouslymmettioned works on asymmetric learning use exactly such an algorithm (e.g., as the "Actor" component in Asymmetric Actor-Critic). An exception is the method of [78], which is a variant of expert distillation that iteratively refines the expert with the goal of decreasing misspecification. Our smoothed distillation method (Section 6) can be thought of as a more lightweight approach that refines the expert in one shot. As mentioned in Section 6, it is also similar (though not identical) to several noise injection methods in imitation learning [35, 4].
B
Additional Preliminaries
B.1
Belief states
The following operators describe how belief state evolves more information is revealed. Definition B.1 (Belief state update [24]). For each h E {1....,
......H), H), the Bayes operator BB,
((S)) x Xx. + ((S)) defined by
Bb (SN) = On( sn, sa)D(sh)
EENES, Ox 2 2n)b(2))
For each h E HY, the belief update operator U₁ A(Sh-1) x A + ((S)), is defined by D₁ (b: a,-1, ==
b; 2n) where (a) denotes the real-valued |Sal x |Sh-1] matrix of latent transition probabilities from step h 1 to step h under action Oh-1-
The following definition of an approximate belief state is analogous to the inductive definition of a true belief state (Definition 2. 2); the only difference is that it updates based on a window of the L most recent observations and actions (Ih- (Ih-L+1:h, Lh- rather than the entire history, and is additionally parametrized by a distribution D (which represents the prior on the latent state at step h L).
Definition B.2. For a window length L > any h > L, and prior D A(Sn-L), the approximate belief state is inductively defined as
by (Ih L+1hh O4- 1:h-1; D) == Un (b,"" 141hh- ( Qh- L:h-2;;; D), ah-1. Z1.) where for L O, ba, D) = D. For h S L, the approximate belief state is defined to coincide with the true belief state.
B.2 Decodability and --bbervabillity
For completeness, include the definition of (perfect) L-step decodability from [19].
Definition B.3 (L-step decodable model [19]). A POMDP is said to be L-step decodable for each timestep h E [H], there exists deterministic mapping Φn -hh-Lsh Lih Ab - Sa. such that for any admissible trajectory T (8, x. a) 1.h (i.e., a trajectory that occurs with positive probability under the uniformly random policy), we have Sn. on Lihs Oh Loh-1).
18

---

Next, we introduce relevant definitions and results relating to 7-observable POMDPs from [24, 23]. Definition B.4 (7-observability (24)). Let y E (0, 1). A POMDP is 7-observable for any h E [H] and distributions b, E (SS)), holds that
|0 - 0 2 211lb bll1
where O2 E X.Xx is the observation matrix defined by (Oh) == On (x (s.
The algorithm of [23] for learning --observable POMDPs in quasi-polynomial time requires bounding a slightly generalized version of the belief contraction error defined in Definition 3.2. We state this version below.
Definition B.5 (Generalized belief contraction [23]). Let E (0.1) and L E N. We say that POMDPP satisfiex (e; (b, L.)belief contraction if the following property holds. Let n be an executable
policy, let h {L + 1,... H3, and let D,D' A(S
If
D S 1/6, then for any fixed
history (Ii:h- L, (1::----)) holds that
E- EET [[]b,, (#R-L+15k Gp L:h D') bank (Th- bith Oh Lah 1; SE
where the inner expectation is over partial trajectories (In- L+1h,, an L:h-1) 1) drawn from P by initializing latent state Sh-L step h L,, and sampling action aj. n (Ticks 01:k-1) at each ---Le L h.
For context, see [23, Theorem 6.2] for the formal statement that y-observability implies (c; d. L)- belief contraction with L ~ 7 log(1/ (=Φ)). Definition 3.2 is a special case of the above definition, with D' = b L (IIAA-L, -11) and D == unif (S..
Theorem B.1 ([23)). There is a constant C* with the following property. Given E, 3, 0, EN,, and a -observvable POMDP P, set Φ o= C= IfP satisfies (#; d, L)-belief contraction, the algorithm BaSeCAMP [23] produces an executable policy to that satisfies
J(TT) ((t) I E. poly(S, (H,
with probability poly((X S. - 1
least 1 B.
Moreover, the time complexity is
Proof. Immediate from inspecting the analysis of BaSeCAMP [23]: while their analysis sets T= log(1// the claim that any y-observable POMDP satisfies (e; Φb. -.)-bllief contraction with that choice of L). Thus, is sufficient to choose any L for which (e; Φ, Le-belief contraction holds.
the only place this is used in the proof is invoke [23, Theorem 6.2] (which
C Technical Lemmas
Lemma C.1 (Data processing inequality). Let S, T be sets, let p. E A(S) be distributions, and let
K:S A(T) be conditional distribution function. Then
TV(K op, K o S TV(p, g).
Similarly, i < g, then
o K o
P
Proof. The first inequality follows from the fact that total variation distance is an f-divergence. The second inequality can be directly checked: for all y T.
(K o p)()
EKO x)p(k)
[<)l)))(()+ - q
(K (Ko
00 WES
as needed.
19

---

Recall that a policy is executable if the action distribution at any step is determined by the ac- tion/observation history (note that latent policy therefore may not be executable). The following lemma, which was implicitly used in prior work [24], verifies under any executable policy, the conditional distribution of the latent state given the history the true belief state.
Lemma C.2. Fix any step h E [H] and executable policy л. Then
PP [sn (I ba(Tis, a1 (8h)
and, if 1,
Fa [a(rn T1 = (0% (as-)) by (T alsh (1))))))(2a))
for any actionfobservation history (Zish: 01:h-1) and latent state Sh-
Proof. We prove the first claim by induction on h. It is clear that [" | x 0 (z) B1 (1 )
s1 )P(ss xc (x1) (51), where proportionality is up to factors independent of 81. Since 1 x1] and by (z1) are distributions, it follows from the proportionality that they are equal. Now fix any E .2..... H} and assume the claim holds for 1. Let ($1:h, Z1.h. 01:h-1) be random trajectory drawn from P", i.e. generated via 8), ~ (a(s)-1. 0n-1), Ih (s,), and
[Z1:kh 01:h-1) (since we assumed that ı is executable, the action distribution does not directly depend on s1s)). Then,
pd [9h 11sh, 01:A-1]
I (11h Tish, 01:h;
81th-1
Σ
(1 (1.a2) 8h-1, an 0n-1,,n-110aa sh) 88-
IP
81sh
Σ
PP
an-1, sR)
0%h
shh)
P(sh (h--1,ah1)
ps 11
8h-1
81:0-2
x (%h |sh)
Σ P[sh 88- a4
[hh-1
11:h-1, 01hh-2
8h-1
= =0 (xt (8h)
Σ P(sn 1h-1, an-1,
(2 (1:h-1)(sh)
where the penultimate equality uses the induction hypothesis and the final equality uses Eq. (1). This proves the first claim. To prove the second claim, observe that by similar argument to above, for any h > 1,
IPT F1:h-1, 12 α Σ P(sh s 9h-1..0-1]0b 1 (01sh 0.h
so that 1a [sA T1:h-1, 11:-, = (Pn(ann1)) -
But then
1sT [r 11:h-1,,41h--1 x
pat 1815h F1sh, 01:h-1]
Σ Og Sn)
Σ
p Pia
Sh.
81:-11
x
Σ DA (N))
111h11, 01h-11
Therefore Pd [ar 1iih-1, a1=- = (0) (a (T as claimed.
We will also need the following variant of Lemma C.2, which shows how approximate belief states arise as conditional probability distributions:
Note that this not true for all policies, since a latent policy could reveal the latent state (or, more generally, bias the conditional distribution) by its choice of action. This issue underpins the "latching" effect observed in behavior cloning of privileged experts [72].
20

---

Lemma C.3. Fix any h E [H], L E fO....,h h
- 1}, and executable policy π where Th-el-
Fi:h-ts -1:h-t-1) is determined by (I L+1:h-f On Lch --h- for all [L]. Then
[*(8h Th 1:h, Oh 1-A-1] = by h 1+1k ag L.h dh-1)-
Proof. We induct on L. If L O then, for any h E [H) by definition Ip [p*[sh] (s) = b% (0; d (sh). Fix any L > 0 and suppose the claim holds for L (for all L Then for any h L,
p sh
Th L- lsh On Lah-
Σ
PPT (8 8hh Lih: -+ -
Lih-1
Σ
IPT
Th- - 2 8h-1, an On sh)
Sh. Loh
Σ
P -hh
Lih- 1 2 [ (4)
8h- Lsh-1
(xn
Pn(Sa 9h-11,h-11B 244
sN)
(nt
sh)
Σ Ph(sh Sh-1,,0-1]P 1
8h-1
=On(
8h)
Σ Pa(sh 8h-1, ah
1b apx
( (1h-L441h-1-) 17 (8h-1)
(1 (Th-L++1:h L.h L1h-11hh1 (88)
by the induction hypothesis and the definition of apk (I (#h- 11 ah- Lch-1i dz
The following fact is well-known.
Lemma C.4. Let n² be the optimal policy of the POMDP, and let llatent be the optimal policy of the MDP. Then we have that
J(T") S (sx lateett.
Proof. We prove by proving
general result. Consider any POMID P and its corresponding
MDP M, for any latent policy _latent, we use Q M:M: Sh x AA. + [0, 1] to denote the Q-value
of following lateent in the MDP at timestep h. We use 0) 2 A [0, 1] denote the
Q-value at timestep h of following executable policy π. We will use QP and Q. denote the optimal POMDP Q-value and optimal MDP Q-value functions. Note that Q" satisfies the following
optimality equation, for any Tith, 01:h, we have
Qh ((rrs) 01.h (1:h-1), 1),
Σ (b((Fissann-)) (ohh,an))))) an) + > P(an+) Tish a1a) max (1a an+)), in)))
1h
where P(EN+1 Fishs a1:h) = E...h (s Fish, 41sh PP 8h, an On ( 8441).
Note that in this case, F1:h, 44-1 can be summarize as by (1 as a)=1); and thus given any belief bn (SR)). we will abuse the notation and define
Qh (bn, and = Σ (s) an) + Σ by, an) max OP (ba+1, ah+1),
oh
Zh+1
where bn41 = Un+i
an, an I.)1). Similarly, can define
(bn. an) Σ (n on).
Note that in this case, let n² be the optimal executable policy, and let latent be the optimal MDP policy, have that
J(x*) Ex, [Q (b xt (()))))))=(())) (x1))),
21

---

and
I(platent) = Esg (2)((1)) nT latent (s1))]-
In the following we will prove that, for any timestep [Hf] for any admissible belief bn E A(S)). fix action Oh, we have that
(bn, an) 2 Qh (b,, an).
We proceed with induction. For h = H, we have
(bH an) = Σ ( Rn(sH, = Qi an).
Then assuming Qh (bn+1, an+1) 2 Qh (bn+1, an+1) for any admissible b141, we have for any admissible bn and action an.
Q (b,, an) = Σ bn Rs (sh, an) + Σ P(In+1 by an) max Qh4 (bu+1, ab+1)
an+1
by (sh (sh,
Σ
P(rnt1 byy ah) max Q 1 ah+1)
antt
aht1
Σ
(a an) +
Σ P(ant1 bn,an)
Σ
I max Q (sh+1, an+1)
84.
2h41
th+1
For any function f that only depend on the state, we have
Σ P( bh, an)
Σ
bn (n+2))))))(((n+t)
8h.11
sh+1
On(ent1 (h+1)) E., Pu(SNt1
8h: an)o((s)) slont))
Σ P(ant1 bny an)
Σ
P bn. an)
2h+1
sh+1
Σ Σ On+1 sh+1)
Σ
Pr (s sh, (n) (sh+1)
2h+t1 8h+1
an
= =E PA(SNt1 8h: (s)))())))((())))))
Sh,8h44
This gives that
Q (bn, ax) < Σ ()())) +
Σ Pa(sn41 Shy (n)b max (541, ap+1
Σ (sn) 8%
Ra(sn: +
Σ
Pn(sn+1 Sh, an) max QM ($)+1,
( aa+1)
axt1
8h+1
Σ by (sn))( (MM,)
Q (bn, an)
Finally, we conclude the proof by noting that
J(m latent) E,, 10, (81, n latent latent(sx))
E,, [max (,, (s1, max
Qi (bb, 2 max Qf (br,a1) J(m²).
8,
a1
We will need the following martingale bound to analyze belief contraction error and decodability error in the perturbed Block MDP.
22

---

X2 be a non-negative supermartingale with B[X,] I S and Pr[Xn+1 eX, [x,] S E almost surely for all 0 S n < L. Then
Lemma C.5. Fix E (0.3-%) and S > 0. Let Xo....,
([, 2 3 L/
Proof. For any integer S n S I and any integer k; define f(n, k)) == Pr|c*+1S < xx, S S). We prove by induction on n that f(n, k) S =3"e(m-k)/3 If n 0, then the claim is trivially true for k Z 0 since [(n, k) S 1 always. For any ho < O, by Markov's s inequality,
X
ʃ(0, S Pr[Xo > .+1 5] 5
c E = k-1 S k/3
For any 0 < n I and integer k; we have
f(n,k) k))
Σ
Prie < X, S | etts < Xn-1 S E'5 f(n 1,6)
1
Σ 1, - 1,k) =ff(n - 1,++
Σ
c f(nn - 1, (4)
fm
where the inequality uses the following two facts. First, for any l 2 k,
Pr|s*+1s < Xn S S e < X S <ESS] S Pr[X, eXn-1 1 < Xn-1 SE'5| by lemma assumption. Second, for any & k
Pr|c*tls < X,, S S e s < x S e5$) $ Pr[X, > 5 atI-tx,--... l < xn S Sc's
since Xo...., XL is a supermartingale. Returning to Eq. (4), we get
f(n,k) k) S
Σ f(n - + ef(n +5
1, + + 1, +, 1) Σ
gl-k-1 1,
t0
k=
k-1
<
3n-1 10-1g(n-1-9)) 1-1/33 3 1n kn-
+ 3 11 k-2/33
3
k- (tn-----))
k=
1 (1-L + 2/3 + 1/3
S 3" (nn-bi//3
1 1/32/3
2/3
< < kn3333
where the final inequality holds since ε S 1/64. This completes the induction. Next,
[imin(X,:S S)] < Σ S. f. + Σ
E=
8
534S.
(LL-8)/3
Σ
t=
(c(++1)/3
E//3
<34s.
+
1- e1/3
2/3
as claimed.
D Omitted Proofs for Perturbed Block MDP
Below, we restate the definition of a 5 5-perturbed Block MDP. We then prove our main theoretical results for the perturbed Block MDP. In Appendix D.I, we prove Theorem 3.2 (the belief contraction result, restated as Theorem D.1). In Appendix D.2, we prove Proposition 4.1 (the decodability result for deterministic dynamics, restated as Proposition D. Finally, in Appendix D.3, we prove Proposi- tion 5.1 (the misspecification lower bound for stochastic dynamics, restated as Proposition D.2).
23

---

Definition D.1. Fix parameter 8 > O. A POMDP P is a d-perturbed Block MDP if. for each h E [H], there Oh, En :Sh A(K)) such that On Sn. ((X)) satisfies the block property [17], i.e. On(: st). On(- 5%2) have disjoint supports for all sh, + s/ and moreover the emission distribution On at step h can be decomposed as follows: (n(an (h) - (1 (1- 61-6)0n sh) + E' (an. sh).
For notational convenience, for each E Nn let ((x) Sn. be the unique state for which C₁ (z 6(z)) > 0 (or arbitrary, if no such state exists).
Definition D.2. For any h {H) b Sh and In On. we write
Cn b)
Σ
Op(on 2x))))))
We similarly define E, (zk b) and (n 16)
Notice that (z)
(z b) b((()))))))))))))))))))))))))))) (n ((()))
D.1 Belief Contraction
In this section, we prove Theorem D.I, a slight generalization of Theorem 3.2. The proof broadly follows the proof of belief contraction for 7-observable POMDPs [24] (of which 6-perturbed Block MDPs are a special case - see Remark D.1), but since we require a stronger bound, we must modify the argument.
The basic idea (and main technical difficulty) in [24] is identify a monotonic transform of an f-divergence that multiplicatively contracts in expectation under the Bayes operator (Definition B.1). In their case, they show that (BL(B,, (b: 2 ) || B, (b'; zx))) contracts by roughly a constant factor (relative / (b || B")) in expectation over Iy, (- b). That is, updating the true belief and approximate belief by an observation drawn from the true belief tends to decrease the KL-divergence. Updating the two beliefs by applying a transition matrix cannot increase the KL- KL-divergence since is an f-divergence, so an iterative argument (alternating between observation updates and transition updates) proves exponential contraction of the belief error.
However, we would like to prove contraction by poly(5) per step. and the following example seems to present obstacle to proving such contraction via KL-divergence. It also presents obstacle to directly analyzing TV-distance.
Example D.1 (Failure of contraction of TV and KL). Fix >> 0. Let S = X' = (0.1) and let O : S ((X) be defined by Ox x) = 5. Define b (1, 0) and b' (52, 1 - -82). Then
holds almost surely over ~ O1- 6) that:
TV(B();)) 2 1 even though TV(b, 6') S 1.
KL(B(b;>) B();,)) 2 log(1/0) even though KL(b || 8') < 2 2ogg(1100)
To resolve this, we observe that when the TV-distance fails to decay, the density ratio [|b/b//lc does decay. To formalize this, we study contraction of the following error metric. While we cannot show that it contracts by poly (8) in expectation, we can show that it contracts with high probability; this is the content of Lemma D.2 below.
Definition D.3. For distributions b, b' E A(S) with b < b. we define
b 17
:V0))):=T(((6))) D.(1))) = TV(b, b):
Note that the above metric upper bounds TVddistance, and is upper bounded by [|b/b'|l Also, as the product of metrics that satisfy the data processing inequality (Lemma C.I), also satisfies the same incquality, so it cannot increase under application of (even stochastic) transitions.
24

---

Lemma D.1. Let h E [H]. b E ((S)) with b < b, and fix E On. Then
(b; æ)
= On(x b))
(b(
02(2 b) 8
Proof. We have
x)(
02(2 8)6(s)
Og 8)
max SES,
(b/
On b)
(x (s)
b(s)
On (8)
max
SES, b((s)
0 (6]
(z 16)
|
On ())
claimed.
Lemma D.2. Fix h [H] and b, V E A(S)). Draw Onl b). Define random variable
B(b;
ç := D. (Br (B) (b:=))) BV(((())).
(5)
B ;z)
00
Then [[g] S (bllb') and
Pr
s 281/3
Proof. First, we compute that for any fixed x E Xh.
TV(B(b; B(b':=)
b(s)
(ss)
= ΣΣ On s)
On b))
On(x (b) (*)
sES,
b(o(z)) b(((z))
b(s) On(o 6)
(((s) Og (x 6))
(1 (1- (1-8) d()))
+ Σ Ex s)
(n(x (b) On(a b*)
SES,
by Definition B.1 and Definition D.I. We bound these terms individually. To bound the first term, since (z b) (1 ()b()())))O.)z) (xx)) + (x b) and O₂ (z B/) = (1 8)b/ (6())) (x ((x))+ + (x B'),
M((x)) ((((())
(x(r ((x))
(g b)
(n bb)
((o(x)) 6') (((())) (6)
= 6o ((x))
On b) 1/)
[b((())) - (((())) En (6)
b((())) Ex b) En 8I
< 6x (x ((x))
+
0g 1)00 ( b))
On b) B)
s (0((te) o(x))
[b((x)) - (o(x)) (x ())
Ex 6) - Ex 67]
+
(7)
Og 6) (a b))
(1- -0, b)
where the second inequality uses the fact that On (x 6) 2 (1 6)((6())) d(z)). To bound the second term,
b(s) On(x1 b)
(s(s)
Ex (b(s) - 1((s)]
Ex s)b(s)
Σ En SESh
(x (x
8)
S
Og b)O by) 10 (b) - 0,(x 18
(x
V)
Og (xr 8')
SE
SESh
Ex(x 8)
En b)
On(x b. (b(s) - -b(s)]
+ On 1) 8J
10x(= () - 0x(x (8)
S
(8)
25

---

Let & be the set of x E Xr such that (x b) < 8 On (5) satisfies the following bound, where the expectation over the randomness of 02 (- b):
b). Then the quantity & defined in Eq.
Bx
[ x
E]|
Σ aEE
(b( 00
b
Σ
On(x (b,
JEE
b
En (x b)
(1-8)0 Σ
Øz(2 ((x))
((((x)) - d'(((2)) + Σ
Ex(2 (6) - Ex B1)
Og (x 6)
ZEE
HEE
En (z b)
+ 0
Σ Σ
En s))b(s) b((s) + 8 Σ
[0 -0)) (1xx11)))
On (z
66)
3E SESH,
ZEE
(1 (1-8))2/3
Ün(2 [+==))((((())) -b))))=))))(((()))) ((((x))1 + Σ EB 6) - En(o B')l
DEE
DEE
+ Σ Σ En(x s)]((s) - bb(s) 82/3
+82/3 10 (6) - On(x (o 63)
EE SES,
3E
<88 TV8 b)
where the second equality is by Lemma D.I: the first inequality bounds each term TV(B, (b: x). (b'') using Eqs. (6) to (8); the second inequality uses the definition of E; and the final inequality uses the data processing inequality for kernels Ey and On. Additionally,
On b) < 84/3 < 8//33
Pr[x & E] = Σ
Og 1b)
Σ ZER
Oz b)1
En b) 82/3
(x b)
1EALNE
ZEX
(10)
since Ea(. 6) is a distribution. It follows that
Pr { > 4/////////// TV
S Pr 51fx E E| 48V/8VV(
+ Pr(a & El
8'
b4
25//3
where the second inequality applies Markov's 's inequality to Eq. (9) for the first term, and Eq. (10) for the second term. This proves the second claim of the lemma statement, To prove the first claim, note that Ex b) < 18-1 O0
18-10, (z b) for all x E Xn. Thus, modifying the calculation from Eq. (9) (this time summing over all a E Xr, instead of x E 8) gives
(Bb; x) B(b;:))
<bTV(b,b) 1U4
[[E]=
Σ M
(z (6:)
as needed.
The following result, which shows that the error metric decays with high probability under belief update, is straightforward consequence of Lemma D.2 and the data processing inequality.
Corollary D.1. Fix h E f2..... H}. b, D' E A(S)-1) with b < V. For any action an-1 An-1- with expectation over Frp ~ (0₂) Pr, (an-1) b,
E DD,, a2 2h U[, (b': an-1, 2n)] < 4D.
and
Pr|D. an FAh || U (V'; 0h- xn)) > 1/3 D. (b]lb') s 281/3
Proof. By applying Lemma D.2 with PA (a. )) b and (a)))))) b,
E[D. (b; an 1. ([Un (1 am))1
(on, DD_ (Ph by by (Pa (1zz)))
4D, (Pn(an-1) (((P) -b)
4D,(6)1))
26

---

where the final inequality uses the fact that (V(Ta(a) b, Tx(o)- TV(6, 8) and
[o)
Ta
by the data processing inequality (Lemma C.I). Similarly, the second claim of Lemma D.2 gives that
&
24) Pr 1.
3 D.PP(((-)))) b ((x 81) - 251/3
and therefore
Pr (v: -0- 48 48%
s 288//3
by again applying the data processing inequality as above.
We now can prove our main belief contraction result (which includes Theorem 3.2 as a special case) by iteratively applying Corollary D.I. The main technical detail is to verify that the observations are indeed drawn from the true belief states, which relies on Lemma C.2.
Theorem D.1. There is a universal constant CD.1 > 1 with the following property. Fix an executable policy π, indices < h < h h L S H, and distributions D, D' E (())). Then for any partial history (Ii:ho 01:h-1) it holds that
D'
E., D E (TV((bb) apx
b (1h41hh 1hb4L-1; sn] S (CD.18)1.10 1/9
D
where the inner expectation is over partial trajectories (2h+1sh+L (hch+L1)) drawn from policy with the environment initialized in state Sh, at step
As a consequence, it holds for any partial history (#ish, 01:k11) that
by by ( a1:b)
E" [TV L (F1s+ 01.4+-1)) big HLL ( - (CD.18)4/9
where the expectation is over trajectories drawn from conditioned on the partial history (Fish 11)
Proof. We first observe that the second claim follows from the first claim by setting D' by (Iii:h; 01:4-1). Indeed, conditioned on (Mish, 01: the law of 8 is precisely by (Zish 01:h-1)
(Lemma C.2), so drawing (#++15h4 1..b+1.-1) conditioned on (Xisk, 01:h-1) is equivalent to first drawing 8n ~ by ( d1:b-1) and then drawing (#h+115+L, aa-h-L-1 from the POMDP initialized at 8h. Moreover, by the recursive definitions of and bapk we have
b l. ( (144L11)
b (I+ an.h 00 ( (11-).1111)))..
It remains prove the first claim. Fix (#1.h, 01:h-1). For 0 St L, define the random variable
X, : 4. (Th+
(1 15644, ahch+t-1; D') Ibb k+
apx ( (I+4 (h:h4t-1;
where (34+1:ht+ 1hsh+t--1 is drawn by sampling 8) ~ D', initializing the POMDP at 8h, and then rolling out with policy (to be precise, the action distribution step h + t is æ (1 (1:+++1))) Note that the roll-out does not resample Th. which is already fixed. Recall that (p(gg) ==
TV(p, 4) ||||
so that TV(p.g) s (pll)) I
for any distributions p, q. Then
Xo = D. apx (0;; b (0: D))
= (D (D)
D'
<
D
Moreover,
( (hght (
< min (ii(D. (TT D') (tD (1 ahth+
< 4 min(X,,1)
(11)
27

---

since gV < 1 for any distributions p. Fix 0 < t < L and condition on (1h+155tt-11 4psh+t-2), which determines X,-1- The conditional distribution of d is then II (1-++-2)) and for any fixed 0h-t-1 the conditional distribution of #h+t is by Lemma C.2 (applied to the mod- ified POMDP that is initialized to a latent state 86 ~ 'D' immediately before the action dn is taken; for this POMDP b bpp
apx (Ow+e) (Pa+e(ah+t-1)- 1 ( SEEh+LL44t-L.hh4-222
D') the true belief state). Recall that by definition,
b (2h- 0:h+t::: D')
U bittttt 1 (1h 2h DD), -h
and
D), batt (1h+1sht -1 D) Un+++ (b 11 -h: 1,
By Corollary D.I, it holds in expectation (resp., in probability) over 24+1, conditioned on the prior history, that
E| x = 4 (b apk (D (Th+1sh+ 11:b+e-1: D')]: b' (0
apx
D`) h ( Ohchtt D))
X
and similarly
Pr[X, x1,3 281/3
Since these bounds hold for any fixed ohtt-1 An. they also hold in expectation (resp., in probability) over the joint draws of a1+--1 and 2h+z, conditioned on any realization of
(Ih+1:sh 1sh+--11 (bsh++122) Thus, E[X, X,-i] S X,- and Pr[X, 81/3 X,-1 X,-1] S 28 both hold almost surely. We can now apply Lemma C.5 to the sequence (Xo....: Xr.) with parame-
ters S =
and 6 == 282/3; we get that D'
D
D'
A(min(X,, 1)] < [llmin(x,, s 2. 22.322//382..
D
Combining this bound with Eq. (11), and setting CD.1 to be a sufficiently large constant, completes the proof.
Remark D.1. Any 5-perturbed Block MDP is y-observable with y 1 28 (Definition B.4): for any h E [H], we have On, = (1 - O) Sh. and thus given any b. b', we have
||0 1,,1 || 0)0 8') F 11|1,
z (1 5) | (b ||]|, - 6 1 (b (b-61 (b-b)
2 (1 6) |b - 6'111 - E Mlpp bbb 6'1l2
10-11,,,
2 (1 26) b- b/11,
because ÜA satisfies the block property. was shown in [24, Theorem 4.7] that, for any 7-observable
POMDP P. the belief contraction error can be bounded as ct ccontract(Tr (T;; L) S (1 40)2 O(S). However, substituting in == 26, we see that due to the constant factor of 240 this bound does not asymptotically improve as 5 decreases indeed, it is never better than (1 11/2202-- ( and moreover is vacuous for L = o(log S).
D.2 Approximate Decodability
In this section we prove Proposition 4.1, restated below Proposition D.I, which states that for 5-perturbed Block MDPs with deterministic latent transitions, the decodability error decays exponentially. The proof is somewhat analogous that of Theorem D.I; the key difference is that the claim that the transitions do not increase decodability error is only true for deterministic transitions (whereas the analogous claim for belief contraction error unconditionally true).
For notational convenience, we make the following definition of the "Loc variance" V.o for a given distribution b.
28

---

Definition D.4. For any set S and distribution b E A(S), define (b) = 1 - 116|l
The following lemma shows that the fox variance contracts by poly(6) with high probability under the Bayes operator.
Lemma D.3. Let å > O, and suppose that P is a ô-perturbed Block MDP with deterministic latent transitions (but potentially stochastic initial state). Fix h E [H] and b E A(S)). Draw x Oal b).
Then E (b; & min(V.>(b),, and
(B.(c(B)()) > V (b) S 361/3
Proof. Pick any s* Sj such that ba- lib] and hence Esesh ((or)
((a+) b(s) (b). Then
On 16] (1 B1
Σ
=
SESA
IEA,
Σ
min (On(x b) - b(s)0n(zz ()) SES,
Σ min sES,
E
b(s')O,, Is))
(12)
('ESA(s)
where the second equality is by the definition B3 (b; = (ole) Oxtz|b)
(Definition B.1). First, Eq.
(12) implies that
V (Ba (b,+)) & Σ Σ (()))((=(8)=
Σ
((8) = Voc (b),
Vox
zEX, d'ESu(le))
s'ESMMo">
where the first equality uses the fact that (.(( (') is a distribution for any fixed s'. Next, Eq. (12) implies that
E (Bn, (b; < Σ Σ
(x)))O(()) s')
zEZ2, o' S'E (((())
8 Σ Σ
b(s')E(()) (s)
8 Σ b(s')
Σ
En(z) |s')
S'ES
< 8 Σ
b(s²)
S'ES,
< 6.
(13)
This, together with the preceding bound, proves the first claim the lemma. Now consider the event that d(x) s* Since (x b) 2 (1 - 6)6(6(z))0..az ((x)), we have
Pr(o(r) # =1
Σ (100)-0000)00)11---0000---------
< =
5+V (B).
==))
(14)
29

---

Moreover, by an analogous calculation as Eq. (12),
(B. ==1]]
E
On(r (b) (1- (1 max BA (b;
=EXr)p())=s*
Σ
min (On (r b) - b(s)0s (s)
sES,
(()))
Σ
On(x b) - b(0))(((((( ) (2: 88))
Σ
Σ
(z))n(()))
(b(o) a (
bx 1s)
xEXr:o(a)= (65)
S (b)
follows that
8//3V (b) - Pr[V (Ba (b)( - =5] (00 s
$ 2/3 + + Vo (b)
by Markov's inequality and Eq. (14). To conclude, we distinguish two cases. If (b) 81/3 then we get
Pr[V (B&, (b; x)) > vx (b)) 2//3 +8+ 52/3 & 331133
as needed. Otherwise, V- (b) 81/3, so
Pr[V (B; x)) > /v (b) S Pr[V (Bx(b))) 82/3 82/3 by Markov's inequality and Eq. (13). This completes the proof.
Using Lemma D.3 and the assumption of deterministic latent dynamics, it is straightforward to show that the fox variance contracts by poly(8) with high probability under the belief update operator:
Corollary D.2. Let > 0, and suppose that P is d-perturbed Block MDP with determin- istic latent transitions (but potentially stochastic initial state). Fix h E [H] and b E A(S)). For any action a;-1 E Ar-1, with expectation over Fh ~ (0a) (P b, it holds that E.Vo~ (n)) < Vo (b)
and
Vo (U, (b; an-1, xN)) > 81/3 [x)) [b)] S 381/3
Proof. From Definition B.I, have for any 2n that Un (b; ah-1, 2n) = (P, b; 22)) Applying Lemma D.3 to the distribution Pú (Q (observe that F4 is indeed distributed according to (.(( (an-1) b)), we get E.V -U, an-1, [)] & Vo (Px (a
and
Pr[Vac (U, (b; on-1, rn)) > 5//3 (P b)] < 3/3
To complete the proof, it suffices show that V (P (0) b) S (b).)). Indeed, since the transitions are deterministic, the matrix (a)-))) E S S, il satisfies that every column is standard basis vector. Identify any s* E Sh with b. = ||b|| c. Then there is some E S₁, with
FA (ah-1)an..* (s) s* a4-1) = But then the entry of PA (ap-1) indexed by sh, is least byt So indeed Vx (PPa(an-)) - S (b).
We can now prove the following restatement of Proposition 4.1.
Proposition D.1. There is a universal constant CD > 1 so that the following holds. Let ô > 0, and suppose that P is 8-perturbed Block MDP with deterministic latent transitions (but potentially stochastic initial state). Fix any executable policy a and index h E [H] holds that
E (by (11A..(1AA..1A11)))) I min(ō, (CD. (CD.18)(--119))
30

---

Proof. Define a sequence of random variables X, := Vo (bx d14-1)) for S t S h, where (# 01.b-1) 1) is a random trajectory drawn from policy æ. We have X1 - 1 almost surely. By the same argument as in Theorem D. (except using Corollary D.2 rather than Corollary D.1), we have for all 1 < t S h that E[X; X S X,-1 and Pr[X, > 81/3 X, X(-1] S 36 hold almost surely. Thus, Lemma C.5 applied to (X,,...,>X) .,) with parameters S = 1 and E = 36 implies that
t
E B[XA] = E[min(Xx, 1)] < 2- 2"3" 3 11/3//111///1111111 1)/9 S 6C (h- 1)/9
so long as CD.1 is sufficiently large. Additionally, we know that b1 (m)) = IB, (PP1; so
(B1 E[X1] = EE" VV (B:PP)())) < 8
by Lemma D.3 and the fact that 01 has distribution Or( Pt). Thus, [[ S 6 for all 1 stts.. h.
D.3 Misspecification Lower Bound for Stochastic Dynamics
In this section we prove the following restatement of Proposition 5.1, which shows that in 6- perturbed Block MDP with general (stochastic) latent transitions, the misspecification of the optimal latent policy with respect the class of executable policies can be as large as (2(6H) (for 6 < 1/H). This implies an analogous lower bound on decodability error, i.e. it cannot improve exponentially as h increases, unlike the case of deterministic latent transitions. Moreover, shows a fundamental source of (rrizzondeeendeen) error that is not mitigated by increasing the frame-stack L: since the following bound applies all executable policies, it also applies the class of L-step executable policies for any L.
Proposition D.2. Let ô >> 0 and H E N. There is ô-perturbed Block MDP P with horizon H such that the optimal latent policy glatent satisfies
min
TV(P Won xell
PP") 2 ((min(1,8H)
where II is the class of executable policies.
Proof. We define P as follows. For all h E [H]]. define the latent state space and observation space to be S₁ == Xr == f0, 1}: also define A, := {0, 1). Let the initial distribution and latent transition dynamics each step be uniformly random (independent of the previous state and action). For each
E [H] define the reward function R, :S, x An > [0, 1] be defined by R3 (s, a) = [ = a].
Define the observation distribution On Sp. (Sa) so that O,(s 8) 8) 5.
and On (1
It is clear that P is 5-perturbed Block MDP. Under the trajectory distribution I lnteor induced by
the optimal latent policy mlaaent it holds that at = sh. for all E [H] with probability 1. However, for any executable policy т, for any step h and history Tish- ( Fi 1, 01.h- 1). it holds that Pr"(ax [an = 8n Ti: S 1 - since the prior history is independent of 8h, and the conditional distribution SA. has only 1 8 mass Th. Thus,
Pr |v E [H] : a4 = sn S (1 8)a.
If 8 2 1/H then (1 5) -1 < - 2(1). 1 Otherwise, (1 5) S 1 - -Q(HH). Thus, TV(P", p " 2 (1min(11 8H) as claimed.
E
Omitted Proofs for Expert Distillation
E.1
Misspecification Bounds for Composed Policies
In this section we prove upper bounds on the misspecification certain executable policies obtained by composing the latent with some belief state) in terms of instance-dependen error metrics. The first main result is Lemma E.3 (a restatement of Lemma 3.,,, where the upper bound is in terms of decodability error (Definition 3. and error in Porooximating
latent policy (with respect to
31

---

the true belief state. The second main result is Lemma E.4, where the decodability error term is replaced by action-preed catton-prediction envor (Definition 6.1).
To prove Lemma E.3, it is convenient to first analyze the policy that samples a state from the true belief state induced by the current history, and then samples action from platent accordingly. The key technical observation, below, encapsulates the intuition that resampling a near-deterministic random variable is likely yield the same realization.
Lemma E.1. Let Y.nu be joint distribution over random variables (Y,Ynut) Let IP P2 be conditional distribution. Define Qz as follows. Resample Y' ~ Py and then sample Z ~ Ip PzIY Then
TV(PY,Y.. PzY Y. Q2) S (Vx(PP))
Additionally,
TV(PY P2jx, Pr, Q7) - 2x
Proof. Consider the process where we draw (Y, nuis) ~ Py, Z ~ PzY,, and ~ Py. Y' Y then we set Z' = Z; otherwise we sample Z' Pzir' Then (Y, Yuiss Z) is distributed according Py,y.. Pz y. y. and (Y, Ynuis: Z') distributed according Py,Y. Qz. Thus, we have defined coupling. Moreover,
Pr[(Y, Z) + (Y, nuis, Z')] S Pr|Y * #Y
s 2rr & arg max Py (v)
2Vo
needed for the first claim. For the second claim,
Pr[(Y, Yuis: 2) * (Y, Yuis 2'] - Pr[z + 7') 2V (Pz)
as needed.
Lemma E.2. Let latent E Ilatent be a latent (Markovian) policy and define the executable policy π
by
n (KInh a1:h-1)
placet b3 a1:h-1).
Then
TV(
bten
Pd
< 2
E (II.,
h=1
Proof. For each 1 < h < H let on latent denote the policy that follows for the first h 1
actions and subsequently follows x latent, Since т 0₁ π latent suffices to show that, for each [H].
π latent and π o π latent π,
TV( beece pronti 2000
S 2E (bn a13h- 1)]]-
Observe that both distributions have the same conditional distributions over (Sh+1:H, Ih a1+1:H) given ($1 Ti:k, a1:h). By this fact and the data processing inequality,
TV(PaTons pp latent
TV( beon
TTONN 1 brent
X,Y.Ymia X.Y.Ymi..2
where X (2isky 01:h-1), Y Sh. Ynuis 81:A-1. and Z an. Both distributions have the same marginal over (X, Y. Ynuis). The distribution of Y|X is precisely by (IIss 41--11 by Lemma C.2 and the fact that is executable. In the former distribution, ag is generated by sampling from or llateet(sx) In the latter distribution, dg is generated by sampling &,, ~ by (Tish, @1--1) and then sampling from latent (s),) Thus, the conditions of Lemma E. are met (after conditioning out X), and we get
TV(p
latert 1p00 lesent < 2E [V (LA-)))))))))
needed.
We now prove the following restatement of Lemma 3.1.
32

---

Lemma E.3. Let laattnt E IIlatent be a latent (Markovian) policy and let b1.H be a collection of functions by X x A + ((S)). Define the executable policy से by
( d1mh-1) = latent bb.(111h a1:h-1).
Then
11
TV(
Stent
E
2Voc (b((((0)))))) + (rin,, (1s))))
1=1
and
H EE
TV(PP
h=1
where π (IIi:, 01:k-1) 1) latent by (Ti,, (1:h-1).
Proof. We can couple 1p" and jp so that at any step h, if the trajectories have thus far been the same sequence (Iish, 01:b-1), 1), then the probability that they choose different actions an is at most
(Zish d1:h-1) by (F (FLA, aL
By standard hybrid argument, it follows that
TV(PP Pd
E
hml
and also
TV(PP po)
E
Combining with Lemma E.2 completes the proof.
The preceding lemma used the intuition that if the latent state is near-deterministic when conditioned on the observation/action history, then resampling it is unlikely to change it. The following lemma uses the intuition that if the action small) when conditioned on the action/observation history, then resampling the latent state and subsequently resampling the action conditioned this resampled latent state is unlikely change the action, though it may have changed the state.
dearmmeteriiiisticc (which is likely when the action- prediction action-predicttin is
Lemma E.4. Let latent IIlatent be a latent (Markovian) policy and let b be collection of functions ba 2h Ah-1 A(Sr). Define the executable policy से by
#( 01:--1)= = latent by (1 a1:h-1)-
Then
Ff
TV(PP bohert
25
act;
Senne (IT) + latent (n(Aaaaannn latent a (2 ana-1))
h=1
where a (11:h, 01:h-1)
latent
by (1ish 01:h-1).
Proof. As with the proof of Lemma E.3, it suffices to show that
TV liint
IP
Σ
E
2e actc
watnn
(TT)
The proof is identical to that of Lemma E.3 except for using the second claim of Lemma E.1 instead of the first.
33

---

E.2 Analysis of Forward for L-step Executable Policies
In this section we describe the (slightly modified) Forward imitation learning algorithm [62], applied to the problem of distilling an expert latent policy nlatent to an L-step executable policy ग x². We first formally derive the expression for the policy learned in the infinttessmppee limit (Lemma E.5), and then prove Theorem E.1 (the regret bound for this policy, restated as Theorem 4.1). Finally, we prove a maite-sample guarantee for the modified Forward algorithm (Theorem E.2), using the same ideas together with standard finite-sample analysis for Maximum Likelihood Estimation [20].
Forward with L-step random actions. For latent Markovian policy glatent II and parameter L E [H], the (modified) Forward algorithm computes an L-step executable policy FI.H as follows. For h = ,,...,,..
Draw n trajectories 7 ($1.1 Fi-H: .H from the policy T-:h---1 o Unif(A) (which follows स until step h L 1 and subsequently plays uniformly random actions).
Compute
nr = arg max Tn E
Σ
log na (1), (s)) Tmmax( 1,b -h- 1jck: Omax(1 1 L)).hi))
Above, I1g. is the set of L-step conditional distributions - A A(A). Note that the standard Forward algorithm identical except that it draws data from मे II:A- at step The modified algorithm is simpler to analyze since the random actions do not bias the conditional distribution of the latent state at step given the partial history (#h-L++=>,, Op-L:h-1). so this distribution can be directly related to approximate belief state with appropriate prior (Lemma C.3).
For notational convenience, let denote the policy obtained from the above algorithm in the infinite- sample limit, i.e. at step h we define
Th arg max Ei L- 1 [log ( (s))))(((ss))
F 1)sh Omax(1,h- L):h- 1)]
T
The following lemma gives a closed-form expression for this policy. Lemma E.5. It holds for all h E [H] that
latent
by, apk (x (2h- 1sh; Oh-Loh-111 11
ih>> otherwise
(- Ih- L+ 1h)
x
h
latent (2 01:h-1)
so long as HI, contains this conditional distribution.
Proof. We have for each h > L that
A = arg max Fi & 19h, Unif((A) [log Th ( (altentt(s) 2h 1h-h+ an an--:)1))
EII,
Since population-level maximum likelihood minimizes KI. divergence, we get
T (ax
Th- 1:hh ah ah-Lah -h)
Σ
n
Jatent
(an
sn.) -e-.s-----ee---DifAA//a/ wh I+ I+lshr ah- Lah-1]
8y. ES
Σ
latent (an 8h.) b (1 (Th- 1+ -
1:h- d 1on (Unit(A))(sn)
Thh
8 ES,
Σ
latent Th
(ah sh.) (0 (Bh-L+1the ah-Lah 1:: d: (5h)
8). SS
where the second equality uses Lemma C.3. The application of this lemma uses the fact that Ti:h---1 P4-L Unif ((A) plays actions at steps L....,h that are uniformly random. This proves the lemma in the case h > L. The case h < L is analogous but uses Lemma C.2 instead of Lemma C.3.
Theorem E.1. Suppose that the POMDP P a 8-perturbed Block MDP with deterministic transitions, and fix L E Let π latent E Illatent be latent (Markovian) policy, and let 7 be the policy computed by Forward with L-step random actions, the infinite-sand sample limit. Then
J [ (7) < TV(E
PP' < 0 (0D
34

---

Proof.
Define the executable policy т by (Zisk 01:h-1) = alatent o (I(I,,,AAA1)) By Lemma E.3 and the closed-form expression for т (Lemma E.5), we have
H
TV
Iatont
p
(2V (21A, (211,:1--1))
h=
Σ
by (1A
by, (1h-L+1 1: oh ||]
A=L+1
By Proposition D.1 and the fact that executable, the first term can be bounded
H
Σ E ( (b a1.-
- min (s. (CD.1))(A
Σ
h=1
0(())
Next, for each { I,... H1 we can bound
E
ba 11 - by (Tn I.+ Luby lib, Un
Lsh di
(a 01:h)
< (0
dh-L
ba a1 (8)
S (CD.1)
(s)
LeES
= (CD.1)
Σ
1
E
(b
(s)
sES,
(Cb.18)
Σ
1
E
[
=s 11/11. a1
d (s)
SES,
d (s)
(CD.10)
Σ
(
SE
= =(CD.1))//8
where the first inequality uses Theorem D.I (and the fact that is an executable policy), and the second equality uses Lemma C.2 (and the fact that 7े is executable policy). Putting everything together, we get
TV( .PT) I 0(8) (C9
as claimed.
E.3 Finite-sample guarantee
Theorem F.2. There is constant CF.2 with the following property. Let 8,1, and suppose that the POMDP P 8-perturbed Block MDP with deterministic transitions. If 2 C L A3L+1 H2 log( Hn/n), the output से of the modified Forward algorithm with samples per step satisfies, with probability at least 17.
I(platent)
((R) TV(PT"
lstes .P=) 5F)5())) (C9.1) Copt-
Moreover, सt can be computed time poly(n, H, HL A4).
Proof. By standard analysis of the log-loss for unconstrained distribution classes, F (T A-o.1.AA-44ttht L+1)sh - L):)b-1) is precisely the empirical distribution of π
latent (x)) over
the data E [n] with (of (m h-L+1)::h m (aox((,A--)-. -- = (Tmax(1, h- L 1):bs Gmax(1. -)):)-hh11 Thus, के can be computed in the stated time complexity.
35

---

To prove the claimed statistical bound, fix h E [H]. Let G = {pm,
E b de-
note the family of distributions indexed by 1 where IN.. is the joint distribution of Th = ( (tmxx(1,h-4)sh--1 and (TA))) over trajectories drawn from -1-b--1 O Unif( Also 9 denote the joint distribution Tn and mlatent (sn) over trajectories drawn from -1----1 O Unif(AA) Then 9" -aş 9 where
Th
h latent by ( 30n--+15h On Lih L:h-1; dh
if h
( Th- 1+1 O/ 9n-L:h11)
latent by (2 01:h-1) "h
otherwise
by the same argument as in Lemma E.5. Moreover, 9R, is precisely the Maximum Likelihood Estimation (MLE) estimate over distribution class G with n samples from g*. Thus, we can compare Tn and Fi using a standard analysis for MLE, e.g. [20, Proposition B.1]: we can bound the log- covering number of & (with discretization error == 1/)) by X A log(1/e), probability least - // H that
get with
TV (...) = LUUn----OO-- (TV( mh), 1 Th)
X 1++11111111 log Hn/n)
0
where = (Imaxx(1, 11-mmx((1---+11tte 1+1) amax( (1.4 L):h 1)). By Change-of-measure it follows that
1 (TV Th); (. mN) 50 A4
X AL+1 log (og(Hn/nn)
Eopt
(15)
n
H
where the final inequality holds by the theorem assumption that n C Le.2X-13le 133++1 H² log( Hn/n), so long as Ca is sufficiently large constant. Next, we observe that
>
TV(IP*
P
E
[TV
(s)) (T)))
Th
latent
h=1
Hf
E [TVVVV
Th
latent (sn),
Σ
h=1
h=1
E
E
bu ba
-h-L:h------- L:h- (00
(#n-L41dh
di
hm L+1
11 +
(T)
h=1
where the final inequality is by Lemma E.3. As in Theorem E. the first term can be bounded by (6) and the second term can be bounded by (Cp.16)4/95, S. By Eq. (15) and union bound over h [H] the third term is at most Sapt with probability at least n,. Substituting these bounds into the above expression completes the proof.
F Omitted Proofs for Reinforcement Learning
In this section we prove Corollary 3.1, stated formally below.
Corollary F.I There is reinforcement learning algorithm that, for any given o, E (0,1/3) 1/3) and N, and any 8-perturbed Block MDP P, learns a policy I" satisfying
J(**) - ) < (/12 (S X,
with probability at least 3 and in time (XA)8)OLL) poly S, (133)).
36

---

Proof. Recall from Remark D.1 that any P- d-perturbed Block MDP P is (1 - 26) obbservabe (Definition B.4). Also, by Theorem D.I, P satisfies (E; o, (E; --belif contraction for any @ > and I E N with == (CD.6))//9 Φ-1. Thus, we can invoke Theorem B.1 with ? == 1/3 and E == of Φ in Theorem B.1 indeed satisfies contraction, and thus the algorithm BaSeCAMP [23] produces executable policy स that satisfies
H5ST/2X2, where C* is as defined in Theorem B.I. The choice (CD.15)4/9 x- so P satisfies (e; Φ. L.)-bliiff
J(²*) ( S E (S X, H) in time poly((AX)*, S, ,log(3-))) Substituting in the choice of e completes the proof.
G A Motivating Toy Model for Smoothing
Adding the discussion from Section 6, informally discuss theoretical toy model in which smoothing the expert may decrease (a metric version of) action-prediction error and thus improve final performance. Consider a horizon-1 POMDP where the state and action spaces have metrics ds and dA. and the reward function R is binary-valued. For each latent state s, let G(s) be the set of "good" actions, i.e. G(s)) {a A R(s, a) 1}, and let D(s) be the diameter of G(s). Suppose that the following natural assumptions hold:
1. The map + G(s) is ds + dA Lipschitz. That is, perturbing s by E (with respect to metric ds) only perturbs the set G(s) by O(E) (with respect to metric d')).
2. Under any observation, the posterior on states is "e-local" with respect to dy, i.c. contained in an 8-ball.
With no smoothing, the optimal expert may, for each 8, play an arbitrary action in G(s), so the "metric" action-prediee prediccioniiiionnn error (i.e. expected dispersion of actions played by the expert, conditioned on an observation) can be as large as O(e) + max. (s). However, suppose the environment has motor noise. In particular, suppose the support of the noise is an 1-radius ball (with respect to da) around the chosen action. Then for each s, the optimal policy is forced to the "interior" of G(s), i.e. not within 17 of the boundary, effectively equivalent decreasing the diameter of G(s) by n. Moreover, if 2 E, then for any two states s, s' in the posterior of observation o, the actions chosen by the optimal policy will lie in both G(s) and G(s'). (under mild additional structural assumptions, e.g. convexity of G(s) in Euclidean space) distillation should produce an optimal policy.
Of course, if is too large, the "interior" of some of the G(s) sets becomes empty, i.e. the optimal policy cannot play a robustly good action. As a result, it may play arbitrary actions for these states, so the action prediction error can become large again (and the policy value decreases).
H Supplemental Materials for Experiments
In Appendix H.1 we present details for our empirical test of whether perfect decodability holds in image-based locomotion tasks. In Appendix H.3 we present figures omitted from the main body of the paper. In Appendix H.4 we include hyperparameter choices and details about compute resources.
H.1 Misspecification of Decodability in Practice
For each of the three tasks (walker-run, humanoid-walk, and dog-walk), we collect 2000 tra- jectories from the expert latent policy, and for each L {1, 3, 4, 5} we train model directly mapping from L observations - to the state sn. by minimizing mean-squared error. We then evaluate the validation error of the model on 100 trajectories collected from the same policy and plot the per-timestep error in Figure 5. We normalize the states with the trajectory mean and standard deviation of the combined dataset. Note that the error is composed with three parts: 1) error due to model capacity: 2) using fixed-length Trame-stacks instead of the whole history, 3) inherent failure of perfect decodability. We observe that the trained model is able to achieve a small error in the later timesteps, which suggests that error 1, model capacity error, is (likely) small. However, the error large in the initial timesteps. As error does not exist for steps h S T,, follows that error is non-trivial, i..., perfect decodability fails.
37

---

Per-timestap Prediction Error- walker
Per-timastop Prediction Error- humanoid
Per-timastep Prediction Error dog
131
221
Haaer uneh
molay Long)
rolay Lengh
1.50
Haatl angh
159
0403) Lerge
130
sidoy Lergh
1.33
4.31 0.23
023
191 201
100
104
110
21C
0/C
120
Figure 5: Per timestep validation error of the state-pre stte-prediction model for different choices of frame- stack L E {1, 2, 3, 4, J,. The model is trained to predict the state given the most recent L observations. We present the average error across random seeds.
Ablation. To investigate whether the enror at initial timesteps is due to parameter sharing, also tried to train non-stationary models (i.e.. one model for each timestep) or using weighted loss with higher weights for the initial timesteps, but neither approach significantly changed the results.
Conclusions. We conjecture that the higher error at early timesteps is due to a nearly uniform distribution for the initial state distribution, where states that induce occlusion may be quite likely. In later time-steps, the observations along the expert trajectory are a more stable regime and thus may introduce less occlusion (and hence be more likely to correspond to unique latent state). Finally, we observe that even at later time-steps there is still significant prediction error. While this could potentially be due to model capacity error, it nevertheless demonstrates impracticality of learning perfect decoder, and it roughly corresponds with task difficulty (humanoid- dwakkk and dog-walk are harder than walker-run).
Source of the error. One may naturally wonder if the error is caused by unpredictable state components that are irrelevant to decision-making (one example could be the absolute position of the agent, but in the environments that we test on, absolute coordinates are actually not part of the latent space). If this is the case, then the error would not negatively impact the performance of the policy distilled from the latent expert.
One piece of evidence against this hypothesis is that the action-predicet prediction error is indeed non- non-trivin trivial for our tasks of interest (c.r. Figure 9), which suggests that the error is not only due to irrelevant components. In addition, we take more detailed look at the state prediction error and identify the components that contribute most the error. With the same setup as in Figure we compute the mean squared error for each coordinate of the state, averaged over the whole trajectories, and present the top 5 and bottom coordinates Table We see that the coordinates that contribute most the error are mostly angular velocities of limbs, which are indeed hard to predict from images. On the other hand, the coordinates that contribute least to the error are mostly joint angles or balance point coordinates, which are easier to predict from images. From first principles, all of these coordinates are crucial for the optimal policy, providing additional confirmation that the error is not only due to irrelevant components.
Table 1: (Left) Top 5 and (right) bottom coordinates contributing to state prediction error.
Coordinates
Error
Coordinates
Error
left ankle_ y angular velocity
0.82
left elboo joint angle
0.006
left_hip_X angular velocity
0.81
balance point
0.020
right_shoulderl angular velocity
0.69
balance point
0.034
right_shoulder2 angular velocity
0.67
balance point
0.044
right_ankle_y angular velocity
0.64
left_knee joint angle
0.045
H.2 Imitating a Smoother Expert under Deterministic Latent Dynamics
In Section 6, we showed that under stochastic latent dynamics, imitating a smoother expert (which is trained under higher motor noise) can lead to better performance. A natural question is whether this phenomenon also exists under deterministic latent dynamics. Theoretically, the answer is no we showed in Theorem E. that with enough framestack, imitating the smoothedd expert can already be optimal under deterministic latent dynamics. That said, it remains unclear if smoothing the expert
38

---

can help improve the performance in practice. To answer this question, we conduct experiments in the same setup in Section but with motor noise o 0 when performing expert distillation. We vary the motor noise level used to train the latent expert over {0.1, 0.2, 0.3, 0.4, 0.5), and we use framestack of size
We present the results in Figure 6. We see that imitating a smoother expert does not lead to better performance in this case, and the best performance is achieved by imitating the non-smoothed expert (c.r., Figure 1). This corroborates our theoretical findings.
Expert Smoothing Noise 0- humanoid
Expert Smoothing Noise 0- dog
000
800
Tragectory Rewards
600
Tragectory Rewards
800
400
Expertruse
Expert
rese 0.2
ne 0.2
200
Expertrese 0.3
Expert 0.3
Expert rose
Expert norse
50,000
300 000
350 000
200,000
250,000
50,000
300,000
350 000
200,000 000
250,000
Training Staps
Training Steps
Figure 6: Performance of DAgger the validation dataset for the humanoid-walk and dog-walk environments with motor noise a = D, as the noise level for the training environment (i.e. the environment in which the latent expert trained) varies over {0.1, 0.2, 0.3, 0.4, 0.5).
39

---

H.3 Omitted Figures
H.3.1 Belief contraction with/without motor noise
Bellef Contraction walker
Belief Contraction dog
Balief Contraction humanoid
Divergence Irpressnoo
Steerencc
Divepennc
300
50
22
Hottery Length
Matorry Length
Histery Length
Figure 7: Belief contraction error with respect to the framestack == 3,,3,4, 4,5) on all tasks. For each framestack L, we use train Gaussian parametrized neural network predict the belief with L framestack input. We compute the KL distance to the output of an L 10 network (serving as an approximation of the true belief), averaged over a validation dataset with 100 episodes of data. The orange plot denotes the decrease in KL divergence between two numbers of framestacks. We repeat the experiment for times and plot the mean and standard deviation. We observe that the belief contraction eπror decreases (although not as fast as predicted by the theory) as the number of framestack increases.
Belief Contraction humanoid
Belief Contraction humanoid noise 0.2
Divergence improvement
Divergence
impovement
28
27
24
26-
History Length
History Langth
Figure 8: Belief contraction with respect to the framestack I. {2, 4, humanoid tasks, with and without motor noise. For each framestack L, we train a Gaussian parametrized neural network predict the belief with L. framestack input. We compute the KL distance to the output of an L = 10 network (serving as an approximation of the true belief), averaged over a validation dataset with 100 episodes of data. The orange plot denotes the decrease in KL divergence between two numbers of framestacks. We repeat the experiment for times and plot the mean and standard deviation. We observe that very similar belief contraction phenomena occur with or without the motor noise.
H.3.2 Action prediction error with smoothed experts
40

---

Final Error Comparison humanoid
Final Error Comparison dog
0:30
0.50
0.25
0.45
Riall Eiror (MSS)
Final Erner (MSSS)
0.20
0.15
0.35
0.10
0.30
0.05
0.25
0.00
0.3
0.5
0.20
0.3 Noise Level
Noise Level
Figure 9: Comparison of the (estimated) oetion-prediccin error of the latent policy on the validation dataset for the humanoid d-walk and dog-walk environments with motor noise a 0.2, as the noise level for the training environment (i.e. the environment in which the latent expert was trained) varies over {0.1, 0.2, 0.3, 0.4, 0.5}. The action- aation-prediction error was estimated using MSE as proxy (normalized by dimension of the action space, as detailed Section 2). We observe that imitating the latent expert that is trained on the same noise level does not yield the smallest prediction error. Moreover, policies with lower action- cetion-prediction error also broadly have higher performance (Figure 4).
H.4 Experiment Details
Hyperparameters for state prediction models. The hyperparameters used and considered for the belief/state prediction models (both deterministic and Gaussian parametrized), corresponding to the experiments in Sections 3.1 and 5.2, in Table 2. For the neural network architecture, we use the same enn block prescribed in [22], followed by three layer neural network with ReLU activation. The architecture remains the same for the policies, and the hyperparameter hidden size refers the hidden size of the feedforward part of the neural network.
Table 2: Hyperparameters for belief prediction models.
Final value
Considered Values
Minibatch size
256
128, 256 1e-3, 2c-4, lc-4 Adam 25, 50, 100
Learning rate
le-4
Optimizer
Adam
Number of epochs Hidden layer size
100
512
128, 256, 512
Hyperparameters for expert distillation. The hyperparameters of BC and DAgger are provided in Table 3 and Table respectively. Note that the only exception is that DAgger run for 6500 episodes in the motor noise 0.1 and 0.3 experiment because converges slower than the rest of the experiments.
Table Hyperparameters for BC.
Final value
Considered Values
Minibatch size
256
128, 256 le-3, 2e-4, le-4
Learning rate Optimizer
le-4
Adam
Adam 1000, 2000, 5000
Number of episodes
2000
Number of epochs
1000
100, 500, 1000
Hidden layer size
256
128. 256, 512
Hyperparameters for RL. The hyperparameters for RI. follows the original hyperparameters prescribed in [22], and we train for 50000 episodes.
Computation details. All our experiments are run with L40S GPU with threads CPU.
41

---

Table 4: Hyperparameters for DAgger.
Final value
Considered Values
Minibatch size Learning rate Optimizer Number of episodes
256
128, 256 le-3, 2e-4, le-4 Adam
le-4
Adam
2, 5, 10, 20 1000, 2000, 5000, 100000 20, 50, 100 128, 256, 512
Number of iterations
5000
Number of gradient step per iteration Hidden layer size
256
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: We provide both theoretical and empirical evidence on how approximate decodability and belief contraction explain the algorithmic trade-off between expert distillation and RL.
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 NA answer 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 to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We include a discussion on the limitations of the work in the final section.
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 (c.g., independence assumptions, noiseless settings, model well-specification
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend 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 or images are taken in low lighting. Or 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.
42

---

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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor 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.
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:
We explicitly state our assumptions and provide proofs all of our theoretical
results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper the supplemental material, but if they appear 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 proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. 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: [Yes]
Justification:
We discuss all details of the experiments, including hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, if the contribution
While NeurIPS does not require releasing code, the conference does require all submissions to 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 reproduce that algorithm.
(b) the contribution primarily a 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).
43

---

(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.
5. 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, described in supplemental material?
Answer: [No]
Justification: We did not provide the code in the supplemental material as the algorithms we implemented are standard ones, and we provide all hyperparameters in Appendix H.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc/ll cctppippccccpppbcc///ccccccccccc guides/CodeSubmi htt.subiiiiioooooiiooo..oooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for 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 to to reproduce the results. See the NeurIPS code and data submission guidelines (https: /ttp///nips.o. cttpsscccppbblllcc guides/CodeSubmiss ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how 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 subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the 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 data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We discussed how generate the training and validation data, and our choice of optimizers.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to a 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 as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about statistical significance of the experiments?
Answer: [Yes]
Justification: All of our results include error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
44

---

The factors of variability that the error bars are capturing should be 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 enror bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables 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 the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
We include our compute details in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of 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 more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, every respect, with the NeurIPS
Code of Ethies https:://euuriai http:/rwww......boo/o//cctttttta
Answer: [Yes]
Justification:
Our research conforms with the NeurIPS Code of Ethics.
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 circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consideration due laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper does not incur significant societal impacts.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address socictal impact.
45

---

Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.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 to par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how 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 (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use 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: Our paper does not leverage existing dataset or codebases.
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 or 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 be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ htt/datasettettttceeeaaaaooaetee datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 not available online, the authors are encouraged reach out to the asset's creators.
46

---

13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do 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/mmodl 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 can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 as much detail possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should paid at least the minimum wage in the country of the data collector.
15. Institutional review board (TRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred study participants, whether such risks were disclosed to 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 nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 we expect authors to 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.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
47

---

Answer: [NA]
The core method development in this research does not involve LLMs as any important, original, non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-standard components.
wttp.///eeeeeeece//22/////////// httt:p////errrss..cccoooeeeeeee/ Please refer to our LLM policy pottts://neuriiin should or should not be described.
for what
48


Reviews:
[{"review_id": "CyKTbKZUg8", "reviewer": "Reviewer_GVpx", "summary": "The paper investigates the trade-off between privileged expert distillation—where a latent policy is trained using privileged information and then distilled into an executable policy via online behavior cloning—and reinforcement learning (RL) without privileged information, which uses frame-stacking, in partially observable Markov decision processes (POMDPs).\n\nAfter formalizing the sources of error in POMDPs in terms of decodability and belief contraction, the authors introduce a theoretical model called the perturbed block MDP. This model extends the block MDP framework by incorporating some irreducible error in the emission distribution. Using this instructive model, the authors demonstrate that expert distillation can be both computationally and sample efficient in deterministic environments, where the belief state becomes concentrated over transitions. However, they also show that in the worst case, expert distillation may lead to irreducible sub-optimality.\n\nAdditionally, the authors present a series of controlled experiments on locomotion tasks (including humanoid, dog, and walker) to empirically illustrate their theoretical findings", "questions": "- in section 5.1, what do you mean by uniformly mixing dynamic? does it mean that we can teleport to any latent state from any latent state  at each step? does this mean that the belief state is uniform over the state space?\n- in the case of uniformly mixing dynamic, do you think we ever need to do frame-stacking, since previous observations don;t inform us about the next state ? \n- in section 5.2, I am curious what happens if we let expert distillation to run for more time and samples. does it recover the RL performance asymptotically ?  I am wondering if it is about having more samples or there are real fundamental gap between the two method in these environments.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "- The paper is well-motivated and clearly structured.\n- The topic of expert distillation versus reinforcement learning is highly relevant and of significant practical interest.\n- Although the paper is mathematically and notationally dense, the authors consistently provide intuitive explanations and high-level interpretations.\n- The authors openly discuss the limitations of their theoretical model and acknowledge the presence of other confounding factors not accounted for.\nI-  particularly appreciate the seamless integration of theorems with empirical validation, which helps to concretize the theoretical findings.\n- Due to time constraints and limited background in POMDP theory, I was unable to thoroughly review the proofs in the appendix and therefore cannot fully assess the correctness of the theorems.", "was_revised": true, "final_justification": "the authors addresses my questions. I maintain my accept score", "rebuttal": "We thank the reviewer for their careful attention to our work and we look forward to a constructive discussion period. \n\n> in section 5.1, what do you mean by uniformly mixing dynamic? does it mean that we can teleport to any latent state from any latent state at each step? does this mean that the belief state is uniform over the state space?\n\nFirst part of the question: Yes, by “uniformly mixing dynamics”, we mean that at each timestep $h$, the transition distribution from each latent state is uniform, i.e. we can “teleport”. This is of course a rather extreme setting, but the experiments (with more realistic sources of stochasticity) validate the basic theoretical intuition that we obtain from this setting.\n\nSecond part of the question: No, recall that the belief state is the posterior distribution of $s_h$ after observing $(x_{1:h},a_{1:h-1})$. Even under uniformly mixing dynamics, the observation $x_h$ may be highly informative of $s_h$. For example, under a $\\delta$-perturbed Block MDP with uniformly mixing dynamics, any true belief state $\\mathbf{b_h}(x_{1:h},a_{1:h-1})$ should concentrate at least $(1-S\\delta)$ mass onto some state, where $S$ is the size of the latent state. We will make sure to explain this point more clearly in the final version. \n\n> in the case of uniformly mixing dynamic, do you think we ever need to do frame-stacking, since previous observations don;t inform us about the next state ?\n\nYour understanding is correct: in this case, frame-stacking does not help expert distillation. This is essentially the message of Proposition 5.1: even as the frame-stack $L$ increases, the decodability error is irreducible, resulting in the stated suboptimality lower bound. \n\nNote that in this case frame-stacking also does not “help” for RL, but this is because POMDPs with uniformly mixing dynamics are already easy for RL: the history does not matter, so we can simply solve the $H$-step decision-making problem as $H$ independent 1-step problems, which are tractable by standard RL methods (both in theory and in practice).\n\n> in section 5.2, I am curious what happens if we let expert distillation to run for more time and samples. does it recover the RL performance asymptotically ? I am wondering if it is about having more samples or there are real fundamental gap between the two method in these environments.\n\nOur theory suggests that there is a real fundamental gap between expert distillation and RL under the stochastic dynamics, and our experiment is trying to demonstrate this point empirically. For this rebuttal, we have rerun the DAgger algorithm for noise levels {0.2, 0.3} and frame-stack $L$=3, in the setting of Fig. 3 (note that for noise level 0.1, Fig. 3 demonstrates that distillation is competitive with RL, so running DAgger longer would only solidify that conclusion). This time, we use 1.5x the number of samples. We repeat the new experiment with 3 random seeds and report the average. While the new averages are somewhat higher, they are now definitely at convergence; moreover, the original empirical conclusion still holds: there is a fundamental gap between distillation and RL in noisier environments. We use the percentage to denote the progress of the training. \n\n|  | DAgger (66%) | DAgger (83%) | DAgger (100%) | RL |\n| --- | --- | --- | --- | --- |\n| humanoid noise 0.2 | 434.2 | 478.1 | 473.9 | 583.6 |\n| humanoid noise 0.3 | 430.8 | 453.3 | 455.1 | 585.6 |\n\nTo further demonstrate the generalizability of the finding, we repeat the experiment on another task, dog-walk, and we observe that the gap between expert distillation and RL is even larger. \n\n|  | DAgger (66%) | DAgger (83%) | DAgger (100%) | RL |\n| --- | --- | --- | --- | --- |\n| dog noise 0.2 | 540.0 | 570.3 | 568.5 | 722.7 |\n| dog noise 0.3 | 432.4 | 449.8 | 452.3 | 703.4 |\n\nWe believe these new results will further consolidate our empirical findings."}, {"review_id": "QjdDUREg4y", "reviewer": "Reviewer_Yzkr", "summary": "The paper studies RL vs imitation learning in POMDPs. It firstly verifies that perfect L-decodable POMDP may not hold using experiments and then considered a setting call $\\delta$-perturbed Block MDP. Then the paper proposed provable algorithms based on the approximate $L$-decodability induced by the $\\delta$-perturbed Block MDP assumption. Finally, the paper also discussed how to improve expert distillation by smoothness.", "questions": "NA", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: \n\n1. The paper combines many theoretical claims with experimental justifications, where provide valuable insights.\n2. The argument that latent expert might not be the best target and smoothness might help is novel.\n\nWeakness:\n\n1. I find the paper oftentimes confuses the concept of decodable and $L$-decodable. Technically speaking, I am not aware of any references that use the nomenclature of ``decodable POMDP''. Although the condition by [6] should be equivalent to decodable by $H$ steps. However, it seems to me what the paper has relaxed is the perfect $L$-decodable condition with small $L$ (Efroni et al 2022) instead of the condition in [6] as claimed in the intro. Therefore, to substantiate a meaningful relaxation over [6], the paper should either: (a) establish provable guarantees in the regime of large $L$, or (b) clearly discuss this distinction in the main text to avoid conceptual confusion.\n\n2. Secondly, it seems the technical assumption that really enables approximate $L$-decodability is perturbed block MDP + deterministic transition. In terms of theoretical contributions, this is arguably quite strong to have structural assumptions on emission and transition at the same time.  \n\n3. Meanwhile, in the experimental validation, the paper is only using $L\\in [5]$ to verify the decodability. This again tries to only verifies whether $L$-decodability holds with small $L$. Moreover, I understand in practice ppl often only use observation history. However, action history is also important in theory and in terms of verifying the theoretical conditions faithfully.\n\n4. As claimed, one important goal of the paper is to understand expert distillation vs RL. However, the message is that with deterministic transition, expert distillation match RL bounds. With stochastic transition, expert distillation is worse. Therefore, it seems the theory itself does not reveal the benefits of distillation.", "was_revised": true, "final_justification": "The rebuttal has clarified my questions and I thus updated my evaluation.", "rebuttal": "We thank the reviewer for their careful attention to our work and we look forward to a constructive discussion period.  \n\nSince the reviewer has several comments about decodable vs $L$-step decodable / large $L$ vs small $L$, we address these first. \n\n- **Nomenclature:** Thanks for pointing out that ``decodable POMDP'' may not be standard terminology. When we say “decodable” with no preface, we indeed mean “H-step decodable”; we will clarify this in the paper.\n- **Experimentally verifying failure of $H$-step perfect decodability:** As the reviewer points out, we only explicitly verify failure of $L$-step decodability for $1 \\leq L \\leq 5$. However, from this experiment (Fig. 5) we can make two additional deductions: **(1)** For each step $1 \\leq h \\leq L$, the most recent $L$ observations comprise the entire history, and the decodability error at such steps $h$ is still large. The method of [6] requires perfect decodability at all steps, so their assumptions are indeed not met. **(2)** In all three tasks, the decodability error appears to essentially converge by $L = 5$. Since there is no principled reason why much older observations should be much more informative, we see this as strong evidence that the steps $h > L$ are also not $H$-step decodable.\n- **Comparison with (Cai et al., 2024):** The reviewer points out that approximate $L$-step decodability does not relax H-step perfect decodability, and suggests that:\n    \n    > …the paper should either: (a) establish provable guarantees in the regime of large L, or (b) clearly discuss this distinction in the main text to avoid conceptual confusion.\n    \n    Thanks for bringing this up; we will add clarification. In our introduction, we did not intend to claim that we have “relaxed” the assumption of (Cai et al., 2024), but merely to argue that perfect $H$-step decodability can be unrealistic in the settings that we care about. This demonstrates that the result of (Cai et al., 2024), though very interesting, is not directly applicable in our tasks of interest. \n    \n    To be clear, our guarantee for expert distillation is incomparable with that of (Cai et al., 2024) — for several reasons, including what the reviewer mentioned. Another reason is that their guarantees are for a variant of expert distillation (compared to what is commonly implemented), which involves learning an autoregressive state decoder. This lets them demonstrate a provable computational benefit of latent state information. Our theory is complementary to theirs: we elucidate the factors that govern the performance of expert distillation as it is commonly implemented — i.e., with some constant frame-stack $L$. We will make this more clear in the final version. \n    \n\nWe now turn to the reviewer’s other comments.\n\n> Secondly, it seems the technical assumption that really enables approximate L-decodability is perturbed block MDP + deterministic transition. In terms of theoretical contributions, this is arguably quite strong to have structural assumptions on emission and transition at the same time.\n\nWe agree that “perturbed block MDP + deterministic transition” is a strong assumption, but this is precisely the point of the theory. One of the main messages of our theoretical results is that even in the perturbed Block MDP setting (a natural theoretical testbed that imposes structure on the emissions based on the properties in the real applications), strong guarantees for expert distillation *cannot* be achieved without some assumption limiting the stochasticity of the transitions. We emphasize that the goal of our theory is not to identify the weakest possible assumptions under which POMDPs are tractable (though this question is very interesting and well-studied), but rather to understand the tradeoffs between popular (existing) algorithms, in settings where they are commonly applied (e.g., image-based robotics and autonomous driving). These settings motivate our theoretical abstractions, and the theory provides a principled explanation for the phenomena that we observe empirically.\n\n> Moreover, I understand in practice ppl often only use observation history. However, action history is also important in theory and in terms of verifying the theoretical conditions faithfully.\n\nWe agree with the reviewer that the current experiment is to appeal to the common practice. For the rebuttal, we conduct experiments where the history is augmented with actions — for both DAgger and RL, and both deterministic and stochastic latent transitions. We find that adding actions to the history does not significantly change the main empirical findings, though it seems to (inconsistently) make RL worse. In the new results, we repeat each experiment with 3 random seeds and report the average. Below, we compare with the existing results (observation-only history):\n\n|  | DAgger | DAgger with action history **(new)** | RL | RL with action history **(new)** |\n| --- | --- | --- | --- | --- |\n| humanoid noise free | 739.1 | 710.8 | 572.4 | 568.6 |\n| humanoid noise=0.2 | 473.9 | 491.2 | 583.6 | 509.0 |\n| dog noise free | 722.5 | 739.3 | 762.6 | 719.5 |\n| dog noise=0.2 | 568.5 | 559.4 | 722.7 | 728.2 |\n\nUnderstanding when action history is unnecessary (or even detrimental) from a theoretical perspective is an interesting question.\n\n> As claimed, one important goal of the paper is to understand expert distillation vs RL. However, the message is that with deterministic transition, expert distillation match RL bounds. With stochastic transition, expert distillation is worse. Therefore, it seems the theory itself does not reveal the benefits of distillation.\n\nThe primary “benefits of distillation” are already empirically well-understood: as a supervised learning method, expert distillation enjoys faster and more stable convergence than RL [2], i.e. it is computationally simpler. Our empirical results corroborate this common knowledge (Fig. 1). However, the main focus of our work — both the theory and empirics — is to shed light on a  much less-understood axis of the trade-off between distillation and RL: the price that we pay in *accuracy* for using (fast) expert distillation instead of (slow) RL. \n\nIt is true that our theoretical results never show expert distillation to achieve superior accuracy than RL. This is corroborated by the empirical results, when computation is taken out of the picture (i.e. both algorithms are run to convergence). Moreover, it is to be expected: modulo issues of optimization (and capacity of the policy network), RL will always approach optimality with enough samples and computation, whereas expert distillation is fundamentally limited by misspecification of the expert policy (regardless of the capacity of the student network).\n\n[1] Eberhard, Muehlebach, and Vernade. \"Partially Observable Reinforcement Learning with Memory Traces.\" *ICML 2025*.\n\n[2] Levine. “Imitation learning vs. offline reinforcement learning.” Lecture @ UC Berkeley RAIL. 2022."}, {"review_id": "mXpZ54GFHu", "reviewer": "Reviewer_Aw6u", "summary": "This paper investigates the trade-off between expert distillation and standard RL in POMDPs, finding that the stochasticity of the latent dynamics governs their relative performance. The authors provide a theoretical framework based on approximate decodability and belief contraction to explain this trade-off. They also show empirically that distilling a smoother expert, trained with noise, can be a more effective strategy than distilling the technically optimal one.", "questions": "Please see weaknesses section.", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n- The paper provides a strong theoretical framework for the distillation vs. RL trade-off by introducing the 'perturbed Block MDP' model and using it to contrast the core conditions of 'approximate decodability' and 'belief contraction'.\n- The paper effectively connects theory to practice, not only by validating its theoretical predictions with experiments (Fig. 3) but also by uncovering a significant and practical insight: distilling a 'smoother' expert can be more effective than distilling the optimal one (Fig. 4).\n\nWeaknesses\n- The provided theoretical bounds, which appear to be worst-case guarantees, do not always align perfectly with the empirical outcomes. \n- The finding that smoother experts can be better teachers is one of the most exciting directions in the paper, and the authors provide a compelling proof-of-concept by injecting motor noise. It would be valuable to see it explored further. For instance, a more systematic study on how to tune the 'optimal' amount of noise for a given task, or a deeper theoretical dive into how this smoothing technique impacts the action-prediction error bound, could significantly build upon this novel contribution.", "was_revised": true, "final_justification": "I will maintain Borderline Accept.", "rebuttal": "We thank the reviewer for their careful attention to our work and we look forward to a constructive discussion period.\n\n> The provided theoretical bounds, which appear to be worst-case guarantees, do not always align perfectly with the empirical outcomes.\n\nWe agree completely: there are several gaps between the empirical results and the worst-case theoretical guarantees (e.g., Sec. 5.2, belief contraction error as a metric for sub-optimality of RL), and we see these gaps as exciting directions for future work — places where a more complex theory could be more tightly predictive. POMDPs are a rich (and still largely mysterious) model class, and the goal of our theory was not to develop some complete quantitative characterization, but rather to achieve a principled qualitative understanding of factors that influence popular algorithms’ performance in practice. We believe the empirical results demonstrate that our theory does have predictive power, despite being derived via worst-case guarantees. \n\n> The finding that smoother experts can be better teachers is one of the most exciting directions in the paper, and the authors provide a compelling proof-of-concept by injecting motor noise. It would be valuable to see it explored further. For instance, a more systematic study on how to tune the 'optimal' amount of noise for a given task, or a deeper theoretical dive into how this smoothing technique impacts the action-prediction error bound, could significantly build upon this novel contribution.\n\nWe are glad that the reviewer also found this result exciting. While this result was indeed a proof-of-concept, we can share some additional thoughts on noise tuning and the theoretical basis for smoothing:\n\n- For tuning the noise, one approach (suggested by our theory and roughly validated by the experiment in Fig. 8) is to select the expert with the smallest action prediction error. Although ideally the error would be estimated under learner visitation distribution, we believe that using the expert visitation distribution could be a good surrogate. A more direct approach is to simply pick the highest noise level for which the expert performance is within a reasonable threshold (which might require certain domain knowledge).\n- Our basic theory for how motor noise improves action-prediction error is the following. Consider a horizon-1 decision-making task where the state and action spaces have metrics $d_S$ and $d_A$. For each latent state $s$, let $G(s)$ be the set of ''good'' actions, i.e. actions that achieve maximal reward. Suppose that (1) the sets $G(s)$ are $d_S \\to d_A$ Lipschitz, i.e. perturbing $s$ by $\\epsilon$ w.r.t. $d_S$ only perturbs $G(s)$ by $O(\\epsilon)$ w.r.t. $d_A$, and (2) the posterior under any observation is ''local'' w.r.t. $d_S$, i.e. contained in an $\\epsilon$-ball. With no smoothing, the optimal expert may, for each $s$, play an arbitrary action in $G(s)$, so the action-prediction error can be as large as $O(\\epsilon)$ + 2 * max diameter of $G(s)$. However, if the environment has motor noise -- say that the support of the noise is an $r$-radius ball (w.r.t. $d_A$) around the chosen action. Then for each $s$, the optimal policy is forced to the ``interior'' of $G(s)$, i.e. not within $r$ of the boundary, effectively equivalent to decreasing the diameter of $G(s)$ by $r$.\n\nThis leads to two predictions. First, the action-prediction error initially decreases as $r$ increases. Second, when $r$ gets too large, the ``interior\" of some of the $G(s)$ sets becomes empty, i.e. the optimal policy cannot play a robustly good action. As a result, it may play arbitrary actions for these states, so the action prediction error becomes larger again (and the policy value decreases). This prediction is validated in the humanoid task (Fig 8a) but unclear for the dog task (Fig 8b) -- where the changes in action-prediction error are within margin-of-error (and the downstream performance gains from smoothing are also smaller).\n\nWe appreciate the questions and we will make sure to include these discussions in the final version of the paper."}, {"review_id": "s7uLrrqH23", "reviewer": "Reviewer_Nv62", "summary": "This paper investigates the theoretical properties of privileged expert distillation in partially observable RL. It begins by arguing that perfect decodability is unrealistic in practice and introduces the notions of approximate decodability and the perturbed Block MDP as a more practical model. The paper then systematically compares the theoretical guarantees and empirical performance of expert distillation versus standard RL in both deterministic and stochastic dynamics. Finally, it suggests that injecting stochasticity into the latent MDP can improve the effectiveness of distillation by yielding smoother experts.", "questions": "1. Is there a theoretical or empirical distinction between injecting noise into actions, observations, or latent state transitions? How do these different sources of stochasticity affect decodability and distillation?\n\n2. In the stochastic setting, is the privileged expert trained with noise injected into the latent MDP, or is it trained on the original (noise-free) latent MDP? If the latter, doesn't that imply the expert and student are being trained on different MDPs, which could explain the degradation in performance?\n\n3. What is the relationship between environment noise and expert smoothing noise? For instance, does higher environment noise require a higher level of expert smoothing? Could expert smoothing still help in environments with no noise?\n\n4. Can the authors comment on whether the deterministic filter condition from [1] relates to their assumptions in Section 4? Is it possible to extend the results for deterministic dynamics to this broader condition?\n\n5. Could the authors provide some discussions on the paradigm introduced in [2]?\n\n[1] Cai, Y, et al. Provable partially observable reinforcement learning with privileged information. \n\n[2] Li, Y, et al. Guided Policy Optimization under Partial Observability.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The paper addresses an important and timely question: when and why expert distillation is beneficial, especially in the context of robot learning. This has significant practical relevance.\n\n- The focus on settings where decodability fails but observations remain informative is both realistic and more practical than prior assumptions of perfect decodability.\n\n- It presents a comprehensive and thoughtful literature review.\n\n- The theoretical results are well-developed, with formal proofs that support the key claims.\n\n- Experimental results are carefully designed and align well with the theoretical predictions.\n\n- The idea of smoothing the expert policy to improve distillation performance is well-motivated.\n\n**Weakness**\n\n1. Assumption about perfect decodability may be premature:\n\nThe paper's rejection of perfect decodability as unrealistic is foundational to its entire framing, and should be argued more rigorously. For instance:\n  - The presence of large initial prediction error is not necessarily evidence against decodability; even in decodable settings, early predictions may be inaccurate due to limited history\n  - Prediction errors could be caused by irrelevant or redundant latent variables (e.g., absolute coordinates) that are not essential for the task and naturally hard to infer without a reference frame.\n  - Figure 5 lacks clarity — it's difficult to determine whether the final error is substantively large or just numerically small due to scale. A more illustrative example showing what is being mispredicted and how much could better support the claim.\n\n2.  Lack of comparison to asymmetric RL:\n\nPrivileged expert distillation is often compared to asymmetric RL, which also utilizes privileged information during training. However, this paper only compares expert distillation to standard RL without privileged information. If latent states are available, then asymmetric RL would be a more practical and competitive baseline.\n\n3. Limited task diversity:\n\nWhile the experimental evaluation includes three DeepMind control suite tasks, all of them are locomotion-based. The lack of coverage of other types of partial observability — such as multi-agent coordination, strategy games, or visual navigation — limits the generality of the conclusions.", "was_revised": true, "final_justification": "My concerns are well addressed, especially regarding the perfect decodability issue. Although the paper still has a limited scope compared to general POMDPs, I believe it establishes a solid foundation.", "rebuttal": "We thank the reviewer for their careful attention to our work and we look forward to a constructive discussion period.\n\nWe start by addressing the reviewer’s comments about our experiment which shows that perfect decodability is unrealistic:\n\n- **Initial prediction error**\n    \n    > The presence of large initial prediction error is not necessarily evidence against decodability; even in decodable settings, early predictions may be inaccurate due to limited history\n    \n    This is a matter of definition: we agree with the reviewer that in a realistic system, early predictions are often inaccurate, and this is precisely what we observe in Fig. 5. Unfortunately, the prior work [1] required the states at *all* steps to be perfectly decodable, in order for their algorithm with latent state information to have provable guarantees. The reviewer’s observation demonstrates why this assumption may be often unrealistic.\n    \n- **Irrelevant latent variables**\n    \n    > Prediction errors could be caused by irrelevant or redundant latent variables (e.g., absolute coordinates)...\n    \n\n     Thanks for bringing up this point! For this rebuttal, we have performed the same experiment as in Fig. 5 but measuring action-prediction error instead, which avoids this confounder — if the state prediction error were solely due to difficult-to-predict latent variables that are irrelevant to the expert actions, we would find that the action-prediction error is very small. However, we observe below that it is in fact substantially large. The action-prediction error is normalized so that the “scale” is $O(1)$, just like the state-prediction error — see the response below.\n\n\n    |  | walker-run | humanoid-walk | dog-walk |\n    | --- | --- | --- | --- |\n    | Error at timestep 5 | 0.202 | 0.224 | 0.414 |\n    | Error at timestep 500 | 0.043 | 0.125 | 0.149 |\n\n- **Scale and source of prediction error**\n    \n    > Figure 5 lacks clarity...A more illustrative example showing what is being mispredicted and how much could better support the claim.\n    \n    Quantitatively, note that the states are normalized so that each coordinate has zero mean and unit variance; moreover, the MSE is normalized by 1/dimension (we mention this in Section 2 but will reiterate it in Section G.1). Therefore an MSE of 0.25 (humanoid) or 0.4 (dog) is indeed substantively large.\n    \n    For this rebuttal, we have investigated which coordinates are mis-predicted the most. We use humanoid-walk as an example, and we measure the per-coordinate state prediction error averaged across 2000 samples, with frame-stack 3. We measured (a) the average error across all time-steps, (b) the first 20 steps, and (c) the last 20 steps, and we observe the coordinates with the highest and lowest errors in (a)/(b)/(c) are the same sets of coordinates. Here we report the results for (a):\n\n    **top-5 coordinates by error:**\n\n    | coordinate | error |\n    | --- | --- |\n    | left_ankle_y angular velocity | 0.82 |\n    | left_hip_x angular velocity | 0.81 |\n    | right_shoulder1 angular velocity | 0.69 |\n    | right_shoulder2 angular velocity | 0.67 |\n    | right_ankle_y angular velocity | 0.64 |\n\n    **bottom-5 coordinates by error:**\n\n    | coordinate | error |\n    | --- | --- |\n    | left_elbow joint angle | 0.006 |\n    | balance point z | 0.020 |\n    | balance point y | 0.034 |\n    | balance point x | 0.044 |\n    | left_knee joint angle | 0.045 |\n\n    We remark that the state space does not include absolute coordinates; all x,y positions are measured relative to the model’s torso. We observe that the hardest coordinates to predict are usually velocity terms that require multiple frames to decode, and suffer from environment stochasticity and especially from occlusion. Also, note that all of these coordinates are essential for decision-making, rather than redundant latent variables. We thank the reviewer for raising this interesting question and we will make sure to add the comprehensive version of this result in the final version of the paper. \n    \n\nWe proceed to the reviewer’s other comments and questions.\n\n> Lack of comparison to asymmetric RL.\n\nAsymmetric RL is an exciting research direction that holds significant promise for balancing computational/statistical efficiency with accuracy. On these axes, we see it as almost a continuum of methods interpolating between expert distillation and standard RL — indeed, typical asymmetric RL methods combine aspects of both paradigms. Our goal in this paper was to understand the trade-offs between the two methods at the “extremes” — which are, to our knowledge, also the two most mainstream methods in applied vision-based robotics and autonomous driving [4,5]. \n\nThat said, we agree that obtaining a theoretical understanding of when asymmetric RL can achieve the best-of-both-worlds is an exciting direction for future research. Our theoretical framework could be an interesting jumping-off point for investigating these methods. We will expand our discussion of asymmetric RL in the paper to include these points.\n\n> Limited task diversity\n\nWe fully agree: as we mention in the paper, our conclusions are specific to the setting where observations are highly informative of the latent state, which is realistic in e.g. image-based robotics but certainly unrealistic in many other domains. That said, the most general theory for POMDPs asserts that learning and planning are statistically and computationally intractable [3]. Such a general theory is too pessimistic for any practical guidance, and thus we believe more fine-grained theory is necessary to understand real-world POMDP problems. \n\n> Is there a theoretical or empirical distinction between injecting noise into actions, observations, or latent state transitions? How do these different sources of stochasticity affect decodability and distillation?\n\nInjecting noise into actions is a specific method of injecting latent state transition noise. We chose this particular type of transition noise since it is well-motivated by real-world robotics systems. As for observation noise, this is exactly the construction of our key setting, perturbed block MDPs, where the observation can be understood as a noisy measurement of the latent state. Our theory shows that (1) with observation noise but without action noise, decodability (and hence the performance of distillation) improves as framestack increases, but (2) with observation noise and action noise, decodability is fundamentally limited by the observation noise. Without observation noise, the latent expert is the same as the POMDP expert, so distillation is trivial (regardless of action noise). Thus, there is indeed a distinction between action noise and observation noise.\n\n> In the stochastic setting, is the privileged expert trained with noise injected into the latent MDP, or is it trained on the original (noise-free) latent MDP?\n\nIn the stochastic setting (Sec 5.2), we trained the expert and the student on the same MDP — i.e., with noise injected into the latent MDP. We will better clarify this point in the revised version. \n\n> What is the relationship between environment noise and expert smoothing noise? For instance, does higher environment noise require a higher level of expert smoothing? Could expert smoothing still help in environments with no noise?\n\nThis is an interesting question — we do not have a complete understanding of how the environment’s inherent stochasticity affects the optimal smoothing noise. In the extreme case where the environment is deterministic, our theory suggests that expert smoothing should not really help, as expert distillation is already near-optimal (with sufficient frame-stacking). For the rebuttal, we conducted this experiment (with $L$=3, the same setting as Fig.4, except no motor noise in the latent dynamics) and it confirms the theory (expert noise denotes expert trained under latent mdp with motor noise $n$):\n\n| expert noise |  0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 |\n| --- | --- | --- | --- | --- | --- | --- |\n| dog | 722.5 | 696.8 | 673.6 | 673.3 | 688.4 | 689.7 |\n| humanoid | 739.1 | 676.6 | 680.5 | 683.7 | 677.1 | 654.0 |\n\n> Can the authors comment on whether the deterministic filter condition from [1] relates to their assumptions in Section 4? Is it possible to extend the results for deterministic dynamics to this broader condition?\n\nGood question, we will clarify this point in the paper. The deterministic filter condition is the same as perfect $H$-step decodability as defined in our paper. However, it is not actually broader than the setting of Proposition 4.1, because $\\delta$-perturbed Block MDPs generically have positive decodability error, even with deterministic transitions. It is unclear if the setting can be relaxed further, but some assumptions on the emission distribution are definitely necessary [3].\n\n> discussions on the paradigm introduced in [2]\n\nWe appreciate the reviewer for pointing out this related work. We were not aware of this paper as it showed up after the submission deadline. That said, we believe [2] is highly relevant as it also considers POMDPs with privileged latent information. The paper proposes a practical teacher-student co-training algorithm that achieves competitive performance on several benchmarks. It focuses on settings where active information gathering is crucial, which is complementary to the focus of our work but an exciting direction for future theoretical investigation. We will make sure to discuss it in our final version. \n\n[1] Cai, Y, et al. Provable partially observable reinforcement learning with privileged information.\n\n[2] Li, Y, et al. Guided Policy Optimization under Partial Observability.\n\n[3] Jin, C, et al. Sample-efficient reinforcement learning of undercomplete pomdps.\n\n[4] Ibarz, J, et al. How to train your robot with deep reinforcement learning: lessons we have learned.\n\n[5] Tang, C, et al. Deep reinforcement learning for robotics: A survey of real-world successes."}]

Author rebuttal:

Meta-review: This paper studies the trade-off between privileged expert distillation (training with access to latent states) and standard RL without privileged information in partially observable environments. It introduces the perturbed block MDP as a theoretical model to compare approximate decodability (favoring distillation) vs. belief contraction (favoring RL). Experiments on locomotion tasks show that distillation is efficient and competitive under deterministic dynamics, but performance degrades under stochastic dynamics where RL would bennefit from frame-stacking. The authors further propose smoothing latent experts (adding motor noise during training) as a lightweight way to improve distillation robustness.

This is a very interesting paper that poses a very clear question and provides clear insights about algorithmic decisions that come up frequently in robotics and sequential decision-making with partial observability in general. The paper has theoretical novelty in terms of introducing approximate decodability. The perturbed block MDP model provides a clear framework for analyzing trade-offs between distillation and RL in POMDPs. The paper also combines formal analysis with controlled experiments on challenging locomotion tasks.  

In terms of weaknesses, one of the most notable is that the analysis does not cover tasks requiring exploration purely for state disambiguation, where distillation may fundamentally fail. Additionally, while the paper offers guidelines, the decision over distilling vs. RL remains qualitative.

Reviewers were satisfied with the technical contributions of the paper. Many (minor) issues and clarifications were addressed during the rebuttal, while some limitations, such as comparison or analysis of asymmetric RL, remain and could not be accomplished during the course of the rebuttal. That said, there is unanimous support among reviewers that the paper is a strong contribution, and I agree with them. I recommend that the paper be accepted.
Decision: Accept (spotlight)